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 <mutex>
37 
38 #include <wx/log.h>
39 
40 // boost:mt19937 is not thread-safe
41 static std::mutex rng_mutex;
42 
43 // Static rng and generators are used because the overhead of constant seeding is expensive
44 // We break out the rng separately from the generator because we want to control seeding in cases like unit tests
45 #if BOOST_VERSION >= 106700
46 static boost::uuids::detail::random_provider seeder; // required to ensure the rng has a random initial seed
47 #else
48 static boost::uuids::detail::seed_rng seeder; // required to ensure the rng has a random initial seed
49 #endif
50 static boost::mt19937 rng( seeder );
51 static boost::uuids::basic_random_generator<boost::mt19937> randomGenerator( rng );
52 
53 // These don't have the same performance penalty, but we might as well be consistent
54 static boost::uuids::string_generator stringGenerator;
55 static boost::uuids::nil_generator nilGenerator;
56 
57 
58 // Global nil reference
59 KIID niluuid( 0 );
60 
61 
62 // When true, always create nil uuids for performance, when valid ones aren't needed
63 static 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 
83  if( g_createNilUuids )
84  {
85  m_uuid = nilGenerator();
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( wxT( "A Boost UUID entropy exception was thrown in %s:%s." ),
98  __FILE__, __FUNCTION__ );
99  }
100 #endif
101 }
102 
103 
104 KIID::KIID( int null ) : m_uuid( nilGenerator() ), m_cached_timestamp( 0 )
105 {
106  wxASSERT( null == 0 );
107 }
108 
109 
110 KIID::KIID( const wxString& aString ) : m_uuid(), m_cached_timestamp( 0 )
111 {
112  if( aString.length() == 8 )
113  {
114  // A legacy-timestamp-based UUID has only the last 4 octets filled in.
115  // Convert them individually to avoid stepping in the little-endian/big-endian
116  // doo-doo.
117  for( int i = 0; i < 4; ++i )
118  {
119  wxString octet = aString.substr( i * 2, 2 );
120  m_uuid.data[i + 12] = strtol( octet.data(), nullptr, 16 );
121  }
122 
123  m_cached_timestamp = strtol( aString.c_str(), nullptr, 16 );
124  }
125  else
126  {
127  try
128  {
129  m_uuid = stringGenerator( aString.wc_str() );
130 
131  if( IsLegacyTimestamp() )
132  m_cached_timestamp = strtol( aString.substr( 28 ).c_str(), nullptr, 16 );
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( wxT( "A Boost UUID entropy exception was thrown in %s:%s." ),
150  __FILE__, __FUNCTION__ );
151  }
152 #endif
153  }
154  }
155 }
156 
157 
158 bool KIID::SniffTest( const wxString& aCandidate )
159 {
160  static wxString niluuidStr = niluuid.AsString();
161 
162  if( aCandidate.Length() != niluuidStr.Length() )
163  return false;
164 
165  for( wxChar c : aCandidate )
166  {
167  if( c >= '0' && c <= '9' )
168  continue;
169 
170  if( c >= 'a' && c <= 'f' )
171  continue;
172 
173  if( c >= 'A' && c <= 'F' )
174  continue;
175 
176  if( c == '-' )
177  continue;
178 
179  return false;
180  }
181 
182  return true;
183 }
184 
185 
186 KIID::KIID( timestamp_t aTimestamp )
187 {
188  m_cached_timestamp = aTimestamp;
189 
190  // A legacy-timestamp-based UUID has only the last 4 octets filled in.
191  // Convert them individually to avoid stepping in the little-endian/big-endian
192  // doo-doo.
193  wxString str = AsLegacyTimestampString();
194 
195  for( int i = 0; i < 4; ++i )
196  {
197  wxString octet = str.substr( i * 2, 2 );
198  m_uuid.data[i + 12] = strtol( octet.data(), nullptr, 16 );
199  }
200 }
201 
202 
204 {
205  return !m_uuid.data[8] && !m_uuid.data[9] && !m_uuid.data[10] && !m_uuid.data[11];
206 }
207 
208 
210 {
211  return m_cached_timestamp;
212 }
213 
214 
215 size_t KIID::Hash() const
216 {
217  size_t hash = 0;
218 
219  // Note: this is NOT little-endian/big-endian safe, but as long as it's just used
220  // at runtime it won't matter.
221 
222  for( int i = 0; i < 4; ++i )
223  boost::hash_combine( hash, reinterpret_cast<const uint32_t*>( m_uuid.data )[i] );
224 
225  return hash;
226 }
227 
228 
229 void KIID::Clone( const KIID& aUUID )
230 {
231  m_uuid = aUUID.m_uuid;
233 }
234 
235 
236 wxString KIID::AsString() const
237 {
238  return boost::uuids::to_string( m_uuid );
239 }
240 
241 
243 {
244  return wxString::Format( "%8.8lX", (unsigned long) AsLegacyTimestamp() );
245 }
246 
247 
249 {
250  if( !IsLegacyTimestamp() )
251  return;
252 
253  m_cached_timestamp = 0;
255 }
256 
257 
259 {
260  // This obviously destroys uniform distribution, but it can be useful when a
261  // deterministic replacement for a duplicate ID is required.
262 
263  for( int i = 15; i >= 0; --i )
264  {
265  m_uuid.data[i]++;
266 
267  if( m_uuid.data[i] != 0 )
268  break;
269  }
270 }
271 
272 
273 void KIID::CreateNilUuids( bool aNil )
274 {
275  g_createNilUuids = aNil;
276 }
277 
278 
279 void KIID::SeedGenerator( unsigned int aSeed )
280 {
281  rng.seed( aSeed );
282 }
283 
284 
285 KIID_PATH::KIID_PATH( const wxString& aString )
286 {
287  for( const wxString& pathStep : wxSplit( aString, '/' ) )
288  {
289  if( !pathStep.empty() )
290  emplace_back( KIID( pathStep ) );
291  }
292 }
293 
294 
296 {
297  KIID_PATH copy = *this;
298  clear();
299 
300  if( aPath.size() > copy.size() )
301  return false; // this path is not contained within aPath
302 
303  for( size_t i = 0; i < aPath.size(); ++i )
304  {
305  if( copy.at( i ).AsString() != aPath.at( i ).AsString() )
306  return false; // this path is not contained within aPath
307  }
308 
309  for( size_t i = aPath.size(); i < copy.size(); ++i )
310  push_back( copy.at( i ) );
311 
312  return true;
313 }
314 
315 
316 wxString KIID_PATH::AsString() const
317 {
318  wxString path;
319 
320  for( const KIID& pathStep : *this )
321  path += '/' + pathStep.AsString();
322 
323  return path;
324 }
KIID niluuid(0)
KIID()
Definition: kiid.cpp:74
wxString AsString() const
Definition: kiid.cpp:236
boost::uuids::uuid m_uuid
Definition: kiid.h:121
static boost::uuids::detail::seed_rng seeder
Definition: kiid.cpp:48
static boost::uuids::basic_random_generator< boost::mt19937 > randomGenerator(rng)
static void SeedGenerator(unsigned int aSeed)
Re-initialize the UUID generator with a given seed (for testing or QA purposes)
Definition: kiid.cpp:279
static void hash_combine(std::size_t &seed)
This is a dummy function to take the final case of hash_combine below.
Definition: hash_eda.h:67
bool IsLegacyTimestamp() const
Definition: kiid.cpp:203
timestamp_t m_cached_timestamp
Definition: kiid.h:123
static boost::uuids::nil_generator nilGenerator
Definition: kiid.cpp:55
bool MakeRelativeTo(const KIID_PATH &aPath)
Definition: kiid.cpp:295
Definition: kiid.h:44
size_t Hash() const
Definition: kiid.cpp:215
KIID_PATH()
Definition: kiid.h:137
timestamp_t AsLegacyTimestamp() const
Definition: kiid.cpp:209
static bool g_createNilUuids
Definition: kiid.cpp:63
static bool SniffTest(const wxString &aCandidate)
Returns true if a string has the correct formatting to be a KIID.
Definition: kiid.cpp:158
void ConvertTimestampToUuid()
Change an existing time stamp based UUID into a true UUID.
Definition: kiid.cpp:248
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
static std::mutex rng_mutex
Definition: kiid.cpp:41
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:32
void Clone(const KIID &aUUID)
Definition: kiid.cpp:229
void Increment()
Generates a deterministic replacement for a given ID.
Definition: kiid.cpp:258
wxString AsLegacyTimestampString() const
Definition: kiid.cpp:242
static void CreateNilUuids(bool aNil=true)
A performance optimization which disables/enables the generation of pseudo-random UUIDs.
Definition: kiid.cpp:273
wxString AsString() const
Definition: kiid.cpp:316
KIID & NilUuid()
Definition: kiid.cpp:67
static boost::mt19937 rng(seeder)
static boost::uuids::string_generator stringGenerator
Definition: kiid.cpp:54