Ziele Untersuchung
mit Columbo Integrität von
Datenbanken Interaktion und
Portierbarkeit Ergonomie der
Schnittstellen

Angebot Produkte Projekt Beratung

Mittel Analytik Modellierung Sprachen Algebra Logik Hardware Denken Kreativität

Zusammenhänge Gesellschaft Wirtschaft Branche Firma


products/sources/formale Sprachen/C/Firefox/js/src/devtools/rootAnalysis/ (Browser von der Mozilla Stiftung Version 136.0.1^©) Datei vom 10.2.2025 mit Größe 15 kB

Quellverzeichnis computeCallgraph.js Sprache: JAVA

/* 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/. */

/* -*- indent-tabs-mode: nil; js-indent-level: 4 -*- */

"use strict";

loadRelativeToScript('callgraph.js');

var options = parse_options([
    {
        name: '--verbose',
        type: 'bool'
    },
    {
        name: '--function',
        type: 'string'
    },
    {
        name: 'typeInfo_filename',
        type: 'string',
        default: "typeInfo.txt"
    },
    {
        name: 'callgraphOut_filename',
        type: 'string',
        default: "rawcalls.txt"
    },
    {
        name: 'batch',
        default: 1,
        type: 'number'
    },
    {
        name: 'numBatches',
        default: 1,
        type: 'number'
    },
]);

var origOut = os.file.redirect(options.callgraphOut_filename);

var memoized = new Map();

var unmangled2id = new Set();

// Insert a string into the name table and return the ID. Do not use for
// functions, which must be handled specially.
function getId(name)
{
    let id = memoized.get(name);
    if (id !== undefined)
        return id;

    id = memoized.size + 1;
    memoized.set(name, id);
    print(`#${id} ${name}`);

    return id;
}

// Split a function into mangled and unmangled parts and return the ID for the
// function.
function functionId(name)
{
    const [mangled, unmangled] = splitFunction(name);
    const id = getId(mangled);

    // Only produce a mangled -> unmangled mapping once, unless there are
    // multiple unmangled names for the same mangled name.
    if (unmangled2id.has(unmangled))
        return id;

    print(`= ${id} ${unmangled}`);
    unmangled2id.add(unmangled);
    return id;
}

var lastline;
function printOnce(line)
{
    if (line != lastline) {
        print(line);
        lastline = line;
    }
}

// Returns a table mapping function name to lists of
// [annotation-name, annotation-value] pairs:
//   { function-name => [ [annotation-name, annotation-value] ] }
//
// Note that sixgill will only store certain attributes (annotation-names), so
// this won't be *all* the attributes in the source, just the ones that sixgill
// watches for.
function getAllAttributes(body)
{
    var all_annotations = {};
    for (var v of (body.DefineVariable || [])) {
        if (v.Variable.Kind != 'Func')
            continue;
        var name = v.Variable.Name[0];
        var annotations = all_annotations[name] = [];

        for (var ann of (v.Type.Annotation || [])) {
            annotations.push(ann.Name);
        }
    }

    return all_annotations;
}

// Get just the annotations understood by the hazard analysis.
function getAnnotations(functionName, body) {
    var tags = new Set();
    var attributes = getAllAttributes(body);
    if (functionName in attributes) {
        for (var [ annName, annValue ] of attributes[functionName]) {
            if (annName == 'annotate')
                tags.add(annValue);
        }
    }
    return tags;
}

