path: root/js/src/devtools/rootAnalysis/analyzeHeapWrites.js

/* 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('utility.js');
loadRelativeToScript('annotations.js');
loadRelativeToScript('callgraph.js');
loadRelativeToScript('dumpCFG.js');

///////////////////////////////////////////////////////////////////////////////
// Annotations
///////////////////////////////////////////////////////////////////////////////

function checkExternalFunction(entry)
{
    var whitelist = [
        "__builtin_clz",
        "__builtin_expect",
        "isprint",
        "ceilf",
        "floorf",
        /^rusturl/,
        "memcmp",
        "strcmp",
        "fmod",
        "floor",
        "ceil",
        "atof",
        /memchr/,
        "strlen",
        /Servo_DeclarationBlock_GetCssText/,
        "Servo_GetArcStringData",
        "Servo_IsWorkerThread",
        /nsIFrame::AppendOwnedAnonBoxes/,
        // Assume that atomic accesses are threadsafe.
        /^__atomic_/,
    ];
    if (entry.matches(whitelist))
        return;

    // memcpy and memset are safe if the target pointer is threadsafe.
    const simpleWrites = [
        "memcpy",
        "memset",
        "memmove",
    ];

    if (entry.isSafeArgument(1) && simpleWrites.includes(entry.name))
        return;

    dumpError(entry, null, "External function");
}

function hasThreadsafeReferenceCounts(entry, regexp)
{
    // regexp should match some nsISupports-operating function and produce the
    // name of the nsISupports class via exec().

    // nsISupports classes which have threadsafe reference counting.
    var whitelist = [
        "nsIRunnable",

        // I don't know if these always have threadsafe refcounts.
        "nsAtom",
        "nsIPermissionManager",
        "nsIURI",
    ];

    var match = regexp.exec(entry.name);
    return match && nameMatchesArray(match[1], whitelist);
}

function checkOverridableVirtualCall(entry, location, callee)
{
    // We get here when a virtual call is made on a structure which might be
    // overridden by script or by a binary extension. This includes almost
    // everything under nsISupports, however, so for the most part we ignore
    // this issue. The exception is for nsISupports AddRef/Release, which are
    // not in general threadsafe and whose overrides will not be generated by
    // the callgraph analysis.
    if (callee != "nsISupports.AddRef" && callee != "nsISupports.Release")
        return;

    if (hasThreadsafeReferenceCounts(entry, /::~?nsCOMPtr\(.*?\[with T = (.*?)\]$/))
        return;
    if (hasThreadsafeReferenceCounts(entry, /RefPtrTraits.*?::Release.*?\[with U = (.*?)\]/))
        return;
    if (hasThreadsafeReferenceCounts(entry, /nsCOMPtr<T>::assign_assuming_AddRef.*?\[with T = (.*?)\]/))
        return;
    if (hasThreadsafeReferenceCounts(entry, /nsCOMPtr<T>::assign_with_AddRef.*?\[with T = (.*?)\]/))
        return;

    // Watch for raw addref/release.
    var whitelist = [
        "Gecko_AddRefAtom",
        "Gecko_ReleaseAtom",
        /nsPrincipal::Get/,
        /CounterStylePtr::Reset/,
    ];
    if (entry.matches(whitelist))
        return;

    dumpError(entry, location, "AddRef/Release on nsISupports");
}

function checkIndirectCall(entry, location, callee)
{
    var name = entry.name;

    // These hash table callbacks should be threadsafe.
    if (/PLDHashTable/.test(name) && (/matchEntry/.test(callee) || /hashKey/.test(callee)))
        return;
    if (/PL_HashTable/.test(name) && /keyCompare/.test(callee))
        return;

    dumpError(entry, location, "Indirect call " + callee);
}

function checkVariableAssignment(entry, location, variable)
{
    var name = entry.name;

    dumpError(entry, location, "Variable assignment " + variable);
}

// Annotations for function parameters, based on function name and parameter
// name + type.
function treatAsSafeArgument(entry, varName, csuName)
{
    var whitelist = [
        // These iterator classes should all be thread local. They are passed
        // in to some Servo bindings and are created on the heap by others, so
        // just ignore writes to them.
        [null, null, /StyleChildrenIterator/],
        [null, null, /ExplicitChildIterator/],

        // The use of BeginReading() to instantiate this class confuses the
        // analysis.
        [null, null, /nsReadingIterator/],

        // These classes are passed to some Servo bindings to fill in.
        [/^Gecko_/, null, "nsStyleImageLayers"],
        [/^Gecko_/, null, /FontFamilyList/],

        // RawGeckoBorrowedNode thread-mutable parameters.
        ["Gecko_SetNodeFlags", "aNode", null],
        ["Gecko_UnsetNodeFlags", "aNode", null],

        // Various Servo binding out parameters. This is a mess and there needs
        // to be a way to indicate which params are out parameters, either using
        // an attribute or a naming convention.
        ["Gecko_CopyAnimationNames", "aDest", null],
        ["Gecko_CopyFontFamilyFrom", "dst", null],
        ["Gecko_SetAnimationName", "aStyleAnimation", null],
        ["Gecko_SetCounterStyleToName", "aPtr", null],
        ["Gecko_SetCounterStyleToSymbols", "aPtr", null],
        ["Gecko_SetCounterStyleToString", "aPtr", null],
        ["Gecko_CopyCounterStyle", "aDst", null],
        ["Gecko_SetMozBinding", "aDisplay", null],
        [/ClassOrClassList/, /aClass/, null],
        ["Gecko_GetAtomAsUTF16", "aLength", null],
        ["Gecko_CopyMozBindingFrom", "aDest", null],
        ["Gecko_SetNullImageValue", "aImage", null],
        ["Gecko_SetGradientImageValue", "aImage", null],
        ["Gecko_SetImageElement", "aImage", null],
        ["Gecko_SetLayerImageImageValue", "aImage", null],
        ["Gecko_CopyImageValueFrom", "aImage", null],
        ["Gecko_SetCursorArrayLength", "aStyleUI", null],
        ["Gecko_CopyCursorArrayFrom", "aDest", null],
        ["Gecko_SetCursorImageValue", "aCursor", null],
        ["Gecko_SetListStyleImageImageValue", "aList", null],
        ["Gecko_SetListStyleImageNone", "aList", null],
        ["Gecko_CopyListStyleImageFrom", "aList", null],
        ["Gecko_ClearStyleContents", "aContent", null],
        ["Gecko_CopyStyleContentsFrom", "aContent", null],
        ["Gecko_CopyStyleGridTemplateValues", "aGridTemplate", null],
        ["Gecko_ResetStyleCoord", null, null],
        ["Gecko_CopyClipPathValueFrom", "aDst", null],
        ["Gecko_DestroyClipPath", "aClip", null],
        ["Gecko_ResetFilters", "effects", null],
        ["Gecko_CopyFiltersFrom", "aDest", null],
        [/Gecko_CSSValue_Set/, "aCSSValue", null],
        ["Gecko_CSSValue_Drop", "aCSSValue", null],
        ["Gecko_CSSFontFaceRule_GetCssText", "aResult", null],
        ["Gecko_EnsureTArrayCapacity", "aArray", null],
        ["Gecko_ClearPODTArray", "aArray", null],
        ["Gecko_SetStyleGridTemplate", "aGridTemplate", null],
        ["Gecko_ResizeTArrayForStrings", "aArray", null],
        ["Gecko_ClearAndResizeStyleContents", "aContent", null],
        [/Gecko_ClearAndResizeCounter/, "aContent", null],
        [/Gecko_CopyCounter.*?From/, "aContent", null],
        [/Gecko_SetContentDataImageValue/, "aList", null],
        [/Gecko_SetContentData/, "aContent", null],
        ["Gecko_SetCounterFunction", "aContent", null],
        [/Gecko_EnsureStyle.*?ArrayLength/, "aArray", null],
        ["Gecko_GetOrCreateKeyframeAtStart", "aKeyframes", null],
        ["Gecko_GetOrCreateInitialKeyframe", "aKeyframes", null],
        ["Gecko_GetOrCreateFinalKeyframe", "aKeyframes", null],
        ["Gecko_AppendPropertyValuePair", "aProperties", null],
        ["Gecko_SetStyleCoordCalcValue", null, null],
        ["Gecko_StyleClipPath_SetURLValue", "aClip", null],
        ["Gecko_nsStyleFilter_SetURLValue", "aEffects", null],
        ["Gecko_nsStyleSVG_SetDashArrayLength", "aSvg", null],
        ["Gecko_nsStyleSVG_CopyDashArray", "aDst", null],
        ["Gecko_nsStyleFont_SetLang", "aFont", null],
        ["Gecko_nsStyleFont_CopyLangFrom", "aFont", null],
        ["Gecko_ClearWillChange", "aDisplay", null],
        ["Gecko_AppendWillChange", "aDisplay", null],
        ["Gecko_CopyWillChangeFrom", "aDest", null],
        ["Gecko_InitializeImageCropRect", "aImage", null],
        ["Gecko_CopyShapeSourceFrom", "aDst", null],
        ["Gecko_DestroyShapeSource", "aShape", null],
        ["Gecko_StyleShapeSource_SetURLValue", "aShape", null],
        ["Gecko_NewBasicShape", "aShape", null],
        ["Gecko_NewShapeImage", "aShape", null],
        ["Gecko_nsFont_InitSystem", "aDest", null],
        ["Gecko_nsFont_SetFontFeatureValuesLookup", "aFont", null],
        ["Gecko_nsFont_ResetFontFeatureValuesLookup", "aFont", null],
        ["Gecko_nsStyleFont_FixupNoneGeneric", "aFont", null],
        ["Gecko_StyleTransition_SetUnsupportedProperty", "aTransition", null],
        ["Gecko_AddPropertyToSet", "aPropertySet", null],
        ["Gecko_CalcStyleDifference", "aAnyStyleChanged", null],
        ["Gecko_CalcStyleDifference", "aOnlyResetStructsChanged", null],
        ["Gecko_nsStyleSVG_CopyContextProperties", "aDst", null],
        ["Gecko_nsStyleFont_PrefillDefaultForGeneric", "aFont", null],
        ["Gecko_nsStyleSVG_SetContextPropertiesLength", "aSvg", null],
        ["Gecko_ClearAlternateValues", "aFont", null],
        ["Gecko_AppendAlternateValues", "aFont", null],
        ["Gecko_CopyAlternateValuesFrom", "aDest", null],
        ["Gecko_CounterStyle_GetName", "aResult", null],
        ["Gecko_CounterStyle_GetSingleString", "aResult", null],
        ["Gecko_nsTArray_FontFamilyName_AppendNamed", "aNames", null],
        ["Gecko_nsTArray_FontFamilyName_AppendGeneric", "aNames", null],
    ];
    for (var [entryMatch, varMatch, csuMatch] of whitelist) {
        assert(entryMatch || varMatch || csuMatch);
        if (entryMatch && !nameMatches(entry.name, entryMatch))
            continue;
        if (varMatch && !nameMatches(varName, varMatch))
            continue;
        if (csuMatch && (!csuName || !nameMatches(csuName, csuMatch)))
            continue;
        return true;
    }
    return false;
}

function isSafeAssignment(entry, edge, variable)
{
    if (edge.Kind != 'Assign')
        return false;

    var [mangled, unmangled] = splitFunction(entry.name);

    // The assignment
    //
    //   nsFont* font = fontTypes[eType];
    //
    // ends up with 'font' pointing to a member of 'this', so it should inherit
    // the safety of 'this'.
    if (unmangled.includes("mozilla::LangGroupFontPrefs::Initialize") &&
        variable == 'font')
    {
        const [lhs, rhs] = edge.Exp;
        const {Kind, Exp: [{Kind: indexKind, Exp: [collection, index]}]} = rhs;
        if (Kind == 'Drf' &&
            indexKind == 'Index' &&
            collection.Kind == 'Var' &&
            collection.Variable.Name[0] == 'fontTypes')
        {
            return entry.isSafeArgument(0); // 'this'
        }
    }

    return false;
}

function checkFieldWrite(entry, location, fields)
{
    var name = entry.name;
    for (var field of fields) {
        // The analysis is having some trouble keeping track of whether
        // already_AddRefed and nsCOMPtr structures are safe to access.
        // Hopefully these will be thread local, but it would be better to
        // improve the analysis to handle these.
        if (/already_AddRefed.*?.mRawPtr/.test(field))
            return;
        if (/nsCOMPtr<.*?>.mRawPtr/.test(field))
            return;

        if (/\bThreadLocal<\b/.test(field))
            return;

        // Debugging check for string corruption.
        if (field == "nsStringBuffer.mCanary")
            return;
    }

    var str = "";
    for (var field of fields)
        str += " " + field;

    dumpError(entry, location, "Field write" + str);
}

function checkDereferenceWrite(entry, location, variable)
{
    var name = entry.name;

    // Maybe<T> uses placement new on local storage in a way we don't understand.
    // Allow this if the Maybe<> value itself is threadsafe.
    if (/Maybe.*?::emplace/.test(name) && entry.isSafeArgument(0))
        return;

    // UniquePtr writes through temporaries referring to its internal storage.
    // Allow this if the UniquePtr<> is threadsafe.
    if (/UniquePtr.*?::reset/.test(name) && entry.isSafeArgument(0))
        return;

    // Operations on nsISupports reference counts.
    if (hasThreadsafeReferenceCounts(entry, /nsCOMPtr<T>::swap\(.*?\[with T = (.*?)\]/))
        return;

    // ConvertToLowerCase::write writes through a local pointer into the first
    // argument.
    if (/ConvertToLowerCase::write/.test(name) && entry.isSafeArgument(0))
        return;

    dumpError(entry, location, "Dereference write " + (variable ? variable : "<unknown>"));
}

function ignoreCallEdge(entry, callee)
{
    var name = entry.name;

    // nsPropertyTable::GetPropertyInternal has the option of removing data
    // from the table, but when it is called by nsPropertyTable::GetProperty
    // this will not occur.
    if (/nsPropertyTable::GetPropertyInternal/.test(callee) &&
        /nsPropertyTable::GetProperty/.test(name))
    {
        return true;
    }

    // Document::PropertyTable calls GetExtraPropertyTable (which has side
    // effects) if the input category is non-zero. If a literal zero was passed
    // in for the category then we treat it as a safe argument, per
    // isEdgeSafeArgument, so just watch for that.
    if (/Document::GetExtraPropertyTable/.test(callee) &&
        /Document::PropertyTable/.test(name) &&
        entry.isSafeArgument(1))
    {
        return true;
    }

    // This function has an explicit test for being on the main thread if the
    // style has non-threadsafe refcounts, but the analysis isn't smart enough
    // to understand what the actual styles that can be involved are.
    if (/nsStyleList::SetCounterStyle/.test(callee))
        return true;

    // CachedBorderImageData is exclusively owned by nsStyleImage, but the
    // analysis is not smart enough to know this.
    if (/CachedBorderImageData::PurgeCachedImages/.test(callee) &&
        /nsStyleImage::/.test(name) &&
        entry.isSafeArgument(0))
    {
        return true;
    }

    // StyleShapeSource exclusively owns its UniquePtr<nsStyleImage>.
    if (/nsStyleImage::SetURLValue/.test(callee) &&
        /StyleShapeSource::SetURL/.test(name) &&
        entry.isSafeArgument(0))
    {
        return true;
    }

    // The AddRef through a just-assigned heap pointer here is not handled by
    // the analysis.
    if (/nsCSSValue::Array::AddRef/.test(callee) &&
        /nsStyleContentData::SetCounters/.test(name) &&
        entry.isSafeArgument(2))
    {
        return true;
    }

    // AllChildrenIterator asks AppendOwnedAnonBoxes to append into an nsTArray
    // local variable.
    if (/nsIFrame::AppendOwnedAnonBoxes/.test(callee) &&
        /AllChildrenIterator::AppendNativeAnonymousChildren/.test(name))
    {
        return true;
    }

    // Runnables are created and named on one thread, then dispatched
    // (possibly to another). Writes on the origin thread are ok.
    if (/::SetName/.test(callee) &&
        /::UnlabeledDispatch/.test(name))
    {
        return true;
    }

    // We manually lock here
    if (name == "Gecko_nsFont_InitSystem" ||
        name == "Gecko_GetFontMetrics" ||
        name == "Gecko_nsStyleFont_FixupMinFontSize" ||
        /ThreadSafeGetDefaultFontHelper/.test(name))
    {
        return true;
    }

    return false;
}

function ignoreContents(entry)
{
    var whitelist = [
        // We don't care what happens when we're about to crash.
        "abort",
        /MOZ_ReportAssertionFailure/,
        /MOZ_ReportCrash/,
        /MOZ_Crash/,
        /MOZ_CrashPrintf/,
        /AnnotateMozCrashReason/,
        /InvalidArrayIndex_CRASH/,
        /NS_ABORT_OOM/,

        // These ought to be threadsafe.
        "NS_DebugBreak",
        /mozalloc_handle_oom/,
        /^NS_Log/, /log_print/, /LazyLogModule::operator/,
        /SprintfLiteral/, "PR_smprintf", "PR_smprintf_free",
        /NS_DispatchToMainThread/, /NS_ReleaseOnMainThread/,
        /NS_NewRunnableFunction/, /NS_Atomize/,
        /nsCSSValue::BufferFromString/,
        /NS_xstrdup/,
        /Assert_NoQueryNeeded/,
        /AssertCurrentThreadOwnsMe/,
        /PlatformThread::CurrentId/,
        /imgRequestProxy::GetProgressTracker/, // Uses an AutoLock
        /Smprintf/,
        "malloc",
        "calloc",
        "free",
        "realloc",
        "memalign",
        "strdup",
        "strndup",
        "moz_xmalloc",
        "moz_xcalloc",
        "moz_xrealloc",
        "moz_xmemalign",
        "moz_xstrdup",
        "moz_xstrndup",
        "jemalloc_thread_local_arena",

        // These all create static strings in local storage, which is threadsafe
        // to do but not understood by the analysis yet.
        / EmptyString\(\)/,

        // These could probably be handled by treating the scope of PSAutoLock
        // aka BaseAutoLock<PSMutex> as threadsafe.
        /profiler_register_thread/,
        /profiler_unregister_thread/,

        // The analysis thinks we'll write to mBits in the DoGetStyleFoo<false>
        // call.  Maybe the template parameter confuses it?
        /ComputedStyle::PeekStyle/,

        // The analysis can't cope with the indirection used for the objects
        // being initialized here, from nsCSSValue::Array::Create to the return
        // value of the Item(i) getter.
        /nsCSSValue::SetCalcValue/,

        // Unable to analyze safety of linked list initialization.
        "Gecko_NewCSSValueSharedList",
        "Gecko_CSSValue_InitSharedList",

        // Unable to trace through dataflow, but straightforward if inspected.
        "Gecko_NewNoneTransform",

        // Need main thread assertions or other fixes.
        /EffectCompositor::GetServoAnimationRule/,
    ];
    if (entry.matches(whitelist))
        return true;

    if (entry.isSafeArgument(0)) {
        var heapWhitelist = [
            // Operations on heap structures pointed to by arrays and strings are
            // threadsafe as long as the array/string itself is threadsafe.
            /nsTArray_Impl.*?::AppendElement/,
            /nsTArray_Impl.*?::RemoveElementsAt/,
            /nsTArray_Impl.*?::ReplaceElementsAt/,
            /nsTArray_Impl.*?::InsertElementAt/,
            /nsTArray_Impl.*?::SetCapacity/,
            /nsTArray_Impl.*?::SetLength/,
            /nsTArray_base.*?::EnsureCapacity/,
            /nsTArray_base.*?::ShiftData/,
            /AutoTArray.*?::Init/,
            /(nsTSubstring<T>|nsAC?String)::SetCapacity/,
            /(nsTSubstring<T>|nsAC?String)::SetLength/,
            /(nsTSubstring<T>|nsAC?String)::Assign/,
            /(nsTSubstring<T>|nsAC?String)::Append/,
            /(nsTSubstring<T>|nsAC?String)::Replace/,
            /(nsTSubstring<T>|nsAC?String)::Trim/,
            /(nsTSubstring<T>|nsAC?String)::Truncate/,
            /(nsTSubstring<T>|nsAC?String)::StripTaggedASCII/,
            /(nsTSubstring<T>|nsAC?String)::operator=/,
            /nsTAutoStringN<T, N>::nsTAutoStringN/,

            // Similar for some other data structures
            /nsCOMArray_base::SetCapacity/,
            /nsCOMArray_base::Clear/,
            /nsCOMArray_base::AppendElement/,

            // UniquePtr is similar.
            /mozilla::UniquePtr/,

            // The use of unique pointers when copying mCropRect here confuses
            // the analysis.
            /nsStyleImage::DoCopy/,
        ];
        if (entry.matches(heapWhitelist))
            return true;
    }

    if (entry.isSafeArgument(1)) {
        var firstArgWhitelist = [
            /nsTextFormatter::snprintf/,
            /nsTextFormatter::ssprintf/,
            /_ASCIIToUpperInSitu/,

            // Handle some writes into an array whose safety we don't have a good way
            // of tracking currently.
            /FillImageLayerList/,
            /FillImageLayerPositionCoordList/,
        ];
        if (entry.matches(firstArgWhitelist))
            return true;
    }

    if (entry.isSafeArgument(2)) {
        var secondArgWhitelist = [
            /nsStringBuffer::ToString/,
            /AppendUTF\d+toUTF\d+/,
            /AppendASCIItoUTF\d+/,
        ];
        if (entry.matches(secondArgWhitelist))
            return true;
    }

    return false;
}

///////////////////////////////////////////////////////////////////////////////
// Sixgill Utilities
///////////////////////////////////////////////////////////////////////////////

function variableName(variable)
{
    return (variable && variable.Name) ? variable.Name[0] : null;
}

function stripFields(exp)
{
    // Fields and index operations do not involve any dereferences. Remove them
    // from the expression but remember any encountered fields for use by
    // annotations later on.
    var fields = [];
    while (true) {
        if (exp.Kind == "Index") {
            exp = exp.Exp[0];
            continue;
        }
        if (exp.Kind == "Fld") {
            var csuName = exp.Field.FieldCSU.Type.Name;
            var fieldName = exp.Field.Name[0];
            assert(csuName && fieldName);
            fields.push(csuName + "." + fieldName);
            exp = exp.Exp[0];
            continue;
        }
        break;
    }
    return [exp, fields];
}

function isLocalVariable(variable)
{
    switch (variable.Kind) {
      case "Return":
      case "Temp":
      case "Local":
      case "Arg":
        return true;
    }
    return false;
}

function isDirectCall(edge, regexp)
{
    return edge.Kind == "Call"
        && edge.Exp[0].Kind == "Var"
        && regexp.test(variableName(edge.Exp[0].Variable));
}

function isZero(exp)
{
    return exp.Kind == "Int" && exp.String == "0";
}

///////////////////////////////////////////////////////////////////////////////
// Analysis Structures
///////////////////////////////////////////////////////////////////////////////

// Safe arguments are those which may be written through (directly, not through
// pointer fields etc.) without concerns about thread safety. This includes
// pointers to stack data, null pointers, and other data we know is thread
// local, such as certain arguments to the root functions.
//
// Entries in the worklist keep track of the pointer arguments to the function
// which are safe using a sorted array, so that this can be propagated down the
// stack. Zero is |this|, and arguments are indexed starting at one.

function WorklistEntry(name, safeArguments, stack, parameterNames)
{
    this.name = name;
    this.safeArguments = safeArguments;
    this.stack = stack;
    this.parameterNames = parameterNames;
}

WorklistEntry.prototype.readable = function()
{
    const [ mangled, readable ] = splitFunction(this.name);
    return readable;
}

WorklistEntry.prototype.mangledName = function()
{
    var str = this.name;
    for (var safe of this.safeArguments)
        str += " SAFE " + safe;
    return str;
}

WorklistEntry.prototype.isSafeArgument = function(index)
{
    for (var safe of this.safeArguments) {
        if (index == safe)
            return true;
    }
    return false;
}

WorklistEntry.prototype.setParameterName = function(index, name)
{
    this.parameterNames[index] = name;
}

WorklistEntry.prototype.addSafeArgument = function(index)
{
    if (this.isSafeArgument(index))
        return;
    this.safeArguments.push(index);

    // Sorting isn't necessary for correctness but makes printed stack info tidier.
    this.safeArguments.sort();
}

function safeArgumentIndex(variable)
{
    if (variable.Kind == "This")
        return 0;
    if (variable.Kind == "Arg")
        return variable.Index + 1;
    return -1;
}

function nameMatches(name, match)
{
    if (typeof match == "string") {
        if (name == match)
            return true;
    } else {
        assert(match instanceof RegExp);
        if (match.test(name))
            return true;
    }
    return false;
}

function nameMatchesArray(name, matchArray)
{
    for (var match of matchArray) {
        if (nameMatches(name, match))
            return true;
    }
    return false;
}

WorklistEntry.prototype.matches = function(matchArray)
{
    return nameMatchesArray(this.name, matchArray);
}

function CallSite(callee, safeArguments, location, parameterNames)
{
    this.callee = callee;
    this.safeArguments = safeArguments;
    this.location = location;
    this.parameterNames = parameterNames;
}

CallSite.prototype.safeString = function()
{
    if (this.safeArguments.length) {
        var str = "";
        for (var i = 0; i < this.safeArguments.length; i++) {
            var arg = this.safeArguments[i];
            if (arg in this.parameterNames)
                str += " " + this.parameterNames[arg];
            else
                str += " <" + ((arg == 0) ? "this" : "arg" + (arg - 1)) + ">";
        }
        return " ### SafeArguments:" + str;
    }
    return "";
}

///////////////////////////////////////////////////////////////////////////////
// Analysis Core
///////////////////////////////////////////////////////////////////////////////

var errorCount = 0;
var errorLimit = 100;

// We want to suppress output for functions that ended up not having any
// hazards, for brevity of the final output. So each new toplevel function will
// initialize this to a string, which should be printed only if an error is
// seen.
var errorHeader;

var startTime = new Date;
function elapsedTime()
{
    var seconds = (new Date - startTime) / 1000;
    return "[" + seconds.toFixed(2) + "s] ";
}

var options = parse_options([
    {
        name: '--strip-prefix',
        default: os.getenv('SOURCE') || '',
        type: 'string'
    },
    {
        name: '--add-prefix',
        default: os.getenv('URLPREFIX') || '',
        type: 'string'
    },
    {
        name: '--verbose',
        type: 'bool'
    },
]);

function add_trailing_slash(str) {
    if (str == '')
        return str;
    return str.endsWith("/") ? str : str + "/";
}

var removePrefix = add_trailing_slash(options.strip_prefix);
var addPrefix = add_trailing_slash(options.add_prefix);

if (options.verbose) {
    printErr(`Removing prefix ${removePrefix} from paths`);
    printErr(`Prepending ${addPrefix} to paths`);
}

print(elapsedTime() + "Loading types...");
if (os.getenv("TYPECACHE"))
    loadTypesWithCache('src_comp.xdb', os.getenv("TYPECACHE"));
else
    loadTypes('src_comp.xdb');
print(elapsedTime() + "Starting analysis...");

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

var minStream = xdb.min_data_stream();
var maxStream = xdb.max_data_stream();
var roots = [];

var [flag, arg] = scriptArgs;
if (flag && (flag == '-f' || flag == '--function')) {
    roots = [arg];
} else {
    for (var bodyIndex = minStream; bodyIndex <= maxStream; bodyIndex++) {
        var key = xdb.read_key(bodyIndex);
        var name = key.readString();
        if (/^Gecko_/.test(name)) {
            var data = xdb.read_entry(key);
            if (/ServoBindings.cpp/.test(data.readString()))
                roots.push(name);
            xdb.free_string(data);
        }
        xdb.free_string(key);
    }
}

print(elapsedTime() + "Found " + roots.length + " roots.");
for (var i = 0; i < roots.length; i++) {
    var root = roots[i];
    errorHeader = elapsedTime() + "#" + (i + 1) + " Analyzing " + root + " ...";
    try {
        processRoot(root);
    } catch (e) {
        if (e != "Error!")
            throw e;
    }
}

print(`${elapsedTime()}Completed analysis, found ${errorCount}/${errorLimit} allowed errors`);

var currentBody;

// All local variable assignments we have seen in either the outer or inner
// function. This crosses loop boundaries, and currently has an unsoundness
// where later assignments in a loop are not taken into account.
var assignments;

// All loops in the current function which are reachable off main thread.
var reachableLoops;

// Functions that are reachable from the current root.
var reachable = {};

function dumpError(entry, location, text)
{
    if (errorHeader) {
        print(errorHeader);
        errorHeader = undefined;
    }

    var stack = entry.stack;
    print("Error: " + text);
    print("Location: " + entry.name + (location ? " @ " + location : "") + stack[0].safeString());
    print("Stack Trace:");
    // Include the callers in the stack trace instead of the callees. Make sure
    // the dummy stack entry we added for the original roots is in place.
    assert(stack[stack.length - 1].location == null);
    for (var i = 0; i < stack.length - 1; i++)
        print(stack[i + 1].callee + " @ " + stack[i].location + stack[i + 1].safeString());
    print("\n");

    if (++errorCount == errorLimit) {
        print("Maximum number of errors encountered, exiting...");
        quit();
    }

    throw "Error!";
}

// If edge is an assignment from a local variable, return the rhs variable.
function variableAssignRhs(edge)
{
    if (edge.Kind == "Assign" && edge.Exp[1].Kind == "Drf" && edge.Exp[1].Exp[0].Kind == "Var") {
        var variable = edge.Exp[1].Exp[0].Variable;
        if (isLocalVariable(variable))
            return variable;
    }
    return null;
}

function processAssign(body, entry, location, lhs, edge)
{
    var fields;
    [lhs, fields] = stripFields(lhs);

    switch (lhs.Kind) {
      case "Var":
        var name = variableName(lhs.Variable);
        if (isLocalVariable(lhs.Variable)) {
            // Remember any assignments to local variables in this function.
            // Note that we ignore any points where the variable's address is
            // taken and indirect assignments might occur. This is an
            // unsoundness in the analysis.

            let assign = [body, edge];

            // Chain assignments if the RHS has only been assigned once.
            var rhsVariable = variableAssignRhs(edge);
            if (rhsVariable) {
                var rhsAssign = singleAssignment(variableName(rhsVariable));
                if (rhsAssign)
                    assign = rhsAssign;
            }

            if (!(name in assignments))
                assignments[name] = [];
            assignments[name].push(assign);
        } else {
            checkVariableAssignment(entry, location, name);
        }
        return;
      case "Drf":
        var variable = null;
        if (lhs.Exp[0].Kind == "Var") {
            variable = lhs.Exp[0].Variable;
            if (isSafeVariable(entry, variable))
                return;
        } else if (lhs.Exp[0].Kind == "Fld") {
            const {
                Name: [ fieldName ],
                Type: {Kind, Type: fieldType},
                FieldCSU: {Type: {Kind: containerTypeKind,
                                  Name: containerTypeName}}
            } = lhs.Exp[0].Field;
            const [containerExpr] = lhs.Exp[0].Exp;

            if (containerTypeKind == 'CSU' &&
                Kind == 'Pointer' &&
                isEdgeSafeArgument(entry, containerExpr) &&
                isSafeMemberPointer(containerTypeName, fieldName, fieldType))
            {
                return;
            }
        }
        if (fields.length)
            checkFieldWrite(entry, location, fields);
        else
            checkDereferenceWrite(entry, location, variableName(variable));
        return;
      case "Int":
        if (isZero(lhs)) {
            // This shows up under MOZ_ASSERT, to crash the process.
            return;
        }
    }
    dumpError(entry, location, "Unknown assignment " + JSON.stringify(lhs));
}

function get_location(rawLocation) {
    const filename = rawLocation.CacheString.replace(removePrefix, '');
    return addPrefix + filename + "#" + rawLocation.Line;
}

function process(entry, body, addCallee)
{
    if (!("PEdge" in body))
        return;

    // Add any arguments which are safe due to annotations.
    if ("DefineVariable" in body) {
        for (var defvar of body.DefineVariable) {
            var index = safeArgumentIndex(defvar.Variable);
            if (index >= 0) {
                var varName = index ? variableName(defvar.Variable) : "this";
                assert(varName);
                entry.setParameterName(index, varName);
                var csuName = null;
                var type = defvar.Type;
                if (type.Kind == "Pointer" && type.Type.Kind == "CSU")
                    csuName = type.Type.Name;
                if (treatAsSafeArgument(entry, varName, csuName))
                    entry.addSafeArgument(index);
            }
        }
    }

    // Points in the body which are reachable if we are not on the main thread.
    var nonMainThreadPoints = [];
    nonMainThreadPoints[body.Index[0]] = true;

    for (var edge of body.PEdge) {
        // Ignore code that only executes on the main thread.
        if (!(edge.Index[0] in nonMainThreadPoints))
            continue;

        var location = get_location(body.PPoint[edge.Index[0] - 1].Location);

        var callees = getCallees(edge);
        for (var callee of callees) {
            switch (callee.kind) {
            case "direct":
                var safeArguments = getEdgeSafeArguments(entry, edge, callee.name);
                addCallee(new CallSite(callee.name, safeArguments, location, {}));
                break;
              case "resolved-field":
                break;
              case "field":
                var field = callee.csu + "." + callee.field;
                if (callee.isVirtual)
                    checkOverridableVirtualCall(entry, location, field);
                else
                    checkIndirectCall(entry, location, field);
                break;
              case "indirect":
                checkIndirectCall(entry, location, callee.variable);
                break;
              default:
                dumpError(entry, location, "Unknown call " + callee.kind);
                break;
            }
        }

        var fallthrough = true;

        if (edge.Kind == "Assign") {
            assert(edge.Exp.length == 2);
            processAssign(body, entry, location, edge.Exp[0], edge);
        } else if (edge.Kind == "Call") {
            assert(edge.Exp.length <= 2);
            if (edge.Exp.length == 2)
                processAssign(body, entry, location, edge.Exp[1], edge);

            // Treat assertion failures as if they don't return, so that
            // asserting NS_IsMainThread() is sufficient to prevent the
            // analysis from considering a block of code.
            if (isDirectCall(edge, /MOZ_ReportAssertionFailure/))
                fallthrough = false;
        } else if (edge.Kind == "Loop") {
            reachableLoops[edge.BlockId.Loop] = true;
        } else if (edge.Kind == "Assume") {
            if (testFailsOffMainThread(edge.Exp[0], edge.PEdgeAssumeNonZero))
                fallthrough = false;
        }

        if (fallthrough)
            nonMainThreadPoints[edge.Index[1]] = true;
    }
}

function maybeProcessMissingFunction(entry, addCallee)
{
    // If a function is missing it might be because a destructor Foo::~Foo() is
    // being called but GCC only gave us an implementation for
    // Foo::~Foo(int32). See computeCallgraph.js for a little more info.
    var name = entry.name;
    if (name.indexOf("::~") > 0 && name.indexOf("()") > 0) {
        var callee = name.replace("()", "(int32)");
        addCallee(new CallSite(name, entry.safeArguments, entry.stack[0].location, entry.parameterNames));
        return true;
    }

    // Similarly, a call to a C1 constructor might invoke the C4 constructor. A
    // mangled constructor will be something like _ZN<length><name>C1E... or in
    // the case of a templatized constructor, _ZN<length><name>C1I...EE... so
    // we hack it and look for "C1E" or "C1I" and replace them with their C4
    // variants. This will have rare false matches, but so far we haven't hit
    // any external function calls of that sort.
    if (entry.mangledName().includes("C1E") || entry.mangledName().includes("C1I")) {
        var callee = name.replace("C1E", "C4E").replace("C1I", "C4I");
        addCallee(new CallSite(name, entry.safeArguments, entry.stack[0].location, entry.parameterNames));
        return true;
    }

    // Hack to manually follow some typedefs that show up on some functions.
    // This is a bug in the sixgill GCC plugin I think, since sixgill is
    // supposed to follow any typedefs itself.
    if (/mozilla::dom::Element/.test(name)) {
        var callee = name.replace("mozilla::dom::Element", "Document::Element");
        addCallee(new CallSite(name, entry.safeArguments, entry.stack[0].location, entry.parameterNames));
        return true;
    }

    // Hack for contravariant return types. When overriding a virtual method
    // with a method that returns a different return type (a subtype of the
    // original return type), we are getting the right mangled name but the
    // wrong return type in the unmangled name.
    if (/\$nsTextFrame*/.test(name)) {
        var callee = name.replace("nsTextFrame", "nsIFrame");
        addCallee(new CallSite(name, entry.safeArguments, entry.stack[0].location, entry.parameterNames));
        return true;
    }

    return false;
}

