KiCad PCB EDA Suite
Loading...
Searching...
No Matches
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 <utility>
27#include <vector>
28
29#include <erc/erc_settings.h>
30#include <sch_connection.h>
31#include <sch_item.h>
32#include <wx/treectrl.h>
33
34
35#ifdef DEBUG
36// Uncomment this line to enable connectivity debugging features
37// #define CONNECTIVITY_DEBUG
38#endif
39
40
42class SCHEMATIC;
43class SCH_EDIT_FRAME;
44class SCH_HIERLABEL;
45class SCH_PIN;
46class SCH_SHEET_PIN;
47
48
62{
63public:
64 enum class PRIORITY
65 {
66 INVALID = -1,
67 NONE = 0,
68 PIN,
73 GLOBAL
74 };
75
77 m_graph( aGraph ),
78 m_dirty( false ),
79 m_absorbed( false ),
80 m_is_bus_member( false ),
81 m_absorbed_by( nullptr ),
82 m_code( -1 ),
83 m_multiple_drivers( false ),
84 m_strong_driver( false ),
85 m_local_driver( false ),
86 m_bus_entry( nullptr ),
87 m_hier_parent( nullptr ),
88 m_driver( nullptr ),
89 m_no_connect( nullptr ),
90 m_driver_connection( nullptr )
91 {}
92
94 {
95 for( SCH_CONNECTION* connection : m_bus_element_connections )
96 delete connection;
97 }
98
99 friend class CONNECTION_GRAPH;
100
110 bool ResolveDrivers( bool aCheckMultipleDrivers = false );
111
115 wxString GetNetName() const;
116
118 std::vector<SCH_ITEM*> GetVectorBusLabels() const;
119
121 std::vector<SCH_ITEM*> GetAllBusLabels() const;
122
124 const wxString& GetNameForDriver( SCH_ITEM* aItem ) const;
125
130 const std::vector<std::pair<wxString, SCH_ITEM*>>
131 GetNetclassesForDriver( SCH_ITEM* aItem, bool returnAll ) const;
132
134 void Absorb( CONNECTION_SUBGRAPH* aOther );
135
137 void AddItem( SCH_ITEM* aItem );
138
141
143 const std::set<SCH_ITEM*>& GetItems() const
144 {
145 return m_items;
146 }
147
149 void getAllConnectedItems( std::set<std::pair<SCH_SHEET_PATH, SCH_ITEM*>>& aItems,
150 std::set<CONNECTION_SUBGRAPH*>& aSubgraphs );
151
166 static PRIORITY GetDriverPriority( SCH_ITEM* aDriver );
167
169 {
170 if( m_driver )
171 return GetDriverPriority( m_driver );
172 else
173 return PRIORITY::NONE;
174 }
175
180 const SCH_ITEM* GetDriver() const
181 {
182 return m_driver;
183 }
184
189 {
190 return m_driver_connection;
191 }
192
196 const SCH_ITEM* GetNoConnect() const
197 {
198 return m_no_connect;
199 }
200
202 {
203 return m_sheet;
204 }
205
206 void RemoveItem( SCH_ITEM* aItem );
207
211 void ExchangeItem( SCH_ITEM* aOldItem, SCH_ITEM* aNewItem );
212
213 // Use this to keep a connection pointer that is not owned by any item
214 // This will be destroyed with the subgraph
216 {
217 m_bus_element_connections.insert( aConnection );
218 }
219
220private:
221 wxString driverName( SCH_ITEM* aItem ) const;
222
224
226
229
235
238
240 std::set<CONNECTION_SUBGRAPH*> m_absorbed_subgraphs;
241
242 long m_code;
243
250
253
256
259
260 std::set<SCH_ITEM*> m_drivers;
261
270 std::unordered_map< std::shared_ptr<SCH_CONNECTION>,
271 std::unordered_set<CONNECTION_SUBGRAPH*> > m_bus_neighbors;
272
278 std::unordered_map< std::shared_ptr<SCH_CONNECTION>,
279 std::unordered_set<CONNECTION_SUBGRAPH*> > m_bus_parents;
280
282 std::set<SCH_SHEET_PIN*> m_hier_pins;
283
285 std::set<SCH_HIERLABEL*> m_hier_ports;
286
289
292 std::unordered_set<CONNECTION_SUBGRAPH*> m_hier_children;
293
295 mutable std::unordered_map<SCH_ITEM*, wxString> m_driver_name_cache;
296
299
301 std::set<SCH_ITEM*> m_items;
302
305
308
311
314 std::set<SCH_CONNECTION*> m_bus_element_connections;
315
316 std::mutex m_driver_mutex;
317};
318
320{
321 wxString Name;
323
324 bool operator==(const NET_NAME_CODE_CACHE_KEY& other) const
325 {
326 return Name == other.Name && Netcode == other.Netcode;
327 }
328};
329
330namespace std
331{
332 template <>
334 {
335 std::size_t operator()( const NET_NAME_CODE_CACHE_KEY& k ) const
336 {
337 const std::size_t prime = 19937;
338
339 return hash<wxString>()( k.Name ) ^ ( hash<int>()( k.Netcode ) * prime );
340 }
341 };
342}
343
345typedef std::unordered_map<NET_NAME_CODE_CACHE_KEY, std::vector<CONNECTION_SUBGRAPH*>> NET_MAP;
346
351{
352public:
353 CONNECTION_GRAPH( SCHEMATIC* aSchematic = nullptr ) :
354 m_last_net_code( 1 ),
355 m_last_bus_code( 1 ),
357 m_schematic( aSchematic )
358 {}
359
361 {
362 Reset();
363 }
364
365 void Reset();
366
367 void SetSchematic( SCHEMATIC* aSchematic )
368 {
369 m_schematic = aSchematic;
370 }
371
372 void SetLastCodes( const CONNECTION_GRAPH* aOther )
373 {
377 }
378
386 void Recalculate( const SCH_SHEET_LIST& aSheetList, bool aUnconditional = false,
387 std::function<void( SCH_ITEM* )>* aChangedItemHandler = nullptr );
388
395 std::shared_ptr<BUS_ALIAS> GetBusAlias( const wxString& aName );
396
404 std::vector<const CONNECTION_SUBGRAPH*> GetBusesNeedingMigration();
405
413 int RunERC();
414
416
424 CONNECTION_SUBGRAPH* FindSubgraphByName( const wxString& aNetName,
425 const SCH_SHEET_PATH& aPath );
426
435 CONNECTION_SUBGRAPH* FindFirstSubgraphByName( const wxString& aNetName );
436
438
439 const std::vector<CONNECTION_SUBGRAPH*> GetAllSubgraphs( const wxString& aNetName ) const;
440
447 wxString GetResolvedSubgraphName( const CONNECTION_SUBGRAPH* aSubGraph ) const;
448
456 std::set<std::pair<SCH_SHEET_PATH, SCH_ITEM*>> ExtractAffectedItems(
457 const std::set<SCH_ITEM*> &aItems );
458
466 void Merge( CONNECTION_GRAPH& aGraph );
467
468 void RemoveItem( SCH_ITEM* aItem );
469
473 void ExchangeItem( SCH_ITEM* aOldItem, SCH_ITEM* aNewItem );
474
475private:
503 void updateItemConnectivity( const SCH_SHEET_PATH& aSheet,
504 const std::vector<SCH_ITEM*>& aItemList );
505
523 void buildConnectionGraph( std::function<void( SCH_ITEM* )>* aChangedItemHandler, bool aUnconditional );
524
528 void buildItemSubGraphs();
529
533 void resolveAllDrivers();
534
539
544
549
553 void processSubGraphs();
554
560 int assignNewNetCode( SCH_CONNECTION& aConnection );
561
567 int getOrCreateNetCode( const wxString& aNetName );
568
574 void assignNetCodesToBus( SCH_CONNECTION* aConnection );
575
585 void propagateToNeighbors( CONNECTION_SUBGRAPH* aSubgraph, bool aForce );
586
592 void removeSubgraphs( std::set<CONNECTION_SUBGRAPH*>& aSubgraphs );
593
604 static SCH_CONNECTION* matchBusMember( SCH_CONNECTION* aBusConnection,
605 SCH_CONNECTION* aSearch );
606
616 std::shared_ptr<SCH_CONNECTION> getDefaultConnection( SCH_ITEM* aItem,
617 CONNECTION_SUBGRAPH* aSubgraph );
618
619 void recacheSubgraphName( CONNECTION_SUBGRAPH* aSubgraph, const wxString& aOldName );
620
629 bool ercCheckMultipleDrivers( const CONNECTION_SUBGRAPH* aSubgraph );
630
631 bool ercCheckNetclassConflicts( const std::vector<CONNECTION_SUBGRAPH*>& subgraphs );
632
641 bool ercCheckBusToNetConflicts( const CONNECTION_SUBGRAPH* aSubgraph );
642
653 bool ercCheckBusToBusConflicts( const CONNECTION_SUBGRAPH* aSubgraph );
654
668
678 bool ercCheckNoConnects( const CONNECTION_SUBGRAPH* aSubgraph );
679
688 bool ercCheckFloatingWires( const CONNECTION_SUBGRAPH* aSubgraph );
689
699 bool ercCheckLabels( const CONNECTION_SUBGRAPH* aSubgraph );
700
708 int ercCheckHierSheets();
709
714
721 size_t hasPins( const CONNECTION_SUBGRAPH* aLocSubgraph );
722
723
724private:
727
729 std::vector<SCH_ITEM*> m_items;
730
732 std::vector<CONNECTION_SUBGRAPH*> m_subgraphs;
733
735 std::vector<CONNECTION_SUBGRAPH*> m_driver_subgraphs;
736
738 std::unordered_map<SCH_SHEET_PATH, std::vector<CONNECTION_SUBGRAPH*>> m_sheet_to_subgraphs_map;
739
740 std::vector<std::pair<SCH_SHEET_PATH, SCH_PIN*>> m_global_power_pins;
741
742 std::unordered_map<wxString, std::shared_ptr<BUS_ALIAS>> m_bus_alias_cache;
743
744 std::unordered_map<wxString, int> m_net_name_to_code_map;
745
746 std::unordered_map<wxString, int> m_bus_name_to_code_map;
747
748 std::unordered_map<wxString, std::vector<const CONNECTION_SUBGRAPH*>> m_global_label_cache;
749
750 std::map< std::pair<SCH_SHEET_PATH, wxString>,
751 std::vector<const CONNECTION_SUBGRAPH*> > m_local_label_cache;
752
753 std::unordered_map<wxString, std::vector<CONNECTION_SUBGRAPH*>> m_net_name_to_subgraphs_map;
754
755 std::unordered_map<SCH_ITEM*, CONNECTION_SUBGRAPH*> m_item_to_subgraph_map;
756
758
760
762
764
766};
767
768#endif
Calculate the connectivity of a schematic and generates netlists.
int RunERC()
Run electrical rule checks on the connectivity graph.
void SetSchematic(SCHEMATIC *aSchematic)
bool ercCheckBusToBusConflicts(const CONNECTION_SUBGRAPH *aSubgraph)
Check 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)
Check one subgraph for proper connection of labels.
void RemoveItem(SCH_ITEM *aItem)
void collectAllDriverValues()
Map the driver values for each subgraph.
CONNECTION_SUBGRAPH * FindSubgraphByName(const wxString &aNetName, const SCH_SHEET_PATH &aPath)
Return 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
Cache to lookup subgraphs in m_driver_subgraphs by sheet path.
CONNECTION_SUBGRAPH * FindFirstSubgraphByName(const wxString &aNetName)
Retrieve a subgraph for the given net name, if one exists.
void propagateToNeighbors(CONNECTION_SUBGRAPH *aSubgraph, bool aForce)
Update all neighbors of a subgraph with this one's connectivity info.
void buildItemSubGraphs()
Generate 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,...
SCH_SHEET_LIST m_sheetList
All the sheets in the schematic (as long as we don't have partial updates).
void generateGlobalPowerPinSubGraphs()
Iterate through the global power pins to collect the global labels as drivers.
const std::vector< CONNECTION_SUBGRAPH * > GetAllSubgraphs(const wxString &aNetName) const
std::unordered_map< wxString, int > m_net_name_to_code_map
int ercCheckSingleGlobalLabel()
Check that a global label is instantiated more that once across the schematic heirarchy.
int ercCheckHierSheets()
Check that a hierarchical sheet has at least one matching label inside the sheet for each port on the...
bool ercCheckBusToNetConflicts(const CONNECTION_SUBGRAPH *aSubgraph)
Check one subgraph for conflicting connections between net and bus labels.
std::shared_ptr< SCH_CONNECTION > getDefaultConnection(SCH_ITEM *aItem, CONNECTION_SUBGRAPH *aSubgraph)
Build a new default connection for the given item based on its properties.
std::vector< const CONNECTION_SUBGRAPH * > GetBusesNeedingMigration()
Determine 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
int getOrCreateNetCode(const wxString &aNetName)
void assignNetCodesToBus(SCH_CONNECTION *aConnection)
Ensure 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
The owner of all CONNECTION_SUBGRAPH objects.
std::vector< std::pair< SCH_SHEET_PATH, SCH_PIN * > > m_global_power_pins
CONNECTION_GRAPH(SCHEMATIC *aSchematic=nullptr)
bool ercCheckNoConnects(const CONNECTION_SUBGRAPH *aSubgraph)
Check 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
All connectable items in the schematic.
std::unordered_map< wxString, std::vector< CONNECTION_SUBGRAPH * > > m_net_name_to_subgraphs_map
std::shared_ptr< BUS_ALIAS > GetBusAlias(const wxString &aName)
Return a bus alias pointer for the given name if it exists (from cache)
void removeSubgraphs(std::set< CONNECTION_SUBGRAPH * > &aSubgraphs)
Remove references to the given subgraphs from all structures in the connection graph.
std::unordered_map< SCH_ITEM *, CONNECTION_SUBGRAPH * > m_item_to_subgraph_map
std::set< std::pair< SCH_SHEET_PATH, SCH_ITEM * > > ExtractAffectedItems(const std::set< SCH_ITEM * > &aItems)
For a set of items, this will remove the connected items and their associated data including subgraph...
wxString GetResolvedSubgraphName(const CONNECTION_SUBGRAPH *aSubGraph) const
Return the fully-resolved netname for a given subgraph.
bool ercCheckBusToBusEntryConflicts(const CONNECTION_SUBGRAPH *aSubgraph)
Check one subgraph for conflicting bus entry to bus connections.
std::vector< CONNECTION_SUBGRAPH * > m_driver_subgraphs
Cache of a subset of m_subgraphs.
void ExchangeItem(SCH_ITEM *aOldItem, SCH_ITEM *aNewItem)
Replace all references to #aOldItem with #aNewItem in the graph.
NET_MAP m_net_code_to_subgraphs_map
bool ercCheckFloatingWires(const CONNECTION_SUBGRAPH *aSubgraph)
Check one subgraph for floating wires.
void SetLastCodes(const CONNECTION_GRAPH *aOther)
void buildConnectionGraph(std::function< void(SCH_ITEM *)> *aChangedItemHandler, bool aUnconditional)
Generate the connection graph (after all item connectivity has been updated).
void Merge(CONNECTION_GRAPH &aGraph)
Combine the input graph contents into the current graph.
void resolveAllDrivers()
Find all subgraphs in the connection graph and calls ResolveDrivers() in parallel.
void updateItemConnectivity(const SCH_SHEET_PATH &aSheet, const std::vector< SCH_ITEM * > &aItemList)
Update the graphical connectivity between items (i.e.
CONNECTION_SUBGRAPH * GetSubgraphForItem(SCH_ITEM *aItem) const
void Recalculate(const SCH_SHEET_LIST &aSheetList, bool aUnconditional=false, std::function< void(SCH_ITEM *)> *aChangedItemHandler=nullptr)
Update the connection graph for the given list of sheets.
void generateBusAliasMembers()
Iterate through labels to create placeholders for bus elements.
A subgraph is a set of items that are electrically connected on a single sheet.
wxString driverName(SCH_ITEM *aItem) const
PRIORITY GetDriverPriority()
const std::set< SCH_ITEM * > & GetItems() const
Provide a read-only reference to the items in the subgraph.
const SCH_ITEM * GetNoConnect() const
void StoreImplicitConnection(SCH_CONNECTION *aConnection)
bool m_strong_driver
True if the driver is "strong": a label or power object.
SCH_ITEM * m_no_connect
No-connect item in graph, if any.
std::set< CONNECTION_SUBGRAPH * > m_absorbed_subgraphs
Set of subgraphs that have been absorbed by this subgraph.
const SCH_ITEM * GetDriver() const
SCH_ITEM * m_bus_entry
Bus entry in graph, if any.
SCH_SHEET_PATH m_sheet
On which logical sheet is the subgraph contained.
void UpdateItemConnections()
Update all items to match the driver connection.
std::set< SCH_SHEET_PIN * > m_hier_pins
Cache for lookup of any hierarchical (sheet) pins on this subgraph (for referring down).
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::vector< SCH_ITEM * > GetAllBusLabels() const
Return all the all bus labels attached to this subgraph (if any).
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
Return the candidate net name for a driver.
wxString GetNetName() const
Return the fully-qualified net name for this subgraph (if one exists)
std::vector< SCH_ITEM * > GetVectorBusLabels() const
Return all the vector-based bus labels attached to this subgraph (if any).
const SCH_SHEET_PATH & GetSheet() const
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)
Determine which potential driver should drive the subgraph.
std::set< SCH_ITEM * > m_drivers
const SCH_CONNECTION * GetDriverConnection() const
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.
std::unordered_set< CONNECTION_SUBGRAPH * > m_hier_children
If not null, this indicates the subgraph(s) on a lower level sheet that are linked to this one.
void AddItem(SCH_ITEM *aItem)
Add a new item to the subgraph.
std::set< SCH_CONNECTION * > m_bus_element_connections
A cache of connections that are part of this subgraph but that don't have an owning element (i....
void Absorb(CONNECTION_SUBGRAPH *aOther)
Combine another subgraph on the same sheet into this one.
std::set< SCH_ITEM * > m_items
Contents of the subgraph.
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.
SCH_ITEM * m_driver
Fully-resolved driver for the subgraph (might not exist in this subgraph).
CONNECTION_SUBGRAPH(CONNECTION_GRAPH *aGraph)
bool m_is_bus_member
True if the subgraph is not actually part of a net.
void ExchangeItem(SCH_ITEM *aOldItem, SCH_ITEM *aNewItem)
Replaces all references to #aOldItem with #aNewItem in the subgraph.
CONNECTION_SUBGRAPH * m_hier_parent
If not null, this indicates the subgraph on a higher level sheet that is linked to this one.
void RemoveItem(SCH_ITEM *aItem)
const std::vector< std::pair< wxString, SCH_ITEM * > > GetNetclassesForDriver(SCH_ITEM *aItem, bool returnAll) const
Return the resolved netclasses for the item, and the source item providing the netclass.
bool m_local_driver
True if the driver is a local (i.e. non-global) type.
std::set< SCH_HIERLABEL * > m_hier_ports
Cache for lookup of any hierarchical ports on this subgraph (for referring up).
void getAllConnectedItems(std::set< std::pair< SCH_SHEET_PATH, SCH_ITEM * > > &aItems, std::set< CONNECTION_SUBGRAPH * > &aSubgraphs)
Find all items in the subgraph as well as child subgraphs recursively.
Holds all the data relating to one schematic.
Definition: schematic.h:75
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:174
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
Associate a #NET_CODE_NAME with all the subgraphs in that net.
STL namespace.
bool operator==(const NET_NAME_CODE_CACHE_KEY &other) const
std::size_t operator()(const NET_NAME_CODE_CACHE_KEY &k) const