diff options
Diffstat (limited to 'Source/WebInspectorUI/UserInterface/Workers')
7 files changed, 2617 insertions, 0 deletions
diff --git a/Source/WebInspectorUI/UserInterface/Workers/Formatter/ESTreeWalker.js b/Source/WebInspectorUI/UserInterface/Workers/Formatter/ESTreeWalker.js new file mode 100644 index 000000000..fafcb6a04 --- /dev/null +++ b/Source/WebInspectorUI/UserInterface/Workers/Formatter/ESTreeWalker.js @@ -0,0 +1,309 @@ +/* + * Copyright (C) 2016 Apple Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, + * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS + * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + */ + +// Visit ES6 ESTree compatible AST nodes in program order. +// <https://github.com/estree/estree>. +// +// The Node types and properties (for ES6) are described in: +// <https://github.com/estree/estree/blob/master/es6.md> +// +// The ESTree spec doesn't appear to be complete yet, so this +// currently assumes some Esprima nodes and properties. +// <http://esprima.org/demo/parse.html> + +// FIXME: Add support for Import/Export/Modules nodes if we allow parsing modules. + +ESTreeWalker = class ESTreeWalker +{ + constructor(before, after) + { + console.assert(typeof before === "function"); + console.assert(typeof after === "function"); + + this._before = before; + this._after = after; + } + + walk(node) + { + this._walk(node, null); + } + + // Private + + _walk(node, parent) + { + if (!node) + return; + + node.parent = parent; + + this._before(node); + this._walkChildren(node); + this._after(node); + } + + _walkArray(array, parent) + { + for (let i = 0; i < array.length; ++i) + this._walk(array[i], parent); + } + + _walkChildren(node) + { + switch (node.type) { + case "AssignmentExpression": + this._walk(node.left, node); + this._walk(node.right, node); + break; + case "ArrayExpression": + case "ArrayPattern": + this._walkArray(node.elements, node); + break; + case "AssignmentPattern": + this._walk(node.left, node); + this._walk(node.right, node); + break; + case "AwaitExpression": + this._walk(node.argument, node); + break; + case "BlockStatement": + this._walkArray(node.body, node); + break; + case "BinaryExpression": + this._walk(node.left, node); + this._walk(node.right, node); + break; + case "BreakStatement": + case "ContinueStatement": + this._walk(node.label, node); + break; + case "CallExpression": + this._walk(node.callee, node); + this._walkArray(node.arguments, node); + break; + case "CatchClause": + this._walk(node.param, node); + this._walk(node.body, node); + break; + case "ClassBody": + this._walkArray(node.body, node); + break; + case "ClassDeclaration": + case "ClassExpression": + this._walk(node.id, node); + this._walk(node.superClass, node); + this._walk(node.body, node); + break; + case "DoWhileStatement": + this._walk(node.body, node); + this._walk(node.test, node); + break; + case "ExpressionStatement": + this._walk(node.expression, node); + break; + case "ForStatement": + this._walk(node.init, node); + this._walk(node.test, node); + this._walk(node.update, node); + this._walk(node.body, node); + break; + case "ForInStatement": + case "ForOfStatement": + this._walk(node.left, node); + this._walk(node.right, node); + this._walk(node.body, node); + break; + case "FunctionDeclaration": + case "FunctionExpression": + case "ArrowFunctionExpression": + this._walk(node.id, node); + this._walkArray(node.params, node); + this._walk(node.body, node); + break; + case "IfStatement": + this._walk(node.test, node); + this._walk(node.consequent, node); + this._walk(node.alternate, node); + break; + case "LabeledStatement": + this._walk(node.label, node); + this._walk(node.body, node); + break; + case "LogicalExpression": + this._walk(node.left, node); + this._walk(node.right, node); + break; + case "MemberExpression": + this._walk(node.object, node); + this._walk(node.property, node); + break; + case "MethodDefinition": + this._walk(node.key, node); + this._walk(node.value, node); + break; + case "NewExpression": + this._walk(node.callee, node); + this._walkArray(node.arguments, node); + break; + case "ObjectExpression": + case "ObjectPattern": + this._walkArray(node.properties, node); + break; + case "Program": + this._walkArray(node.body, node); + break; + case "Property": + this._walk(node.key, node); + this._walk(node.value, node); + break; + case "RestElement": + this._walk(node.argument, node); + break; + case "RestProperty": + this._walk(node.argument, node); + break; + case "ReturnStatement": + this._walk(node.argument, node); + break; + case "SequenceExpression": + this._walkArray(node.expressions, node); + break; + case "SpreadElement": + this._walk(node.argument, node); + break; + case "SpreadProperty": + this._walk(node.argument, node); + break; + case "SwitchStatement": + this._walk(node.discriminant, node); + this._walkArray(node.cases, node); + break; + case "SwitchCase": + this._walk(node.test, node); + this._walkArray(node.consequent, node); + break; + case "ConditionalExpression": + this._walk(node.test, node); + this._walk(node.consequent, node); + this._walk(node.alternate, node); + break; + case "TaggedTemplateExpression": + this._walk(node.tag, node); + this._walk(node.quasi, node); + break; + case "ThrowStatement": + this._walk(node.argument, node); + break; + case "TryStatement": + this._walk(node.block, node); + this._walk(node.handler, node); + this._walk(node.finalizer, node); + break; + case "UnaryExpression": + this._walk(node.argument, node); + break; + case "UpdateExpression": + this._walk(node.argument, node); + break; + case "VariableDeclaration": + this._walkArray(node.declarations, node); + break; + case "VariableDeclarator": + this._walk(node.id, node); + this._walk(node.init, node); + break; + case "WhileStatement": + this._walk(node.test, node); + this._walk(node.body, node); + break; + case "WithStatement": + this._walk(node.object, node); + this._walk(node.body, node); + break; + case "YieldExpression": + this._walk(node.argument, node); + break; + + case "ExportAllDeclaration": + this._walk(node.source, node); + break; + case "ExportNamedDeclaration": + this._walk(node.declaration, node); + this._walkArray(node.specifiers, node); + this._walk(node.source, node); + break; + case "ExportDefaultDeclaration": + this._walk(node.declaration, node); + break; + case "ExportSpecifier": + this._walk(node.local, node); + this._walk(node.exported, node); + break; + case "ImportDeclaration": + this._walkArray(node.specifiers, node); + this._walk(node.source, node); + break; + case "ImportDefaultSpecifier": + this._walk(node.local, node); + break; + case "ImportNamespaceSpecifier": + this._walk(node.local, node); + break; + case "ImportSpecifier": + this._walk(node.imported, node); + this._walk(node.local, node); + break; + case "MetaProperty": + this._walk(node.meta, node); + this._walk(node.property, node); + break; + + // Special case. We want to walk in program order, + // so walk quasi, expression, quasi, expression, etc. + case "TemplateLiteral": + for (var i = 0; i < node.expressions.length; ++i) { + this._walk(node.quasis[i], node); + this._walk(node.expressions[i], node); + } + break; + + // Leaf nodes. + case "DebuggerStatement": + case "EmptyStatement": + case "Identifier": + case "Import": + case "Literal": + case "Super": + case "ThisExpression": + case "TemplateElement": + break; + + default: + console.error("ESTreeWalker unhandled node type", node.type); + break; + } + } +}; diff --git a/Source/WebInspectorUI/UserInterface/Workers/Formatter/EsprimaFormatter.js b/Source/WebInspectorUI/UserInterface/Workers/Formatter/EsprimaFormatter.js new file mode 100644 index 000000000..7feae46b8 --- /dev/null +++ b/Source/WebInspectorUI/UserInterface/Workers/Formatter/EsprimaFormatter.js @@ -0,0 +1,934 @@ +/* + * Copyright (C) 2016 Apple Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, + * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS + * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + */ + +// There is no standard for tokenizer types in JavaScript ASTs. +// This currently assumes Esprima tokens, ranges, and comments. +// <http://esprima.org/demo/parse.html> + +EsprimaFormatter = class EsprimaFormatter +{ + constructor(sourceText, sourceType, indentString = " ") + { + this._success = false; + + let tree = (function() { + try { + return esprima.parse(sourceText, {attachComment: true, range: true, tokens: true, sourceType}); + } catch (error) { + return null; + } + })(); + + if (!tree) + return; + + this._sourceText = sourceText; + this._builder = null; + + let walker = new ESTreeWalker(this._before.bind(this), this._after.bind(this)); + + this._tokens = tree.tokens; + this._tokensLength = this._tokens.length; + this._tokenIndex = 0; + + this._lineEndings = sourceText.lineEndings(); + this._lineEndingsIndex = 0; + + this._builder = new FormatterContentBuilder(indentString); + this._builder.setOriginalLineEndings(this._lineEndings.slice()); + + walker.walk(tree); + this._afterProgram(tree); + this._builder.appendNewline(); + + this._success = true; + } + + // Static + + static isWhitespace(ch) + { + return isECMAScriptWhitespace(ch) || isECMAScriptLineTerminator(ch); + } + + // Public + + get success() + { + return this._success; + } + + get formattedText() + { + if (!this._success) + return null; + return this._builder.formattedContent; + } + + get sourceMapData() + { + if (!this._success) + return null; + return this._builder.sourceMapData; + } + + // Private + + _insertNewlinesBeforeToken(token) + { + let force = false; + while (token.range[0] > this._lineEndings[this._lineEndingsIndex]) { + this._builder.appendNewline(force); + this._lineEndingsIndex++; + force = true; + } + } + + _insertComment(comment) + { + if (comment.type === "Line") + this._builder.appendToken("//" + comment.value, comment.range[0]); + else if (comment.type === "Block") + this._builder.appendToken("/*" + comment.value + "*/", comment.range[0]); + this._builder.appendNewline(); + comment.__handled = true; + } + + _insertSameLineTrailingComments(node) + { + let endOfLine = this._lineEndings[this._lineEndingsIndex]; + for (let comment of node.trailingComments) { + if (comment.range[0] > endOfLine) + break; + this._builder.removeLastNewline(); + this._builder.appendSpace(); + this._insertComment(comment); + } + } + + _insertCommentsAndNewlines(comments) + { + for (let comment of comments) { + // A previous node may have handled this as a trailing comment. + if (comment.__handled) + continue; + + // We expect the comment to be ahead of the last line. + // But if it is ahead of the next line ending, then it + // was preceded by an empty line. So include that. + if (comment.range[0] > this._lineEndings[this._lineEndingsIndex + 1]) + this._builder.appendNewline(true); + + this._insertComment(comment); + + // Remove line endings for this comment. + while (comment.range[1] > this._lineEndings[this._lineEndingsIndex]) + this._lineEndingsIndex++; + } + } + + _before(node) + { + if (!node.parent) + return; + + // Handle the tokens before this node, so in the context of our parent node. + while (this._tokenIndex < this._tokensLength && this._tokens[this._tokenIndex].range[0] < node.range[0]) { + let token = this._tokens[this._tokenIndex++]; + this._insertNewlinesBeforeToken(token); + this._handleTokenAtNode(token, node.parent); + } + + if (node.leadingComments) + this._insertCommentsAndNewlines(node.leadingComments); + } + + _after(node) + { + // Handle any other tokens inside of this node before exiting. + while (this._tokenIndex < this._tokensLength && this._tokens[this._tokenIndex].range[0] < node.range[1]) { + let token = this._tokens[this._tokenIndex++]; + this._insertNewlinesBeforeToken(token); + this._handleTokenAtNode(token, node); + } + + this._exitNode(node); + + if (node.trailingComments) + this._insertSameLineTrailingComments(node); + } + + _isInForHeader(node) + { + let parent = node.parent; + if (!parent) + return false; + + return (parent.type === "ForStatement" || parent.type === "ForInStatement" || parent.type === "ForOfStatement") && node !== parent.body; + } + + _isRangeWhitespace(from, to) + { + let substring = this._sourceText.substring(from, to); + for (let i = 0; i < substring.length; ++i) { + if (!EsprimaFormatter.isWhitespace(substring.charCodeAt(i))) + return false; + } + + return true; + } + + _handleTokenAtNode(token, node) + { + let builder = this._builder; + let nodeType = node.type; + let tokenType = token.type; + let tokenValue = token.value; + let tokenOffset = token.range[0]; + + // Very common types that just pass through. + if (nodeType === "MemberExpression" || nodeType === "Literal" || nodeType === "ThisExpression" || nodeType === "UpdateExpression") { + builder.appendToken(tokenValue, tokenOffset); + return; + } + + // Most identifiers just pass through, but a few are special. + if (nodeType === "Identifier") { + builder.appendToken(tokenValue, tokenOffset); + if (tokenValue === "async" && node.parent.type === "Property" && node.parent.value.async && token.range[1] !== node.range[1]) + builder.appendSpace(); + return; + } + + // Most newline handling is done with semicolons. However, we preserve + // newlines so code relying on automatic semicolon insertion should + // continue to work. + if (tokenValue === ";") { + // Avoid newlines for for loop header semicolons. + if (nodeType === "ForStatement") { + builder.appendToken(tokenValue, tokenOffset); + // Do not include spaces in empty for loop header sections: for(;;) + if (node.test || node.update) { + if (node.test && this._isRangeWhitespace(token.range[1], node.test.range[0])) + builder.appendSpace(); + else if (node.update && this._isRangeWhitespace(token.range[1], node.update.range[0])) + builder.appendSpace(); + } + return; + } + + // Sometimes more specific nodes gets the semicolon inside a for loop header. + // Avoid newlines. Example is a VariableDeclaration in: for (var a, b; ...; ...). + if (this._isInForHeader(node)) { + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + + // Avoid newline for single statement arrow functions with semicolons. + if (node.parent.type === "BlockStatement" && node.parent.body.length === 1 && node.parent.parent && node.parent.parent.type === "ArrowFunctionExpression") { + builder.appendToken(tokenValue, tokenOffset); + return; + } + + builder.appendToken(tokenValue, tokenOffset); + builder.appendNewline(); + return; + } + + if (nodeType === "CallExpression" || nodeType === "ArrayExpression" || nodeType === "ArrayPattern" || nodeType === "ObjectPattern" || nodeType === "SequenceExpression") { + if (tokenValue === ",") { + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "LogicalExpression" || nodeType === "BinaryExpression") { + if (tokenValue !== "(" && tokenValue !== ")") { + builder.appendSpace(); + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + if (tokenType === "Keyword") { + // in, instanceof, ... + builder.appendSpace(); + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "BlockStatement") { + let isSingleStatementArrowFunction = node.parent.type === "ArrowFunctionExpression" && node.body.length === 1; + if (tokenValue === "{") { + // Class methods we put the opening brace on its own line. + if (node.parent && node.parent.parent && node.parent.parent.type === "MethodDefinition" && node.body.length) { + builder.appendNewline(); + builder.appendToken(tokenValue, tokenOffset); + builder.appendNewline(); + builder.indent(); + return; + } + builder.appendToken(tokenValue, tokenOffset); + if (node.body.length && !isSingleStatementArrowFunction) + builder.appendNewline(); + builder.indent(); + return; + } + if (tokenValue === "}") { + if (node.body.length && !isSingleStatementArrowFunction) + builder.appendNewline(); + builder.dedent(); + builder.appendToken(tokenValue, tokenOffset); + return; + } + console.warn("Unexpected BlockStatement token", token); + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "VariableDeclaration") { + if (tokenValue === ",") { + if (this._isInForHeader(node)) { + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + builder.appendToken(tokenValue, tokenOffset); + builder.appendNewline(); + return; + } + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + // If this is a multiple variable declaration, indent. + if (node.declarations.length > 1 && !node.__autoDedent) { + builder.indent(); + node.__autoDedent = true; + } + return; + } + + if (nodeType === "VariableDeclarator" || nodeType === "AssignmentExpression") { + if (tokenType === "Punctuator") { + let surroundWithSpaces = tokenValue !== "(" && tokenValue !== ")"; + if (surroundWithSpaces) + builder.appendSpace(); + builder.appendToken(tokenValue, tokenOffset); + if (surroundWithSpaces) + builder.appendSpace(); + return; + } + console.warn("Unexpected " + nodeType + " token", token); + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "IfStatement") { + if (tokenType === "Keyword") { + if (tokenValue === "else") { + if (node.__autoDedent) { + builder.dedent(); + node.__autoDedent = false; + } + builder.appendSpace(); + builder.appendToken(tokenValue, tokenOffset); + + if (node.alternate && (node.alternate.type !== "BlockStatement" && node.alternate.type !== "IfStatement")) { + builder.appendNewline(); + builder.indent(); + node.__autoDedent = true; + } else + builder.appendSpace(); + return; + } + + console.assert(tokenValue === "if", token); + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + + // The last ')' in if(){}. + if (tokenValue === ")" && this._isRangeWhitespace(token.range[1], node.consequent.range[0])) { + if (node.consequent.type === "BlockStatement") { + // The block will handle indenting. + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + + builder.appendToken(tokenValue, tokenOffset); + builder.appendNewline(); + builder.indent(); + node.__autoDedent = true; + return; + } + + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "ReturnStatement") { + if (tokenValue === ";") { + builder.appendToken(tokenValue, tokenOffset); + return; + } + builder.appendToken(tokenValue, tokenOffset); + if (node.argument) { + // Multi-line LogicalExpressions (&& and ||) are a common style of return + // statement that benefits from indentation. + if (node.argument.type === "LogicalExpression" && !node.__autoDedent) { + builder.indent(); + node.__autoDedent = true; + } + builder.appendSpace(); + } + return; + } + + if (nodeType === "FunctionDeclaration" || nodeType === "FunctionExpression") { + if (tokenType === "Keyword") { + console.assert(tokenValue === "function", token); + builder.appendToken(tokenValue, tokenOffset); + if (node.id) + builder.appendSpace(); + return; + } + if (tokenType === "Punctuator") { + if (tokenValue === "*") { + builder.removeLastWhitespace(); + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + builder.appendToken(tokenValue, tokenOffset); + if (tokenValue === ")" || tokenValue === ",") + builder.appendSpace(); + return; + } + if (tokenType === "Identifier" && tokenValue === "async") { + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "WhileStatement" || nodeType === "WithStatement") { + if (tokenValue === "while" || tokenValue === "with") { + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + + // The last ')' in while(){} or with(){}. + if (tokenValue === ")" && this._isRangeWhitespace(token.range[1], node.body.range[0])) { + if (node.body.type === "BlockStatement") { + // The block will handle indenting. + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + + builder.appendToken(tokenValue, tokenOffset); + builder.appendNewline(); + builder.indent(); + node.__autoDedent = true; + return; + } + + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "ForStatement" || nodeType === "ForOfStatement" || nodeType === "ForInStatement") { + if (tokenValue === "for") { + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + if (tokenValue === "in" || tokenValue === "of") { + builder.appendSpace(); + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + + // The last ')' in for(){}. + if (tokenValue === ")" && this._isRangeWhitespace(token.range[1], node.body.range[0])) { + if (node.body.type === "BlockStatement") { + // The block will handle indenting. + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + + builder.appendToken(tokenValue, tokenOffset); + builder.appendNewline(); + builder.indent(); + node.__autoDedent = true; + return; + } + + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "SwitchStatement") { + if (tokenValue === "switch") { + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + if (tokenType === "Punctuator") { + if (tokenValue === ")") { + // FIXME: Would be nice to only add a space if this the ')' closing the discriminant: switch((1)){} + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + if (tokenValue === "{") { + builder.appendToken(tokenValue, tokenOffset); + builder.appendNewline(); + return; + } + if (tokenValue === "}") { + builder.appendNewline(); + builder.appendToken(tokenValue, tokenOffset); + builder.appendNewline(); + return; + } + } + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "SwitchCase") { + if (tokenType === "Keyword") { + if (tokenValue === "case") { + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + if (tokenValue === "default") { + builder.appendToken(tokenValue, tokenOffset); + return; + } + console.warn("Unexpected SwitchCase Keyword token", token); + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (tokenValue === ":") { + builder.appendToken(tokenValue, tokenOffset); + builder.appendNewline(); + if (node.consequent.length) { + builder.indent(); + node.__autoDedent = true; + } + return; + } + + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "NewExpression") { + if (tokenValue === "new") { + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + if (tokenValue === ",") { + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "DoWhileStatement") { + if (tokenValue === "do") { + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + if (tokenValue === "while") { + builder.appendSpace(); + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "ThrowStatement") { + if (tokenValue === "throw") { + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "UnaryExpression") { + if (tokenType === "Keyword") { + // typeof, instanceof, void + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "ConditionalExpression") { + if (tokenValue === "?" || tokenValue === ":") { + builder.appendSpace(); + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "ObjectExpression") { + // FIXME: It would be nice to detect if node.properties is very short + // and the node.properties themselves are very small then inline them + // instead of always adding newlines. Objects like: {a}, {a:1} but + // not objects like {a:function(){1;}}. + if (tokenValue === "{") { + builder.appendToken(tokenValue, tokenOffset); + if (node.properties.length) { + builder.appendNewline(); + builder.indent(); + } + return; + } + if (tokenValue === "}") { + if (node.properties.length) { + builder.appendNewline(); + builder.dedent(); + } + builder.appendToken(tokenValue, tokenOffset); + return; + } + if (tokenValue === ",") { + builder.appendToken(tokenValue, tokenOffset); + if (node.properties.length) + builder.appendNewline(); + else + builder.appendSpace(); + return; + } + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "ArrowFunctionExpression") { + if (tokenType === "Punctuator") { + if (tokenValue === "=>") { + builder.appendSpace(); + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + if (tokenValue === ",") { + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + } + builder.appendToken(tokenValue, tokenOffset); + if (tokenType === "Identifier" && tokenValue === "async") + builder.appendSpace(); + return; + } + + if (nodeType === "AwaitExpression") { + builder.appendToken(tokenValue, tokenOffset); + if (tokenType === "Identifier" && tokenValue === "await") + builder.appendSpace(); + return; + } + + if (nodeType === "Property") { + console.assert(tokenValue === ":" || tokenValue === "get" || tokenValue === "set" || tokenValue === "async" || tokenValue === "*" || tokenValue === "[" || tokenValue === "]" || tokenValue === "(" || tokenValue === ")", token); + builder.appendToken(tokenValue, tokenOffset); + if (tokenValue === ":" || tokenValue === "get" || tokenValue === "set" || tokenValue === "async") + builder.appendSpace(); + return; + } + + if (nodeType === "MethodDefinition") { + console.assert(tokenValue === "static" || tokenValue === "get" || tokenValue === "set" || tokenValue === "async" || tokenValue === "*" || tokenValue === "[" || tokenValue === "]" || tokenValue === "(" || tokenValue === ")", token); + builder.appendToken(tokenValue, tokenOffset); + if (tokenValue === "static" || tokenValue === "get" || tokenValue === "set" || tokenValue === "async") + builder.appendSpace(); + return; + } + + if (nodeType === "BreakStatement" || nodeType === "ContinueStatement") { + builder.appendToken(tokenValue, tokenOffset); + if (tokenType === "Keyword" && node.label) + builder.appendSpace(); + return; + } + + if (nodeType === "LabeledStatement") { + console.assert(tokenValue === ":", token); + builder.appendToken(tokenValue, tokenOffset); + builder.appendNewline(); + return; + } + + if (nodeType === "TryStatement") { + if (tokenValue === "try") { + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + if (tokenValue === "finally") { + builder.appendSpace(); + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + console.warn("Unexpected TryStatement token", token); + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "CatchClause") { + if (tokenValue === "catch") { + builder.appendSpace(); + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + if (tokenValue === ")") { + // The block will handle indenting. + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "ClassExpression" || nodeType === "ClassDeclaration") { + if (tokenValue === "class") { + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + if (tokenValue === "extends") { + builder.appendSpace(); + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "ClassBody") { + if (tokenValue === "{") { + if (node.parent.id) + builder.appendSpace(); + builder.appendToken(tokenValue, tokenOffset); + if (node.body.length) + builder.appendNewline(); + builder.indent(); + return; + } + if (tokenValue === "}") { + if (node.body.length) + builder.appendNewline(); + builder.dedent(); + builder.appendToken(tokenValue, tokenOffset); + builder.appendNewline(); + return; + } + console.warn("Unexpected ClassBody token", token); + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "YieldExpression") { + if (tokenType === "Keyword") { + console.assert(tokenValue === "yield", token); + builder.appendToken(tokenValue, tokenOffset); + if (node.argument) + builder.appendSpace(); + return; + } + builder.appendToken(tokenValue, tokenOffset); + return; + } + + if (nodeType === "ImportDeclaration" || nodeType === "ExportNamedDeclaration") { + if (tokenValue === "}" || (tokenType === "Identifier" && tokenValue === "from")) + builder.appendSpace(); + builder.appendToken(tokenValue, tokenOffset); + if (tokenValue !== "}") + builder.appendSpace(); + return; + } + + if (nodeType === "ExportSpecifier" || nodeType === "ImportSpecifier") { + if (tokenType === "Identifier" && tokenValue === "as") + builder.appendSpace(); + builder.appendToken(tokenValue, tokenOffset); + builder.appendSpace(); + return; + } + + if (nodeType === "ExportAllDeclaration" || nodeType === "ExportDefaultDeclaration" || nodeType === "ImportDefaultSpecifier" || nodeType === "ImportNamespaceSpecifier") { + builder.appendToken(tokenValue, tokenOffset); + if (tokenValue !== "(" && tokenValue !== ")") + builder.appendSpace(); + return; + } + + // Include these here so we get only get warnings about unhandled nodes. + if (nodeType === "ExpressionStatement" + || nodeType === "SpreadElement" + || nodeType === "SpreadProperty" + || nodeType === "Super" + || nodeType === "Import" + || nodeType === "MetaProperty" + || nodeType === "RestElement" + || nodeType === "RestProperty" + || nodeType === "TemplateElement" + || nodeType === "TemplateLiteral" + || nodeType === "DebuggerStatement" + || nodeType === "AssignmentPattern") { + builder.appendToken(tokenValue, tokenOffset); + return; + } + + // Warn about possible unhandled types. + console.warn(nodeType, tokenValue); + + // Fallback behavior in case there are unhandled types. + builder.appendToken(tokenValue, tokenOffset); + + if (tokenType === "Keyword") + builder.appendSpace(); + } + + _exitNode(node) + { + if (node.__autoDedent) + this._builder.dedent(); + + if (node.type === "BlockStatement") { + if (node.parent) { + // Newline after if(){} + if (node.parent.type === "IfStatement" && (!node.parent.alternate || node.parent.consequent !== node)) { + this._builder.appendNewline(); + return; + } + // Newline after for(){} + if (node.parent.type === "ForStatement" || node.parent.type === "ForOfStatement" || node.parent.type === "ForInStatement") { + this._builder.appendNewline(); + return; + } + // Newline after while(){} + if (node.parent.type === "WhileStatement") { + this._builder.appendNewline(); + return; + } + // Newline after function(){} + if (node.parent.type === "FunctionDeclaration") { + this._builder.appendNewline(); + return; + } + // Newline after catch block in try{}catch(e){} + if (node.parent.type === "CatchClause" && !node.parent.parent.finalizer) { + this._builder.appendNewline(); + return; + } + // Newline after finally block in try{}catch(e){}finally{} + if (node.parent.type === "TryStatement" && node.parent.finalizer && node.parent.finalizer === node) { + this._builder.appendNewline(); + return; + } + // Newline after class body methods in class {method(){}} + if (node.parent.parent && node.parent.parent.type === "MethodDefinition") { + this._builder.appendNewline(); + return; + } + // Newline after anonymous block inside a block or program. + if (node.parent.type === "BlockStatement" || node.parent.type === "Program") { + this._builder.appendNewline(); + return; + } + } + return; + } + } + + _afterProgram(programNode) + { + if (!programNode) + return; + + console.assert(programNode.type === "Program"); + + // If a program ends with comments, Esprima puts those + // comments on the last node of the body. However, if + // a program is entirely comments, then they are + // leadingComments on the program node. + + if (programNode.body.length) { + let lastNode = programNode.body[programNode.body.length - 1]; + if (lastNode.trailingComments) + this._insertCommentsAndNewlines(lastNode.trailingComments); + } else { + if (programNode.leadingComments) + this._insertCommentsAndNewlines(programNode.leadingComments); + console.assert(!programNode.trailingComments); + } + } +}; + +EsprimaFormatter.SourceType = { + Script: "script", + Module: "module", +}; diff --git a/Source/WebInspectorUI/UserInterface/Workers/Formatter/FormatterContentBuilder.js b/Source/WebInspectorUI/UserInterface/Workers/Formatter/FormatterContentBuilder.js new file mode 100644 index 000000000..a60a27e32 --- /dev/null +++ b/Source/WebInspectorUI/UserInterface/Workers/Formatter/FormatterContentBuilder.js @@ -0,0 +1,244 @@ +/* + * Copyright (C) 2013 Apple Inc. All rights reserved. + * Copyright (C) 2015 Tobias Reiss <tobi+webkit@basecode.de> + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, + * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS + * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + */ + +FormatterContentBuilder = class FormatterContentBuilder +{ + constructor(indentString) + { + this._originalContent = null; + this._formattedContent = []; + this._formattedContentLength = 0; + + this._startOfLine = true; + this.lastTokenWasNewline = false; + this.lastTokenWasWhitespace = false; + this.lastNewlineAppendWasMultiple = false; + + this._indent = 0; + this._indentString = indentString; + this._indentCache = ["", this._indentString]; + + this._mapping = {original: [0], formatted: [0]}; + this._originalLineEndings = []; + this._formattedLineEndings = []; + this._originalOffset = 0; + this._formattedOffset = 0; + + this._lastOriginalPosition = 0; + this._lastFormattedPosition = 0; + } + + // Public + + get originalContent() + { + return this._originalContent; + } + + get formattedContent() + { + let formatted = this._formattedContent.join(""); + console.assert(formatted.length === this._formattedContentLength); + return formatted; + } + + get sourceMapData() + { + return { + mapping: this._mapping, + originalLineEndings: this._originalLineEndings, + formattedLineEndings: this._formattedLineEndings, + }; + } + + setOriginalContent(originalContent) + { + console.assert(!this._originalContent); + this._originalContent = originalContent; + } + + setOriginalLineEndings(originalLineEndings) + { + console.assert(!this._originalLineEndings.length); + this._originalLineEndings = originalLineEndings; + } + + appendToken(string, originalPosition) + { + if (this._startOfLine) + this._appendIndent(); + + this._addMappingIfNeeded(originalPosition); + + this._append(string); + this._startOfLine = false; + this.lastTokenWasNewline = false; + this.lastTokenWasWhitespace = false; + } + + appendSpace() + { + if (!this._startOfLine) { + this._append(" "); + this.lastTokenWasNewline = false; + this.lastTokenWasWhitespace = true; + } + } + + appendNewline(force) + { + if ((!this.lastTokenWasNewline && !this._startOfLine) || force) { + if (this.lastTokenWasWhitespace) + this._popFormattedContent(); + this._append("\n"); + this._addFormattedLineEnding(); + this._startOfLine = true; + this.lastTokenWasNewline = true; + this.lastTokenWasWhitespace = false; + this.lastNewlineAppendWasMultiple = false; + } + } + + appendMultipleNewlines(newlines) + { + console.assert(newlines > 0); + + let wasMultiple = newlines > 1; + + while (newlines-- > 0) + this.appendNewline(true); + + if (wasMultiple) + this.lastNewlineAppendWasMultiple = true; + } + + removeLastNewline() + { + console.assert(this.lastTokenWasNewline); + console.assert(this._formattedContent.lastValue === "\n"); + if (this.lastTokenWasNewline) { + this._popFormattedContent(); + this._formattedLineEndings.pop(); + this._startOfLine = false; + this.lastTokenWasNewline = false; + this.lastTokenWasWhitespace = false; + } + } + + removeLastWhitespace() + { + console.assert(this.lastTokenWasWhitespace); + console.assert(this._formattedContent.lastValue === " "); + if (this.lastTokenWasWhitespace) { + this._popFormattedContent(); + // No need to worry about `_startOfLine` and `lastTokenWasNewline` + // because `appendSpace` takes care of not adding whitespace + // to the beginning of a line. + this.lastTokenWasWhitespace = false; + } + } + + indent() + { + ++this._indent; + } + + dedent() + { + --this._indent; + + console.assert(this._indent >= 0); + if (this._indent < 0) + this._indent = 0; + } + + addOriginalLineEnding(originalPosition) + { + this._originalLineEndings.push(originalPosition); + } + + finish() + { + this.appendNewline(); + } + + // Private + + _popFormattedContent() + { + let removed = this._formattedContent.pop(); + this._formattedContentLength -= removed.length; + } + + _append(str) + { + this._formattedContent.push(str); + this._formattedContentLength += str.length; + } + + _appendIndent() + { + // Indent is already in the cache. + if (this._indent < this._indentCache.length) { + this._append(this._indentCache[this._indent]); + return; + } + + // Indent was not in the cache, fill up the cache up with what was needed. + let maxCacheIndent = 20; + let max = Math.min(this._indent, maxCacheIndent); + for (let i = this._indentCache.length; i <= max; ++i) + this._indentCache[i] = this._indentCache[i - 1] + this._indentString; + + // Append indents as needed. + let indent = this._indent; + do { + if (indent >= maxCacheIndent) + this._append(this._indentCache[maxCacheIndent]); + else + this._append(this._indentCache[indent]); + indent -= maxCacheIndent; + } while (indent > 0); + } + + _addMappingIfNeeded(originalPosition) + { + if (originalPosition - this._lastOriginalPosition === this._formattedContentLength - this._lastFormattedPosition) + return; + + this._mapping.original.push(this._originalOffset + originalPosition); + this._mapping.formatted.push(this._formattedOffset + this._formattedContentLength); + + this._lastOriginalPosition = originalPosition; + this._lastFormattedPosition = this._formattedContentLength; + } + + _addFormattedLineEnding() + { + console.assert(this._formattedContent.lastValue === "\n"); + this._formattedLineEndings.push(this._formattedContentLength - 1); + } +}; diff --git a/Source/WebInspectorUI/UserInterface/Workers/Formatter/FormatterUtilities.js b/Source/WebInspectorUI/UserInterface/Workers/Formatter/FormatterUtilities.js new file mode 100644 index 000000000..3d77c14d2 --- /dev/null +++ b/Source/WebInspectorUI/UserInterface/Workers/Formatter/FormatterUtilities.js @@ -0,0 +1,64 @@ +/* + * Copyright (C) 2016 Apple Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, + * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS + * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + */ + +Object.defineProperty(Array.prototype, "lastValue", +{ + get() + { + if (!this.length) + return undefined; + return this[this.length - 1]; + } +}); + +Object.defineProperty(String.prototype, "lineEndings", +{ + value() + { + let lineEndings = []; + + let index = this.indexOf("\n"); + while (index !== -1) { + lineEndings.push(index); + index = this.indexOf("\n", index + 1); + } + + lineEndings.push(this.length); + return lineEndings; + } +}); + +// Whitespace helpers from Esprima. + +// ECMA-262 11.2 White Space +function isECMAScriptWhitespace(ch) { + return (ch === 0x20) || (ch === 0x09) || (ch === 0x0B) || (ch === 0x0C) || (ch === 0xA0) || + (ch >= 0x1680 && [0x1680, 0x180E, 0x2000, 0x2001, 0x2002, 0x2003, 0x2004, 0x2005, 0x2006, 0x2007, 0x2008, 0x2009, 0x200A, 0x202F, 0x205F, 0x3000, 0xFEFF].indexOf(ch) >= 0); +} + +// ECMA-262 11.3 Line Terminators +function isECMAScriptLineTerminator(ch) { + return (ch === 0x0A) || (ch === 0x0D) || (ch === 0x2028) || (ch === 0x2029); +} diff --git a/Source/WebInspectorUI/UserInterface/Workers/Formatter/FormatterWorker.js b/Source/WebInspectorUI/UserInterface/Workers/Formatter/FormatterWorker.js new file mode 100644 index 000000000..9c056f11d --- /dev/null +++ b/Source/WebInspectorUI/UserInterface/Workers/Formatter/FormatterWorker.js @@ -0,0 +1,108 @@ +/* + * Copyright (C) 2016 Apple Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, + * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS + * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + */ + +importScripts(...[ + "../../External/Esprima/esprima.js", + "FormatterUtilities.js", + "FormatterContentBuilder.js", + "ESTreeWalker.js", + "EsprimaFormatter.js", +]); + +FormatterWorker = class FormatterWorker +{ + constructor() + { + self.addEventListener("message", this._handleMessage.bind(this)); + } + + // Actions + + formatJavaScript(sourceText, isModule, indentString, includeSourceMapData) + { + let sourceType = isModule ? EsprimaFormatter.SourceType.Module : EsprimaFormatter.SourceType.Script; + + // Format a JavaScript program. + let formatter = new EsprimaFormatter(sourceText, sourceType, indentString); + if (formatter.success) { + let result = {formattedText: formatter.formattedText}; + if (includeSourceMapData) { + result.sourceMapData = formatter.sourceMapData; + // NOTE: With the EsprimaFormatter, multi-line tokens, such as comments and strings, + // would not have had their newlines counted properly by the builder. Rather then + // modify the formatter to check and account for newlines in every token just + // compute the list of line endings directly on the result. + result.sourceMapData.formattedLineEndings = result.formattedText.lineEndings(); + } + return result; + } + + // Format valid JSON. + // The formatter could fail if this was just a JSON string. So try a JSON.parse and stringify. + // This will produce empty source map data, but it is not code, so it is not as important. + try { + let jsonStringified = JSON.stringify(JSON.parse(sourceText), null, indentString); + let result = {formattedText: jsonStringified}; + if (includeSourceMapData) + result.sourceMapData = {mapping: {original: [], formatted: []}, originalLineEndings: [], formattedLineEndings: []}; + return result; + } catch (e) {} + + // Format invalid JSON and anonymous functions. + // Some applications do not use JSON.parse but eval on JSON content. That is more permissive + // so try to format invalid JSON. Again no source map data since it is not code. + // Likewise, an unnamed function's toString() produces a "function() { ... }", which is not + // a valid program on its own. Wrap it in parenthesis to make it a function expression, + // which is a valid program. + let invalidJSONFormatter = new EsprimaFormatter("(" + sourceText + ")", sourceType, indentString); + if (invalidJSONFormatter.success) { + let formattedTextWithParens = invalidJSONFormatter.formattedText; + let result = {formattedText: formattedTextWithParens.substring(1, formattedTextWithParens.length - 2)}; // Remove "(" and ")\n". + if (includeSourceMapData) + result.sourceMapData = {mapping: {original: [], formatted: []}, originalLineEndings: [], formattedLineEndings: []}; + return result; + } + + return {formattedText: null}; + } + + // Private + + _handleMessage(event) + { + let data = event.data; + + // Action. + if (data.actionName) { + let result = this[data.actionName](...data.actionArguments); + self.postMessage({callId: data.callId, result}); + return; + } + + console.error("Unexpected FormatterWorker message", data); + } +}; + +self.formatterWorker = new FormatterWorker; diff --git a/Source/WebInspectorUI/UserInterface/Workers/HeapSnapshot/HeapSnapshot.js b/Source/WebInspectorUI/UserInterface/Workers/HeapSnapshot/HeapSnapshot.js new file mode 100644 index 000000000..b9e14dd65 --- /dev/null +++ b/Source/WebInspectorUI/UserInterface/Workers/HeapSnapshot/HeapSnapshot.js @@ -0,0 +1,838 @@ +/* + * Copyright (C) 2011 Google Inc. All rights reserved. + * Copyright (C) 2016 Apple Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +// nodes +// [<0:id>, <1:size>, <2:classNameTableIndex>, <3:internal>] +const nodeFieldCount = 4; +const nodeIdOffset = 0; +const nodeSizeOffset = 1; +const nodeClassNameOffset = 2; +const nodeInternalOffset = 3; + +// edges +// [<0:fromId>, <1:toId>, <2:typeTableIndex>, <3:edgeDataIndexOrEdgeNameIndex>] +const edgeFieldCount = 4; +const edgeFromIdOffset = 0; +const edgeToIdOffset = 1; +const edgeTypeOffset = 2; +const edgeDataOffset = 3; + +// Other constants. +const rootNodeIndex = 0; +const rootNodeOrdinal = 0; +const rootNodeIdentifier = 0; + +// Terminology: +// - `nodeIndex` is an index into the `nodes` list. +// - `nodeOrdinal` is the order of the node in the `nodes` list. (nodeIndex / nodeFieldCount). +// - `nodeIdentifier` is the node's id value. (nodes[nodeIndex + nodeIdOffset]). +// - `edgeIndex` is an index into the `edges` list. +// +// Lists: +// - _nodeOrdinalToFirstOutgoingEdge - `nodeOrdinal` to `edgeIndex` in `edges`. +// Iterate edges by walking `edges` (edgeFieldCount) and checking if fromIdentifier is current. +// - _nodeOrdinalToFirstIncomingEdge - `nodeOrdinal` to `incomingEdgeIndex` in `incomingEdges`. +// Iterate edges by walking `incomingEdges` until `nodeOrdinal+1`'s first incoming edge index. +// - _nodeOrdinalToDominatorNodeOrdinal - `nodeOrdinal` to `nodeOrdinal` of dominator. +// - _nodeOrdinalToRetainedSizes - `nodeOrdinal` to retain size value. +// - _nodeOrdinalIsDead - `nodeOrdinal` is dead or alive. +// +// Temporary Lists: +// - nodeOrdinalToPostOrderIndex - `nodeOrdinal` to a `postOrderIndex`. +// - postOrderIndexToNodeOrdinal - `postOrderIndex` to a `nodeOrdinal`. + +let nextSnapshotIdentifier = 1; + +HeapSnapshot = class HeapSnapshot +{ + constructor(objectId, snapshotDataString, title = null) + { + this._identifier = nextSnapshotIdentifier++; + this._objectId = objectId; + this._title = title; + + let json = JSON.parse(snapshotDataString); + snapshotDataString = null; + + let {version, nodes, nodeClassNames, edges, edgeTypes, edgeNames} = json; + console.assert(version === 1, "Expect JavaScriptCore Heap Snapshot version 1"); + + this._nodes = nodes; + this._nodeCount = nodes.length / nodeFieldCount; + + this._edges = edges; + this._edgeCount = edges.length / edgeFieldCount; + + this._edgeTypesTable = edgeTypes; + this._edgeNamesTable = edgeNames; + this._nodeClassNamesTable = nodeClassNames; + + this._totalSize = 0; + this._nodeIdentifierToOrdinal = new Map; // <node identifier> => nodeOrdinal + this._lastNodeIdentifier = 0; + for (let nodeIndex = 0; nodeIndex < nodes.length; nodeIndex += nodeFieldCount) { + let nodeOrdinal = nodeIndex / nodeFieldCount; + let nodeIdentifier = nodes[nodeIndex + nodeIdOffset]; + this._nodeIdentifierToOrdinal.set(nodeIdentifier, nodeOrdinal); + this._totalSize += nodes[nodeIndex + nodeSizeOffset]; + if (nodeIdentifier > this._lastNodeIdentifier) + this._lastNodeIdentifier = nodeIdentifier; + } + + // FIXME: Replace toIdentifier and fromIdentifier in edges with nodeIndex to reduce hash lookups? + + this._nodeOrdinalToFirstOutgoingEdge = new Uint32Array(this._nodeCount); // nodeOrdinal => edgeIndex + this._buildOutgoingEdges(); + + this._nodeOrdinalToFirstIncomingEdge = new Uint32Array(this._nodeCount + 1); // nodeOrdinal => incomingNodes/incomingEdges index + this._incomingNodes = new Uint32Array(this._edgeCount); // from nodeOrdinals. + this._incomingEdges = new Uint32Array(this._edgeCount); // edgeIndex. + this._buildIncomingEdges(); + + let {nodeOrdinalToPostOrderIndex, postOrderIndexToNodeOrdinal} = this._buildPostOrderIndexes(); + + this._nodeOrdinalToDominatorNodeOrdinal = new Uint32Array(this._nodeCount); + this._nodeOrdinalIsGCRoot = new Uint8Array(this._nodeCount); + this._buildDominatorIndexes(nodeOrdinalToPostOrderIndex, postOrderIndexToNodeOrdinal); + + nodeOrdinalToPostOrderIndex = null; + + this._nodeOrdinalToRetainedSizes = new Uint32Array(this._nodeCount); + this._buildRetainedSizes(postOrderIndexToNodeOrdinal); + + postOrderIndexToNodeOrdinal = null; + + this._nodeOrdinalIsDead = new Uint8Array(this._nodeCount); + + let {liveSize, categories} = HeapSnapshot.updateCategoriesAndMetadata(this); + this._liveSize = liveSize; + this._categories = categories; + } + + // Static + + static updateCategoriesAndMetadata(snapshot, allowNodeIdentifierCallback) + { + let liveSize = 0; + let categories = {}; + + let nodes = snapshot._nodes; + let nodeClassNamesTable = snapshot._nodeClassNamesTable; + let nodeOrdinalToRetainedSizes = snapshot._nodeOrdinalToRetainedSizes; + let nodeOrdinalIsDead = snapshot._nodeOrdinalIsDead; + + // Skip the <root> node. + let firstNodeIndex = nodeFieldCount; + let firstNodeOrdinal = 1; + for (let nodeIndex = firstNodeIndex, nodeOrdinal = firstNodeOrdinal; nodeIndex < nodes.length; nodeIndex += nodeFieldCount, nodeOrdinal++) { + if (allowNodeIdentifierCallback && !allowNodeIdentifierCallback(nodes[nodeIndex + nodeIdOffset])) + continue; + + let classNameTableIndex = nodes[nodeIndex + nodeClassNameOffset]; + let className = nodeClassNamesTable[classNameTableIndex]; + let size = nodes[nodeIndex + nodeSizeOffset]; + let retainedSize = nodeOrdinalToRetainedSizes[nodeOrdinal]; + let internal = nodes[nodeIndex + nodeInternalOffset] ? true : false; + let dead = nodeOrdinalIsDead[nodeOrdinal] ? true : false; + + let category = categories[className]; + if (!category) + category = categories[className] = {className, size: 0, retainedSize: 0, count: 0, internalCount: 0, deadCount: 0}; + + category.size += size; + category.retainedSize += retainedSize; + category.count += 1; + if (internal) + category.internalCount += 1; + if (dead) + category.deadCount += 1; + else + liveSize += size; + } + + return {liveSize, categories}; + } + + static allocationBucketCounts(snapshot, bucketSizes, allowNodeIdentifierCallback) + { + let counts = new Array(bucketSizes.length + 1); + let remainderBucket = counts.length - 1; + counts.fill(0); + + let nodes = snapshot._nodes; + + // Skip the <root> node. + let firstNodeIndex = nodeFieldCount; + + outer: + for (let nodeIndex = firstNodeIndex; nodeIndex < nodes.length; nodeIndex += nodeFieldCount) { + if (allowNodeIdentifierCallback && !allowNodeIdentifierCallback(nodes[nodeIndex + nodeIdOffset])) + continue; + + let size = nodes[nodeIndex + nodeSizeOffset]; + for (let i = 0; i < bucketSizes.length; ++i) { + if (size < bucketSizes[i]) { + counts[i]++; + continue outer; + } + } + counts[remainderBucket]++; + } + + return counts; + } + + static instancesWithClassName(snapshot, className, allowNodeIdentifierCallback) + { + let instances = []; + + let nodes = snapshot._nodes; + let nodeClassNamesTable = snapshot._nodeClassNamesTable; + + // Skip the <root> node. + let firstNodeIndex = nodeFieldCount; + let firstNodeOrdinal = 1; + for (let nodeIndex = firstNodeIndex, nodeOrdinal = firstNodeOrdinal; nodeIndex < nodes.length; nodeIndex += nodeFieldCount, nodeOrdinal++) { + if (allowNodeIdentifierCallback && !allowNodeIdentifierCallback(nodes[nodeIndex + nodeIdOffset])) + continue; + + let classNameTableIndex = nodes[nodeIndex + nodeClassNameOffset]; + if (nodeClassNamesTable[classNameTableIndex] === className) + instances.push(nodeIndex); + } + + return instances.map(snapshot.serializeNode, snapshot); + } + + // Worker Methods + + allocationBucketCounts(bucketSizes) + { + return HeapSnapshot.allocationBucketCounts(this, bucketSizes); + } + + instancesWithClassName(className) + { + return HeapSnapshot.instancesWithClassName(this, className); + } + + update() + { + return HeapSnapshot.updateCategoriesAndMetadata(this); + } + + nodeWithIdentifier(nodeIdentifier) + { + let nodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier); + let nodeIndex = nodeOrdinal * nodeFieldCount; + return this.serializeNode(nodeIndex); + } + + shortestGCRootPath(nodeIdentifier) + { + // Returns an array from this node to a gcRoot node. + // E.g. [Node (target), Edge, Node, Edge, Node (root)]. + // Internal nodes are avoided, so if the path is empty this + // node is either a gcRoot or only reachable via Internal nodes. + + let paths = this._gcRootPathes(nodeIdentifier); + if (!paths.length) + return []; + + paths.sort((a, b) => a.length - b.length); + + let shortestPathWithGlobalObject = null; + for (let path of paths) { + let lastNodeIndex = path[path.length - 1].node; + if (this._isNodeGlobalObject(lastNodeIndex)) { + shortestPathWithGlobalObject = path; + break; + } + } + + let shortestPath = shortestPathWithGlobalObject || paths[0]; + console.assert("node" in shortestPath[0], "Path should start with a node"); + console.assert("node" in shortestPath[shortestPath.length - 1], "Path should end with a node"); + + return shortestPath.map((component) => { + if (component.node) + return this.serializeNode(component.node); + return this.serializeEdge(component.edge); + }); + } + + dominatedNodes(nodeIdentifier) + { + let dominatedNodes = []; + + let targetNodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier); + for (let nodeOrdinal = 0; nodeOrdinal < this._nodeCount; ++nodeOrdinal) { + if (this._nodeOrdinalToDominatorNodeOrdinal[nodeOrdinal] === targetNodeOrdinal) + dominatedNodes.push(nodeOrdinal * nodeFieldCount); + } + + return dominatedNodes.map(this.serializeNode, this); + } + + retainedNodes(nodeIdentifier) + { + let retainedNodes = []; + let edges = []; + + let nodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier); + let edgeIndex = this._nodeOrdinalToFirstOutgoingEdge[nodeOrdinal]; + for (; this._edges[edgeIndex + edgeFromIdOffset] === nodeIdentifier; edgeIndex += edgeFieldCount) { + let toNodeIdentifier = this._edges[edgeIndex + edgeToIdOffset]; + let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(toNodeIdentifier); + let toNodeIndex = toNodeOrdinal * nodeFieldCount; + retainedNodes.push(toNodeIndex); + edges.push(edgeIndex); + } + + return { + retainedNodes: retainedNodes.map(this.serializeNode, this), + edges: edges.map(this.serializeEdge, this), + }; + } + + retainers(nodeIdentifier) + { + let retainers = []; + let edges = []; + + let nodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier); + let incomingEdgeIndex = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal]; + let incomingEdgeIndexEnd = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal + 1]; + for (let edgeIndex = incomingEdgeIndex; edgeIndex < incomingEdgeIndexEnd; ++edgeIndex) { + let fromNodeOrdinal = this._incomingNodes[edgeIndex]; + let fromNodeIndex = fromNodeOrdinal * nodeFieldCount; + retainers.push(fromNodeIndex); + edges.push(this._incomingEdges[edgeIndex]); + } + + return { + retainers: retainers.map(this.serializeNode, this), + edges: edges.map(this.serializeEdge, this), + }; + } + + updateDeadNodesAndGatherCollectionData(snapshots) + { + let previousSnapshotIndex = snapshots.indexOf(this) - 1; + let previousSnapshot = snapshots[previousSnapshotIndex]; + if (!previousSnapshot) + return null; + + let lastNodeIdentifier = previousSnapshot._lastNodeIdentifier; + + // All of the node identifiers that could have existed prior to this snapshot. + let known = new Map; + for (let nodeIndex = 0; nodeIndex < this._nodes.length; nodeIndex += nodeFieldCount) { + let nodeIdentifier = this._nodes[nodeIndex + nodeIdOffset]; + if (nodeIdentifier > lastNodeIdentifier) + continue; + known.set(nodeIdentifier, nodeIndex); + } + + // Determine which node identifiers have since been deleted. + let collectedNodesList = []; + for (let nodeIndex = 0; nodeIndex < previousSnapshot._nodes.length; nodeIndex += nodeFieldCount) { + let nodeIdentifier = previousSnapshot._nodes[nodeIndex + nodeIdOffset]; + let wasDeleted = !known.has(nodeIdentifier); + if (wasDeleted) + collectedNodesList.push(nodeIdentifier); + } + + // Update dead nodes in previous snapshots. + let affectedSnapshots = []; + for (let snapshot of snapshots) { + if (snapshot === this) + break; + if (snapshot._markDeadNodes(collectedNodesList)) + affectedSnapshots.push(snapshot._identifier); + } + + // Convert list to a map. + let collectedNodes = {}; + for (let i = 0; i < collectedNodesList.length; ++i) + collectedNodes[collectedNodesList[i]] = true; + + return { + collectedNodes, + affectedSnapshots, + }; + } + + // Public + + serialize() + { + return { + identifier: this._identifier, + title: this._title, + totalSize: this._totalSize, + totalObjectCount: this._nodeCount - 1, // <root>. + liveSize: this._liveSize, + categories: this._categories, + }; + } + + serializeNode(nodeIndex) + { + console.assert((nodeIndex % nodeFieldCount) === 0, "Invalid nodeIndex to serialize"); + + let nodeIdentifier = this._nodes[nodeIndex + nodeIdOffset]; + let nodeOrdinal = nodeIndex / nodeFieldCount; + let edgeIndex = this._nodeOrdinalToFirstOutgoingEdge[nodeOrdinal]; + let hasChildren = this._edges[edgeIndex + edgeFromIdOffset] === nodeIdentifier; + + let dominatorNodeOrdinal = this._nodeOrdinalToDominatorNodeOrdinal[nodeOrdinal]; + let dominatorNodeIndex = dominatorNodeOrdinal * nodeFieldCount; + let dominatorNodeIdentifier = this._nodes[dominatorNodeIndex + nodeIdOffset]; + + return { + id: nodeIdentifier, + className: this._nodeClassNamesTable[this._nodes[nodeIndex + nodeClassNameOffset]], + size: this._nodes[nodeIndex + nodeSizeOffset], + retainedSize: this._nodeOrdinalToRetainedSizes[nodeOrdinal], + internal: this._nodes[nodeIndex + nodeInternalOffset] ? true : false, + gcRoot: this._nodeOrdinalIsGCRoot[nodeOrdinal] ? true : false, + dead: this._nodeOrdinalIsDead[nodeOrdinal] ? true : false, + dominatorNodeIdentifier, + hasChildren, + }; + } + + serializeEdge(edgeIndex) + { + console.assert((edgeIndex % edgeFieldCount) === 0, "Invalid edgeIndex to serialize"); + + let edgeType = this._edgeTypesTable[this._edges[edgeIndex + edgeTypeOffset]]; + let edgeData = this._edges[edgeIndex + edgeDataOffset]; + switch (edgeType) { + case "Internal": + // edgeData can be ignored. + break; + case "Property": + case "Variable": + // edgeData is a table index. + edgeData = this._edgeNamesTable[edgeData]; + break; + case "Index": + // edgeData is the index. + break; + default: + console.error("Unexpected edge type: " + edgeType); + break; + } + + return { + from: this._edges[edgeIndex + edgeFromIdOffset], + to: this._edges[edgeIndex + edgeToIdOffset], + type: edgeType, + data: edgeData, + }; + } + + // Private + + _buildOutgoingEdges() + { + let lastFromIdentifier = -1; + for (let edgeIndex = 0; edgeIndex < this._edges.length; edgeIndex += edgeFieldCount) { + let fromIdentifier = this._edges[edgeIndex + edgeFromIdOffset]; + console.assert(lastFromIdentifier <= fromIdentifier, "Edge list should be ordered by from node identifier"); + if (fromIdentifier !== lastFromIdentifier) { + let nodeOrdinal = this._nodeIdentifierToOrdinal.get(fromIdentifier); + this._nodeOrdinalToFirstOutgoingEdge[nodeOrdinal] = edgeIndex; + lastFromIdentifier = fromIdentifier; + } + } + } + + _buildIncomingEdges() + { + // First calculate the count of incoming edges for each node. + for (let edgeIndex = 0; edgeIndex < this._edges.length; edgeIndex += edgeFieldCount) { + let toIdentifier = this._edges[edgeIndex + edgeToIdOffset]; + let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(toIdentifier); + this._nodeOrdinalToFirstIncomingEdge[toNodeOrdinal]++; + } + + // Replace the counts with what will be the resulting index by running up the counts. + // Store the counts in what will be the edges list to use when placing edges in the list. + let runningFirstIndex = 0; + for (let nodeOrdinal = 0; nodeOrdinal < this._nodeCount; ++nodeOrdinal) { + let count = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal]; + this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal] = runningFirstIndex; + this._incomingNodes[runningFirstIndex] = count; + runningFirstIndex += count; + } + + // Fill in the incoming edges list. Use the count as an offset when placing edges in the list. + for (let edgeIndex = 0; edgeIndex < this._edges.length; edgeIndex += edgeFieldCount) { + let fromIdentifier = this._edges[edgeIndex + edgeFromIdOffset]; + let fromNodeOrdinal = this._nodeIdentifierToOrdinal.get(fromIdentifier); + let toIdentifier = this._edges[edgeIndex + edgeToIdOffset]; + let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(toIdentifier); + + let firstIncomingEdgeIndex = this._nodeOrdinalToFirstIncomingEdge[toNodeOrdinal]; + console.assert(this._incomingNodes[firstIncomingEdgeIndex] > 0, "Should be expecting edges for this node"); + let countAsOffset = this._incomingNodes[firstIncomingEdgeIndex]--; + let index = firstIncomingEdgeIndex + countAsOffset - 1; + this._incomingNodes[index] = fromNodeOrdinal; + this._incomingEdges[index] = edgeIndex; + } + + // Duplicate value on the end. Incoming edge iteration walks firstIncomingEdge(ordinal) to firstIncomingEdge(ordinal+1). + this._nodeOrdinalToFirstIncomingEdge[this._nodeCount] = this._nodeOrdinalToFirstIncomingEdge[this._nodeCount - 1]; + } + + _buildPostOrderIndexes() + { + let postOrderIndex = 0; + let nodeOrdinalToPostOrderIndex = new Uint32Array(this._nodeCount); + let postOrderIndexToNodeOrdinal = new Uint32Array(this._nodeCount); + + let stackNodes = new Uint32Array(this._nodeCount); // nodeOrdinal. + let stackEdges = new Uint32Array(this._nodeCount); // edgeIndex. + let visited = new Uint8Array(this._nodeCount); + + let stackTop = 0; + stackNodes[stackTop] = rootNodeOrdinal; + stackEdges[stackTop] = this._nodeOrdinalToFirstOutgoingEdge[rootNodeOrdinal]; + + while (stackTop >= 0) { + let nodeOrdinal = stackNodes[stackTop]; + let nodeIdentifier = this._nodes[(nodeOrdinal * nodeFieldCount) + nodeIdOffset]; + let edgeIndex = stackEdges[stackTop]; + + if (this._edges[edgeIndex + edgeFromIdOffset] === nodeIdentifier) { + // Prepare the next child for the current node. + stackEdges[stackTop] += edgeFieldCount; + + let toIdentifier = this._edges[edgeIndex + edgeToIdOffset]; + let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(toIdentifier); + if (visited[toNodeOrdinal]) + continue; + + // Child. + stackTop++; + stackNodes[stackTop] = toNodeOrdinal; + stackEdges[stackTop] = this._nodeOrdinalToFirstOutgoingEdge[toNodeOrdinal]; + visited[toNodeOrdinal] = 1; + } else { + // Self. + nodeOrdinalToPostOrderIndex[nodeOrdinal] = postOrderIndex; + postOrderIndexToNodeOrdinal[postOrderIndex] = nodeOrdinal; + postOrderIndex++; + stackTop--; + } + } + + // Unvisited nodes. + // This can happen if the parent node was disallowed on the backend, but other nodes + // that were only referenced from that disallowed node were eventually allowed because + // they may be generic system objects. Give these nodes a postOrderIndex anyways. + if (postOrderIndex !== this._nodeCount) { + // Root was the last node visited. Revert assigning it an index, add it back at the end. + postOrderIndex--; + + // Visit unvisited nodes. + for (let nodeOrdinal = 1; nodeOrdinal < this._nodeCount; ++nodeOrdinal) { + if (visited[nodeOrdinal]) + continue; + nodeOrdinalToPostOrderIndex[nodeOrdinal] = postOrderIndex; + postOrderIndexToNodeOrdinal[postOrderIndex] = nodeOrdinal; + postOrderIndex++; + } + + // Visit root again. + nodeOrdinalToPostOrderIndex[rootNodeOrdinal] = postOrderIndex; + postOrderIndexToNodeOrdinal[postOrderIndex] = rootNodeOrdinal; + postOrderIndex++; + } + + console.assert(postOrderIndex === this._nodeCount, "All nodes were visited"); + console.assert(nodeOrdinalToPostOrderIndex[rootNodeOrdinal] === this._nodeCount - 1, "Root node should have the last possible postOrderIndex"); + + return {nodeOrdinalToPostOrderIndex, postOrderIndexToNodeOrdinal}; + } + + _buildDominatorIndexes(nodeOrdinalToPostOrderIndex, postOrderIndexToNodeOrdinal) + { + // The algorithm is based on the article: + // K. Cooper, T. Harvey and K. Kennedy "A Simple, Fast Dominance Algorithm" + + let rootPostOrderIndex = this._nodeCount - 1; + let noEntry = this._nodeCount; + + let affected = new Uint8Array(this._nodeCount); + let dominators = new Uint32Array(this._nodeCount); + + // Initialize with unset value. + dominators.fill(noEntry); + + // Mark the root's dominator value. + dominators[rootPostOrderIndex] = rootPostOrderIndex; + + // Affect the root's children. Also use this opportunity to mark them as GC roots. + let rootEdgeIndex = this._nodeOrdinalToFirstOutgoingEdge[rootNodeOrdinal]; + for (let edgeIndex = rootEdgeIndex; this._edges[edgeIndex + edgeFromIdOffset] === rootNodeIdentifier; edgeIndex += edgeFieldCount) { + let toIdentifier = this._edges[edgeIndex + edgeToIdOffset]; + let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(toIdentifier); + let toPostOrderIndex = nodeOrdinalToPostOrderIndex[toNodeOrdinal]; + affected[toPostOrderIndex] = 1; + this._nodeOrdinalIsGCRoot[toNodeOrdinal] = 1; + } + + let changed = true; + while (changed) { + changed = false; + + for (let postOrderIndex = rootPostOrderIndex - 1; postOrderIndex >= 0; --postOrderIndex) { + if (!affected[postOrderIndex]) + continue; + affected[postOrderIndex] = 0; + + // The dominator is already the root, nothing to do. + if (dominators[postOrderIndex] === rootPostOrderIndex) + continue; + + let newDominatorIndex = noEntry; + let nodeOrdinal = postOrderIndexToNodeOrdinal[postOrderIndex]; + let incomingEdgeIndex = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal]; + let incomingEdgeIndexEnd = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal + 1]; + for (let edgeIndex = incomingEdgeIndex; edgeIndex < incomingEdgeIndexEnd; ++edgeIndex) { + let fromNodeOrdinal = this._incomingNodes[edgeIndex]; + let fromPostOrderIndex = nodeOrdinalToPostOrderIndex[fromNodeOrdinal]; + if (dominators[fromPostOrderIndex] !== noEntry) { + if (newDominatorIndex === noEntry) + newDominatorIndex = fromPostOrderIndex; + else { + while (fromPostOrderIndex !== newDominatorIndex) { + while (fromPostOrderIndex < newDominatorIndex) + fromPostOrderIndex = dominators[fromPostOrderIndex]; + while (newDominatorIndex < fromPostOrderIndex) + newDominatorIndex = dominators[newDominatorIndex]; + } + } + } + if (newDominatorIndex === rootPostOrderIndex) + break; + } + + // Changed. Affect children. + if (newDominatorIndex !== noEntry && dominators[postOrderIndex] !== newDominatorIndex) { + dominators[postOrderIndex] = newDominatorIndex; + changed = true; + + let outgoingEdgeIndex = this._nodeOrdinalToFirstOutgoingEdge[nodeOrdinal]; + let nodeIdentifier = this._nodes[(nodeOrdinal * nodeFieldCount) + nodeIdOffset]; + for (let edgeIndex = outgoingEdgeIndex; this._edges[edgeIndex + edgeFromIdOffset] === nodeIdentifier; edgeIndex += edgeFieldCount) { + let toNodeIdentifier = this._edges[edgeIndex + edgeToIdOffset]; + let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(toNodeIdentifier); + let toNodePostOrder = nodeOrdinalToPostOrderIndex[toNodeOrdinal]; + affected[toNodePostOrder] = 1; + } + } + } + } + + for (let postOrderIndex = 0; postOrderIndex < this._nodeCount; ++postOrderIndex) { + let nodeOrdinal = postOrderIndexToNodeOrdinal[postOrderIndex]; + let dominatorNodeOrdinal = postOrderIndexToNodeOrdinal[dominators[postOrderIndex]]; + this._nodeOrdinalToDominatorNodeOrdinal[nodeOrdinal] = dominatorNodeOrdinal; + } + } + + _buildRetainedSizes(postOrderIndexToNodeOrdinal) + { + // Self size. + for (let nodeIndex = 0, nodeOrdinal = 0; nodeOrdinal < this._nodeCount; nodeIndex += nodeFieldCount, nodeOrdinal++) + this._nodeOrdinalToRetainedSizes[nodeOrdinal] = this._nodes[nodeIndex + nodeSizeOffset]; + + // Attribute size to dominator. + for (let postOrderIndex = 0; postOrderIndex < this._nodeCount - 1; ++postOrderIndex) { + let nodeOrdinal = postOrderIndexToNodeOrdinal[postOrderIndex]; + let nodeRetainedSize = this._nodeOrdinalToRetainedSizes[nodeOrdinal]; + let dominatorNodeOrdinal = this._nodeOrdinalToDominatorNodeOrdinal[nodeOrdinal]; + this._nodeOrdinalToRetainedSizes[dominatorNodeOrdinal] += nodeRetainedSize; + } + } + + _markDeadNodes(collectedNodesList) + { + let affected = false; + + for (let i = 0; i < collectedNodesList.length; ++i) { + let nodeIdentifier = collectedNodesList[i]; + if (nodeIdentifier > this._lastNodeIdentifier) + continue; + let nodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier); + this._nodeOrdinalIsDead[nodeOrdinal] = 1; + affected = true; + } + + return affected; + } + + _isNodeGlobalObject(nodeIndex) + { + let className = this._nodeClassNamesTable[this._nodes[nodeIndex + nodeClassNameOffset]]; + return className === "Window" + || className === "JSDOMWindowShell" + || className === "GlobalObject"; + } + + _gcRootPathes(nodeIdentifier) + { + let targetNodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier); + + if (this._nodeOrdinalIsGCRoot[targetNodeOrdinal]) + return []; + + // FIXME: Array push/pop can affect performance here, but in practice it hasn't been an issue. + + let paths = []; + let currentPath = []; + let visited = new Uint8Array(this._nodeCount); + + function visitNode(nodeOrdinal) + { + if (this._nodeOrdinalIsGCRoot[nodeOrdinal]) { + let fullPath = currentPath.slice(); + let nodeIndex = nodeOrdinal * nodeFieldCount; + fullPath.push({node: nodeIndex}); + paths.push(fullPath); + return; + } + + if (visited[nodeOrdinal]) + return; + visited[nodeOrdinal] = 1; + + let nodeIndex = nodeOrdinal * nodeFieldCount; + currentPath.push({node: nodeIndex}); + + // Loop in reverse order because edges were added in reverse order. + // It doesn't particularly matter other then consistency with previous code. + let incomingEdgeIndexStart = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal]; + let incomingEdgeIndexEnd = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal + 1]; + for (let incomingEdgeIndex = incomingEdgeIndexEnd - 1; incomingEdgeIndex >= incomingEdgeIndexStart; --incomingEdgeIndex) { + let fromNodeOrdinal = this._incomingNodes[incomingEdgeIndex]; + let fromNodeIndex = fromNodeOrdinal * nodeFieldCount; + let fromNodeIsInternal = this._nodes[fromNodeIndex + nodeInternalOffset]; + if (fromNodeIsInternal) + continue; + + let edgeIndex = this._incomingEdges[incomingEdgeIndex]; + currentPath.push({edge: edgeIndex}); + visitNode.call(this, fromNodeOrdinal); + currentPath.pop(); + } + + currentPath.pop(); + } + + visitNode.call(this, targetNodeOrdinal); + + return paths; + } +}; + +HeapSnapshotDiff = class HeapSnapshotDiff +{ + constructor(objectId, snapshot1, snapshot2) + { + this._objectId = objectId; + + this._snapshot1 = snapshot1; + this._snapshot2 = snapshot2; + + this._totalSize = 0; + this._addedNodeIdentifiers = new Set; + + let known = new Map; + for (let nodeIndex = 0; nodeIndex < this._snapshot1._nodes.length; nodeIndex += nodeFieldCount) { + let nodeIdentifier = this._snapshot1._nodes[nodeIndex + nodeIdOffset]; + known.set(nodeIdentifier, nodeIndex); + } + + for (let nodeIndex = 0; nodeIndex < this._snapshot2._nodes.length; nodeIndex += nodeFieldCount) { + let nodeIdentifier = this._snapshot2._nodes[nodeIndex + nodeIdOffset]; + let existed = known.delete(nodeIdentifier); + if (!existed) { + this._addedNodeIdentifiers.add(nodeIdentifier); + this._totalSize += this._snapshot2._nodes[nodeIndex + nodeSizeOffset]; + } + } + + let {liveSize, categories} = HeapSnapshot.updateCategoriesAndMetadata(this._snapshot2, (nodeIdentifier) => this._addedNodeIdentifiers.has(nodeIdentifier)); + this._categories = categories; + } + + // Worker Methods + + allocationBucketCounts(bucketSizes) + { + return HeapSnapshot.allocationBucketCounts(this._snapshot2, bucketSizes, (nodeIdentifier) => this._addedNodeIdentifiers.has(nodeIdentifier)); + } + + instancesWithClassName(className) + { + return HeapSnapshot.instancesWithClassName(this._snapshot2, className, (nodeIdentifier) => this._addedNodeIdentifiers.has(nodeIdentifier)); + } + + update() + { + return HeapSnapshot.updateCategoriesAndMetadata(this._snapshot2, (nodeIdentifier) => this._addedNodeIdentifiers.has(nodeIdentifier)); + } + + nodeWithIdentifier(nodeIdentifier) { return this._snapshot2.nodeWithIdentifier(nodeIdentifier); } + shortestGCRootPath(nodeIdentifier) { return this._snapshot2.shortestGCRootPath(nodeIdentifier); } + dominatedNodes(nodeIdentifier) { return this._snapshot2.dominatedNodes(nodeIdentifier); } + retainedNodes(nodeIdentifier) { return this._snapshot2.retainedNodes(nodeIdentifier); } + retainers(nodeIdentifier) { return this._snapshot2.retainers(nodeIdentifier); } + + // Public + + serialize() + { + return { + snapshot1: this._snapshot1.serialize(), + snapshot2: this._snapshot2.serialize(), + totalSize: this._totalSize, + totalObjectCount: this._addedNodeIdentifiers.size, + categories: this._categories, + }; + } +}; diff --git a/Source/WebInspectorUI/UserInterface/Workers/HeapSnapshot/HeapSnapshotWorker.js b/Source/WebInspectorUI/UserInterface/Workers/HeapSnapshot/HeapSnapshotWorker.js new file mode 100644 index 000000000..13f684983 --- /dev/null +++ b/Source/WebInspectorUI/UserInterface/Workers/HeapSnapshot/HeapSnapshotWorker.js @@ -0,0 +1,120 @@ +/* + * Copyright (C) 2016 Apple Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, + * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS + * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + */ + +importScripts(...[ + "HeapSnapshot.js" +]); + +HeapSnapshotWorker = class HeapSnapshotWorker +{ + constructor() + { + this._nextObjectId = 1; + this._objects = new Map; + this._snapshots = []; + + self.addEventListener("message", this._handleMessage.bind(this)); + } + + // Actions + + clearSnapshots() + { + this._objects.clear(); + + this._snapshots = []; + } + + createSnapshot(snapshotString, title) + { + let objectId = this._nextObjectId++; + let snapshot = new HeapSnapshot(objectId, snapshotString, title); + this._snapshots.push(snapshot); + this._objects.set(objectId, snapshot); + + if (this._snapshots.length > 1) { + setTimeout(() => { + let collectionData = snapshot.updateDeadNodesAndGatherCollectionData(this._snapshots); + if (!collectionData || !collectionData.affectedSnapshots.length) + return; + this.sendEvent("HeapSnapshot.CollectionEvent", collectionData); + }, 0); + } + + return {objectId, snapshot: snapshot.serialize()}; + } + + createSnapshotDiff(objectId1, objectId2) + { + let snapshot1 = this._objects.get(objectId1); + let snapshot2 = this._objects.get(objectId2); + + console.assert(snapshot1 instanceof HeapSnapshot); + console.assert(snapshot2 instanceof HeapSnapshot); + + let objectId = this._nextObjectId++; + let snapshotDiff = new HeapSnapshotDiff(objectId, snapshot1, snapshot2); + this._objects.set(objectId, snapshotDiff); + return {objectId, snapshotDiff: snapshotDiff.serialize()}; + } + + // Public + + sendEvent(eventName, eventData) + { + self.postMessage({eventName, eventData}); + } + + // Private + + _handleMessage(event) + { + let data = event.data; + + // Action. + if (data.actionName) { + let result = this[data.actionName](...data.actionArguments); + self.postMessage({callId: data.callId, result}); + return; + } + + // Method. + if (data.methodName) { + console.assert(data.objectId, "Must have an objectId to call the method on"); + let object = this._objects.get(data.objectId); + if (!object) + self.postMessage({callId: data.callId, error: "No such object."}); + else { + let result = object[data.methodName](...data.methodArguments); + self.postMessage({callId: data.callId, result}); + } + return; + } + + console.error("Unexpected HeapSnapshotWorker message", data); + } +}; + +self.heapSnapshotWorker = new HeapSnapshotWorker; |