--- /dev/null
+/**
+ * @fileoverview A class of the code path analyzer.
+ * @author Toru Nagashima
+ */
+
+"use strict";
+
+//------------------------------------------------------------------------------
+// Requirements
+//------------------------------------------------------------------------------
+
+const assert = require("assert"),
+ { breakableTypePattern } = require("../../shared/ast-utils"),
+ CodePath = require("./code-path"),
+ CodePathSegment = require("./code-path-segment"),
+ IdGenerator = require("./id-generator"),
+ debug = require("./debug-helpers");
+
+//------------------------------------------------------------------------------
+// Helpers
+//------------------------------------------------------------------------------
+
+/**
+ * Checks whether or not a given node is a `case` node (not `default` node).
+ * @param {ASTNode} node A `SwitchCase` node to check.
+ * @returns {boolean} `true` if the node is a `case` node (not `default` node).
+ */
+function isCaseNode(node) {
+ return Boolean(node.test);
+}
+
+/**
+ * Checks whether the given logical operator is taken into account for the code
+ * path analysis.
+ * @param {string} operator The operator found in the LogicalExpression node
+ * @returns {boolean} `true` if the operator is "&&" or "||" or "??"
+ */
+function isHandledLogicalOperator(operator) {
+ return operator === "&&" || operator === "||" || operator === "??";
+}
+
+/**
+ * Checks whether the given assignment operator is a logical assignment operator.
+ * Logical assignments are taken into account for the code path analysis
+ * because of their short-circuiting semantics.
+ * @param {string} operator The operator found in the AssignmentExpression node
+ * @returns {boolean} `true` if the operator is "&&=" or "||=" or "??="
+ */
+function isLogicalAssignmentOperator(operator) {
+ return operator === "&&=" || operator === "||=" || operator === "??=";
+}
+
+/**
+ * Gets the label if the parent node of a given node is a LabeledStatement.
+ * @param {ASTNode} node A node to get.
+ * @returns {string|null} The label or `null`.
+ */
+function getLabel(node) {
+ if (node.parent.type === "LabeledStatement") {
+ return node.parent.label.name;
+ }
+ return null;
+}
+
+/**
+ * Checks whether or not a given logical expression node goes different path
+ * between the `true` case and the `false` case.
+ * @param {ASTNode} node A node to check.
+ * @returns {boolean} `true` if the node is a test of a choice statement.
+ */
+function isForkingByTrueOrFalse(node) {
+ const parent = node.parent;
+
+ switch (parent.type) {
+ case "ConditionalExpression":
+ case "IfStatement":
+ case "WhileStatement":
+ case "DoWhileStatement":
+ case "ForStatement":
+ return parent.test === node;
+
+ case "LogicalExpression":
+ return isHandledLogicalOperator(parent.operator);
+
+ case "AssignmentExpression":
+ return isLogicalAssignmentOperator(parent.operator);
+
+ default:
+ return false;
+ }
+}
+
+/**
+ * Gets the boolean value of a given literal node.
+ *
+ * This is used to detect infinity loops (e.g. `while (true) {}`).
+ * Statements preceded by an infinity loop are unreachable if the loop didn't
+ * have any `break` statement.
+ * @param {ASTNode} node A node to get.
+ * @returns {boolean|undefined} a boolean value if the node is a Literal node,
+ * otherwise `undefined`.
+ */
+function getBooleanValueIfSimpleConstant(node) {
+ if (node.type === "Literal") {
+ return Boolean(node.value);
+ }
+ return void 0;
+}
+
+/**
+ * Checks that a given identifier node is a reference or not.
+ *
+ * This is used to detect the first throwable node in a `try` block.
+ * @param {ASTNode} node An Identifier node to check.
+ * @returns {boolean} `true` if the node is a reference.
+ */
+function isIdentifierReference(node) {
+ const parent = node.parent;
+
+ switch (parent.type) {
+ case "LabeledStatement":
+ case "BreakStatement":
+ case "ContinueStatement":
+ case "ArrayPattern":
+ case "RestElement":
+ case "ImportSpecifier":
+ case "ImportDefaultSpecifier":
+ case "ImportNamespaceSpecifier":
+ case "CatchClause":
+ return false;
+
+ case "FunctionDeclaration":
+ case "FunctionExpression":
+ case "ArrowFunctionExpression":
+ case "ClassDeclaration":
+ case "ClassExpression":
+ case "VariableDeclarator":
+ return parent.id !== node;
+
+ case "Property":
+ case "MethodDefinition":
+ return (
+ parent.key !== node ||
+ parent.computed ||
+ parent.shorthand
+ );
+
+ case "AssignmentPattern":
+ return parent.key !== node;
+
+ default:
+ return true;
+ }
+}
+
+/**
+ * Updates the current segment with the head segment.
+ * This is similar to local branches and tracking branches of git.
+ *
+ * To separate the current and the head is in order to not make useless segments.
+ *
+ * In this process, both "onCodePathSegmentStart" and "onCodePathSegmentEnd"
+ * events are fired.
+ * @param {CodePathAnalyzer} analyzer The instance.
+ * @param {ASTNode} node The current AST node.
+ * @returns {void}
+ */
+function forwardCurrentToHead(analyzer, node) {
+ const codePath = analyzer.codePath;
+ const state = CodePath.getState(codePath);
+ const currentSegments = state.currentSegments;
+ const headSegments = state.headSegments;
+ const end = Math.max(currentSegments.length, headSegments.length);
+ let i, currentSegment, headSegment;
+
+ // Fires leaving events.
+ for (i = 0; i < end; ++i) {
+ currentSegment = currentSegments[i];
+ headSegment = headSegments[i];
+
+ if (currentSegment !== headSegment && currentSegment) {
+ debug.dump(`onCodePathSegmentEnd ${currentSegment.id}`);
+
+ if (currentSegment.reachable) {
+ analyzer.emitter.emit(
+ "onCodePathSegmentEnd",
+ currentSegment,
+ node
+ );
+ }
+ }
+ }
+
+ // Update state.
+ state.currentSegments = headSegments;
+
+ // Fires entering events.
+ for (i = 0; i < end; ++i) {
+ currentSegment = currentSegments[i];
+ headSegment = headSegments[i];
+
+ if (currentSegment !== headSegment && headSegment) {
+ debug.dump(`onCodePathSegmentStart ${headSegment.id}`);
+
+ CodePathSegment.markUsed(headSegment);
+ if (headSegment.reachable) {
+ analyzer.emitter.emit(
+ "onCodePathSegmentStart",
+ headSegment,
+ node
+ );
+ }
+ }
+ }
+
+}
+
+/**
+ * Updates the current segment with empty.
+ * This is called at the last of functions or the program.
+ * @param {CodePathAnalyzer} analyzer The instance.
+ * @param {ASTNode} node The current AST node.
+ * @returns {void}
+ */
+function leaveFromCurrentSegment(analyzer, node) {
+ const state = CodePath.getState(analyzer.codePath);
+ const currentSegments = state.currentSegments;
+
+ for (let i = 0; i < currentSegments.length; ++i) {
+ const currentSegment = currentSegments[i];
+
+ debug.dump(`onCodePathSegmentEnd ${currentSegment.id}`);
+ if (currentSegment.reachable) {
+ analyzer.emitter.emit(
+ "onCodePathSegmentEnd",
+ currentSegment,
+ node
+ );
+ }
+ }
+
+ state.currentSegments = [];
+}
+
+/**
+ * Updates the code path due to the position of a given node in the parent node
+ * thereof.
+ *
+ * For example, if the node is `parent.consequent`, this creates a fork from the
+ * current path.
+ * @param {CodePathAnalyzer} analyzer The instance.
+ * @param {ASTNode} node The current AST node.
+ * @returns {void}
+ */
+function preprocess(analyzer, node) {
+ const codePath = analyzer.codePath;
+ const state = CodePath.getState(codePath);
+ const parent = node.parent;
+
+ switch (parent.type) {
+
+ // The `arguments.length == 0` case is in `postprocess` function.
+ case "CallExpression":
+ if (parent.optional === true && parent.arguments.length >= 1 && parent.arguments[0] === node) {
+ state.makeOptionalRight();
+ }
+ break;
+ case "MemberExpression":
+ if (parent.optional === true && parent.property === node) {
+ state.makeOptionalRight();
+ }
+ break;
+
+ case "LogicalExpression":
+ if (
+ parent.right === node &&
+ isHandledLogicalOperator(parent.operator)
+ ) {
+ state.makeLogicalRight();
+ }
+ break;
+
+ case "AssignmentExpression":
+ if (
+ parent.right === node &&
+ isLogicalAssignmentOperator(parent.operator)
+ ) {
+ state.makeLogicalRight();
+ }
+ break;
+
+ case "ConditionalExpression":
+ case "IfStatement":
+
+ /*
+ * Fork if this node is at `consequent`/`alternate`.
+ * `popForkContext()` exists at `IfStatement:exit` and
+ * `ConditionalExpression:exit`.
+ */
+ if (parent.consequent === node) {
+ state.makeIfConsequent();
+ } else if (parent.alternate === node) {
+ state.makeIfAlternate();
+ }
+ break;
+
+ case "SwitchCase":
+ if (parent.consequent[0] === node) {
+ state.makeSwitchCaseBody(false, !parent.test);
+ }
+ break;
+
+ case "TryStatement":
+ if (parent.handler === node) {
+ state.makeCatchBlock();
+ } else if (parent.finalizer === node) {
+ state.makeFinallyBlock();
+ }
+ break;
+
+ case "WhileStatement":
+ if (parent.test === node) {
+ state.makeWhileTest(getBooleanValueIfSimpleConstant(node));
+ } else {
+ assert(parent.body === node);
+ state.makeWhileBody();
+ }
+ break;
+
+ case "DoWhileStatement":
+ if (parent.body === node) {
+ state.makeDoWhileBody();
+ } else {
+ assert(parent.test === node);
+ state.makeDoWhileTest(getBooleanValueIfSimpleConstant(node));
+ }
+ break;
+
+ case "ForStatement":
+ if (parent.test === node) {
+ state.makeForTest(getBooleanValueIfSimpleConstant(node));
+ } else if (parent.update === node) {
+ state.makeForUpdate();
+ } else if (parent.body === node) {
+ state.makeForBody();
+ }
+ break;
+
+ case "ForInStatement":
+ case "ForOfStatement":
+ if (parent.left === node) {
+ state.makeForInOfLeft();
+ } else if (parent.right === node) {
+ state.makeForInOfRight();
+ } else {
+ assert(parent.body === node);
+ state.makeForInOfBody();
+ }
+ break;
+
+ case "AssignmentPattern":
+
+ /*
+ * Fork if this node is at `right`.
+ * `left` is executed always, so it uses the current path.
+ * `popForkContext()` exists at `AssignmentPattern:exit`.
+ */
+ if (parent.right === node) {
+ state.pushForkContext();
+ state.forkBypassPath();
+ state.forkPath();
+ }
+ break;
+
+ default:
+ break;
+ }
+}
+
+/**
+ * Updates the code path due to the type of a given node in entering.
+ * @param {CodePathAnalyzer} analyzer The instance.
+ * @param {ASTNode} node The current AST node.
+ * @returns {void}
+ */
+function processCodePathToEnter(analyzer, node) {
+ let codePath = analyzer.codePath;
+ let state = codePath && CodePath.getState(codePath);
+ const parent = node.parent;
+
+ switch (node.type) {
+ case "Program":
+ case "FunctionDeclaration":
+ case "FunctionExpression":
+ case "ArrowFunctionExpression":
+ if (codePath) {
+
+ // Emits onCodePathSegmentStart events if updated.
+ forwardCurrentToHead(analyzer, node);
+ debug.dumpState(node, state, false);
+ }
+
+ // Create the code path of this scope.
+ codePath = analyzer.codePath = new CodePath(
+ analyzer.idGenerator.next(),
+ codePath,
+ analyzer.onLooped
+ );
+ state = CodePath.getState(codePath);
+
+ // Emits onCodePathStart events.
+ debug.dump(`onCodePathStart ${codePath.id}`);
+ analyzer.emitter.emit("onCodePathStart", codePath, node);
+ break;
+
+ case "ChainExpression":
+ state.pushChainContext();
+ break;
+ case "CallExpression":
+ if (node.optional === true) {
+ state.makeOptionalNode();
+ }
+ break;
+ case "MemberExpression":
+ if (node.optional === true) {
+ state.makeOptionalNode();
+ }
+ break;
+
+ case "LogicalExpression":
+ if (isHandledLogicalOperator(node.operator)) {
+ state.pushChoiceContext(
+ node.operator,
+ isForkingByTrueOrFalse(node)
+ );
+ }
+ break;
+
+ case "AssignmentExpression":
+ if (isLogicalAssignmentOperator(node.operator)) {
+ state.pushChoiceContext(
+ node.operator.slice(0, -1), // removes `=` from the end
+ isForkingByTrueOrFalse(node)
+ );
+ }
+ break;
+
+ case "ConditionalExpression":
+ case "IfStatement":
+ state.pushChoiceContext("test", false);
+ break;
+
+ case "SwitchStatement":
+ state.pushSwitchContext(
+ node.cases.some(isCaseNode),
+ getLabel(node)
+ );
+ break;
+
+ case "TryStatement":
+ state.pushTryContext(Boolean(node.finalizer));
+ break;
+
+ case "SwitchCase":
+
+ /*
+ * Fork if this node is after the 2st node in `cases`.
+ * It's similar to `else` blocks.
+ * The next `test` node is processed in this path.
+ */
+ if (parent.discriminant !== node && parent.cases[0] !== node) {
+ state.forkPath();
+ }
+ break;
+
+ case "WhileStatement":
+ case "DoWhileStatement":
+ case "ForStatement":
+ case "ForInStatement":
+ case "ForOfStatement":
+ state.pushLoopContext(node.type, getLabel(node));
+ break;
+
+ case "LabeledStatement":
+ if (!breakableTypePattern.test(node.body.type)) {
+ state.pushBreakContext(false, node.label.name);
+ }
+ break;
+
+ default:
+ break;
+ }
+
+ // Emits onCodePathSegmentStart events if updated.
+ forwardCurrentToHead(analyzer, node);
+ debug.dumpState(node, state, false);
+}
+
+/**
+ * Updates the code path due to the type of a given node in leaving.
+ * @param {CodePathAnalyzer} analyzer The instance.
+ * @param {ASTNode} node The current AST node.
+ * @returns {void}
+ */
+function processCodePathToExit(analyzer, node) {
+ const codePath = analyzer.codePath;
+ const state = CodePath.getState(codePath);
+ let dontForward = false;
+
+ switch (node.type) {
+ case "ChainExpression":
+ state.popChainContext();
+ break;
+
+ case "IfStatement":
+ case "ConditionalExpression":
+ state.popChoiceContext();
+ break;
+
+ case "LogicalExpression":
+ if (isHandledLogicalOperator(node.operator)) {
+ state.popChoiceContext();
+ }
+ break;
+
+ case "AssignmentExpression":
+ if (isLogicalAssignmentOperator(node.operator)) {
+ state.popChoiceContext();
+ }
+ break;
+
+ case "SwitchStatement":
+ state.popSwitchContext();
+ break;
+
+ case "SwitchCase":
+
+ /*
+ * This is the same as the process at the 1st `consequent` node in
+ * `preprocess` function.
+ * Must do if this `consequent` is empty.
+ */
+ if (node.consequent.length === 0) {
+ state.makeSwitchCaseBody(true, !node.test);
+ }
+ if (state.forkContext.reachable) {
+ dontForward = true;
+ }
+ break;
+
+ case "TryStatement":
+ state.popTryContext();
+ break;
+
+ case "BreakStatement":
+ forwardCurrentToHead(analyzer, node);
+ state.makeBreak(node.label && node.label.name);
+ dontForward = true;
+ break;
+
+ case "ContinueStatement":
+ forwardCurrentToHead(analyzer, node);
+ state.makeContinue(node.label && node.label.name);
+ dontForward = true;
+ break;
+
+ case "ReturnStatement":
+ forwardCurrentToHead(analyzer, node);
+ state.makeReturn();
+ dontForward = true;
+ break;
+
+ case "ThrowStatement":
+ forwardCurrentToHead(analyzer, node);
+ state.makeThrow();
+ dontForward = true;
+ break;
+
+ case "Identifier":
+ if (isIdentifierReference(node)) {
+ state.makeFirstThrowablePathInTryBlock();
+ dontForward = true;
+ }
+ break;
+
+ case "CallExpression":
+ case "ImportExpression":
+ case "MemberExpression":
+ case "NewExpression":
+ case "YieldExpression":
+ state.makeFirstThrowablePathInTryBlock();
+ break;
+
+ case "WhileStatement":
+ case "DoWhileStatement":
+ case "ForStatement":
+ case "ForInStatement":
+ case "ForOfStatement":
+ state.popLoopContext();
+ break;
+
+ case "AssignmentPattern":
+ state.popForkContext();
+ break;
+
+ case "LabeledStatement":
+ if (!breakableTypePattern.test(node.body.type)) {
+ state.popBreakContext();
+ }
+ break;
+
+ default:
+ break;
+ }
+
+ // Emits onCodePathSegmentStart events if updated.
+ if (!dontForward) {
+ forwardCurrentToHead(analyzer, node);
+ }
+ debug.dumpState(node, state, true);
+}
+
+/**
+ * Updates the code path to finalize the current code path.
+ * @param {CodePathAnalyzer} analyzer The instance.
+ * @param {ASTNode} node The current AST node.
+ * @returns {void}
+ */
+function postprocess(analyzer, node) {
+ switch (node.type) {
+ case "Program":
+ case "FunctionDeclaration":
+ case "FunctionExpression":
+ case "ArrowFunctionExpression": {
+ let codePath = analyzer.codePath;
+
+ // Mark the current path as the final node.
+ CodePath.getState(codePath).makeFinal();
+
+ // Emits onCodePathSegmentEnd event of the current segments.
+ leaveFromCurrentSegment(analyzer, node);
+
+ // Emits onCodePathEnd event of this code path.
+ debug.dump(`onCodePathEnd ${codePath.id}`);
+ analyzer.emitter.emit("onCodePathEnd", codePath, node);
+ debug.dumpDot(codePath);
+
+ codePath = analyzer.codePath = analyzer.codePath.upper;
+ if (codePath) {
+ debug.dumpState(node, CodePath.getState(codePath), true);
+ }
+ break;
+ }
+
+ // The `arguments.length >= 1` case is in `preprocess` function.
+ case "CallExpression":
+ if (node.optional === true && node.arguments.length === 0) {
+ CodePath.getState(analyzer.codePath).makeOptionalRight();
+ }
+ break;
+
+ default:
+ break;
+ }
+}
+
+//------------------------------------------------------------------------------
+// Public Interface
+//------------------------------------------------------------------------------
+
+/**
+ * The class to analyze code paths.
+ * This class implements the EventGenerator interface.
+ */
+class CodePathAnalyzer {
+
+ // eslint-disable-next-line jsdoc/require-description
+ /**
+ * @param {EventGenerator} eventGenerator An event generator to wrap.
+ */
+ constructor(eventGenerator) {
+ this.original = eventGenerator;
+ this.emitter = eventGenerator.emitter;
+ this.codePath = null;
+ this.idGenerator = new IdGenerator("s");
+ this.currentNode = null;
+ this.onLooped = this.onLooped.bind(this);
+ }
+
+ /**
+ * Does the process to enter a given AST node.
+ * This updates state of analysis and calls `enterNode` of the wrapped.
+ * @param {ASTNode} node A node which is entering.
+ * @returns {void}
+ */
+ enterNode(node) {
+ this.currentNode = node;
+
+ // Updates the code path due to node's position in its parent node.
+ if (node.parent) {
+ preprocess(this, node);
+ }
+
+ /*
+ * Updates the code path.
+ * And emits onCodePathStart/onCodePathSegmentStart events.
+ */
+ processCodePathToEnter(this, node);
+
+ // Emits node events.
+ this.original.enterNode(node);
+
+ this.currentNode = null;
+ }
+
+ /**
+ * Does the process to leave a given AST node.
+ * This updates state of analysis and calls `leaveNode` of the wrapped.
+ * @param {ASTNode} node A node which is leaving.
+ * @returns {void}
+ */
+ leaveNode(node) {
+ this.currentNode = node;
+
+ /*
+ * Updates the code path.
+ * And emits onCodePathStart/onCodePathSegmentStart events.
+ */
+ processCodePathToExit(this, node);
+
+ // Emits node events.
+ this.original.leaveNode(node);
+
+ // Emits the last onCodePathStart/onCodePathSegmentStart events.
+ postprocess(this, node);
+
+ this.currentNode = null;
+ }
+
+ /**
+ * This is called on a code path looped.
+ * Then this raises a looped event.
+ * @param {CodePathSegment} fromSegment A segment of prev.
+ * @param {CodePathSegment} toSegment A segment of next.
+ * @returns {void}
+ */
+ onLooped(fromSegment, toSegment) {
+ if (fromSegment.reachable && toSegment.reachable) {
+ debug.dump(`onCodePathSegmentLoop ${fromSegment.id} -> ${toSegment.id}`);
+ this.emitter.emit(
+ "onCodePathSegmentLoop",
+ fromSegment,
+ toSegment,
+ this.currentNode
+ );
+ }
+ }
+}
+
+module.exports = CodePathAnalyzer;
projects / dotfiles / .git / blobdiff