1 /*
2 * Copyright © 2020 Google, Inc.
3 *
4 * This is part of HarfBuzz, a text shaping library.
5 *
6 * Permission is hereby granted, without written agreement and without
7 * license or royalty fees, to use, copy, modify, and distribute this
8 * software and its documentation for any purpose, provided that the
9 * above copyright notice and the following two paragraphs appear in
10 * all copies of this software.
11 *
12 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
13 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
14 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
15 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
16 * DAMAGE.
17 *
18 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
19 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
20 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
21 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
22 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
23 *
24 * Google Author(s): Garret Rieger
25 */
26
27 #include <string>
28
29 #include "hb-repacker.hh"
30 #include "hb-open-type.hh"
31
start_object(const char * tag,unsigned len,hb_serialize_context_t * c)32 static void start_object(const char* tag,
33 unsigned len,
34 hb_serialize_context_t* c)
35 {
36 c->push ();
37 char* obj = c->allocate_size<char> (len);
38 strncpy (obj, tag, len);
39 }
40
41
add_object(const char * tag,unsigned len,hb_serialize_context_t * c)42 static unsigned add_object(const char* tag,
43 unsigned len,
44 hb_serialize_context_t* c)
45 {
46 start_object (tag, len, c);
47 return c->pop_pack (false);
48 }
49
50
add_offset(unsigned id,hb_serialize_context_t * c)51 static void add_offset (unsigned id,
52 hb_serialize_context_t* c)
53 {
54 OT::Offset16* offset = c->start_embed<OT::Offset16> ();
55 c->extend_min (offset);
56 c->add_link (*offset, id);
57 }
58
add_wide_offset(unsigned id,hb_serialize_context_t * c)59 static void add_wide_offset (unsigned id,
60 hb_serialize_context_t* c)
61 {
62 OT::Offset32* offset = c->start_embed<OT::Offset32> ();
63 c->extend_min (offset);
64 c->add_link (*offset, id);
65 }
66
run_resolve_overflow_test(const char * name,hb_serialize_context_t & overflowing,hb_serialize_context_t & expected,unsigned num_iterations=0)67 static void run_resolve_overflow_test (const char* name,
68 hb_serialize_context_t& overflowing,
69 hb_serialize_context_t& expected,
70 unsigned num_iterations = 0)
71 {
72 printf (">>> Testing overflowing resolution for %s\n",
73 name);
74
75 graph_t graph (overflowing.object_graph ());
76
77
78 assert (overflowing.offset_overflow ());
79 hb_blob_t* out = hb_resolve_overflows (overflowing.object_graph (),
80 HB_TAG ('G', 'S', 'U', 'B'), num_iterations);
81 assert (out);
82
83 hb_bytes_t result = out->as_bytes ();
84
85 assert (!expected.offset_overflow ());
86 hb_bytes_t expected_result = expected.copy_bytes ();
87
88 assert (result.length == expected_result.length);
89 for (unsigned i = 0; i < expected_result.length; i++)
90 {
91 assert (result[i] == expected_result[i]);
92 }
93
94 expected_result.fini ();
95 hb_blob_destroy (out);
96 }
97
add_virtual_offset(unsigned id,hb_serialize_context_t * c)98 static void add_virtual_offset (unsigned id,
99 hb_serialize_context_t* c)
100 {
101 c->add_virtual_link (id);
102 }
103
104 static void
populate_serializer_simple(hb_serialize_context_t * c)105 populate_serializer_simple (hb_serialize_context_t* c)
106 {
107 c->start_serialize<char> ();
108
109 unsigned obj_1 = add_object ("ghi", 3, c);
110 unsigned obj_2 = add_object ("def", 3, c);
111
112 start_object ("abc", 3, c);
113 add_offset (obj_2, c);
114 add_offset (obj_1, c);
115 c->pop_pack (false);
116
117 c->end_serialize();
118 }
119
120 static void
populate_serializer_with_overflow(hb_serialize_context_t * c)121 populate_serializer_with_overflow (hb_serialize_context_t* c)
122 {
123 std::string large_string(50000, 'a');
124 c->start_serialize<char> ();
125
126 unsigned obj_1 = add_object (large_string.c_str(), 10000, c);
127 unsigned obj_2 = add_object (large_string.c_str(), 20000, c);
128 unsigned obj_3 = add_object (large_string.c_str(), 50000, c);
129
130 start_object ("abc", 3, c);
131 add_offset (obj_3, c);
132 add_offset (obj_2, c);
133 add_offset (obj_1, c);
134 c->pop_pack (false);
135
136 c->end_serialize();
137 }
138
139 static void
populate_serializer_with_priority_overflow(hb_serialize_context_t * c)140 populate_serializer_with_priority_overflow (hb_serialize_context_t* c)
141 {
142 std::string large_string(50000, 'a');
143 c->start_serialize<char> ();
144
145 unsigned obj_e = add_object ("e", 1, c);
146 unsigned obj_d = add_object ("d", 1, c);
147
148 start_object (large_string.c_str (), 50000, c);
149 add_offset (obj_e, c);
150 unsigned obj_c = c->pop_pack (false);
151
152 start_object (large_string.c_str (), 20000, c);
153 add_offset (obj_d, c);
154 unsigned obj_b = c->pop_pack (false);
155
156 start_object ("a", 1, c);
157 add_offset (obj_b, c);
158 add_offset (obj_c, c);
159 c->pop_pack (false);
160
161 c->end_serialize();
162 }
163
164 static void
populate_serializer_with_priority_overflow_expected(hb_serialize_context_t * c)165 populate_serializer_with_priority_overflow_expected (hb_serialize_context_t* c)
166 {
167 std::string large_string(50000, 'a');
168 c->start_serialize<char> ();
169
170 unsigned obj_e = add_object ("e", 1, c);
171
172 start_object (large_string.c_str (), 50000, c);
173 add_offset (obj_e, c);
174 unsigned obj_c = c->pop_pack (false);
175
176 unsigned obj_d = add_object ("d", 1, c);
177
178 start_object (large_string.c_str (), 20000, c);
179 add_offset (obj_d, c);
180 unsigned obj_b = c->pop_pack (false);
181
182 start_object ("a", 1, c);
183 add_offset (obj_b, c);
184 add_offset (obj_c, c);
185 c->pop_pack (false);
186
187 c->end_serialize();
188 }
189
190
191 static void
populate_serializer_with_dedup_overflow(hb_serialize_context_t * c)192 populate_serializer_with_dedup_overflow (hb_serialize_context_t* c)
193 {
194 std::string large_string(70000, 'a');
195 c->start_serialize<char> ();
196
197 unsigned obj_1 = add_object ("def", 3, c);
198
199 start_object (large_string.c_str(), 60000, c);
200 add_offset (obj_1, c);
201 unsigned obj_2 = c->pop_pack (false);
202
203 start_object (large_string.c_str(), 10000, c);
204 add_offset (obj_2, c);
205 add_offset (obj_1, c);
206 c->pop_pack (false);
207
208 c->end_serialize();
209 }
210
211 static void
populate_serializer_with_isolation_overflow(hb_serialize_context_t * c)212 populate_serializer_with_isolation_overflow (hb_serialize_context_t* c)
213 {
214 std::string large_string(70000, 'a');
215 c->start_serialize<char> ();
216
217 unsigned obj_4 = add_object ("4", 1, c);
218
219 start_object (large_string.c_str(), 60000, c);
220 add_offset (obj_4, c);
221 unsigned obj_3 = c->pop_pack (false);
222
223 start_object (large_string.c_str(), 10000, c);
224 add_offset (obj_4, c);
225 unsigned obj_2 = c->pop_pack (false);
226
227 start_object ("1", 1, c);
228 add_wide_offset (obj_3, c);
229 add_offset (obj_2, c);
230 c->pop_pack (false);
231
232 c->end_serialize();
233 }
234
235 static void
populate_serializer_with_isolation_overflow_complex(hb_serialize_context_t * c)236 populate_serializer_with_isolation_overflow_complex (hb_serialize_context_t* c)
237 {
238 std::string large_string(70000, 'a');
239 c->start_serialize<char> ();
240
241 unsigned obj_f = add_object ("f", 1, c);
242
243 start_object ("e", 1, c);
244 add_offset (obj_f, c);
245 unsigned obj_e = c->pop_pack (false);
246
247 start_object ("c", 1, c);
248 add_offset (obj_e, c);
249 unsigned obj_c = c->pop_pack (false);
250
251 start_object ("d", 1, c);
252 add_offset (obj_e, c);
253 unsigned obj_d = c->pop_pack (false);
254
255 start_object (large_string.c_str(), 60000, c);
256 add_offset (obj_d, c);
257 unsigned obj_h = c->pop_pack (false);
258
259 start_object (large_string.c_str(), 60000, c);
260 add_offset (obj_c, c);
261 add_offset (obj_h, c);
262 unsigned obj_b = c->pop_pack (false);
263
264 start_object (large_string.c_str(), 10000, c);
265 add_offset (obj_d, c);
266 unsigned obj_g = c->pop_pack (false);
267
268 start_object (large_string.c_str(), 11000, c);
269 add_offset (obj_d, c);
270 unsigned obj_i = c->pop_pack (false);
271
272 start_object ("a", 1, c);
273 add_wide_offset (obj_b, c);
274 add_offset (obj_g, c);
275 add_offset (obj_i, c);
276 c->pop_pack (false);
277
278 c->end_serialize();
279 }
280
281 static void
populate_serializer_with_isolation_overflow_complex_expected(hb_serialize_context_t * c)282 populate_serializer_with_isolation_overflow_complex_expected (hb_serialize_context_t* c)
283 {
284 std::string large_string(70000, 'a');
285 c->start_serialize<char> ();
286
287
288 // space 1
289
290 unsigned obj_f_prime = add_object ("f", 1, c);
291
292 start_object ("e", 1, c);
293 add_offset (obj_f_prime, c);
294 unsigned obj_e_prime = c->pop_pack (false);
295
296 start_object ("d", 1, c);
297 add_offset (obj_e_prime, c);
298 unsigned obj_d_prime = c->pop_pack (false);
299
300 start_object (large_string.c_str(), 60000, c);
301 add_offset (obj_d_prime, c);
302 unsigned obj_h = c->pop_pack (false);
303
304 start_object ("c", 1, c);
305 add_offset (obj_e_prime, c);
306 unsigned obj_c = c->pop_pack (false);
307
308 start_object (large_string.c_str(), 60000, c);
309 add_offset (obj_c, c);
310 add_offset (obj_h, c);
311 unsigned obj_b = c->pop_pack (false);
312
313 // space 0
314
315 unsigned obj_f = add_object ("f", 1, c);
316
317 start_object ("e", 1, c);
318 add_offset (obj_f, c);
319 unsigned obj_e = c->pop_pack (false);
320
321
322 start_object ("d", 1, c);
323 add_offset (obj_e, c);
324 unsigned obj_d = c->pop_pack (false);
325
326 start_object (large_string.c_str(), 11000, c);
327 add_offset (obj_d, c);
328 unsigned obj_i = c->pop_pack (false);
329
330 start_object (large_string.c_str(), 10000, c);
331 add_offset (obj_d, c);
332 unsigned obj_g = c->pop_pack (false);
333
334 start_object ("a", 1, c);
335 add_wide_offset (obj_b, c);
336 add_offset (obj_g, c);
337 add_offset (obj_i, c);
338 c->pop_pack (false);
339
340 c->end_serialize();
341 }
342
343 static void
populate_serializer_with_isolation_overflow_spaces(hb_serialize_context_t * c)344 populate_serializer_with_isolation_overflow_spaces (hb_serialize_context_t* c)
345 {
346 std::string large_string(70000, 'a');
347 c->start_serialize<char> ();
348
349 unsigned obj_d = add_object ("f", 1, c);
350 unsigned obj_e = add_object ("f", 1, c);
351
352 start_object (large_string.c_str(), 60000, c);
353 add_offset (obj_d, c);
354 unsigned obj_b = c->pop_pack ();
355
356 start_object (large_string.c_str(), 60000, c);
357 add_offset (obj_e, c);
358 unsigned obj_c = c->pop_pack ();
359
360
361 start_object ("a", 1, c);
362 add_wide_offset (obj_b, c);
363 add_wide_offset (obj_c, c);
364 c->pop_pack ();
365
366 c->end_serialize();
367 }
368
369 static void
populate_serializer_spaces(hb_serialize_context_t * c,bool with_overflow)370 populate_serializer_spaces (hb_serialize_context_t* c, bool with_overflow)
371 {
372 std::string large_string(70000, 'a');
373 c->start_serialize<char> ();
374
375 unsigned obj_i;
376
377 if (with_overflow)
378 obj_i = add_object ("i", 1, c);
379
380 // Space 2
381 unsigned obj_h = add_object ("h", 1, c);
382
383 start_object (large_string.c_str(), 30000, c);
384 add_offset (obj_h, c);
385 unsigned obj_e = c->pop_pack (false);
386
387 start_object ("b", 1, c);
388 add_offset (obj_e, c);
389 unsigned obj_b = c->pop_pack (false);
390
391 // Space 1
392 if (!with_overflow)
393 obj_i = add_object ("i", 1, c);
394
395 start_object (large_string.c_str(), 30000, c);
396 add_offset (obj_i, c);
397 unsigned obj_g = c->pop_pack (false);
398
399 start_object (large_string.c_str(), 30000, c);
400 add_offset (obj_i, c);
401 unsigned obj_f = c->pop_pack (false);
402
403 start_object ("d", 1, c);
404 add_offset (obj_g, c);
405 unsigned obj_d = c->pop_pack (false);
406
407 start_object ("c", 1, c);
408 add_offset (obj_f, c);
409 unsigned obj_c = c->pop_pack (false);
410
411 start_object ("a", 1, c);
412 add_wide_offset (obj_b, c);
413 add_wide_offset (obj_c, c);
414 add_wide_offset (obj_d, c);
415 c->pop_pack (false);
416
417 c->end_serialize();
418 }
419
420 static void
populate_serializer_spaces_16bit_connection(hb_serialize_context_t * c)421 populate_serializer_spaces_16bit_connection (hb_serialize_context_t* c)
422 {
423 std::string large_string(70000, 'a');
424 c->start_serialize<char> ();
425
426 unsigned obj_g = add_object ("g", 1, c);
427 unsigned obj_h = add_object ("h", 1, c);
428
429 start_object (large_string.c_str (), 40000, c);
430 add_offset (obj_g, c);
431 unsigned obj_e = c->pop_pack (false);
432
433 start_object (large_string.c_str (), 40000, c);
434 add_offset (obj_h, c);
435 unsigned obj_f = c->pop_pack (false);
436
437 start_object ("c", 1, c);
438 add_offset (obj_e, c);
439 unsigned obj_c = c->pop_pack (false);
440
441 start_object ("d", 1, c);
442 add_offset (obj_f, c);
443 unsigned obj_d = c->pop_pack (false);
444
445 start_object ("b", 1, c);
446 add_offset (obj_e, c);
447 add_offset (obj_h, c);
448 unsigned obj_b = c->pop_pack (false);
449
450 start_object ("a", 1, c);
451 add_offset (obj_b, c);
452 add_wide_offset (obj_c, c);
453 add_wide_offset (obj_d, c);
454 c->pop_pack (false);
455
456 c->end_serialize();
457 }
458
459 static void
populate_serializer_spaces_16bit_connection_expected(hb_serialize_context_t * c)460 populate_serializer_spaces_16bit_connection_expected (hb_serialize_context_t* c)
461 {
462 std::string large_string(70000, 'a');
463 c->start_serialize<char> ();
464
465 unsigned obj_g_prime = add_object ("g", 1, c);
466
467 start_object (large_string.c_str (), 40000, c);
468 add_offset (obj_g_prime, c);
469 unsigned obj_e_prime = c->pop_pack (false);
470
471 start_object ("c", 1, c);
472 add_offset (obj_e_prime, c);
473 unsigned obj_c = c->pop_pack (false);
474
475 unsigned obj_h_prime = add_object ("h", 1, c);
476
477 start_object (large_string.c_str (), 40000, c);
478 add_offset (obj_h_prime, c);
479 unsigned obj_f = c->pop_pack (false);
480
481 start_object ("d", 1, c);
482 add_offset (obj_f, c);
483 unsigned obj_d = c->pop_pack (false);
484
485 unsigned obj_g = add_object ("g", 1, c);
486
487 start_object (large_string.c_str (), 40000, c);
488 add_offset (obj_g, c);
489 unsigned obj_e = c->pop_pack (false);
490
491 unsigned obj_h = add_object ("h", 1, c);
492
493 start_object ("b", 1, c);
494 add_offset (obj_e, c);
495 add_offset (obj_h, c);
496 unsigned obj_b = c->pop_pack (false);
497
498 start_object ("a", 1, c);
499 add_offset (obj_b, c);
500 add_wide_offset (obj_c, c);
501 add_wide_offset (obj_d, c);
502 c->pop_pack (false);
503
504 c->end_serialize ();
505 }
506
507 static void
populate_serializer_short_and_wide_subgraph_root(hb_serialize_context_t * c)508 populate_serializer_short_and_wide_subgraph_root (hb_serialize_context_t* c)
509 {
510 std::string large_string(70000, 'a');
511 c->start_serialize<char> ();
512
513 unsigned obj_e = add_object ("e", 1, c);
514
515 start_object (large_string.c_str (), 40000, c);
516 add_offset (obj_e, c);
517 unsigned obj_c = c->pop_pack (false);
518
519 start_object (large_string.c_str (), 40000, c);
520 add_offset (obj_c, c);
521 unsigned obj_d = c->pop_pack (false);
522
523 start_object ("b", 1, c);
524 add_offset (obj_c, c);
525 add_offset (obj_e, c);
526 unsigned obj_b = c->pop_pack (false);
527
528 start_object ("a", 1, c);
529 add_offset (obj_b, c);
530 add_wide_offset (obj_c, c);
531 add_wide_offset (obj_d, c);
532 c->pop_pack (false);
533
534 c->end_serialize();
535 }
536
537 static void
populate_serializer_short_and_wide_subgraph_root_expected(hb_serialize_context_t * c)538 populate_serializer_short_and_wide_subgraph_root_expected (hb_serialize_context_t* c)
539 {
540 std::string large_string(70000, 'a');
541 c->start_serialize<char> ();
542
543 unsigned obj_e_prime = add_object ("e", 1, c);
544
545 start_object (large_string.c_str (), 40000, c);
546 add_offset (obj_e_prime, c);
547 unsigned obj_c_prime = c->pop_pack (false);
548
549 start_object (large_string.c_str (), 40000, c);
550 add_offset (obj_c_prime, c);
551 unsigned obj_d = c->pop_pack (false);
552
553 unsigned obj_e = add_object ("e", 1, c);
554
555 start_object (large_string.c_str (), 40000, c);
556 add_offset (obj_e, c);
557 unsigned obj_c = c->pop_pack (false);
558
559
560 start_object ("b", 1, c);
561 add_offset (obj_c, c);
562 add_offset (obj_e, c);
563 unsigned obj_b = c->pop_pack (false);
564
565 start_object ("a", 1, c);
566 add_offset (obj_b, c);
567 add_wide_offset (obj_c_prime, c);
568 add_wide_offset (obj_d, c);
569 c->pop_pack (false);
570
571 c->end_serialize();
572 }
573
574 static void
populate_serializer_with_split_spaces(hb_serialize_context_t * c)575 populate_serializer_with_split_spaces (hb_serialize_context_t* c)
576 {
577 // Overflow needs to be resolved by splitting the single space
578 std::string large_string(70000, 'a');
579 c->start_serialize<char> ();
580
581 unsigned obj_f = add_object ("f", 1, c);
582
583 start_object (large_string.c_str(), 40000, c);
584 add_offset (obj_f, c);
585 unsigned obj_d = c->pop_pack (false);
586
587 start_object (large_string.c_str(), 40000, c);
588 add_offset (obj_f, c);
589 unsigned obj_e = c->pop_pack (false);
590
591 start_object ("b", 1, c);
592 add_offset (obj_d, c);
593 unsigned obj_b = c->pop_pack (false);
594
595 start_object ("c", 1, c);
596 add_offset (obj_e, c);
597 unsigned obj_c = c->pop_pack (false);
598
599 start_object ("a", 1, c);
600 add_wide_offset (obj_b, c);
601 add_wide_offset (obj_c, c);
602 c->pop_pack (false);
603
604 c->end_serialize();
605 }
606
607 static void
populate_serializer_with_split_spaces_2(hb_serialize_context_t * c)608 populate_serializer_with_split_spaces_2 (hb_serialize_context_t* c)
609 {
610 // Overflow needs to be resolved by splitting the single space
611 std::string large_string(70000, 'a');
612 c->start_serialize<char> ();
613
614 unsigned obj_f = add_object ("f", 1, c);
615
616 start_object (large_string.c_str(), 40000, c);
617 add_offset (obj_f, c);
618 unsigned obj_d = c->pop_pack (false);
619
620 start_object (large_string.c_str(), 40000, c);
621 add_offset (obj_f, c);
622 unsigned obj_e = c->pop_pack (false);
623
624 start_object ("b", 1, c);
625 add_offset (obj_d, c);
626 unsigned obj_b = c->pop_pack (false);
627
628 start_object ("c", 1, c);
629 add_offset (obj_e, c);
630 unsigned obj_c = c->pop_pack (false);
631
632 start_object ("a", 1, c);
633 add_offset (obj_b, c);
634 add_wide_offset (obj_b, c);
635 add_wide_offset (obj_c, c);
636 c->pop_pack (false);
637
638 c->end_serialize();
639 }
640
641 static void
populate_serializer_with_split_spaces_expected(hb_serialize_context_t * c)642 populate_serializer_with_split_spaces_expected (hb_serialize_context_t* c)
643 {
644 // Overflow needs to be resolved by splitting the single space
645
646 std::string large_string(70000, 'a');
647 c->start_serialize<char> ();
648
649 unsigned obj_f_prime = add_object ("f", 1, c);
650
651 start_object (large_string.c_str(), 40000, c);
652 add_offset (obj_f_prime, c);
653 unsigned obj_d = c->pop_pack (false);
654
655 start_object ("b", 1, c);
656 add_offset (obj_d, c);
657 unsigned obj_b = c->pop_pack (false);
658
659 unsigned obj_f = add_object ("f", 1, c);
660
661 start_object (large_string.c_str(), 40000, c);
662 add_offset (obj_f, c);
663 unsigned obj_e = c->pop_pack (false);
664
665 start_object ("c", 1, c);
666 add_offset (obj_e, c);
667 unsigned obj_c = c->pop_pack (false);
668
669 start_object ("a", 1, c);
670 add_wide_offset (obj_b, c);
671 add_wide_offset (obj_c, c);
672 c->pop_pack (false);
673
674 c->end_serialize();
675 }
676
677 static void
populate_serializer_with_split_spaces_expected_2(hb_serialize_context_t * c)678 populate_serializer_with_split_spaces_expected_2 (hb_serialize_context_t* c)
679 {
680 // Overflow needs to be resolved by splitting the single space
681
682 std::string large_string(70000, 'a');
683 c->start_serialize<char> ();
684
685 // Space 2
686
687 unsigned obj_f_double_prime = add_object ("f", 1, c);
688
689 start_object (large_string.c_str(), 40000, c);
690 add_offset (obj_f_double_prime, c);
691 unsigned obj_d_prime = c->pop_pack (false);
692
693 start_object ("b", 1, c);
694 add_offset (obj_d_prime, c);
695 unsigned obj_b_prime = c->pop_pack (false);
696
697 // Space 1
698
699 unsigned obj_f_prime = add_object ("f", 1, c);
700
701 start_object (large_string.c_str(), 40000, c);
702 add_offset (obj_f_prime, c);
703 unsigned obj_e = c->pop_pack (false);
704
705 start_object ("c", 1, c);
706 add_offset (obj_e, c);
707 unsigned obj_c = c->pop_pack (false);
708
709 // Space 0
710
711 unsigned obj_f = add_object ("f", 1, c);
712
713 start_object (large_string.c_str(), 40000, c);
714 add_offset (obj_f, c);
715 unsigned obj_d = c->pop_pack (false);
716
717 start_object ("b", 1, c);
718 add_offset (obj_d, c);
719 unsigned obj_b = c->pop_pack (false);
720
721 // Root
722 start_object ("a", 1, c);
723 add_offset (obj_b, c);
724 add_wide_offset (obj_b_prime, c);
725 add_wide_offset (obj_c, c);
726 c->pop_pack (false);
727
728 c->end_serialize();
729 }
730
731 static void
populate_serializer_complex_1(hb_serialize_context_t * c)732 populate_serializer_complex_1 (hb_serialize_context_t* c)
733 {
734 c->start_serialize<char> ();
735
736 unsigned obj_4 = add_object ("jkl", 3, c);
737 unsigned obj_3 = add_object ("ghi", 3, c);
738
739 start_object ("def", 3, c);
740 add_offset (obj_3, c);
741 unsigned obj_2 = c->pop_pack (false);
742
743 start_object ("abc", 3, c);
744 add_offset (obj_2, c);
745 add_offset (obj_4, c);
746 c->pop_pack (false);
747
748 c->end_serialize();
749 }
750
751 static void
populate_serializer_complex_2(hb_serialize_context_t * c)752 populate_serializer_complex_2 (hb_serialize_context_t* c)
753 {
754 c->start_serialize<char> ();
755
756 unsigned obj_5 = add_object ("mn", 2, c);
757
758 unsigned obj_4 = add_object ("jkl", 3, c);
759
760 start_object ("ghi", 3, c);
761 add_offset (obj_4, c);
762 unsigned obj_3 = c->pop_pack (false);
763
764 start_object ("def", 3, c);
765 add_offset (obj_3, c);
766 unsigned obj_2 = c->pop_pack (false);
767
768 start_object ("abc", 3, c);
769 add_offset (obj_2, c);
770 add_offset (obj_4, c);
771 add_offset (obj_5, c);
772 c->pop_pack (false);
773
774 c->end_serialize();
775 }
776
777 static void
populate_serializer_complex_3(hb_serialize_context_t * c)778 populate_serializer_complex_3 (hb_serialize_context_t* c)
779 {
780 c->start_serialize<char> ();
781
782 unsigned obj_6 = add_object ("opqrst", 6, c);
783
784 unsigned obj_5 = add_object ("mn", 2, c);
785
786 start_object ("jkl", 3, c);
787 add_offset (obj_6, c);
788 unsigned obj_4 = c->pop_pack (false);
789
790 start_object ("ghi", 3, c);
791 add_offset (obj_4, c);
792 unsigned obj_3 = c->pop_pack (false);
793
794 start_object ("def", 3, c);
795 add_offset (obj_3, c);
796 unsigned obj_2 = c->pop_pack (false);
797
798 start_object ("abc", 3, c);
799 add_offset (obj_2, c);
800 add_offset (obj_4, c);
801 add_offset (obj_5, c);
802 c->pop_pack (false);
803
804 c->end_serialize();
805 }
806
807 static void
populate_serializer_virtual_link(hb_serialize_context_t * c)808 populate_serializer_virtual_link (hb_serialize_context_t* c)
809 {
810 c->start_serialize<char> ();
811
812 unsigned obj_d = add_object ("d", 1, c);
813
814 start_object ("b", 1, c);
815 add_offset (obj_d, c);
816 unsigned obj_b = c->pop_pack (false);
817
818 start_object ("e", 1, c);
819 add_virtual_offset (obj_b, c);
820 unsigned obj_e = c->pop_pack (false);
821
822 start_object ("c", 1, c);
823 add_offset (obj_e, c);
824 unsigned obj_c = c->pop_pack (false);
825
826 start_object ("a", 1, c);
827 add_offset (obj_b, c);
828 add_offset (obj_c, c);
829 c->pop_pack (false);
830
831 c->end_serialize();
832 }
833
test_sort_kahn_1()834 static void test_sort_kahn_1 ()
835 {
836 size_t buffer_size = 100;
837 void* buffer = malloc (buffer_size);
838 hb_serialize_context_t c (buffer, buffer_size);
839 populate_serializer_complex_1 (&c);
840
841 graph_t graph (c.object_graph ());
842 graph.sort_kahn ();
843
844 assert(strncmp (graph.object (3).head, "abc", 3) == 0);
845 assert(graph.object (3).real_links.length == 2);
846 assert(graph.object (3).real_links[0].objidx == 2);
847 assert(graph.object (3).real_links[1].objidx == 1);
848
849 assert(strncmp (graph.object (2).head, "def", 3) == 0);
850 assert(graph.object (2).real_links.length == 1);
851 assert(graph.object (2).real_links[0].objidx == 0);
852
853 assert(strncmp (graph.object (1).head, "jkl", 3) == 0);
854 assert(graph.object (1).real_links.length == 0);
855
856 assert(strncmp (graph.object (0).head, "ghi", 3) == 0);
857 assert(graph.object (0).real_links.length == 0);
858
859 free (buffer);
860 }
861
test_sort_kahn_2()862 static void test_sort_kahn_2 ()
863 {
864 size_t buffer_size = 100;
865 void* buffer = malloc (buffer_size);
866 hb_serialize_context_t c (buffer, buffer_size);
867 populate_serializer_complex_2 (&c);
868
869 graph_t graph (c.object_graph ());
870 graph.sort_kahn ();
871
872
873 assert(strncmp (graph.object (4).head, "abc", 3) == 0);
874 assert(graph.object (4).real_links.length == 3);
875 assert(graph.object (4).real_links[0].objidx == 3);
876 assert(graph.object (4).real_links[1].objidx == 0);
877 assert(graph.object (4).real_links[2].objidx == 2);
878
879 assert(strncmp (graph.object (3).head, "def", 3) == 0);
880 assert(graph.object (3).real_links.length == 1);
881 assert(graph.object (3).real_links[0].objidx == 1);
882
883 assert(strncmp (graph.object (2).head, "mn", 2) == 0);
884 assert(graph.object (2).real_links.length == 0);
885
886 assert(strncmp (graph.object (1).head, "ghi", 3) == 0);
887 assert(graph.object (1).real_links.length == 1);
888 assert(graph.object (1).real_links[0].objidx == 0);
889
890 assert(strncmp (graph.object (0).head, "jkl", 3) == 0);
891 assert(graph.object (0).real_links.length == 0);
892
893 free (buffer);
894 }
895
test_sort_shortest()896 static void test_sort_shortest ()
897 {
898 size_t buffer_size = 100;
899 void* buffer = malloc (buffer_size);
900 hb_serialize_context_t c (buffer, buffer_size);
901 populate_serializer_complex_2 (&c);
902
903 graph_t graph (c.object_graph ());
904 graph.sort_shortest_distance ();
905
906 assert(strncmp (graph.object (4).head, "abc", 3) == 0);
907 assert(graph.object (4).real_links.length == 3);
908 assert(graph.object (4).real_links[0].objidx == 2);
909 assert(graph.object (4).real_links[1].objidx == 0);
910 assert(graph.object (4).real_links[2].objidx == 3);
911
912 assert(strncmp (graph.object (3).head, "mn", 2) == 0);
913 assert(graph.object (3).real_links.length == 0);
914
915 assert(strncmp (graph.object (2).head, "def", 3) == 0);
916 assert(graph.object (2).real_links.length == 1);
917 assert(graph.object (2).real_links[0].objidx == 1);
918
919 assert(strncmp (graph.object (1).head, "ghi", 3) == 0);
920 assert(graph.object (1).real_links.length == 1);
921 assert(graph.object (1).real_links[0].objidx == 0);
922
923 assert(strncmp (graph.object (0).head, "jkl", 3) == 0);
924 assert(graph.object (0).real_links.length == 0);
925
926 free (buffer);
927 }
928
test_duplicate_leaf()929 static void test_duplicate_leaf ()
930 {
931 size_t buffer_size = 100;
932 void* buffer = malloc (buffer_size);
933 hb_serialize_context_t c (buffer, buffer_size);
934 populate_serializer_complex_2 (&c);
935
936 graph_t graph (c.object_graph ());
937 graph.duplicate (4, 1);
938
939 assert(strncmp (graph.object (5).head, "abc", 3) == 0);
940 assert(graph.object (5).real_links.length == 3);
941 assert(graph.object (5).real_links[0].objidx == 3);
942 assert(graph.object (5).real_links[1].objidx == 4);
943 assert(graph.object (5).real_links[2].objidx == 0);
944
945 assert(strncmp (graph.object (4).head, "jkl", 3) == 0);
946 assert(graph.object (4).real_links.length == 0);
947
948 assert(strncmp (graph.object (3).head, "def", 3) == 0);
949 assert(graph.object (3).real_links.length == 1);
950 assert(graph.object (3).real_links[0].objidx == 2);
951
952 assert(strncmp (graph.object (2).head, "ghi", 3) == 0);
953 assert(graph.object (2).real_links.length == 1);
954 assert(graph.object (2).real_links[0].objidx == 1);
955
956 assert(strncmp (graph.object (1).head, "jkl", 3) == 0);
957 assert(graph.object (1).real_links.length == 0);
958
959 assert(strncmp (graph.object (0).head, "mn", 2) == 0);
960 assert(graph.object (0).real_links.length == 0);
961
962 free (buffer);
963 }
964
test_duplicate_interior()965 static void test_duplicate_interior ()
966 {
967 size_t buffer_size = 100;
968 void* buffer = malloc (buffer_size);
969 hb_serialize_context_t c (buffer, buffer_size);
970 populate_serializer_complex_3 (&c);
971
972 graph_t graph (c.object_graph ());
973 graph.duplicate (3, 2);
974
975 assert(strncmp (graph.object (6).head, "abc", 3) == 0);
976 assert(graph.object (6).real_links.length == 3);
977 assert(graph.object (6).real_links[0].objidx == 4);
978 assert(graph.object (6).real_links[1].objidx == 2);
979 assert(graph.object (6).real_links[2].objidx == 1);
980
981 assert(strncmp (graph.object (5).head, "jkl", 3) == 0);
982 assert(graph.object (5).real_links.length == 1);
983 assert(graph.object (5).real_links[0].objidx == 0);
984
985 assert(strncmp (graph.object (4).head, "def", 3) == 0);
986 assert(graph.object (4).real_links.length == 1);
987 assert(graph.object (4).real_links[0].objidx == 3);
988
989 assert(strncmp (graph.object (3).head, "ghi", 3) == 0);
990 assert(graph.object (3).real_links.length == 1);
991 assert(graph.object (3).real_links[0].objidx == 5);
992
993 assert(strncmp (graph.object (2).head, "jkl", 3) == 0);
994 assert(graph.object (2).real_links.length == 1);
995 assert(graph.object (2).real_links[0].objidx == 0);
996
997 assert(strncmp (graph.object (1).head, "mn", 2) == 0);
998 assert(graph.object (1).real_links.length == 0);
999
1000 assert(strncmp (graph.object (0).head, "opqrst", 6) == 0);
1001 assert(graph.object (0).real_links.length == 0);
1002
1003 free (buffer);
1004 }
1005
1006 static void
test_serialize()1007 test_serialize ()
1008 {
1009 size_t buffer_size = 100;
1010 void* buffer_1 = malloc (buffer_size);
1011 hb_serialize_context_t c1 (buffer_1, buffer_size);
1012 populate_serializer_simple (&c1);
1013 hb_bytes_t expected = c1.copy_bytes ();
1014
1015 graph_t graph (c1.object_graph ());
1016 hb_blob_t* out = graph.serialize ();
1017 free (buffer_1);
1018
1019 hb_bytes_t actual = out->as_bytes ();
1020 assert (actual == expected);
1021 expected.fini ();
1022 hb_blob_destroy (out);
1023 }
1024
test_will_overflow_1()1025 static void test_will_overflow_1 ()
1026 {
1027 size_t buffer_size = 100;
1028 void* buffer = malloc (buffer_size);
1029 hb_serialize_context_t c (buffer, buffer_size);
1030 populate_serializer_complex_2 (&c);
1031 graph_t graph (c.object_graph ());
1032
1033 assert (!graph.will_overflow (nullptr));
1034
1035 free (buffer);
1036 }
1037
test_will_overflow_2()1038 static void test_will_overflow_2 ()
1039 {
1040 size_t buffer_size = 160000;
1041 void* buffer = malloc (buffer_size);
1042 hb_serialize_context_t c (buffer, buffer_size);
1043 populate_serializer_with_overflow (&c);
1044 graph_t graph (c.object_graph ());
1045
1046 assert (graph.will_overflow (nullptr));
1047
1048 free (buffer);
1049 }
1050
test_will_overflow_3()1051 static void test_will_overflow_3 ()
1052 {
1053 size_t buffer_size = 160000;
1054 void* buffer = malloc (buffer_size);
1055 hb_serialize_context_t c (buffer, buffer_size);
1056 populate_serializer_with_dedup_overflow (&c);
1057 graph_t graph (c.object_graph ());
1058
1059 assert (graph.will_overflow (nullptr));
1060
1061 free (buffer);
1062 }
1063
test_resolve_overflows_via_sort()1064 static void test_resolve_overflows_via_sort ()
1065 {
1066 size_t buffer_size = 160000;
1067 void* buffer = malloc (buffer_size);
1068 hb_serialize_context_t c (buffer, buffer_size);
1069 populate_serializer_with_overflow (&c);
1070 graph_t graph (c.object_graph ());
1071
1072 hb_blob_t* out = hb_resolve_overflows (c.object_graph (), HB_TAG_NONE);
1073 assert (out);
1074 hb_bytes_t result = out->as_bytes ();
1075 assert (result.length == (80000 + 3 + 3 * 2));
1076
1077 free (buffer);
1078 hb_blob_destroy (out);
1079 }
1080
test_resolve_overflows_via_duplication()1081 static void test_resolve_overflows_via_duplication ()
1082 {
1083 size_t buffer_size = 160000;
1084 void* buffer = malloc (buffer_size);
1085 hb_serialize_context_t c (buffer, buffer_size);
1086 populate_serializer_with_dedup_overflow (&c);
1087 graph_t graph (c.object_graph ());
1088
1089 hb_blob_t* out = hb_resolve_overflows (c.object_graph (), HB_TAG_NONE);
1090 assert (out);
1091 hb_bytes_t result = out->as_bytes ();
1092 assert (result.length == (10000 + 2 * 2 + 60000 + 2 + 3 * 2));
1093
1094 free (buffer);
1095 hb_blob_destroy (out);
1096 }
1097
test_resolve_overflows_via_space_assignment()1098 static void test_resolve_overflows_via_space_assignment ()
1099 {
1100 size_t buffer_size = 160000;
1101 void* buffer = malloc (buffer_size);
1102 hb_serialize_context_t c (buffer, buffer_size);
1103 populate_serializer_spaces (&c, true);
1104
1105 void* expected_buffer = malloc (buffer_size);
1106 hb_serialize_context_t e (expected_buffer, buffer_size);
1107 populate_serializer_spaces (&e, false);
1108
1109 run_resolve_overflow_test ("test_resolve_overflows_via_space_assignment",
1110 c,
1111 e);
1112
1113 free (buffer);
1114 free (expected_buffer);
1115 }
1116
test_resolve_overflows_via_isolation()1117 static void test_resolve_overflows_via_isolation ()
1118 {
1119 size_t buffer_size = 160000;
1120 void* buffer = malloc (buffer_size);
1121 hb_serialize_context_t c (buffer, buffer_size);
1122 populate_serializer_with_isolation_overflow (&c);
1123 graph_t graph (c.object_graph ());
1124
1125 assert (c.offset_overflow ());
1126 hb_blob_t* out = hb_resolve_overflows (c.object_graph (), HB_TAG ('G', 'S', 'U', 'B'), 0);
1127 assert (out);
1128 hb_bytes_t result = out->as_bytes ();
1129 assert (result.length == (1 + 10000 + 60000 + 1 + 1
1130 + 4 + 3 * 2));
1131
1132 free (buffer);
1133 hb_blob_destroy (out);
1134 }
1135
test_resolve_overflows_via_isolation_with_recursive_duplication()1136 static void test_resolve_overflows_via_isolation_with_recursive_duplication ()
1137 {
1138 size_t buffer_size = 160000;
1139 void* buffer = malloc (buffer_size);
1140 hb_serialize_context_t c (buffer, buffer_size);
1141 populate_serializer_with_isolation_overflow_complex (&c);
1142
1143 void* expected_buffer = malloc (buffer_size);
1144 hb_serialize_context_t e (expected_buffer, buffer_size);
1145 populate_serializer_with_isolation_overflow_complex_expected (&e);
1146
1147 run_resolve_overflow_test ("test_resolve_overflows_via_isolation_with_recursive_duplication",
1148 c,
1149 e);
1150 free (buffer);
1151 free (expected_buffer);
1152 }
1153
test_resolve_overflows_via_isolating_16bit_space()1154 static void test_resolve_overflows_via_isolating_16bit_space ()
1155 {
1156 size_t buffer_size = 160000;
1157 void* buffer = malloc (buffer_size);
1158 hb_serialize_context_t c (buffer, buffer_size);
1159 populate_serializer_spaces_16bit_connection (&c);
1160
1161 void* expected_buffer = malloc (buffer_size);
1162 hb_serialize_context_t e (expected_buffer, buffer_size);
1163 populate_serializer_spaces_16bit_connection_expected (&e);
1164
1165 run_resolve_overflow_test ("test_resolve_overflows_via_isolating_16bit_space",
1166 c,
1167 e);
1168
1169 free (buffer);
1170 free (expected_buffer);
1171 }
1172
test_resolve_overflows_via_isolating_16bit_space_2()1173 static void test_resolve_overflows_via_isolating_16bit_space_2 ()
1174 {
1175 size_t buffer_size = 160000;
1176 void* buffer = malloc (buffer_size);
1177 hb_serialize_context_t c (buffer, buffer_size);
1178 populate_serializer_short_and_wide_subgraph_root (&c);
1179
1180 void* expected_buffer = malloc (buffer_size);
1181 hb_serialize_context_t e (expected_buffer, buffer_size);
1182 populate_serializer_short_and_wide_subgraph_root_expected (&e);
1183
1184 run_resolve_overflow_test ("test_resolve_overflows_via_isolating_16bit_space_2",
1185 c,
1186 e);
1187
1188 free (buffer);
1189 free (expected_buffer);
1190 }
1191
test_resolve_overflows_via_isolation_spaces()1192 static void test_resolve_overflows_via_isolation_spaces ()
1193 {
1194 size_t buffer_size = 160000;
1195 void* buffer = malloc (buffer_size);
1196 hb_serialize_context_t c (buffer, buffer_size);
1197 populate_serializer_with_isolation_overflow_spaces (&c);
1198 graph_t graph (c.object_graph ());
1199
1200 assert (c.offset_overflow ());
1201 hb_blob_t* out = hb_resolve_overflows (c.object_graph (), HB_TAG ('G', 'S', 'U', 'B'), 0);
1202 assert (out);
1203 hb_bytes_t result = out->as_bytes ();
1204
1205 unsigned expected_length = 3 + 2 * 60000; // objects
1206 expected_length += 2 * 4 + 2 * 2; // links
1207 assert (result.length == expected_length);
1208
1209 free (buffer);
1210 hb_blob_destroy (out);
1211 }
1212
test_resolve_overflows_via_splitting_spaces()1213 static void test_resolve_overflows_via_splitting_spaces ()
1214 {
1215 size_t buffer_size = 160000;
1216 void* buffer = malloc (buffer_size);
1217 hb_serialize_context_t c (buffer, buffer_size);
1218 populate_serializer_with_split_spaces (&c);
1219
1220 void* expected_buffer = malloc (buffer_size);
1221 hb_serialize_context_t e (expected_buffer, buffer_size);
1222 populate_serializer_with_split_spaces_expected (&e);
1223
1224 run_resolve_overflow_test ("test_resolve_overflows_via_splitting_spaces",
1225 c,
1226 e,
1227 1);
1228
1229 free (buffer);
1230 free (expected_buffer);
1231
1232 }
1233
test_resolve_overflows_via_splitting_spaces_2()1234 static void test_resolve_overflows_via_splitting_spaces_2 ()
1235 {
1236 size_t buffer_size = 160000;
1237 void* buffer = malloc (buffer_size);
1238 hb_serialize_context_t c (buffer, buffer_size);
1239 populate_serializer_with_split_spaces_2 (&c);
1240
1241 void* expected_buffer = malloc (buffer_size);
1242 hb_serialize_context_t e (expected_buffer, buffer_size);
1243 populate_serializer_with_split_spaces_expected_2 (&e);
1244
1245 run_resolve_overflow_test ("test_resolve_overflows_via_splitting_spaces_2",
1246 c,
1247 e,
1248 1);
1249 free (buffer);
1250 free (expected_buffer);
1251 }
1252
test_resolve_overflows_via_priority()1253 static void test_resolve_overflows_via_priority ()
1254 {
1255 size_t buffer_size = 160000;
1256 void* buffer = malloc (buffer_size);
1257 hb_serialize_context_t c (buffer, buffer_size);
1258 populate_serializer_with_priority_overflow (&c);
1259
1260 void* expected_buffer = malloc (buffer_size);
1261 hb_serialize_context_t e (expected_buffer, buffer_size);
1262 populate_serializer_with_priority_overflow_expected (&e);
1263
1264 run_resolve_overflow_test ("test_resolve_overflows_via_priority",
1265 c,
1266 e,
1267 3);
1268 free (buffer);
1269 free (expected_buffer);
1270 }
1271
1272
test_virtual_link()1273 static void test_virtual_link ()
1274 {
1275 size_t buffer_size = 100;
1276 void* buffer = malloc (buffer_size);
1277 hb_serialize_context_t c (buffer, buffer_size);
1278 populate_serializer_virtual_link (&c);
1279
1280 hb_blob_t* out = hb_resolve_overflows (c.object_graph (), HB_TAG_NONE);
1281 assert (out);
1282
1283 hb_bytes_t result = out->as_bytes ();
1284 assert (result.length == 5 + 4 * 2);
1285 assert (result[0] == 'a');
1286 assert (result[5] == 'c');
1287 assert (result[8] == 'e');
1288 assert (result[9] == 'b');
1289 assert (result[12] == 'd');
1290
1291 free (buffer);
1292 hb_blob_destroy (out);
1293 }
1294
1295 static void
test_shared_node_with_virtual_links()1296 test_shared_node_with_virtual_links ()
1297 {
1298 size_t buffer_size = 100;
1299 void* buffer = malloc (buffer_size);
1300 hb_serialize_context_t c (buffer, buffer_size);
1301
1302 c.start_serialize<char> ();
1303
1304 unsigned obj_b = add_object ("b", 1, &c);
1305 unsigned obj_c = add_object ("c", 1, &c);
1306
1307 start_object ("d", 1, &c);
1308 add_virtual_offset (obj_b, &c);
1309 unsigned obj_d_1 = c.pop_pack ();
1310
1311 start_object ("d", 1, &c);
1312 add_virtual_offset (obj_c, &c);
1313 unsigned obj_d_2 = c.pop_pack ();
1314
1315 assert (obj_d_1 == obj_d_2);
1316
1317 start_object ("a", 1, &c);
1318 add_offset (obj_b, &c);
1319 add_offset (obj_c, &c);
1320 add_offset (obj_d_1, &c);
1321 add_offset (obj_d_2, &c);
1322 c.pop_pack ();
1323 c.end_serialize ();
1324
1325 assert(c.object_graph() [obj_d_1]->virtual_links.length == 2);
1326 assert(c.object_graph() [obj_d_1]->virtual_links[0].objidx == obj_b);
1327 assert(c.object_graph() [obj_d_1]->virtual_links[1].objidx == obj_c);
1328 free(buffer);
1329 }
1330
1331
1332 // TODO(garretrieger): update will_overflow tests to check the overflows array.
1333 // TODO(garretrieger): add tests for priority raising.
1334
1335 int
main(int argc,char ** argv)1336 main (int argc, char **argv)
1337 {
1338 test_serialize ();
1339 test_sort_kahn_1 ();
1340 test_sort_kahn_2 ();
1341 test_sort_shortest ();
1342 test_will_overflow_1 ();
1343 test_will_overflow_2 ();
1344 test_will_overflow_3 ();
1345 test_resolve_overflows_via_sort ();
1346 test_resolve_overflows_via_duplication ();
1347 test_resolve_overflows_via_priority ();
1348 test_resolve_overflows_via_space_assignment ();
1349 test_resolve_overflows_via_isolation ();
1350 test_resolve_overflows_via_isolation_with_recursive_duplication ();
1351 test_resolve_overflows_via_isolation_spaces ();
1352 test_resolve_overflows_via_isolating_16bit_space ();
1353 test_resolve_overflows_via_isolating_16bit_space_2 ();
1354 test_resolve_overflows_via_splitting_spaces ();
1355 test_resolve_overflows_via_splitting_spaces_2 ();
1356 test_duplicate_leaf ();
1357 test_duplicate_interior ();
1358 test_virtual_link ();
1359 test_shared_node_with_virtual_links ();
1360 }
1361