Source code
Revision control
Copy as Markdown
Other Tools
/* 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,
/* -*- indent-tabs-mode: nil; js-indent-level: 4 -*- */
"use strict";
loadRelativeToScript('utility.js');
loadRelativeToScript('annotations.js');
var options = parse_options([
{ name: '--verbose', type: 'bool' },
{ name: "gcTypes", default: "gcTypes.txt" },
{ name: "typeInfo", default: "typeInfo.txt" }
]);
var typeInfo = {
'GCPointers': [],
'GCThings': [],
'GCInvalidated': [],
'GCRefs': [],
'NonGCTypes': {}, // unused
'NonGCPointers': {},
'RootedGCThings': {},
'RootedPointers': {},
'RootedBases': {'JS::AutoGCRooter': true},
'InheritFromTemplateArgs': {},
'OtherCSUTags': {},
'OtherFieldTags': {},
// RAII types within which we should assume GC is suppressed, eg
// AutoSuppressGC.
'GCSuppressors': {},
};
var gDescriptors = new Map; // Map from descriptor string => Set of typeName
var structureParents = {}; // Map from field => list of <parent, fieldName>
var pointerParents = {}; // Map from field => list of <parent, fieldName>
var baseClasses = {}; // Map from struct name => list of base class name strings
var subClasses = {}; // Map from struct name => list of subclass name strings
var gcTypes = {}; // map from parent struct => Set of GC typed children
var gcPointers = {}; // map from parent struct => Set of GC typed children
var gcFields = new Map;
var rootedPointers = {};
// Accumulate the base GC types before propagating info through the type graph,
// so that we can include edges from types processed later
// (eg MOZ_INHERIT_TYPE_ANNOTATIONS_FROM_TEMPLATE_ARGS).
var pendingGCTypes = []; // array of [name, reason, ptrdness]
function processCSU(csu, body)
{
for (let { 'Name': [ annType, tag ] } of (body.Annotation || [])) {
if (annType != 'annotate')
continue;
if (tag == 'GC Pointer')
typeInfo.GCPointers.push(csu);
else if (tag == 'Invalidated by GC')
typeInfo.GCInvalidated.push(csu);
else if (tag == 'GC Pointer or Reference')
typeInfo.GCRefs.push(csu);
else if (tag == 'GC Thing')
typeInfo.GCThings.push(csu);
else if (tag == 'Suppressed GC Pointer')
typeInfo.NonGCPointers[csu] = true;
else if (tag == 'Rooted Pointer')
typeInfo.RootedPointers[csu] = true;
else if (tag == 'Rooted Base')
typeInfo.RootedBases[csu] = true;
else if (tag == 'Suppress GC')
typeInfo.GCSuppressors[csu] = true;
else if (tag == 'moz_inherit_type_annotations_from_template_args')
typeInfo.InheritFromTemplateArgs[csu] = true;
else
addToKeyedList(typeInfo.OtherCSUTags, csu, tag);
}
for (let { 'Base': base } of (body.CSUBaseClass || []))
addBaseClass(csu, base);
for (const field of (body.DataField || [])) {
var type = field.Field.Type;
var fieldName = field.Field.Name[0];
if (type.Kind == "Pointer") {
var target = type.Type;
if (target.Kind == "CSU")
addNestedPointer(csu, target.Name, fieldName);
}
if (type.Kind == "Array") {
var target = type.Type;
if (target.Kind == "CSU")
addNestedStructure(csu, target.Name, fieldName);
}
if (type.Kind == "CSU")
addNestedStructure(csu, type.Name, fieldName);
for (const { 'Name': [ annType, tag ] } of (field.Annotation || [])) {
if (!(csu in typeInfo.OtherFieldTags))
typeInfo.OtherFieldTags[csu] = [];
addToKeyedList(typeInfo.OtherFieldTags[csu], fieldName, tag);
}
}
for (const funcfield of (body.FunctionField || [])) {
const fields = funcfield.Field;
// Pure virtual functions will not have field.Variable; others will.
for (const field of funcfield.Field) {
for (const {'Name': [annType, tag]} of (field.Annotation || [])) {
if (!(csu in typeInfo.OtherFieldTags))
typeInfo.OtherFieldTags[csu] = {};
addToKeyedList(typeInfo.OtherFieldTags[csu], field.Name[0], tag);
}
}
}
}
// csu.field is of type inner
function addNestedStructure(csu, inner, field)
{
if (!(inner in structureParents))
structureParents[inner] = [];
// Skip fields that are really base classes, to avoid duplicating the base
// fields; addBaseClass already added a "base-N" name.
if (field.match(/^field:\d+$/) && (csu in baseClasses) && (baseClasses[csu].indexOf(inner) != -1))
return;
structureParents[inner].push([ csu, field ]);
}
function addBaseClass(csu, base) {
if (!(csu in baseClasses))
baseClasses[csu] = [];
baseClasses[csu].push(base);
if (!(base in subClasses))
subClasses[base] = [];
subClasses[base].push(csu);
var k = baseClasses[csu].length;
addNestedStructure(csu, base, `<base-${k}>`);
}
function addNestedPointer(csu, inner, field)
{
if (!(inner in pointerParents))
pointerParents[inner] = [];
pointerParents[inner].push([ csu, field ]);
}
var xdb = xdbLibrary();
xdb.open("src_comp.xdb");
var minStream = xdb.min_data_stream();
var maxStream = xdb.max_data_stream();
for (var csuIndex = minStream; csuIndex <= maxStream; csuIndex++) {
var csu = xdb.read_key(csuIndex);
var data = xdb.read_entry(csu);
var json = JSON.parse(data.readString());
assert(json.length == 1);
processCSU(csu.readString(), json[0]);
xdb.free_string(csu);
xdb.free_string(data);
}
for (const typename of extraRootedGCThings())
typeInfo.RootedGCThings[typename] = true;
for (const typename of extraRootedPointers())
typeInfo.RootedPointers[typename] = true;
// Everything that inherits from a "Rooted Base" is considered to be rooted.
// This is for things like CustomAutoRooter and its subclasses.
var basework = Object.keys(typeInfo.RootedBases);
while (basework.length) {
const base = basework.pop();
typeInfo.RootedPointers[base] = true;
if (base in subClasses)
basework.push(...subClasses[base]);
}
// Now that we have the whole hierarchy set up, add all the types and propagate
// info.
for (const csu of typeInfo.GCThings)
addGCType(csu);
for (const csu of typeInfo.GCPointers)
addGCPointer(csu);
for (const csu of typeInfo.GCInvalidated)
addGCPointer(csu);
function parseTemplateType(typeName, validate=false) {
// We only want templatized types. `Foo<U, T>::Member` doesn't count.
// Foo<U, T>::Bar<X, Y> does count. Which turns out to be a simple rule:
// check whether the type ends in '>'.
if (!typeName.endsWith(">")) {
return [typeName, undefined];
}
// "Tokenize" into angle brackets, commas, and everything else. We store
// match objects as tokens because we'll need the string offset after we
// finish grabbing the template parameters.
const tokens = [];
const tokenizer = /[<>,]|[^<>,]+/g;
let match;
while ((match = tokenizer.exec(typeName)) !== null) {
tokens.push(match);
}
// Walk backwards through the tokens, stopping when we find the matching
// open bracket.
const args = [];
let depth = 0;
let arg;
let first_result;
for (const match of tokens.reverse()) {
const token = match[0];
if (depth == 1 && (token == ',' || token == '<')) {
// We've walked back to the beginning of a template parameter,
// where we will see either a comma or open bracket.
args.unshift(arg);
arg = '';
} else if (depth == 0 && token == '>') {
arg = ''; // We just started.
} else {
arg = token + arg;
}
// Maintain the depth.
if (token == '<') {
assert(depth > 0, `Invalid type: too many '<' signs in '${typeName}'`);
depth--;
} else if (token == '>') {
depth++;
}
if (depth == 0) {
// We've walked out of the template parameter list.
// Record the results.
assert(args.length > 0);
const templateName = typeName.substr(0, match.index);
const result = [templateName, args.map(arg => arg.trim())];
if (!validate) {
// Normal processing is to return the result the first time we
// get to the '<' that matches the terminal '>', without validating
// that the rest of the type name is balanced.
return result;
} else if (!first_result) {
// If we are validating, remember the result when we hit the
// first matching '<', but then keep processing the rest of
// the input string to count brackets.
first_result = result;
}
}
}
assert(depth == 0, `Invalid type: too many '>' signs in '${typeName}'`);
return first_result;
}
if (os.getenv("HAZARD_RUN_INTERNAL_TESTS")) {
function check_parse(typeName, result) {
assertEq(JSON.stringify(parseTemplateType(typeName)), JSON.stringify(result));
}
check_parse("int", ["int", undefined]);
check_parse("Type<int>", ["Type", ["int"]]);
check_parse("Container<int, double>", ["Container", ["int", "double"]]);
check_parse("Container<Container<void, void>, double>", ["Container", ["Container<void, void>", "double"]]);
check_parse("Foo<Bar<a,b>,Bar<a,b>>::Container<Container<void, void>, double>", ["Foo<Bar<a,b>,Bar<a,b>>::Container", ["Container<void, void>", "double"]]);
check_parse("AlignedStorage2<TypedArray<foo>>", ["AlignedStorage2", ["TypedArray<foo>"]]);
check_parse("mozilla::AlignedStorage2<mozilla::dom::TypedArray<unsigned char, JS::UnwrapArrayBufferMaybeShared, JS::GetArrayBufferMaybeSharedData, JS::GetArrayBufferMaybeSharedLengthAndData, JS::NewArrayBuffer> >",
[
"mozilla::AlignedStorage2",
[
"mozilla::dom::TypedArray<unsigned char, JS::UnwrapArrayBufferMaybeShared, JS::GetArrayBufferMaybeSharedData, JS::GetArrayBufferMaybeSharedLengthAndData, JS::NewArrayBuffer>"
]
]
);
check_parse(
"mozilla::ArrayIterator<const mozilla::dom::binding_detail::RecordEntry<nsTString<char16_t>, mozilla::dom::Nullable<mozilla::dom::TypedArray<unsigned char, JS::UnwrapArrayBufferMaybeShared, JS::GetArrayBufferMaybeSharedData, JS::GetArrayBufferMaybeSharedLengthAndData, JS::NewArrayBuffer> > >&, nsTArray_Impl<mozilla::dom::binding_detail::RecordEntry<nsTString<char16_t>, mozilla::dom::Nullable<mozilla::dom::TypedArray<unsigned char, JS::UnwrapArrayBufferMaybeShared, JS::GetArrayBufferMaybeSharedData, JS::GetArrayBufferMaybeSharedLengthAndData, JS::NewArrayBuffer> > >, nsTArrayInfallibleAllocator> >",
[
"mozilla::ArrayIterator",
[
"const mozilla::dom::binding_detail::RecordEntry<nsTString<char16_t>, mozilla::dom::Nullable<mozilla::dom::TypedArray<unsigned char, JS::UnwrapArrayBufferMaybeShared, JS::GetArrayBufferMaybeSharedData, JS::GetArrayBufferMaybeSharedLengthAndData, JS::NewArrayBuffer> > >&",
"nsTArray_Impl<mozilla::dom::binding_detail::RecordEntry<nsTString<char16_t>, mozilla::dom::Nullable<mozilla::dom::TypedArray<unsigned char, JS::UnwrapArrayBufferMaybeShared, JS::GetArrayBufferMaybeSharedData, JS::GetArrayBufferMaybeSharedLengthAndData, JS::NewArrayBuffer> > >, nsTArrayInfallibleAllocator>"
]
]
);
function check_throws(f, exc) {
try {
f();
} catch (e) {
assertEq(e.message.includes(exc), true, "incorrect exception: " + e.message);
return;
}
assertEq(undefined, exc);
}
// Note that these need to end in '>' or the whole thing will be ignored.
check_throws(() => parseTemplateType("foo>", true), "too many '>' signs");
check_throws(() => parseTemplateType("foo<<>", true), "too many '<' signs");
check_throws(() => parseTemplateType("foo<a::bar<a,b>", true), "too many '<' signs");
check_throws(() => parseTemplateType("foo<a>*>::bar<a,b>", true), "too many '>' signs");
}
// GC Thing and GC Pointer annotations can be inherited from template args if
// this annotation is used. Think of Maybe<T> for example: Maybe<JSObject*> has
// the same GC rules as JSObject*.
var inheritors = Object.keys(typeInfo.InheritFromTemplateArgs).sort((a, b) => a.length - b.length);
for (const csu of inheritors) {
const [templateName, templateArgs] = parseTemplateType(csu);
for (const param of (templateArgs || [])) {
const pos = param.search(/\**$/);
const ptrdness = param.length - pos;
const core_type = param.substr(0, pos);
if (ptrdness == 0) {
addToKeyedList(structureParents, core_type, [csu, "template-param-" + param]);
} else if (ptrdness == 1) {
addToKeyedList(pointerParents, core_type, [csu, "template-param-" + param]);
}
}
}
function Ptr(level) {
if (level < 0)
return Array(-level).fill("&").join("");
else
return Array(level).fill("*").join("");
}
// "typeName is a (pointer to a)^'typePtrLevel' GC type because it contains a field
// named 'child' of type 'childType' (or pointer to 'childType' if fieldPtrLevel == 1),
// which is itself a GCThing or GCPointer."
function markGCType(typeName, child, childType, typePtrLevel, fieldPtrLevel, indent = "") {
// Some types, like UniquePtr, do not mark/trace/relocate their contained
// pointers and so should not hold them live across a GC. UniquePtr in
// particular should be the only thing pointing to a structure containing a
// GCPointer, so nothing else can possibly trace it and it'll die when the
// UniquePtr goes out of scope. So we say that memory pointed to by a
// UniquePtr is just as unsafe as the stack for storing GC pointers.
if (isUnsafeStorage(typeName)) {
// If a UniquePtr<T> itself is on the stack, then there's a problem if
// T contains a Cell*. But the UniquePtr itself stores a T*, not a T,
// so set fieldPtrLevel=-1 to "undo" the pointer. When the type T is
// scanned for pointers and a Cell* is found, then when unwrapping the
// types, UniquePtr<T> will be seen as a T*=Cell** that should be
// treated as a Cell*.
//
// However, that creates the possibility of an infinite loop, if you
// have a type T that contains a UniquePtr<T> (which is allowed, because
// it's storing a T* not a T.)
const ptrLevel = typePtrLevel + fieldPtrLevel - 1;
if (options.verbose) {
printErr(`.${child} : (${childType} : "Cell${Ptr(typePtrLevel)}")${Ptr(fieldPtrLevel)} is-field-of ${typeName} : "Cell${Ptr(ptrLevel)}" [unsafe]`);
}
markGCTypeImpl(typeName, child, childType, ptrLevel, indent);
// Also treat UniquePtr<T> as if it were any other struct.
}
// Example: with:
// struct Pair { JSObject* foo; int bar; };
// struct { Pair** info }***
// make a call to:
// child='info' typePtrLevel=3 fieldPtrLevel=2
// for a final ptrLevel of 5, used to later call:
// child='foo' typePtrLevel=5 fieldPtrLevel=1
//
const ptrLevel = typePtrLevel + fieldPtrLevel;
if (options.verbose) {
printErr(`.${child} : (${childType} : "Cell${Ptr(typePtrLevel)}")${Ptr(fieldPtrLevel)} is-field-of ${typeName} : "Cell${Ptr(ptrLevel)}"`);
}
markGCTypeImpl(typeName, child, childType, ptrLevel, indent);
}
function markGCTypeImpl(typeName, child, childType, ptrLevel, indent) {
// ...except when > 2 levels of pointers away from an actual GC thing, stop
// searching the graph. (This would just be > 1, except that a UniquePtr
// field might still have a GC pointer.)
if (ptrLevel > 2)
return;
if (isRootedGCPointerTypeName(typeName) && !(typeName in typeInfo.RootedPointers))
printErr("FIXME: use in-source annotation for " + typeName);
if (ptrLevel == 0 && (typeName in typeInfo.RootedGCThings))
return;
if (ptrLevel == 1 && (isRootedGCPointerTypeName(typeName) || (typeName in typeInfo.RootedPointers)))
return;
if (ptrLevel == 0) {
if (typeName in typeInfo.NonGCTypes)
return;
if (!(typeName in gcTypes))
gcTypes[typeName] = new Set();
gcTypes[typeName].add(childType);
} else if (ptrLevel == 1) {
if (typeName in typeInfo.NonGCPointers)
return;
if (!(typeName in gcPointers))
gcPointers[typeName] = new Set();
gcPointers[typeName].add(childType);
}
if (ptrLevel < 2) {
if (!gcFields.has(typeName))
gcFields.set(typeName, new Map());
const fields = gcFields.get(typeName);
if (fields.has(child)) {
const [orig_childType, orig_ptrLevel] = fields.get(child);
if (ptrLevel >= orig_ptrLevel) {
// Do not recurse for things more levels of pointers away from Cell.
// This will prevent infinite loops when types are defined recursively
// (eg a struct containing a UniquePtr of itself).
return;
}
}
fields.set(child, [childType, ptrLevel]);
}
if (typeName in structureParents) {
for (var field of structureParents[typeName]) {
var [ holderType, fieldName ] = field;
markGCType(holderType, fieldName, typeName, ptrLevel, 0, indent + " ");
}
}
if (typeName in pointerParents) {
for (var field of pointerParents[typeName]) {
var [ holderType, fieldName ] = field;
markGCType(holderType, fieldName, typeName, ptrLevel, 1, indent + " ");
}
}
}
function addGCType(typeName)
{
pendingGCTypes.push([typeName, '<annotation>', '(annotation)', 0, 0]);
}
function addGCPointer(typeName)
{
pendingGCTypes.push([typeName, '<pointer-annotation>', '(annotation)', 1, 0]);
}
for (const pending of pendingGCTypes) {
markGCType(...pending);
}
// Call a function for a type and every type that contains the type in a field
// or as a base class (which internally is pretty much the same thing --
// subclasses are structs beginning with the base class and adding on their
// local fields.)
function foreachContainingStruct(typeName, func, seen = new Set())
{
function recurse(container, typeName) {
if (seen.has(typeName))
return;
seen.add(typeName);
func(container, typeName);
if (typeName in subClasses) {
for (const sub of subClasses[typeName])
recurse("subclass of " + typeName, sub);
}
if (typeName in structureParents) {
for (const [holder, field] of structureParents[typeName])
recurse(field + " : " + typeName, holder);
}
}
recurse('<annotation>', typeName);
}
for (var type of listNonGCPointers())
typeInfo.NonGCPointers[type] = true;
function explain(csu, indent, seen) {
if (!seen)
seen = new Set();
seen.add(csu);
if (!gcFields.has(csu))
return;
var fields = gcFields.get(csu);
if (fields.has('<annotation>')) {
print(indent + "which is annotated as a GCThing");
return;
}
if (fields.has('<pointer-annotation>')) {
print(indent + "which is annotated as a GCPointer");
return;
}
for (var [ field, [ child, ptrdness ] ] of fields) {
var msg = indent;
if (field[0] == '<')
msg += "inherits from ";
else {
if (field.startsWith("template-param-")) {
msg += "inherits annotations from template parameter '" + field.substr(15) + "' ";
} else {
msg += "contains field '" + field + "' ";
}
if (ptrdness == -1)
msg += "(with a pointer to unsafe storage) holding a ";
else if (ptrdness == 0)
msg += "of type ";
else
msg += "pointing to type ";
}
msg += child;
print(msg);
if (!seen.has(child))
explain(child, indent + " ", seen);
}
}
var origOut = os.file.redirect(options.gcTypes);
for (var csu in gcTypes) {
print("GCThing: " + csu);
explain(csu, " ");
}
for (var csu in gcPointers) {
print("GCPointer: " + csu);
explain(csu, " ");
}
// Redirect output to the typeInfo file and close the gcTypes file.
os.file.close(os.file.redirect(options.typeInfo));
// Compute the set of types that suppress GC within their RAII scopes (eg
// AutoSuppressGC, AutoSuppressGCForAnalysis).
var seen = new Set();
for (let csu in typeInfo.GCSuppressors)
foreachContainingStruct(csu,
(holder, typeName) => { typeInfo.GCSuppressors[typeName] = holder },
seen);
print(JSON.stringify(typeInfo, null, 4));
os.file.close(os.file.redirect(origOut));