// 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.

#pragma once

#include <atomic>
#include <map>
#include <mutex>

#include "Delay.hh"
#include "GraphClass.hh"
#include "Iterator.hh"
#include "LibertyClass.hh"
#include "NetworkClass.hh"
#include "ObjectTable.hh"
#include "Path.hh"
#include "StaState.hh"
#include "VertexId.hh"

namespace sta {

class MinMax;
class Sdc;

using VertexTable = ObjectTable<Vertex>;
using EdgeTable = ObjectTable<Edge>;
using PinVertexMap = std::map<const Pin*, Vertex*>;
using VertexEdgeIterator = Iterator<Edge*>;
using PeriodCheckAnnotations = std::map<const Pin*, float*, PinIdLess>;
using EdgeId = ObjectId;

static constexpr EdgeId edge_id_null = object_id_null;
static constexpr ObjectIdx edge_idx_null = object_id_null;
static constexpr ObjectIdx vertex_idx_null = object_idx_null;

// The graph acts as a BUILDER for the graph vertices and edges.
class Graph : public StaState
{
public:
  Graph(StaState *sta,
        DcalcAPIndex ap_count);
  void makeGraph();
  ~Graph() override;

  void delayCountChanged();
  size_t slewCount();

  // Vertex functions.
  // Bidirect pins have two vertices.
  Vertex *vertex(VertexId vertex_id) const;
  VertexId id(const Vertex *vertex) const;
  void makePinVertices(Pin *pin);
  void makePinVertices(Pin *pin,
                       Vertex *&vertex,
                       Vertex *&bidir_drvr_vertex);
  // Both vertices for bidirects.
  void pinVertices(const Pin *pin,
                   // Return values.
                   Vertex *&vertex,
                   Vertex *&bidirect_drvr_vertex) const;
  // Driver vertex for bidirects.
  Vertex *pinDrvrVertex(const Pin *pin) const;
  // Load vertex for bidirects.
  Vertex *pinLoadVertex(const Pin *pin) const;
  void deleteVertex(Vertex *vertex);
  bool hasFaninOne(Vertex *vertex) const;
  VertexId vertexCount() { return vertices_->size(); }

  void visitFanouts(Vertex *vertex,
                    SearchPred *pred,
                    const VertexFn &fn);
  void visitFanins(Vertex *vertex,
                   SearchPred *pred,
                   const VertexFn &fn);
  void visitFanoutEdges(Vertex *vertex,
                        SearchPred *pred,
                        const EdgeFn &fn);
  void visitFaninEdges(Vertex *vertex,
                       SearchPred *pred,
                       const EdgeFn &fn);

  // Reported slew are the same as those in the liberty tables.
  //  reported_slews = measured_slews / slew_derate_from_library
  // Measured slews are between slew_lower_threshold and slew_upper_threshold.
  Slew slew(const Vertex *vertex,
            const RiseFall *rf,
            DcalcAPIndex ap_index);
  Slew slew(const Vertex *vertex,
            size_t index);
  void setSlew(Vertex *vertex,
               const RiseFall *rf,
               DcalcAPIndex ap_index,
               const Slew &slew);

  // Edge functions.
  Edge *edge(EdgeId edge_id) const;
  EdgeId id(const Edge *edge) const;
  Edge *makeEdge(Vertex *from,
                 Vertex *to,
                 TimingArcSet *arc_set);
  void makeWireEdge(const Pin *from_pin,
                    const Pin *to_pin);
  void makePinInstanceEdges(const Pin *pin);
  void makeInstanceEdges(const Instance *inst);
  void makeWireEdgesToPin(const Pin *to_pin);
  void makeWireEdgesThruPin(const Pin *hpin);
  void makeWireEdgesFromPin(const Pin *drvr_pin);
  void deleteEdge(Edge *edge);
  // Find the edge and timing arc on a gate between in_pin and drvr_pin.
  void gateEdgeArc(const Pin *in_pin,
                   const RiseFall *in_rf,
                   const Pin *drvr_pin,
                   const RiseFall *drvr_rf,
                   // Return values.
                   Edge *&edge,
                   const TimingArc *&arc) const;

