KiCad PCB EDA Suite
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-2021 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 ) : m_uuid( nilGenerator() ), m_cached_timestamp( 0 )
105{
106 wxASSERT( null == 0 );
107}
108
109
110KIID::KIID( const std::string& aString ) : m_uuid(), m_cached_timestamp( 0 )
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 m_cached_timestamp = strtol( aString.c_str(), nullptr, 16 );
129 }
130 else
131 {
132 try
133 {
134 m_uuid = stringGenerator( aString );
135
136 if( IsLegacyTimestamp() )
137 m_cached_timestamp = strtol( aString.substr( 28 ).c_str(), nullptr, 16 );
138 }
139 catch( ... )
140 {
141 // Failed to parse string representation; best we can do is assign a new
142 // random one.
143#if BOOST_VERSION >= 106700
144 try
145 {
146#endif
147
149
150#if BOOST_VERSION >= 106700
151 }
152 catch( const boost::uuids::entropy_error& )
153 {
154 wxLogFatalError( "A Boost UUID entropy exception was thrown in %s:%s.",
155 __FILE__, __FUNCTION__ );
156 }
157#endif
158 }
159 }
160}
161
162
163KIID::KIID( const char* aString ) : KIID( std::string( aString ) )
164{
165}
166
167
168KIID::KIID( const wxString& aString ) : KIID( std::string( aString.ToUTF8() ) )
169{
170}
171
172
173bool KIID::SniffTest( const wxString& aCandidate )
174{
175 static wxString niluuidStr = niluuid.AsString();
176
177 if( aCandidate.Length() != niluuidStr.Length() )
178 return false;
179
180 for( wxChar c : aCandidate )
181 {
182 if( c >= '0' && c <= '9' )
183 continue;
184
185 if( c >= 'a' && c <= 'f' )
186 continue;
187
188 if( c >= 'A' && c <= 'F' )
189 continue;
190
191 if( c == '-' )
192 continue;
193
194 return false;
195 }
196
197 return true;
198}
199
200
202{
203 m_cached_timestamp = aTimestamp;
204
205 // A legacy-timestamp-based UUID has only the last 4 octets filled in.
206 // Convert them individually to avoid stepping in the little-endian/big-endian
207 // doo-doo.
208 wxString str = AsLegacyTimestampString();
209
210 for( int i = 0; i < 4; ++i )
211 {
212 wxString octet = str.substr( i * 2, 2 );
213 m_uuid.data[i + 12] = strtol( octet.data(), nullptr, 16 );
214 }
215}
216
217
219{
220 return !m_uuid.data[8] && !m_uuid.data[9] && !m_uuid.data[10] && !m_uuid.data[11];
221}
222
223
225{
226 return m_cached_timestamp;
227}
228
229
230size_t KIID::Hash() const
231{
232 size_t hash = 0;
233
234 // Note: this is NOT little-endian/big-endian safe, but as long as it's just used
235 // at runtime it won't matter.
236
237 for( int i = 0; i < 4; ++i )
238 boost::hash_combine( hash, reinterpret_cast<const uint32_t*>( m_uuid.data )[i] );
239
240 return hash;
241}
242
243
244void KIID::Clone( const KIID& aUUID )
245{
246 m_uuid = aUUID.m_uuid;
248}
249
250
251wxString KIID::AsString() const
252{
253 return boost::uuids::to_string( m_uuid );
254}
255
256
258{
259 return wxString::Format( "%8.8lX", (unsigned long) AsLegacyTimestamp() );
260}
261
262
264{
265 if( !IsLegacyTimestamp() )
266 return;
267
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 ).AsString() != aPath.at( i ).AsString() )
322 return false; // this path is not contained within aPath
323 }
324
325 for( size_t i = aPath.size(); i < copy.size(); ++i )
326 push_back( copy.at( i ) );
327
328 return true;
329}
330
331
332wxString KIID_PATH::AsString() const
333{
334 wxString path;
335
336 for( const KIID& pathStep : *this )
337 path += '/' + pathStep.AsString();
338
339 return path;
340}
341
342
343void to_json( nlohmann::json& aJson, const KIID& aKIID )
344{
345 aJson = aKIID.AsString().ToUTF8();
346}
347
348
349void from_json( const nlohmann::json& aJson, KIID& aKIID )
350{
351 aKIID = KIID( aJson.get<std::string>() );
352}
bool MakeRelativeTo(const KIID_PATH &aPath)
Definition: kiid.cpp:311
KIID_PATH()
Definition: kiid.h:142
wxString AsString() const
Definition: kiid.cpp:332
Definition: kiid.h:48
timestamp_t m_cached_timestamp
Definition: kiid.h:128
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:230
wxString AsString() const
Definition: kiid.cpp:251
boost::uuids::uuid m_uuid
Definition: kiid.h:126
void Increment()
Generates a deterministic replacement for a given ID.
Definition: kiid.cpp:273
wxString AsLegacyTimestampString() const
Definition: kiid.cpp:257
timestamp_t AsLegacyTimestamp() const
Definition: kiid.cpp:224
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:173
void Clone(const KIID &aUUID)
Definition: kiid.cpp:244
bool IsLegacyTimestamp() const
Definition: kiid.cpp:218
void ConvertTimestampToUuid()
Change an existing time stamp based UUID into a true UUID.
Definition: kiid.cpp:263
nlohmann::json json
Definition: gerbview.cpp:44
static void hash_combine(std::size_t &seed)
This is a dummy function to take the final case of hash_combine below.
Definition: hash.h:34
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:349
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:343
KIID niluuid(0)
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:45
Definition: bitmap.cpp:64
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200