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
40class SCHEMATIC;
41class SCH_EDIT_FRAME;
42class SCH_HIERLABEL;
43class SCH_PIN;
44class SCH_SHEET_PIN;
45
46
61{
62public:
63 enum class PRIORITY
64 {
65 INVALID = -1,
66 NONE = 0,
67 PIN,
68 SHEET_PIN,
69 HIER_LABEL,
70 LOCAL_LABEL,
71 POWER_PIN,
72 GLOBAL
73 };
74
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
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 ) const;
116
117 const wxString GetNetclassForDriver( SCH_ITEM* aItem ) const;
118
120 void Absorb( CONNECTION_SUBGRAPH* aOther );
121
123 void AddItem( SCH_ITEM* aItem );
124
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
152private:
153 wxString driverName( SCH_ITEM* aItem ) const;
154
155public:
157
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 mutable std::unordered_map<SCH_ITEM*, wxString> m_driver_name_cache;
228
234
237};
238
240{
241 wxString Name;
243
244 bool operator==(const NET_NAME_CODE_CACHE_KEY& other) const
245 {
246 return Name == other.Name && Netcode == other.Netcode;
247 }
248};
249
250namespace std
251{
252 template <>
254 {
255 std::size_t operator()( const NET_NAME_CODE_CACHE_KEY& k ) const
256 {
257 const std::size_t prime = 19937;
258
259 return hash<wxString>()( k.Name ) ^ ( hash<int>()( k.Netcode ) * prime );
260 }
261 };
262}
263
265typedef std::unordered_map<NET_NAME_CODE_CACHE_KEY, std::vector<CONNECTION_SUBGRAPH*>> NET_MAP;
266
271{
272public:
273 CONNECTION_GRAPH( SCHEMATIC* aSchematic = nullptr ) :
274 m_last_net_code( 1 ),
275 m_last_bus_code( 1 ),
277 m_schematic( aSchematic )
278 {}
279
281 {
282 Reset();
283 }
284
285 void Reset();
286
287 void SetSchematic( SCHEMATIC* aSchematic )
288 {
289 m_schematic = aSchematic;
290 }
291
299 void Recalculate( const SCH_SHEET_LIST& aSheetList, bool aUnconditional = false,
300 std::function<void( SCH_ITEM* )>* aChangedItemHandler = nullptr );
301
308 std::shared_ptr<BUS_ALIAS> GetBusAlias( const wxString& aName );
309
317 std::vector<const CONNECTION_SUBGRAPH*> GetBusesNeedingMigration();
318
326 int RunERC();
327
329
336 CONNECTION_SUBGRAPH* FindSubgraphByName( const wxString& aNetName,
337 const SCH_SHEET_PATH& aPath );
338
345 CONNECTION_SUBGRAPH* FindFirstSubgraphByName( const wxString& aNetName );
346
348
354 wxString GetResolvedSubgraphName( const CONNECTION_SUBGRAPH* aSubGraph ) const;
355
356private:
384 void updateItemConnectivity( const SCH_SHEET_PATH& aSheet,
385 const std::vector<SCH_ITEM*>& aItemList );
386
400 void buildConnectionGraph( std::function<void( SCH_ITEM* )>* aChangedItemHandler );
401
405 void buildItemSubGraphs();
406
411 void resolveAllDrivers();
412
417
423
427 void processSubGraphs();
428
434 int assignNewNetCode( SCH_CONNECTION& aConnection );
435
440 void assignNetCodesToBus( SCH_CONNECTION* aConnection );
441
451 void propagateToNeighbors( CONNECTION_SUBGRAPH* aSubgraph, bool aForce );
452
463 static SCH_CONNECTION* matchBusMember( SCH_CONNECTION* aBusConnection,
464 SCH_CONNECTION* aSearch );
465
474 std::shared_ptr<SCH_CONNECTION> getDefaultConnection( SCH_ITEM* aItem,
475 CONNECTION_SUBGRAPH* aSubgraph );
476
477 void recacheSubgraphName( CONNECTION_SUBGRAPH* aSubgraph, const wxString& aOldName );
478
486 bool ercCheckMultipleDrivers( const CONNECTION_SUBGRAPH* aSubgraph );
487
488 bool ercCheckNetclassConflicts( const std::vector<CONNECTION_SUBGRAPH*>& subgraphs );
489
498 bool ercCheckBusToNetConflicts( const CONNECTION_SUBGRAPH* aSubgraph );
499
510 bool ercCheckBusToBusConflicts( const CONNECTION_SUBGRAPH* aSubgraph );
511
525
535 bool ercCheckNoConnects( const CONNECTION_SUBGRAPH* aSubgraph );
536
545 bool ercCheckFloatingWires( const CONNECTION_SUBGRAPH* aSubgraph );
546
556 bool ercCheckLabels( const CONNECTION_SUBGRAPH* aSubgraph );
557
565 int ercCheckHierSheets();
566
572 size_t hasPins( const CONNECTION_SUBGRAPH* aLocSubgraph );
573
574
575private:
576 // All the sheets in the schematic (as long as we don't have partial updates)
578
579 // All connectable items in the schematic
580 std::vector<SCH_ITEM*> m_items;
581
582 // The owner of all CONNECTION_SUBGRAPH objects
583 std::vector<CONNECTION_SUBGRAPH*> m_subgraphs;
584
585 // Cache of a subset of m_subgraphs
586 std::vector<CONNECTION_SUBGRAPH*> m_driver_subgraphs;
587
588 // Cache to lookup subgraphs in m_driver_subgraphs by sheet path
589 std::unordered_map<SCH_SHEET_PATH, std::vector<CONNECTION_SUBGRAPH*>> m_sheet_to_subgraphs_map;
590
591 std::vector<std::pair<SCH_SHEET_PATH, SCH_PIN*>> m_invisible_power_pins;
592
593 std::unordered_map<wxString, std::shared_ptr<BUS_ALIAS>> m_bus_alias_cache;
594
595 std::unordered_map<wxString, int> m_net_name_to_code_map;
596
597 std::unordered_map<wxString, int> m_bus_name_to_code_map;
598
599 std::unordered_map<wxString, std::vector<const CONNECTION_SUBGRAPH*>> m_global_label_cache;
600
601 std::map< std::pair<SCH_SHEET_PATH, wxString>,
602 std::vector<const CONNECTION_SUBGRAPH*> > m_local_label_cache;
603
604 std::unordered_map<wxString, std::vector<CONNECTION_SUBGRAPH*>> m_net_name_to_subgraphs_map;
605
606 std::unordered_map<SCH_ITEM*, CONNECTION_SUBGRAPH*> m_item_to_subgraph_map;
607
609
611
613
615
617};
618
619#endif
Calculates the connectivity of a schematic and generates netlists.
int RunERC()
Runs electrical rule checks on the connectivity graph.
void SetSchematic(SCHEMATIC *aSchematic)
bool ercCheckBusToBusConflicts(const CONNECTION_SUBGRAPH *aSubgraph)
Checks one subgraph for conflicting connections between two bus items.
void processSubGraphs()
Process all subgraphs to assign netcodes and merge subgraphs based on labels.
bool ercCheckNetclassConflicts(const std::vector< CONNECTION_SUBGRAPH * > &subgraphs)
bool ercCheckLabels(const CONNECTION_SUBGRAPH *aSubgraph)
Checks one subgraph for proper connection of labels.
void collectAllDriverValues()
Maps the driver values for each subgraph.
CONNECTION_SUBGRAPH * FindSubgraphByName(const wxString &aNetName, const SCH_SHEET_PATH &aPath)
Returns the subgraph for a given net name on a given sheet.
void recacheSubgraphName(CONNECTION_SUBGRAPH *aSubgraph, const wxString &aOldName)
const NET_MAP & GetNetMap() const
static SCH_CONNECTION * matchBusMember(SCH_CONNECTION *aBusConnection, SCH_CONNECTION *aSearch)
Search for a matching bus member inside a bus connection.
std::unordered_map< wxString, std::shared_ptr< BUS_ALIAS > > m_bus_alias_cache
SCHEMATIC * m_schematic
The schematic this graph represents.
std::unordered_map< SCH_SHEET_PATH, std::vector< CONNECTION_SUBGRAPH * > > m_sheet_to_subgraphs_map
CONNECTION_SUBGRAPH * FindFirstSubgraphByName(const wxString &aNetName)
Retrieves a subgraph for the given net name, if one exists.
void propagateToNeighbors(CONNECTION_SUBGRAPH *aSubgraph, bool aForce)
Updates all neighbors of a subgraph with this one's connectivity info.
void buildItemSubGraphs()
Generates individual item subgraphs on a per-sheet basis.
bool ercCheckMultipleDrivers(const CONNECTION_SUBGRAPH *aSubgraph)
If the subgraph has multiple drivers of equal priority that are graphically connected,...
CONNECTION_SUBGRAPH * GetSubgraphForItem(SCH_ITEM *aItem)
SCH_SHEET_LIST m_sheetList
std::unordered_map< wxString, int > m_net_name_to_code_map
void buildConnectionGraph(std::function< void(SCH_ITEM *)> *aChangedItemHandler)
Generates the connection graph (after all item connectivity has been updated)
int ercCheckHierSheets()
Checks that a hierarchical sheet has at least one matching label inside the sheet for each port on th...
bool ercCheckBusToNetConflicts(const CONNECTION_SUBGRAPH *aSubgraph)
Checks one subgraph for conflicting connections between net and bus labels.
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< const CONNECTION_SUBGRAPH * > GetBusesNeedingMigration()
Determines which subgraphs have more than one conflicting bus label.
int assignNewNetCode(SCH_CONNECTION &aConnection)
Helper to assign a new net code to a connection.
std::map< std::pair< SCH_SHEET_PATH, wxString >, std::vector< const CONNECTION_SUBGRAPH * > > m_local_label_cache
std::vector< std::pair< SCH_SHEET_PATH, SCH_PIN * > > m_invisible_power_pins
void generateInvisiblePinSubGraphs()
Iterate through the invisible power pins to collect the global labels as drivers.
void assignNetCodesToBus(SCH_CONNECTION *aConnection)
Ensures all members of the bus connection have a valid net code assigned.
std::unordered_map< wxString, int > m_bus_name_to_code_map
std::unordered_map< wxString, std::vector< const CONNECTION_SUBGRAPH * > > m_global_label_cache
std::vector< CONNECTION_SUBGRAPH * > m_subgraphs
CONNECTION_GRAPH(SCHEMATIC *aSchematic=nullptr)
bool ercCheckNoConnects(const CONNECTION_SUBGRAPH *aSubgraph)
Checks one subgraph for proper presence or absence of no-connect symbols.
size_t hasPins(const CONNECTION_SUBGRAPH *aLocSubgraph)
Get the number of pins in a given subgraph.
std::vector< SCH_ITEM * > m_items
std::unordered_map< wxString, std::vector< CONNECTION_SUBGRAPH * > > m_net_name_to_subgraphs_map
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< SCH_ITEM *, CONNECTION_SUBGRAPH * > m_item_to_subgraph_map
wxString GetResolvedSubgraphName(const CONNECTION_SUBGRAPH *aSubGraph) const
Returns the fully-resolved netname for a given subgraph.
bool ercCheckBusToBusEntryConflicts(const CONNECTION_SUBGRAPH *aSubgraph)
Checks one subgraph for conflicting bus entry to bus connections.
std::vector< CONNECTION_SUBGRAPH * > m_driver_subgraphs
NET_MAP m_net_code_to_subgraphs_map
bool ercCheckFloatingWires(const CONNECTION_SUBGRAPH *aSubgraph)
Checks one subgraph for floating wires.
void resolveAllDrivers()
Finds all subgraphs in the connection graph and calls ResolveDrivers() in parallel.
void updateItemConnectivity(const SCH_SHEET_PATH &aSheet, const std::vector< SCH_ITEM * > &aItemList)
Updates the graphical connectivity between items (i.e.
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.
A subgraph is a set of items that are electrically connected on a single sheet.
wxString driverName(SCH_ITEM *aItem) const
PRIORITY GetDriverPriority()
bool m_strong_driver
True if the driver is "strong": a label or power object.
std::vector< SCH_ITEM * > m_items
SCH_ITEM * m_no_connect
No-connect item in graph, if any.
std::vector< SCH_ITEM * > m_drivers
SCH_ITEM * m_bus_entry
Bus entry in graph, if any.
SCH_SHEET_PATH m_sheet
void UpdateItemConnections()
Updates all items to match the driver connection.
const wxString GetNetclassForDriver(SCH_ITEM *aItem) const
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...
CONNECTION_GRAPH * m_graph
std::unordered_map< SCH_ITEM *, wxString > m_driver_name_cache
A cache of escaped netnames from schematic items.
const wxString & GetNameForDriver(SCH_ITEM *aItem) const
Returns the candidate net name for a driver.
wxString GetNetName() const
Returns the fully-qualified net name for this subgraph (if one exists)
bool m_multiple_drivers
True if this subgraph contains more than one driver that should be shorted together in the netlist.
bool ResolveDrivers(bool aCheckMultipleDrivers=false)
Determines which potential driver should drive the subgraph.
SCH_ITEM * m_first_driver
Stores the primary driver for the multiple drivers ERC check.
bool m_absorbed
True if this subgraph has been absorbed into another. No pointers here are safe if so!
SCH_CONNECTION * m_driver_connection
Cache for driver connection.
CONNECTION_SUBGRAPH * m_absorbed_by
If this subgraph is absorbed, points to the absorbing (and valid) subgraph.
void AddItem(SCH_ITEM *aItem)
Adds a new item to the subgraph.
std::vector< SCH_ITEM * > GetBusLabels() const
Returns all the bus labels attached to this subgraph (if any)
void Absorb(CONNECTION_SUBGRAPH *aOther)
Combines another subgraph on the same sheet into this one.
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.
CONNECTION_SUBGRAPH(CONNECTION_GRAPH *aGraph)
std::vector< SCH_HIERLABEL * > m_hier_ports
std::vector< SCH_SHEET_PIN * > m_hier_pins
~CONNECTION_SUBGRAPH()=default
CONNECTION_SUBGRAPH * m_hier_parent
SCH_ITEM * m_second_driver
Used for multiple drivers ERC message; stores the second possible driver (or nullptr)
bool m_local_driver
True if the driver is a local (i.e. non-global) type.
Holds all the data relating to one schematic.
Definition: schematic.h:61
Each graphical item can have a SCH_CONNECTION describing its logical connection (to a bus or net).
Schematic editor (Eeschema) main window.
Base class for any item which can be embedded within the SCHEMATIC container class,...
Definition: sch_item.h:147
A container for handling SCH_SHEET_PATH objects in a flattened hierarchy.
Handle access to a stack of flattened SCH_SHEET objects by way of a path for creating a flattened sch...
Define a sheet pin (label) used in sheets to create hierarchical schematics.
Definition: sch_sheet_pin.h:66
std::unordered_map< NET_NAME_CODE_CACHE_KEY, std::vector< CONNECTION_SUBGRAPH * > > NET_MAP
Associates a NET_CODE_NAME with all the subgraphs in that net.
@ NONE
Definition: kibis.h:53
@ INVALID
Definition: kiface_ids.h:32
Definition: bitmap.cpp:64
bool operator==(const NET_NAME_CODE_CACHE_KEY &other) const
std::size_t operator()(const NET_NAME_CODE_CACHE_KEY &k) const