// Copyright (c) 2020-2021 Thomas Kramer.
// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
//
// SPDX-License-Identifier: AGPL-3.0-or-later

//! Trait for a simplified router.

use crate::db;
use db::{Geometry, Point, Rect, SInt, SimpleRPolygon};
use db::{L2NBase, L2NEdit};
use db::{ToPolygon, Translate};
use num_traits::{NumCast, PrimInt};
use std::collections::{HashMap, HashSet};

/// Represents a routed net.
pub struct SimpleRoutedNet<T = SInt> {
    /// Geometries of the metal wires as a list of `(layer, geometry)` tuples.
    pub routes: Vec<(u8, Geometry<T>)>,
    /// Locations of vias as `(layer1, layer2, location)` tuples.
    pub vias: Vec<(u8, u8, Point<T>)>,
}

/// Basic trait for a router with a simplified interface.
///
/// The simplified router gets as an input an already flattened set of
/// net terminal shapes that need to be connected.
pub trait SimpleRouter {
    /// Get the name of the routing engine.
    fn name(&self) -> &str;

    /// Routing algorithm implementation.
    fn compute_routes_impl(
        &self,
        boundary: Rect<SInt>,
        net_terminals: &HashMap<usize, Vec<Vec<(SimpleRPolygon<SInt>, u8)>>>,
        obstacles: &Vec<(SimpleRPolygon<SInt>, u8)>,
    ) -> HashMap<usize, SimpleRoutedNet>;

    /// Wrapper around `compute_route_impl()`.
    /// Does some sanity checks before and after.
    ///
    /// * `boundary`: Boundary of the area that can be used for the routing.
    /// * `net_terminals`: Pin shapes for each net together with the layer number. Lowest layer is `0`.
    /// * `obstacles`: Obstacle shapes together with the layer number.
    ///
    /// Returns all freshly drawn routes.
    fn compute_routes(
        &self,
        boundary: Rect<SInt>,
        net_terminals: &HashMap<usize, Vec<Vec<(SimpleRPolygon<SInt>, u8)>>>,
        obstacles: &Vec<(SimpleRPolygon<SInt>, u8)>,
    ) -> HashMap<usize, SimpleRoutedNet> {
        self.compute_routes_impl(boundary, net_terminals, obstacles)
    }

    /// Draw the computed routes into the layout.
    ///
    /// * `routes`: Routes computed with `compute_routes()`.
    /// * `routes_cell`: The cell where to draw the routes into.
    /// * `routing_layers`: The metal layer stack starting with the layer ID of the lowest metal layer.
    /// * `via_layers`: IDs of the via layers, starting with the lowest via layer which is the
    /// via layer between the first two metal layers.
    fn draw_routes<LN: L2NEdit<Coord = db::SInt>>(
        &self,
        chip: &mut LN,
        routes: HashMap<usize, SimpleRoutedNet>,
        routes_cell: LN::CellId,
        routing_layers: &Vec<LN::LayerId>,
        via_layers: &Vec<LN::LayerId>,
    ) {
        for (_net, routed_net) in routes {
            // Draw routing paths.

            // Draw wires.
            for (layer, shape) in routed_net.routes {
                if layer as usize > routing_layers.len() {
                    log::error!("Route uses more layers than specified in the layerstack.");
                }

                chip.insert_shape(&routes_cell, &routing_layers[layer as usize], shape);
            }

            // Draw vias.
            let via_shape0 = db::Rect::new((-20, -20), (20, 20));
            for (layer1, layer2, location) in routed_net.vias {
                assert_eq!(
                    layer1 + 1,
                    layer2,
                    "Invalid via between two non-neighbour layers."
                );
                let via_shape = via_shape0.translate(location.into());
                chip.insert_shape(&routes_cell, &via_layers[layer1 as usize], via_shape.into());
            }
        }
    }