// Scan through a function body, pulling out all annotations and calls and
// recording them in callgraph.txt.
function processBody(functionName, body, functionBodies)
{
    if (!('PEdge' in body))
        return;

    for (var tag of getAnnotations(functionName, body).values()) {
        const id = functionId(functionName);
        print(`T ${id} ${tag}`);
        if (tag == "Calls JSNatives")
            printOnce(`D ${id} ${functionId("(js-code)")}`);
    }

    // Set of all callees that have been output so far, in order to suppress
    // repeated callgraph edges from being recorded. This uses a Map from
    // callees to limit sets, because we don't want a limited edge to prevent
    // an unlimited edge from being recorded later. (So an edge will be skipped
    // if it exists and is at least as limited as the previously seen edge.)
    //
    // Limit sets are implemented as integers interpreted as bitfields.
    //
    var seen = new Map();

    lastline = null;
    for (var edge of body.PEdge) {
        if (edge.Kind != "Call")
            continue;

        // The attrs (eg ATTR_GC_SUPPRESSED) are determined by whatever RAII
        // scopes might be active, which have been computed previously for all
        // points in the body.
        const scopeAttrs = body.attrs[edge.Index[0]] | 0;

        for (const { callee, attrs } of getCallees(body, edge, scopeAttrs, functionBodies)) {
            // Some function names will be synthesized by manually constructing
            // their names. Verify that we managed to synthesize an existing function.
            // This cannot be done later with either the callees or callers tables,
            // because the function may be an otherwise uncalled leaf.
            if (attrs & ATTR_SYNTHETIC) {
                assertFunctionExists(callee.name);
            }

            // Individual callees may have additional attrs. The only such
            // bit currently is that nsISupports.{AddRef,Release} are assumed
            // to never GC.
            let prologue = attrs ? `/${attrs} ` : "";
            prologue += functionId(functionName) + " ";
            if (callee.kind == 'direct') {
                const prev_attrs = seen.has(callee.name) ? seen.get(callee.name) : ATTRS_UNVISITED;
                if (prev_attrs & ~attrs) {
                    // Only output an edge if it loosens a limit.
                    seen.set(callee.name, prev_attrs & attrs);
                    printOnce("D " + prologue + functionId(callee.name));
                }
            } else if (callee.kind == 'field') {
                var { csu, field, isVirtual } = callee;
                const tag = isVirtual ? 'V' : 'F';
                const fullfield = `${csu}.${field}`;
                printOnce(`${tag} ${prologue}${getId(fullfield)} CLASS ${csu} FIELD ${field}`);
            } else if (callee.kind == 'resolved-field') {
                // Fully-resolved field (virtual method) call. Record the
                // callgraph edges. Do not consider attrs, since they are local
                // to this callsite and we are writing out a global record
                // here.
                //
                // Any field call that does *not* have an R entry must be
                // assumed to call anything.
                var { csu, field, callees } = callee;
                var fullFieldName = csu + "." + field;
                if (!virtualResolutionsSeen.has(fullFieldName)) {
                    virtualResolutionsSeen.add(fullFieldName);
                    for (var target of callees)
                        printOnce("R " + getId(fullFieldName) + " " + functionId(target.name));
                }
            } else if (callee.kind == 'indirect') {
                printOnce("I " + prologue + "VARIABLE " + callee.variable);
            } else if (callee.kind == 'unknown') {
                printOnce("I " + prologue + "VARIABLE UNKNOWN");
            } else {
                printErr("invalid " + callee.kind + " callee");
                debugger;
            }
        }
    }
}

// Reserve IDs for special function names.

// represents anything that can run JS
assert(ID.jscode == functionId("(js-code)"));

// function pointers will get an edge to this in loadCallgraph.js; only the ID
// reservation is present in callgraph.txt
assert(ID.anyfunc == functionId("(any-function)"));

// same as above, but for fields annotated to never GC
assert(ID.nogcfunc == functionId("(nogc-function)"));

// garbage collection
assert(ID.gc == functionId("(GC)"));

var typeInfo = loadTypeInfo(options.typeInfo_filename);

loadTypes("src_comp.xdb");

// Arbitrary JS code must always be assumed to GC. In real code, there would
// always be a path anyway through some arbitrary JSNative, but this route will be shorter.
print(`D ${ID.jscode} ${ID.gc}`);

// An unknown function is assumed to GC.
print(`D ${ID.anyfunc} ${ID.gc}`);