  ArcDelay arcDelay(const Edge *edge,
                    const TimingArc *arc,
                    DcalcAPIndex ap_index) const;
  void setArcDelay(Edge *edge,
                   const TimingArc *arc,
                   DcalcAPIndex ap_index,
                   const ArcDelay &delay);
  // Alias for arcDelays using library wire arcs.
  ArcDelay wireArcDelay(const Edge *edge,
                        const RiseFall *rf,
                        DcalcAPIndex ap_index);
  void setWireArcDelay(Edge *edge,
                       const RiseFall *rf,
                       DcalcAPIndex ap_index,
                       const ArcDelay &delay);
  // Is timing arc delay annotated.
  bool arcDelayAnnotated(const Edge *edge,
                         const TimingArc *arc,
                         DcalcAPIndex ap_index) const;
  void setArcDelayAnnotated(Edge *edge,
                            const TimingArc *arc,
                            DcalcAPIndex ap_index,
                            bool annotated);
  bool wireDelayAnnotated(const Edge *edge,
                          const RiseFall *rf,
                          DcalcAPIndex ap_index) const;
  void setWireDelayAnnotated(Edge *edge,
                             const RiseFall *rf,
                             DcalcAPIndex ap_index,
                             bool annotated);

  void minPulseWidthArc(Vertex *vertex,
                        const RiseFall *hi_low,
                        // Return values.
                        Edge *&edge,
                        TimingArc *&arc);
  void minPeriodArc(Vertex *vertex,
                    const RiseFall *rf,
                    // Return values.
                    Edge *&edge,
                    TimingArc *&arc);
  // Sdf period check annotation.
  void periodCheckAnnotation(const Pin *pin,
                             DcalcAPIndex ap_index,
                             // Return values.
                             float &period,
                             bool &exists);
  void setPeriodCheckAnnotation(const Pin *pin,
                                DcalcAPIndex ap_index,
                                float period);

  // Remove all delay and slew annotations.
  void removeDelaySlewAnnotations();
  VertexSet &regClkVertices() { return reg_clk_vertices_; }

  static constexpr int vertex_level_bits = 24;
  static constexpr int vertex_level_max = (1<<vertex_level_bits) - 1;

protected:
  void makeVerticesAndEdges();
  Vertex *makeVertex(Pin *pin,
                     bool is_bidirect_drvr,
                     bool is_reg_clk);
  void makeEdgeArcDelays(Edge *edge);
  void makePinVertices(const Instance *inst);
  void makeWireEdgesFromPin(const Pin *drvr_pin,
                            PinSet &visited_drvrs);
  bool isIsolatedNet(PinSeq &drvrs,
                     PinSeq &loads) const;
  void makeWireEdges();
  void makeInstDrvrWireEdges(const Instance *inst,
                             PinSet &visited_drvrs);
  void makePortInstanceEdges(const Instance *inst,
                             LibertyCell *cell,
                             LibertyPort *from_to_port);
  void removePeriodCheckAnnotations();
  void makeVertexSlews(Vertex *vertex);
  void deleteInEdge(Vertex *vertex,
                    Edge *edge);
  void deleteOutEdge(Vertex *vertex,
                     Edge *edge);
  void initSlews();
  void initSlews(Vertex *vertex);
  void initArcDelays(Edge *edge);
  void removeDelayAnnotated(Edge *edge);

  VertexTable *vertices_{nullptr};
  EdgeTable *edges_{nullptr};
  // Bidirect pins are split into two vertices:
  //  load/sink (top level output, instance pin input) vertex in pin_vertex_map
  //  driver/source (top level input, instance pin output) vertex
  //  in pin_bidirect_drvr_vertex_map
  PinVertexMap pin_bidirect_drvr_vertex_map_;
  // Sdf period check annotations.
  PeriodCheckAnnotations period_check_annotations_;
  // Register/latch clock vertices to search from.
  VertexSet reg_clk_vertices_;
  DcalcAPIndex ap_count_;