    /// Route all nets in the `top_cell`.
    /// * `top_cell`: The cell containing the layout to be routed.
    /// * `routing_layers`: The metal layer stack starting with the layer ID of the lowest metal layer.
    /// * `via_layers`: IDs of the via layers, starting with the lowest via layer which is the
    /// via layer between the first two metal layers.
    ///
    /// # Returns
    /// * On success returns `Ok(())`.
    /// * On failure, when some nets could not be routed returns a list of the unrouted nets `Err(unrouted nets)`.
    fn route_all_nets<LN: L2NEdit<Coord = db::SInt>>(
        &self,
        chip: &mut LN,
        top_cell: LN::CellId,
        routing_layers: &Vec<LN::LayerId>,
        via_layers: &Vec<LN::LayerId>,
    ) -> Result<(), Vec<LN::NetId>> {
        let nets = chip.each_internal_net_vec(&top_cell);
        self.route_nets(chip, top_cell, routing_layers, via_layers, &nets)
    }

    /// Route a set of nets and creates a new cell that contains the shapes of the routes.
    /// Also outputs the routing terminal shapes to this cell (for debugging).
    ///
    /// * `top_cell`: The cell containing the layout to be routed.
    /// * `routing_layers`: The metal layer stack starting with the layer ID of the lowest metal layer.
    /// * `via_layers`: IDs of the via layers, starting with the lowest via layer which is the
    /// via layer between the first two metal layers.
    /// * `nets`: The nets to be routed.
    ///
    /// # Returns
    /// * On success returns `Ok(())`.
    /// * On failure, when some nets could not be routed returns a list of the unrouted nets `Err(unrouted nets)`.
    fn route_nets<LN: L2NEdit<Coord = db::SInt>>(
        &self,
        chip: &mut LN,
        top_cell: LN::CellId,
        routing_layers: &Vec<LN::LayerId>, // TODO: Store technology information in the router implementation.
        via_layers: &Vec<LN::LayerId>, // TODO: Store technology information in the router implementation.
        nets: &Vec<LN::NetId>,
    ) -> Result<(), Vec<LN::NetId>> {
        log::info!("Start router '{}'.", self.name());
        assert_eq!(
            routing_layers.len(),
            via_layers.len() + 1,
            "There must be exactly one more routing layer than via layers."
        );

        // ** PREPARE for ROUTING **
        //
        // Draw layout of routing terminals, i.e. pin shapes of cells and macros.
        // Create flat structure of routing terminals.
        // Plot pin shapes and net names.

        // Create a cell which will contain the extracted routing terminals, i.e. cell pins.
        let routing_cell = // Find a unused name for the cell containing the routes.
            (0..).into_iter()
                .map(|i| format!("routes_{}_{}", self.name(), i))
                .find(|name| chip.cell_by_name(name).is_none())
                .map(|name| chip.create_cell(
                    name.into()
                ))
                .unwrap();

        let routing_terminal_cell_inst = chip.create_cell_instance(&top_cell, &routing_cell, None);
        chip.set_transform(&routing_terminal_cell_inst, db::SimpleTransform::identity());

        // Find geometries of terminals for each net.
        let net_terminals =
            extract_and_plot_net_terminal_geometries(chip, &top_cell, Some(&routing_cell));

        // Take only nets that should be routed.
        let nets_set: HashSet<_> = nets.iter().cloned().collect();
        let net_terminals: HashMap<_, _> = net_terminals
            .into_iter()
            .filter(|(n, _)| nets_set.contains(n))
            .collect();

        // Print some statistics on terminals.
        let num_terminals: usize = net_terminals.values().map(|t| t.len()).sum();
        let num_one_terminal_nets = net_terminals.iter().filter(|(_, t)| t.len() <= 1).count();
        log::info!("Number of nets with terminals: {}", net_terminals.len());
        log::info!("Number of net terminals: {}", num_terminals);
        if num_one_terminal_nets > 0 {
            log::warn!(
                "Number of nets with less than two terminals: {}",
                num_one_terminal_nets
            );
        }

        // Mapping from layer IDs to subsequent layer numbers.
        let layer_numbers: HashMap<_, _> = routing_layers
            .iter()
            .enumerate()
            .map(|(i, layer)| (layer.clone(), i as u8))
            .collect();

        // Convert terminals into rectilinear polygons.
        let net_terminals: HashMap<_, _> = net_terminals
            .into_iter()
            .map(|(net, terminals)| {
                let r_terminals: Vec<_> = terminals
                    .into_iter()
                    .map(|(t, layer)| {
                        assert_eq!(
                            t.interiors.len(),
                            0,
                            "Polygons with holes are not supported."
                        );
                        vec![(
                            SimpleRPolygon::try_new(t.exterior.points())
                                .expect("Only rectilinear polygons are supported"),
                            layer_numbers[&layer],
                        )] // Assign correct layer.
                    })
                    .collect();
                (net, r_terminals)
            })
            .collect();

        // Create a set of obstacles.
        // For testing everything is put on a single layer.
        let mut obstacles: Vec<_> = net_terminals
            .values()
            .flat_map(|terminals| terminals.iter().flatten().cloned())
            .collect();

        debug_assert!(
            obstacles
                .iter()
                .all(|(poly, _)| poly.orientation().is_counter_clock_wise()),
            "Obstacle polygons must have counter-clock-wise orientation."
        );

        // Get the bounding box of the top cell.
        let top_cell_bounding_box = chip.bounding_box(&top_cell).unwrap();

        assert!(routing_layers.len() <= u8::MAX as usize);
        let num_layers = routing_layers.len() as u8;

        // Draw a boundary shape around the core on all layers.
        // for layer in 0..num_layers {
        //     // Add core boundary on each layer.
        //     // TODO: Needed for line-search router only.
        //     let bbox = top_cell_bounding_box.sized(1, 1);
        //     let bbox_outer = bbox.sized(1, 1);
        //     let boundary_inner: db::SimpleRPolygon<_> = bbox.into();
        //     let boundary_outer: db::SimpleRPolygon<_> = bbox_outer.into();
        //     let boundary_outer = boundary_outer.reversed();
        //     obstacles.push(
        //         // Containing box.
        //         // Hole (oriented clock wise).
        //         (boundary_inner, layer)
        //     );
        //
        //     obstacles.push(
        //         // Outer border (oriented counter-clock wise).
        //         (boundary_outer, layer),
        //     );
        // }

        // Register existing shapes such as the power grid as obstacles.

        for (layer_num, layer) in routing_layers.iter().enumerate() {
            let layer_info = chip.layer_info(layer);
            log::info!(
                "Find obstacles on layer {}/{} (name={:?})",
                layer_info.index,
                layer_info.datatype,
                layer_info.name
            );
            // let mut debug_shapes = Vec::new();
            chip.for_each_shape_recursive(&top_cell, layer, |tf, _id, shape| {
                let poly = shape.transformed(&tf).to_polygon();
                assert_eq!(
                    poly.interiors.len(),
                    0,
                    "Polygons with holes are not supported."
                );

                let rpoly = SimpleRPolygon::try_new(poly.exterior.points())
                    .expect("Only rectilinear polygons are supported");

                // debug_shapes.push((rpoly.clone(), layer.clone()));
                obstacles.push((rpoly, layer_num as u8));
            });
        }
        log::info!("Number of obstacle shapes: {}", obstacles.len());

        // Replace net IDs by identifiers of type usize.
        // Create lookup table for the net-to-ID mapping.
        let nets_to_be_routed: Vec<_> = net_terminals.keys().cloned().collect();
        let net_id_lookup_table: HashMap<_, _> = nets_to_be_routed
            .iter()
            .enumerate()
            .map(|(i, net)| (net.clone(), i))
            .collect();
        // Replace net IDs with integers.
        let terminals = net_terminals
            .into_iter()
            .map(|(net, terms)| (net_id_lookup_table[&net], terms))
            .collect();

        // TODO: This sizing is arbitrary.
        let boundary = top_cell_bounding_box.sized(4000, 4000);

        assert!(num_layers <= u8::MAX);

        let result = self.compute_routes(boundary, &terminals, &obstacles);

        // Find nets that have not been routed.
        let unrouted_nets: Vec<_> = nets_to_be_routed
            .iter()
            .filter(|&n| !result.contains_key(&net_id_lookup_table[n]))
            .cloned()
            .collect();

        self.draw_routes(chip, result, routing_cell, routing_layers, via_layers);

        if unrouted_nets.is_empty() {
            Ok(())
        } else {
            Err(unrouted_nets)
        }
    }
}

