1 #include <algorithm>
2 #include <bitset>
3 #include <set>
4 #include <sstream>
5 #include <string>
6 #include <unordered_set>
7 #include <vector>
8
9 #include "catch/catch.hpp"
10 #include "colony_list_test_helpers.h"
11 #include "flat_set.h"
12 #include "generic_factory.h"
13 #include "type_id.h"
14
15 #ifdef _MSC_VER
16 # include <intrin.h>
17
18 # define __builtin_popcount __popcnt
19 #endif
20
21 namespace
22 {
23 struct test_obj;
24
25 using test_obj_id = string_id<test_obj>;
26
27 struct test_obj {
28 test_obj_id id;
29 std::string value;
30 };
31
32 } // namespace
33
34 TEST_CASE( "generic_factory_insert_convert_valid", "[generic_factory]" )
35 {
36 test_obj_id id_0( "id_0" );
37 test_obj_id id_1( "id_1" );
38 test_obj_id id_2( "id_2" );
39
40 generic_factory<test_obj> test_factory( "test_factory" );
41
42 REQUIRE_FALSE( test_factory.is_valid( id_0 ) );
43 REQUIRE_FALSE( test_factory.is_valid( id_1 ) );
44 REQUIRE_FALSE( test_factory.is_valid( id_2 ) );
45
46 test_factory.insert( {test_obj_id( "id_0" ), "value_0"} );
47 test_factory.insert( {test_obj_id( "id_1" ), "value_1"} );
48 test_factory.insert( {test_obj_id( "id_2" ), "value_2"} );
49
50 // testing correctness when finalized was both called and not called
51 if( GENERATE( false, true ) ) {
52 INFO( "Calling finalize" );
53 test_factory.finalize();
54 }
55
56 CHECK( test_factory.is_valid( id_0 ) );
57 CHECK( test_factory.is_valid( id_1 ) );
58 CHECK( test_factory.is_valid( id_2 ) );
59 CHECK( test_factory.size() == 3 );
60 CHECK_FALSE( test_factory.empty() );
61
62 CHECK_FALSE( test_factory.is_valid( test_obj_id( "non_existent_id" ) ) );
63
64 int_id<test_obj> int_id_1 = test_factory.convert( test_obj_id( "id_1" ), int_id<test_obj>( -1 ) );
65 CHECK( int_id_1.to_i() == 1 );
66
67 CHECK( test_factory.convert( int_id_1 ) == id_1 );
68 CHECK( test_factory.convert( int_id_1 ) == test_obj_id( "id_1" ) );
69
70 CHECK( test_factory.obj( id_0 ).value == "value_0" );
71 CHECK( test_factory.obj( id_1 ).value == "value_1" );
72 CHECK( test_factory.obj( id_2 ).value == "value_2" );
73 CHECK( test_factory.obj( int_id_1 ).value == "value_1" );
74
75 test_factory.reset();
76 // factory is be empty, all ids must be invalid
77 CHECK( test_factory.empty() );
78 CHECK( test_factory.size() == 0 ); // NOLINT
79
80 // technically, lookup by non-valid int_id may result undefined behavior, if factory is non-empty
81 // this is expected
82 REQUIRE_FALSE( test_factory.is_valid( int_id_1 ) );
83 REQUIRE_FALSE( test_factory.is_valid( id_0 ) );
84 REQUIRE_FALSE( test_factory.is_valid( id_1 ) );
85 REQUIRE_FALSE( test_factory.is_valid( id_2 ) );
86 }
87
88 TEST_CASE( "generic_factory_repeated_overwrite", "[generic_factory]" )
89 {
90 test_obj_id id_1( "id_1" );
91 generic_factory<test_obj> test_factory( "test_factory" );
92 REQUIRE_FALSE( test_factory.is_valid( id_1 ) );
93
94 test_factory.insert( { test_obj_id( "id_1" ), "1" } );
95 CHECK( test_factory.is_valid( id_1 ) );
96 CHECK( test_factory.obj( id_1 ).value == "1" );
97
98 test_factory.insert( { test_obj_id( "id_1" ), "2" } );
99 CHECK( test_factory.is_valid( id_1 ) );
100 CHECK( test_factory.obj( id_1 ).value == "2" );
101 }
102
103 TEST_CASE( "generic_factory_repeated_invalidation", "[generic_factory]" )
104 {
105 // if id is static, factory must be static (or singleton by other means)
106 static test_obj_id id_1( "id_1" );
107 static generic_factory<test_obj> test_factory( "test_factory" );
108
109 for( int i = 0; i < 10; i++ ) {
110 INFO( "iteration: " << i );
111 test_factory.reset();
112 REQUIRE_FALSE( test_factory.is_valid( id_1 ) );
113 std::string value = "value_" + std::to_string( i );
114 test_factory.insert( { test_obj_id( "id_1" ), value } );
115 CHECK( test_factory.is_valid( id_1 ) );
116 CHECK( test_factory.obj( id_1 ).value == value );
117 }
118 }
119
120 TEST_CASE( "generic_factory_common_null_ids", "[generic_factory]" )
121 {
122 CHECK( itype_id::NULL_ID().is_null() );
123 CHECK( itype_id::NULL_ID().is_valid() );
124
125 CHECK( field_type_str_id::NULL_ID().is_null() );
126 CHECK( field_type_str_id::NULL_ID().is_valid() );
127 }
128
129 TEST_CASE( "generic_factory_version_wrapper", "[generic_factory]" )
130 {
131 generic_factory<test_obj> test_factory( "test_factory" );
132 generic_factory<test_obj>::Version v1;
133 generic_factory<test_obj>::Version v2;
134
135 CHECK_FALSE( test_factory.is_valid( v1 ) );
136 test_factory.reset();
137 CHECK_FALSE( test_factory.is_valid( v1 ) );
138
139 v1 = test_factory.get_version();
140
141 CHECK( test_factory.is_valid( v1 ) );
142 CHECK_FALSE( v1 == v2 );
143 CHECK( v1 != v2 );
144
145 v2 = v1;
146
147 CHECK( v1 == v2 );
148 CHECK_FALSE( v1 != v2 );
149
150 test_factory.reset();
151 CHECK_FALSE( test_factory.is_valid( v1 ) );
152 CHECK_FALSE( test_factory.is_valid( v2 ) );
153 }
154
155 TEST_CASE( "string_ids_comparison", "[generic_factory][string_id]" )
156 {
157 // checks equality correctness for the following combinations of parameters:
158 bool equal = GENERATE( true, false ); // whether ids are equal
159 bool first_cached = GENERATE( true, false ); // whether _version is current (first id)
160 bool first_valid = GENERATE( true, false ); // whether id is present in the factory (first id)
161 bool second_cached = GENERATE( true, false ); // --- second id
162 bool second_valid = GENERATE( true, false ); // --- second id
163
164 test_obj_id id1( "id1" );
165 test_obj_id id2( ( equal ? "id1" : "id2" ) );
166
167 generic_factory<test_obj> test_factory( "test_factory" );
168
169 // both ids must be inserted first and then cached for the test to be valid
170 // as `insert` invalidates the cache
171 if( first_valid ) {
172 test_factory.insert( { id1, "value" } );
173 }
174 if( second_valid ) {
175 test_factory.insert( { id2, "value" } );
176 }
177 if( first_cached ) {
178 // is_valid should update cache internally
179 test_factory.is_valid( id1 );
180 }
181 if( second_cached ) {
182 test_factory.is_valid( id2 );
183 }
184
__anond803dce90202( bool cached, bool valid ) 185 const auto id_info = []( bool cached, bool valid ) {
186 std::ostringstream ret;
187 ret << "cached_" << cached << "__" "valid_" << valid;
188 return ret.str();
189 };
190
191 DYNAMIC_SECTION( ( equal ? "equal" : "not_equal" ) << "___" <<
192 "first_" << id_info( first_cached, first_valid ) << "___"
193 "second_" << id_info( second_cached, second_valid )
194 ) {
195 if( equal ) {
196 CHECK( id1 == id2 );
197 } else {
198 CHECK_FALSE( id1 == id2 );
199 }
200 }
201 }
202
203 // Benchmarks are skipped by default by using [.] tag
204 TEST_CASE( "generic_factory_lookup_benchmark", "[.][generic_factory][benchmark]" )
205 {
206 test_obj_id id_200( "id_200" );
207
208 generic_factory<test_obj> test_factory( "test_factory" );
209
210 for( int i = 0; i < 1000; ++i ) {
211 std::string id = "id_" + std::to_string( i );
212 std::string value = "value_" + std::to_string( i );
213 test_factory.insert( {test_obj_id( id ), value} );
214 }
215
216 BENCHMARK( "single lookup" ) {
217 return test_factory.obj( id_200 ).value;
218 };
219 }
220
221 TEST_CASE( "string_id_compare_benchmark", "[.][generic_factory][string_id][benchmark]" )
222 {
223 std::string prefix;
224 SECTION( "short id" ) {
225 }
226 SECTION( "long id" ) {
227 prefix = "log_common_prefix_";
228 }
229
230 test_obj_id id_200( prefix + "id_200" );
231 test_obj_id id_200_( prefix + "id_200" );
232 test_obj_id id_300( prefix + "id_300" );
233
234 generic_factory<test_obj> test_factory( "test_factory" );
235
236 CHECK( id_200 == id_200_ );
237 BENCHMARK( "ids are equal, invalid version" ) {
238 return id_200 == id_200_;
239 };
240
241 CHECK_FALSE( id_200 == id_300 );
242 BENCHMARK( "ids are not equal, invalid version" ) {
243 return id_200 == id_300;
244 };
245
246 test_factory.insert( {test_obj_id( id_200 ), "value_200"} );
247 test_factory.insert( {test_obj_id( id_200_ ), "value_200_"} );
248 test_factory.insert( {test_obj_id( id_300 ), "value_300"} );
249 // make _version inside the ids valid
250 test_factory.is_valid( id_200 );
251 test_factory.is_valid( id_200_ );
252 test_factory.is_valid( id_300 );
253
254 CHECK( id_200 == id_200_ );
255 BENCHMARK( "ids are equal, valid version" ) {
256 return id_200 == id_200_;
257 };
258
259 CHECK_FALSE( id_200 == id_300 );
260 BENCHMARK( "ids are not equal, valid version" ) {
261 return id_200 == id_300;
262 };
263 }
264
265 namespace
266 {
267 struct dyn_test_obj {};
268 using dyn_str_id = string_id<dyn_test_obj>;
269
270 struct stat_test_obj {
271 string_id<stat_test_obj> id;
272 bool was_loaded = false;
273 };
274 using stat_str_id = string_id<stat_test_obj>;
275 using stat_int_id = int_id<stat_test_obj>;
276 int_id<stat_test_obj> stat_int_id_null( -1 );
277
278 generic_factory<stat_test_obj> stat_test_obj_factory( "stat_test_obj" );
279 } // namespace
280
281 // standard "generic_factory" methods to support the benchmark below
id() const282 template<> int_id<stat_test_obj> string_id<stat_test_obj>::id() const
283 {
284 return stat_test_obj_factory.convert( *this, stat_int_id_null );
285 }
int_id(const string_id<stat_test_obj> & id)286 template<> int_id<stat_test_obj>::int_id( const string_id<stat_test_obj> &id ) : _id( id.id() ) {}
obj() const287 template<> const stat_test_obj &string_id<stat_test_obj>::obj() const
288 {
289 return stat_test_obj_factory.obj( *this );
290 }
291
292 // mark string_id<dyn_test_obj> as dynamic/non-interned
293 template<> struct string_id_params<dyn_test_obj> {
294 static constexpr bool dynamic = true;
295 };
296
297 // compares the lookup performance of different flag container implementations
298 TEST_CASE( "string_and_int_ids_benchmark", "[.][generic_factory][int_id][string_id][benchmark]" )
299 {
300 stat_test_obj_factory.reset();
301 for( int i = 0; i < 1000; i ++ ) {
302 stat_test_obj_factory.insert( {
303 string_id<stat_test_obj>( "stat_test_id_" + std::to_string( i ) )
304 } );
305 }
306
307 static constexpr int bit_flags_size = 100;
308 static constexpr int bloom_size = 64;
309
310 INFO( "bloom_size must be a power of two" );
311 REQUIRE( __builtin_popcount( bloom_size ) == 1 );
312
313 const unsigned int flags_in_item = GENERATE( 2, 8, 32, 128 );
314
315 struct fake_item {
316 int dummy;
317 std::bitset<bit_flags_size> bit_flags;
318 std::set<stat_str_id> std_set_string_ids;
319 cata::flat_set<stat_str_id> flat_set_string_ids;
320 std::unordered_set<stat_str_id> uo_set_string_ids;
321 std::set<dyn_str_id> std_set_dyn_string_ids;
322 cata::flat_set<dyn_str_id> flat_set_dyn_string_ids;
323 std::unordered_set<dyn_str_id> uo_set_dyn_string_ids;
324 std::bitset<bloom_size> bloom;
325 std::set<stat_int_id> std_set_int_ids;
326 std::unordered_set<stat_int_id> std_uo_set_int_ids;
327 std::set<std::string> std_set_std_strings;
328 cata::flat_set<std::string> flat_set_std_strings;
329 cata::flat_set<stat_int_id> flat_set_int_ids;
330 std::vector<stat_int_id> vector_int_ids;
331
set_flagfake_item332 void set_flag( const stat_str_id &flag ) {
333 const auto int_id = flag.id();
334 const int i = int_id.to_i();
335 bit_flags[i % bit_flags_size] = true;
336 bloom[i % bloom_size] = true;
337 flat_set_string_ids.insert( flag );
338 std_set_string_ids.insert( flag );
339 uo_set_string_ids.insert( flag );
340 std_set_dyn_string_ids.insert( dyn_str_id( flag.str() ) );
341 flat_set_dyn_string_ids.insert( dyn_str_id( flag.str() ) );
342 uo_set_dyn_string_ids.insert( dyn_str_id( flag.str() ) );
343 std_set_std_strings.emplace( flag.str() );
344 flat_set_std_strings.insert( flag.str() );
345 flat_set_int_ids.insert( int_id );
346 std_set_int_ids.emplace( int_id );
347 std_uo_set_int_ids.emplace( int_id );
348 // do not add duplicates
349 if( std_uo_set_int_ids.size() > vector_int_ids.size() ) {
350 vector_int_ids.push_back( flag );
351 }
352 }
353 } item;
354
355 const auto &all_flags = stat_test_obj_factory.get_all();
356 const int all_flags_n = static_cast<int>( all_flags.size() );
357 REQUIRE( all_flags_n >= 10 );
358
359 for( const auto &f : all_flags ) {
360 if( xor_rand() % all_flags_n <= flags_in_item ) {
361 item.set_flag( f.id );
362 }
363 }
364 while( item.std_set_string_ids.size() < flags_in_item ) {
365 item.set_flag( all_flags[xor_rand() % all_flags_n].id );
366 }
367
368 std::vector<stat_str_id> test_flags;
369 bool hits = GENERATE( false, true );
370 if( hits ) {
371 // populate only with flags that exist in the item
372 for( const auto &f : item.std_set_string_ids ) {
373 test_flags.push_back( f );
374 }
375 } else {
376 // populate with random flags
377 for( int i = 0; i < 20; i++ ) {
378 test_flags.push_back( all_flags[xor_rand() % all_flags_n].id );
379 }
380 }
381 const int test_flags_size = test_flags.size();
382 std::vector<dyn_str_id > test_dyn_str_ids;
383 for( const auto &f : test_flags ) {
384 test_dyn_str_ids.push_back( dyn_str_id( f.str() ) );
385 }
386
387 DYNAMIC_SECTION( "number_ids_in_collection: " << flags_in_item << "; only_hits: " << hits ) {
388 }
389
390 int i = 0;
391
392 BENCHMARK( "baseline: string_id access" ) {
393 return test_flags[( i++ ) % test_flags_size].str().size();
394 };
395
396 BENCHMARK( "baseline: string_id::obj()" ) {
397 return test_flags[0].obj().was_loaded;
398 };
399
400 BENCHMARK( "baseline: string_id -> int_id" ) {
401 return test_flags[0].id().to_i();
402 };
403
404 BENCHMARK( "\"enum\" bitset" ) {
405 return !!item.bit_flags[( i++ ) % bit_flags_size];
406 };
407
408 BENCHMARK( "std::set<std::string>" ) {
409 return item.std_set_std_strings.count( test_flags[( i++ ) % test_flags_size].str() );
410 };
411
412 BENCHMARK( "flat_set<std::string>" ) {
413 return item.flat_set_std_strings.count( test_flags[( i++ ) % test_flags_size].str() );
414 };
415
416 BENCHMARK( "flat_set<string_id>" ) {
417 return item.flat_set_string_ids.count( test_flags[( i++ ) % test_flags_size] );
418 };
419
420 BENCHMARK( "std::set<string_id>" ) {
421 return item.std_set_string_ids.count( test_flags[( i++ ) % test_flags_size] );
422 };
423
424 BENCHMARK( "std::unordered_set<string_id>" ) {
425 return item.uo_set_string_ids.count( test_flags[( i++ ) % test_flags_size] );
426 };
427
428 BENCHMARK( "flat_set<dyn_string_id>" ) {
429 return item.flat_set_dyn_string_ids.count( test_dyn_str_ids[( i++ ) % test_flags_size] );
430 };
431
432 BENCHMARK( "std::set<dyn_string_id>" ) {
433 return item.std_set_dyn_string_ids.count( test_dyn_str_ids[( i++ ) % test_flags_size] );
434 };
435
436 BENCHMARK( "std::unordered_set<dyn_string_id>" ) {
437 return item.uo_set_dyn_string_ids.count( test_dyn_str_ids[( i++ ) % test_flags_size] );
438 };
439
440 BENCHMARK( "flat_set<int_id>" ) {
441 return item.flat_set_int_ids.count( test_flags[( i++ ) % test_flags_size] );
442 };
443
444 BENCHMARK( "std::set<int_id>" ) {
445 return item.std_set_int_ids.count( test_flags[( i++ ) % test_flags_size] );
446 };
447
448 BENCHMARK( "std::unordered_set<int_id>" ) {
449 return item.std_uo_set_int_ids.count( test_flags[( i++ ) % test_flags_size] );
450 };
451
452 BENCHMARK( "std::vector<int_id>" ) {
453 const std::vector<stat_int_id> &v = item.vector_int_ids;
454 return std::find( v.begin(), v.end(), test_flags[( i++ ) % test_flags_size] ) != v.end();
455 };
456 }
457