.config/coc/extensions/node_modules/coc-prettier/node_modules/eslint/lib/linter/code-path-analysis/code-path-analyzer.js

   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
  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");
  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  */
  28 function isCaseNode(node) {
  29     return Boolean(node.test);
  30 }
  31
  32 /**
  33  * Checks whether the given logical operator is taken into account for the code
  34  * path analysis.
  35  * @param {string} operator The operator found in the LogicalExpression node
  36  * @returns {boolean} `true` if the operator is "&&" or "||" or "??"
  37  */
  38 function isHandledLogicalOperator(operator) {
  39     return operator === "&&" || operator === "||" || operator === "??";
  40 }
  41
  42 /**
  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 "??="
  48  */
  49 function isLogicalAssignmentOperator(operator) {
  50     return operator === "&&=" || operator === "||=" || operator === "??=";
  51 }
  52
  53 /**
  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`.
  57  */
  58 function getLabel(node) {
  59     if (node.parent.type === "LabeledStatement") {
  60         return node.parent.label.name;
  61     }
  62     return null;
  63 }
  64
  65 /**
  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.
  70  */
  71 function isForkingByTrueOrFalse(node) {
  72     const parent = node.parent;
  73
  74     switch (parent.type) {
  75         case "ConditionalExpression":
  76         case "IfStatement":
  77         case "WhileStatement":
  78         case "DoWhileStatement":
  79         case "ForStatement":
  80             return parent.test === node;
  81
  82         case "LogicalExpression":
  83             return isHandledLogicalOperator(parent.operator);
  84
  85         case "AssignmentExpression":
  86             return isLogicalAssignmentOperator(parent.operator);
  87
  88         default:
  89             return false;
  90     }
  91 }
  92
  93 /**
  94  * Gets the boolean value of a given literal node.
  95  *
  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`.
 102  */
 103 function getBooleanValueIfSimpleConstant(node) {
 104     if (node.type === "Literal") {
 105         return Boolean(node.value);
 106     }
 107     return void 0;
 108 }
 109
 110 /**
 111  * Checks that a given identifier node is a reference or not.
 112  *
 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.
 116  */
 117 function isIdentifierReference(node) {
 118     const parent = node.parent;
 119
 120     switch (parent.type) {
 121         case "LabeledStatement":
 122         case "BreakStatement":
 123         case "ContinueStatement":
 124         case "ArrayPattern":
 125         case "RestElement":
 126         case "ImportSpecifier":
 127         case "ImportDefaultSpecifier":
 128         case "ImportNamespaceSpecifier":
 129         case "CatchClause":
 130             return false;
 131
 132         case "FunctionDeclaration":
 133         case "FunctionExpression":
 134         case "ArrowFunctionExpression":
 135         case "ClassDeclaration":
 136         case "ClassExpression":
 137         case "VariableDeclarator":
 138             return parent.id !== node;
 139
 140         case "Property":
 141         case "MethodDefinition":
 142             return (
 143                 parent.key !== node ||
 144                 parent.computed ||
 145                 parent.shorthand
 146             );
 147
 148         case "AssignmentPattern":
 149             return parent.key !== node;
 150
 151         default:
 152             return true;
 153     }
 154 }
 155
 156 /**
 157  * Updates the current segment with the head segment.
 158  * This is similar to local branches and tracking branches of git.
 159  *
 160  * To separate the current and the head is in order to not make useless segments.
 161  *
 162  * In this process, both "onCodePathSegmentStart" and "onCodePathSegmentEnd"
 163  * events are fired.
 164  * @param {CodePathAnalyzer} analyzer The instance.
 165  * @param {ASTNode} node The current AST node.
 166  * @returns {void}
 167  */
 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;
 175
 176     // Fires leaving events.
 177     for (i = 0; i < end; ++i) {
 178         currentSegment = currentSegments[i];
 179         headSegment = headSegments[i];
 180
 181         if (currentSegment !== headSegment && currentSegment) {
 182             debug.dump(`onCodePathSegmentEnd ${currentSegment.id}`);
 183
 184             if (currentSegment.reachable) {
 185                 analyzer.emitter.emit(
 186                     "onCodePathSegmentEnd",
 187                     currentSegment,
 188                     node
 189                 );
 190             }
 191         }
 192     }
 193
 194     // Update state.
 195     state.currentSegments = headSegments;
 196
 197     // Fires entering events.
 198     for (i = 0; i < end; ++i) {
 199         currentSegment = currentSegments[i];
 200         headSegment = headSegments[i];
 201
 202         if (currentSegment !== headSegment && headSegment) {
 203             debug.dump(`onCodePathSegmentStart ${headSegment.id}`);
 204
 205             CodePathSegment.markUsed(headSegment);
 206             if (headSegment.reachable) {
 207                 analyzer.emitter.emit(
 208                     "onCodePathSegmentStart",
 209                     headSegment,
 210                     node
 211                 );
 212             }
 213         }
 214     }
 215
 216 }
 217
 218 /**
 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.
 223  * @returns {void}
 224  */
 225 function leaveFromCurrentSegment(analyzer, node) {
 226     const state = CodePath.getState(analyzer.codePath);
 227     const currentSegments = state.currentSegments;
 228
 229     for (let i = 0; i < currentSegments.length; ++i) {
 230         const currentSegment = currentSegments[i];
 231
 232         debug.dump(`onCodePathSegmentEnd ${currentSegment.id}`);
 233         if (currentSegment.reachable) {
 234             analyzer.emitter.emit(
 235                 "onCodePathSegmentEnd",
 236                 currentSegment,
 237                 node
 238             );
 239         }
 240     }
 241
 242     state.currentSegments = [];
 243 }
 244
 245 /**
 246  * Updates the code path due to the position of a given node in the parent node
 247  * thereof.
 248  *
 249  * For example, if the node is `parent.consequent`, this creates a fork from the
 250  * current path.
 251  * @param {CodePathAnalyzer} analyzer The instance.
 252  * @param {ASTNode} node The current AST node.
 253  * @returns {void}
 254  */
 255 function preprocess(analyzer, node) {
 256     const codePath = analyzer.codePath;
 257     const state = CodePath.getState(codePath);
 258     const parent = node.parent;
 259
 260     switch (parent.type) {
 261
 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();
 266             }
 267             break;
 268         case "MemberExpression":
 269             if (parent.optional === true && parent.property === node) {
 270                 state.makeOptionalRight();
 271             }
 272             break;
 273
 274         case "LogicalExpression":
 275             if (
 276                 parent.right === node &&
 277                 isHandledLogicalOperator(parent.operator)
 278             ) {
 279                 state.makeLogicalRight();
 280             }
 281             break;
 282
 283         case "AssignmentExpression":
 284             if (
 285                 parent.right === node &&
 286                 isLogicalAssignmentOperator(parent.operator)
 287             ) {
 288                 state.makeLogicalRight();
 289             }
 290             break;
 291
 292         case "ConditionalExpression":
 293         case "IfStatement":
 294
 295             /*
 296              * Fork if this node is at `consequent`/`alternate`.
 297              * `popForkContext()` exists at `IfStatement:exit` and
 298              * `ConditionalExpression:exit`.
 299              */
 300             if (parent.consequent === node) {
 301                 state.makeIfConsequent();
 302             } else if (parent.alternate === node) {
 303                 state.makeIfAlternate();
 304             }
 305             break;
 306
 307         case "SwitchCase":
 308             if (parent.consequent[0] === node) {
 309                 state.makeSwitchCaseBody(false, !parent.test);
 310             }
 311             break;
 312
 313         case "TryStatement":
 314             if (parent.handler === node) {
 315                 state.makeCatchBlock();
 316             } else if (parent.finalizer === node) {
 317                 state.makeFinallyBlock();
 318             }
 319             break;
 320
 321         case "WhileStatement":
 322             if (parent.test === node) {
 323                 state.makeWhileTest(getBooleanValueIfSimpleConstant(node));
 324             } else {
 325                 assert(parent.body === node);
 326                 state.makeWhileBody();
 327             }
 328             break;
 329
 330         case "DoWhileStatement":
 331             if (parent.body === node) {
 332                 state.makeDoWhileBody();
 333             } else {
 334                 assert(parent.test === node);
 335                 state.makeDoWhileTest(getBooleanValueIfSimpleConstant(node));
 336             }
 337             break;
 338
 339         case "ForStatement":
 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) {
 345                 state.makeForBody();
 346             }
 347             break;
 348
 349         case "ForInStatement":
 350         case "ForOfStatement":
 351             if (parent.left === node) {
 352                 state.makeForInOfLeft();
 353             } else if (parent.right === node) {
 354                 state.makeForInOfRight();
 355             } else {
 356                 assert(parent.body === node);
 357                 state.makeForInOfBody();
 358             }
 359             break;
 360
 361         case "AssignmentPattern":
 362
 363             /*
 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`.
 367              */
 368             if (parent.right === node) {
 369                 state.pushForkContext();
 370                 state.forkBypassPath();
 371                 state.forkPath();
 372             }
 373             break;
 374
 375         default:
 376             break;
 377     }
 378 }
 379
 380 /**
 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.
 384  * @returns {void}
 385  */
 386 function processCodePathToEnter(analyzer, node) {
 387     let codePath = analyzer.codePath;
 388     let state = codePath && CodePath.getState(codePath);
 389     const parent = node.parent;
 390
 391     switch (node.type) {
 392         case "Program":
 393         case "FunctionDeclaration":
 394         case "FunctionExpression":
 395         case "ArrowFunctionExpression":
 396             if (codePath) {
 397
 398                 // Emits onCodePathSegmentStart events if updated.
 399                 forwardCurrentToHead(analyzer, node);
 400                 debug.dumpState(node, state, false);
 401             }
 402
 403             // Create the code path of this scope.
 404             codePath = analyzer.codePath = new CodePath(
 405                 analyzer.idGenerator.next(),
 406                 codePath,
 407                 analyzer.onLooped
 408             );
 409             state = CodePath.getState(codePath);
 410
 411             // Emits onCodePathStart events.
 412             debug.dump(`onCodePathStart ${codePath.id}`);
 413             analyzer.emitter.emit("onCodePathStart", codePath, node);
 414             break;
 415
 416         case "ChainExpression":
 417             state.pushChainContext();
 418             break;
 419         case "CallExpression":
 420             if (node.optional === true) {
 421                 state.makeOptionalNode();
 422             }
 423             break;
 424         case "MemberExpression":
 425             if (node.optional === true) {
 426                 state.makeOptionalNode();
 427             }
 428             break;
 429
 430         case "LogicalExpression":
 431             if (isHandledLogicalOperator(node.operator)) {
 432                 state.pushChoiceContext(
 433                     node.operator,
 434                     isForkingByTrueOrFalse(node)
 435                 );
 436             }
 437             break;
 438
 439         case "AssignmentExpression":
 440             if (isLogicalAssignmentOperator(node.operator)) {
 441                 state.pushChoiceContext(
 442                     node.operator.slice(0, -1), // removes `=` from the end
 443                     isForkingByTrueOrFalse(node)
 444                 );
 445             }
 446             break;
 447
 448         case "ConditionalExpression":
 449         case "IfStatement":
 450             state.pushChoiceContext("test", false);
 451             break;
 452
 453         case "SwitchStatement":
 454             state.pushSwitchContext(
 455                 node.cases.some(isCaseNode),
 456                 getLabel(node)
 457             );
 458             break;
 459
 460         case "TryStatement":
 461             state.pushTryContext(Boolean(node.finalizer));
 462             break;
 463
 464         case "SwitchCase":
 465
 466             /*
 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.
 470              */
 471             if (parent.discriminant !== node && parent.cases[0] !== node) {
 472                 state.forkPath();
 473             }
 474             break;
 475
 476         case "WhileStatement":
 477         case "DoWhileStatement":
 478         case "ForStatement":
 479         case "ForInStatement":
 480         case "ForOfStatement":
 481             state.pushLoopContext(node.type, getLabel(node));
 482             break;
 483
 484         case "LabeledStatement":
 485             if (!breakableTypePattern.test(node.body.type)) {
 486                 state.pushBreakContext(false, node.label.name);
 487             }
 488             break;
 489
 490         default:
 491             break;
 492     }
 493
 494     // Emits onCodePathSegmentStart events if updated.
 495     forwardCurrentToHead(analyzer, node);
 496     debug.dumpState(node, state, false);
 497 }
 498
 499 /**
 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.
 503  * @returns {void}
 504  */
 505 function processCodePathToExit(analyzer, node) {
 506     const codePath = analyzer.codePath;
 507     const state = CodePath.getState(codePath);
 508     let dontForward = false;
 509
 510     switch (node.type) {
 511         case "ChainExpression":
 512             state.popChainContext();
 513             break;
 514
 515         case "IfStatement":
 516         case "ConditionalExpression":
 517             state.popChoiceContext();
 518             break;
 519
 520         case "LogicalExpression":
 521             if (isHandledLogicalOperator(node.operator)) {
 522                 state.popChoiceContext();
 523             }
 524             break;
 525
 526         case "AssignmentExpression":
 527             if (isLogicalAssignmentOperator(node.operator)) {
 528                 state.popChoiceContext();
 529             }
 530             break;
 531
 532         case "SwitchStatement":
 533             state.popSwitchContext();
 534             break;
 535
 536         case "SwitchCase":
 537
 538             /*
 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.
 542              */
 543             if (node.consequent.length === 0) {
 544                 state.makeSwitchCaseBody(true, !node.test);
 545             }
 546             if (state.forkContext.reachable) {
 547                 dontForward = true;
 548             }
 549             break;
 550
 551         case "TryStatement":
 552             state.popTryContext();
 553             break;
 554
 555         case "BreakStatement":
 556             forwardCurrentToHead(analyzer, node);
 557             state.makeBreak(node.label && node.label.name);
 558             dontForward = true;
 559             break;
 560
 561         case "ContinueStatement":
 562             forwardCurrentToHead(analyzer, node);
 563             state.makeContinue(node.label && node.label.name);
 564             dontForward = true;
 565             break;
 566
 567         case "ReturnStatement":
 568             forwardCurrentToHead(analyzer, node);
 569             state.makeReturn();
 570             dontForward = true;
 571             break;
 572
 573         case "ThrowStatement":
 574             forwardCurrentToHead(analyzer, node);
 575             state.makeThrow();
 576             dontForward = true;
 577             break;
 578
 579         case "Identifier":
 580             if (isIdentifierReference(node)) {
 581                 state.makeFirstThrowablePathInTryBlock();
 582                 dontForward = true;
 583             }
 584             break;
 585
 586         case "CallExpression":
 587         case "ImportExpression":
 588         case "MemberExpression":
 589         case "NewExpression":
 590         case "YieldExpression":
 591             state.makeFirstThrowablePathInTryBlock();
 592             break;
 593
 594         case "WhileStatement":
 595         case "DoWhileStatement":
 596         case "ForStatement":
 597         case "ForInStatement":
 598         case "ForOfStatement":
 599             state.popLoopContext();
 600             break;
 601
 602         case "AssignmentPattern":
 603             state.popForkContext();
 604             break;
 605
 606         case "LabeledStatement":
 607             if (!breakableTypePattern.test(node.body.type)) {
 608                 state.popBreakContext();
 609             }
 610             break;
 611
 612         default:
 613             break;
 614     }
 615
 616     // Emits onCodePathSegmentStart events if updated.
 617     if (!dontForward) {
 618         forwardCurrentToHead(analyzer, node);
 619     }
 620     debug.dumpState(node, state, true);
 621 }
 622
 623 /**
 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.
 627  * @returns {void}
 628  */
 629 function postprocess(analyzer, node) {
 630     switch (node.type) {
 631         case "Program":
 632         case "FunctionDeclaration":
 633         case "FunctionExpression":
 634         case "ArrowFunctionExpression": {
 635             let codePath = analyzer.codePath;
 636
 637             // Mark the current path as the final node.
 638             CodePath.getState(codePath).makeFinal();
 639
 640             // Emits onCodePathSegmentEnd event of the current segments.
 641             leaveFromCurrentSegment(analyzer, node);
 642
 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);
 647
 648             codePath = analyzer.codePath = analyzer.codePath.upper;
 649             if (codePath) {
 650                 debug.dumpState(node, CodePath.getState(codePath), true);
 651             }
 652             break;
 653         }
 654
 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();
 659             }
 660             break;
 661
 662         default:
 663             break;
 664     }
 665 }
 666
 667 //------------------------------------------------------------------------------
 668 // Public Interface
 669 //------------------------------------------------------------------------------
 670
 671 /**
 672  * The class to analyze code paths.
 673  * This class implements the EventGenerator interface.
 674  */
 675 class CodePathAnalyzer {
 676
 677     // eslint-disable-next-line jsdoc/require-description
 678     /**
 679      * @param {EventGenerator} eventGenerator An event generator to wrap.
 680      */
 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);
 688     }
 689
 690     /**
 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.
 694      * @returns {void}
 695      */
 696     enterNode(node) {
 697         this.currentNode = node;
 698
 699         // Updates the code path due to node's position in its parent node.
 700         if (node.parent) {
 701             preprocess(this, node);
 702         }
 703
 704         /*
 705          * Updates the code path.
 706          * And emits onCodePathStart/onCodePathSegmentStart events.
 707          */
 708         processCodePathToEnter(this, node);
 709
 710         // Emits node events.
 711         this.original.enterNode(node);
 712
 713         this.currentNode = null;
 714     }
 715
 716     /**
 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.
 720      * @returns {void}
 721      */
 722     leaveNode(node) {
 723         this.currentNode = node;
 724
 725         /*
 726          * Updates the code path.
 727          * And emits onCodePathStart/onCodePathSegmentStart events.
 728          */
 729         processCodePathToExit(this, node);
 730
 731         // Emits node events.
 732         this.original.leaveNode(node);
 733
 734         // Emits the last onCodePathStart/onCodePathSegmentStart events.
 735         postprocess(this, node);
 736
 737         this.currentNode = null;
 738     }
 739
 740     /**
 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.
 745      * @returns {void}
 746      */
 747     onLooped(fromSegment, toSegment) {
 748         if (fromSegment.reachable && toSegment.reachable) {
 749             debug.dump(`onCodePathSegmentLoop ${fromSegment.id} -> ${toSegment.id}`);
 750             this.emitter.emit(
 751                 "onCodePathSegmentLoop",
 752                 fromSegment,
 753                 toSegment,
 754                 this.currentNode
 755             );
 756         }
 757     }
 758 }
 759
 760 module.exports = CodePathAnalyzer;