michael@0: /* -*- Mode: Javascript; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
michael@0: 
michael@0: "use strict";
michael@0: 
michael@0: loadRelativeToScript('utility.js');
michael@0: loadRelativeToScript('annotations.js');
michael@0: loadRelativeToScript('CFG.js');
michael@0: 
michael@0: var subclasses = {};
michael@0: var superclasses = {};
michael@0: var classFunctions = {};
michael@0: 
michael@0: var fieldCallSeen = {};
michael@0: 
michael@0: function addClassEntry(index, name, other)
michael@0: {
michael@0:     if (!(name in index)) {
michael@0:         index[name] = [other];
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     for (var entry of index[name]) {
michael@0:         if (entry == other)
michael@0:             return;
michael@0:     }
michael@0: 
michael@0:     index[name].push(other);
michael@0: }
michael@0: 
michael@0: // CSU is "Class/Struct/Union"
michael@0: function processCSU(csuName, csu)
michael@0: {
michael@0:     if (!("FunctionField" in csu))
michael@0:         return;
michael@0:     for (var field of csu.FunctionField) {
michael@0:         if (1 in field.Field) {
michael@0:             var superclass = field.Field[1].Type.Name;
michael@0:             var subclass = field.Field[1].FieldCSU.Type.Name;
michael@0:             assert(subclass == csuName);
michael@0:             addClassEntry(subclasses, superclass, subclass);
michael@0:             addClassEntry(superclasses, subclass, superclass);
michael@0:         }
michael@0:         if ("Variable" in field) {
michael@0:             // Note: not dealing with overloading correctly.
michael@0:             var name = field.Variable.Name[0];
michael@0:             var key = csuName + ":" + field.Field[0].Name[0];
michael@0:             if (!(key in classFunctions))
michael@0:                 classFunctions[key] = [];
michael@0:             classFunctions[key].push(name);
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: function findVirtualFunctions(initialCSU, field, suppressed)
michael@0: {
michael@0:     var worklist = [initialCSU];
michael@0: 
michael@0:     // Virtual call targets on subclasses of nsISupports may be incomplete,
michael@0:     // if the interface is scriptable. Just treat all indirect calls on
michael@0:     // nsISupports objects as potentially GC'ing, except AddRef/Release
michael@0:     // which should never enter the JS engine (even when calling dtors).
michael@0:     while (worklist.length) {
michael@0:         var csu = worklist.pop();
michael@0:         if (csu == "nsISupports" && (field == "AddRef" || field == "Release")) {
michael@0:             suppressed[0] = true;
michael@0:             return [];
michael@0:         }
michael@0:         if (isOverridableField(initialCSU, csu, field))
michael@0:             return null;
michael@0: 
michael@0:         if (csu in superclasses) {
michael@0:             for (var superclass of superclasses[csu])
michael@0:                 worklist.push(superclass);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     var functions = [];
michael@0:     var worklist = [csu];
michael@0: 
michael@0:     while (worklist.length) {
michael@0:         var csu = worklist.pop();
michael@0:         var key = csu + ":" + field;
michael@0: 
michael@0:         if (key in classFunctions) {
michael@0:             for (var name of classFunctions[key])
michael@0:                 functions.push(name);
michael@0:         }
michael@0: 
michael@0:         if (csu in subclasses) {
michael@0:             for (var subclass of subclasses[csu])
michael@0:                 worklist.push(subclass);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return functions;
michael@0: }
michael@0: 
michael@0: var memoized = {};
michael@0: var memoizedCount = 0;
michael@0: 
michael@0: function memo(name)
michael@0: {
michael@0:     if (!(name in memoized)) {
michael@0:         memoizedCount++;
michael@0:         memoized[name] = "" + memoizedCount;
michael@0:         print("#" + memoizedCount + " " + name);
michael@0:     }
michael@0:     return memoized[name];
michael@0: }
michael@0: 
michael@0: var seenCallees = null;
michael@0: var seenSuppressedCallees = null;
michael@0: 
michael@0: // Return a list of all callees that the given edge might be a call to. Each
michael@0: // one is represented by an object with a 'kind' field that is one of
michael@0: // ('direct', 'field', 'indirect', 'unknown').
michael@0: function getCallees(edge)
michael@0: {
michael@0:     if (edge.Kind != "Call")
michael@0:         return [];
michael@0: 
michael@0:     var callee = edge.Exp[0];
michael@0:     var callees = [];
michael@0:     if (callee.Kind == "Var") {
michael@0:         assert(callee.Variable.Kind == "Func");
michael@0:         callees.push({'kind': 'direct', 'name': callee.Variable.Name[0]});
michael@0:     } else {
michael@0:         assert(callee.Kind == "Drf");
michael@0:         if (callee.Exp[0].Kind == "Fld") {
michael@0:             var field = callee.Exp[0].Field;
michael@0:             var fieldName = field.Name[0];
michael@0:             var csuName = field.FieldCSU.Type.Name;
michael@0:             var functions = null;
michael@0:             if ("FieldInstanceFunction" in field) {
michael@0:                 var suppressed = [ false ];
michael@0:                 functions = findVirtualFunctions(csuName, fieldName, suppressed);
michael@0:                 if (suppressed[0]) {
michael@0:                     // Field call known to not GC; mark it as suppressed so
michael@0:                     // direct invocations will be ignored
michael@0:                     callees.push({'kind': "field", 'csu': csuName, 'field': fieldName,
michael@0:                                   'suppressed': true});
michael@0:                 }
michael@0:             }
michael@0:             if (functions) {
michael@0:                 // Known set of virtual call targets. Treat them as direct
michael@0:                 // calls to all possible resolved types, but also record edges
michael@0:                 // from this field call to each final callee. When the analysis
michael@0:                 // is checking whether an edge can GC and it sees an unrooted
michael@0:                 // pointer held live across this field call, it will know
michael@0:                 // whether any of the direct callees can GC or not.
michael@0:                 var targets = [];
michael@0:                 for (var name of functions) {
michael@0:                     callees.push({'kind': "direct", 'name': name});
michael@0:                     targets.push({'kind': "direct", 'name': name});
michael@0:                 }
michael@0:                 callees.push({'kind': "resolved-field", 'csu': csuName, 'field': fieldName, 'callees': targets});
michael@0:             } else {
michael@0:                 // Unknown set of call targets. Non-virtual field call,
michael@0:                 // or virtual call on an nsISupports object.
michael@0:                 callees.push({'kind': "field", 'csu': csuName, 'field': fieldName});
michael@0:             }
michael@0:         } else if (callee.Exp[0].Kind == "Var") {
michael@0:             // indirect call through a variable.
michael@0:             callees.push({'kind': "indirect", 'variable': callee.Exp[0].Variable.Name[0]});
michael@0:         } else {
michael@0:             // unknown call target.
michael@0:             callees.push({'kind': "unknown"});
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return callees;
michael@0: }
michael@0: 
michael@0: var lastline;
michael@0: function printOnce(line)
michael@0: {
michael@0:     if (line != lastline) {
michael@0:         print(line);
michael@0:         lastline = line;
michael@0:     }
michael@0: }
michael@0: 
michael@0: function processBody(caller, body)
michael@0: {
michael@0:     if (!('PEdge' in body))
michael@0:         return;
michael@0: 
michael@0:     lastline = null;
michael@0:     for (var edge of body.PEdge) {
michael@0:         if (edge.Kind != "Call")
michael@0:             continue;
michael@0:         var edgeSuppressed = false;
michael@0:         var seen = seenCallees;
michael@0:         if (edge.Index[0] in body.suppressed) {
michael@0:             edgeSuppressed = true;
michael@0:             seen = seenSuppressedCallees;
michael@0:         }
michael@0:         for (var callee of getCallees(edge)) {
michael@0:             var prologue = (edgeSuppressed || callee.suppressed) ? "SUPPRESS_GC " : "";
michael@0:             prologue += memo(caller) + " ";
michael@0:             if (callee.kind == 'direct') {
michael@0:                 if (!(callee.name in seen)) {
michael@0:                     seen[name] = true;
michael@0:                     printOnce("D " + prologue + memo(callee.name));
michael@0:                 }
michael@0:             } else if (callee.kind == 'field') {
michael@0:                 var { csu, field } = callee;
michael@0:                 printOnce("F " + prologue + "CLASS " + csu + " FIELD " + field);
michael@0:             } else if (callee.kind == 'resolved-field') {
michael@0:                 // Fully-resolved field call (usually a virtual method). Record
michael@0:                 // the callgraph edges. Do not consider suppression, since it
michael@0:                 // is local to this callsite and we are writing out a global
michael@0:                 // record here.
michael@0:                 //
michael@0:                 // Any field call that does *not* have an R entry must be
michael@0:                 // assumed to call anything.
michael@0:                 var { csu, field, callees } = callee;
michael@0:                 var fullFieldName = csu + "." + field;
michael@0:                 if (!(fullFieldName in fieldCallSeen)) {
michael@0:                     fieldCallSeen[fullFieldName] = true;
michael@0:                     for (var target of callees)
michael@0:                         printOnce("R " + memo(fullFieldName) + " " + memo(target.name));
michael@0:                 }
michael@0:             } else if (callee.kind == 'indirect') {
michael@0:                 printOnce("I " + prologue + "VARIABLE " + callee.variable);
michael@0:             } else if (callee.kind == 'unknown') {
michael@0:                 printOnce("I " + prologue + "VARIABLE UNKNOWN");
michael@0:             } else {
michael@0:                 printErr("invalid " + callee.kind + " callee");
michael@0:                 debugger;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: var callgraph = {};
michael@0: 
michael@0: var xdb = xdbLibrary();
michael@0: xdb.open("src_comp.xdb");
michael@0: 
michael@0: var minStream = xdb.min_data_stream();
michael@0: var maxStream = xdb.max_data_stream();
michael@0: 
michael@0: for (var csuIndex = minStream; csuIndex <= maxStream; csuIndex++) {
michael@0:     var csu = xdb.read_key(csuIndex);
michael@0:     var data = xdb.read_entry(csu);
michael@0:     var json = JSON.parse(data.readString());
michael@0:     processCSU(csu.readString(), json[0]);
michael@0: 
michael@0:     xdb.free_string(csu);
michael@0:     xdb.free_string(data);
michael@0: }
michael@0: 
michael@0: xdb.open("src_body.xdb");
michael@0: 
michael@0: printErr("Finished loading data structures");
michael@0: 
michael@0: var minStream = xdb.min_data_stream();
michael@0: var maxStream = xdb.max_data_stream();
michael@0: 
michael@0: for (var nameIndex = minStream; nameIndex <= maxStream; nameIndex++) {
michael@0:     var name = xdb.read_key(nameIndex);
michael@0:     var data = xdb.read_entry(name);
michael@0:     functionBodies = JSON.parse(data.readString());
michael@0:     for (var body of functionBodies)
michael@0:         body.suppressed = [];
michael@0:     for (var body of functionBodies) {
michael@0:         for (var [pbody, id] of allRAIIGuardedCallPoints(body, isSuppressConstructor))
michael@0:             pbody.suppressed[id] = true;
michael@0:     }
michael@0: 
michael@0:     seenCallees = {};
michael@0:     seenSuppressedCallees = {};
michael@0: 
michael@0:     var functionName = name.readString();
michael@0:     for (var body of functionBodies)
michael@0:         processBody(functionName, body);
michael@0: 
michael@0:     xdb.free_string(name);
michael@0:     xdb.free_string(data);
michael@0: }