  friend class Vertex;
  friend class VertexIterator;
  friend class VertexInEdgeIterator;
  friend class VertexOutEdgeIterator;
  friend class MakeEdgesThruHierPin;
};

// Each Vertex corresponds to one network pin.
class Vertex
{
public:
  Vertex();
  ~Vertex();
  Pin *pin() const { return pin_; }
  // Pin path with load/driver suffix for bidirects.
  std::string to_string(const StaState *sta) const;
  // compatibility
  std::string name(const Network *network) const;
  [[nodiscard]] bool isBidirectDriver() const { return is_bidirect_drvr_; }
  [[nodiscard]] bool isDriver(const Network *network) const;
  Level level() const { return level_; }
  void setLevel(Level level);
  [[nodiscard]] bool visited() const { return visited1_; }
  void setVisited(bool visited);
  [[nodiscard]] bool visited2() const { return visited2_; }
  void setVisited2(bool visited);
  [[nodiscard]] bool isRoot() const{ return level_ == 0; }
  [[nodiscard]] bool hasFanin() const;
  [[nodiscard]] bool hasFanout() const;
  Path *paths() const { return paths_; }
  Path *makePaths(uint32_t count);
  void setPaths(Path *paths);
  void deletePaths();
  TagGroupIndex tagGroupIndex() const;
  void setTagGroupIndex(TagGroupIndex tag_index);
  // Slew is annotated by sdc set_annotated_transition cmd.
  bool slewAnnotated(const RiseFall *rf,
                     const MinMax *min_max) const;
  // True if any rise/fall analysis pt slew is annotated.
  bool slewAnnotated() const;
  void setSlewAnnotated(bool annotated,
                        const RiseFall *rf,
                        DcalcAPIndex ap_index);
  void removeSlewAnnotated();
  // True when vertex has timing check edges that constrain it.
  [[nodiscard]] bool hasChecks() const  { return has_checks_; }
  void setHasChecks(bool has_checks);
  [[nodiscard]] bool isCheckClk() const { return is_check_clk_; }
  void setIsCheckClk(bool is_check_clk);
  [[nodiscard]] bool hasDownstreamClkPin() const { return has_downstream_clk_pin_; }
  void setHasDownstreamClkPin(bool has_clk_pin);
  [[nodiscard]] bool bfsInQueue(BfsIndex index) const;
  void setBfsInQueue(BfsIndex index, bool value);
  [[nodiscard]] bool isRegClk() const { return is_reg_clk_; }
  // Has sim value in some mode.
  [[nodiscard]] bool hasSimValue() const { return has_sim_value_; }
  void setHasSimValue(bool has_sim);
  
  // ObjectTable interface.
  [[nodiscard]] ObjectIdx objectIdx() const { return object_idx_; }
  void setObjectIdx(ObjectIdx idx);

protected:
  void init(Pin *pin,
            bool is_bidirect_drvr,
            bool is_reg_clk);
  void clear();
  Slew *slews() { return reinterpret_cast<Slew*>(slews_); }
  const Slew *slews() const { return reinterpret_cast<const Slew*>(slews_); }
  float *slewsFloat() { return slews_; }
  const float *slewsFloat() const { return slews_; }
  void setSlews(float *slews);

  Pin *pin_;
  EdgeId in_edges_;             // Edges to this vertex.
  EdgeId out_edges_;            // Edges from this vertex.

  // Delay calc
  float *slews_;
  // Search
  Path *paths_;

  // These fields are written by multiple threads, so they
  // cannot share the same word as the following bit fields.
  uint32_t tag_group_index_;
  uint32_t object_idx_;
  // Each bit corresponds to a different BFS queue.
  std::atomic<uint8_t> bfs_in_queue_; // 8

  // Bidirect pins have two vertices.
  // This flag distinguishes the driver and load vertices.
  unsigned int is_bidirect_drvr_:1;
  unsigned int is_reg_clk_:1;
  // Constrained by timing check edge.
  unsigned int has_checks_:1;
  // Is the clock for a timing check.
  unsigned int is_check_clk_:1;
  unsigned int has_downstream_clk_pin_:1;
  unsigned int visited1_:1;
  unsigned int visited2_:1;
  unsigned int has_sim_value_:1;
  int level_:Graph::vertex_level_bits; // 24
  unsigned int slew_annotated_:slew_annotated_bits;  // 4

private:
  friend class Graph;
  friend class Edge;
  friend class VertexInEdgeIterator;
  friend class VertexOutEdgeIterator;
};

// There is one Edge between each pair of pins that has a timing
// path between them.
class Edge
{
public:
  Edge();
  ~Edge();
  std::string to_string(const StaState *sta) const;
  Vertex *to(const Graph *graph) const { return graph->vertex(to_); }
  VertexId to() const { return to_; }
  Vertex *from(const Graph *graph) const { return graph->vertex(from_); }
  VertexId from() const { return from_; }
  const TimingRole *role() const;
  bool isWire() const;
  TimingSense sense() const;
  TimingArcSet *timingArcSet() const { return arc_set_; }
  void setTimingArcSet(TimingArcSet *set);
  float *arcDelays() { return arc_delays_; }
  const float *arcDelays() const { return arc_delays_; }
  void setArcDelays(float *delays);
  bool delay_Annotation_Is_Incremental() const {return delay_annotation_is_incremental_;};
  void setDelayAnnotationIsIncremental(bool is_incr);
  // Edge is disabled to break combinational loops.
  [[nodiscard]] bool isDisabledLoop() const { return is_disabled_loop_; }
  void setIsDisabledLoop(bool disabled);
  // Edge is disabled to prevent converging clocks from merging (Xilinx).
  bool isBidirectInstPath() const { return is_bidirect_inst_path_; }
  void setIsBidirectInstPath(bool is_bidir);
  bool isBidirectNetPath() const { return is_bidirect_net_path_; }
  void setIsBidirectNetPath(bool is_bidir);
  bool isBidirectPortPath() const { return is_bidirect_port_path_; }
  void setIsBidirectPortPath(bool is_bidir);