function processRoot(name)
{
    var safeArguments = [];
    var parameterNames = {};
    var worklist = [new WorklistEntry(name, safeArguments, [new CallSite(name, safeArguments, null, parameterNames)], parameterNames)];

    reachable = {};

    while (worklist.length > 0) {
        var entry = worklist.pop();

        // In principle we would be better off doing a meet-over-paths here to get
        // the common subset of arguments which are safe to write through. However,
        // analyzing functions separately for each subset if simpler, ensures that
        // the stack traces we produce accurately characterize the stack arguments,
        // and should be fast enough for now.

        if (entry.mangledName() in reachable)
            continue;
        reachable[entry.mangledName()] = true;

        if (ignoreContents(entry))
            continue;

        var data = xdb.read_entry(entry.name);
        var dataString = data.readString();
        var callees = [];
        if (dataString.length) {
            // Reverse the order of the bodies we process so that we visit the
            // outer function and see its assignments before the inner loops.
            assignments = {};
            reachableLoops = {};
            var bodies = JSON.parse(dataString).reverse();
            for (var body of bodies) {
                if (!body.BlockId.Loop || body.BlockId.Loop in reachableLoops) {
                    currentBody = body;
                    process(entry, body, Array.prototype.push.bind(callees));
                }
            }
        } else {
            if (!maybeProcessMissingFunction(entry, Array.prototype.push.bind(callees)))
                checkExternalFunction(entry);
        }
        xdb.free_string(data);

        for (var callee of callees) {
            if (!ignoreCallEdge(entry, callee.callee)) {
                var nstack = [callee, ...entry.stack];
                worklist.push(new WorklistEntry(callee.callee, callee.safeArguments, nstack, callee.parameterNames));
            }
        }
    }
}

