js/src/jsapi-tests/testUbiNode.cpp

   1 /* This Source Code Form is subject to the terms of the Mozilla Public
   2  * License, v. 2.0. If a copy of the MPL was not distributed with this
   3  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   4
   5 #include "mozilla/Utf8.h"  // mozilla::Utf8Unit
   6
   7 #include "builtin/TestingFunctions.h"
   8 #include "js/CompilationAndEvaluation.h"  // JS::Compile
   9 #include "js/GlobalObject.h"              // JS_NewGlobalObject
  10 #include "js/SourceText.h"                // JS::Source{Ownership,Text}
  11 #include "js/UbiNode.h"
  12 #include "js/UbiNodeDominatorTree.h"
  13 #include "js/UbiNodePostOrder.h"
  14 #include "js/UbiNodeShortestPaths.h"
  15 #include "jsapi-tests/tests.h"
  16 #include "util/Text.h"
  17 #include "vm/Compartment.h"
  18 #include "vm/Realm.h"
  19 #include "vm/SavedFrame.h"
  20
  21 #include "vm/JSObject-inl.h"
  22
  23 using JS::RootedObject;
  24 using JS::RootedScript;
  25 using JS::RootedString;
  26 using namespace js;
  27
  28 // A helper JS::ubi::Node concrete implementation that can be used to make mock
  29 // graphs for testing traversals with.
  30 struct FakeNode {
  31   char name;
  32   JS::ubi::EdgeVector edges;
  33
  34   explicit FakeNode(char name) : name(name), edges() {}
  35
  36   bool addEdgeTo(FakeNode& referent, const char16_t* edgeName = nullptr) {
  37     JS::ubi::Node node(&referent);
  38
  39     if (edgeName) {
  40       auto ownedName = js::DuplicateString(edgeName);
  41       MOZ_RELEASE_ASSERT(ownedName);
  42       return edges.emplaceBack(ownedName.release(), node);
  43     }
  44
  45     return edges.emplaceBack(nullptr, node);
  46   }
  47 };
  48
  49 namespace JS {
  50 namespace ubi {
  51
  52 template <>
  53 class Concrete<FakeNode> : public Base {
  54  protected:
  55   explicit Concrete(FakeNode* ptr) : Base(ptr) {}
  56   FakeNode& get() const { return *static_cast<FakeNode*>(ptr); }
  57
  58  public:
  59   static void construct(void* storage, FakeNode* ptr) {
  60     new (storage) Concrete(ptr);
  61   }
  62
  63   UniquePtr<EdgeRange> edges(JSContext* cx, bool wantNames) const override {
  64     return UniquePtr<EdgeRange>(js_new<PreComputedEdgeRange>(get().edges));
  65   }
  66
  67   Node::Size size(mozilla::MallocSizeOf) const override { return 1; }
  68
  69   static const char16_t concreteTypeName[];
  70   const char16_t* typeName() const override { return concreteTypeName; }
  71 };
  72
  73 const char16_t Concrete<FakeNode>::concreteTypeName[] = u"FakeNode";
  74
  75 }  // namespace ubi
  76 }  // namespace JS
  77
  78 // ubi::Node::zone works
  79 BEGIN_TEST(test_ubiNodeZone) {
  80   RootedObject global1(cx, JS::CurrentGlobalOrNull(cx));
  81   CHECK(global1);
  82   CHECK(JS::ubi::Node(global1).zone() == cx->zone());
  83
  84   JS::RealmOptions globalOptions;
  85   RootedObject global2(
  86       cx, JS_NewGlobalObject(cx, getGlobalClass(), nullptr,
  87                              JS::FireOnNewGlobalHook, globalOptions));
  88   CHECK(global2);
  89   CHECK(global1->zone() != global2->zone());
  90   CHECK(JS::ubi::Node(global2).zone() == global2->zone());
  91   CHECK(JS::ubi::Node(global2).zone() != global1->zone());
  92
  93   JS::CompileOptions options(cx);
  94
  95   // Create a string and a script in the original zone...
  96   RootedString string1(
  97       cx, JS_NewStringCopyZ(cx, "Simpson's Individual Stringettes!"));
  98   CHECK(string1);
  99
 100   JS::SourceText<mozilla::Utf8Unit> emptySrcBuf;
 101   CHECK(emptySrcBuf.init(cx, "", 0, JS::SourceOwnership::Borrowed));
 102
 103   RootedScript script1(cx, JS::Compile(cx, options, emptySrcBuf));
 104   CHECK(script1);
 105
 106   {
 107     // ... and then enter global2's zone and create a string and script
 108     // there, too.
 109     JSAutoRealm ar(cx, global2);
 110
 111     RootedString string2(cx,
 112                          JS_NewStringCopyZ(cx, "A million household uses!"));
 113     CHECK(string2);
 114     RootedScript script2(cx, JS::Compile(cx, options, emptySrcBuf));
 115     CHECK(script2);
 116
 117     CHECK(JS::ubi::Node(string1).zone() == global1->zone());
 118     CHECK(JS::ubi::Node(script1).zone() == global1->zone());
 119
 120     CHECK(JS::ubi::Node(string2).zone() == global2->zone());
 121     CHECK(JS::ubi::Node(script2).zone() == global2->zone());
 122   }
 123
 124   return true;
 125 }
 126 END_TEST(test_ubiNodeZone)
 127
 128 // ubi::Node::compartment works
 129 BEGIN_TEST(test_ubiNodeCompartment) {
 130   RootedObject global1(cx, JS::CurrentGlobalOrNull(cx));
 131   CHECK(global1);
 132   CHECK(JS::ubi::Node(global1).compartment() == cx->compartment());
 133   CHECK(JS::ubi::Node(global1).realm() == cx->realm());
 134
 135   JS::RealmOptions globalOptions;
 136   RootedObject global2(
 137       cx, JS_NewGlobalObject(cx, getGlobalClass(), nullptr,
 138                              JS::FireOnNewGlobalHook, globalOptions));
 139   CHECK(global2);
 140   CHECK(global1->compartment() != global2->compartment());
 141   CHECK(JS::ubi::Node(global2).compartment() == global2->compartment());
 142   CHECK(JS::ubi::Node(global2).compartment() != global1->compartment());
 143   CHECK(JS::ubi::Node(global2).realm() == global2->nonCCWRealm());
 144   CHECK(JS::ubi::Node(global2).realm() != global1->nonCCWRealm());
 145
 146   JS::CompileOptions options(cx);
 147
 148   JS::SourceText<mozilla::Utf8Unit> emptySrcBuf;
 149   CHECK(emptySrcBuf.init(cx, "", 0, JS::SourceOwnership::Borrowed));
 150
 151   // Create a script in the original realm...
 152   RootedScript script1(cx, JS::Compile(cx, options, emptySrcBuf));
 153   CHECK(script1);
 154
 155   {
 156     // ... and then enter global2's realm and create a script
 157     // there, too.
 158     JSAutoRealm ar(cx, global2);
 159
 160     RootedScript script2(cx, JS::Compile(cx, options, emptySrcBuf));
 161     CHECK(script2);
 162
 163     CHECK(JS::ubi::Node(script1).compartment() == global1->compartment());
 164     CHECK(JS::ubi::Node(script2).compartment() == global2->compartment());
 165     CHECK(JS::ubi::Node(script1).realm() == global1->nonCCWRealm());
 166     CHECK(JS::ubi::Node(script2).realm() == global2->nonCCWRealm());
 167
 168     // Now create a wrapper for global1 in global2's compartment.
 169     RootedObject wrappedGlobal1(cx, global1);
 170     CHECK(cx->compartment()->wrap(cx, &wrappedGlobal1));
 171
 172     // Cross-compartment wrappers have a compartment() but not a realm().
 173     CHECK(JS::ubi::Node(wrappedGlobal1).zone() == cx->zone());
 174     CHECK(JS::ubi::Node(wrappedGlobal1).compartment() == cx->compartment());
 175     CHECK(JS::ubi::Node(wrappedGlobal1).realm() == nullptr);
 176   }
 177
 178   return true;
 179 }
 180 END_TEST(test_ubiNodeCompartment)
 181
 182 template <typename F, typename G>
 183 static bool checkString(const char* expected, F fillBufferFunction,
 184                         G stringGetterFunction) {
 185   auto expectedLength = strlen(expected);
 186   char16_t buf[1024];
 187   if (fillBufferFunction(mozilla::RangedPtr<char16_t>(buf, 1024), 1024) !=
 188           expectedLength ||
 189       !EqualChars(buf, expected, expectedLength)) {
 190     return false;
 191   }
 192
 193   auto string = stringGetterFunction();
 194   // Expecting a |JSAtom*| from a live |JS::ubi::StackFrame|.
 195   if (!string.template is<JSAtom*>() ||
 196       !StringEqualsAscii(string.template as<JSAtom*>(), expected)) {
 197     return false;
 198   }
 199
 200   return true;
 201 }
 202
 203 BEGIN_TEST(test_ubiStackFrame) {
 204   CHECK(js::DefineTestingFunctions(cx, global, false, false));
 205
 206   JS::RootedValue val(cx);
 207   CHECK(
 208       evaluate("(function one() {                      \n"   // 1
 209                "  return (function two() {             \n"   // 2
 210                "    return (function three() {         \n"   // 3
 211                "      return saveStack();              \n"   // 4
 212                "    }());                              \n"   // 5
 213                "  }());                                \n"   // 6
 214                "}());                                  \n",  // 7
 215                "filename.js", 1, &val));
 216
 217   CHECK(val.isObject());
 218   JS::RootedObject obj(cx, &val.toObject());
 219
 220   CHECK(obj->is<SavedFrame>());
 221   JS::Rooted<SavedFrame*> savedFrame(cx, &obj->as<SavedFrame>());
 222
 223   JS::ubi::StackFrame ubiFrame(savedFrame);
 224
 225   // All frames should be from the "filename.js" source.
 226   while (ubiFrame) {
 227     CHECK(checkString(
 228         "filename.js",
 229         [&](mozilla::RangedPtr<char16_t> ptr, size_t length) {
 230           return ubiFrame.source(ptr, length);
 231         },
 232         [&] { return ubiFrame.source(); }));
 233     ubiFrame = ubiFrame.parent();
 234   }
 235
 236   ubiFrame = savedFrame;
 237
 238   auto bufferFunctionDisplayName = [&](mozilla::RangedPtr<char16_t> ptr,
 239                                        size_t length) {
 240     return ubiFrame.functionDisplayName(ptr, length);
 241   };
 242   auto getFunctionDisplayName = [&] { return ubiFrame.functionDisplayName(); };
 243
 244   CHECK(
 245       checkString("three", bufferFunctionDisplayName, getFunctionDisplayName));
 246   CHECK(ubiFrame.line() == 4);
 247
 248   ubiFrame = ubiFrame.parent();
 249   CHECK(checkString("two", bufferFunctionDisplayName, getFunctionDisplayName));
 250   CHECK(ubiFrame.line() == 5);
 251
 252   ubiFrame = ubiFrame.parent();
 253   CHECK(checkString("one", bufferFunctionDisplayName, getFunctionDisplayName));
 254   CHECK(ubiFrame.line() == 6);
 255
 256   ubiFrame = ubiFrame.parent();
 257   CHECK(ubiFrame.functionDisplayName().is<JSAtom*>());
 258   CHECK(ubiFrame.functionDisplayName().as<JSAtom*>() == nullptr);
 259   CHECK(ubiFrame.line() == 7);
 260
 261   ubiFrame = ubiFrame.parent();
 262   CHECK(!ubiFrame);
 263
 264   return true;
 265 }
 266 END_TEST(test_ubiStackFrame)
 267
 268 BEGIN_TEST(test_ubiCoarseType) {
 269   // Test that our explicit coarseType() overrides work as expected.
 270
 271   JSObject* obj = nullptr;
 272   CHECK(JS::ubi::Node(obj).coarseType() == JS::ubi::CoarseType::Object);
 273
 274   JSScript* script = nullptr;
 275   CHECK(JS::ubi::Node(script).coarseType() == JS::ubi::CoarseType::Script);
 276
 277   js::BaseScript* baseScript = nullptr;
 278   CHECK(JS::ubi::Node(baseScript).coarseType() == JS::ubi::CoarseType::Script);
 279
 280   js::jit::JitCode* jitCode = nullptr;
 281   CHECK(JS::ubi::Node(jitCode).coarseType() == JS::ubi::CoarseType::Script);
 282
 283   JSString* str = nullptr;
 284   CHECK(JS::ubi::Node(str).coarseType() == JS::ubi::CoarseType::String);
 285
 286   // Test that the default when coarseType() is not overridden is Other.
 287
 288   JS::Symbol* sym = nullptr;
 289   CHECK(JS::ubi::Node(sym).coarseType() == JS::ubi::CoarseType::Other);
 290
 291   return true;
 292 }
 293 END_TEST(test_ubiCoarseType)
 294
 295 struct ExpectedEdge {
 296   char from;
 297   char to;
 298
 299   ExpectedEdge(FakeNode& fromNode, FakeNode& toNode)
 300       : from(fromNode.name), to(toNode.name) {}
 301 };
 302
 303 namespace mozilla {
 304
 305 template <>
 306 struct DefaultHasher<ExpectedEdge> {
 307   using Lookup = ExpectedEdge;
 308
 309   static HashNumber hash(const Lookup& l) {
 310     return mozilla::AddToHash(l.from, l.to);
 311   }
 312
 313   static bool match(const ExpectedEdge& k, const Lookup& l) {
 314     return k.from == l.from && k.to == l.to;
 315   }
 316 };
 317
 318 }  // namespace mozilla
 319
 320 BEGIN_TEST(test_ubiPostOrder) {
 321   // Construct the following graph:
 322   //
 323   //                          .-----.
 324   //                          |     |
 325   //                  .-------|  r  |---------------.
 326   //                  |       |     |               |
 327   //                  |       '-----'               |
 328   //                  |                             |
 329   //               .--V--.                       .--V--.
 330   //               |     |                       |     |
 331   //        .------|  a  |------.           .----|  e  |----.
 332   //        |      |     |      |           |    |     |    |
 333   //        |      '--^--'      |           |    '-----'    |
 334   //        |         |         |           |               |
 335   //     .--V--.      |      .--V--.     .--V--.         .--V--.
 336   //     |     |      |      |     |     |     |         |     |
 337   //     |  b  |      '------|  c  |----->  f  |--------->  g  |
 338   //     |     |             |     |     |     |         |     |
 339   //     '-----'             '-----'     '-----'         '-----'
 340   //        |                   |
 341   //        |      .-----.      |
 342   //        |      |     |      |
 343   //        '------>  d  <------'
 344   //               |     |
 345   //               '-----'
 346   //
 347
 348   FakeNode r('r');
 349   FakeNode a('a');
 350   FakeNode b('b');
 351   FakeNode c('c');
 352   FakeNode d('d');
 353   FakeNode e('e');
 354   FakeNode f('f');
 355   FakeNode g('g');
 356
 357   js::HashSet<ExpectedEdge> expectedEdges(cx);
 358
 359   auto declareEdge = [&](FakeNode& from, FakeNode& to) {
 360     return from.addEdgeTo(to) && expectedEdges.putNew(ExpectedEdge(from, to));
 361   };
 362
 363   CHECK(declareEdge(r, a));
 364   CHECK(declareEdge(r, e));
 365   CHECK(declareEdge(a, b));
 366   CHECK(declareEdge(a, c));
 367   CHECK(declareEdge(b, d));
 368   CHECK(declareEdge(c, a));
 369   CHECK(declareEdge(c, d));
 370   CHECK(declareEdge(c, f));
 371   CHECK(declareEdge(e, f));
 372   CHECK(declareEdge(e, g));
 373   CHECK(declareEdge(f, g));
 374
 375   js::Vector<char, 8, js::SystemAllocPolicy> visited;
 376   {
 377     // Do a PostOrder traversal, starting from r. Accumulate the names of
 378     // the nodes we visit in `visited`. Remove edges we traverse from
 379     // `expectedEdges` as we find them to ensure that we only find each edge
 380     // once.
 381
 382     JS::AutoCheckCannotGC nogc(cx);
 383     JS::ubi::PostOrder traversal(cx, nogc);
 384     CHECK(traversal.addStart(&r));
 385
 386     auto onNode = [&](const JS::ubi::Node& node) {
 387       return visited.append(node.as<FakeNode>()->name);
 388     };
 389
 390     auto onEdge = [&](const JS::ubi::Node& origin, const JS::ubi::Edge& edge) {
 391       ExpectedEdge e(*origin.as<FakeNode>(), *edge.referent.as<FakeNode>());
 392       if (!expectedEdges.has(e)) {
 393         fprintf(stderr, "Error: Unexpected edge from %c to %c!\n",
 394                 origin.as<FakeNode>()->name,
 395                 edge.referent.as<FakeNode>()->name);
 396         return false;
 397       }
 398
 399       expectedEdges.remove(e);
 400       return true;
 401     };
 402
 403     CHECK(traversal.traverse(onNode, onEdge));
 404   }
 405
 406   fprintf(stderr, "visited.length() = %lu\n", (unsigned long)visited.length());
 407   for (size_t i = 0; i < visited.length(); i++) {
 408     fprintf(stderr, "visited[%lu] = '%c'\n", (unsigned long)i, visited[i]);
 409   }
 410
 411   CHECK(visited.length() == 8);
 412   CHECK(visited[0] == 'g');
 413   CHECK(visited[1] == 'f');
 414   CHECK(visited[2] == 'e');
 415   CHECK(visited[3] == 'd');
 416   CHECK(visited[4] == 'c');
 417   CHECK(visited[5] == 'b');
 418   CHECK(visited[6] == 'a');
 419   CHECK(visited[7] == 'r');
 420
 421   // We found all the edges we expected.
 422   CHECK(expectedEdges.count() == 0);
 423
 424   return true;
 425 }
 426 END_TEST(test_ubiPostOrder)
 427
 428 BEGIN_TEST(test_JS_ubi_DominatorTree) {
 429   // Construct the following graph:
 430   //
 431   //                                  .-----.
 432   //                                  |     <--------------------------------.
 433   //          .--------+--------------|  r  |--------------.                 |
 434   //          |        |              |     |              |                 |
 435   //          |        |              '-----'              |                 |
 436   //          |     .--V--.                             .--V--.              |
 437   //          |     |     |                             |     |              |
 438   //          |     |  b  |                             |  c  |--------.     |
 439   //          |     |     |                             |     |        |     |
 440   //          |     '-----'                             '-----'        |     |
 441   //       .--V--.     |                                   |        .--V--.  |
 442   //       |     |     |                                   |        |     |  |
 443   //       |  a  <-----+                                   |   .----|  g  |  |
 444   //       |     |     |                              .----'   |    |     |  |
 445   //       '-----'     |                              |        |    '-----'  |
 446   //          |        |                              |        |       |     |
 447   //       .--V--.     |    .-----.                .--V--.     |       |     |
 448   //       |     |     |    |     |                |     |     |       |     |
 449   //       |  d  <-----+---->  e  <----.           |  f  |     |       |     |
 450   //       |     |          |     |    |           |     |     |       |     |
 451   //       '-----'          '-----'    |           '-----'     |       |     |
 452   //          |     .-----.    |       |              |        |    .--V--.  |
 453   //          |     |     |    |       |              |      .-'    |     |  |
 454   //          '----->  l  |    |       |              |      |      |  j  |  |
 455   //                |     |    '--.    |              |      |      |     |  |
 456   //                '-----'       |    |              |      |      '-----'  |
 457   //                   |       .--V--. |              |   .--V--.      |     |
 458   //                   |       |     | |              |   |     |      |     |
 459   //                   '------->  h  |-'              '--->  i  <------'     |
 460   //                           |     |          .--------->     |            |
 461   //                           '-----'          |         '-----'            |
 462   //                              |          .-----.         |               |
 463   //                              |          |     |         |               |
 464   //                              '---------->  k  <---------'               |
 465   //                                         |     |                         |
 466   //                                         '-----'                         |
 467   //                                            |                            |
 468   //                                            '----------------------------'
 469   //
 470   // This graph has the following dominator tree:
 471   //
 472   //     r
 473   //     |-- a
 474   //     |-- b
 475   //     |-- c
 476   //     |   |-- f
 477   //     |   `-- g
 478   //     |       `-- j
 479   //     |-- d
 480   //     |   `-- l
 481   //     |-- e
 482   //     |-- i
 483   //     |-- k
 484   //     `-- h
 485   //
 486   // This graph and dominator tree are taken from figures 1 and 2 of "A Fast
 487   // Algorithm for Finding Dominators in a Flowgraph" by Lengauer et al:
 488   // http://www.cs.princeton.edu/courses/archive/spr03/cs423/download/dominators.pdf.
 489
 490   FakeNode r('r');
 491   FakeNode a('a');
 492   FakeNode b('b');
 493   FakeNode c('c');
 494   FakeNode d('d');
 495   FakeNode e('e');
 496   FakeNode f('f');
 497   FakeNode g('g');
 498   FakeNode h('h');
 499   FakeNode i('i');
 500   FakeNode j('j');
 501   FakeNode k('k');
 502   FakeNode l('l');
 503
 504   CHECK(r.addEdgeTo(a));
 505   CHECK(r.addEdgeTo(b));
 506   CHECK(r.addEdgeTo(c));
 507   CHECK(a.addEdgeTo(d));
 508   CHECK(b.addEdgeTo(a));
 509   CHECK(b.addEdgeTo(d));
 510   CHECK(b.addEdgeTo(e));
 511   CHECK(c.addEdgeTo(f));
 512   CHECK(c.addEdgeTo(g));
 513   CHECK(d.addEdgeTo(l));
 514   CHECK(e.addEdgeTo(h));
 515   CHECK(f.addEdgeTo(i));
 516   CHECK(g.addEdgeTo(i));
 517   CHECK(g.addEdgeTo(j));
 518   CHECK(h.addEdgeTo(e));
 519   CHECK(h.addEdgeTo(k));
 520   CHECK(i.addEdgeTo(k));
 521   CHECK(j.addEdgeTo(i));
 522   CHECK(k.addEdgeTo(r));
 523   CHECK(k.addEdgeTo(i));
 524   CHECK(l.addEdgeTo(h));
 525
 526   mozilla::Maybe<JS::ubi::DominatorTree> maybeTree;
 527   {
 528     JS::AutoCheckCannotGC noGC(cx);
 529     maybeTree = JS::ubi::DominatorTree::Create(cx, noGC, &r);
 530   }
 531
 532   CHECK(maybeTree.isSome());
 533   auto& tree = *maybeTree;
 534
 535   // We return the null JS::ubi::Node for nodes that were not reachable in the
 536   // graph when computing the dominator tree.
 537   FakeNode m('m');
 538   CHECK(tree.getImmediateDominator(&m) == JS::ubi::Node());
 539   CHECK(tree.getDominatedSet(&m).isNothing());
 540
 541   struct {
 542     FakeNode& dominated;
 543     FakeNode& dominator;
 544   } domination[] = {{r, r}, {a, r}, {b, r}, {c, r}, {d, r}, {e, r}, {f, c},
 545                     {g, c}, {h, r}, {i, r}, {j, g}, {k, r}, {l, d}};
 546
 547   for (auto& relation : domination) {
 548     // Test immediate dominator.
 549     fprintf(
 550         stderr, "%c's immediate dominator is %c\n", relation.dominated.name,
 551         tree.getImmediateDominator(&relation.dominator).as<FakeNode>()->name);
 552     CHECK(tree.getImmediateDominator(&relation.dominated) ==
 553           JS::ubi::Node(&relation.dominator));
 554
 555     // Test the dominated set. Build up the expected dominated set based on
 556     // the set of nodes immediately dominated by this one in `domination`,
 557     // then iterate over the actual dominated set and check against the
 558     // expected set.
 559
 560     auto& node = relation.dominated;
 561     fprintf(stderr, "Checking %c's dominated set:\n", node.name);
 562
 563     js::HashSet<char> expectedDominatedSet(cx);
 564     for (auto& rel : domination) {
 565       if (&rel.dominator == &node) {
 566         fprintf(stderr, "    Expecting %c\n", rel.dominated.name);
 567         CHECK(expectedDominatedSet.putNew(rel.dominated.name));
 568       }
 569     }
 570
 571     auto maybeActualDominatedSet = tree.getDominatedSet(&node);
 572     CHECK(maybeActualDominatedSet.isSome());
 573     auto& actualDominatedSet = *maybeActualDominatedSet;
 574
 575     for (const auto& dominated : actualDominatedSet) {
 576       fprintf(stderr, "    Found %c\n", dominated.as<FakeNode>()->name);
 577       CHECK(expectedDominatedSet.has(dominated.as<FakeNode>()->name));
 578       expectedDominatedSet.remove(dominated.as<FakeNode>()->name);
 579     }
 580
 581     // Ensure we found them all and aren't still expecting nodes we never
 582     // got.
 583     CHECK(expectedDominatedSet.count() == 0);
 584
 585     fprintf(stderr, "Done checking %c's dominated set.\n\n", node.name);
 586   }
 587
 588   struct {
 589     FakeNode& node;
 590     JS::ubi::Node::Size retainedSize;
 591   } sizes[] = {
 592       {r, 13}, {a, 1}, {b, 1}, {c, 4}, {d, 2}, {e, 1}, {f, 1},
 593       {g, 2},  {h, 1}, {i, 1}, {j, 1}, {k, 1}, {l, 1},
 594   };
 595
 596   for (auto& expected : sizes) {
 597     JS::ubi::Node::Size actual = 0;
 598     CHECK(tree.getRetainedSize(&expected.node, nullptr, actual));
 599     CHECK(actual == expected.retainedSize);
 600   }
 601
 602   return true;
 603 }
 604 END_TEST(test_JS_ubi_DominatorTree)
 605
 606 BEGIN_TEST(test_JS_ubi_Node_scriptFilename) {
 607   JS::RootedValue val(cx);
 608   CHECK(
 609       evaluate("(function one() {                      \n"   // 1
 610                "  return (function two() {             \n"   // 2
 611                "    return (function three() {         \n"   // 3
 612                "      return function four() {};       \n"   // 4
 613                "    }());                              \n"   // 5
 614                "  }());                                \n"   // 6
 615                "}());                                  \n",  // 7
 616                "my-cool-filename.js", 1, &val));
 617
 618   CHECK(val.isObject());
 619   JS::RootedObject obj(cx, &val.toObject());
 620
 621   CHECK(obj->is<JSFunction>());
 622   JS::RootedFunction func(cx, &obj->as<JSFunction>());
 623
 624   JS::RootedScript script(cx, JSFunction::getOrCreateScript(cx, func));
 625   CHECK(script);
 626   CHECK(script->filename());
 627
 628   JS::ubi::Node node(script);
 629   const char* filename = node.scriptFilename();
 630   CHECK(filename);
 631   CHECK(strcmp(filename, script->filename()) == 0);
 632   CHECK(strcmp(filename, "my-cool-filename.js") == 0);
 633
 634   return true;
 635 }
 636 END_TEST(test_JS_ubi_Node_scriptFilename)
 637
 638 #define LAMBDA_CHECK(cond)                                                    \
 639   do {                                                                        \
 640     if (!(cond)) {                                                            \
 641       fprintf(stderr, "%s:%d:CHECK failed: " #cond "\n", __FILE__, __LINE__); \
 642       return false;                                                           \
 643     }                                                                         \
 644   } while (false)
 645
 646 static void dumpPath(JS::ubi::Path& path) {
 647   for (size_t i = 0; i < path.length(); i++) {
 648     fprintf(stderr, "path[%llu]->predecessor() = '%c'\n", (long long unsigned)i,
 649             path[i]->predecessor().as<FakeNode>()->name);
 650   }
 651 }
 652
 653 BEGIN_TEST(test_JS_ubi_ShortestPaths_no_path) {
 654   // Create the following graph:
 655   //
 656   //     .---.      .---.    .---.
 657   //     | a | <--> | c |    | b |
 658   //     '---'      '---'    '---'
 659   FakeNode a('a');
 660   FakeNode b('b');
 661   FakeNode c('c');
 662   CHECK(a.addEdgeTo(c));
 663   CHECK(c.addEdgeTo(a));
 664
 665   mozilla::Maybe<JS::ubi::ShortestPaths> maybeShortestPaths;
 666   {
 667     JS::AutoCheckCannotGC noGC(cx);
 668
 669     JS::ubi::NodeSet targets;
 670     CHECK(targets.put(&b));
 671
 672     maybeShortestPaths =
 673         JS::ubi::ShortestPaths::Create(cx, noGC, 10, &a, std::move(targets));
 674   }
 675
 676   CHECK(maybeShortestPaths);
 677   auto& paths = *maybeShortestPaths;
 678
 679   size_t numPathsFound = 0;
 680   bool ok = paths.forEachPath(&b, [&](JS::ubi::Path& path) {
 681     numPathsFound++;
 682     dumpPath(path);
 683     return true;
 684   });
 685   CHECK(ok);
 686   CHECK(numPathsFound == 0);
 687
 688   return true;
 689 }
 690 END_TEST(test_JS_ubi_ShortestPaths_no_path)
 691
 692 BEGIN_TEST(test_JS_ubi_ShortestPaths_one_path) {
 693   // Create the following graph:
 694   //
 695   //     .---.      .---.     .---.
 696   //     | a | <--> | c | --> | b |
 697   //     '---'      '---'     '---'
 698   FakeNode a('a');
 699   FakeNode b('b');
 700   FakeNode c('c');
 701   CHECK(a.addEdgeTo(c));
 702   CHECK(c.addEdgeTo(a));
 703   CHECK(c.addEdgeTo(b));
 704
 705   mozilla::Maybe<JS::ubi::ShortestPaths> maybeShortestPaths;
 706   {
 707     JS::AutoCheckCannotGC noGC(cx);
 708
 709     JS::ubi::NodeSet targets;
 710     CHECK(targets.put(&b));
 711
 712     maybeShortestPaths =
 713         JS::ubi::ShortestPaths::Create(cx, noGC, 10, &a, std::move(targets));
 714   }
 715
 716   CHECK(maybeShortestPaths);
 717   auto& paths = *maybeShortestPaths;
 718
 719   size_t numPathsFound = 0;
 720   bool ok = paths.forEachPath(&b, [&](JS::ubi::Path& path) {
 721     numPathsFound++;
 722
 723     dumpPath(path);
 724     LAMBDA_CHECK(path.length() == 2);
 725     LAMBDA_CHECK(path[0]->predecessor() == JS::ubi::Node(&a));
 726     LAMBDA_CHECK(path[1]->predecessor() == JS::ubi::Node(&c));
 727
 728     return true;
 729   });
 730
 731   CHECK(ok);
 732   CHECK(numPathsFound == 1);
 733
 734   return true;
 735 }
 736 END_TEST(test_JS_ubi_ShortestPaths_one_path)
 737
 738 BEGIN_TEST(test_JS_ubi_ShortestPaths_multiple_paths) {
 739   // Create the following graph:
 740   //
 741   //                .---.
 742   //          .-----| a |-----.
 743   //          |     '---'     |
 744   //          V       |       V
 745   //        .---.     |     .---.
 746   //        | b |     |     | d |
 747   //        '---'     |     '---'
 748   //          |       |       |
 749   //          V       |       V
 750   //        .---.     |     .---.
 751   //        | c |     |     | e |
 752   //        '---'     V     '---'
 753   //          |     .---.     |
 754   //          '---->| f |<----'
 755   //                '---'
 756   FakeNode a('a');
 757   FakeNode b('b');
 758   FakeNode c('c');
 759   FakeNode d('d');
 760   FakeNode e('e');
 761   FakeNode f('f');
 762   CHECK(a.addEdgeTo(b));
 763   CHECK(a.addEdgeTo(f));
 764   CHECK(a.addEdgeTo(d));
 765   CHECK(b.addEdgeTo(c));
 766   CHECK(c.addEdgeTo(f));
 767   CHECK(d.addEdgeTo(e));
 768   CHECK(e.addEdgeTo(f));
 769
 770   mozilla::Maybe<JS::ubi::ShortestPaths> maybeShortestPaths;
 771   {
 772     JS::AutoCheckCannotGC noGC(cx);
 773
 774     JS::ubi::NodeSet targets;
 775     CHECK(targets.put(&f));
 776
 777     maybeShortestPaths =
 778         JS::ubi::ShortestPaths::Create(cx, noGC, 10, &a, std::move(targets));
 779   }
 780
 781   CHECK(maybeShortestPaths);
 782   auto& paths = *maybeShortestPaths;
 783
 784   size_t numPathsFound = 0;
 785   bool ok = paths.forEachPath(&f, [&](JS::ubi::Path& path) {
 786     numPathsFound++;
 787     dumpPath(path);
 788
 789     switch (path.back()->predecessor().as<FakeNode>()->name) {
 790       case 'a': {
 791         LAMBDA_CHECK(path.length() == 1);
 792         break;
 793       }
 794
 795       case 'c': {
 796         LAMBDA_CHECK(path.length() == 3);
 797         LAMBDA_CHECK(path[0]->predecessor() == JS::ubi::Node(&a));
 798         LAMBDA_CHECK(path[1]->predecessor() == JS::ubi::Node(&b));
 799         LAMBDA_CHECK(path[2]->predecessor() == JS::ubi::Node(&c));
 800         break;
 801       }
 802
 803       case 'e': {
 804         LAMBDA_CHECK(path.length() == 3);
 805         LAMBDA_CHECK(path[0]->predecessor() == JS::ubi::Node(&a));
 806         LAMBDA_CHECK(path[1]->predecessor() == JS::ubi::Node(&d));
 807         LAMBDA_CHECK(path[2]->predecessor() == JS::ubi::Node(&e));
 808         break;
 809       }
 810
 811       default: {
 812         // Unexpected path!
 813         LAMBDA_CHECK(false);
 814       }
 815     }
 816
 817     return true;
 818   });
 819
 820   CHECK(ok);
 821   fprintf(stderr, "numPathsFound = %llu\n", (long long unsigned)numPathsFound);
 822   CHECK(numPathsFound == 3);
 823
 824   return true;
 825 }
 826 END_TEST(test_JS_ubi_ShortestPaths_multiple_paths)
 827
 828 BEGIN_TEST(test_JS_ubi_ShortestPaths_more_paths_than_max) {
 829   // Create the following graph:
 830   //
 831   //                .---.
 832   //          .-----| a |-----.
 833   //          |     '---'     |
 834   //          V       |       V
 835   //        .---.     |     .---.
 836   //        | b |     |     | d |
 837   //        '---'     |     '---'
 838   //          |       |       |
 839   //          V       |       V
 840   //        .---.     |     .---.
 841   //        | c |     |     | e |
 842   //        '---'     V     '---'
 843   //          |     .---.     |
 844   //          '---->| f |<----'
 845   //                '---'
 846   FakeNode a('a');
 847   FakeNode b('b');
 848   FakeNode c('c');
 849   FakeNode d('d');
 850   FakeNode e('e');
 851   FakeNode f('f');
 852   CHECK(a.addEdgeTo(b));
 853   CHECK(a.addEdgeTo(f));
 854   CHECK(a.addEdgeTo(d));
 855   CHECK(b.addEdgeTo(c));
 856   CHECK(c.addEdgeTo(f));
 857   CHECK(d.addEdgeTo(e));
 858   CHECK(e.addEdgeTo(f));
 859
 860   mozilla::Maybe<JS::ubi::ShortestPaths> maybeShortestPaths;
 861   {
 862     JS::AutoCheckCannotGC noGC(cx);
 863
 864     JS::ubi::NodeSet targets;
 865     CHECK(targets.put(&f));
 866
 867     maybeShortestPaths =
 868         JS::ubi::ShortestPaths::Create(cx, noGC, 1, &a, std::move(targets));
 869   }
 870
 871   CHECK(maybeShortestPaths);
 872   auto& paths = *maybeShortestPaths;
 873
 874   size_t numPathsFound = 0;
 875   bool ok = paths.forEachPath(&f, [&](JS::ubi::Path& path) {
 876     numPathsFound++;
 877     dumpPath(path);
 878     return true;
 879   });
 880
 881   CHECK(ok);
 882   fprintf(stderr, "numPathsFound = %llu\n", (long long unsigned)numPathsFound);
 883   CHECK(numPathsFound == 1);
 884
 885   return true;
 886 }
 887 END_TEST(test_JS_ubi_ShortestPaths_more_paths_than_max)
 888
 889 BEGIN_TEST(test_JS_ubi_ShortestPaths_multiple_edges_to_target) {
 890   // Create the following graph:
 891   //
 892   //                .---.
 893   //          .-----| a |-----.
 894   //          |     '---'     |
 895   //          |       |       |
 896   //          |x      |y      |z
 897   //          |       |       |
 898   //          |       V       |
 899   //          |     .---.     |
 900   //          '---->| b |<----'
 901   //                '---'
 902   FakeNode a('a');
 903   FakeNode b('b');
 904   CHECK(a.addEdgeTo(b, u"x"));
 905   CHECK(a.addEdgeTo(b, u"y"));
 906   CHECK(a.addEdgeTo(b, u"z"));
 907
 908   mozilla::Maybe<JS::ubi::ShortestPaths> maybeShortestPaths;
 909   {
 910     JS::AutoCheckCannotGC noGC(cx);
 911
 912     JS::ubi::NodeSet targets;
 913     CHECK(targets.put(&b));
 914
 915     maybeShortestPaths =
 916         JS::ubi::ShortestPaths::Create(cx, noGC, 10, &a, std::move(targets));
 917   }
 918
 919   CHECK(maybeShortestPaths);
 920   auto& paths = *maybeShortestPaths;
 921
 922   size_t numPathsFound = 0;
 923   bool foundX = false;
 924   bool foundY = false;
 925   bool foundZ = false;
 926
 927   bool ok = paths.forEachPath(&b, [&](JS::ubi::Path& path) {
 928     numPathsFound++;
 929     dumpPath(path);
 930
 931     LAMBDA_CHECK(path.length() == 1);
 932     LAMBDA_CHECK(path.back()->name());
 933     LAMBDA_CHECK(js_strlen(path.back()->name().get()) == 1);
 934
 935     auto c = uint8_t(path.back()->name().get()[0]);
 936     fprintf(stderr, "Edge name = '%c'\n", c);
 937
 938     switch (c) {
 939       case 'x': {
 940         foundX = true;
 941         break;
 942       }
 943       case 'y': {
 944         foundY = true;
 945         break;
 946       }
 947       case 'z': {
 948         foundZ = true;
 949         break;
 950       }
 951       default: {
 952         // Unexpected edge!
 953         LAMBDA_CHECK(false);
 954       }
 955     }
 956
 957     return true;
 958   });
 959
 960   CHECK(ok);
 961   fprintf(stderr, "numPathsFound = %llu\n", (long long unsigned)numPathsFound);
 962   CHECK(numPathsFound == 3);
 963   CHECK(foundX);
 964   CHECK(foundY);
 965   CHECK(foundZ);
 966
 967   return true;
 968 }
 969 END_TEST(test_JS_ubi_ShortestPaths_multiple_edges_to_target)
 970
 971 #undef LAMBDA_CHECK