  void removeDelayAnnotated();
  [[nodiscard]] bool hasSimSense() const { return has_sim_sense_; }
  void setHasSimSense(bool has_sense);
  [[nodiscard]] bool hasDisabledCond() const { return has_disabled_cond_; }
  void setHasDisabledCond(bool has_disabled);

  // ObjectTable interface.
  ObjectIdx objectIdx() const { return object_idx_; }
  void setObjectIdx(ObjectIdx idx);

protected:
  void init(VertexId from,
            VertexId to,
            TimingArcSet *arc_set);
  void clear();
  bool arcDelayAnnotated(const TimingArc *arc,
                         DcalcAPIndex ap_index,
                         DcalcAPIndex ap_count) const;
  void setArcDelayAnnotated(const TimingArc *arc,
                            DcalcAPIndex ap_index,
                            DcalcAPIndex ap_count,
                            bool annotated);
  static uintptr_t arcDelayAnnotateBit(size_t index);

  TimingArcSet *arc_set_;
  float *arc_delays_;
  union {
    uintptr_t bits_;
    std::vector<bool> *seq_;
  } arc_delay_annotated_;
  VertexId from_;
  VertexId to_;
  EdgeId vertex_in_next_;               // Vertex in edges list.
  EdgeId vertex_out_next_;              // Vertex out edges doubly linked list.
  EdgeId vertex_out_prev_;
  bool arc_delay_annotated_is_bits_:1;
  bool delay_annotation_is_incremental_:1;
  bool is_bidirect_inst_path_:1;
  bool is_bidirect_net_path_:1;
  // Bidirect load -> driver edge.
  bool is_bidirect_port_path_:1;
  bool is_disabled_loop_:1;
  bool has_sim_sense_:1;
  bool has_disabled_cond_:1;
  unsigned object_idx_:VertexTable::idx_bits;

private:
  friend class Graph;
  friend class GraphDelays1;
  friend class GraphSlewsDelays1;
  friend class GraphSlewsDelays2;
  friend class Vertex;
  friend class VertexInEdgeIterator;
  friend class VertexOutEdgeIterator;
};

// Iterate over all graph vertices.
class VertexIterator : public Iterator<Vertex*>
{
public:
  VertexIterator(Graph *graph);
  bool hasNext() override { return vertex_ || bidir_vertex_; }
  Vertex *next() override;

private:
  bool findNextPin();
  void findNext();

  Graph *graph_;
  Network *network_;
  Instance *top_inst_;
  LeafInstanceIterator *inst_iter_;
  InstancePinIterator *pin_iter_{nullptr};
  Vertex *vertex_{nullptr};
  Vertex *bidir_vertex_{nullptr};
};

class VertexInEdgeIterator : public VertexEdgeIterator
{
public:
  VertexInEdgeIterator(Vertex *vertex,
                       const Graph *graph);
  VertexInEdgeIterator(VertexId vertex_id,
                       const Graph *graph);
  bool hasNext() override { return (next_ != nullptr); }
  Edge *next() override;

private:
  Edge *next_;
  const Graph *graph_;
};

class VertexOutEdgeIterator : public VertexEdgeIterator
{
public:
  VertexOutEdgeIterator(Vertex *vertex,
                        const Graph *graph);
  bool hasNext() override { return (next_ != nullptr); }
  Edge *next() override;

private:
  Edge *next_;
  const Graph *graph_;
};

// Iterate over the edges through a hierarchical pin.
class EdgesThruHierPinIterator : public Iterator<Edge*>
{
public:
  EdgesThruHierPinIterator(const Pin *hpin,
                           Network *network,
                           Graph *graph);
  bool hasNext() override;
  Edge *next() override;

private:
  EdgeSet edges_;
  EdgeSet::iterator edge_iter_;
};

// Helper function to create a VertexSet with the comparator initialized
inline VertexSet
makeVertexSet(StaState *sta)
{
  return VertexSet(VertexIdLess(sta->graphRef()));
}

} // namespace sta