function isEdgeSafeArgument(entry, exp)
{
    var fields;
    [exp, fields] = stripFields(exp);

    if (exp.Kind == "Var" && isLocalVariable(exp.Variable))
        return true;
    if (exp.Kind == "Drf" && exp.Exp[0].Kind == "Var") {
        var variable = exp.Exp[0].Variable;
        return isSafeVariable(entry, variable);
    }
    if (isZero(exp))
        return true;
    return false;
}

function getEdgeSafeArguments(entry, edge, callee)
{
    assert(edge.Kind == "Call");
    var res = [];
    if ("PEdgeCallInstance" in edge) {
        if (isEdgeSafeArgument(entry, edge.PEdgeCallInstance.Exp))
            res.push(0);
    }
    if ("PEdgeCallArguments" in edge) {
        var args = edge.PEdgeCallArguments.Exp;
        for (var i = 0; i < args.length; i++) {
            if (isEdgeSafeArgument(entry, args[i]))
                res.push(i + 1);
        }
    }
    return res;
}

function singleAssignment(name)
{
    if (name in assignments) {
        var edges = assignments[name];
        if (edges.length == 1)
            return edges[0];
    }
    return null;
}

function expressionValueEdge(exp) {
    if (!(exp.Kind == "Var" && exp.Variable.Kind == "Temp"))
        return null;
    const assign = singleAssignment(variableName(exp.Variable));
    if (!assign)
        return null;
    const [body, edge] = assign;
    return edge;
}

