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#include <advanced_config.h>
34
35
36#ifdef DEBUG
37// Uncomment this line to enable connectivity debugging features
38// #define CONNECTIVITY_DEBUG
39#endif
40
41
43class SCHEMATIC;
44class SCH_EDIT_FRAME;
45class SCH_HIERLABEL;
46class SCH_PIN;
47class SCH_SHEET_PIN;
48
49
63{
64public:
65 enum class PRIORITY
66 {
67 INVALID = -1,
68 NONE = 0,
69 PIN,
74 GLOBAL
75 };
76
78 m_graph( aGraph ),
79 m_dirty( false ),
80 m_absorbed( false ),
81 m_is_bus_member( false ),
82 m_absorbed_by( nullptr ),
83 m_code( -1 ),
84 m_multiple_drivers( false ),
85 m_strong_driver( false ),
86 m_local_driver( false ),
87 m_bus_entry( nullptr ),
88 m_hier_parent( nullptr ),
89 m_driver( nullptr ),
90 m_no_connect( nullptr ),
91 m_driver_connection( nullptr )
92 {}
93
95 {
96 for( SCH_CONNECTION* connection : m_bus_element_connections )
97 delete connection;
98 }
99
100 friend class CONNECTION_GRAPH;
101
111 bool ResolveDrivers( bool aCheckMultipleDrivers = false );
112
116 wxString GetNetName() const;
117
119 std::vector<SCH_ITEM*> GetVectorBusLabels() const;
120
122 std::vector<SCH_ITEM*> GetAllBusLabels() const;
123
125 const wxString& GetNameForDriver( SCH_ITEM* aItem ) const;
126
131 const std::vector<std::pair<wxString, SCH_ITEM*>>
132 GetNetclassesForDriver( SCH_ITEM* aItem, bool returnAll ) const;
133
135 void Absorb( CONNECTION_SUBGRAPH* aOther );
136
138 void AddItem( SCH_ITEM* aItem );
139
142
144 const std::set<SCH_ITEM*>& GetItems() const
145 {
146 return m_items;
147 }
148
150 void getAllConnectedItems( std::set<std::pair<SCH_SHEET_PATH, SCH_ITEM*>>& aItems,
151 std::set<CONNECTION_SUBGRAPH*>& aSubgraphs );
152
167 static PRIORITY GetDriverPriority( SCH_ITEM* aDriver );
168
170 {
171 if( m_driver )
172 return GetDriverPriority( m_driver );
173 else
174 return PRIORITY::NONE;
175 }
176
181 const SCH_ITEM* GetDriver() const
182 {
183 return m_driver;
184 }
185
190 {
191 return m_driver_connection;
192 }
193
197 const SCH_ITEM* GetNoConnect() const
198 {
199 return m_no_connect;
200 }
201
203 {
204 return m_sheet;
205 }
206
207 void RemoveItem( SCH_ITEM* aItem );
208
212 void ExchangeItem( SCH_ITEM* aOldItem, SCH_ITEM* aNewItem );
213
214 // Use this to keep a connection pointer that is not owned by any item
215 // This will be destroyed with the subgraph
217 {
218 m_bus_element_connections.insert( aConnection );
219 }
220
221private:
222 wxString driverName( SCH_ITEM* aItem ) const;
223
225
227
230
236
239
241 std::set<CONNECTION_SUBGRAPH*> m_absorbed_subgraphs;
242
243 long m_code;
244
251
254
257
260
261 std::set<SCH_ITEM*> m_drivers;
262
271 std::unordered_map< std::shared_ptr<SCH_CONNECTION>,
272 std::unordered_set<CONNECTION_SUBGRAPH*> > m_bus_neighbors;
273
279 std::unordered_map< std::shared_ptr<SCH_CONNECTION>,
280 std::unordered_set<CONNECTION_SUBGRAPH*> > m_bus_parents;
281
283 std::set<SCH_SHEET_PIN*> m_hier_pins;
284
286 std::set<SCH_HIERLABEL*> m_hier_ports;
287
290
293 std::unordered_set<CONNECTION_SUBGRAPH*> m_hier_children;
294
296 mutable std::unordered_map<SCH_ITEM*, wxString> m_driver_name_cache;
297
300
302 std::set<SCH_ITEM*> m_items;
303
306
309
312
315 std::set<SCH_CONNECTION*> m_bus_element_connections;
316
317 std::mutex m_driver_mutex;
318};
319
321{
322 wxString Name;
324
325 bool operator==(const NET_NAME_CODE_CACHE_KEY& other) const
326 {
327 return Name == other.Name && Netcode == other.Netcode;
328 }
329};
330
331namespace std
332{
333 template <>
335 {
336 std::size_t operator()( const NET_NAME_CODE_CACHE_KEY& k ) const
337 {
338 const std::size_t prime = 19937;
339
340 return hash<wxString>()( k.Name ) ^ ( hash<int>()( k.Netcode ) * prime );
341 }
342 };
343}
344
346typedef std::unordered_map<NET_NAME_CODE_CACHE_KEY, std::vector<CONNECTION_SUBGRAPH*>> NET_MAP;
347
352{
353public:
354 CONNECTION_GRAPH( SCHEMATIC* aSchematic = nullptr ) :
355 m_last_net_code( 1 ),
356 m_last_bus_code( 1 ),
358 m_schematic( aSchematic )
359 {}
360
362 {
363 Reset();
364 }
365
366 void Reset();
367
368 void SetSchematic( SCHEMATIC* aSchematic )
369 {
370 m_schematic = aSchematic;
371 }
372
373 void SetLastCodes( const CONNECTION_GRAPH* aOther )
374 {
378 }
379
387 void Recalculate( const SCH_SHEET_LIST& aSheetList, bool aUnconditional = false,
388 std::function<void( SCH_ITEM* )>* aChangedItemHandler = nullptr );
389
396 std::shared_ptr<BUS_ALIAS> GetBusAlias( const wxString& aName );
397
405 std::vector<const CONNECTION_SUBGRAPH*> GetBusesNeedingMigration();
406
414 int RunERC();
415
417
425 CONNECTION_SUBGRAPH* FindSubgraphByName( const wxString& aNetName,
426 const SCH_SHEET_PATH& aPath );
427
436 CONNECTION_SUBGRAPH* FindFirstSubgraphByName( const wxString& aNetName );
437
439
440 const std::vector<CONNECTION_SUBGRAPH*> GetAllSubgraphs( const wxString& aNetName ) const;
441
448 wxString GetResolvedSubgraphName( const CONNECTION_SUBGRAPH* aSubGraph ) const;
449
457 std::set<std::pair<SCH_SHEET_PATH, SCH_ITEM*>> ExtractAffectedItems(
458 const std::set<SCH_ITEM*> &aItems );
459
467 void Merge( CONNECTION_GRAPH& aGraph );
468
469 void RemoveItem( SCH_ITEM* aItem );
470
474 void ExchangeItem( SCH_ITEM* aOldItem, SCH_ITEM* aNewItem );
475
483 bool IsMinor() const
484 {
485 return static_cast<ssize_t>( m_items.size() )
487 }
488
489private:
517 void updateItemConnectivity( const SCH_SHEET_PATH& aSheet,
518 const std::vector<SCH_ITEM*>& aItemList );
519
537 void buildConnectionGraph( std::function<void( SCH_ITEM* )>* aChangedItemHandler, bool aUnconditional );
538
542 void buildItemSubGraphs();
543
547 void resolveAllDrivers();
548
553
558
563
567 void processSubGraphs();
568
574 int assignNewNetCode( SCH_CONNECTION& aConnection );
575
581 int getOrCreateNetCode( const wxString& aNetName );
582
588 void assignNetCodesToBus( SCH_CONNECTION* aConnection );
589
599 void propagateToNeighbors( CONNECTION_SUBGRAPH* aSubgraph, bool aForce );
600
606 void removeSubgraphs( std::set<CONNECTION_SUBGRAPH*>& aSubgraphs );
607
618 static SCH_CONNECTION* matchBusMember( SCH_CONNECTION* aBusConnection,
619 SCH_CONNECTION* aSearch );
620
630 std::shared_ptr<SCH_CONNECTION> getDefaultConnection( SCH_ITEM* aItem,
631 CONNECTION_SUBGRAPH* aSubgraph );
632
633 void recacheSubgraphName( CONNECTION_SUBGRAPH* aSubgraph, const wxString& aOldName );
634
643 bool ercCheckMultipleDrivers( const CONNECTION_SUBGRAPH* aSubgraph );
644
645 bool ercCheckNetclassConflicts( const std::vector<CONNECTION_SUBGRAPH*>& subgraphs );
646
655 bool ercCheckBusToNetConflicts( const CONNECTION_SUBGRAPH* aSubgraph );
656
667 bool ercCheckBusToBusConflicts( const CONNECTION_SUBGRAPH* aSubgraph );
668
682
692 bool ercCheckNoConnects( const CONNECTION_SUBGRAPH* aSubgraph );
693
702 bool ercCheckFloatingWires( const CONNECTION_SUBGRAPH* aSubgraph );
703
713 bool ercCheckLabels( const CONNECTION_SUBGRAPH* aSubgraph );
714
722 int ercCheckHierSheets();
723
728
735 size_t hasPins( const CONNECTION_SUBGRAPH* aLocSubgraph );
736
737
738private:
741
743 std::vector<SCH_ITEM*> m_items;
744
746 std::vector<CONNECTION_SUBGRAPH*> m_subgraphs;
747
749 std::vector<CONNECTION_SUBGRAPH*> m_driver_subgraphs;
750
752 std::unordered_map<SCH_SHEET_PATH, std::vector<CONNECTION_SUBGRAPH*>> m_sheet_to_subgraphs_map;
753
754 std::vector<std::pair<SCH_SHEET_PATH, SCH_PIN*>> m_global_power_pins;
755
756 std::unordered_map<wxString, std::shared_ptr<BUS_ALIAS>> m_bus_alias_cache;
757
758 std::unordered_map<wxString, int> m_net_name_to_code_map;
759
760 std::unordered_map<wxString, int> m_bus_name_to_code_map;
761
762 std::unordered_map<wxString, std::vector<const CONNECTION_SUBGRAPH*>> m_global_label_cache;
763
764 std::map< std::pair<SCH_SHEET_PATH, wxString>,
765 std::vector<const CONNECTION_SUBGRAPH*> > m_local_label_cache;
766
767 std::unordered_map<wxString, std::vector<CONNECTION_SUBGRAPH*>> m_net_name_to_subgraphs_map;
768
769 std::unordered_map<SCH_ITEM*, CONNECTION_SUBGRAPH*> m_item_to_subgraph_map;
770
772
774
776
778
780};
781
782#endif
static const ADVANCED_CFG & GetCfg()
Get the singleton instance's config, which is shared by all consumers.
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
bool IsMinor() const
We modify how we handle the connectivity graph for small graphs vs large graphs.
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:76
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:166
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.
int m_MinorSchematicGraphSize
Set the number of items in a schematic graph for it to be considered "minor".
STL namespace.
bool operator==(const NET_NAME_CODE_CACHE_KEY &other) const
std::size_t operator()(const NET_NAME_CODE_CACHE_KEY &k) const