#include "RoutingGraph.hpp"
#include "Chip.hpp"
#include "Tile.hpp"
#include <regex>
#include <iostream>
#include <algorithm>

namespace Trellis {

// This is ignored for the MachXO2 family- globals are handled during routing
// graph creation.
const Location GlobalLoc(-2, -2);

RoutingGraph::RoutingGraph(const Chip &c) : chip_name(c.info.name), chip_family(c.info.family), max_row(c.get_max_row()), max_col(c.get_max_col())
{
    tiles[GlobalLoc].loc = GlobalLoc;
    for (int y = 0; y <= max_row; y++) {
        for (int x = 0; x <= max_col; x++) {
            Location loc(x, y);
            tiles[loc].loc = loc;
        }
    }
    if (chip_name.find("25F") != string::npos || chip_name.find("12F") != string::npos)
        chip_prefix = "25K_";
    else if (chip_name.find("45F") != string::npos)
        chip_prefix = "45K_";
    else if (chip_name.find("85F") != string::npos)
        chip_prefix = "85K_";
    else if (chip_name.find("1200HC") != string::npos)
        // FIXME: Prefix to distinguish XO, XO2, and XO3?
        chip_prefix = "1200_";
    else
        assert(false);

    if(c.info.family == "MachXO2")
        global_data_machxo2 = get_global_info_machxo2(DeviceLocator{c.info.family, c.info.name});
}

ident_t IdStore::ident(const std::string &str) const
{
    if (str_to_id.find(str) != str_to_id.end()) {
        return str_to_id.at(str);
    } else {
        str_to_id[str] = int(identifiers.size());
        identifiers.push_back(str);
        return str_to_id.at(str);
    }
}

std::string IdStore::to_str(ident_t id) const
{
    return identifiers.at(id);
}

RoutingId IdStore::id_at_loc(int16_t x, int16_t y, const std::string &str) const
{
    RoutingId rid;
    rid.id = ident(str);
    rid.loc = Location(x, y);
    return rid;
}

RoutingId RoutingGraph::globalise_net(int row, int col, const std::string &db_name)
{
    if(chip_family == "ECP5") {
        return globalise_net_ecp5(row, col, db_name);
    } else if(chip_family == "MachXO2") {
        return globalise_net_machxo2(row, col, db_name);
    } else
        throw runtime_error("Unknown chip family: " + chip_family);
}

RoutingId RoutingGraph::globalise_net_ecp5(int row, int col, const std::string &db_name)
{
    static const std::regex e(R"(^([NS]\d+)?([EW]\d+)?_(.*))", std::regex::optimize);
    std::string stripped_name = db_name;
    if (db_name.find("25K_") == 0 || db_name.find("45K_") == 0 || db_name.find("85K_") == 0) {
        if (db_name.substr(0, 4) == chip_prefix) {
            stripped_name = db_name.substr(4);
        } else {
            return RoutingId();
        }
    }
    // Workaround for PCSA/B sharing tile dbs
    if (col >= 69) {
        size_t pcsa_pos = stripped_name.find("PCSA");
        if (pcsa_pos != std::string::npos)
            stripped_name.replace(pcsa_pos + 3, 1, "B");
    }
    if (stripped_name.find("G_") == 0 || stripped_name.find("L_") == 0 || stripped_name.find("R_") == 0) {
        // Global net
        // TODO: quadrants and TAP_DRIVE regions
        // TAP_DRIVE and SPINE wires go in their respective tiles
        // Other globals are placed at a nominal location of (0, 0)
        RoutingId id;
        if (stripped_name.find("G_") == 0 && stripped_name.find("VPTX") == string::npos &&
            stripped_name.find("HPBX") == string::npos && stripped_name.find("HPRX") == string::npos) {
            id.loc.x = 0;
            id.loc.y = 0;
        } else {
            id.loc.x = int16_t(col);
            id.loc.y = int16_t(row);
        }
        id.id = ident(stripped_name);
        return id;
    } else {
        RoutingId id;
        id.loc.x = int16_t(col);
        id.loc.y = int16_t(row);
        // Local net, process prefix
        smatch m;
        if (regex_match(stripped_name, m, e)) {
            for (int i = 1; i < int(m.size()) - 1; i++) {
                string g = m.str(i);
                if (g.empty()) continue;
                if (g[0] == 'N') id.loc.y -= std::stoi(g.substr(1));
                else if (g[0] == 'S') id.loc.y += std::stoi(g.substr(1));
                else if (g[0] == 'W') id.loc.x -= std::stoi(g.substr(1));
                else if (g[0] == 'E') id.loc.x += std::stoi(g.substr(1));
                else
                    assert(false);
            }
            id.id = ident(m.str(m.size() - 1));
        } else {
            id.id = ident(stripped_name);
        }
        if (id.loc.x < 0 || id.loc.x > max_col || id.loc.y < 0 || id.loc.y > max_row)
            return RoutingId(); // TODO: handle edge nets properly
        return id;
    }
}

RoutingId RoutingGraph::globalise_net_machxo2(int row, int col, const std::string &db_name)
{
  static const std::regex e(R"(^([NS]\d+)?([EW]\d+)?_(.*))", std::regex::optimize);
  std::string stripped_name = db_name;

  if (db_name.find("256_") == 0 || db_name.find("640_") == 0) {
      if (db_name.substr(0, 4) == chip_prefix) {
          stripped_name = db_name.substr(4);
      } else {
          return RoutingId();
      }
  }

  if (db_name.find("1200_") == 0 || db_name.find("2000_") == 0 ||
      db_name.find("4000_") == 0 || db_name.find("7000_") == 0) {
      if (db_name.substr(0, 5) == chip_prefix) {
          stripped_name = db_name.substr(5);
      } else {
          return RoutingId();
      }
  }

  if (stripped_name.find("G_") == 0 || stripped_name.find("L_") == 0 || stripped_name.find("R_") == 0 ||
      stripped_name.find("U_") == 0 || stripped_name.find("D_") == 0 || stripped_name.find("BRANCH_") == 0) {
      // Global prefix detected, use the prefix and row/col to map "logical"
      // globals on a tile basis to physical globals which are shared between
      // tiles.
      return find_machxo2_global_position(row, col, stripped_name);
  } else {
      RoutingId id;
      id.loc.x = int16_t(col);
      id.loc.y = int16_t(row);
      // Local net, process prefix
      smatch m;
      if (regex_match(stripped_name, m, e)) {
          for (int i = 1; i < int(m.size()) - 1; i++) {
              string g = m.str(i);
              if (g.empty()) continue;
              if (g[0] == 'N') id.loc.y -= std::stoi(g.substr(1));
              else if (g[0] == 'S') id.loc.y += std::stoi(g.substr(1));
              else if (g[0] == 'W') {
                  id.loc.x -= std::stoi(g.substr(1));

                  if(id.loc.x < 0) {
                      // Special case: PIO wires on left side have a relative
                      // position placing them outside the chip thanks to MachXO2's
                      // wonderful 1-based column numbering, and lack of dedicated
                      // PIO tiles on the left and right.
                      // Top and bottom unaffected due to dedicated PIO tiles.
                      // TODO: Convert to regex.
                      bool pio_wire = (
                          db_name.find("DI") != string::npos ||
                          db_name.find("JDI") != string::npos ||
                          db_name.find("PADD") != string::npos ||
                          db_name.find("INDD") != string::npos ||
                          db_name.find("IOLDO") != string::npos ||
                          db_name.find("IOLTO") != string::npos ||
                          db_name.find("JCE") != string::npos ||
                          db_name.find("JCLK") != string::npos ||
                          db_name.find("JLSR") != string::npos ||
                          db_name.find("JONEG") != string::npos ||
                          db_name.find("JOPOS") != string::npos ||
                          db_name.find("JTS") != string::npos ||
                          db_name.find("JIN") != string::npos ||
                          db_name.find("JIP") != string::npos ||
                          // Connections to global mux
                          db_name.find("JINCK") != string::npos
                      );

                      if((id.loc.x == -1) && pio_wire)
                          id.loc.x = 0;
                  }
              }
              else if (g[0] == 'E') {
                  id.loc.x += std::stoi(g.substr(1));

                  if(id.loc.x > max_col) {
                      bool pio_wire = (
                          db_name.find("DI") != string::npos ||
                          db_name.find("JDI") != string::npos ||
                          db_name.find("PADD") != string::npos ||
                          db_name.find("INDD") != string::npos ||
                          db_name.find("IOLDO") != string::npos ||
                          db_name.find("IOLTO") != string::npos ||
                          db_name.find("JCE") != string::npos ||
                          db_name.find("JCLK") != string::npos ||
                          db_name.find("JLSR") != string::npos ||
                          db_name.find("JONEG") != string::npos ||
                          db_name.find("JOPOS") != string::npos ||
                          db_name.find("JTS") != string::npos ||
                          db_name.find("JIN") != string::npos ||
                          db_name.find("JIP") != string::npos ||
                          // Connections to global mux
                          db_name.find("JINCK") != string::npos
                      );

                      // Same deal as left side, except the position exceeds
                      // the maximum row.
                      // TODO: Should this become part of general edge-handling
                      // code, rather than a special case in the generic relative-
                      // position logic?
                      if((id.loc.x == max_col + 1) && pio_wire)
                          id.loc.x = max_col;
                  }
              }
              else
                  assert(false);
          }
          id.id = ident(m.str(m.size() - 1));
      } else {
          id.id = ident(stripped_name);
      }
      if (id.loc.x < 0 || id.loc.x > max_col || id.loc.y < 0 || id.loc.y > max_row)
          return RoutingId(); // TODO: handle edge nets properly
      return id;
  }
}

void RoutingGraph::add_arc(Location loc, const RoutingArc &arc)
{
    RoutingId arcId;
    arcId.loc = loc;
    arcId.id = arc.id;
    add_wire(arc.source);
    add_wire(arc.sink);
    tiles[loc].arcs[arc.id] = arc;
    tiles[arc.sink.loc].wires.at(arc.sink.id).uphill.push_back(arcId);
    tiles[arc.source.loc].wires.at(arc.source.id).downhill.push_back(arcId);
}

void RoutingGraph::add_wire(RoutingId wire)
{
    RoutingTileLoc &tile = tiles[wire.loc];
    if (tile.wires.find(wire.id) == tile.wires.end()) {
        RoutingWire rw;
        rw.id = wire.id;
        tiles[wire.loc].wires[rw.id] = rw;
    }
}

void RoutingGraph::add_bel(RoutingBel &bel)
{
    tiles[bel.loc].bels[bel.name] = bel;
}

void RoutingGraph::add_bel_input(RoutingBel &bel, ident_t pin, int wire_x, int wire_y, ident_t wire_name) {
    RoutingId wireId, belId;
    wireId.id = wire_name;
    wireId.loc.x = wire_x;
    wireId.loc.y = wire_y;
    belId.id = bel.name;
    belId.loc = bel.loc;
    add_wire(wireId);
    bel.pins[pin] = make_pair(wireId, PORT_IN);
    tiles[wireId.loc].wires[wireId.id].belsDownhill.push_back(make_pair(belId, pin));
}

void RoutingGraph::add_bel_output(RoutingBel &bel, ident_t pin, int wire_x, int wire_y, ident_t wire_name) {
    RoutingId wireId, belId;
    wireId.id = wire_name;
    wireId.loc.x = wire_x;
    wireId.loc.y = wire_y;
    belId.id = bel.name;
    belId.loc = bel.loc;
    add_wire(wireId);
    bel.pins[pin] = make_pair(wireId, PORT_OUT);
    tiles[wireId.loc].wires[wireId.id].belsUphill.push_back(make_pair(belId, pin));
}

RoutingId RoutingGraph::find_machxo2_global_position(int row, int col, const std::string &db_name) {
    // Globals are given their nominal position, even if they span multiple
    // tiles, by the following rules (determined by a combination of regexes
    // on db_name and row/col):
    smatch m;
    pair<int, int> center = center_map[make_pair(max_row, max_col)];
    RoutingId curr_global;

    GlobalType strategy = get_global_type_from_name(db_name, m);

    // All globals in the center tile get a nominal position of the center
    // tile. We have to use regexes because a number of these connections
    // in the center mux have config bits spread across multiple tiles
    // (although few nets actually have routing bits which cross tiles).
    //
    // This handles L/R_HPSX as well. DCCs are handled a bit differently
    // until we can determine they only truly exist in center tile (the row,
    // col, and db_name will still be enough to distinguish them).
    if(strategy == GlobalType::CENTER) {
        // Some arcs, like those which connect to VPRXCLKI0 in the 1200HC part
        // may appear more than once. We assume that open tools like nextpnr
        // are able to tolerate the same physical arc appearing twice in the
        // routing graph without any problems. This should also make bitstream
        // generation easier if the open tools make sure to set an arc as used
        // in each tile where it exists.
        curr_global.id = ident(db_name);
        curr_global.loc.x = center.second;
        curr_global.loc.y = center.first;
        return curr_global;

    // If we found a global emanating from the CENTER MUX, return a L_/R_
    // global net in the center tile based upon the current tile position
    // (specifically column).
    } else if(strategy == GlobalType::LEFT_RIGHT) {
        assert(row == center.first);
        // Prefixes only required in the center tile.
        assert(db_name[0] == 'G');

        std::string db_copy = db_name;

        // Center column tiles connect to the left side of the center mux.
        if(col <= center.second)
            db_copy[0] = 'L';
        else
            db_copy[0] = 'R';

        curr_global.id = ident(db_copy);
        curr_global.loc.x = center.second;
        curr_global.loc.y = center.first;
        return curr_global;

    // U/D wires get the nominal position of center row, current column.
    // Both U_/D_ and G_ prefixes are handled here.
    } else if(strategy == GlobalType::UP_DOWN) {
        std::string db_copy = db_name;
        std::vector<int> & ud_conns_in_col = global_data_machxo2.ud_conns[col];
        auto conn_begin = ud_conns_in_col.begin();
        auto conn_end = ud_conns_in_col.end();
        int conn_no = std::stoi(m.str(1));

        // First check whether the requested global is in the current column.
        // If not, no point in continuing.
        if(std::find(conn_begin, conn_end, conn_no) == conn_end)
            return RoutingId();

        // Special case the center row, which will have both U/D wires.
        if(row == center.first) {
            assert((db_name[0] == 'U') || (db_name[0] == 'D'));
        } else {
            // Otherwise choose an U_/D_ wire at nominal position based on
            // the current tile's row.
            // Prefixes only required in the center row.
            assert(db_name[0] == 'G');

            // Center column tiles are considered above the center mux,
            // despite sharing the same tile.
            if(row <= center.first)
                db_copy[0] = 'U';
            else
                db_copy[0] = 'D';
        }

        curr_global.id = ident(db_copy);
        curr_global.loc.x = col;
        curr_global.loc.y = center.first;
        return curr_global;

    // BRANCH wires get nominal position of the row/col where they connect
    // to U_/D_ routing. We need the global_data_machxo2 struct to figure
    // out this information.
    } else if(strategy == GlobalType::BRANCH) {
        std::vector<int> candidate_cols;

        if(col > 1)
            candidate_cols.push_back(col - 2);
        if(col > 0)
            candidate_cols.push_back(col - 1);
        candidate_cols.push_back(col);
        if(col < max_col)
            candidate_cols.push_back(col + 1);

        for(auto curr_col : candidate_cols) {
            std::vector<int> & ud_conns_in_col = global_data_machxo2.ud_conns[curr_col];
            auto conn_begin = ud_conns_in_col.begin();
            auto conn_end = ud_conns_in_col.end();
            int conn_no = std::stoi(m.str(1));

            // First check whether the requested global is in the current column.
            // If not, no point in continuing.
            if(std::find(conn_begin, conn_end, conn_no) != conn_end) {
                curr_global.id = ident(db_name);
                curr_global.loc.x = curr_col;
                curr_global.loc.y = row;
                break;
            }
        }

        // One of the candidate columns should have had the correct U/D
        // connection to route to.
        assert(curr_global != RoutingId());
        return curr_global;

    // For OSCH, and DCCs assign nominal position of current requested tile.
    // DCM only exist in center tile but have their routing spread out
    // across tiles.
    } else if(strategy == GlobalType::OTHER) {
        curr_global.id = ident(db_name);
        curr_global.loc.x = col;
        curr_global.loc.y = row;
        return curr_global;
    } else {
        // TODO: Not fuzzed and/or handled yet!
        return RoutingId();
    }
}

RoutingGraph::GlobalType RoutingGraph::get_global_type_from_name(const std::string &db_name, smatch &match) {
    // A RoutingId uniquely describes a net on the chip- using a string
    // identifier (id- converted to int), and a nominal position (loc).
    // Two RoutingIds with the same id and loc represent the same net, so
    // we can use heuristics to connect globals to the rest of the routing
    // graph properly, given the current tile position and the global's
    // identifier.

    // First copy regexes from utils.nets.machxo2, adjusting as necessary for
    // prefixes and regex syntax. Commented-out ones are not ready yet:
    // Globals
    static const std::regex global_entry(R"(G_VPRX(\d){2}00)", std::regex::optimize);
    static const std::regex global_left_right(R"([LR]_HPSX(\d){2}00)", std::regex::optimize);
    static const std::regex global_left_right_g(R"(G_HPSX(\d){2}00)", std::regex::optimize);
    static const std::regex global_up_down(R"([UD]_VPTX(\d){2}00)", std::regex::optimize);
    static const std::regex global_up_down_g(R"(G_VPTX(\d){2}00)", std::regex::optimize);
    static const std::regex global_branch(R"(BRANCH_HPBX(\d){2}00)", std::regex::optimize);

    // High Fanout Secondary Nets
    // static const std::regex hfsn_entry(R"(G_VSRX(\d){2}00)", std::regex::optimize);
    // static const std::regex hfsn_left_right(R"(G_HSSX(\d){2}00)", std::regex::optimize);
    // L2Rs control bidirectional portion of HFSNs!!
    // static const std::regex hfsn_l2r(R"(G_HSSX(\d){2}00_[RL]2[LR])", std::regex::optimize);
    // static const std::regex hfsn_up_down(R"(G_VSTX(\d){2}00)", std::regex::optimize);
    // HSBX(\d){2}00 are fixed connections to HSBX(\d){2}01s.
    // static const std::regex hfsn_branch(R"(G_HSBX(\d){2}0[01])", std::regex::optimize);

    // Center Mux
    // Outputs- entry to DCCs connected to globals (VPRXI -> DCC -> VPRX) *
    static const std::regex center_mux_glb_out(R"(G_VPRXCLKI\d+)", std::regex::optimize);
    // Outputs- connected to ECLKBRIDGEs *
    // static const std::regex center_mux_ebrg_out(R"(G_EBRG(\d){1}CLK(\d){1})", std::regex::optimize);

    // Inputs- CIB routing to HFSNs
    // static const std::regex cib_out_to_hfsn(R"(G_JSNETCIB([TBRL]|MID)(\d){1})", std::regex::optimize);
    // Inputs- CIB routing to globals
    static const std::regex cib_out_to_glb(R"(G_J?PCLKCIB(L[TBRL]Q|MID|VIQ[TBRL])(\d){1})", std::regex::optimize);
    // Inputs- CIB routing to ECLKBRIDGEs
    // static const std::regex cib_out_to_eclk(R"(G_J?ECLKCIB[TBRL](\d){1})", std::regex::optimize);

    // Inputs- Edge clocks dividers
    // static const std::regex eclk_out(R"(G_J?[TBRL]CDIV(X(\d){1}|(\d){2}))", std::regex::optimize);
    // Inputs- PLL
    // static const std::regex pll_out(R"(G_J?[LR]PLLCLK\d+)", std::regex::optimize);
    // Inputs- Clock pads
    // static const std::regex clock_pin(R"(G_J?PCLK[TBLR]\d+)", std::regex::optimize);

    // Part of center-mux but can also be found elsewhere
    // DCCs connected to globals *
    static const std::regex dcc_sig(R"(G_J?(CLK[IO]|CE)(\d){1}[TB]?_DCC)", std::regex::optimize);

    // DCMs- connected to DCCs on globals 6 and 7 *
    static const std::regex dcm_sig(R"(G_J?(CLK(\d){1}_|SEL|DCMOUT)(\d){1}_DCM)", std::regex::optimize);

    // ECLKBRIDGEs- TODO
    // static const std::regex eclkbridge_sig(R"(G_J?(CLK(\d){1}_|SEL|ECSOUT)(\d){1}_ECLKBRIDGECS)", std::regex::optimize);

    // Oscillator output
    static const std::regex osc_clk(R"(G_J?OSC_.*)", std::regex::optimize);

    // Soft Error Detection Clock *
    // static const std::regex sed_clk(R"(G_J?SEDCLKOUT)", std::regex::optimize);

    // PLL/DLL Clocks
    // static const std::regex pll_clk(R"(G_[TB]ECLK\d)", std::regex::optimize);

    // PG/INRD/LVDS
    // static const std::regex pg(R"(G_PG)", std::regex::optimize);
    // static const std::regex inrd(R"(G_INRD)", std::regex::optimize);
    // static const std::regex vds(R"(G_LVDS)", std::regex::optimize);

    // DDR
    // static const std::regex ddrclkpol(R"(G_DDRCLKPOL)", std::regex::optimize);
    // static const std::regex dqsr90(R"(G_DQSR90)", std::regex::optimize);
    // static const std::regex qsw90(R"(G_DQSW90)", std::regex::optimize);

    if(regex_match(db_name, match, global_entry) ||
        regex_match(db_name, match, global_left_right) ||
        regex_match(db_name, match, center_mux_glb_out) ||
        regex_match(db_name, match, cib_out_to_glb) ||
        regex_match(db_name, match, dcm_sig)) {
        return GlobalType::CENTER;
    } else if(regex_match(db_name, match, global_left_right_g)) {
        return GlobalType::LEFT_RIGHT;
    } else if(regex_match(db_name, match, global_up_down) ||
        regex_match(db_name, match, global_up_down_g)) {
        return GlobalType::UP_DOWN;
    } else if(regex_match(db_name, match, global_branch)) {
        return GlobalType::BRANCH;
    } else if(regex_match(db_name, match, dcc_sig) ||
        regex_match(db_name, match, osc_clk)) {
        return GlobalType::OTHER;
    } else {
        // TODO: Not fuzzed and/or handled yet!
        return GlobalType::NONE;
    }
}

}