// Examples:
//
//   void foo(type* aSafe) {
//     type* safeBecauseNew = new type(...);
//     type* unsafeBecauseMultipleAssignments = new type(...);
//     if (rand())
//       unsafeBecauseMultipleAssignments = bar();
//     type* safeBecauseSingleAssignmentOfSafe = aSafe;
//   }
//
function isSafeVariable(entry, variable)
{
    var index = safeArgumentIndex(variable);
    if (index >= 0)
        return entry.isSafeArgument(index);

    if (variable.Kind != "Temp" && variable.Kind != "Local")
        return false;
    var name = variableName(variable);

    if (!entry.safeLocals)
        entry.safeLocals = new Map;
    if (entry.safeLocals.has(name))
        return entry.safeLocals.get(name);

    const safe = isSafeLocalVariable(entry, name);
    entry.safeLocals.set(name, safe);
    return safe;
}

function isSafeLocalVariable(entry, name)
{
    // If there is a single place where this variable has been assigned on
    // edges we are considering, look at that edge.
    var assign = singleAssignment(name);
    if (assign) {
        const [body, edge] = assign;

        // Treat temporary pointers to DebugOnly contents as thread local.
        if (isDirectCall(edge, /DebugOnly.*?::operator/))
            return true;

        // Treat heap allocated pointers as thread local during construction.
        // Hopefully the construction code doesn't leak pointers to the object
        // to places where other threads might access it.
        if (isDirectCall(edge, /operator new/) ||
            isDirectCall(edge, /nsCSSValue::Array::Create/))
        {
            return true;
        }

        if ("PEdgeCallInstance" in edge) {
            // References to the contents of an array are threadsafe if the array
            // itself is threadsafe.
            if ((isDirectCall(edge, /operator\[\]/) ||
                 isDirectCall(edge, /nsTArray.*?::InsertElementAt\b/) ||
                 isDirectCall(edge, /nsStyleContent::ContentAt/) ||
                 isDirectCall(edge, /nsTArray_base.*?::GetAutoArrayBuffer\b/)) &&
                isEdgeSafeArgument(entry, edge.PEdgeCallInstance.Exp))
            {
                return true;
            }

            // Watch for the coerced result of a getter_AddRefs or getter_Copies call.
            if (isDirectCall(edge, /operator /)) {
                var otherEdge = expressionValueEdge(edge.PEdgeCallInstance.Exp);
                if (otherEdge &&
                    isDirectCall(otherEdge, /getter_(?:AddRefs|Copies)/) &&
                    isEdgeSafeArgument(entry, otherEdge.PEdgeCallArguments.Exp[0]))
                {
                    return true;
                }
            }

            // RefPtr::operator->() and operator* transmit the safety of the
            // RefPtr to the return value.
            if (isDirectCall(edge, /RefPtr<.*?>::operator(->|\*)\(\)/) &&
                isEdgeSafeArgument(entry, edge.PEdgeCallInstance.Exp))
            {
                return true;
            }

            // Placement-new returns a pointer that is as safe as the pointer
            // passed to it. Exp[0] is the size, Exp[1] is the pointer/address.
            // Note that the invocation of the constructor is a separate call,
            // and so need not be considered here.
            if (isDirectCall(edge, /operator new/) &&
                edge.PEdgeCallInstance.Exp.length == 2 &&
                isEdgeSafeArgument(entry, edge.PEdgeCallInstance.Exp[1]))
            {
                return true;
            }

            // Coercion via AsAString preserves safety.
            if (isDirectCall(edge, /AsAString/) &&
                isEdgeSafeArgument(entry, edge.PEdgeCallInstance.Exp))
            {
                return true;
            }

            // Special case:
            //
            //   keyframe->mTimingFunction.emplace()
            //   keyframe->mTimingFunction->Init()
            //
            // The object calling Init should be considered safe here because
            // we just emplaced it, though in general keyframe::operator->
            // could do something crazy.
            if (isDirectCall(edge, /operator->/)) do {
                const predges = getPredecessors(body)[edge.Index[0]];
                if (!predges || predges.length != 1)
                    break;
                const predge = predges[0];
                if (!isDirectCall(predge, /\bemplace\b/))
                    break;
                const instance = predge.PEdgeCallInstance;
                if (JSON.stringify(instance) == JSON.stringify(edge.PEdgeCallInstance))
                    return true;
            } while (false);
        }

        if (isSafeAssignment(entry, edge, name))
            return true;

        // Watch out for variables which were assigned arguments.
        var rhsVariable = variableAssignRhs(edge);
        if (rhsVariable)
            return isSafeVariable(entry, rhsVariable);
    }

    // When temporary stack structures are created (either to return or to call
    // methods on without assigning them a name), the generated sixgill JSON is
    // rather strange. The temporary has structure type and is never assigned
    // to, but is dereferenced. GCC is probably not showing us everything it is
    // doing to compile this code. Pattern match for this case here.

    // The variable should have structure type.
    var type = null;
    for (var defvar of currentBody.DefineVariable) {
        if (variableName(defvar.Variable) == name) {
            type = defvar.Type;
            break;
        }
    }
    if (!type || type.Kind != "CSU")
        return false;

    // The variable should not have been written to anywhere up to this point.
    // If it is initialized at this point we should have seen *some* write
    // already, since the CFG edges are visited in reverse post order.
    if (name in assignments)
        return false;

    return true;
}

