.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 "||"
  37  */
  38 function isHandledLogicalOperator(operator) {
  39     return operator === "&&" || operator === "||";
  40 }
  41
  42 /**
  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`.
  46  */
  47 function getLabel(node) {
  48     if (node.parent.type === "LabeledStatement") {
  49         return node.parent.label.name;
  50     }
  51     return null;
  52 }
  53
  54 /**
  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.
  59  */
  60 function isForkingByTrueOrFalse(node) {
  61     const parent = node.parent;
  62
  63     switch (parent.type) {
  64         case "ConditionalExpression":
  65         case "IfStatement":
  66         case "WhileStatement":
  67         case "DoWhileStatement":
  68         case "ForStatement":
  69             return parent.test === node;
  70
  71         case "LogicalExpression":
  72             return isHandledLogicalOperator(parent.operator);
  73
  74         default:
  75             return false;
  76     }
  77 }
  78
  79 /**
  80  * Gets the boolean value of a given literal node.
  81  *
  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`.
  88  */
  89 function getBooleanValueIfSimpleConstant(node) {
  90     if (node.type === "Literal") {
  91         return Boolean(node.value);
  92     }
  93     return void 0;
  94 }
  95
  96 /**
  97  * Checks that a given identifier node is a reference or not.
  98  *
  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.
 102  */
 103 function isIdentifierReference(node) {
 104     const parent = node.parent;
 105
 106     switch (parent.type) {
 107         case "LabeledStatement":
 108         case "BreakStatement":
 109         case "ContinueStatement":
 110         case "ArrayPattern":
 111         case "RestElement":
 112         case "ImportSpecifier":
 113         case "ImportDefaultSpecifier":
 114         case "ImportNamespaceSpecifier":
 115         case "CatchClause":
 116             return false;
 117
 118         case "FunctionDeclaration":
 119         case "FunctionExpression":
 120         case "ArrowFunctionExpression":
 121         case "ClassDeclaration":
 122         case "ClassExpression":
 123         case "VariableDeclarator":
 124             return parent.id !== node;
 125
 126         case "Property":
 127         case "MethodDefinition":
 128             return (
 129                 parent.key !== node ||
 130                 parent.computed ||
 131                 parent.shorthand
 132             );
 133
 134         case "AssignmentPattern":
 135             return parent.key !== node;
 136
 137         default:
 138             return true;
 139     }
 140 }
 141
 142 /**
 143  * Updates the current segment with the head segment.
 144  * This is similar to local branches and tracking branches of git.
 145  *
 146  * To separate the current and the head is in order to not make useless segments.
 147  *
 148  * In this process, both "onCodePathSegmentStart" and "onCodePathSegmentEnd"
 149  * events are fired.
 150  * @param {CodePathAnalyzer} analyzer The instance.
 151  * @param {ASTNode} node The current AST node.
 152  * @returns {void}
 153  */
 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;
 161
 162     // Fires leaving events.
 163     for (i = 0; i < end; ++i) {
 164         currentSegment = currentSegments[i];
 165         headSegment = headSegments[i];
 166
 167         if (currentSegment !== headSegment && currentSegment) {
 168             debug.dump(`onCodePathSegmentEnd ${currentSegment.id}`);
 169
 170             if (currentSegment.reachable) {
 171                 analyzer.emitter.emit(
 172                     "onCodePathSegmentEnd",
 173                     currentSegment,
 174                     node
 175                 );
 176             }
 177         }
 178     }
 179
 180     // Update state.
 181     state.currentSegments = headSegments;
 182
 183     // Fires entering events.
 184     for (i = 0; i < end; ++i) {
 185         currentSegment = currentSegments[i];
 186         headSegment = headSegments[i];
 187
 188         if (currentSegment !== headSegment && headSegment) {
 189             debug.dump(`onCodePathSegmentStart ${headSegment.id}`);
 190
 191             CodePathSegment.markUsed(headSegment);
 192             if (headSegment.reachable) {
 193                 analyzer.emitter.emit(
 194                     "onCodePathSegmentStart",
 195                     headSegment,
 196                     node
 197                 );
 198             }
 199         }
 200     }
 201
 202 }
 203
 204 /**
 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.
 209  * @returns {void}
 210  */
 211 function leaveFromCurrentSegment(analyzer, node) {
 212     const state = CodePath.getState(analyzer.codePath);
 213     const currentSegments = state.currentSegments;
 214
 215     for (let i = 0; i < currentSegments.length; ++i) {
 216         const currentSegment = currentSegments[i];
 217
 218         debug.dump(`onCodePathSegmentEnd ${currentSegment.id}`);
 219         if (currentSegment.reachable) {
 220             analyzer.emitter.emit(
 221                 "onCodePathSegmentEnd",
 222                 currentSegment,
 223                 node
 224             );
 225         }
 226     }
 227
 228     state.currentSegments = [];
 229 }
 230
 231 /**
 232  * Updates the code path due to the position of a given node in the parent node
 233  * thereof.
 234  *
 235  * For example, if the node is `parent.consequent`, this creates a fork from the
 236  * current path.
 237  * @param {CodePathAnalyzer} analyzer The instance.
 238  * @param {ASTNode} node The current AST node.
 239  * @returns {void}
 240  */
 241 function preprocess(analyzer, node) {
 242     const codePath = analyzer.codePath;
 243     const state = CodePath.getState(codePath);
 244     const parent = node.parent;
 245
 246     switch (parent.type) {
 247         case "LogicalExpression":
 248             if (
 249                 parent.right === node &&
 250                 isHandledLogicalOperator(parent.operator)
 251             ) {
 252                 state.makeLogicalRight();
 253             }
 254             break;
 255
 256         case "ConditionalExpression":
 257         case "IfStatement":
 258
 259             /*
 260              * Fork if this node is at `consequent`/`alternate`.
 261              * `popForkContext()` exists at `IfStatement:exit` and
 262              * `ConditionalExpression:exit`.
 263              */
 264             if (parent.consequent === node) {
 265                 state.makeIfConsequent();
 266             } else if (parent.alternate === node) {
 267                 state.makeIfAlternate();
 268             }
 269             break;
 270
 271         case "SwitchCase":
 272             if (parent.consequent[0] === node) {
 273                 state.makeSwitchCaseBody(false, !parent.test);
 274             }
 275             break;
 276
 277         case "TryStatement":
 278             if (parent.handler === node) {
 279                 state.makeCatchBlock();
 280             } else if (parent.finalizer === node) {
 281                 state.makeFinallyBlock();
 282             }
 283             break;
 284
 285         case "WhileStatement":
 286             if (parent.test === node) {
 287                 state.makeWhileTest(getBooleanValueIfSimpleConstant(node));
 288             } else {
 289                 assert(parent.body === node);
 290                 state.makeWhileBody();
 291             }
 292             break;
 293
 294         case "DoWhileStatement":
 295             if (parent.body === node) {
 296                 state.makeDoWhileBody();
 297             } else {
 298                 assert(parent.test === node);
 299                 state.makeDoWhileTest(getBooleanValueIfSimpleConstant(node));
 300             }
 301             break;
 302
 303         case "ForStatement":
 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) {
 309                 state.makeForBody();
 310             }
 311             break;
 312
 313         case "ForInStatement":
 314         case "ForOfStatement":
 315             if (parent.left === node) {
 316                 state.makeForInOfLeft();
 317             } else if (parent.right === node) {
 318                 state.makeForInOfRight();
 319             } else {
 320                 assert(parent.body === node);
 321                 state.makeForInOfBody();
 322             }
 323             break;
 324
 325         case "AssignmentPattern":
 326
 327             /*
 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`.
 331              */
 332             if (parent.right === node) {
 333                 state.pushForkContext();
 334                 state.forkBypassPath();
 335                 state.forkPath();
 336             }
 337             break;
 338
 339         default:
 340             break;
 341     }
 342 }
 343
 344 /**
 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.
 348  * @returns {void}
 349  */
 350 function processCodePathToEnter(analyzer, node) {
 351     let codePath = analyzer.codePath;
 352     let state = codePath && CodePath.getState(codePath);
 353     const parent = node.parent;
 354
 355     switch (node.type) {
 356         case "Program":
 357         case "FunctionDeclaration":
 358         case "FunctionExpression":
 359         case "ArrowFunctionExpression":
 360             if (codePath) {
 361
 362                 // Emits onCodePathSegmentStart events if updated.
 363                 forwardCurrentToHead(analyzer, node);
 364                 debug.dumpState(node, state, false);
 365             }
 366
 367             // Create the code path of this scope.
 368             codePath = analyzer.codePath = new CodePath(
 369                 analyzer.idGenerator.next(),
 370                 codePath,
 371                 analyzer.onLooped
 372             );
 373             state = CodePath.getState(codePath);
 374
 375             // Emits onCodePathStart events.
 376             debug.dump(`onCodePathStart ${codePath.id}`);
 377             analyzer.emitter.emit("onCodePathStart", codePath, node);
 378             break;
 379
 380         case "LogicalExpression":
 381             if (isHandledLogicalOperator(node.operator)) {
 382                 state.pushChoiceContext(
 383                     node.operator,
 384                     isForkingByTrueOrFalse(node)
 385                 );
 386             }
 387             break;
 388
 389         case "ConditionalExpression":
 390         case "IfStatement":
 391             state.pushChoiceContext("test", false);
 392             break;
 393
 394         case "SwitchStatement":
 395             state.pushSwitchContext(
 396                 node.cases.some(isCaseNode),
 397                 getLabel(node)
 398             );
 399             break;
 400
 401         case "TryStatement":
 402             state.pushTryContext(Boolean(node.finalizer));
 403             break;
 404
 405         case "SwitchCase":
 406
 407             /*
 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.
 411              */
 412             if (parent.discriminant !== node && parent.cases[0] !== node) {
 413                 state.forkPath();
 414             }
 415             break;
 416
 417         case "WhileStatement":
 418         case "DoWhileStatement":
 419         case "ForStatement":
 420         case "ForInStatement":
 421         case "ForOfStatement":
 422             state.pushLoopContext(node.type, getLabel(node));
 423             break;
 424
 425         case "LabeledStatement":
 426             if (!breakableTypePattern.test(node.body.type)) {
 427                 state.pushBreakContext(false, node.label.name);
 428             }
 429             break;
 430
 431         default:
 432             break;
 433     }
 434
 435     // Emits onCodePathSegmentStart events if updated.
 436     forwardCurrentToHead(analyzer, node);
 437     debug.dumpState(node, state, false);
 438 }
 439
 440 /**
 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.
 444  * @returns {void}
 445  */
 446 function processCodePathToExit(analyzer, node) {
 447     const codePath = analyzer.codePath;
 448     const state = CodePath.getState(codePath);
 449     let dontForward = false;
 450
 451     switch (node.type) {
 452         case "IfStatement":
 453         case "ConditionalExpression":
 454             state.popChoiceContext();
 455             break;
 456
 457         case "LogicalExpression":
 458             if (isHandledLogicalOperator(node.operator)) {
 459                 state.popChoiceContext();
 460             }
 461             break;
 462
 463         case "SwitchStatement":
 464             state.popSwitchContext();
 465             break;
 466
 467         case "SwitchCase":
 468
 469             /*
 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.
 473              */
 474             if (node.consequent.length === 0) {
 475                 state.makeSwitchCaseBody(true, !node.test);
 476             }
 477             if (state.forkContext.reachable) {
 478                 dontForward = true;
 479             }
 480             break;
 481
 482         case "TryStatement":
 483             state.popTryContext();
 484             break;
 485
 486         case "BreakStatement":
 487             forwardCurrentToHead(analyzer, node);
 488             state.makeBreak(node.label && node.label.name);
 489             dontForward = true;
 490             break;
 491
 492         case "ContinueStatement":
 493             forwardCurrentToHead(analyzer, node);
 494             state.makeContinue(node.label && node.label.name);
 495             dontForward = true;
 496             break;
 497
 498         case "ReturnStatement":
 499             forwardCurrentToHead(analyzer, node);
 500             state.makeReturn();
 501             dontForward = true;
 502             break;
 503
 504         case "ThrowStatement":
 505             forwardCurrentToHead(analyzer, node);
 506             state.makeThrow();
 507             dontForward = true;
 508             break;
 509
 510         case "Identifier":
 511             if (isIdentifierReference(node)) {
 512                 state.makeFirstThrowablePathInTryBlock();
 513                 dontForward = true;
 514             }
 515             break;
 516
 517         case "CallExpression":
 518         case "ImportExpression":
 519         case "MemberExpression":
 520         case "NewExpression":
 521             state.makeFirstThrowablePathInTryBlock();
 522             break;
 523
 524         case "WhileStatement":
 525         case "DoWhileStatement":
 526         case "ForStatement":
 527         case "ForInStatement":
 528         case "ForOfStatement":
 529             state.popLoopContext();
 530             break;
 531
 532         case "AssignmentPattern":
 533             state.popForkContext();
 534             break;
 535
 536         case "LabeledStatement":
 537             if (!breakableTypePattern.test(node.body.type)) {
 538                 state.popBreakContext();
 539             }
 540             break;
 541
 542         default:
 543             break;
 544     }
 545
 546     // Emits onCodePathSegmentStart events if updated.
 547     if (!dontForward) {
 548         forwardCurrentToHead(analyzer, node);
 549     }
 550     debug.dumpState(node, state, true);
 551 }
 552
 553 /**
 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.
 557  * @returns {void}
 558  */
 559 function postprocess(analyzer, node) {
 560     switch (node.type) {
 561         case "Program":
 562         case "FunctionDeclaration":
 563         case "FunctionExpression":
 564         case "ArrowFunctionExpression": {
 565             let codePath = analyzer.codePath;
 566
 567             // Mark the current path as the final node.
 568             CodePath.getState(codePath).makeFinal();
 569
 570             // Emits onCodePathSegmentEnd event of the current segments.
 571             leaveFromCurrentSegment(analyzer, node);
 572
 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);
 577
 578             codePath = analyzer.codePath = analyzer.codePath.upper;
 579             if (codePath) {
 580                 debug.dumpState(node, CodePath.getState(codePath), true);
 581             }
 582             break;
 583         }
 584
 585         default:
 586             break;
 587     }
 588 }
 589
 590 //------------------------------------------------------------------------------
 591 // Public Interface
 592 //------------------------------------------------------------------------------
 593
 594 /**
 595  * The class to analyze code paths.
 596  * This class implements the EventGenerator interface.
 597  */
 598 class CodePathAnalyzer {
 599
 600     // eslint-disable-next-line jsdoc/require-description
 601     /**
 602      * @param {EventGenerator} eventGenerator An event generator to wrap.
 603      */
 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);
 611     }
 612
 613     /**
 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.
 617      * @returns {void}
 618      */
 619     enterNode(node) {
 620         this.currentNode = node;
 621
 622         // Updates the code path due to node's position in its parent node.
 623         if (node.parent) {
 624             preprocess(this, node);
 625         }
 626
 627         /*
 628          * Updates the code path.
 629          * And emits onCodePathStart/onCodePathSegmentStart events.
 630          */
 631         processCodePathToEnter(this, node);
 632
 633         // Emits node events.
 634         this.original.enterNode(node);
 635
 636         this.currentNode = null;
 637     }
 638
 639     /**
 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.
 643      * @returns {void}
 644      */
 645     leaveNode(node) {
 646         this.currentNode = node;
 647
 648         /*
 649          * Updates the code path.
 650          * And emits onCodePathStart/onCodePathSegmentStart events.
 651          */
 652         processCodePathToExit(this, node);
 653
 654         // Emits node events.
 655         this.original.leaveNode(node);
 656
 657         // Emits the last onCodePathStart/onCodePathSegmentStart events.
 658         postprocess(this, node);
 659
 660         this.currentNode = null;
 661     }
 662
 663     /**
 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.
 668      * @returns {void}
 669      */
 670     onLooped(fromSegment, toSegment) {
 671         if (fromSegment.reachable && toSegment.reachable) {
 672             debug.dump(`onCodePathSegmentLoop ${fromSegment.id} -> ${toSegment.id}`);
 673             this.emitter.emit(
 674                 "onCodePathSegmentLoop",
 675                 fromSegment,
 676                 toSegment,
 677                 this.currentNode
 678             );
 679         }
 680     }
 681 }
 682
 683 module.exports = CodePathAnalyzer;