KiCad PCB EDA Suite
Loading...
Searching...
No Matches
topo_match.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
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU 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, you may find one here:
18 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
19 * or you may search the http://www.gnu.org website for the version 2 license,
20 * or you may write to the Free Software Foundation, Inc.,
21 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
22 */
23
24#include <cstdio>
25#include <cstdlib>
26#include <cmath>
27#include <string>
28#include <vector>
29#include <algorithm>
30#include <cassert>
31#include <map>
32#include <set>
33#include <cctype>
34
35#include <pad.h>
36#include <footprint.h>
37#include <refdes_utils.h>
38#include <wx/string.h>
39#include <wx/log.h>
40
41#include "topo_match.h"
42
43
44static const wxString traceTopoMatch = wxT( "TOPO_MATCH" );
45
46namespace TMATCH
47{
48
49bool PIN::IsIsomorphic( const PIN& b ) const
50{
51 if( m_conns.size() != b.m_conns.size() )
52 {
53 wxLogTrace( traceTopoMatch, wxT("[conns mismatch n1 %d n2 %d c-ref %d c-other %d thispin %s-%s otherpin %s-%s"),
55 b.m_netcode,
56 (int) m_conns.size(),
57 (int) b.m_conns.size(),
59 m_ref,
61 b.m_ref );
62
63 for( auto c : m_conns )
64 {
65 wxLogTrace( traceTopoMatch, wxT("%s-%s "), c->m_parent->m_reference, c->m_ref );
66 }
67
68 wxLogTrace( traceTopoMatch, wxT("||") );
69
70 for( auto c : b.m_conns )
71 {
72 wxLogTrace( traceTopoMatch, wxT("%s-%s "), c->m_parent->m_reference, c->m_ref );
73 }
74
75
76 wxLogTrace( traceTopoMatch, wxT("] ") );
77 return false;
78 }
79
80 if( m_conns.empty() )
81 {
82 wxLogTrace( traceTopoMatch, wxT("[conns empty]") );
83 return true;
84 }
85
86 std::vector<bool> matches( m_conns.size() );
87
88 for( int i = 0; i < m_conns.size(); i++ )
89 matches[i] = false;
90
91 int nref = 0;
92
93 for( auto& cref : m_conns )
94 {
95 //printf("[CREF: %s]", cref->Format().c_str().AsChar() );
96 for( int i = 0; i < m_conns.size(); i++ )
97 {
98 if( b.m_conns[i]->IsTopologicallySimilar( *cref ) )
99 {
100 //printf("[CMATCH: %s]", b.m_conns[i]->Format().c_str().AsChar() );
101 matches[nref] = true;
102 break;
103 }
104 }
105
106 nref++;
107 }
108
109 for( int i = 0; i < m_conns.size(); i++ )
110 {
111 if( !matches[i] )
112 {
113 return false;
114 }
115 }
116
117 return true;
118}
119
120// fixme: terrible performance, but computers are fast these days, ain't they? :D
121bool checkIfPadNetsMatch( const BACKTRACK_STAGE& aMatches, CONNECTION_GRAPH* aRefGraph, COMPONENT* aRef, COMPONENT* aTgt )
122{
123 std::map<PIN*, PIN*> pairs;
124 std::vector<PIN*> pref, ptgt;
125
126 // GetMatchingComponentPairs() returns target->reference map
127 for( auto& m : aMatches.GetMatchingComponentPairs() )
128 {
129 for( PIN* p : m.second->Pins() )
130 {
131 pref.push_back( p );
132 }
133
134 for( PIN* p : m.first->Pins() )
135 {
136 ptgt.push_back( p );
137 }
138 }
139
140 for( PIN* p : aRef->Pins() )
141 {
142 pref.push_back( p );
143 }
144
145 for( PIN* p : aTgt->Pins() )
146 {
147 ptgt.push_back( p );
148 }
149
150 if( pref.size() != ptgt.size() )
151 {
152 return false;
153 }
154
155 for( unsigned int i = 0; i < pref.size(); i++ )
156 {
157 pairs[pref[i]] = ptgt[i];
158 }
159
160 for( PIN* refPin : aRef->Pins() )
161 {
162 wxLogTrace( traceTopoMatch, wxT("pad %s-%s: ") , aRef->GetParent()->GetReferenceAsString() , refPin->GetReference() );
163
164 std::optional<int> prevNet;
165
166 for( COMPONENT* refCmp : aRefGraph->Components() )
167 {
168 for( PIN* ppin : refCmp->Pins() )
169 {
170 if ( ppin->GetNetCode() != refPin->GetNetCode() )
171 continue;
172
173 wxLogTrace( traceTopoMatch, wxT("{ref %s-%s:%d} "), ppin->GetParent()->GetParent()->GetReferenceAsString(), ppin->GetReference(), ppin->GetNetCode() );
174
175 auto tpin = pairs.find( ppin );
176
177 if( tpin != pairs.end() )
178 {
179 int nc = tpin->second->GetNetCode();
180
181// printf("%s-%s:%d ", tpin->second->GetParent()->GetParent()->GetReferenceAsString(), tpin->second->GetReference().c_str().AsChar(), tpin->second->GetNetCode() );
182
183 if( prevNet && ( *prevNet != nc ) )
184 {
185 wxLogTrace( traceTopoMatch, wxT("nets inconsistent\n") );
186 return false;
187 }
188
189 prevNet = nc;
190 }
191 }
192 }
193 }
194
195 return true;
196}
197
198
199std::vector<COMPONENT*>
201{
202 std::vector<COMPONENT*> matches;
203 for( auto cmpTarget : m_components )
204 {
205 // already matched to sth? move on.
206 if( partialMatches.m_locked.find( cmpTarget ) != partialMatches.m_locked.end() )
207 {
208 continue;
209 }
210
211 wxLogTrace( traceTopoMatch, wxT("Check '%s'/'%s' "), aRef->m_reference, cmpTarget->m_reference );
212
213 // first, a basic heuristic (reference prefix, pin count & footprint) followed by a pin connection topology check
214 if( aRef->MatchesWith( cmpTarget ) )
215 {
216 // then a net integrity check (expensive because of poor optimization)
217 if( checkIfPadNetsMatch( partialMatches, aRefGraph, aRef, cmpTarget ) )
218 {
219 wxLogTrace( traceTopoMatch, wxT("match!\n") );
220 matches.push_back( cmpTarget );
221 }
222 else
223 {
224 wxLogTrace( traceTopoMatch, wxT("Reject [net topo mismatch]\n") );
225 }
226 }
227 else
228 {
229 wxLogTrace( traceTopoMatch, wxT("reject\n") );
230 }
231 }
232
233 auto padSimilarity=[]( COMPONENT*a, COMPONENT*b ) -> double {
234 int n=0;
235 for(int i=0;i<a->m_pins.size();i++)
236 {
237 PIN* pa = a->m_pins[i];
238 PIN* pb = b->m_pins[i];
239 if( pa->GetNetCode() == pb->GetNetCode() )
240 n++;
241 }
242 return (double)n / (double) a->m_pins.size();
243 };
244
245
246 std::sort(matches.begin(), matches.end(), [&] ( COMPONENT*a, COMPONENT*b ) -> int
247 {
248 return padSimilarity( aRef,a ) > padSimilarity( aRef, b );
249 }
250);
251
252 return matches;
253}
254
256{
257std::sort( m_pins.begin(), m_pins.end(),
258 []( PIN* a, PIN* b )
259 {
260 return a->GetReference() < b->GetReference();
261 } );
262}
263
265{
266 std::map<int, std::vector<PIN*>> nets;
267
269
270 for( auto c : m_components )
271 {
272 c->sortPinsByName();
273
274 for( auto p : c->Pins() )
275 {
276 if( p->GetNetCode() > 0 )
277 nets[p->GetNetCode()].push_back( p );
278 }
279 }
280
281 for( auto iter : nets )
282 {
283 wxLogTrace( traceTopoMatch, wxT("net %d: %d connections\n"), iter.first, (int) iter.second.size() );
284 for( auto p : iter.second )
285 {
286 for( auto p2 : iter.second )
287 if( p != p2 && !alg::contains( p->m_conns, p2 ) )
288 {
289 p->m_conns.push_back( p2 );
290 }
291 }
292 }
293
294/* for( auto c : m_components )
295 for( auto p : c->Pins() )
296 {
297 printf("pin %s: \n", p->m_ref.c_str().AsChar() );
298
299 for( auto c : p->m_conns )
300 printf( "%s ", c->m_ref.c_str().AsChar() );
301 printf("\n");
302 }
303 */
304}
305
306
308 COMPONENT_MATCHES& aResult )
309{
310 std::vector<BACKTRACK_STAGE> stack;
311 BACKTRACK_STAGE top;
312
313 if( m_components.empty()|| aTarget->m_components.empty() )
314 return ST_EMPTY;
315
316 if( m_components.size() != aTarget->m_components.size() )
318
319 top.m_ref = m_components.front();
320 top.m_refIndex = 0;
321
322 stack.push_back( top );
323
324 bool matchFound = false;
325 int nloops = 0;
326 while( !stack.empty() )
327 {
328 nloops++;
329 auto& current = stack.back();
330
331 for( auto it = current.m_locked.begin(); it != current.m_locked.end(); it++ )
332 {
333 if (it->second == current.m_ref)
334 {
335 wxLogTrace( traceTopoMatch, wxT("stk: Remove %s from locked\n"), current.m_ref->m_reference );
336 current.m_locked.erase( it );
337 break;
338 }
339 }
340
341 if( nloops >= c_ITER_LIMIT )
342 {
343 wxLogTrace( traceTopoMatch, wxT("stk: Iter cnt exceeded\n") );
345 }
346
347 if( current.m_currentMatch < 0 )
348 {
349 current.m_matches = aTarget->findMatchingComponents( this, current.m_ref, current );
350 current.m_currentMatch = 0;
351 }
352
353 wxLogTrace( traceTopoMatch, wxT("stk: Current '%s' stack %d cm %d/%d locked %d/%d\n" ),
354 current.m_ref->m_reference, (int) stack.size(),
355 current.m_currentMatch, (int) current.m_matches.size(),
356 (int) current.m_locked.size(), (int) m_components.size() );
357
358 if ( current.m_matches.empty() )
359 {
360 wxLogTrace( traceTopoMatch, wxT("stk: No matches at all, going up [level=%d]\n"), (int) stack.size() );
361 stack.pop_back();
362 continue;
363 }
364
365 if( current.m_currentMatch >= 0 && current.m_currentMatch >= current.m_matches.size() )
366 {
367 wxLogTrace( traceTopoMatch, wxT("stk: No more matches, going up [level=%d]\n"), (int) stack.size() );
368 stack.pop_back();
369 continue;
370 }
371
372 auto& match = current.m_matches[current.m_currentMatch];
373
374 wxLogTrace( traceTopoMatch, wxT("stk: candidate '%s', match list : ( "),
375 current.m_matches[current.m_currentMatch]->m_reference,
376 current.m_refIndex );
377
378 for( auto m : current.m_matches )
379 wxLogTrace( traceTopoMatch, wxT("%s "), m->GetParent()->GetReferenceAsString() );
380
381 wxLogTrace( traceTopoMatch, wxT("\n") );
382
383
384
385 current.m_currentMatch++;
386 current.m_locked[match] = current.m_ref;
387
388
389 if( current.m_locked.size() == m_components.size() )
390 {
391 current.m_nloops = nloops;
392
393 aResult.clear();
394
395 for( auto iter : current.m_locked )
396 aResult[ iter.second->GetParent() ] = iter.first->GetParent();
397
398 return ST_OK;
399 }
400
401
402 int minMatches = std::numeric_limits<int>::max();
403 COMPONENT* altNextRef = nullptr;
404 COMPONENT* bestNextRef = nullptr;
405 int bestRefIndex;
406 int altRefIndex;
407
408 for( size_t i = 0; i < m_components.size(); i++ )
409 {
410 COMPONENT* cmp = m_components[i];
411
412 if( cmp == current.m_ref )
413 continue;
414
415 bool found = false;
416
417 for( auto it = current.m_locked.begin(); it != current.m_locked.end(); it++ )
418 {
419 if( it->second == cmp )
420 {
421 found = true;
422 break;
423 }
424 }
425
426 if( found )
427 continue;
428
429 auto matches = aTarget->findMatchingComponents( this, cmp, current );
430
431 int nMatches = matches.size();
432 if( nMatches == 1 )
433 {
434 bestNextRef = cmp;
435 bestRefIndex = i;
436 break;
437 }
438 else if( nMatches == 0 )
439 {
440 altNextRef = cmp;
441 altRefIndex = i;
442 }
443 else if( nMatches < minMatches )
444 {
445 minMatches = nMatches;
446 bestNextRef = cmp;
447 bestRefIndex = i;
448 }
449 }
450
451 BACKTRACK_STAGE next( current );
452 next.m_currentMatch = -1;
453
454 if( bestNextRef )
455 {
456 next.m_ref = bestNextRef;
457 next.m_refIndex = bestRefIndex;
458 }
459 else
460 {
461 next.m_ref = altNextRef;
462 next.m_refIndex = altRefIndex;
463 }
464
465 stack.push_back( next );
466 };
467
468
470}
471
472#if 0
473int main()
474{
475 FILE * f = fopen("connectivity.dump","rb" );
476 auto cgRef = loadCGraph(f);
477 auto cgTarget = loadCGraph(f);
478
479 cgRef->buildConnectivity();
480 cgTarget->buildConnectivity();
481
482 int attempts = 0;
483 int max_loops = 0;
484
485 for( ;; )
486 {
487 cgRef->shuffle();
488 cgTarget->shuffle();
489
490 const BacktrackStage latest = cgRef->matchCGraphs( cgTarget );
491
492 if( !latest.locked.size() )
493 {
494 printf("MATCH FAIL\n");
495 break;
496 }
497
498 //printf("loops: %d\n", latest.nloops );
499 //printf("Locked: %d\n", latest.locked.size() );
500
501 //if (matchFound)
502 //{
503 // for( auto& iter : latest.locked )
504 //{
505 // printf("%-10s : %-10s\n", iter.first->reference.c_str(), iter.second->reference.c_str() );
506 //}
507
508 //}
509
510 if( latest.nloops > max_loops )
511 {
512 max_loops = latest.nloops;
513 }
514
515 if (attempts % 10000 == 0)
516 {
517 printf("attempts: %d maxloops: %d\n", attempts, max_loops );
518 }
519
520 attempts++;
521
522 }
523
524 fclose(f);
525
526 return 0;
527}
528
529#endif
530
531COMPONENT::COMPONENT( const wxString& aRef, FOOTPRINT* aParentFp, std::optional<VECTOR2I> aRaOffset ) :
532 m_reference( aRef ), m_parentFootprint( aParentFp ), m_raOffset( aRaOffset )
533{
535}
536
537bool COMPONENT::IsSameKind( const COMPONENT& b ) const
538{
539 return m_prefix == b.m_prefix &&
542}
543
545{
546 m_pins.push_back( aPin );
547 aPin->SetParent( this );
548}
549
551{
552 if( GetPinCount() != b->GetPinCount() )
553 {
554 return false;
555 }
556
557 if( !IsSameKind( *b ) )
558 {
559 return false;
560 }
561
562 for( int pin = 0; pin < b->GetPinCount(); pin++ )
563 {
564 if( !b->m_pins[pin]->IsIsomorphic( *m_pins[pin] ) )
565 {
566 return false;
567 }
568
569 }
570
571 return true;
572}
573
575{
576 auto cmp = new COMPONENT( aFp->GetReference(), aFp );;
577
578 for( auto pad : aFp->Pads() )
579 {
580 auto pin = new PIN( );
581 pin->m_netcode = pad->GetNetCode();
582 pin->m_ref = pad->GetNumber();
583 cmp->AddPin( pin );
584 }
585
586 m_components.push_back( cmp );
587}
588
589std::unique_ptr<CONNECTION_GRAPH> CONNECTION_GRAPH::BuildFromFootprintSet( const std::set<FOOTPRINT*>& aFps )
590{
591 auto cgraph = std::make_unique<CONNECTION_GRAPH>();
592 VECTOR2I ref(0, 0);
593
594 if( aFps.size() > 0 )
595 ref = (*aFps.begin())->GetPosition();
596
597 for( auto fp : aFps )
598 {
599 cgraph->AddFootprint( fp, fp->GetPosition() - ref );
600 }
601
602 cgraph->BuildConnectivity();
603
604 return std::move(cgraph);
605}
606
607
609{
610
611}
612
613
615{
616 for( COMPONENT* fp : m_components )
617 {
618 delete fp;
619 }
620}
621
622
624{
625 for( PIN* p : m_pins )
626 {
627 delete p;
628 }
629}
630
631
632}; // namespace TMATCH
std::deque< PAD * > & Pads()
Definition: footprint.h:205
const LIB_ID & GetFPID() const
Definition: footprint.h:247
wxString GetReferenceAsString() const
Definition: footprint.h:630
const wxString & GetReference() const
Definition: footprint.h:621
bool empty() const
Definition: lib_id.h:193
const std::map< COMPONENT *, COMPONENT * > & GetMatchingComponentPairs() const
Definition: topo_match.h:138
std::map< COMPONENT *, COMPONENT * > m_locked
Definition: topo_match.h:145
bool MatchesWith(COMPONENT *b)
Definition: topo_match.cpp:550
bool IsSameKind(const COMPONENT &b) const
Definition: topo_match.cpp:537
int GetPinCount() const
Definition: topo_match.h:56
COMPONENT(const wxString &aRef, FOOTPRINT *aParentFp, std::optional< VECTOR2I > aRaOffset=std::optional< VECTOR2I >())
Definition: topo_match.cpp:531
FOOTPRINT * m_parentFootprint
Definition: topo_match.h:71
wxString m_prefix
Definition: topo_match.h:70
void AddPin(PIN *p)
Definition: topo_match.cpp:544
std::vector< PIN * > & Pins()
Definition: topo_match.h:58
wxString m_reference
Definition: topo_match.h:69
std::vector< PIN * > m_pins
Definition: topo_match.h:72
FOOTPRINT * GetParent() const
Definition: topo_match.h:59
STATUS FindIsomorphism(CONNECTION_GRAPH *target, COMPONENT_MATCHES &result)
Definition: topo_match.cpp:307
std::vector< COMPONENT * > findMatchingComponents(CONNECTION_GRAPH *aRefGraph, COMPONENT *ref, const BACKTRACK_STAGE &partialMatches)
Definition: topo_match.cpp:200
std::vector< COMPONENT * > & Components()
Definition: topo_match.h:172
std::vector< COMPONENT * > m_components
Definition: topo_match.h:189
void AddFootprint(FOOTPRINT *aFp, const VECTOR2I &aOffset)
Definition: topo_match.cpp:574
static std::unique_ptr< CONNECTION_GRAPH > BuildFromFootprintSet(const std::set< FOOTPRINT * > &aFps)
Definition: topo_match.cpp:589
std::vector< PIN * > m_conns
Definition: topo_match.h:112
void SetParent(COMPONENT *parent)
Definition: topo_match.h:83
COMPONENT * m_parent
Definition: topo_match.h:111
bool IsIsomorphic(const PIN &b) const
Definition: topo_match.cpp:49
int GetNetCode() const
Definition: topo_match.h:101
wxString m_ref
Definition: topo_match.h:109
main()
std::map< FOOTPRINT *, FOOTPRINT * > COMPONENT_MATCHES
Definition: topo_match.h:149
bool checkIfPadNetsMatch(const BACKTRACK_STAGE &aMatches, CONNECTION_GRAPH *aRefGraph, COMPONENT *aRef, COMPONENT *aTgt)
Definition: topo_match.cpp:121
wxString GetRefDesPrefix(const wxString &aRefDes)
Get the (non-numeric) prefix from a refdes - e.g.
bool contains(const _Container &__container, _Value __value)
Returns true if the container contains the given value.
Definition: kicad_algo.h:100
CITER next(CITER it)
Definition: ptree.cpp:124
Collection of utility functions for component reference designators (refdes)
static const wxString traceTopoMatch
Definition: topo_match.cpp:44