function isSafeMemberPointer(containerType, memberName, memberType)
{
    // nsTArray owns its header.
    if (containerType.includes("nsTArray_base") && memberName == "mHdr")
        return true;

    if (memberType.Kind != 'Pointer')
        return false;

    // Special-cases go here :)
    return false;
}

// Return whether 'exp == value' holds only when execution is on the main thread.
function testFailsOffMainThread(exp, value) {
    switch (exp.Kind) {
      case "Drf":
        var edge = expressionValueEdge(exp.Exp[0]);
        if (edge) {
            if (isDirectCall(edge, /NS_IsMainThread/) && value)
                return true;
            if (isDirectCall(edge, /IsInServoTraversal/) && !value)
                return true;
            if (isDirectCall(edge, /IsCurrentThreadInServoTraversal/) && !value)
                return true;
            if (isDirectCall(edge, /__builtin_expect/))
                return testFailsOffMainThread(edge.PEdgeCallArguments.Exp[0], value);
            if (edge.Kind == "Assign")
                return testFailsOffMainThread(edge.Exp[1], value);
        }
        break;
      case "Unop":
        if (exp.OpCode == "LogicalNot")
            return testFailsOffMainThread(exp.Exp[0], !value);
        break;
      case "Binop":
        if (exp.OpCode == "NotEqual" || exp.OpCode == "Equal") {
            var cmpExp = isZero(exp.Exp[0])
                ? exp.Exp[1]
                : (isZero(exp.Exp[1]) ? exp.Exp[0] : null);
            if (cmpExp)
                return testFailsOffMainThread(cmpExp, exp.OpCode == "NotEqual" ? value : !value);
        }
        break;
      case "Int":
        if (exp.String == "0" && value)
            return true;
        if (exp.String == "1" && !value)
            return true;
        break;
    }
    return false;
}