KiCad PCB EDA Suite
Loading...
Searching...
No Matches
kiid.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 (C) 2020 Ian McInerney <[email protected]>
5 * Copyright (C) 2007-2014 Jean-Pierre Charras, jp.charras at wanadoo.fr
6 * Copyright (C) 1992-2023 KiCad Developers, see AUTHORS.TXT for contributors.
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
19 * along with this program; if not, you may find one here:
20 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
21 * or you may search the http://www.gnu.org website for the version 2 license,
22 * or you may write to the Free Software Foundation, Inc.,
23 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24 */
25
26#include <kiid.h>
27
28#include <boost/uuid/uuid_generators.hpp>
29#include <boost/uuid/uuid_io.hpp>
30#include <boost/functional/hash.hpp>
31
32#if BOOST_VERSION >= 106700
33#include <boost/uuid/entropy_error.hpp>
34#endif
35
36#include <nlohmann/json.hpp>
37
38#include <cctype>
39#include <mutex>
40
41#include <wx/log.h>
42
43// boost:mt19937 is not thread-safe
44static std::mutex rng_mutex;
45
46// Static rng and generators are used because the overhead of constant seeding is expensive
47// We rely on the default non-arg constructor of basic_random_generator to provide a random seed.
48// We use a separate rng object for cases where we want to control the basic_random_generator
49// initial seed by calling SeedGenerator from unit tests and other special cases.
50static boost::mt19937 rng;
51static boost::uuids::basic_random_generator<boost::mt19937> randomGenerator;
52
53// These don't have the same performance penalty, but we might as well be consistent
54static boost::uuids::string_generator stringGenerator;
55static boost::uuids::nil_generator nilGenerator;
56
57
58// Global nil reference
60
61
62// When true, always create nil uuids for performance, when valid ones aren't needed
63static bool g_createNilUuids = false;
64
65
66// For static initialization
68{
69 static KIID nil( 0 );
70 return nil;
71}
72
73
75{
77
78#if BOOST_VERSION >= 106700
79 try
80 {
81#endif
82
84 {
86 }
87 else
88 {
89 std::lock_guard<std::mutex> lock( rng_mutex );
91 }
92
93#if BOOST_VERSION >= 106700
94 }
95 catch( const boost::uuids::entropy_error& )
96 {
97 wxLogFatalError( "A Boost UUID entropy exception was thrown in %s:%s.",
98 __FILE__, __FUNCTION__ );
99 }
100#endif
101}
102
103
104KIID::KIID( int null ) :
105 m_uuid( nilGenerator() ),
106 m_cached_timestamp( 0 )
107{
108 wxASSERT( null == 0 );
109}
110
111
112KIID::KIID( const std::string& aString ) :
113 m_uuid(),
114 m_cached_timestamp( 0 )
115{
116 if( aString.length() == 8
117 && std::all_of( aString.begin(), aString.end(),
118 []( unsigned char c )
119 {
120 return std::isxdigit( c );
121 } ) )
122 {
123 // A legacy-timestamp-based UUID has only the last 4 octets filled in.
124 // Convert them individually to avoid stepping in the little-endian/big-endian
125 // doo-doo.
126 for( int i = 0; i < 4; ++i )
127 {
128 std::string octet = aString.substr( i * 2, 2 );
129 m_uuid.data[i + 12] = strtol( octet.data(), nullptr, 16 );
130 }
131
132 m_cached_timestamp = strtol( aString.c_str(), nullptr, 16 );
133 }
134 else
135 {
136 try
137 {
138 m_uuid = stringGenerator( aString );
139
140 if( IsLegacyTimestamp() )
141 m_cached_timestamp = strtol( aString.substr( 28 ).c_str(), nullptr, 16 );
142 }
143 catch( ... )
144 {
145 // Failed to parse string representation; best we can do is assign a new
146 // random one.
147#if BOOST_VERSION >= 106700
148 try
149 {
150#endif
151
153
154#if BOOST_VERSION >= 106700
155 }
156 catch( const boost::uuids::entropy_error& )
157 {
158 wxLogFatalError( "A Boost UUID entropy exception was thrown in %s:%s.",
159 __FILE__, __FUNCTION__ );
160 }
161#endif
162 }
163 }
164}
165
166
167KIID::KIID( const char* aString ) :
168 KIID( std::string( aString ) )
169{
170}
171
172
173KIID::KIID( const wxString& aString ) :
174 KIID( std::string( aString.ToUTF8() ) )
175{
176}
177
178
179bool KIID::SniffTest( const wxString& aCandidate )
180{
181 static wxString niluuidStr = niluuid.AsString();
182
183 if( aCandidate.Length() != niluuidStr.Length() )
184 return false;
185
186 for( wxChar c : aCandidate )
187 {
188 if( c >= '0' && c <= '9' )
189 continue;
190
191 if( c >= 'a' && c <= 'f' )
192 continue;
193
194 if( c >= 'A' && c <= 'F' )
195 continue;
196
197 if( c == '-' )
198 continue;
199
200 return false;
201 }
202
203 return true;
204}
205
206
208{
209 m_cached_timestamp = aTimestamp;
210
211 // A legacy-timestamp-based UUID has only the last 4 octets filled in.
212 // Convert them individually to avoid stepping in the little-endian/big-endian
213 // doo-doo.
214 wxString str = AsLegacyTimestampString();
215
216 for( int i = 0; i < 4; ++i )
217 {
218 wxString octet = str.substr( i * 2, 2 );
219 m_uuid.data[i + 12] = strtol( octet.data(), nullptr, 16 );
220 }
221}
222
223
225{
226 return !m_uuid.data[8] && !m_uuid.data[9] && !m_uuid.data[10] && !m_uuid.data[11];
227}
228
229
231{
232 return m_cached_timestamp;
233}
234
235
236size_t KIID::Hash() const
237{
238 size_t hash = 0;
239
240 // Note: this is NOT little-endian/big-endian safe, but as long as it's just used
241 // at runtime it won't matter.
242
243 for( int i = 0; i < 4; ++i )
244 boost::hash_combine( hash, reinterpret_cast<const uint32_t*>( m_uuid.data )[i] );
245
246 return hash;
247}
248
249
250void KIID::Clone( const KIID& aUUID )
251{
252 m_uuid = aUUID.m_uuid;
254}
255
256
257wxString KIID::AsString() const
258{
259 return boost::uuids::to_string( m_uuid );
260}
261
262
264{
265 return wxString::Format( "%8.8lX", (unsigned long) AsLegacyTimestamp() );
266}
267
268
270{
271 if( !IsLegacyTimestamp() )
272 return;
273
276}
277
278
280{
281 // This obviously destroys uniform distribution, but it can be useful when a
282 // deterministic replacement for a duplicate ID is required.
283
284 for( int i = 15; i >= 0; --i )
285 {
286 m_uuid.data[i]++;
287
288 if( m_uuid.data[i] != 0 )
289 break;
290 }
291}
292
293
294void KIID::CreateNilUuids( bool aNil )
295{
296 g_createNilUuids = aNil;
297}
298
299
300void KIID::SeedGenerator( unsigned int aSeed )
301{
302 rng.seed( aSeed );
303 randomGenerator = boost::uuids::basic_random_generator<boost::mt19937>( rng );
304}
305
306
307KIID_PATH::KIID_PATH( const wxString& aString )
308{
309 for( const wxString& pathStep : wxSplit( aString, '/' ) )
310 {
311 if( !pathStep.empty() )
312 emplace_back( KIID( pathStep ) );
313 }
314}
315
316
318{
319 KIID_PATH copy = *this;
320 clear();
321
322 if( aPath.size() > copy.size() )
323 return false; // this path is not contained within aPath
324
325 for( size_t i = 0; i < aPath.size(); ++i )
326 {
327 if( copy.at( i ) != aPath.at( i ) )
328 {
329 *this = copy;
330 return false; // this path is not contained within aPath
331 }
332 }
333
334 for( size_t i = aPath.size(); i < copy.size(); ++i )
335 push_back( copy.at( i ) );
336
337 return true;
338}
339
340
341bool KIID_PATH::EndsWith( const KIID_PATH& aPath ) const
342{
343 if( aPath.size() > size() )
344 return false; // this path can not end aPath
345
346 KIID_PATH copyThis = *this;
347 KIID_PATH copyThat = aPath;
348
349 while( !copyThat.empty() )
350 {
351 if( *std::prev( copyThis.end() ) != *std::prev( copyThat.end() ) )
352 return false;
353
354 copyThis.pop_back();
355 copyThat.pop_back();
356 }
357
358 return true;
359}
360
361
362wxString KIID_PATH::AsString() const
363{
364 wxString path;
365
366 for( const KIID& pathStep : *this )
367 path += '/' + pathStep.AsString();
368
369 return path;
370}
371
372
373void to_json( nlohmann::json& aJson, const KIID& aKIID )
374{
375 aJson = aKIID.AsString().ToUTF8();
376}
377
378
379void from_json( const nlohmann::json& aJson, KIID& aKIID )
380{
381 aKIID = KIID( aJson.get<std::string>() );
382}
bool EndsWith(const KIID_PATH &aPath) const
Test if aPath from the last path towards the first path.
Definition: kiid.cpp:341
bool MakeRelativeTo(const KIID_PATH &aPath)
Definition: kiid.cpp:317
KIID_PATH()
Definition: kiid.h:143
wxString AsString() const
Definition: kiid.cpp:362
Definition: kiid.h:49
timestamp_t m_cached_timestamp
Definition: kiid.h:129
KIID()
Definition: kiid.cpp:74
static void SeedGenerator(unsigned int aSeed)
Re-initialize the UUID generator with a given seed (for testing or QA purposes)
Definition: kiid.cpp:300
size_t Hash() const
Definition: kiid.cpp:236
wxString AsString() const
Definition: kiid.cpp:257
boost::uuids::uuid m_uuid
Definition: kiid.h:127
void Increment()
Generates a deterministic replacement for a given ID.
Definition: kiid.cpp:279
wxString AsLegacyTimestampString() const
Definition: kiid.cpp:263
timestamp_t AsLegacyTimestamp() const
Definition: kiid.cpp:230
static void CreateNilUuids(bool aNil=true)
A performance optimization which disables/enables the generation of pseudo-random UUIDs.
Definition: kiid.cpp:294
static bool SniffTest(const wxString &aCandidate)
Returns true if a string has the correct formatting to be a KIID.
Definition: kiid.cpp:179
void Clone(const KIID &aUUID)
Definition: kiid.cpp:250
bool IsLegacyTimestamp() const
Definition: kiid.cpp:224
void ConvertTimestampToUuid()
Change an existing time stamp based UUID into a true UUID.
Definition: kiid.cpp:269
static boost::uuids::nil_generator nilGenerator
Definition: kiid.cpp:55
static bool g_createNilUuids
Definition: kiid.cpp:63
KIID & NilUuid()
Definition: kiid.cpp:67
static std::mutex rng_mutex
Definition: kiid.cpp:44
static boost::mt19937 rng
Definition: kiid.cpp:50
void from_json(const nlohmann::json &aJson, KIID &aKIID)
Definition: kiid.cpp:379
static boost::uuids::string_generator stringGenerator
Definition: kiid.cpp:54
static boost::uuids::basic_random_generator< boost::mt19937 > randomGenerator
Definition: kiid.cpp:51
void to_json(nlohmann::json &aJson, const KIID &aKIID)
Definition: kiid.cpp:373
KIID niluuid(0)
KICOMMON_API KIID niluuid
uint32_t timestamp_t
timestamp_t is our type to represent unique IDs for all kinds of elements; historically simply the ti...
Definition: kiid.h:46
STL namespace.