KiCad PCB EDA Suite
Loading...
Searching...
No Matches
refdes_tracker.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 * KiCad is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * KiCad 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 KiCad. If not, see <https://www.gnu.org/licenses/>.
18 */
19
20#include <regex>
21#include <algorithm>
22#include <cctype>
23#include <charconv>
24#include <iostream>
25
26#include <sch_reference_list.h>
27
28#include "refdes_tracker.h"
29
30REFDES_TRACKER::REFDES_TRACKER( bool aThreadSafe ) :
31 m_threadSafe( aThreadSafe ), m_reuseRefDes( true )
32{
33}
34
35bool REFDES_TRACKER::Insert( const std::string& aRefDes )
36{
37 std::unique_lock<std::mutex> lock;
38
39 if( m_threadSafe )
40 lock = std::unique_lock<std::mutex>( m_mutex );
41
42 return insertImpl( aRefDes );
43}
44
45bool REFDES_TRACKER::insertImpl( const std::string& aRefDes )
46{
47 if( m_allRefDes.find( aRefDes ) != m_allRefDes.end() )
48 return false;
49
50 auto [prefix, number] = parseRefDes( aRefDes );
51
52 m_allRefDes.insert( aRefDes );
53
54 // Insert the number and update caches
55 return insertNumber( prefix, number );
56}
57
58bool REFDES_TRACKER::insertNumber( const std::string& aPrefix, int aNumber )
59{
60 PREFIX_DATA& data = m_prefixData[aPrefix];
61
62 if( data.m_usedNumbers.find( aNumber ) != data.m_usedNumbers.end() )
63 return false;
64
65 data.m_usedNumbers.insert( aNumber );
66
67 if( aNumber > 0 )
68 updateCacheOnInsert( data, aNumber );
69
70 return true;
71}
72
73
74bool REFDES_TRACKER::containsImpl( const std::string& aRefDes ) const
75{
76 return m_allRefDes.contains( aRefDes );
77}
78
79bool REFDES_TRACKER::Contains( const std::string& aRefDes ) const
80{
81 std::unique_lock<std::mutex> lock;
82
83 if( m_threadSafe )
84 lock = std::unique_lock<std::mutex>( m_mutex );
85
86 return containsImpl( aRefDes );
87}
88
89
91 const std::map<int, std::vector<SCH_REFERENCE>>& aRefNumberMap,
92 const std::vector<int>& aRequiredUnits, int aMinValue,
93 const std::function<bool( int )>& aAcceptNumber )
94{
95 std::unique_lock<std::mutex> lock;
96
97 if( m_threadSafe )
98 lock = std::unique_lock<std::mutex>( m_mutex );
99
100 // Filter out negative unit numbers
101 std::vector<int> validUnits;
102 std::copy_if( aRequiredUnits.begin(), aRequiredUnits.end(),
103 std::back_inserter( validUnits ),
104 []( int unit ) { return unit >= 0; } );
105
106 int candidate = aMinValue;
107
108 while( true )
109 {
110 if( aAcceptNumber && !aAcceptNumber( candidate ) )
111 {
112 candidate++;
113 continue;
114 }
115
116 // Check if this candidate number is currently in use
117 auto mapIt = aRefNumberMap.find( candidate );
118
119 if( mapIt == aRefNumberMap.end() )
120 {
121 // Not currently in use - check if it was previously used
122 std::string candidateRefDes = aRef.GetRef().ToStdString() + std::to_string( candidate );
123
124 if( m_reuseRefDes || !containsImpl( candidateRefDes ) )
125 {
126 // Completely unused - this is our answer
127 insertNumber( aRef.GetRefStr(), candidate );
128 m_allRefDes.insert( candidateRefDes );
129 return candidate;
130 }
131 else
132 {
133 // Previously used but no longer active - skip to next candidate
134 candidate++;
135 continue;
136 }
137 }
138 else
139 {
140 // Currently in use - check if required units are available
141 if( validUnits.empty() )
142 {
143 // Need completely unused reference, but this one is in use
144 candidate++;
145 continue;
146 }
147
148 if( areUnitsAvailable( aRef, mapIt->second, validUnits ) )
149 {
150 // All required units are available - this is our answer
151 // Note: Don't insert into tracker since reference is already in use
152 return candidate;
153 }
154 else
155 {
156 // Some required units are not available - try next candidate
157 candidate++;
158 continue;
159 }
160 }
161 }
162}
163
164
166 const std::vector<SCH_REFERENCE>& aRefVector,
167 const std::vector<int>& aRequiredUnits ) const
168{
169 for( const int& unit : aRequiredUnits )
170 {
171 for( const SCH_REFERENCE& ref : aRefVector )
172 {
173 // If we have a different library or different value,
174 // we cannot share a reference designator. Also, if the unit matches,
175 // the reference designator + unit is already in use.
176 if( ref.CompareLibId( aRef ) != 0
177 || ref.CompareValue( aRef ) != 0
178 || ref.GetUnit() == unit )
179 {
180 return false; // Conflict found
181 }
182 }
183 }
184
185 return true; // All required units are available
186}
187
188
189std::pair<std::string, int> REFDES_TRACKER::parseRefDes( const std::string& aRefDes ) const
190{
191 if( aRefDes.empty() )
192 return { "", 0 };
193
194 // Split on the trailing run of digits so any non-digit prefix (including '#'
195 // used by power and flag symbols) is preserved as the map key.
196 size_t pos = aRefDes.size();
197
198 while( pos > 0 && std::isdigit( static_cast<unsigned char>( aRefDes[pos - 1] ) ) )
199 pos--;
200
201 if( pos == 0 )
202 return { aRefDes, 0 };
203
204 if( pos == aRefDes.size() )
205 return { aRefDes, 0 };
206
207 int number = 0;
208 const char* first = aRefDes.data() + pos;
209 const char* last = aRefDes.data() + aRefDes.size();
210 auto [ptr, ec] = std::from_chars( first, last, number );
211
212 if( ec != std::errc() || ptr != last )
213 return { aRefDes, 0 };
214
215 return { aRefDes.substr( 0, pos ), number };
216}
217
219{
220 if( aData.m_cacheValid )
221 return;
222
223 // Find the first gap in the sequence starting from 1
224 int candidate = 1;
225 for( int used : aData.m_usedNumbers )
226 {
227 if( used <= 0 )
228 continue; // Skip non-positive numbers (like our 0 marker)
229 if( used == candidate )
230 {
231 candidate++;
232 }
233 else if( used > candidate )
234 {
235 break; // Found a gap
236 }
237 }
238
239 aData.m_baseNext = candidate;
240 aData.m_cacheValid = true;
241}
242
243void REFDES_TRACKER::updateCacheOnInsert( PREFIX_DATA& aData, int aInsertedNumber ) const
244{
245 // Update base next cache if it's valid and affected
246 if( aData.m_cacheValid )
247 {
248 if( aInsertedNumber == aData.m_baseNext )
249 {
250 // The base next was just used, find the new next
251 int candidate = aData.m_baseNext + 1;
252 while( aData.m_usedNumbers.find( candidate ) != aData.m_usedNumbers.end() )
253 {
254 candidate++;
255 }
256 aData.m_baseNext = candidate;
257 }
258 // If aInsertedNumber > m_baseNext, base cache is still valid
259 // If aInsertedNumber < m_baseNext, base cache is still valid
260 }
261
262 for( auto cacheIt = aData.m_nextCache.begin(); cacheIt != aData.m_nextCache.end(); ++cacheIt )
263 {
264 int cachedNext = cacheIt->second;
265
266 if( aInsertedNumber == cachedNext )
267 {
268 // This cached value was just used, need to update it
269 int candidate = cachedNext + 1;
270
271 while( aData.m_usedNumbers.contains( candidate ) )
272 candidate++;
273
274 cacheIt->second = candidate;
275 }
276 }
277}
278
279int REFDES_TRACKER::findNextAvailable( const PREFIX_DATA& aData, int aMinValue ) const
280{
281 if( auto cacheIt = aData.m_nextCache.find( aMinValue ); cacheIt != aData.m_nextCache.end() )
282 return cacheIt->second;
283
284 updateBaseNext( const_cast<PREFIX_DATA&>( aData ) );
285
286 int candidate;
287
288 if( aMinValue <= 1 )
289 {
290 candidate = aData.m_baseNext;
291 }
292 else
293 {
294 // Start search from aMinValue
295 candidate = aMinValue;
296
297 while( aData.m_usedNumbers.find( candidate ) != aData.m_usedNumbers.end() )
298 candidate++;
299 }
300
301 // Cache the result
302 aData.m_nextCache[aMinValue] = candidate;
303
304 return candidate;
305}
306
307std::string REFDES_TRACKER::Serialize() const
308{
309 std::unique_lock<std::mutex> lock;
310 if( m_threadSafe )
311 lock = std::unique_lock<std::mutex>( m_mutex );
312
313 std::ostringstream result;
314 bool first = true;
315
316 using PREFIX_ENTRY = std::pair<const std::string, PREFIX_DATA>;
317
318 std::vector<const PREFIX_ENTRY*> entries;
319 entries.reserve( m_prefixData.size() );
320
321 for( const auto& entry : m_prefixData )
322 entries.push_back( &entry );
323
324 std::sort( entries.begin(), entries.end(),
325 []( const auto* aLeft, const auto* aRight )
326 {
327 return aLeft->first < aRight->first;
328 } );
329
330 for( const auto* entry : entries )
331 {
332 const std::string& prefix = entry->first;
333 const PREFIX_DATA& data = entry->second;
334
335 if( !first )
336 result << ",";
337 first = false;
338
339 std::string escapedPrefix = escapeForSerialization( prefix );
340
341 // Separate numbers from prefix-only entries
342 std::vector<int> numbers;
343 bool hasPrefix = false;
344
345 for( int num : data.m_usedNumbers )
346 {
347 if( num > 0 )
348 numbers.push_back( num );
349 else if( num == 0 )
350 hasPrefix = true;
351 }
352
353 if( numbers.empty() && !hasPrefix )
354 continue; // No data for this prefix
355
356 // Create ranges for numbered entries
357 std::vector<std::pair<int, int>> ranges;
358
359 if( !numbers.empty() )
360 {
361 int start = numbers[0];
362 int end = numbers[0];
363
364 for( size_t i = 1; i < numbers.size(); ++i )
365 {
366 if( numbers[i] == end + 1 )
367 {
368 end = numbers[i];
369 }
370 else
371 {
372 ranges.push_back( { start, end } );
373 start = end = numbers[i];
374 }
375 }
376 ranges.push_back( { start, end } );
377 }
378
379 bool firstRange = true;
380 for( const auto& [start, end] : ranges )
381 {
382 if( !firstRange )
383 result << ",";
384 firstRange = false;
385
386 result << escapedPrefix;
387 if( start == end )
388 {
389 result << start;
390 }
391 else
392 {
393 result << start << "-" << end;
394 }
395 }
396
397 // Add prefix-only entry if it exists
398 if( hasPrefix )
399 {
400 if( !firstRange )
401 result << ",";
402 result << escapedPrefix;
403 }
404 }
405
406 return result.str();
407}
408
409bool REFDES_TRACKER::Deserialize( const std::string& aData )
410{
411 std::unique_lock<std::mutex> lock;
412
413 if( m_threadSafe )
414 lock = std::unique_lock<std::mutex>( m_mutex );
415
416 clearImpl();
417
418 if( aData.empty() )
419 return true;
420
421 auto parts = splitString( aData, ',' );
422
423 // A malformed project file must fail Deserialize cleanly rather than throw,
424 // since QA builds install wxAssertThrower around the calling load path.
425 auto parsePositiveInt = []( const std::ssub_match& aMatch, int& aOut ) -> bool
426 {
427 const char* first = std::to_address( aMatch.first );
428 const char* last = std::to_address( aMatch.second );
429 int value = 0;
430 auto [ptr, ec] = std::from_chars( first, last, value );
431
432 if( ec != std::errc() || ptr != last || value <= 0 )
433 return false;
434
435 aOut = value;
436 return true;
437 };
438
439 // Prefix may contain any non-digit characters, including '#' for power flags
440 // and embedded digits (e.g. "U1U2"), so anchor on the final non-digit before
441 // the trailing digit run. Hoisted out of the loop because std::regex
442 // construction dominates the per-part match cost.
443 const std::regex rangePattern( R"(^(.*\D)(\d+)-(\d+)$)" );
444 const std::regex numberedPattern( R"(^(.*\D)(\d+)$)" );
445 const std::regex prefixOnlyPattern( R"(^(.+)$)" );
446
447 for( const std::string& part : parts )
448 {
449 std::string unescaped = unescapeFromSerialization( part );
450 std::smatch match;
451
452 if( std::regex_match( unescaped, match, rangePattern ) )
453 {
454 std::string prefix = match[1].str();
455 int start = 0;
456 int end = 0;
457
458 if( !parsePositiveInt( match[2], start ) || !parsePositiveInt( match[3], end ) )
459 {
460 clearImpl();
461 return false;
462 }
463
464 for( int i = start; i <= end; ++i )
465 insertImpl( prefix + std::to_string( i ) );
466 }
467 else if( std::regex_match( unescaped, match, numberedPattern ) )
468 {
469 std::string prefix = match[1].str();
470 int number = 0;
471
472 if( !parsePositiveInt( match[2], number ) )
473 {
474 clearImpl();
475 return false;
476 }
477
478 insertImpl( prefix + std::to_string( number ) );
479 }
480 else if( std::regex_match( unescaped, match, prefixOnlyPattern ) )
481 {
482 std::string prefix = match[1].str();
483
484 insertImpl( prefix );
485 }
486 else
487 {
488 // Invalid format
489 clearImpl();
490 return false;
491 }
492 }
493
494 return true;
495}
496
498{
499 std::unique_lock<std::mutex> lock;
500
501 if( m_threadSafe )
502 lock = std::unique_lock<std::mutex>( m_mutex );
503
504 clearImpl();
505}
506
507
509{
510 m_prefixData.clear();
511 m_allRefDes.clear();
512}
513
515{
516 std::unique_lock<std::mutex> lock;
517
518 if( m_threadSafe )
519 lock = std::unique_lock<std::mutex>( m_mutex );
520
521 return m_allRefDes.size();
522}
523
524std::string REFDES_TRACKER::escapeForSerialization( const std::string& aStr ) const
525{
526 std::string result;
527 result.reserve( aStr.length() * 2 ); // Reserve space to avoid frequent reallocations
528
529 for( char c : aStr )
530 {
531 if( c == '\\' || c == ',' || c == '-' )
532 result += '\\';
533 result += c;
534 }
535 return result;
536}
537
538std::string REFDES_TRACKER::unescapeFromSerialization( const std::string& aStr ) const
539{
540 std::string result;
541 result.reserve( aStr.length() );
542
543 bool escaped = false;
544 for( char c : aStr )
545 {
546 if( escaped )
547 {
548 result += c;
549 escaped = false;
550 }
551 else if( c == '\\' )
552 {
553 escaped = true;
554 }
555 else
556 {
557 result += c;
558 }
559 }
560 return result;
561}
562
563std::vector<std::string> REFDES_TRACKER::splitString( const std::string& aStr, char aDelimiter ) const
564{
565 std::vector<std::string> result;
566 std::string current;
567 bool escaped = false;
568
569 for( char c : aStr )
570 {
571 if( escaped )
572 {
573 current += c;
574 escaped = false;
575 }
576 else if( c == '\\' )
577 {
578 escaped = true;
579 current += c;
580 }
581 else if( c == aDelimiter )
582 {
583 result.push_back( current );
584 current.clear();
585 }
586 else
587 {
588 current += c;
589 }
590 }
591
592 if( !current.empty() )
593 result.push_back( current );
594
595 return result;
596}
void updateBaseNext(PREFIX_DATA &aData) const
std::string escapeForSerialization(const std::string &aStr) const
Escape special characters for serialization.
bool insertNumber(const std::string &aPrefix, int aNumber)
Insert a number for a specific prefix, updating internal structures.
bool Deserialize(const std::string &aData)
Deserialize tracker data from string representation.
std::vector< std::string > splitString(const std::string &aStr, char aDelimiter) const
Split string by delimiter, handling escaped characters.
bool m_reuseRefDes
If true, allows reusing existing reference designators.
int GetNextRefDesForUnits(const SCH_REFERENCE &aRef, const std::map< int, std::vector< SCH_REFERENCE > > &aRefNumberMap, const std::vector< int > &aRequiredUnits, int aMinValue, const std::function< bool(int)> &aAcceptNumber={})
Get the next available reference designator number for multi-unit symbols.
std::mutex m_mutex
Mutex for thread safety.
std::unordered_set< std::string > m_allRefDes
bool Insert(const std::string &aRefDes)
Insert a reference designator into the tracker.
void clearImpl()
Clear all internal data structures without locking.
size_t Size() const
Get the total count of stored reference designators.
std::string unescapeFromSerialization(const std::string &aStr) const
Unescape special characters from serialization.
bool insertImpl(const std::string &aRefDes)
Internal implementation of Insert without locking.
int findNextAvailable(const PREFIX_DATA &aData, int aMinValue) const
Find next available number for a prefix starting from a minimum value.
REFDES_TRACKER(bool aThreadSafe=false)
Constructor.
bool areUnitsAvailable(const SCH_REFERENCE &aRef, const std::vector< SCH_REFERENCE > &aRefVector, const std::vector< int > &aRequiredUnits) const
Check if all required units are available for a given reference number.
void updateCacheOnInsert(PREFIX_DATA &aData, int aInsertedNumber) const
Update cached next available values when a number is inserted.
std::string Serialize() const
Serialize the tracker data to a compact string representation.
std::unordered_map< std::string, PREFIX_DATA > m_prefixData
Map from prefix to its tracking data.
bool m_threadSafe
True if thread safety is enabled.
bool Contains(const std::string &aRefDes) const
Check if a reference designator exists in the tracker.
std::pair< std::string, int > parseRefDes(const std::string &aRefDes) const
Parse a reference designator into prefix and numerical suffix.
bool containsImpl(const std::string &aRefDes) const
Check if a reference designator exists in the tracker without locking.
void Clear()
Clear all stored reference designators.
A helper to define a symbol's reference designator in a schematic.
wxString GetRef() const
const char * GetRefStr() const
Data structure for tracking used numbers and caching next available values.
std::set< int > m_usedNumbers
Sorted set of used numbers for this prefix.
bool m_cacheValid
True if m_baseNext cache is valid.
int m_baseNext
Next available from 1 (cached)
std::map< int, int > m_nextCache
Cache of next available number for given min values.
VECTOR2I end
wxString result
Test unit parsing edge cases and error handling.