// Output call edges for all virtual methods defined anywhere, from
// Class.methodname to what a (dynamic) instance of Class would run when
// methodname was called (either Class::methodname() if defined, or some
// Base::methodname() for inherited method definitions).
for (const [fieldkey, methods] of virtualDefinitions) {
    const caller = getId(fieldkey);
    for (const name of methods) {
        const callee = functionId(name);
        printOnce(`D ${caller} ${callee}`);
    }
}

// Output call edges from C.methodname -> S.methodname for all subclasses S of
// class C. This is for when you are calling methodname on a pointer/ref of
// dynamic type C, so that the callgraph contains calls to all descendant
// subclasses' implementations.
for (const [csu, methods] of virtualDeclarations) {
    for (const {field, dtor} of methods) {
        const caller = getId(fieldKey(csu, field));
        if (virtualCanRunJS(csu, field.Name[0]))
            printOnce(`D ${caller} ${functionId("(js-code)")}`);
        if (dtor)
            printOnce(`D ${caller} ${functionId(dtor)}`);
        if (!subclasses.has(csu))
            continue;
        for (const sub of subclasses.get(csu)) {
            printOnce(`D ${caller} ${getId(fieldKey(sub, field))}`);
        }
    }
}

var xdb = xdbLibrary();
xdb.open("src_body.xdb");

if (options.verbose) {
    printErr("Finished loading data structures");
}

var minStream = xdb.min_data_stream();
var maxStream = xdb.max_data_stream();

if (options.function) {
    var index = xdb.lookup_key(options.function);
    if (!index) {
        printErr("Function not found");
        quit(1);
    }
    minStream = maxStream = index;
}

function assertFunctionExists(name) {
    var data = xdb.read_entry(name);
    assert(data.contents != 0, `synthetic function '${name}' not found!`);
}

