KiCad PCB EDA Suite
connection_graph.h
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2018 CERN
5  * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors.
6  * @author Jon Evans <[email protected]>
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License along
19  * with this program. If not, see <http://www.gnu.org/licenses/>.
20  */
21 
22 #ifndef _CONNECTION_GRAPH_H
23 #define _CONNECTION_GRAPH_H
24 
25 #include <mutex>
26 #include <vector>
27 
28 #include <erc_settings.h>
29 #include <sch_connection.h>
30 #include <sch_item.h>
31 
32 
33 #ifdef DEBUG
34 // Uncomment this line to enable connectivity debugging features
35 // #define CONNECTIVITY_DEBUG
36 #endif
37 
38 
39 class CONNECTION_GRAPH;
40 class SCHEMATIC;
41 class SCH_EDIT_FRAME;
42 class SCH_HIERLABEL;
43 class SCH_PIN;
44 class SCH_SHEET_PIN;
45 
46 
61 {
62 public:
63  enum class PRIORITY
64  {
65  INVALID = -1,
66  NONE = 0,
67  PIN,
68  SHEET_PIN,
69  HIER_LABEL,
71  POWER_PIN,
72  GLOBAL
73  };
74 
75  explicit CONNECTION_SUBGRAPH( CONNECTION_GRAPH* aGraph ) :
76  m_graph( aGraph ),
77  m_dirty( false ),
78  m_absorbed( false ),
79  m_absorbed_by( nullptr ),
80  m_code( -1 ),
81  m_multiple_drivers( false ),
82  m_strong_driver( false ),
83  m_local_driver( false ),
84  m_no_connect( nullptr ),
85  m_bus_entry( nullptr ),
86  m_driver( nullptr ),
87  m_driver_connection( nullptr ),
88  m_hier_parent( nullptr ),
89  m_first_driver( nullptr ),
90  m_second_driver( nullptr )
91  {}
92 
93  ~CONNECTION_SUBGRAPH() = default;
94 
104  bool ResolveDrivers( bool aCheckMultipleDrivers = false );
105 
109  wxString GetNetName() const;
110 
112  std::vector<SCH_ITEM*> GetBusLabels() const;
113 
115  const wxString& GetNameForDriver( SCH_ITEM* aItem );
116 
117  const wxString GetNameForDriver( SCH_ITEM* aItem ) const;
118 
120  void Absorb( CONNECTION_SUBGRAPH* aOther );
121 
123  void AddItem( SCH_ITEM* aItem );
124 
126  void UpdateItemConnections();
127 
142  static PRIORITY GetDriverPriority( SCH_ITEM* aDriver );
143 
145  {
146  if( m_driver )
147  return GetDriverPriority( m_driver );
148  else
149  return PRIORITY::NONE;
150  }
151 
152 private:
153  wxString driverName( SCH_ITEM* aItem ) const;
154 
155 public:
157 
158  bool m_dirty;
159 
162 
165 
166  long m_code;
167 
174 
177 
180 
183 
186 
187  std::vector<SCH_ITEM*> m_items;
188 
189  std::vector<SCH_ITEM*> m_drivers;
190 
192 
194 
197 
206  std::unordered_map< std::shared_ptr<SCH_CONNECTION>,
207  std::unordered_set<CONNECTION_SUBGRAPH*> > m_bus_neighbors;
208 
214  std::unordered_map< std::shared_ptr<SCH_CONNECTION>,
215  std::unordered_set<CONNECTION_SUBGRAPH*> > m_bus_parents;
216 
217  // Cache for lookup of any hierarchical (sheet) pins on this subgraph (for referring down)
218  std::vector<SCH_SHEET_PIN*> m_hier_pins;
219 
220  // Cache for lookup of any hierarchical ports on this subgraph (for referring up)
221  std::vector<SCH_HIERLABEL*> m_hier_ports;
222 
223  // If not null, this indicates the subgraph on a higher level sheet that is linked to this one
225 
227  std::unordered_map<SCH_ITEM*, wxString> m_driver_name_cache;
228 
234 
237 };
238 
240 typedef std::pair<wxString, int> NET_NAME_CODE;
241 
243 typedef std::map<NET_NAME_CODE, std::vector<CONNECTION_SUBGRAPH*>> NET_MAP;
244 
249 {
250 public:
251  CONNECTION_GRAPH( SCHEMATIC* aSchematic = nullptr ) :
252  m_last_net_code( 1 ),
253  m_last_bus_code( 1 ),
255  m_schematic( aSchematic )
256  {}
257 
259  {
260  Reset();
261  }
262 
263  void Reset();
264 
265  void SetSchematic( SCHEMATIC* aSchematic )
266  {
267  m_schematic = aSchematic;
268  }
269 
277  void Recalculate( const SCH_SHEET_LIST& aSheetList, bool aUnconditional = false,
278  std::function<void( SCH_ITEM* )>* aChangedItemHandler = nullptr );
279 
286  std::shared_ptr<BUS_ALIAS> GetBusAlias( const wxString& aName );
287 
295  std::vector<const CONNECTION_SUBGRAPH*> GetBusesNeedingMigration();
296 
304  int RunERC();
305 
306  const NET_MAP& GetNetMap() const { return m_net_code_to_subgraphs_map; }
307 
314  CONNECTION_SUBGRAPH* FindSubgraphByName( const wxString& aNetName,
315  const SCH_SHEET_PATH& aPath );
316 
323  CONNECTION_SUBGRAPH* FindFirstSubgraphByName( const wxString& aNetName );
324 
326 
327 private:
355  void updateItemConnectivity( const SCH_SHEET_PATH& aSheet,
356  const std::vector<SCH_ITEM*>& aItemList );
357 
371  void buildConnectionGraph();
372 
376  void buildItemSubGraphs();
377 
382  void resolveAllDrivers();
383 
387  void collectAllDriverValues();
388 
394 
398  void processSubGraphs();
399 
405  int assignNewNetCode( SCH_CONNECTION& aConnection );
406 
411  void assignNetCodesToBus( SCH_CONNECTION* aConnection );
412 
419  void propagateToNeighbors( CONNECTION_SUBGRAPH* aSubgraph );
420 
431  static SCH_CONNECTION* matchBusMember( SCH_CONNECTION* aBusConnection,
432  SCH_CONNECTION* aSearch );
433 
442  std::shared_ptr<SCH_CONNECTION> getDefaultConnection( SCH_ITEM* aItem,
443  CONNECTION_SUBGRAPH* aSubgraph );
444 
445  void recacheSubgraphName( CONNECTION_SUBGRAPH* aSubgraph, const wxString& aOldName );
446 
454  bool ercCheckMultipleDrivers( const CONNECTION_SUBGRAPH* aSubgraph );
455 
464  bool ercCheckBusToNetConflicts( const CONNECTION_SUBGRAPH* aSubgraph );
465 
476  bool ercCheckBusToBusConflicts( const CONNECTION_SUBGRAPH* aSubgraph );
477 
490  bool ercCheckBusToBusEntryConflicts( const CONNECTION_SUBGRAPH* aSubgraph );
491 
501  bool ercCheckNoConnects( const CONNECTION_SUBGRAPH* aSubgraph );
502 
511  bool ercCheckFloatingWires( const CONNECTION_SUBGRAPH* aSubgraph );
512 
522  bool ercCheckLabels( const CONNECTION_SUBGRAPH* aSubgraph );
523 
531  int ercCheckHierSheets();
532 
533 public:
534  // TODO(JE) Remove this when pressure valve is removed
535  static bool m_allowRealTime;
536 
537 private:
538  // All the sheets in the schematic (as long as we don't have partial updates)
540 
541  // All connectable items in the schematic
542  std::vector<SCH_ITEM*> m_items;
543 
544  // The owner of all CONNECTION_SUBGRAPH objects
545  std::vector<CONNECTION_SUBGRAPH*> m_subgraphs;
546 
547  // Cache of a subset of m_subgraphs
548  std::vector<CONNECTION_SUBGRAPH*> m_driver_subgraphs;
549 
550  // Cache to lookup subgraphs in m_driver_subgraphs by sheet path
551  std::unordered_map<SCH_SHEET_PATH, std::vector<CONNECTION_SUBGRAPH*>> m_sheet_to_subgraphs_map;
552 
553  std::vector<std::pair<SCH_SHEET_PATH, SCH_PIN*>> m_invisible_power_pins;
554 
555  std::unordered_map< wxString, std::shared_ptr<BUS_ALIAS> > m_bus_alias_cache;
556 
557  std::map<wxString, int> m_net_name_to_code_map;
558 
559  std::map<wxString, int> m_bus_name_to_code_map;
560 
561  std::map<wxString, std::vector<const CONNECTION_SUBGRAPH*>> m_global_label_cache;
562 
563  std::map< std::pair<SCH_SHEET_PATH, wxString>,
564  std::vector<const CONNECTION_SUBGRAPH*> > m_local_label_cache;
565 
566  std::unordered_map<wxString, std::vector<CONNECTION_SUBGRAPH*>> m_net_name_to_subgraphs_map;
567 
568  std::map<SCH_ITEM*, CONNECTION_SUBGRAPH*> m_item_to_subgraph_map;
569 
571 
573 
575 
577 
579 };
580 
581 #endif
CONNECTION_SUBGRAPH * FindSubgraphByName(const wxString &aNetName, const SCH_SHEET_PATH &aPath)
Returns the subgraph for a given net name on a given sheet.
bool ercCheckMultipleDrivers(const CONNECTION_SUBGRAPH *aSubgraph)
If the subgraph has multiple drivers of equal priority that are graphically connected,...
SCH_SHEET_PATH m_sheet
A container for handling SCH_SHEET_PATH objects in a flattened hierarchy.
SCH_CONNECTION * m_driver_connection
Cache for driver connection.
void SetSchematic(SCHEMATIC *aSchematic)
void propagateToNeighbors(CONNECTION_SUBGRAPH *aSubgraph)
Updates all neighbors of a subgraph with this one's connectivity info.
bool ercCheckBusToBusEntryConflicts(const CONNECTION_SUBGRAPH *aSubgraph)
Checks one subgraph for conflicting bus entry to bus connections.
void resolveAllDrivers()
Finds all subgraphs in the connection graph and calls ResolveDrivers() in parallel.
void buildConnectionGraph()
Generates the connection graph (after all item connectivity has been updated)
std::unordered_map< wxString, std::shared_ptr< BUS_ALIAS > > m_bus_alias_cache
Holds all the data relating to one schematic.
Definition: schematic.h:59
std::shared_ptr< BUS_ALIAS > GetBusAlias(const wxString &aName)
Returns a bus alias pointer for the given name if it exists (from cache)
std::unordered_map< std::shared_ptr< SCH_CONNECTION >, std::unordered_set< CONNECTION_SUBGRAPH * > > m_bus_neighbors
If a subgraph is a bus, this map contains links between the bus members and any local sheet neighbors...
SCH_ITEM * m_bus_entry
Bus entry in graph, if any.
CONNECTION_SUBGRAPH(CONNECTION_GRAPH *aGraph)
Calculates the connectivity of a schematic and generates netlists.
void Absorb(CONNECTION_SUBGRAPH *aOther)
Combines another subgraph on the same sheet into this one.
SCH_ITEM * m_second_driver
Used for multiple drivers ERC message; stores the second possible driver (or nullptr)
bool m_absorbed
True if this subgraph has been absorbed into another. No pointers here are safe if so!
std::unordered_map< SCH_SHEET_PATH, std::vector< CONNECTION_SUBGRAPH * > > m_sheet_to_subgraphs_map
std::pair< wxString, int > NET_NAME_CODE
Associates a net code with the final name of a net.
bool ercCheckFloatingWires(const CONNECTION_SUBGRAPH *aSubgraph)
Checks one subgraph for floating wires.
std::vector< SCH_SHEET_PIN * > m_hier_pins
bool m_local_driver
True if the driver is a local (i.e. non-global) type.
std::vector< CONNECTION_SUBGRAPH * > m_subgraphs
~CONNECTION_SUBGRAPH()=default
std::unordered_map< std::shared_ptr< SCH_CONNECTION >, std::unordered_set< CONNECTION_SUBGRAPH * > > m_bus_parents
If this is a net, this vector contains links to any same-sheet buses that contain it.
NET_MAP m_net_code_to_subgraphs_map
Schematic editor (Eeschema) main window.
void Recalculate(const SCH_SHEET_LIST &aSheetList, bool aUnconditional=false, std::function< void(SCH_ITEM *)> *aChangedItemHandler=nullptr)
Updates the connection graph for the given list of sheets.
std::vector< SCH_ITEM * > m_items
SCHEMATIC * m_schematic
The schematic this graph represents.
void buildItemSubGraphs()
Generates individual item subgraphs on a per-sheet basis.
std::unordered_map< wxString, std::vector< CONNECTION_SUBGRAPH * > > m_net_name_to_subgraphs_map
A subgraph is a set of items that are electrically connected on a single sheet.
void updateItemConnectivity(const SCH_SHEET_PATH &aSheet, const std::vector< SCH_ITEM * > &aItemList)
Updates the graphical connectivity between items (i.e.
int ercCheckHierSheets()
Checks that a hierarchical sheet has at least one matching label inside the sheet for each port on th...
bool m_multiple_drivers
True if this subgraph contains more than one driver that should be shorted together in the netlist.
void recacheSubgraphName(CONNECTION_SUBGRAPH *aSubgraph, const wxString &aOldName)
bool ercCheckBusToNetConflicts(const CONNECTION_SUBGRAPH *aSubgraph)
Checks one subgraph for conflicting connections between net and bus labels.
CONNECTION_GRAPH * m_graph
const wxString & GetNameForDriver(SCH_ITEM *aItem)
Returns the candidate net name for a driver.
int assignNewNetCode(SCH_CONNECTION &aConnection)
Helper to assign a new net code to a connection.
CONNECTION_GRAPH(SCHEMATIC *aSchematic=nullptr)
bool ercCheckNoConnects(const CONNECTION_SUBGRAPH *aSubgraph)
Checks one subgraph for proper presence or absence of no-connect symbols.
std::vector< SCH_ITEM * > m_items
bool ResolveDrivers(bool aCheckMultipleDrivers=false)
Determines which potential driver should drive the subgraph.
std::vector< CONNECTION_SUBGRAPH * > m_driver_subgraphs
const NET_MAP & GetNetMap() const
void AddItem(SCH_ITEM *aItem)
Adds a new item to the subgraph.
bool m_strong_driver
True if the driver is "strong": a label or power object.
std::vector< SCH_ITEM * > m_drivers
Define a sheet pin (label) used in sheets to create hierarchical schematics.
Definition: sch_sheet_pin.h:65
Handle access to a stack of flattened SCH_SHEET objects by way of a path for creating a flattened sch...
void generateInvisiblePinSubGraphs()
Iterate through the invisible power pins to collect the global labels as drivers.
CONNECTION_SUBGRAPH * FindFirstSubgraphByName(const wxString &aNetName)
Retrieves a subgraph for the given net name, if one exists.
std::vector< SCH_HIERLABEL * > m_hier_ports
std::map< wxString, std::vector< const CONNECTION_SUBGRAPH * > > m_global_label_cache
void assignNetCodesToBus(SCH_CONNECTION *aConnection)
Ensures all members of the bus connection have a valid net code assigned.
SCH_ITEM * m_first_driver
Stores the primary driver for the multiple drivers ERC check.
std::vector< std::pair< SCH_SHEET_PATH, SCH_PIN * > > m_invisible_power_pins
static bool m_allowRealTime
void processSubGraphs()
Process all subgraphs to assign netcodes and merge subgraphs based on labels.
CONNECTION_SUBGRAPH * m_absorbed_by
If this subgraph is absorbed, points to the absorbing (and valid) subgraph.
std::map< NET_NAME_CODE, std::vector< CONNECTION_SUBGRAPH * > > NET_MAP
Associates a NET_CODE_NAME with all the subgraphs in that net.
Each graphical item can have a SCH_CONNECTION describing its logical connection (to a bus or net).
SCH_SHEET_LIST m_sheetList
std::shared_ptr< SCH_CONNECTION > getDefaultConnection(SCH_ITEM *aItem, CONNECTION_SUBGRAPH *aSubgraph)
Builds a new default connection for the given item based on its properties.
std::vector< SCH_ITEM * > GetBusLabels() const
Returns all the bus labels attached to this subgraph (if any)
std::map< wxString, int > m_bus_name_to_code_map
wxString driverName(SCH_ITEM *aItem) const
std::map< wxString, int > m_net_name_to_code_map
CONNECTION_SUBGRAPH * m_hier_parent
void collectAllDriverValues()
Maps the driver values for each subgraph.
CONNECTION_SUBGRAPH * GetSubgraphForItem(SCH_ITEM *aItem)
SCH_ITEM * m_no_connect
No-connect item in graph, if any.
std::map< std::pair< SCH_SHEET_PATH, wxString >, std::vector< const CONNECTION_SUBGRAPH * > > m_local_label_cache
std::vector< const CONNECTION_SUBGRAPH * > GetBusesNeedingMigration()
Determines which subgraphs have more than one conflicting bus label.
bool ercCheckLabels(const CONNECTION_SUBGRAPH *aSubgraph)
Checks one subgraph for proper connection of labels.
Base class for any item which can be embedded within the SCHEMATIC container class,...
Definition: sch_item.h:182
std::map< SCH_ITEM *, CONNECTION_SUBGRAPH * > m_item_to_subgraph_map
int RunERC()
Runs electrical rule checks on the connectivity graph.
wxString GetNetName() const
Returns the fully-qualified net name for this subgraph (if one exists)
PRIORITY GetDriverPriority()
static SCH_CONNECTION * matchBusMember(SCH_CONNECTION *aBusConnection, SCH_CONNECTION *aSearch)
Search for a matching bus member inside a bus connection.
bool ercCheckBusToBusConflicts(const CONNECTION_SUBGRAPH *aSubgraph)
Checks one subgraph for conflicting connections between two bus items.
std::unordered_map< SCH_ITEM *, wxString > m_driver_name_cache
A cache of escaped netnames from schematic items.
void UpdateItemConnections()
Updates all items to match the driver connection.