/// Extract the flattened terminal geometries of all nets in the `top_cell`.
pub fn extract_net_terminal_geometries<LN>(
    chip: &LN,
    top_cell: &LN::CellId,
) -> HashMap<LN::NetId, Vec<(db::Polygon<LN::Coord>, LN::LayerId)>>
where
    LN: L2NBase,
    LN::Coord: PrimInt + NumCast,
{
    // Terminal shapes for each net.
    // This shapes need to be connected by the router.
    let mut net_terminals = HashMap::new();

    log::info!("Extract net terminals.");
    // Create all pin shapes and associate them with the connected net.
    for circuit_inst in chip.each_cell_instance_vec(&top_cell) {
        let template_circuit = chip.template_cell(&circuit_inst);
        let circuit_name = chip.cell_name(&template_circuit);
        log::debug!("Find net terminals of cell '{}'.", &circuit_name);

        let cell_position = Some(chip.get_transform(&circuit_inst));
        // TODO: Assert that the cell is marked as 'placed'. Needs additional attributes.

        if let Some(cell_position) = cell_position {
            for pin_inst in chip.each_pin_instance_vec(&circuit_inst) {
                let pin = chip.template_pin(&pin_inst);

                let pin_name = chip.pin_name(&pin);

                // Get the layout shapes of the pin.
                let pin_shapes: Vec<_> = chip.shapes_of_pin(&pin).collect();

                if pin_shapes.is_empty() {
                    log::warn!(
                        "No pin shape found for pin '{}' in cell '{}'.",
                        &pin_name,
                        &circuit_name
                    );
                }

                // Get signal direction of the pin.
                let signal_direction = chip.pin_direction(&pin);

                // Find net connected to this pin.
                if let Some(net) = chip.net_of_pin_instance(&pin_inst) {
                    let terminals = net_terminals.entry(net).or_insert(Vec::new());

                    let mut pin_geometries = vec![];
                    for pin_shape in &pin_shapes {
                        chip.with_shape(pin_shape, |layer, g| {
                            pin_geometries.push((layer.clone(), g.clone()))
                        })
                    }

                    for (pin_shape_layer, geo) in pin_geometries {
                        // Create a transformed copy of the pin shape.
                        let geo_tf = geo.transformed(&cell_position);

                        // Remember the terminal of this net.
                        let terminal = (geo_tf.to_polygon(), pin_shape_layer.clone());
                        if signal_direction.is_output() {
                            // Put the signal source first.
                            terminals.insert(0, terminal);
                        } else {
                            terminals.push(terminal);
                        }
                    }
                }
            }
        } else {
            let inst_name = chip
                .cell_instance_name(&circuit_inst)
                .map(|s| s.to_string())
                .unwrap_or_else(|| "<unnamed>".to_string());
            log::warn!(
                "No position found for cell '{}' (type '{}').",
                inst_name,
                circuit_name
            );
        }
    }
    net_terminals
}

