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