// OpenSTA, Static Timing Analyzer
// Copyright (c) 2026, Parallax Software, Inc.
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <https://www.gnu.org/licenses/>.
//
// The origin of this software must not be misrepresented; you must not
// claim that you wrote the original software.
//
// Altered source versions must be plainly marked as such, and must not be
// misrepresented as being the original software.
//
// This notice may not be removed or altered from any source distribution.

#include "Genclks.hh"

#include <cmath>

#include "Clock.hh"
#include "ContainerHelpers.hh"
#include "Debug.hh"
#include "ExceptionPath.hh"
#include "Graph.hh"
#include "Levelize.hh"
#include "Mode.hh"
#include "Network.hh"
#include "Path.hh"
#include "PortDirection.hh"
#include "Report.hh"
#include "Scene.hh"
#include "Sdc.hh"
#include "Search.hh"
#include "SearchPred.hh"
#include "StaState.hh"
#include "Stats.hh"
#include "TagGroup.hh"
#include "Variables.hh"

namespace sta {

class GenclkInfo
{
public:
  GenclkInfo(Clock *gclk,
             Level gclk_level,
             FilterPath *src_filter,
             const StaState *sta);
  ~GenclkInfo();
  EdgeSet &fdbkEdges() { return fdbk_edges_; }
  VertexSet &fanins() { return fanins_; }
  Level gclkLevel() const { return gclk_level_; }
  FilterPath *srcFilter() const { return src_filter_; }
  bool foundLatchFdbkEdges() const { return found_latch_fdbk_edges_; }
  void setFoundLatchFdbkEdges(bool found);

protected:
  Clock *gclk_;
  Level gclk_level_;
  VertexSet fanins_;
  EdgeSet fdbk_edges_;
  bool found_latch_fdbk_edges_{false};
  FilterPath *src_filter_;
};

GenclkInfo::GenclkInfo(Clock *gclk,
                       Level gclk_level,
                       FilterPath *src_filter,
                       const StaState *sta) :
  gclk_(gclk),
  gclk_level_(gclk_level),
  fanins_(makeVertexSet(sta->graph())),
  src_filter_(src_filter)
{
}

GenclkInfo::~GenclkInfo() { delete src_filter_; }

void
GenclkInfo::setFoundLatchFdbkEdges(bool found)
{
  found_latch_fdbk_edges_ = found;
}

////////////////////////////////////////////////////////////////

Genclks::Genclks(const Mode *mode,
                 StaState *sta) :
  StaState(sta),
  mode_(mode),
  vertex_src_paths_map_(graph_)
{
}

Genclks::~Genclks()
{
  deleteContents(genclk_info_map_);
  clearSrcPaths();
}

void
Genclks::clear()
{
  found_insertion_delays_ = false;
  deleteContents(genclk_info_map_);
  clearSrcPaths();
}

VertexSet *
Genclks::fanins(const Clock *clk)
{
  GenclkInfo *genclk_info = genclkInfo(clk);
  if (genclk_info)
    return &genclk_info->fanins();
  else
    return nullptr;
}

Vertex *
Genclks::srcPath(const Pin *pin) const
{
  bool is_bidirect = network_->direction(pin)->isBidirect();
  // Insertion delay is to the driver vertex for clks defined on
  // bidirect pins.
  if (is_bidirect && network_->isLeaf(pin))
    return graph_->pinDrvrVertex(pin);
  else
    // Insertion delay is to the load vertex for clks defined on
    // bidirect ports.
    return graph_->pinLoadVertex(pin);
}

Level
Genclks::clkPinMaxLevel(const Clock *clk) const
{
  Level max_level = 0;
  for (const Pin *pin : clk->leafPins()) {
    Vertex *vertex = srcPath(pin);
    max_level = std::max(max_level, vertex->level());
  }
  return max_level;
}

class ClockPinMaxLevelLess
{
public:
  ClockPinMaxLevelLess(const Genclks *genclks);
  bool operator()(Clock *clk1,
                  Clock *clk2) const;

protected:
  const Genclks *genclks_;
};

ClockPinMaxLevelLess::ClockPinMaxLevelLess(const Genclks *genclks) :
  genclks_(genclks)
{
}

bool
ClockPinMaxLevelLess::operator()(Clock *clk1,
                                 Clock *clk2) const
{
  return genclks_->clkPinMaxLevel(clk1) < genclks_->clkPinMaxLevel(clk2);
}

// Generated clock source paths.
// The path between the source clock and generated clock is used
// to find the insertion delay (source latency) when the clock is
// propagated and for reporting path type "full_clock_expanded".
void
Genclks::ensureInsertionDelays()
{
  if (!found_insertion_delays_) {
    Stats stats(debug_, report_);
    debugPrint(debug_, "genclk", 1, "find generated clk insertion delays");

    clearSrcPaths();
    Sdc *sdc = mode_->sdc();
    ClockSeq gclks;
    for (Clock *clk : sdc->clocks()) {
      if (clk->isGenerated()) {
        checkMaster(clk, sdc);
        gclks.push_back(clk);
      }
    }

    // Generated clocks derived from a generated clock inherit its
    // insertion delay, so sort the clocks by source pin level.
    sort(gclks, ClockPinMaxLevelLess(this));

    for (Clock *gclk : gclks) {
      if (gclk->masterClk()) {
        findInsertionDelays(gclk);
        recordSrcPaths(gclk);
      }
    }
    stats.report("Find generated clk insertion delays");
    found_insertion_delays_ = true;
  }
}

////////////////////////////////////////////////////////////////

class GenClkMasterSearchPred : public ClkTreeSearchPred
{
public:
  GenClkMasterSearchPred(const StaState *sta);
  bool searchThruAllow(const TimingRole *role) const override;
};

GenClkMasterSearchPred::GenClkMasterSearchPred(const StaState *sta) :
  ClkTreeSearchPred(sta)
{
}

bool
GenClkMasterSearchPred::searchThruAllow(const TimingRole *role) const
{
  return role->isWire()
    || role == TimingRole::combinational()
    || role == TimingRole::regClkToQ();
}

////////////////////////////////////////////////////////////////

void
Genclks::checkMaster(Clock *gclk,
                     const Sdc *sdc)
{
  ensureMaster(gclk, sdc);
  if (gclk->masterClk() == nullptr)
    report_->warn(1060, "no master clock found for generated clock {}.",
                  gclk->name());
}

void
Genclks::ensureMaster(Clock *gclk,
                      const Sdc *sdc)
{
  Clock *master_clk = gclk->masterClk();
  if (master_clk == nullptr) {
    int master_clk_count = 0;
    bool found_master = false;
    Pin *src_pin = gclk->srcPin();
    ClockSet *master_clks = sdc->findClocks(src_pin);
    if (master_clks) {
      ClockSet::iterator master_iter = master_clks->begin();
      while (master_iter != master_clks->end()) {
        master_clk = *master_iter++;
        // Master source pin can actually be a clock source pin.
        if (master_clk != gclk) {
          gclk->setInferedMasterClk(master_clk);
          debugPrint(debug_, "genclk", 2, " {} master clk {}", gclk->name(),
                     master_clk->name());
          found_master = true;
          master_clk_count++;
        }
      }
    }
    if (!found_master) {
      // Search backward from generated clock source pin to a clock pin.
      GenClkMasterSearchPred srch_pred(this);
      VertexQueue master_queue;
      VertexSet visited = makeVertexSet(this);
      VertexSet src_vertices = makeVertexSet(this);
      gclk->srcPinVertices(src_vertices, network_, graph_);
      for (Vertex *vertex : src_vertices)
        master_queue.push(vertex);
      while (!master_queue.empty()) {
        Vertex *vertex = master_queue.front();
        master_queue.pop();
        if (!visited.contains(vertex)) {
          visited.insert(vertex);
          Pin *pin = vertex->pin();
          if (sdc->isLeafPinClock(pin)) {
            ClockSet *master_clks = sdc->findLeafPinClocks(pin);
            if (master_clks) {
              ClockSet::iterator master_iter = master_clks->begin();
              if (master_iter != master_clks->end()) {
                master_clk = *master_iter++;
                // Master source pin can actually be a clock source pin.
                if (master_clk != gclk) {
                  gclk->setInferedMasterClk(master_clk);
                  debugPrint(debug_, "genclk", 2, " {} master clk {}", gclk->name(),
                             master_clk->name());
                  master_clk_count++;
                  break;
                }
              }
            }
          }
          enqueueFanin(vertex, master_queue, srch_pred);
        }
      }
    }
    if (master_clk_count > 1)
      report_->warn(1061,
                    "generated clock {} pin {} is in the fanout of multiple clocks.",
                    gclk->name(), network_->pathName(src_pin));
  }
}

////////////////////////////////////////////////////////////////

// Similar to ClkTreeSearchPred but
//  respect generated clock combinational attribute
class GenClkFaninSrchPred : public GenClkMasterSearchPred
{
public:
  GenClkFaninSrchPred(Clock *gclk,
                      const StaState *sta);
  bool searchThruAllow(const TimingRole *role) const override;

private:
  bool combinational_;
};

GenClkFaninSrchPred::GenClkFaninSrchPred(Clock *gclk,
                                         const StaState *sta) :
  GenClkMasterSearchPred(sta),
  combinational_(gclk->combinational())
{
}

bool
GenClkFaninSrchPred::searchThruAllow(const TimingRole *role) const
{
  return role == TimingRole::combinational()
    || role == TimingRole::wire()
    || !combinational_;
}

void
Genclks::findFanin(Clock *gclk,
                   VertexSet &fanins)
{
  // Search backward from generated clock source pin to a clock pin.
  GenClkFaninSrchPred srch_pred(gclk, this);
  VertexQueue fanin_queue;
  seedClkVertices(gclk, fanin_queue, fanins, srch_pred);
  while (!fanin_queue.empty()) {
    Vertex *vertex = fanin_queue.front();
    fanin_queue.pop();
    if (!fanins.contains(vertex)) {
      fanins.insert(vertex);
      debugPrint(debug_, "genclk", 2, "gen clk {} fanin {}", gclk->name(),
                 vertex->to_string(this));
      enqueueFanin(vertex, fanin_queue, srch_pred);
    }
  }
}

void
Genclks::seedClkVertices(Clock *clk,
                         VertexQueue &fanin_queue,
                         VertexSet &fanins,
                         SearchPred &srch_pred)
{
  for (const Pin *pin : clk->leafPins()) {
    Vertex *vertex, *bidirect_drvr_vertex;
    graph_->pinVertices(pin, vertex, bidirect_drvr_vertex);
    fanins.insert(vertex);
    enqueueFanin(vertex, fanin_queue, srch_pred);
    if (bidirect_drvr_vertex) {
      fanins.insert(bidirect_drvr_vertex);
      enqueueFanin(bidirect_drvr_vertex, fanin_queue, srch_pred);
    }
  }
}

////////////////////////////////////////////////////////////////

class GenClkInsertionSearchPred : public SearchPred0
{
public:
  GenClkInsertionSearchPred(Clock *gclk,
                            GenclkInfo *genclk_info,
                            const StaState *sta);
  bool searchThru(Edge *edge,
                  const Mode *mode) const override;
  bool searchTo(const Vertex *to_vertex,
                const Mode *mode) const override;

private:
  bool isNonGeneratedClkPin(const Pin *pin,
                            const Sdc *sdc) const;

