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 "||"
38 function isHandledLogicalOperator(operator) {
39 return operator === "&&" || operator === "||";
43 * Gets the label if the parent node of a given node is a LabeledStatement.
44 * @param {ASTNode} node A node to get.
45 * @returns {string|null} The label or `null`.
47 function getLabel(node) {
48 if (node.parent.type === "LabeledStatement") {
49 return node.parent.label.name;
55 * Checks whether or not a given logical expression node goes different path
56 * between the `true` case and the `false` case.
57 * @param {ASTNode} node A node to check.
58 * @returns {boolean} `true` if the node is a test of a choice statement.
60 function isForkingByTrueOrFalse(node) {
61 const parent = node.parent;
63 switch (parent.type) {
64 case "ConditionalExpression":
66 case "WhileStatement":
67 case "DoWhileStatement":
69 return parent.test === node;
71 case "LogicalExpression":
72 return isHandledLogicalOperator(parent.operator);
80 * Gets the boolean value of a given literal node.
82 * This is used to detect infinity loops (e.g. `while (true) {}`).
83 * Statements preceded by an infinity loop are unreachable if the loop didn't
84 * have any `break` statement.
85 * @param {ASTNode} node A node to get.
86 * @returns {boolean|undefined} a boolean value if the node is a Literal node,
87 * otherwise `undefined`.
89 function getBooleanValueIfSimpleConstant(node) {
90 if (node.type === "Literal") {
91 return Boolean(node.value);
97 * Checks that a given identifier node is a reference or not.
99 * This is used to detect the first throwable node in a `try` block.
100 * @param {ASTNode} node An Identifier node to check.
101 * @returns {boolean} `true` if the node is a reference.
103 function isIdentifierReference(node) {
104 const parent = node.parent;
106 switch (parent.type) {
107 case "LabeledStatement":
108 case "BreakStatement":
109 case "ContinueStatement":
112 case "ImportSpecifier":
113 case "ImportDefaultSpecifier":
114 case "ImportNamespaceSpecifier":
118 case "FunctionDeclaration":
119 case "FunctionExpression":
120 case "ArrowFunctionExpression":
121 case "ClassDeclaration":
122 case "ClassExpression":
123 case "VariableDeclarator":
124 return parent.id !== node;
127 case "MethodDefinition":
129 parent.key !== node ||
134 case "AssignmentPattern":
135 return parent.key !== node;
143 * Updates the current segment with the head segment.
144 * This is similar to local branches and tracking branches of git.
146 * To separate the current and the head is in order to not make useless segments.
148 * In this process, both "onCodePathSegmentStart" and "onCodePathSegmentEnd"
150 * @param {CodePathAnalyzer} analyzer The instance.
151 * @param {ASTNode} node The current AST node.
154 function forwardCurrentToHead(analyzer, node) {
155 const codePath = analyzer.codePath;
156 const state = CodePath.getState(codePath);
157 const currentSegments = state.currentSegments;
158 const headSegments = state.headSegments;
159 const end = Math.max(currentSegments.length, headSegments.length);
160 let i, currentSegment, headSegment;
162 // Fires leaving events.
163 for (i = 0; i < end; ++i) {
164 currentSegment = currentSegments[i];
165 headSegment = headSegments[i];
167 if (currentSegment !== headSegment && currentSegment) {
168 debug.dump(`onCodePathSegmentEnd ${currentSegment.id}`);
170 if (currentSegment.reachable) {
171 analyzer.emitter.emit(
172 "onCodePathSegmentEnd",
181 state.currentSegments = headSegments;
183 // Fires entering events.
184 for (i = 0; i < end; ++i) {
185 currentSegment = currentSegments[i];
186 headSegment = headSegments[i];
188 if (currentSegment !== headSegment && headSegment) {
189 debug.dump(`onCodePathSegmentStart ${headSegment.id}`);
191 CodePathSegment.markUsed(headSegment);
192 if (headSegment.reachable) {
193 analyzer.emitter.emit(
194 "onCodePathSegmentStart",
205 * Updates the current segment with empty.
206 * This is called at the last of functions or the program.
207 * @param {CodePathAnalyzer} analyzer The instance.
208 * @param {ASTNode} node The current AST node.
211 function leaveFromCurrentSegment(analyzer, node) {
212 const state = CodePath.getState(analyzer.codePath);
213 const currentSegments = state.currentSegments;
215 for (let i = 0; i < currentSegments.length; ++i) {
216 const currentSegment = currentSegments[i];
218 debug.dump(`onCodePathSegmentEnd ${currentSegment.id}`);
219 if (currentSegment.reachable) {
220 analyzer.emitter.emit(
221 "onCodePathSegmentEnd",
228 state.currentSegments = [];
232 * Updates the code path due to the position of a given node in the parent node
235 * For example, if the node is `parent.consequent`, this creates a fork from the
237 * @param {CodePathAnalyzer} analyzer The instance.
238 * @param {ASTNode} node The current AST node.
241 function preprocess(analyzer, node) {
242 const codePath = analyzer.codePath;
243 const state = CodePath.getState(codePath);
244 const parent = node.parent;
246 switch (parent.type) {
247 case "LogicalExpression":
249 parent.right === node &&
250 isHandledLogicalOperator(parent.operator)
252 state.makeLogicalRight();
256 case "ConditionalExpression":
260 * Fork if this node is at `consequent`/`alternate`.
261 * `popForkContext()` exists at `IfStatement:exit` and
262 * `ConditionalExpression:exit`.
264 if (parent.consequent === node) {
265 state.makeIfConsequent();
266 } else if (parent.alternate === node) {
267 state.makeIfAlternate();
272 if (parent.consequent[0] === node) {
273 state.makeSwitchCaseBody(false, !parent.test);
278 if (parent.handler === node) {
279 state.makeCatchBlock();
280 } else if (parent.finalizer === node) {
281 state.makeFinallyBlock();
285 case "WhileStatement":
286 if (parent.test === node) {
287 state.makeWhileTest(getBooleanValueIfSimpleConstant(node));
289 assert(parent.body === node);
290 state.makeWhileBody();
294 case "DoWhileStatement":
295 if (parent.body === node) {
296 state.makeDoWhileBody();
298 assert(parent.test === node);
299 state.makeDoWhileTest(getBooleanValueIfSimpleConstant(node));
304 if (parent.test === node) {
305 state.makeForTest(getBooleanValueIfSimpleConstant(node));
306 } else if (parent.update === node) {
307 state.makeForUpdate();
308 } else if (parent.body === node) {
313 case "ForInStatement":
314 case "ForOfStatement":
315 if (parent.left === node) {
316 state.makeForInOfLeft();
317 } else if (parent.right === node) {
318 state.makeForInOfRight();
320 assert(parent.body === node);
321 state.makeForInOfBody();
325 case "AssignmentPattern":
328 * Fork if this node is at `right`.
329 * `left` is executed always, so it uses the current path.
330 * `popForkContext()` exists at `AssignmentPattern:exit`.
332 if (parent.right === node) {
333 state.pushForkContext();
334 state.forkBypassPath();
345 * Updates the code path due to the type of a given node in entering.
346 * @param {CodePathAnalyzer} analyzer The instance.
347 * @param {ASTNode} node The current AST node.
350 function processCodePathToEnter(analyzer, node) {
351 let codePath = analyzer.codePath;
352 let state = codePath && CodePath.getState(codePath);
353 const parent = node.parent;
357 case "FunctionDeclaration":
358 case "FunctionExpression":
359 case "ArrowFunctionExpression":
362 // Emits onCodePathSegmentStart events if updated.
363 forwardCurrentToHead(analyzer, node);
364 debug.dumpState(node, state, false);
367 // Create the code path of this scope.
368 codePath = analyzer.codePath = new CodePath(
369 analyzer.idGenerator.next(),
373 state = CodePath.getState(codePath);
375 // Emits onCodePathStart events.
376 debug.dump(`onCodePathStart ${codePath.id}`);
377 analyzer.emitter.emit("onCodePathStart", codePath, node);
380 case "LogicalExpression":
381 if (isHandledLogicalOperator(node.operator)) {
382 state.pushChoiceContext(
384 isForkingByTrueOrFalse(node)
389 case "ConditionalExpression":
391 state.pushChoiceContext("test", false);
394 case "SwitchStatement":
395 state.pushSwitchContext(
396 node.cases.some(isCaseNode),
402 state.pushTryContext(Boolean(node.finalizer));
408 * Fork if this node is after the 2st node in `cases`.
409 * It's similar to `else` blocks.
410 * The next `test` node is processed in this path.
412 if (parent.discriminant !== node && parent.cases[0] !== node) {
417 case "WhileStatement":
418 case "DoWhileStatement":
420 case "ForInStatement":
421 case "ForOfStatement":
422 state.pushLoopContext(node.type, getLabel(node));
425 case "LabeledStatement":
426 if (!breakableTypePattern.test(node.body.type)) {
427 state.pushBreakContext(false, node.label.name);
435 // Emits onCodePathSegmentStart events if updated.
436 forwardCurrentToHead(analyzer, node);
437 debug.dumpState(node, state, false);
441 * Updates the code path due to the type of a given node in leaving.
442 * @param {CodePathAnalyzer} analyzer The instance.
443 * @param {ASTNode} node The current AST node.
446 function processCodePathToExit(analyzer, node) {
447 const codePath = analyzer.codePath;
448 const state = CodePath.getState(codePath);
449 let dontForward = false;
453 case "ConditionalExpression":
454 state.popChoiceContext();
457 case "LogicalExpression":
458 if (isHandledLogicalOperator(node.operator)) {
459 state.popChoiceContext();
463 case "SwitchStatement":
464 state.popSwitchContext();
470 * This is the same as the process at the 1st `consequent` node in
471 * `preprocess` function.
472 * Must do if this `consequent` is empty.
474 if (node.consequent.length === 0) {
475 state.makeSwitchCaseBody(true, !node.test);
477 if (state.forkContext.reachable) {
483 state.popTryContext();
486 case "BreakStatement":
487 forwardCurrentToHead(analyzer, node);
488 state.makeBreak(node.label && node.label.name);
492 case "ContinueStatement":
493 forwardCurrentToHead(analyzer, node);
494 state.makeContinue(node.label && node.label.name);
498 case "ReturnStatement":
499 forwardCurrentToHead(analyzer, node);
504 case "ThrowStatement":
505 forwardCurrentToHead(analyzer, node);
511 if (isIdentifierReference(node)) {
512 state.makeFirstThrowablePathInTryBlock();
517 case "CallExpression":
518 case "ImportExpression":
519 case "MemberExpression":
520 case "NewExpression":
521 state.makeFirstThrowablePathInTryBlock();
524 case "WhileStatement":
525 case "DoWhileStatement":
527 case "ForInStatement":
528 case "ForOfStatement":
529 state.popLoopContext();
532 case "AssignmentPattern":
533 state.popForkContext();
536 case "LabeledStatement":
537 if (!breakableTypePattern.test(node.body.type)) {
538 state.popBreakContext();
546 // Emits onCodePathSegmentStart events if updated.
548 forwardCurrentToHead(analyzer, node);
550 debug.dumpState(node, state, true);
554 * Updates the code path to finalize the current code path.
555 * @param {CodePathAnalyzer} analyzer The instance.
556 * @param {ASTNode} node The current AST node.
559 function postprocess(analyzer, node) {
562 case "FunctionDeclaration":
563 case "FunctionExpression":
564 case "ArrowFunctionExpression": {
565 let codePath = analyzer.codePath;
567 // Mark the current path as the final node.
568 CodePath.getState(codePath).makeFinal();
570 // Emits onCodePathSegmentEnd event of the current segments.
571 leaveFromCurrentSegment(analyzer, node);
573 // Emits onCodePathEnd event of this code path.
574 debug.dump(`onCodePathEnd ${codePath.id}`);
575 analyzer.emitter.emit("onCodePathEnd", codePath, node);
576 debug.dumpDot(codePath);
578 codePath = analyzer.codePath = analyzer.codePath.upper;
580 debug.dumpState(node, CodePath.getState(codePath), true);
590 //------------------------------------------------------------------------------
592 //------------------------------------------------------------------------------
595 * The class to analyze code paths.
596 * This class implements the EventGenerator interface.
598 class CodePathAnalyzer {
600 // eslint-disable-next-line jsdoc/require-description
602 * @param {EventGenerator} eventGenerator An event generator to wrap.
604 constructor(eventGenerator) {
605 this.original = eventGenerator;
606 this.emitter = eventGenerator.emitter;
607 this.codePath = null;
608 this.idGenerator = new IdGenerator("s");
609 this.currentNode = null;
610 this.onLooped = this.onLooped.bind(this);
614 * Does the process to enter a given AST node.
615 * This updates state of analysis and calls `enterNode` of the wrapped.
616 * @param {ASTNode} node A node which is entering.
620 this.currentNode = node;
622 // Updates the code path due to node's position in its parent node.
624 preprocess(this, node);
628 * Updates the code path.
629 * And emits onCodePathStart/onCodePathSegmentStart events.
631 processCodePathToEnter(this, node);
633 // Emits node events.
634 this.original.enterNode(node);
636 this.currentNode = null;
640 * Does the process to leave a given AST node.
641 * This updates state of analysis and calls `leaveNode` of the wrapped.
642 * @param {ASTNode} node A node which is leaving.
646 this.currentNode = node;
649 * Updates the code path.
650 * And emits onCodePathStart/onCodePathSegmentStart events.
652 processCodePathToExit(this, node);
654 // Emits node events.
655 this.original.leaveNode(node);
657 // Emits the last onCodePathStart/onCodePathSegmentStart events.
658 postprocess(this, node);
660 this.currentNode = null;
664 * This is called on a code path looped.
665 * Then this raises a looped event.
666 * @param {CodePathSegment} fromSegment A segment of prev.
667 * @param {CodePathSegment} toSegment A segment of next.
670 onLooped(fromSegment, toSegment) {
671 if (fromSegment.reachable && toSegment.reachable) {
672 debug.dump(`onCodePathSegmentLoop ${fromSegment.id} -> ${toSegment.id}`);
674 "onCodePathSegmentLoop",
683 module.exports = CodePathAnalyzer;