// TODO: Remove this.
/// Extract the flattened terminal geometries of all nets in the `top_cell`.
/// If the `destination_cell` is given, the terminals will be written to its layout with additional
/// text annotations for debugging.
pub fn extract_and_plot_net_terminal_geometries<LN>(
    chip: &mut LN,
    top_cell: &LN::CellId,
    destination_cell: Option<&LN::CellId>,
) -> HashMap<LN::NetId, Vec<(db::Polygon<LN::Coord>, LN::LayerId)>>
where
    LN: L2NEdit,
    LN::Coord: PrimInt + NumCast,
{
    let net_terminals = extract_net_terminal_geometries(chip, top_cell);

    if let Some(destination_cell) = destination_cell {
        // Property key for the net property.
        let property_key_net = LN::NameType::from("net".to_string());

        for (net, terminals) in &net_terminals {
            for (polygon, layer) in terminals {
                // Add the terminal shape to the cell with routing terminals.
                let shape = chip.insert_shape(destination_cell, &layer, polygon.clone().into());

                // Store the net name in the layout as property and text label.
                if let Some(net_name) = &chip.net_name(net) {
                    chip.set_shape_property(
                        &shape,
                        property_key_net.clone(),
                        net_name.to_string().into(),
                    );

                    // // Add a label for debugging.
                    let label_location = polygon.exterior.points()[0];

                    let text = db::Text::new(net_name.to_string(), label_location).into();
                    chip.insert_shape(destination_cell, &layer, text);
                }
            }
        }
    }

    net_terminals
}