src/test-repacker.cc

   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
  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
  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
  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
  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
  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
  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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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 }