source: imaps-frontend/node_modules/eslint/lib/linter/code-path-analysis/code-path-analyzer.js

main
Last change on this file was d565449, checked in by stefan toskovski <stefantoska84@…>, 4 weeks ago

Update repo after prototype presentation
  • Property mode set to 100644
File size: 24.6 KB
RevLine 
[d565449]1/**
2 * @fileoverview A class of the code path analyzer.
3 * @author Toru Nagashima
4 */
5
6"use strict";
7
8//------------------------------------------------------------------------------
9// Requirements
10//------------------------------------------------------------------------------
11
12const 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");
18
19//------------------------------------------------------------------------------
20// Helpers
21//------------------------------------------------------------------------------
22
23/**
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).
27 */
28function isCaseNode(node) {
29 return Boolean(node.test);
30}
31
32/**
33 * Checks if a given node appears as the value of a PropertyDefinition node.
34 * @param {ASTNode} node THe node to check.
35 * @returns {boolean} `true` if the node is a PropertyDefinition value,
36 * false if not.
37 */
38function isPropertyDefinitionValue(node) {
39 const parent = node.parent;
40
41 return parent && parent.type === "PropertyDefinition" && parent.value === node;
42}
43
44/**
45 * Checks whether the given logical operator is taken into account for the code
46 * path analysis.
47 * @param {string} operator The operator found in the LogicalExpression node
48 * @returns {boolean} `true` if the operator is "&&" or "||" or "??"
49 */
50function isHandledLogicalOperator(operator) {
51 return operator === "&&" || operator === "||" || operator === "??";
52}
53
54/**
55 * Checks whether the given assignment operator is a logical assignment operator.
56 * Logical assignments are taken into account for the code path analysis
57 * because of their short-circuiting semantics.
58 * @param {string} operator The operator found in the AssignmentExpression node
59 * @returns {boolean} `true` if the operator is "&&=" or "||=" or "??="
60 */
61function isLogicalAssignmentOperator(operator) {
62 return operator === "&&=" || operator === "||=" || operator === "??=";
63}
64
65/**
66 * Gets the label if the parent node of a given node is a LabeledStatement.
67 * @param {ASTNode} node A node to get.
68 * @returns {string|null} The label or `null`.
69 */
70function getLabel(node) {
71 if (node.parent.type === "LabeledStatement") {
72 return node.parent.label.name;
73 }
74 return null;
75}
76
77/**
78 * Checks whether or not a given logical expression node goes different path
79 * between the `true` case and the `false` case.
80 * @param {ASTNode} node A node to check.
81 * @returns {boolean} `true` if the node is a test of a choice statement.
82 */
83function isForkingByTrueOrFalse(node) {
84 const parent = node.parent;
85
86 switch (parent.type) {
87 case "ConditionalExpression":
88 case "IfStatement":
89 case "WhileStatement":
90 case "DoWhileStatement":
91 case "ForStatement":
92 return parent.test === node;
93
94 case "LogicalExpression":
95 return isHandledLogicalOperator(parent.operator);
96
97 case "AssignmentExpression":
98 return isLogicalAssignmentOperator(parent.operator);
99
100 default:
101 return false;
102 }
103}
104
105/**
106 * Gets the boolean value of a given literal node.
107 *
108 * This is used to detect infinity loops (e.g. `while (true) {}`).
109 * Statements preceded by an infinity loop are unreachable if the loop didn't
110 * have any `break` statement.
111 * @param {ASTNode} node A node to get.
112 * @returns {boolean|undefined} a boolean value if the node is a Literal node,
113 * otherwise `undefined`.
114 */
115function getBooleanValueIfSimpleConstant(node) {
116 if (node.type === "Literal") {
117 return Boolean(node.value);
118 }
119 return void 0;
120}
121
122/**
123 * Checks that a given identifier node is a reference or not.
124 *
125 * This is used to detect the first throwable node in a `try` block.
126 * @param {ASTNode} node An Identifier node to check.
127 * @returns {boolean} `true` if the node is a reference.
128 */
129function isIdentifierReference(node) {
130 const parent = node.parent;
131
132 switch (parent.type) {
133 case "LabeledStatement":
134 case "BreakStatement":
135 case "ContinueStatement":
136 case "ArrayPattern":
137 case "RestElement":
138 case "ImportSpecifier":
139 case "ImportDefaultSpecifier":
140 case "ImportNamespaceSpecifier":
141 case "CatchClause":
142 return false;
143
144 case "FunctionDeclaration":
145 case "FunctionExpression":
146 case "ArrowFunctionExpression":
147 case "ClassDeclaration":
148 case "ClassExpression":
149 case "VariableDeclarator":
150 return parent.id !== node;
151
152 case "Property":
153 case "PropertyDefinition":
154 case "MethodDefinition":
155 return (
156 parent.key !== node ||
157 parent.computed ||
158 parent.shorthand
159 );
160
161 case "AssignmentPattern":
162 return parent.key !== node;
163
164 default:
165 return true;
166 }
167}
168
169/**
170 * Updates the current segment with the head segment.
171 * This is similar to local branches and tracking branches of git.
172 *
173 * To separate the current and the head is in order to not make useless segments.
174 *
175 * In this process, both "onCodePathSegmentStart" and "onCodePathSegmentEnd"
176 * events are fired.
177 * @param {CodePathAnalyzer} analyzer The instance.
178 * @param {ASTNode} node The current AST node.
179 * @returns {void}
180 */
181function forwardCurrentToHead(analyzer, node) {
182 const codePath = analyzer.codePath;
183 const state = CodePath.getState(codePath);
184 const currentSegments = state.currentSegments;
185 const headSegments = state.headSegments;
186 const end = Math.max(currentSegments.length, headSegments.length);
187 let i, currentSegment, headSegment;
188
189 // Fires leaving events.
190 for (i = 0; i < end; ++i) {
191 currentSegment = currentSegments[i];
192 headSegment = headSegments[i];
193
194 if (currentSegment !== headSegment && currentSegment) {
195
196 const eventName = currentSegment.reachable
197 ? "onCodePathSegmentEnd"
198 : "onUnreachableCodePathSegmentEnd";
199
200 debug.dump(`${eventName} ${currentSegment.id}`);
201
202 analyzer.emitter.emit(
203 eventName,
204 currentSegment,
205 node
206 );
207 }
208 }
209
210 // Update state.
211 state.currentSegments = headSegments;
212
213 // Fires entering events.
214 for (i = 0; i < end; ++i) {
215 currentSegment = currentSegments[i];
216 headSegment = headSegments[i];
217
218 if (currentSegment !== headSegment && headSegment) {
219
220 const eventName = headSegment.reachable
221 ? "onCodePathSegmentStart"
222 : "onUnreachableCodePathSegmentStart";
223
224 debug.dump(`${eventName} ${headSegment.id}`);
225
226 CodePathSegment.markUsed(headSegment);
227 analyzer.emitter.emit(
228 eventName,
229 headSegment,
230 node
231 );
232 }
233 }
234
235}
236
237/**
238 * Updates the current segment with empty.
239 * This is called at the last of functions or the program.
240 * @param {CodePathAnalyzer} analyzer The instance.
241 * @param {ASTNode} node The current AST node.
242 * @returns {void}
243 */
244function leaveFromCurrentSegment(analyzer, node) {
245 const state = CodePath.getState(analyzer.codePath);
246 const currentSegments = state.currentSegments;
247
248 for (let i = 0; i < currentSegments.length; ++i) {
249 const currentSegment = currentSegments[i];
250 const eventName = currentSegment.reachable
251 ? "onCodePathSegmentEnd"
252 : "onUnreachableCodePathSegmentEnd";
253
254 debug.dump(`${eventName} ${currentSegment.id}`);
255
256 analyzer.emitter.emit(
257 eventName,
258 currentSegment,
259 node
260 );
261 }
262
263 state.currentSegments = [];
264}
265
266/**
267 * Updates the code path due to the position of a given node in the parent node
268 * thereof.
269 *
270 * For example, if the node is `parent.consequent`, this creates a fork from the
271 * current path.
272 * @param {CodePathAnalyzer} analyzer The instance.
273 * @param {ASTNode} node The current AST node.
274 * @returns {void}
275 */
276function preprocess(analyzer, node) {
277 const codePath = analyzer.codePath;
278 const state = CodePath.getState(codePath);
279 const parent = node.parent;
280
281 switch (parent.type) {
282
283 // The `arguments.length == 0` case is in `postprocess` function.
284 case "CallExpression":
285 if (parent.optional === true && parent.arguments.length >= 1 && parent.arguments[0] === node) {
286 state.makeOptionalRight();
287 }
288 break;
289 case "MemberExpression":
290 if (parent.optional === true && parent.property === node) {
291 state.makeOptionalRight();
292 }
293 break;
294
295 case "LogicalExpression":
296 if (
297 parent.right === node &&
298 isHandledLogicalOperator(parent.operator)
299 ) {
300 state.makeLogicalRight();
301 }
302 break;
303
304 case "AssignmentExpression":
305 if (
306 parent.right === node &&
307 isLogicalAssignmentOperator(parent.operator)
308 ) {
309 state.makeLogicalRight();
310 }
311 break;
312
313 case "ConditionalExpression":
314 case "IfStatement":
315
316 /*
317 * Fork if this node is at `consequent`/`alternate`.
318 * `popForkContext()` exists at `IfStatement:exit` and
319 * `ConditionalExpression:exit`.
320 */
321 if (parent.consequent === node) {
322 state.makeIfConsequent();
323 } else if (parent.alternate === node) {
324 state.makeIfAlternate();
325 }
326 break;
327
328 case "SwitchCase":
329 if (parent.consequent[0] === node) {
330 state.makeSwitchCaseBody(false, !parent.test);
331 }
332 break;
333
334 case "TryStatement":
335 if (parent.handler === node) {
336 state.makeCatchBlock();
337 } else if (parent.finalizer === node) {
338 state.makeFinallyBlock();
339 }
340 break;
341
342 case "WhileStatement":
343 if (parent.test === node) {
344 state.makeWhileTest(getBooleanValueIfSimpleConstant(node));
345 } else {
346 assert(parent.body === node);
347 state.makeWhileBody();
348 }
349 break;
350
351 case "DoWhileStatement":
352 if (parent.body === node) {
353 state.makeDoWhileBody();
354 } else {
355 assert(parent.test === node);
356 state.makeDoWhileTest(getBooleanValueIfSimpleConstant(node));
357 }
358 break;
359
360 case "ForStatement":
361 if (parent.test === node) {
362 state.makeForTest(getBooleanValueIfSimpleConstant(node));
363 } else if (parent.update === node) {
364 state.makeForUpdate();
365 } else if (parent.body === node) {
366 state.makeForBody();
367 }
368 break;
369
370 case "ForInStatement":
371 case "ForOfStatement":
372 if (parent.left === node) {
373 state.makeForInOfLeft();
374 } else if (parent.right === node) {
375 state.makeForInOfRight();
376 } else {
377 assert(parent.body === node);
378 state.makeForInOfBody();
379 }
380 break;
381
382 case "AssignmentPattern":
383
384 /*
385 * Fork if this node is at `right`.
386 * `left` is executed always, so it uses the current path.
387 * `popForkContext()` exists at `AssignmentPattern:exit`.
388 */
389 if (parent.right === node) {
390 state.pushForkContext();
391 state.forkBypassPath();
392 state.forkPath();
393 }
394 break;
395
396 default:
397 break;
398 }
399}
400
401/**
402 * Updates the code path due to the type of a given node in entering.
403 * @param {CodePathAnalyzer} analyzer The instance.
404 * @param {ASTNode} node The current AST node.
405 * @returns {void}
406 */
407function processCodePathToEnter(analyzer, node) {
408 let codePath = analyzer.codePath;
409 let state = codePath && CodePath.getState(codePath);
410 const parent = node.parent;
411
412 /**
413 * Creates a new code path and trigger the onCodePathStart event
414 * based on the currently selected node.
415 * @param {string} origin The reason the code path was started.
416 * @returns {void}
417 */
418 function startCodePath(origin) {
419 if (codePath) {
420
421 // Emits onCodePathSegmentStart events if updated.
422 forwardCurrentToHead(analyzer, node);
423 debug.dumpState(node, state, false);
424 }
425
426 // Create the code path of this scope.
427 codePath = analyzer.codePath = new CodePath({
428 id: analyzer.idGenerator.next(),
429 origin,
430 upper: codePath,
431 onLooped: analyzer.onLooped
432 });
433 state = CodePath.getState(codePath);
434
435 // Emits onCodePathStart events.
436 debug.dump(`onCodePathStart ${codePath.id}`);
437 analyzer.emitter.emit("onCodePathStart", codePath, node);
438 }
439
440 /*
441 * Special case: The right side of class field initializer is considered
442 * to be its own function, so we need to start a new code path in this
443 * case.
444 */
445 if (isPropertyDefinitionValue(node)) {
446 startCodePath("class-field-initializer");
447
448 /*
449 * Intentional fall through because `node` needs to also be
450 * processed by the code below. For example, if we have:
451 *
452 * class Foo {
453 * a = () => {}
454 * }
455 *
456 * In this case, we also need start a second code path.
457 */
458
459 }
460
461 switch (node.type) {
462 case "Program":
463 startCodePath("program");
464 break;
465
466 case "FunctionDeclaration":
467 case "FunctionExpression":
468 case "ArrowFunctionExpression":
469 startCodePath("function");
470 break;
471
472 case "StaticBlock":
473 startCodePath("class-static-block");
474 break;
475
476 case "ChainExpression":
477 state.pushChainContext();
478 break;
479 case "CallExpression":
480 if (node.optional === true) {
481 state.makeOptionalNode();
482 }
483 break;
484 case "MemberExpression":
485 if (node.optional === true) {
486 state.makeOptionalNode();
487 }
488 break;
489
490 case "LogicalExpression":
491 if (isHandledLogicalOperator(node.operator)) {
492 state.pushChoiceContext(
493 node.operator,
494 isForkingByTrueOrFalse(node)
495 );
496 }
497 break;
498
499 case "AssignmentExpression":
500 if (isLogicalAssignmentOperator(node.operator)) {
501 state.pushChoiceContext(
502 node.operator.slice(0, -1), // removes `=` from the end
503 isForkingByTrueOrFalse(node)
504 );
505 }
506 break;
507
508 case "ConditionalExpression":
509 case "IfStatement":
510 state.pushChoiceContext("test", false);
511 break;
512
513 case "SwitchStatement":
514 state.pushSwitchContext(
515 node.cases.some(isCaseNode),
516 getLabel(node)
517 );
518 break;
519
520 case "TryStatement":
521 state.pushTryContext(Boolean(node.finalizer));
522 break;
523
524 case "SwitchCase":
525
526 /*
527 * Fork if this node is after the 2st node in `cases`.
528 * It's similar to `else` blocks.
529 * The next `test` node is processed in this path.
530 */
531 if (parent.discriminant !== node && parent.cases[0] !== node) {
532 state.forkPath();
533 }
534 break;
535
536 case "WhileStatement":
537 case "DoWhileStatement":
538 case "ForStatement":
539 case "ForInStatement":
540 case "ForOfStatement":
541 state.pushLoopContext(node.type, getLabel(node));
542 break;
543
544 case "LabeledStatement":
545 if (!breakableTypePattern.test(node.body.type)) {
546 state.pushBreakContext(false, node.label.name);
547 }
548 break;
549
550 default:
551 break;
552 }
553
554 // Emits onCodePathSegmentStart events if updated.
555 forwardCurrentToHead(analyzer, node);
556 debug.dumpState(node, state, false);
557}
558
559/**
560 * Updates the code path due to the type of a given node in leaving.
561 * @param {CodePathAnalyzer} analyzer The instance.
562 * @param {ASTNode} node The current AST node.
563 * @returns {void}
564 */
565function processCodePathToExit(analyzer, node) {
566
567 const codePath = analyzer.codePath;
568 const state = CodePath.getState(codePath);
569 let dontForward = false;
570
571 switch (node.type) {
572 case "ChainExpression":
573 state.popChainContext();
574 break;
575
576 case "IfStatement":
577 case "ConditionalExpression":
578 state.popChoiceContext();
579 break;
580
581 case "LogicalExpression":
582 if (isHandledLogicalOperator(node.operator)) {
583 state.popChoiceContext();
584 }
585 break;
586
587 case "AssignmentExpression":
588 if (isLogicalAssignmentOperator(node.operator)) {
589 state.popChoiceContext();
590 }
591 break;
592
593 case "SwitchStatement":
594 state.popSwitchContext();
595 break;
596
597 case "SwitchCase":
598
599 /*
600 * This is the same as the process at the 1st `consequent` node in
601 * `preprocess` function.
602 * Must do if this `consequent` is empty.
603 */
604 if (node.consequent.length === 0) {
605 state.makeSwitchCaseBody(true, !node.test);
606 }
607 if (state.forkContext.reachable) {
608 dontForward = true;
609 }
610 break;
611
612 case "TryStatement":
613 state.popTryContext();
614 break;
615
616 case "BreakStatement":
617 forwardCurrentToHead(analyzer, node);
618 state.makeBreak(node.label && node.label.name);
619 dontForward = true;
620 break;
621
622 case "ContinueStatement":
623 forwardCurrentToHead(analyzer, node);
624 state.makeContinue(node.label && node.label.name);
625 dontForward = true;
626 break;
627
628 case "ReturnStatement":
629 forwardCurrentToHead(analyzer, node);
630 state.makeReturn();
631 dontForward = true;
632 break;
633
634 case "ThrowStatement":
635 forwardCurrentToHead(analyzer, node);
636 state.makeThrow();
637 dontForward = true;
638 break;
639
640 case "Identifier":
641 if (isIdentifierReference(node)) {
642 state.makeFirstThrowablePathInTryBlock();
643 dontForward = true;
644 }
645 break;
646
647 case "CallExpression":
648 case "ImportExpression":
649 case "MemberExpression":
650 case "NewExpression":
651 case "YieldExpression":
652 state.makeFirstThrowablePathInTryBlock();
653 break;
654
655 case "WhileStatement":
656 case "DoWhileStatement":
657 case "ForStatement":
658 case "ForInStatement":
659 case "ForOfStatement":
660 state.popLoopContext();
661 break;
662
663 case "AssignmentPattern":
664 state.popForkContext();
665 break;
666
667 case "LabeledStatement":
668 if (!breakableTypePattern.test(node.body.type)) {
669 state.popBreakContext();
670 }
671 break;
672
673 default:
674 break;
675 }
676
677 // Emits onCodePathSegmentStart events if updated.
678 if (!dontForward) {
679 forwardCurrentToHead(analyzer, node);
680 }
681 debug.dumpState(node, state, true);
682}
683
684/**
685 * Updates the code path to finalize the current code path.
686 * @param {CodePathAnalyzer} analyzer The instance.
687 * @param {ASTNode} node The current AST node.
688 * @returns {void}
689 */
690function postprocess(analyzer, node) {
691
692 /**
693 * Ends the code path for the current node.
694 * @returns {void}
695 */
696 function endCodePath() {
697 let codePath = analyzer.codePath;
698
699 // Mark the current path as the final node.
700 CodePath.getState(codePath).makeFinal();
701
702 // Emits onCodePathSegmentEnd event of the current segments.
703 leaveFromCurrentSegment(analyzer, node);
704
705 // Emits onCodePathEnd event of this code path.
706 debug.dump(`onCodePathEnd ${codePath.id}`);
707 analyzer.emitter.emit("onCodePathEnd", codePath, node);
708 debug.dumpDot(codePath);
709
710 codePath = analyzer.codePath = analyzer.codePath.upper;
711 if (codePath) {
712 debug.dumpState(node, CodePath.getState(codePath), true);
713 }
714
715 }
716
717 switch (node.type) {
718 case "Program":
719 case "FunctionDeclaration":
720 case "FunctionExpression":
721 case "ArrowFunctionExpression":
722 case "StaticBlock": {
723 endCodePath();
724 break;
725 }
726
727 // The `arguments.length >= 1` case is in `preprocess` function.
728 case "CallExpression":
729 if (node.optional === true && node.arguments.length === 0) {
730 CodePath.getState(analyzer.codePath).makeOptionalRight();
731 }
732 break;
733
734 default:
735 break;
736 }
737
738 /*
739 * Special case: The right side of class field initializer is considered
740 * to be its own function, so we need to end a code path in this
741 * case.
742 *
743 * We need to check after the other checks in order to close the
744 * code paths in the correct order for code like this:
745 *
746 *
747 * class Foo {
748 * a = () => {}
749 * }
750 *
751 * In this case, The ArrowFunctionExpression code path is closed first
752 * and then we need to close the code path for the PropertyDefinition
753 * value.
754 */
755 if (isPropertyDefinitionValue(node)) {
756 endCodePath();
757 }
758}
759
760//------------------------------------------------------------------------------
761// Public Interface
762//------------------------------------------------------------------------------
763
764/**
765 * The class to analyze code paths.
766 * This class implements the EventGenerator interface.
767 */
768class CodePathAnalyzer {
769
770 /**
771 * @param {EventGenerator} eventGenerator An event generator to wrap.
772 */
773 constructor(eventGenerator) {
774 this.original = eventGenerator;
775 this.emitter = eventGenerator.emitter;
776 this.codePath = null;
777 this.idGenerator = new IdGenerator("s");
778 this.currentNode = null;
779 this.onLooped = this.onLooped.bind(this);
780 }
781
782 /**
783 * Does the process to enter a given AST node.
784 * This updates state of analysis and calls `enterNode` of the wrapped.
785 * @param {ASTNode} node A node which is entering.
786 * @returns {void}
787 */
788 enterNode(node) {
789 this.currentNode = node;
790
791 // Updates the code path due to node's position in its parent node.
792 if (node.parent) {
793 preprocess(this, node);
794 }
795
796 /*
797 * Updates the code path.
798 * And emits onCodePathStart/onCodePathSegmentStart events.
799 */
800 processCodePathToEnter(this, node);
801
802 // Emits node events.
803 this.original.enterNode(node);
804
805 this.currentNode = null;
806 }
807
808 /**
809 * Does the process to leave a given AST node.
810 * This updates state of analysis and calls `leaveNode` of the wrapped.
811 * @param {ASTNode} node A node which is leaving.
812 * @returns {void}
813 */
814 leaveNode(node) {
815 this.currentNode = node;
816
817 /*
818 * Updates the code path.
819 * And emits onCodePathStart/onCodePathSegmentStart events.
820 */
821 processCodePathToExit(this, node);
822
823 // Emits node events.
824 this.original.leaveNode(node);
825
826 // Emits the last onCodePathStart/onCodePathSegmentStart events.
827 postprocess(this, node);
828
829 this.currentNode = null;
830 }
831
832 /**
833 * This is called on a code path looped.
834 * Then this raises a looped event.
835 * @param {CodePathSegment} fromSegment A segment of prev.
836 * @param {CodePathSegment} toSegment A segment of next.
837 * @returns {void}
838 */
839 onLooped(fromSegment, toSegment) {
840 if (fromSegment.reachable && toSegment.reachable) {
841 debug.dump(`onCodePathSegmentLoop ${fromSegment.id} -> ${toSegment.id}`);
842 this.emitter.emit(
843 "onCodePathSegmentLoop",
844 fromSegment,
845 toSegment,
846 this.currentNode
847 );
848 }
849 }
850}
851
852module.exports = CodePathAnalyzer;
Note: See TracBrowser for help on using the repository browser.