  Clock *gclk_;
  GenclkInfo *genclk_info_;
};

GenClkInsertionSearchPred::GenClkInsertionSearchPred(Clock *gclk,
                                                     GenclkInfo *genclk_info,
                                                     const StaState *sta) :
  SearchPred0(sta),
  gclk_(gclk),
  genclk_info_(genclk_info)
{
}

bool
GenClkInsertionSearchPred::searchThru(Edge *edge,
                                      const Mode *mode) const
{
  const TimingRole *role = edge->role();
  EdgeSet &fdbk_edges = genclk_info_->fdbkEdges();
  return SearchPred0::searchThru(edge, mode) && !role->isTimingCheck()
      && (sta_->variables()->clkThruTristateEnabled()
          || !(role == TimingRole::tristateEnable()
               || role == TimingRole::tristateDisable()))
      && !fdbk_edges.contains(edge);
}

bool
GenClkInsertionSearchPred::searchTo(const Vertex *to_vertex,
                                    const Mode *mode) const
{
  Pin *to_pin = to_vertex->pin();
  return SearchPred0::searchTo(to_vertex, mode)
      // Propagate through other generated clock roots but not regular
      // clock roots.
      && !(!gclk_->leafPins().contains(to_pin)
           && isNonGeneratedClkPin(to_pin, mode->sdc()))
      && genclk_info_->fanins().contains(const_cast<Vertex *>(to_vertex));
}

bool
GenClkInsertionSearchPred::isNonGeneratedClkPin(const Pin *pin,
                                                const Sdc *sdc) const
{
  ClockSet *clks = sdc->findLeafPinClocks(pin);
  if (clks) {
    for (const Clock *clk : *clks) {
      if (!clk->isGenerated())
        return true;
    }
  }
  return false;
}

////////////////////////////////////////////////////////////////

void
Genclks::findInsertionDelays(Clock *gclk)
{
  debugPrint(debug_, "genclk", 2, "find gen clk {} insertion", gclk->name());
  GenclkInfo *genclk_info = makeGenclkInfo(gclk);
  FilterPath *src_filter = genclk_info->srcFilter();
  VertexQueue insert_queue;
  GenClkInsertionSearchPred srch_pred(gclk, genclk_info, this);
  seedSrcPins(gclk, src_filter, insert_queue, srch_pred);
  // Propagate arrivals to generated clk root pin level.
  findSrcArrivals(gclk, genclk_info, insert_queue);
  // Unregister the filter so that it is not triggered by other searches.
  // The exception itself has to stick around because the source path
  // tags reference it.
  mode_->sdc()->unrecordException(src_filter);
}

GenclkInfo *
Genclks::makeGenclkInfo(Clock *gclk)
{
  FilterPath *src_filter = makeSrcFilter(gclk, mode_->sdc());
  Level gclk_level = clkPinMaxLevel(gclk);
  GenclkInfo *genclk_info = new GenclkInfo(gclk, gclk_level, src_filter, this);
  findFanin(gclk, genclk_info->fanins());
  genclk_info_map_[gclk] = genclk_info;
  return genclk_info;
}

GenclkInfo *
Genclks::genclkInfo(const Clock *gclk) const
{
  return findKey(genclk_info_map_, const_cast<Clock *>(gclk));
}

FilterPath *
Genclks::srcFilter(Clock *gclk)
{
  GenclkInfo *genclk_info = findKey(genclk_info_map_, gclk);
  if (genclk_info)
    return genclk_info->srcFilter();
  else
    return nullptr;
}

EdgeSet &
Genclks::latchFdbkEdges(const Clock *clk)
{
  GenclkInfo *genclk_info = genclkInfo(clk);
  return genclk_info->fdbkEdges();
}

void
Genclks::findLatchFdbkEdges(const Clock *clk)
{
  GenclkInfo *genclk_info = genclkInfo(clk);
  if (genclk_info && !genclk_info->foundLatchFdbkEdges())
    findLatchFdbkEdges(clk, genclk_info);
}

// Generated clock insertion delays propagate through latch D->Q.
// This exposes loops through latches that are not discovered and
// flagged by levelization.  Find these loops with a depth first
// search from the master clock source pins and record them to prevent
// the clock insertion search from searching through them.
//
// Because this is relatively expensive to search and it is rare to
// find latches in the clock network it is only called when a latch
// D to Q edge is encountered in the BFS arrival search.
void
Genclks::findLatchFdbkEdges(const Clock *gclk,
                            GenclkInfo *genclk_info)
{
  Level gclk_level = genclk_info->gclkLevel();
  EdgeSet &fdbk_edges = genclk_info->fdbkEdges();
  for (const Pin *pin : gclk->masterClk()->leafPins()) {
    Vertex *vertex = graph_->pinDrvrVertex(pin);
    VertexSet path_vertices = makeVertexSet(this);
    VertexSet visited_vertices = makeVertexSet(this);
    SearchPred1 srch_pred(this);
    findLatchFdbkEdges(vertex, gclk_level, srch_pred, path_vertices,
                       visited_vertices, fdbk_edges);
  }
  genclk_info->setFoundLatchFdbkEdges(true);
}

void
Genclks::findLatchFdbkEdges(Vertex *from_vertex,
                            Level gclk_level,
                            SearchPred &srch_pred,
                            VertexSet &path_vertices,
                            VertexSet &visited_vertices,
                            EdgeSet &fdbk_edges)
{
  if (!visited_vertices.contains(from_vertex)) {
    visited_vertices.insert(from_vertex);
    path_vertices.insert(from_vertex);
    VertexOutEdgeIterator edge_iter(from_vertex, graph_);
    while (edge_iter.hasNext()) {
      Edge *edge = edge_iter.next();
      Vertex *to_vertex = edge->to(graph_);
      if (path_vertices.contains(to_vertex)) {
        debugPrint(debug_, "genclk", 2, " found feedback edge {}",
                   edge->to_string(this));
        fdbk_edges.insert(edge);
      }
      else if (srch_pred.searchThru(edge, mode_)
               && srch_pred.searchTo(to_vertex, mode_)
               && to_vertex->level() <= gclk_level)
        findLatchFdbkEdges(to_vertex, gclk_level, srch_pred, path_vertices,
                           visited_vertices, fdbk_edges);
    }
    path_vertices.erase(from_vertex);
  }
}

FilterPath *
Genclks::makeSrcFilter(Clock *gclk,
                       Sdc *sdc)
{
  ClockSet *from_clks = new ClockSet;
  from_clks->insert(gclk->masterClk());
  const RiseFallBoth *rf = RiseFallBoth::riseFall();
  ExceptionFrom *from = sdc->makeExceptionFrom(nullptr, from_clks, nullptr, rf);

  PinSet *thru_pins = new PinSet(network_);
  thru_pins->insert(gclk->srcPin());
  ExceptionThru *thru = sdc->makeExceptionThru(thru_pins, nullptr, nullptr, rf);
  ExceptionThruSeq *thrus = new ExceptionThruSeq;
  thrus->push_back(thru);

  ClockSet *to_clks = new ClockSet;
  to_clks->insert(gclk);
  ExceptionTo *to = sdc->makeExceptionTo(nullptr, to_clks, nullptr, rf, rf);

  return sdc->makeFilterPath(from, thrus, to);
}

void
Genclks::seedSrcPins(Clock *gclk,
                     FilterPath *src_filter,
                     VertexQueue &insert_queue,
                     SearchPred &srch_pred)
{
  Clock *master_clk = gclk->masterClk();
  for (const Pin *master_pin : master_clk->leafPins()) {
    Vertex *vertex = graph_->pinDrvrVertex(master_pin);
    if (vertex) {
      debugPrint(debug_, "genclk", 2, " seed src pin {}",
                 network_->pathName(master_pin));
      TagGroupBldr tag_bldr(true, this);
      tag_bldr.init(vertex);
      copyGenClkSrcPaths(vertex, &tag_bldr);
      for (Scene *scene : mode_->scenes()) {
        for (const MinMax *min_max : MinMax::range()) {
          const EarlyLate *early_late = min_max;
          for (const RiseFall *rf : RiseFall::range()) {
            Arrival insert = search_->clockInsertion(master_clk, master_pin, rf,
                                                     min_max, early_late, mode_);
            Tag *tag = makeTag(gclk, master_clk, master_pin, rf, src_filter, insert,
                               scene, min_max);
            tag_bldr.setArrival(tag, insert);
          }
        }
      }
      search_->setVertexArrivals(vertex, &tag_bldr);
      enqueueFanout(vertex, insert_queue, srch_pred);
    }
  }
}

void
Genclks::enqueueFanin(Vertex *vertex,
                      VertexQueue &insert_queue,
                      SearchPred &srch_pred)
{
  graph_->visitFanins(vertex, &srch_pred,
                      [&insert_queue] (Vertex *fanin) {
                        insert_queue.push(fanin);
                      });
}

void
Genclks::enqueueFanout(Vertex *vertex,
                       VertexQueue &insert_queue,
                       SearchPred &srch_pred)
{
  graph_->visitFanouts(vertex, &srch_pred,
                       [&insert_queue] (Vertex *fanout) {
                         insert_queue.push(fanout);
                       });
}

Tag *
Genclks::makeTag(const Clock *gclk,
                 const Clock *master_clk,
                 const Pin *master_pin,
                 const RiseFall *master_rf,
                 FilterPath *src_filter,
                 Arrival insert,
                 Scene *scene,
                 const MinMax *min_max)
{
  ExceptionState *state = src_filter->firstState();
  // If the src pin is one of the master pins the filter is active
  // from the get go.
  if (master_pin == gclk->srcPin())
    state = state->nextState();
  ExceptionStateSet *states = new ExceptionStateSet();
  states->insert(state);
  const ClkInfo *clk_info = search_->findClkInfo(scene, master_clk->edge(master_rf),
                                                 master_pin, true, nullptr, true,
                                                 nullptr, insert, 0.0, nullptr,
                                                 min_max, nullptr);
  return search_->findTag(scene, master_rf, min_max, clk_info, false, nullptr,
                          false, states, true, nullptr);
}

class GenClkArrivalSearchPred : public EvalPred
{
public:
  GenClkArrivalSearchPred(Clock *gclk,
                          const StaState *sta);
  bool searchThru(Edge *edge,
                  const Mode *mode) const override;
  bool searchTo(const Vertex *to_vertex,
                const Mode *mode) const override;

private:
  bool combinational_;
};

GenClkArrivalSearchPred::GenClkArrivalSearchPred(Clock *gclk,
                                                 const StaState *sta) :
  EvalPred(sta),
  combinational_(gclk->combinational())
{
}

bool
GenClkArrivalSearchPred::searchThru(Edge *edge,
                                    const Mode *mode) const
{
  const TimingRole *role = edge->role();
  return EvalPred::searchThru(edge, mode)
      && (role == TimingRole::combinational() || role->isWire() || !combinational_)
      && (sta_->variables()->clkThruTristateEnabled()
          || !(role == TimingRole::tristateEnable()
               || role == TimingRole::tristateDisable()));
}

// Override EvalPred::searchTo to search to generated clock pin.
bool
GenClkArrivalSearchPred::searchTo(const Vertex *to_vertex,
                                  const Mode *mode) const
{
  // NOLINTNEXTLINE(bugprone-parent-virtual-call)
  return SearchPred0::searchTo(to_vertex, mode);
}

class GenclkSrcArrivalVisitor : public ArrivalVisitor
{
public:
  GenclkSrcArrivalVisitor(Clock *gclk,
                          GenclkInfo *genclk_info,
                          VertexQueue &insert_queue,
                          const Mode *mode);
  GenclkSrcArrivalVisitor(const GenclkSrcArrivalVisitor &visitor);
  VertexVisitor *copy() const override;
  void visit(Vertex *vertex) override;

protected:
  Clock *gclk_;
  VertexQueue &insert_queue_;
  GenclkInfo *genclk_info_;
  GenClkInsertionSearchPred srch_pred_;
  const Mode *mode_;
  const Sdc *sdc_;
  Genclks *genclks_;
};

GenclkSrcArrivalVisitor::GenclkSrcArrivalVisitor(Clock *gclk,
                                                 GenclkInfo *genclk_info,
                                                 VertexQueue &insert_queue,
                                                 const Mode *mode) :
  ArrivalVisitor(mode->sta()),
  gclk_(gclk),
  insert_queue_(insert_queue),
  genclk_info_(genclk_info),
  srch_pred_(gclk_, genclk_info, mode->sta()),
  mode_(mode),
  sdc_(mode->sdc()),
  genclks_(mode->genclks())
{
}

GenclkSrcArrivalVisitor::GenclkSrcArrivalVisitor(const GenclkSrcArrivalVisitor &visitor) :
  ArrivalVisitor(visitor),
  gclk_(visitor.gclk_),
  insert_queue_(visitor.insert_queue_),
  genclk_info_(visitor.genclk_info_),
  srch_pred_(visitor.gclk_, visitor.genclk_info_, this),
  mode_(visitor.mode_),
  sdc_(visitor.sdc_),
  genclks_(visitor.genclks_)
{
}

VertexVisitor *
GenclkSrcArrivalVisitor::copy() const
{
  return new GenclkSrcArrivalVisitor(*this);
}

void
GenclkSrcArrivalVisitor::visit(Vertex *vertex)
{
  debugPrint(debug_, "genclk", 2, "find gen clk insert arrival {}",
             vertex->to_string(this));
  tag_bldr_->init(vertex);
  has_fanin_one_ = graph_->hasFaninOne(vertex);
  genclks_->copyGenClkSrcPaths(vertex, tag_bldr_);
  visitFaninPaths(vertex, true);
  search_->setVertexArrivals(vertex, tag_bldr_);
  // Propagate beyond the clock tree to reach generated clk roots.
  genclks_->enqueueFanout(vertex, insert_queue_, srch_pred_);
}

void
Genclks::findSrcArrivals(Clock *gclk,
                         GenclkInfo *genclk_info,
                         VertexQueue &insert_queue)
{
  GenClkArrivalSearchPred eval_pred(gclk, this);
  GenclkSrcArrivalVisitor arrival_visitor(gclk, genclk_info, insert_queue, mode_);
  arrival_visitor.init(true, false, &eval_pred);
  // This cannot restrict the search level because loops in the clock tree
  // can circle back to the generated clock src pin.
  // Parallel visit is slightly slower (at last check).
  while (!insert_queue.empty()) {
    Vertex *vertex = insert_queue.front();
    insert_queue.pop();
    arrival_visitor.visit(vertex);
  }
}

// Copy generated clock source paths to tag_bldr.
void
Genclks::copyGenClkSrcPaths(Vertex *vertex,
                            TagGroupBldr *tag_bldr)
{
  auto itr = vertex_src_paths_map_.find(vertex);
  if (itr != vertex_src_paths_map_.end()) {
    const std::vector<const Path *> &src_paths = itr->second;
    for (const Path *path : src_paths) {
      Path src_path = *path;
      Path *prev_path = src_path.prevPath();
      if (prev_path && !prev_path->isNull()) {
        Path *prev_vpath = Path::vertexPath(prev_path, this);
        src_path.setPrevPath(prev_vpath);
      }
      debugPrint(debug_, "genclk", 3, "vertex {} insert genclk {} src path {} {}s",
                 src_path.vertex(this)->to_string(this),
                 src_path.tag(this)->genClkSrcPathClk()->name(),
                 src_path.tag(this)->minMax()->to_string(),
                 src_path.tag(this)->to_string(true, false, this));
      tag_bldr->insertPath(src_path);
    }
  }
}

////////////////////////////////////////////////////////////////

void
Genclks::clearSrcPaths()
{
  for (const auto& [vertex, paths] : vertex_src_paths_map_) {
    for (const Path *path : paths)
      delete path;
  }
  vertex_src_paths_map_.clear();
  genclk_src_paths_.clear();
}

size_t
Genclks::srcPathIndex(const RiseFall *clk_rf,
                      const MinMax *min_max) const
{
  return min_max->index() * RiseFall::index_count + clk_rf->index();
}

void
Genclks::recordSrcPaths(Clock *gclk)
{
  size_t path_count = RiseFall::index_count * MinMax::index_count;

  bool divide_by_1 = gclk->isDivideByOneCombinational();
  bool invert = gclk->invert();
  bool has_edges = !gclk->edges().empty();

  for (const Pin *gclk_pin : gclk->leafPins()) {
    std::vector<Path> &src_paths = genclk_src_paths_[ClockPinPair(gclk, gclk_pin)];
    src_paths.resize(path_count);
    Vertex *gclk_vertex = srcPath(gclk_pin);
    VertexPathIterator path_iter(gclk_vertex, this);
    while (path_iter.hasNext()) {
      Path *path = path_iter.next();
      const ClockEdge *src_clk_edge = path->clkEdge(this);
      if (src_clk_edge && matchesSrcFilter(path, gclk)) {
        const EarlyLate *early_late = path->minMax(this);
        const RiseFall *src_clk_rf = src_clk_edge->transition();
        const RiseFall *rf = path->transition(this);
        bool inverting_path = (rf != src_clk_rf);
        size_t path_index = srcPathIndex(rf, path->minMax(this));
        Path &src_path = src_paths[path_index];
        if ((!divide_by_1 || (inverting_path == invert))
            && (!has_edges || src_clk_rf == gclk->masterClkEdgeTr(rf))
            && (src_path.isNull()
                || delayGreater(path->arrival(), src_path.arrival(), early_late,
                                this))) {
          debugPrint(debug_, "genclk", 2, "  {} insertion {} {} {}",
                     network_->pathName(gclk_pin), early_late->to_string(),
                     rf->shortName(), delayAsString(path->arrival(), this));
          src_path = *path;
        }
      }
    }
    // Record vertex->genclk src paths.
    bool found_src_paths = false;
    for (size_t path_index = 0; path_index < path_count; path_index++) {
      Path &src_path = src_paths[path_index];
      if (!src_path.isNull()) {
        Path *prev_copy = &src_path;
        const Path *p = src_path.prevPath();
        while (p) {
          Path *copy = new Path(p);
          copy->setIsEnum(true);
          prev_copy->setPrevPath(copy);
          prev_copy = copy;

          Vertex *vertex = p->vertex(this);
          vertex_src_paths_map_[vertex].push_back(copy);
          p = p->prevPath();
        }
        found_src_paths = true;
      }
    }
    // Don't warn if the master clock is ideal.
    if (!found_src_paths
        && gclk->masterClk()
        && gclk->masterClk()->isPropagated())
      report_->warn(1062,
                    "generated clock {} source pin {} missing paths from master clock {}.",
                    gclk->name(),
                    network_->pathName(gclk_pin),
                    gclk->masterClk()->name());
  }
  deleteGenclkSrcPaths(gclk);
}

void
Genclks::deleteGenclkSrcPaths(Clock *gclk)
{
  GenclkInfo *genclk_info = genclkInfo(gclk);
  VertexQueue insert_queue;
  GenClkInsertionSearchPred srch_pred(gclk, genclk_info, this);
  FilterPath *src_filter = genclk_info->srcFilter();
  seedSrcPins(gclk, src_filter, insert_queue, srch_pred);
  while (!insert_queue.empty()) {
    Vertex *vertex = insert_queue.front();
    insert_queue.pop();
    search_->deletePaths(vertex);
    enqueueFanout(vertex, insert_queue, srch_pred);
  }
}

bool
Genclks::matchesSrcFilter(Path *path,
                          const Clock *gclk) const
{
  Tag *tag = path->tag(this);
  const ExceptionStateSet *states = tag->states();
  if (tag->isGenClkSrcPath() && states) {
    for (ExceptionState *state : *states) {
      ExceptionPath *except = state->exception();
      if (except->isFilter() && state->nextThru() == nullptr && except->to()
          && except->to()->matches(gclk))
        return true;
    }
  }
  return false;
}

const Path *
Genclks::srcPath(const Path *clk_path) const
{
  const Pin *src_pin = clk_path->pin(this);
  const ClockEdge *clk_edge = clk_path->clkEdge(this);
  const EarlyLate *early_late = clk_path->minMax(this);
  return srcPath(clk_edge->clock(), src_pin, clk_edge->transition(), early_late);
}

const Path *
Genclks::srcPath(const ClockEdge *clk_edge,
                 const Pin *src_pin,
                 const MinMax *min_max) const
{
  return srcPath(clk_edge->clock(), src_pin, clk_edge->transition(), min_max);
}

const Path *
Genclks::srcPath(const Clock *gclk,
                 const Pin *src_pin,
                 const RiseFall *rf,
                 const MinMax *min_max) const
{
  auto itr = genclk_src_paths_.find(ClockPinPair(gclk, src_pin));
  if (itr != genclk_src_paths_.end()) {
    const std::vector<Path> &src_paths = itr->second;
    if (!src_paths.empty()) {
      size_t path_index = srcPathIndex(rf, min_max);
      const Path *src_path = &src_paths[path_index];
      if (!src_path->isNull())
        return src_path;
    }
  }
  return nullptr;
}

Arrival
Genclks::insertionDelay(const Clock *clk,
                        const Pin *pin,
                        const RiseFall *rf,
                        const EarlyLate *early_late) const
{
  const Path *src_path = srcPath(clk, pin, rf, early_late);
  if (src_path)
    return src_path->arrival();
  else
    return 0.0;
}

////////////////////////////////////////////////////////////////

bool
ClockPinPairLess::operator()(const ClockPinPair &pair1,
                             const ClockPinPair &pair2) const

{
  const Clock *clk1 = pair1.first;
  const Clock *clk2 = pair2.first;
  int clk_index1 = clk1->index();
  int clk_index2 = clk2->index();
  const Pin *pin1 = pair1.second;
  const Pin *pin2 = pair2.second;
  return (clk_index1 < clk_index2 || (clk_index1 == clk_index2 && pin1 < pin2));
}

class ClockPinPairHash
{
public:
  ClockPinPairHash(const Network *network);
  size_t operator()(const ClockPinPair &pair) const;

private:
  const Network *network_;
};

ClockPinPairHash::ClockPinPairHash(const Network *network) :
  network_(network)
{
}

size_t
ClockPinPairHash::operator()(const ClockPinPair &pair) const
{
  return hashSum(pair.first->index(), network_->id(pair.second));
}

class ClockPinPairEqual
{
public:
  bool operator()(const ClockPinPair &pair1,
                  const ClockPinPair &pair2) const;
};

bool
ClockPinPairEqual::operator()(const ClockPinPair &pair1,
                              const ClockPinPair &pair2) const

{
  return pair1.first == pair2.first && pair1.second == pair2.second;
}

}  // namespace sta
