1 files changed, 247 insertions, 0 deletions
diff --git a/js/src/devtools/rootAnalysis/callgraph.js b/js/src/devtools/rootAnalysis/callgraph.js
new file mode 100644
index 0000000000..9b198791e0
--- /dev/null
+++ b/js/src/devtools/rootAnalysis/callgraph.js
@@ -0,0 +1,247 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this file,
+ * You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+loadRelativeToScript('utility.js');
+loadRelativeToScript('annotations.js');
+loadRelativeToScript('CFG.js');
+
+// Map from csu => set of immediate subclasses
+var subclasses = new Map();
+
+// Map from csu => set of immediate superclasses
+var superclasses = new Map();
+
+// Map from "csu.name:nargs" => set of full method name
+var virtualDefinitions = new Map();
+
+// Every virtual method declaration, anywhere.
+//
+//   field : CFG of the field
+var virtualResolutionsSeen = new Set();
+
+// map is a map from names to sets of entries.
+function addToNamedSet(map, name, entry)
+{
+    if (!map.has(name))
+        map.set(name, new Set());
+    map.get(name).add(entry);
+}
+
+function fieldKey(csuName, field)
+{
+    // This makes a minimal attempt at dealing with overloading: it will not
+    // conflate two virtual methods with differing numbers of arguments. So
+    // far, that is all that has been needed.
+    var nargs = 0;
+    if (field.Type.Kind == "Function" && "TypeFunctionArguments" in field.Type)
+        nargs = field.Type.TypeFunctionArguments.Type.length;
+    return csuName + ":" + field.Name[0] + ":" + nargs;
+}
+
+// CSU is "Class/Struct/Union"
+function processCSU(csuName, csu)
+{
+    if (!("FunctionField" in csu))
+        return;
+    for (const field of csu.FunctionField) {
+        if (1 in field.Field) {
+            const superclass = field.Field[1].Type.Name;
+            const subclass = field.Field[1].FieldCSU.Type.Name;
+            assert(subclass == csuName);
+            addToNamedSet(subclasses, superclass, subclass);
+            addToNamedSet(superclasses, subclass, superclass);
+        }
+
+        if ("Variable" in field) {
+            // Note: not dealing with overloading correctly.
+            const name = field.Variable.Name[0];
+            addToNamedSet(virtualDefinitions, fieldKey(csuName, field.Field[0]), name);
+        }
+    }
+}
+
+// Return the nearest ancestor method definition, or all nearest definitions in
+// the case of multiple inheritance.
+function nearestAncestorMethods(csu, field)
+{
+    const key = fieldKey(csu, field);
+
+    if (virtualDefinitions.has(key))
+        return new Set(virtualDefinitions.get(key));
+
+    const functions = new Set();
+    if (superclasses.has(csu)) {
+        for (const parent of superclasses.get(csu))
+            functions.update(nearestAncestorMethods(parent, field));
+    }
+
+    return functions;
+}
+
+// Return [ instantiations, limits ], where instantiations is a Set of all
+// possible implementations of 'field' given static type 'initialCSU', plus
+// null if arbitrary other implementations are possible, and limits gives
+// information about what things are not possible within it (currently, that it
+// cannot GC).
+function findVirtualFunctions(initialCSU, field)
+{
+    const fieldName = field.Name[0];
+    const worklist = [initialCSU];
+    const functions = new Set();
+
+    // Loop through all methods of initialCSU (by looking at all methods of ancestor csus).
+    //
+    // If field is nsISupports::AddRef or ::Release, return an empty list and a
+    // boolean that says we assert that it cannot GC.
+    //
+    // If this is a method that is annotated to be dangerous (eg, it could be
+    // overridden with an implementation that could GC), then use null as a
+    // signal value that it should be considered to GC, even though we'll also
+    // collect all of the instantiations for other purposes.
+
+    while (worklist.length) {
+        const csu = worklist.pop();
+        if (isSuppressedVirtualMethod(csu, fieldName))
+            return [ new Set(), LIMIT_CANNOT_GC ];
+        if (isOverridableField(initialCSU, csu, fieldName)) {
+            // We will still resolve the virtual function call, because it's
+            // nice to have as complete a callgraph as possible for other uses.
+            // But push a token saying that we can run arbitrary code.
+            functions.add(null);
+        }
+
+        if (superclasses.has(csu))
+            worklist.push(...superclasses.get(csu));
+    }
+
+    // Now return a list of all the instantiations of the method named 'field'
+    // that could execute on an instance of initialCSU or a descendant class.
+
+    // Start with the class itself, or if it doesn't define the method, all
+    // nearest ancestor definitions.
+    functions.update(nearestAncestorMethods(initialCSU, field));
+
+    // Then recurse through all descendants to add in their definitions.
+
+    worklist.push(initialCSU);
+    while (worklist.length) {
+        const csu = worklist.pop();
+        const key = fieldKey(csu, field);
+
+        if (virtualDefinitions.has(key))
+            functions.update(virtualDefinitions.get(key));
+
+        if (subclasses.has(csu))
+            worklist.push(...subclasses.get(csu));
+    }
+
+    return [ functions, LIMIT_NONE ];
+}
+
+// Return a list of all callees that the given edge might be a call to. Each
+// one is represented by an object with a 'kind' field that is one of
+// ('direct', 'field', 'resolved-field', 'indirect', 'unknown'), though note
+// that 'resolved-field' is really a global record of virtual method
+// resolutions, indepedent of this particular edge.
+function getCallees(edge)
+{
+    if (edge.Kind != "Call")
+        return [];
+
+    const callee = edge.Exp[0];
+    if (callee.Kind == "Var") {
+        assert(callee.Variable.Kind == "Func");
+        return [{'kind': 'direct', 'name': callee.Variable.Name[0]}];
+    }
+
+    if (callee.Kind == "Int")
+        return []; // Intentional crash
+
+    assert(callee.Kind == "Drf");
+    const called = callee.Exp[0];
+    if (called.Kind == "Var") {
+        // indirect call through a variable.
+        return [{'kind': "indirect", 'variable': callee.Exp[0].Variable.Name[0]}];
+    }
+
+    if (called.Kind != "Fld") {
+        // unknown call target.
+        return [{'kind': "unknown"}];
+    }
+
+    const callees = [];
+    const field = callee.Exp[0].Field;
+    const fieldName = field.Name[0];
+    const csuName = field.FieldCSU.Type.Name;
+    let functions;
+    let limits = LIMIT_NONE;
+    if ("FieldInstanceFunction" in field) {
+        [ functions, limits ] = findVirtualFunctions(csuName, field);
+        callees.push({'kind': "field", 'csu': csuName, 'field': fieldName,
+                      'limits': limits, 'isVirtual': true});
+    } else {
+        functions = new Set([null]); // field call
+    }
+
+    // Known set of virtual call targets. Treat them as direct calls to all
+    // possible resolved types, but also record edges from this field call to
+    // each final callee. When the analysis is checking whether an edge can GC
+    // and it sees an unrooted pointer held live across this field call, it
+    // will know whether any of the direct callees can GC or not.
+    const targets = [];
+    let fullyResolved = true;
+    for (const name of functions) {
+        if (name === null) {
+            // Unknown set of call targets, meaning either a function pointer
+            // call ("field call") or a virtual method that can be overridden
+            // in extensions. Use the isVirtual property so that callers can
+            // tell which case holds.
+            callees.push({'kind': "field", 'csu': csuName, 'field': fieldName,
+                          'limits': limits,
+			  'isVirtual': "FieldInstanceFunction" in field});
+            fullyResolved = false;
+        } else {
+            targets.push({'kind': "direct", name, limits });
+        }
+    }
+    if (fullyResolved)
+        callees.push({'kind': "resolved-field", 'csu': csuName, 'field': fieldName, 'callees': targets});
+
+    return callees;
+}
+
+function loadTypes(type_xdb_filename) {
+    const xdb = xdbLibrary();
+    xdb.open(type_xdb_filename);
+
+    const minStream = xdb.min_data_stream();
+    const maxStream = xdb.max_data_stream();
+
+    for (var csuIndex = minStream; csuIndex <= maxStream; csuIndex++) {
+        const csu = xdb.read_key(csuIndex);
+        const data = xdb.read_entry(csu);
+        const json = JSON.parse(data.readString());
+        processCSU(csu.readString(), json[0]);
+
+        xdb.free_string(csu);
+        xdb.free_string(data);
+    }
+}
+
+function loadTypesWithCache(type_xdb_filename, cache_filename) {
+    try {
+        const cacheAB = os.file.readFile(cache_filename, "binary");
+        const cb = serialize();
+        cb.clonebuffer = cacheAB.buffer;
+        const cacheData = deserialize(cb);
+        subclasses = cacheData.subclasses;
+        superclasses = cacheData.superclasses;
+        virtualDefinitions = cacheData.virtualDefinitions;
+    } catch (e) {
+        loadTypes(type_xdb_filename);
+        const cb = serialize({subclasses, superclasses, virtualDefinitions});
+        os.file.writeTypedArrayToFile(cache_filename,
+                                      new Uint8Array(cb.arraybuffer));
+    }
+}