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 <jon@craftyjon.com>
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 
378  int assignNewNetCode( SCH_CONNECTION& aConnection );
379 
384  void assignNetCodesToBus( SCH_CONNECTION* aConnection );
385 
392  void propagateToNeighbors( CONNECTION_SUBGRAPH* aSubgraph );
393 
404  static SCH_CONNECTION* matchBusMember( SCH_CONNECTION* aBusConnection,
405  SCH_CONNECTION* aSearch );
406 
415  std::shared_ptr<SCH_CONNECTION> getDefaultConnection( SCH_ITEM* aItem,
416  CONNECTION_SUBGRAPH* aSubgraph );
417 
418  void recacheSubgraphName( CONNECTION_SUBGRAPH* aSubgraph, const wxString& aOldName );
419 
427  bool ercCheckMultipleDrivers( const CONNECTION_SUBGRAPH* aSubgraph );
428 
437  bool ercCheckBusToNetConflicts( const CONNECTION_SUBGRAPH* aSubgraph );
438 
449  bool ercCheckBusToBusConflicts( const CONNECTION_SUBGRAPH* aSubgraph );
450 
463  bool ercCheckBusToBusEntryConflicts( const CONNECTION_SUBGRAPH* aSubgraph );
464 
474  bool ercCheckNoConnects( const CONNECTION_SUBGRAPH* aSubgraph );
475 
484  bool ercCheckFloatingWires( const CONNECTION_SUBGRAPH* aSubgraph );
485 
495  bool ercCheckLabels( const CONNECTION_SUBGRAPH* aSubgraph );
496 
504  int ercCheckHierSheets();
505 
506 public:
507  // TODO(JE) Remove this when pressure valve is removed
508  static bool m_allowRealTime;
509 
510 private:
511  // All the sheets in the schematic (as long as we don't have partial updates)
513 
514  // All connectable items in the schematic
515  std::vector<SCH_ITEM*> m_items;
516 
517  // The owner of all CONNECTION_SUBGRAPH objects
518  std::vector<CONNECTION_SUBGRAPH*> m_subgraphs;
519 
520  // Cache of a subset of m_subgraphs
521  std::vector<CONNECTION_SUBGRAPH*> m_driver_subgraphs;
522 
523  // Cache to lookup subgraphs in m_driver_subgraphs by sheet path
524  std::unordered_map<SCH_SHEET_PATH, std::vector<CONNECTION_SUBGRAPH*>> m_sheet_to_subgraphs_map;
525 
526  std::vector<std::pair<SCH_SHEET_PATH, SCH_PIN*>> m_invisible_power_pins;
527 
528  std::unordered_map< wxString, std::shared_ptr<BUS_ALIAS> > m_bus_alias_cache;
529 
530  std::map<wxString, int> m_net_name_to_code_map;
531 
532  std::map<wxString, int> m_bus_name_to_code_map;
533 
534  std::map<wxString, std::vector<const CONNECTION_SUBGRAPH*>> m_global_label_cache;
535 
536  std::map< std::pair<SCH_SHEET_PATH, wxString>,
537  std::vector<const CONNECTION_SUBGRAPH*> > m_local_label_cache;
538 
539  std::unordered_map<wxString, std::vector<CONNECTION_SUBGRAPH*>> m_net_name_to_subgraphs_map;
540 
541  std::map<SCH_ITEM*, CONNECTION_SUBGRAPH*> m_item_to_subgraph_map;
542 
544 
546 
548 
550 
552 };
553 
554 #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 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.
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...
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
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
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:197
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.