KiCad PCB EDA Suite
Loading...
Searching...
No Matches
conn_bindings.cpp
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 The KiCad Developers, see AUTHORS.txt for contributors.
5 *
6 * This program is free software: you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License as published by the
8 * Free Software Foundation, either version 3 of the License, or (at your
9 * option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program. If not, see <https://www.gnu.org/licenses/>.
18 */
19
20#include "conn_bindings.h"
21
22#include <algorithm>
23#include <map>
24#include <stdexcept>
25#include <set>
26#include <utility>
27#include <wx/thread.h>
28
29namespace SCH_CONNECTIVITY
30{
32 SESSION_KEYS& aKeys )
33{
34 wxASSERT( wxThread::IsMain() );
36 result.parent = aPartition.anchor;
37
38 for( const auto& [node, version] : aPartition.identity )
39 {
40 const NODE_KEY& nodeKey = aKeys.Node( node );
41
42 if( std::holds_alternative<NAME_KEY>( nodeKey ) && version == 0 )
43 continue;
44
45 const auto* key = std::get_if<RECORD_NODE>( &nodeKey );
46 const auto* entry = key ? aRecords.Find( key->record ) : nullptr;
47
48 if( !entry || entry->version != version || key->kind != KIND::BUNDLE || entry->value.kind != KIND::BUNDLE )
49 throw std::invalid_argument( "Bundle partition does not match current records" );
50
51 const ISLAND_RECORD& record = entry->value;
52
53 for( const KIID& item : record.items )
54 result.items.push_back( { item, key->record.inst } );
55
56 result.netclasses.insert( result.netclasses.end(), record.netclasses.begin(), record.netclasses.end() );
57
58 for( const CLAIM& claim : record.claims )
59 {
60 if( claim.schema )
61 result.claims.push_back( { key->record, claim, {}, &claim == &record.claims.front() } );
62 }
63 }
64
65 std::ranges::sort( result.items, KEY_LESS{ aKeys } );
66 std::ranges::sort( result.netclasses, NAME_LESS{ &aKeys } );
67 result.netclasses.erase( std::ranges::unique( result.netclasses ).begin(), result.netclasses.end() );
68
69 if( result.claims.empty() )
70 return result;
71
72 std::swap( result.claims.front(), *SelectDriver( result.claims, CLAIM_LESS{ aKeys }, &BUNDLE_CLAIM::claim ) );
73
74 for( BUNDLE_CLAIM& source : result.claims )
75 {
76 const auto& leaves = source.claim.schema->leaves;
77 const wxString path = aKeys.Name( source.claim.path );
78
79 if( !leaves.empty() && !std::in_range<uint32_t>( leaves.size() - 1 ) )
80 throw std::length_error( "Bus schema exceeds slot ordinal range" );
81
82 source.leaves.reserve( leaves.size() );
83
84 for( const BUS_SCHEMA::LEAF& leaf : leaves )
85 {
86 wxString local;
87
88 for( const wxString& group : leaf.groupPath )
89 local += group + ".";
90
91 local += leaf.localName;
92 source.leaves.push_back( { aKeys.InternName( leaf.name ), aKeys.InternName( path + leaf.name ),
93 aKeys.InternName( local ) } );
94 }
95 }
96
97 return result;
98}
99
101{
103 result.items = aInput.items;
104 result.netclasses = aInput.netclasses;
105
106 if( aInput.claims.empty() )
107 return result;
108
109 const BUNDLE_CLAIM& canonical = aInput.claims.front();
110
111 if( aInput.parent == INVALID_ID || !canonical.claim.schema )
112 throw std::invalid_argument( "Bundle binding requires a parent and canonical schema" );
113
114 result.canonical = canonical.claim;
115 const auto makeSlot = [&]( const SLOT_KEY& key, const BUNDLE_CLAIM& owner, size_t aLeaf )
116 {
117 const BUNDLE_CLAIM::LEAF_NAME& leaf = owner.leaves.at( aLeaf );
118 SLOT_INPUT slot;
119 slot.key = key;
121 slot.claim.depth = owner.claim.depth;
122 slot.claim.path = owner.claim.path;
123 slot.claim.name = slot.claim.ncName = leaf.name;
124 slot.claim.fullName = leaf.fullName;
125 slot.claim.source = owner.claim.source;
126 slot.localName = leaf.localName;
127 slot.parentNetclasses = aInput.netclasses;
128 slot.parentBundle = aInput.parent;
129 return slot;
130 };
131
132 for( size_t i = 0; i < canonical.leaves.size(); ++i )
133 {
134 const SLOT_KEY key{ canonical.claim.source, static_cast<uint32_t>( i ) };
135 result.members.push_back( key );
136 result.slots.push_back( makeSlot( key, canonical, i ) );
137 }
138
139 const CLAIM_LESS claimLess{ aKeys };
140 std::map<std::pair<INST_ID, NAME_ID>, const BUNDLE_CLAIM*> answers;
141
142 for( const BUNDLE_CLAIM& source : aInput.claims )
143 {
144 if( source.claim.priority != PRIORITY::HIER_LABEL )
145 continue;
146
147 const auto [found, inserted] = answers.try_emplace( { source.record.inst, source.claim.name }, &source );
148
149 if( !inserted && claimLess( found->second->claim, source.claim ) )
150 found->second = &source;
151 }
152
153 for( const BUNDLE_CLAIM& source : aInput.claims )
154 {
155 if( !source.claim.schema || source.leaves.size() != source.claim.schema->leaves.size() )
156 throw std::invalid_argument( "Prepared bundle leaves do not match their schema" );
157
158 const bool sheetPin = source.claim.priority == PRIORITY::SHEET_PIN;
159 const BUNDLE_CLAIM* answer = nullptr;
160
161 if( sheetPin && source.claim.portInstance )
162 {
163 if( auto found = answers.find( { *source.claim.portInstance, source.claim.name } ); found != answers.end() )
164 answer = found->second;
165 }
166
167 // A sheet pin names parent members only while it drives its bus there, and answering labels cover children
168 const bool named = !sheetPin || source.drivesRecord;
169
170 // Such a pin would publish member nets that hold no item on either sheet
171 if( !named && !answer )
172 continue;
173
174 const BUS_ALIGNMENT alignment = Align( *source.claim.schema, *canonical.claim.schema );
175 const auto parentEdges = [&]( SLOT_INPUT& aSlot ) -> std::vector<NAME_KEY>&
176 {
177 return sheetPin ? aSlot.parentEdges : aSlot.edges;
178 };
179
180 if( named )
181 {
182 for( const auto& [from, to] : alignment.matched )
183 {
184 parentEdges( result.slots[to] )
185 .push_back( { SCOPE::SHEET, source.record.inst, source.leaves[from].name } );
186 }
187 }
188
189 for( size_t from : alignment.unmappedLeft )
190 {
191 // An answered pin member takes the label's claim so that both slots name the child member alike
192 const auto ordinal = static_cast<uint32_t>( from );
193 SLOT_INPUT slot = makeSlot( { source.claim.source, ordinal }, answer ? *answer : source, from );
194
195 if( named )
196 parentEdges( slot ).push_back( { SCOPE::SHEET, source.record.inst, source.leaves[from].name } );
197
198 if( answer )
199 slot.edges.push_back( { SCOPE::SHEET, answer->record.inst, source.leaves[from].name } );
200
201 result.slots.push_back( std::move( slot ) );
202 }
203 }
204
205 const KEY_LESS keyLess{ aKeys };
206
207 for( SLOT_INPUT& slot : result.slots )
208 {
209 for( std::vector<NAME_KEY>* edges : { &slot.edges, &slot.parentEdges } )
210 {
211 std::ranges::sort( *edges, keyLess );
212 edges->erase( std::ranges::unique( *edges ).begin(), edges->end() );
213 }
214 }
215
216 std::ranges::sort( result.slots, keyLess, &SLOT_INPUT::key );
217 return result;
218}
219
221 m_slots( aVersions, KEY_LESS{ aKeys } )
222{
223}
224
226{
227 wxASSERT( wxThread::IsMain() );
228 try
229 {
230 std::set<SLOT_KEY, KEY_LESS> live( m_slots.Entries().key_comp() );
231 std::set<NODE_ID> parents;
232
233 for( const auto& bundle : aBundles.Entries() )
234 {
235 const NODE_ID parent = bundle->input.anchor;
236
237 if( !parents.insert( parent ).second )
238 throw std::invalid_argument( "Duplicate bundle component" );
239
240 const auto [previous, inserted] = m_bundleInputs.try_emplace( parent, bundle->version );
241 const bool changed = inserted || std::exchange( previous->second, bundle->version ) != bundle->version;
242
243 for( const SLOT_INPUT& slot : bundle->value.slots )
244 {
245 if( slot.parentBundle != parent || !live.insert( slot.key ).second )
246 throw std::invalid_argument( "Slot has a duplicate key or inconsistent parent" );
247
248 if( changed )
249 m_slots.Set( slot.key, slot );
250 }
251 }
252
253 for( auto it = m_slots.Entries().begin(); it != m_slots.Entries().end(); )
254 {
255 // Erasing by a key stored in the erased node is not guaranteed safe
256 const SLOT_KEY key = ( it++ )->first;
257
258 if( !live.contains( key ) )
259 m_slots.Erase( key );
260 }
261
262 std::erase_if( m_bundleInputs,
263 [&]( const auto& entry )
264 {
265 return !parents.contains( entry.first );
266 } );
267 }
268 catch( ... )
269 {
270 Clear();
271 throw;
272 }
273}
274
276{
277 m_slots.Clear();
278 m_bundleInputs.clear();
279}
280
281std::vector<NODE_INPUT> SignalNodes( const RECORD_STORE::RECORD_CACHE& aRecords, const SLOT_STORE::SLOT_CACHE& aSlots,
282 SESSION_KEYS& aKeys )
283{
284 auto result = RecordNodes( aRecords, KIND::SIGNAL, aKeys );
285 result.reserve( result.size() + aSlots.Entries().size() );
286 std::set<NODE_ID> claimedNames;
287
288 for( const NODE_INPUT& record : result )
289 claimedNames.insert( record.edges.begin(), record.edges.end() );
290
291 for( const auto& [key, entry] : aSlots.Entries() )
292 {
293 NODE_INPUT input{ aKeys.InternNode( key ), entry->version, {} };
294 input.edges.reserve( entry->value.edges.size() );
295
296 for( const NAME_KEY& edge : entry->value.edges )
297 input.edges.push_back( aKeys.InternNode( edge ) );
298
299 // Two buses must not join through a parent name that no signal on that sheet claims
300 for( const NAME_KEY& edge : entry->value.parentEdges )
301 {
302 if( const NODE_ID node = aKeys.InternNode( edge ); claimedNames.contains( node ) )
303 input.edges.push_back( node );
304 }
305
306 result.push_back( std::move( input ) );
307 }
308
309 return result;
310}
311
312} // namespace SCH_CONNECTIVITY
Definition kiid.h:46
const auto & Entries() const
Definition conn_cache.h:105
const ENTRY * Find(const KEY &aKey) const
Entry references survive unchanged writes, but not replacement or erasure of their key.
Definition conn_cache.h:80
One sequence for all cache tables for the lifetime of an engine session.
Definition conn_cache.h:37
Cache current component evaluations by exact node/version identity, within one stratum and key sessio...
CACHE_TABLE< RECORD_KEY, ISLAND_RECORD, KEY_LESS > RECORD_CACHE
Session IDs are dense handles, never a canonical ordering.
Definition conn_keys.h:146
const NODE_KEY & Node(NODE_ID aId) const
Definition conn_keys.h:164
const wxString & Name(NAME_ID aId) const
Definition conn_keys.h:163
NAME_ID InternName(const wxString &aText)
Definition conn_keys.h:153
NODE_ID InternNode(NODE_KEY aKey)
Definition conn_keys.cpp:28
CACHE_TABLE< SLOT_KEY, SLOT_INPUT, KEY_LESS > SLOT_CACHE
std::map< NODE_ID, uint64_t > m_bundleInputs
void Update(const COMPONENT_CACHE< BUNDLE_BINDING > &aBundles)
SLOT_STORE(CACHE_VERSIONS &aVersions, SESSION_KEYS &aKeys)
std::string source
Value keys and the key session of the schematic connectivity engine.
std::variant< RECORD_NODE, NAME_KEY, SLOT_KEY > NODE_KEY
Any node of the union-find graph.
Definition conn_keys.h:136
std::ranges::iterator_t< RANGE > SelectDriver(RANGE &aClaims, const CLAIM_LESS &aLess, PROJ aProj={})
The driver of aClaims.
Definition conn_claims.h:90
BUNDLE_INPUT PrepareBundle(const PARTITION &aPartition, const RECORD_STORE::RECORD_CACHE &aRecords, SESSION_KEYS &aKeys)
Collect the bus claims of a bundle partition and intern their leaf names on the main thread.
uint32_t NODE_ID
Session handle of a NODE_KEY graph node.
Definition conn_keys.h:43
BUS_ALIGNMENT Align(const BUS_SCHEMA &aLeft, const BUS_SCHEMA &aRight)
Match the leaves of aLeft to the leaves of aRight.
Definition conn_bus.cpp:302
constexpr uint32_t INVALID_ID
Marks an unset handle.
Definition conn_keys.h:47
BUNDLE_BINDING BindBundle(const BUNDLE_INPUT &aInput, const SESSION_KEYS &aKeys)
Align the prepared claims to the canonical claim and make the member slots.
std::vector< NODE_INPUT > SignalNodes(const RECORD_STORE::RECORD_CACHE &aRecords, const SLOT_STORE::SLOT_CACHE &aSlots, SESSION_KEYS &aKeys)
Main-thread interning of current signal records and slots for the signal fold.
@ SHEET_PIN
Sheet pin. The name belongs to the child instance.
Definition conn_claims.h:43
@ BUS_MEMBER
Synthetic claim of a bus member slot, set by BindBundle().
Definition conn_claims.h:47
@ HIER_LABEL
Hierarchical label. The first strong priority.
Definition conn_claims.h:44
std::vector< NODE_INPUT > RecordNodes(const RECORD_STORE::RECORD_CACHE &aRecords, KIND aKind, SESSION_KEYS &aKeys)
Main-thread node interning for one record stratum.
Bound result of one bus component.
NAME_ID fullName
Leaf name after the sheet path of this claim.
NAME_ID localName
Group path and leaf local name joined with dots.
NAME_ID name
Leaf name with all group prefixes.
One bus claim of a bundle partition, with its leaf names interned.
std::vector< LEAF_NAME > leaves
One entry for each leaf of the claim schema, in the same order.
RECORD_KEY record
Record of the island that holds the claim.
Main-thread input of BindBundle() for one bundle partition.
std::vector< NAME_ID > netclasses
NODE_ID parent
Anchor node of the partition.
std::vector< ITEM_KEY > items
std::vector< BUNDLE_CLAIM > claims
Bus claims. The canonical claim is first.
Member correspondence between two bus schemas.
Definition conn_bus.h:186
std::vector< size_t > unmappedLeft
Left leaf ordinals without a right partner.
Definition conn_bus.h:188
std::vector< std::pair< size_t, size_t > > matched
Pairs of left and right leaf ordinals.
Definition conn_bus.h:187
Strict weak order on claims by value.
Definition conn_claims.h:80
The claim of one item for the name of its island.
Definition conn_claims.h:56
ITEM_KEY source
The claiming item, the last tie-break.
Definition conn_claims.h:63
uint16_t depth
Sheet path size, or zero if unscoped.
Definition conn_claims.h:58
NAME_ID ncName
Name of an unconnected pin net.
Definition conn_claims.h:61
NAME_ID name
Item text without the sheet prefix.
Definition conn_claims.h:60
std::shared_ptr< const BUS_SCHEMA > schema
Parsed bus, or null for a signal.
Definition conn_claims.h:68
NAME_ID path
Sheet prefix, or the empty name if unscoped.
Definition conn_claims.h:59
NAME_ID fullName
path followed by name.
Definition conn_claims.h:62
std::vector< NAME_ID > netclasses
std::vector< CLAIM > claims
front() is the SelectDriver() result, the rest descend by CLAIM_LESS.
Orders keys by value through SESSION_KEYS::Less().
Definition conn_keys.h:255
The graph node of one name in one scope.
Definition conn_keys.h:110
Orders name handles by UTF-8 value.
Definition conn_keys.h:246
std::vector< NODE_ID > edges
Exact identity of one connected component.
std::vector< std::pair< NODE_ID, uint64_t > > identity
INST_ID inst
The sheet instance of the record.
Definition conn_keys.h:88
One bus member as a node of the signal stratum.
std::vector< NAME_KEY > parentEdges
Parent-sheet names from a driving sheet pin, which join only names a signal record already claims.
SLOT_KEY key
Source item of the declaring claim and the leaf ordinal in its schema.
CLAIM claim
PRIORITY::BUS_MEMBER claim with the leaf name and the path of its owning claim.
std::vector< NAME_ID > parentNetclasses
Netclasses of the bus component.
NAME_ID localName
Group path and leaf local name joined with dots.
NODE_ID parentBundle
Anchor node of the bus component.
std::vector< NAME_KEY > edges
Sheet name keys that always join this slot.
One member position of a bus.
Definition conn_keys.h:127
std::string path
wxString result
Test unit parsing edge cases and error handling.