2 * @fileoverview A class of the code path analyzer.
3 * @author Toru Nagashima
8 //------------------------------------------------------------------------------
10 //------------------------------------------------------------------------------
12 const assert = require("assert"),
13 { breakableTypePattern } = require("../../shared/ast-utils"),
14 CodePath = require("./code-path"),
15 CodePathSegment = require("./code-path-segment"),
16 IdGenerator = require("./id-generator"),
17 debug = require("./debug-helpers");
19 //------------------------------------------------------------------------------
21 //------------------------------------------------------------------------------
24 * Checks whether or not a given node is a `case` node (not `default` node).
25 * @param {ASTNode} node A `SwitchCase` node to check.
26 * @returns {boolean} `true` if the node is a `case` node (not `default` node).
28 function isCaseNode(node) {
29 return Boolean(node.test);
33 * Checks whether the given logical operator is taken into account for the code
35 * @param {string} operator The operator found in the LogicalExpression node
36 * @returns {boolean} `true` if the operator is "&&" or "||" or "??"
38 function isHandledLogicalOperator(operator) {
39 return operator === "&&" || operator === "||" || operator === "??";
43 * Checks whether the given assignment operator is a logical assignment operator.
44 * Logical assignments are taken into account for the code path analysis
45 * because of their short-circuiting semantics.
46 * @param {string} operator The operator found in the AssignmentExpression node
47 * @returns {boolean} `true` if the operator is "&&=" or "||=" or "??="
49 function isLogicalAssignmentOperator(operator) {
50 return operator === "&&=" || operator === "||=" || operator === "??=";
54 * Gets the label if the parent node of a given node is a LabeledStatement.
55 * @param {ASTNode} node A node to get.
56 * @returns {string|null} The label or `null`.
58 function getLabel(node) {
59 if (node.parent.type === "LabeledStatement") {
60 return node.parent.label.name;
66 * Checks whether or not a given logical expression node goes different path
67 * between the `true` case and the `false` case.
68 * @param {ASTNode} node A node to check.
69 * @returns {boolean} `true` if the node is a test of a choice statement.
71 function isForkingByTrueOrFalse(node) {
72 const parent = node.parent;
74 switch (parent.type) {
75 case "ConditionalExpression":
77 case "WhileStatement":
78 case "DoWhileStatement":
80 return parent.test === node;
82 case "LogicalExpression":
83 return isHandledLogicalOperator(parent.operator);
85 case "AssignmentExpression":
86 return isLogicalAssignmentOperator(parent.operator);
94 * Gets the boolean value of a given literal node.
96 * This is used to detect infinity loops (e.g. `while (true) {}`).
97 * Statements preceded by an infinity loop are unreachable if the loop didn't
98 * have any `break` statement.
99 * @param {ASTNode} node A node to get.
100 * @returns {boolean|undefined} a boolean value if the node is a Literal node,
101 * otherwise `undefined`.
103 function getBooleanValueIfSimpleConstant(node) {
104 if (node.type === "Literal") {
105 return Boolean(node.value);
111 * Checks that a given identifier node is a reference or not.
113 * This is used to detect the first throwable node in a `try` block.
114 * @param {ASTNode} node An Identifier node to check.
115 * @returns {boolean} `true` if the node is a reference.
117 function isIdentifierReference(node) {
118 const parent = node.parent;
120 switch (parent.type) {
121 case "LabeledStatement":
122 case "BreakStatement":
123 case "ContinueStatement":
126 case "ImportSpecifier":
127 case "ImportDefaultSpecifier":
128 case "ImportNamespaceSpecifier":
132 case "FunctionDeclaration":
133 case "FunctionExpression":
134 case "ArrowFunctionExpression":
135 case "ClassDeclaration":
136 case "ClassExpression":
137 case "VariableDeclarator":
138 return parent.id !== node;
141 case "MethodDefinition":
143 parent.key !== node ||
148 case "AssignmentPattern":
149 return parent.key !== node;
157 * Updates the current segment with the head segment.
158 * This is similar to local branches and tracking branches of git.
160 * To separate the current and the head is in order to not make useless segments.
162 * In this process, both "onCodePathSegmentStart" and "onCodePathSegmentEnd"
164 * @param {CodePathAnalyzer} analyzer The instance.
165 * @param {ASTNode} node The current AST node.
168 function forwardCurrentToHead(analyzer, node) {
169 const codePath = analyzer.codePath;
170 const state = CodePath.getState(codePath);
171 const currentSegments = state.currentSegments;
172 const headSegments = state.headSegments;
173 const end = Math.max(currentSegments.length, headSegments.length);
174 let i, currentSegment, headSegment;
176 // Fires leaving events.
177 for (i = 0; i < end; ++i) {
178 currentSegment = currentSegments[i];
179 headSegment = headSegments[i];
181 if (currentSegment !== headSegment && currentSegment) {
182 debug.dump(`onCodePathSegmentEnd ${currentSegment.id}`);
184 if (currentSegment.reachable) {
185 analyzer.emitter.emit(
186 "onCodePathSegmentEnd",
195 state.currentSegments = headSegments;
197 // Fires entering events.
198 for (i = 0; i < end; ++i) {
199 currentSegment = currentSegments[i];
200 headSegment = headSegments[i];
202 if (currentSegment !== headSegment && headSegment) {
203 debug.dump(`onCodePathSegmentStart ${headSegment.id}`);
205 CodePathSegment.markUsed(headSegment);
206 if (headSegment.reachable) {
207 analyzer.emitter.emit(
208 "onCodePathSegmentStart",
219 * Updates the current segment with empty.
220 * This is called at the last of functions or the program.
221 * @param {CodePathAnalyzer} analyzer The instance.
222 * @param {ASTNode} node The current AST node.
225 function leaveFromCurrentSegment(analyzer, node) {
226 const state = CodePath.getState(analyzer.codePath);
227 const currentSegments = state.currentSegments;
229 for (let i = 0; i < currentSegments.length; ++i) {
230 const currentSegment = currentSegments[i];
232 debug.dump(`onCodePathSegmentEnd ${currentSegment.id}`);
233 if (currentSegment.reachable) {
234 analyzer.emitter.emit(
235 "onCodePathSegmentEnd",
242 state.currentSegments = [];
246 * Updates the code path due to the position of a given node in the parent node
249 * For example, if the node is `parent.consequent`, this creates a fork from the
251 * @param {CodePathAnalyzer} analyzer The instance.
252 * @param {ASTNode} node The current AST node.
255 function preprocess(analyzer, node) {
256 const codePath = analyzer.codePath;
257 const state = CodePath.getState(codePath);
258 const parent = node.parent;
260 switch (parent.type) {
262 // The `arguments.length == 0` case is in `postprocess` function.
263 case "CallExpression":
264 if (parent.optional === true && parent.arguments.length >= 1 && parent.arguments[0] === node) {
265 state.makeOptionalRight();
268 case "MemberExpression":
269 if (parent.optional === true && parent.property === node) {
270 state.makeOptionalRight();
274 case "LogicalExpression":
276 parent.right === node &&
277 isHandledLogicalOperator(parent.operator)
279 state.makeLogicalRight();
283 case "AssignmentExpression":
285 parent.right === node &&
286 isLogicalAssignmentOperator(parent.operator)
288 state.makeLogicalRight();
292 case "ConditionalExpression":
296 * Fork if this node is at `consequent`/`alternate`.
297 * `popForkContext()` exists at `IfStatement:exit` and
298 * `ConditionalExpression:exit`.
300 if (parent.consequent === node) {
301 state.makeIfConsequent();
302 } else if (parent.alternate === node) {
303 state.makeIfAlternate();
308 if (parent.consequent[0] === node) {
309 state.makeSwitchCaseBody(false, !parent.test);
314 if (parent.handler === node) {
315 state.makeCatchBlock();
316 } else if (parent.finalizer === node) {
317 state.makeFinallyBlock();
321 case "WhileStatement":
322 if (parent.test === node) {
323 state.makeWhileTest(getBooleanValueIfSimpleConstant(node));
325 assert(parent.body === node);
326 state.makeWhileBody();
330 case "DoWhileStatement":
331 if (parent.body === node) {
332 state.makeDoWhileBody();
334 assert(parent.test === node);
335 state.makeDoWhileTest(getBooleanValueIfSimpleConstant(node));
340 if (parent.test === node) {
341 state.makeForTest(getBooleanValueIfSimpleConstant(node));
342 } else if (parent.update === node) {
343 state.makeForUpdate();
344 } else if (parent.body === node) {
349 case "ForInStatement":
350 case "ForOfStatement":
351 if (parent.left === node) {
352 state.makeForInOfLeft();
353 } else if (parent.right === node) {
354 state.makeForInOfRight();
356 assert(parent.body === node);
357 state.makeForInOfBody();
361 case "AssignmentPattern":
364 * Fork if this node is at `right`.
365 * `left` is executed always, so it uses the current path.
366 * `popForkContext()` exists at `AssignmentPattern:exit`.
368 if (parent.right === node) {
369 state.pushForkContext();
370 state.forkBypassPath();
381 * Updates the code path due to the type of a given node in entering.
382 * @param {CodePathAnalyzer} analyzer The instance.
383 * @param {ASTNode} node The current AST node.
386 function processCodePathToEnter(analyzer, node) {
387 let codePath = analyzer.codePath;
388 let state = codePath && CodePath.getState(codePath);
389 const parent = node.parent;
393 case "FunctionDeclaration":
394 case "FunctionExpression":
395 case "ArrowFunctionExpression":
398 // Emits onCodePathSegmentStart events if updated.
399 forwardCurrentToHead(analyzer, node);
400 debug.dumpState(node, state, false);
403 // Create the code path of this scope.
404 codePath = analyzer.codePath = new CodePath(
405 analyzer.idGenerator.next(),
409 state = CodePath.getState(codePath);
411 // Emits onCodePathStart events.
412 debug.dump(`onCodePathStart ${codePath.id}`);
413 analyzer.emitter.emit("onCodePathStart", codePath, node);
416 case "ChainExpression":
417 state.pushChainContext();
419 case "CallExpression":
420 if (node.optional === true) {
421 state.makeOptionalNode();
424 case "MemberExpression":
425 if (node.optional === true) {
426 state.makeOptionalNode();
430 case "LogicalExpression":
431 if (isHandledLogicalOperator(node.operator)) {
432 state.pushChoiceContext(
434 isForkingByTrueOrFalse(node)
439 case "AssignmentExpression":
440 if (isLogicalAssignmentOperator(node.operator)) {
441 state.pushChoiceContext(
442 node.operator.slice(0, -1), // removes `=` from the end
443 isForkingByTrueOrFalse(node)
448 case "ConditionalExpression":
450 state.pushChoiceContext("test", false);
453 case "SwitchStatement":
454 state.pushSwitchContext(
455 node.cases.some(isCaseNode),
461 state.pushTryContext(Boolean(node.finalizer));
467 * Fork if this node is after the 2st node in `cases`.
468 * It's similar to `else` blocks.
469 * The next `test` node is processed in this path.
471 if (parent.discriminant !== node && parent.cases[0] !== node) {
476 case "WhileStatement":
477 case "DoWhileStatement":
479 case "ForInStatement":
480 case "ForOfStatement":
481 state.pushLoopContext(node.type, getLabel(node));
484 case "LabeledStatement":
485 if (!breakableTypePattern.test(node.body.type)) {
486 state.pushBreakContext(false, node.label.name);
494 // Emits onCodePathSegmentStart events if updated.
495 forwardCurrentToHead(analyzer, node);
496 debug.dumpState(node, state, false);
500 * Updates the code path due to the type of a given node in leaving.
501 * @param {CodePathAnalyzer} analyzer The instance.
502 * @param {ASTNode} node The current AST node.
505 function processCodePathToExit(analyzer, node) {
506 const codePath = analyzer.codePath;
507 const state = CodePath.getState(codePath);
508 let dontForward = false;
511 case "ChainExpression":
512 state.popChainContext();
516 case "ConditionalExpression":
517 state.popChoiceContext();
520 case "LogicalExpression":
521 if (isHandledLogicalOperator(node.operator)) {
522 state.popChoiceContext();
526 case "AssignmentExpression":
527 if (isLogicalAssignmentOperator(node.operator)) {
528 state.popChoiceContext();
532 case "SwitchStatement":
533 state.popSwitchContext();
539 * This is the same as the process at the 1st `consequent` node in
540 * `preprocess` function.
541 * Must do if this `consequent` is empty.
543 if (node.consequent.length === 0) {
544 state.makeSwitchCaseBody(true, !node.test);
546 if (state.forkContext.reachable) {
552 state.popTryContext();
555 case "BreakStatement":
556 forwardCurrentToHead(analyzer, node);
557 state.makeBreak(node.label && node.label.name);
561 case "ContinueStatement":
562 forwardCurrentToHead(analyzer, node);
563 state.makeContinue(node.label && node.label.name);
567 case "ReturnStatement":
568 forwardCurrentToHead(analyzer, node);
573 case "ThrowStatement":
574 forwardCurrentToHead(analyzer, node);
580 if (isIdentifierReference(node)) {
581 state.makeFirstThrowablePathInTryBlock();
586 case "CallExpression":
587 case "ImportExpression":
588 case "MemberExpression":
589 case "NewExpression":
590 case "YieldExpression":
591 state.makeFirstThrowablePathInTryBlock();
594 case "WhileStatement":
595 case "DoWhileStatement":
597 case "ForInStatement":
598 case "ForOfStatement":
599 state.popLoopContext();
602 case "AssignmentPattern":
603 state.popForkContext();
606 case "LabeledStatement":
607 if (!breakableTypePattern.test(node.body.type)) {
608 state.popBreakContext();
616 // Emits onCodePathSegmentStart events if updated.
618 forwardCurrentToHead(analyzer, node);
620 debug.dumpState(node, state, true);
624 * Updates the code path to finalize the current code path.
625 * @param {CodePathAnalyzer} analyzer The instance.
626 * @param {ASTNode} node The current AST node.
629 function postprocess(analyzer, node) {
632 case "FunctionDeclaration":
633 case "FunctionExpression":
634 case "ArrowFunctionExpression": {
635 let codePath = analyzer.codePath;
637 // Mark the current path as the final node.
638 CodePath.getState(codePath).makeFinal();
640 // Emits onCodePathSegmentEnd event of the current segments.
641 leaveFromCurrentSegment(analyzer, node);
643 // Emits onCodePathEnd event of this code path.
644 debug.dump(`onCodePathEnd ${codePath.id}`);
645 analyzer.emitter.emit("onCodePathEnd", codePath, node);
646 debug.dumpDot(codePath);
648 codePath = analyzer.codePath = analyzer.codePath.upper;
650 debug.dumpState(node, CodePath.getState(codePath), true);
655 // The `arguments.length >= 1` case is in `preprocess` function.
656 case "CallExpression":
657 if (node.optional === true && node.arguments.length === 0) {
658 CodePath.getState(analyzer.codePath).makeOptionalRight();
667 //------------------------------------------------------------------------------
669 //------------------------------------------------------------------------------
672 * The class to analyze code paths.
673 * This class implements the EventGenerator interface.
675 class CodePathAnalyzer {
677 // eslint-disable-next-line jsdoc/require-description
679 * @param {EventGenerator} eventGenerator An event generator to wrap.
681 constructor(eventGenerator) {
682 this.original = eventGenerator;
683 this.emitter = eventGenerator.emitter;
684 this.codePath = null;
685 this.idGenerator = new IdGenerator("s");
686 this.currentNode = null;
687 this.onLooped = this.onLooped.bind(this);
691 * Does the process to enter a given AST node.
692 * This updates state of analysis and calls `enterNode` of the wrapped.
693 * @param {ASTNode} node A node which is entering.
697 this.currentNode = node;
699 // Updates the code path due to node's position in its parent node.
701 preprocess(this, node);
705 * Updates the code path.
706 * And emits onCodePathStart/onCodePathSegmentStart events.
708 processCodePathToEnter(this, node);
710 // Emits node events.
711 this.original.enterNode(node);
713 this.currentNode = null;
717 * Does the process to leave a given AST node.
718 * This updates state of analysis and calls `leaveNode` of the wrapped.
719 * @param {ASTNode} node A node which is leaving.
723 this.currentNode = node;
726 * Updates the code path.
727 * And emits onCodePathStart/onCodePathSegmentStart events.
729 processCodePathToExit(this, node);
731 // Emits node events.
732 this.original.leaveNode(node);
734 // Emits the last onCodePathStart/onCodePathSegmentStart events.
735 postprocess(this, node);
737 this.currentNode = null;
741 * This is called on a code path looped.
742 * Then this raises a looped event.
743 * @param {CodePathSegment} fromSegment A segment of prev.
744 * @param {CodePathSegment} toSegment A segment of next.
747 onLooped(fromSegment, toSegment) {
748 if (fromSegment.reachable && toSegment.reachable) {
749 debug.dump(`onCodePathSegmentLoop ${fromSegment.id} -> ${toSegment.id}`);
751 "onCodePathSegmentLoop",
760 module.exports = CodePathAnalyzer;