function process(functionName, functionBodies)
{
    for (var body of functionBodies)
        body.attrs = [];

    for (var body of functionBodies) {
        for (var [pbody, id, attrs] of allRAIIGuardedCallPoints(typeInfo, functionBodies, body, isLimitConstructor)) {
            pbody.attrs[id] = attrs;
        }
    }

    if (options.function) {
        debugger;
    }
    for (var body of functionBodies) {
        processBody(functionName, body, functionBodies);
    }

    // Not strictly necessary, but add an edge from the synthetic "(js-code)"
    // to RunScript to allow better stacks than just randomly selecting a
    // JSNative to blame things on.
    if (functionName.includes("js::RunScript"))
        print(`D ${functionId("(js-code)")} ${functionId(functionName)}`);

    // GCC generates multiple constructors and destructors ("in-charge" and
    // "not-in-charge") to handle virtual base classes. They are normally
    // identical, and it appears that GCC does some magic to alias them to the
    // same thing. But this aliasing is not visible to the analysis. So we'll
    // add a dummy call edge from "foo" -> "foo *INTERNAL* ", since only "foo"
    // will show up as called but only "foo *INTERNAL* " will be emitted in the
    // case where the constructors are identical.
    //
    // This is slightly conservative in the case where they are *not*
    // identical, but that should be rare enough that we don't care.
    var markerPos = functionName.indexOf(internalMarker);
    if (markerPos > 0) {
        var inChargeXTor = functionName.replace(internalMarker, "");
        printOnce("D " + functionId(inChargeXTor) + " " + functionId(functionName));
    }

    const [ mangled, unmangled ] = splitFunction(functionName);

    // Further note: from https://itanium-cxx-abi.github.io/cxx-abi/abi.html the
    // different kinds of constructors/destructors are:
    // C1 # complete object constructor
    // C2 # base object constructor
    // C3 # complete object allocating constructor
    // D0 # deleting destructor
    // D1 # complete object destructor
    // D2 # base object destructor
    //
    // In actual practice, I have observed C4 and D4 xtors generated by gcc
    // 4.9.3 (but not 4.7.3). The gcc source code says:
    //
    //   /* This is the old-style "[unified]" constructor.
    //      In some cases, we may emit this function and call
    //      it from the clones in order to share code and save space.  */
    //
    // Unfortunately, that "call... from the clones" does not seem to appear in
    // the CFG we get from GCC. So if we see a C4 constructor or D4 destructor,
    // inject an edge to it from C1, C2, and C3 (or D1, D2, and D3). (Note that
    // C3 isn't even used in current GCC, but add the edge anyway just in
    // case.)
    //
    // from gcc/cp/mangle.c:
    //
    // <special-name> ::= D0 # deleting (in-charge) destructor
    //                ::= D1 # complete object (in-charge) destructor
    //                ::= D2 # base object (not-in-charge) destructor
    // <special-name> ::= C1   # complete object constructor
    //                ::= C2   # base object constructor
    //                ::= C3   # complete object allocating constructor
    //
    // Currently, allocating constructors are never used.
    //
    if (functionName.indexOf("C4") != -1) {
        // E terminates the method name (and precedes the method parameters).
        // If eg "C4E" shows up in the mangled name for another reason, this
        // will create bogus edges in the callgraph. But it will affect little
        // and is somewhat difficult to avoid, so we will live with it.
        //
        // Another possibility! A templatized constructor will contain C4I...E
        // for template arguments.
        //
        for (let [synthetic, variant, desc] of [
            ['C4E', 'C1E', 'complete_ctor'],
            ['C4E', 'C2E', 'base_ctor'],
            ['C4E', 'C3E', 'complete_alloc_ctor'],
            ['C4I', 'C1I', 'complete_ctor'],
            ['C4I', 'C2I', 'base_ctor'],
            ['C4I', 'C3I', 'complete_alloc_ctor']])
        {
            if (mangled.indexOf(synthetic) == -1)
                continue;

            let variant_mangled = mangled.replace(synthetic, variant);
            let variant_full = `${variant_mangled}$${unmangled} [[${desc}]]`;
            printOnce("D " + functionId(variant_full) + " " + functionId(functionName));
        }
    }

    // For destructors:
    //
    // I've never seen D4Ev() + D4Ev(int32), only one or the other. So
    // for a D4Ev of any sort, create:
    //
    //   D0() -> D1()  # deleting destructor calls complete destructor, then deletes
    //   D1() -> D2()  # complete destructor calls base destructor, then destroys virtual bases
    //   D2() -> D4(?) # base destructor might be aliased to unified destructor
    //                 # use whichever one is defined, in-charge or not.
    //                 # ('?') means either () or (int32).
    //
    // Note that this doesn't actually make sense -- D0 and D1 should be
    // in-charge, but gcc doesn't seem to give them the in-charge parameter?!
    //
    if (functionName.indexOf("D4Ev") != -1 && functionName.indexOf("::~") != -1) {
        const not_in_charge_dtor = functionName.replace("(int32)", "()");
        const D0 = not_in_charge_dtor.replace("D4Ev", "D0Ev") + " [[deleting_dtor]]";
        const D1 = not_in_charge_dtor.replace("D4Ev", "D1Ev") + " [[complete_dtor]]";
        const D2 = not_in_charge_dtor.replace("D4Ev", "D2Ev") + " [[base_dtor]]";
        printOnce("D " + functionId(D0) + " " + functionId(D1));
        printOnce("D " + functionId(D1) + " " + functionId(D2));
        printOnce("D " + functionId(D2) + " " + functionId(functionName));
    }

    if (isJSNative(mangled))
        printOnce(`D ${functionId("(js-code)")} ${functionId(functionName)}`);
}

var start = batchStart(options.batch, options.numBatches, minStream, maxStream);
var end = batchLast(options.batch, options.numBatches, minStream, maxStream);

for (var nameIndex = start; nameIndex <= end; nameIndex++) {
    var name = xdb.read_key(nameIndex);
    var data = xdb.read_entry(name);
    process(name.readString(), JSON.parse(data.readString()));
    xdb.free_string(name);
    xdb.free_string(data);
}

os.file.close(os.file.redirect(origOut));

quality76%

¤ Dauer der Verarbeitung: 0.32 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.