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{
76#if BOOST_VERSION >= 106700
77 try
78 {
79#endif
80
82 {
84 }
85 else
86 {
87 std::lock_guard<std::mutex> lock( rng_mutex );
89 }
90
91#if BOOST_VERSION >= 106700
92 }
93 catch( const boost::uuids::entropy_error& )
94 {
95 wxLogFatalError( "A Boost UUID entropy exception was thrown in %s:%s.",
96 __FILE__, __FUNCTION__ );
97 }
98#endif
99}
100
101
102KIID::KIID( int null ) :
103 m_uuid( nilGenerator() )
104{
105 wxASSERT( null == 0 );
106}
107
108
109KIID::KIID( const std::string& aString ) :
110 m_uuid()
111{
112 if( aString.length() == 8
113 && std::all_of( aString.begin(), aString.end(),
114 []( unsigned char c )
115 {
116 return std::isxdigit( c );
117 } ) )
118 {
119 // A legacy-timestamp-based UUID has only the last 4 octets filled in.
120 // Convert them individually to avoid stepping in the little-endian/big-endian
121 // doo-doo.
122 for( int i = 0; i < 4; ++i )
123 {
124 std::string octet = aString.substr( i * 2, 2 );
125 m_uuid.data[i + 12] = strtol( octet.data(), nullptr, 16 );
126 }
127 }
128 else
129 {
130 try
131 {
132 m_uuid = stringGenerator( aString );
133 }
134 catch( ... )
135 {
136 // Failed to parse string representation; best we can do is assign a new
137 // random one.
138#if BOOST_VERSION >= 106700
139 try
140 {
141#endif
142
144
145#if BOOST_VERSION >= 106700
146 }
147 catch( const boost::uuids::entropy_error& )
148 {
149 wxLogFatalError( "A Boost UUID entropy exception was thrown in %s:%s.",
150 __FILE__, __FUNCTION__ );
151 }
152#endif
153 }
154 }
155}
156
157
158KIID::KIID( const char* aString ) :
159 KIID( std::string( aString ) )
160{
161}
162
163
164KIID::KIID( const wxString& aString ) :
165 KIID( std::string( aString.ToUTF8() ) )
166{
167}
168
169
170bool KIID::SniffTest( const wxString& aCandidate )
171{
172 static wxString niluuidStr = niluuid.AsString();
173
174 if( aCandidate.Length() != niluuidStr.Length() )
175 return false;
176
177 for( wxChar c : aCandidate )
178 {
179 if( c >= '0' && c <= '9' )
180 continue;
181
182 if( c >= 'a' && c <= 'f' )
183 continue;
184
185 if( c >= 'A' && c <= 'F' )
186 continue;
187
188 if( c == '-' )
189 continue;
190
191 return false;
192 }
193
194 return true;
195}
196
197
199{
200 m_uuid.data[12] = static_cast<uint8_t>( aTimestamp >> 24 );
201 m_uuid.data[13] = static_cast<uint8_t>( aTimestamp >> 16 );
202 m_uuid.data[14] = static_cast<uint8_t>( aTimestamp >> 8 );
203 m_uuid.data[15] = static_cast<uint8_t>( aTimestamp );
204}
205
206
208{
209 return !m_uuid.data[8] && !m_uuid.data[9] && !m_uuid.data[10] && !m_uuid.data[11];
210}
211
212
214{
215 timestamp_t ret = 0;
216
217 ret |= m_uuid.data[12] << 24;
218 ret |= m_uuid.data[13] << 16;
219 ret |= m_uuid.data[14] << 8;
220 ret |= m_uuid.data[15];
221
222 return ret;
223}
224
225
226size_t KIID::Hash() const
227{
228 size_t hash = 0;
229
230 // Note: this is NOT little-endian/big-endian safe, but as long as it's just used
231 // at runtime it won't matter.
232
233 for( int i = 0; i < 4; ++i )
234 boost::hash_combine( hash, reinterpret_cast<const uint32_t*>( m_uuid.data )[i] );
235
236 return hash;
237}
238
239
240void KIID::Clone( const KIID& aUUID )
241{
242 m_uuid = aUUID.m_uuid;
243}
244
245
246wxString KIID::AsString() const
247{
248 return boost::uuids::to_string( m_uuid );
249}
250
251
252std::string KIID::AsStdString() const
253{
254 return boost::uuids::to_string( m_uuid );
255}
256
257
259{
260 return wxString::Format( "%8.8lX", (unsigned long) AsLegacyTimestamp() );
261}
262
263
265{
266 if( !IsLegacyTimestamp() )
267 return;
268
270}
271
272
274{
275 // This obviously destroys uniform distribution, but it can be useful when a
276 // deterministic replacement for a duplicate ID is required.
277
278 for( int i = 15; i >= 0; --i )
279 {
280 m_uuid.data[i]++;
281
282 if( m_uuid.data[i] != 0 )
283 break;
284 }
285}
286
287
288void KIID::CreateNilUuids( bool aNil )
289{
290 g_createNilUuids = aNil;
291}
292
293
294void KIID::SeedGenerator( unsigned int aSeed )
295{
296 rng.seed( aSeed );
297 randomGenerator = boost::uuids::basic_random_generator<boost::mt19937>( rng );
298}
299
300
301KIID_PATH::KIID_PATH( const wxString& aString )
302{
303 for( const wxString& pathStep : wxSplit( aString, '/' ) )
304 {
305 if( !pathStep.empty() )
306 emplace_back( KIID( pathStep ) );
307 }
308}
309
310
312{
313 KIID_PATH copy = *this;
314 clear();
315
316 if( aPath.size() > copy.size() )
317 return false; // this path is not contained within aPath
318
319 for( size_t i = 0; i < aPath.size(); ++i )
320 {
321 if( copy.at( i ) != aPath.at( i ) )
322 {
323 *this = copy;
324 return false; // this path is not contained within aPath
325 }
326 }
327
328 for( size_t i = aPath.size(); i < copy.size(); ++i )
329 push_back( copy.at( i ) );
330
331 return true;
332}
333
334
335bool KIID_PATH::EndsWith( const KIID_PATH& aPath ) const
336{
337 if( aPath.size() > size() )
338 return false; // this path can not end aPath
339
340 KIID_PATH copyThis = *this;
341 KIID_PATH copyThat = aPath;
342
343 while( !copyThat.empty() )
344 {
345 if( *std::prev( copyThis.end() ) != *std::prev( copyThat.end() ) )
346 return false;
347
348 copyThis.pop_back();
349 copyThat.pop_back();
350 }
351
352 return true;
353}
354
355
356wxString KIID_PATH::AsString() const
357{
358 wxString path;
359
360 for( const KIID& pathStep : *this )
361 path += '/' + pathStep.AsString();
362
363 return path;
364}
365
366
367void to_json( nlohmann::json& aJson, const KIID& aKIID )
368{
369 aJson = aKIID.AsString().ToUTF8();
370}
371
372
373void from_json( const nlohmann::json& aJson, KIID& aKIID )
374{
375 aKIID = KIID( aJson.get<std::string>() );
376}
bool EndsWith(const KIID_PATH &aPath) const
Test if aPath from the last path towards the first path.
Definition: kiid.cpp:335
bool MakeRelativeTo(const KIID_PATH &aPath)
Definition: kiid.cpp:311
KIID_PATH()
Definition: kiid.h:142
wxString AsString() const
Definition: kiid.cpp:356
Definition: kiid.h:49
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:294
size_t Hash() const
Definition: kiid.cpp:226
wxString AsString() const
Definition: kiid.cpp:246
boost::uuids::uuid m_uuid
Definition: kiid.h:128
void Increment()
Generates a deterministic replacement for a given ID.
Definition: kiid.cpp:273
std::string AsStdString() const
Definition: kiid.cpp:252
wxString AsLegacyTimestampString() const
Definition: kiid.cpp:258
timestamp_t AsLegacyTimestamp() const
Definition: kiid.cpp:213
static void CreateNilUuids(bool aNil=true)
A performance optimization which disables/enables the generation of pseudo-random UUIDs.
Definition: kiid.cpp:288
static bool SniffTest(const wxString &aCandidate)
Returns true if a string has the correct formatting to be a KIID.
Definition: kiid.cpp:170
void Clone(const KIID &aUUID)
Definition: kiid.cpp:240
bool IsLegacyTimestamp() const
Definition: kiid.cpp:207
void ConvertTimestampToUuid()
Change an existing time stamp based UUID into a true UUID.
Definition: kiid.cpp:264
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:373
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:367
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.