code-path-state.js 47 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480
  1. /**
  2. * @fileoverview A class to manage state of generating a code path.
  3. * @author Toru Nagashima
  4. */
  5. "use strict";
  6. //------------------------------------------------------------------------------
  7. // Requirements
  8. //------------------------------------------------------------------------------
  9. const CodePathSegment = require("./code-path-segment"),
  10. ForkContext = require("./fork-context");
  11. //------------------------------------------------------------------------------
  12. // Helpers
  13. //------------------------------------------------------------------------------
  14. /**
  15. * Adds given segments into the `dest` array.
  16. * If the `others` array does not includes the given segments, adds to the `all`
  17. * array as well.
  18. *
  19. * This adds only reachable and used segments.
  20. * @param {CodePathSegment[]} dest A destination array (`returnedSegments` or `thrownSegments`).
  21. * @param {CodePathSegment[]} others Another destination array (`returnedSegments` or `thrownSegments`).
  22. * @param {CodePathSegment[]} all The unified destination array (`finalSegments`).
  23. * @param {CodePathSegment[]} segments Segments to add.
  24. * @returns {void}
  25. */
  26. function addToReturnedOrThrown(dest, others, all, segments) {
  27. for (let i = 0; i < segments.length; ++i) {
  28. const segment = segments[i];
  29. dest.push(segment);
  30. if (others.indexOf(segment) === -1) {
  31. all.push(segment);
  32. }
  33. }
  34. }
  35. /**
  36. * Gets a loop-context for a `continue` statement.
  37. * @param {CodePathState} state A state to get.
  38. * @param {string} label The label of a `continue` statement.
  39. * @returns {LoopContext} A loop-context for a `continue` statement.
  40. */
  41. function getContinueContext(state, label) {
  42. if (!label) {
  43. return state.loopContext;
  44. }
  45. let context = state.loopContext;
  46. while (context) {
  47. if (context.label === label) {
  48. return context;
  49. }
  50. context = context.upper;
  51. }
  52. /* istanbul ignore next: foolproof (syntax error) */
  53. return null;
  54. }
  55. /**
  56. * Gets a context for a `break` statement.
  57. * @param {CodePathState} state A state to get.
  58. * @param {string} label The label of a `break` statement.
  59. * @returns {LoopContext|SwitchContext} A context for a `break` statement.
  60. */
  61. function getBreakContext(state, label) {
  62. let context = state.breakContext;
  63. while (context) {
  64. if (label ? context.label === label : context.breakable) {
  65. return context;
  66. }
  67. context = context.upper;
  68. }
  69. /* istanbul ignore next: foolproof (syntax error) */
  70. return null;
  71. }
  72. /**
  73. * Gets a context for a `return` statement.
  74. * @param {CodePathState} state A state to get.
  75. * @returns {TryContext|CodePathState} A context for a `return` statement.
  76. */
  77. function getReturnContext(state) {
  78. let context = state.tryContext;
  79. while (context) {
  80. if (context.hasFinalizer && context.position !== "finally") {
  81. return context;
  82. }
  83. context = context.upper;
  84. }
  85. return state;
  86. }
  87. /**
  88. * Gets a context for a `throw` statement.
  89. * @param {CodePathState} state A state to get.
  90. * @returns {TryContext|CodePathState} A context for a `throw` statement.
  91. */
  92. function getThrowContext(state) {
  93. let context = state.tryContext;
  94. while (context) {
  95. if (context.position === "try" ||
  96. (context.hasFinalizer && context.position === "catch")
  97. ) {
  98. return context;
  99. }
  100. context = context.upper;
  101. }
  102. return state;
  103. }
  104. /**
  105. * Removes a given element from a given array.
  106. * @param {any[]} xs An array to remove the specific element.
  107. * @param {any} x An element to be removed.
  108. * @returns {void}
  109. */
  110. function remove(xs, x) {
  111. xs.splice(xs.indexOf(x), 1);
  112. }
  113. /**
  114. * Disconnect given segments.
  115. *
  116. * This is used in a process for switch statements.
  117. * If there is the "default" chunk before other cases, the order is different
  118. * between node's and running's.
  119. * @param {CodePathSegment[]} prevSegments Forward segments to disconnect.
  120. * @param {CodePathSegment[]} nextSegments Backward segments to disconnect.
  121. * @returns {void}
  122. */
  123. function removeConnection(prevSegments, nextSegments) {
  124. for (let i = 0; i < prevSegments.length; ++i) {
  125. const prevSegment = prevSegments[i];
  126. const nextSegment = nextSegments[i];
  127. remove(prevSegment.nextSegments, nextSegment);
  128. remove(prevSegment.allNextSegments, nextSegment);
  129. remove(nextSegment.prevSegments, prevSegment);
  130. remove(nextSegment.allPrevSegments, prevSegment);
  131. }
  132. }
  133. /**
  134. * Creates looping path.
  135. * @param {CodePathState} state The instance.
  136. * @param {CodePathSegment[]} unflattenedFromSegments Segments which are source.
  137. * @param {CodePathSegment[]} unflattenedToSegments Segments which are destination.
  138. * @returns {void}
  139. */
  140. function makeLooped(state, unflattenedFromSegments, unflattenedToSegments) {
  141. const fromSegments = CodePathSegment.flattenUnusedSegments(unflattenedFromSegments);
  142. const toSegments = CodePathSegment.flattenUnusedSegments(unflattenedToSegments);
  143. const end = Math.min(fromSegments.length, toSegments.length);
  144. for (let i = 0; i < end; ++i) {
  145. const fromSegment = fromSegments[i];
  146. const toSegment = toSegments[i];
  147. if (toSegment.reachable) {
  148. fromSegment.nextSegments.push(toSegment);
  149. }
  150. if (fromSegment.reachable) {
  151. toSegment.prevSegments.push(fromSegment);
  152. }
  153. fromSegment.allNextSegments.push(toSegment);
  154. toSegment.allPrevSegments.push(fromSegment);
  155. if (toSegment.allPrevSegments.length >= 2) {
  156. CodePathSegment.markPrevSegmentAsLooped(toSegment, fromSegment);
  157. }
  158. state.notifyLooped(fromSegment, toSegment);
  159. }
  160. }
  161. /**
  162. * Finalizes segments of `test` chunk of a ForStatement.
  163. *
  164. * - Adds `false` paths to paths which are leaving from the loop.
  165. * - Sets `true` paths to paths which go to the body.
  166. * @param {LoopContext} context A loop context to modify.
  167. * @param {ChoiceContext} choiceContext A choice context of this loop.
  168. * @param {CodePathSegment[]} head The current head paths.
  169. * @returns {void}
  170. */
  171. function finalizeTestSegmentsOfFor(context, choiceContext, head) {
  172. if (!choiceContext.processed) {
  173. choiceContext.trueForkContext.add(head);
  174. choiceContext.falseForkContext.add(head);
  175. choiceContext.qqForkContext.add(head);
  176. }
  177. if (context.test !== true) {
  178. context.brokenForkContext.addAll(choiceContext.falseForkContext);
  179. }
  180. context.endOfTestSegments = choiceContext.trueForkContext.makeNext(0, -1);
  181. }
  182. //------------------------------------------------------------------------------
  183. // Public Interface
  184. //------------------------------------------------------------------------------
  185. /**
  186. * A class which manages state to analyze code paths.
  187. */
  188. class CodePathState {
  189. // eslint-disable-next-line jsdoc/require-description
  190. /**
  191. * @param {IdGenerator} idGenerator An id generator to generate id for code
  192. * path segments.
  193. * @param {Function} onLooped A callback function to notify looping.
  194. */
  195. constructor(idGenerator, onLooped) {
  196. this.idGenerator = idGenerator;
  197. this.notifyLooped = onLooped;
  198. this.forkContext = ForkContext.newRoot(idGenerator);
  199. this.choiceContext = null;
  200. this.switchContext = null;
  201. this.tryContext = null;
  202. this.loopContext = null;
  203. this.breakContext = null;
  204. this.chainContext = null;
  205. this.currentSegments = [];
  206. this.initialSegment = this.forkContext.head[0];
  207. // returnedSegments and thrownSegments push elements into finalSegments also.
  208. const final = this.finalSegments = [];
  209. const returned = this.returnedForkContext = [];
  210. const thrown = this.thrownForkContext = [];
  211. returned.add = addToReturnedOrThrown.bind(null, returned, thrown, final);
  212. thrown.add = addToReturnedOrThrown.bind(null, thrown, returned, final);
  213. }
  214. /**
  215. * The head segments.
  216. * @type {CodePathSegment[]}
  217. */
  218. get headSegments() {
  219. return this.forkContext.head;
  220. }
  221. /**
  222. * The parent forking context.
  223. * This is used for the root of new forks.
  224. * @type {ForkContext}
  225. */
  226. get parentForkContext() {
  227. const current = this.forkContext;
  228. return current && current.upper;
  229. }
  230. /**
  231. * Creates and stacks new forking context.
  232. * @param {boolean} forkLeavingPath A flag which shows being in a
  233. * "finally" block.
  234. * @returns {ForkContext} The created context.
  235. */
  236. pushForkContext(forkLeavingPath) {
  237. this.forkContext = ForkContext.newEmpty(
  238. this.forkContext,
  239. forkLeavingPath
  240. );
  241. return this.forkContext;
  242. }
  243. /**
  244. * Pops and merges the last forking context.
  245. * @returns {ForkContext} The last context.
  246. */
  247. popForkContext() {
  248. const lastContext = this.forkContext;
  249. this.forkContext = lastContext.upper;
  250. this.forkContext.replaceHead(lastContext.makeNext(0, -1));
  251. return lastContext;
  252. }
  253. /**
  254. * Creates a new path.
  255. * @returns {void}
  256. */
  257. forkPath() {
  258. this.forkContext.add(this.parentForkContext.makeNext(-1, -1));
  259. }
  260. /**
  261. * Creates a bypass path.
  262. * This is used for such as IfStatement which does not have "else" chunk.
  263. * @returns {void}
  264. */
  265. forkBypassPath() {
  266. this.forkContext.add(this.parentForkContext.head);
  267. }
  268. //--------------------------------------------------------------------------
  269. // ConditionalExpression, LogicalExpression, IfStatement
  270. //--------------------------------------------------------------------------
  271. /**
  272. * Creates a context for ConditionalExpression, LogicalExpression, AssignmentExpression (logical assignments only),
  273. * IfStatement, WhileStatement, DoWhileStatement, or ForStatement.
  274. *
  275. * LogicalExpressions have cases that it goes different paths between the
  276. * `true` case and the `false` case.
  277. *
  278. * For Example:
  279. *
  280. * if (a || b) {
  281. * foo();
  282. * } else {
  283. * bar();
  284. * }
  285. *
  286. * In this case, `b` is evaluated always in the code path of the `else`
  287. * block, but it's not so in the code path of the `if` block.
  288. * So there are 3 paths.
  289. *
  290. * a -> foo();
  291. * a -> b -> foo();
  292. * a -> b -> bar();
  293. * @param {string} kind A kind string.
  294. * If the new context is LogicalExpression's or AssignmentExpression's, this is `"&&"` or `"||"` or `"??"`.
  295. * If it's IfStatement's or ConditionalExpression's, this is `"test"`.
  296. * Otherwise, this is `"loop"`.
  297. * @param {boolean} isForkingAsResult A flag that shows that goes different
  298. * paths between `true` and `false`.
  299. * @returns {void}
  300. */
  301. pushChoiceContext(kind, isForkingAsResult) {
  302. this.choiceContext = {
  303. upper: this.choiceContext,
  304. kind,
  305. isForkingAsResult,
  306. trueForkContext: ForkContext.newEmpty(this.forkContext),
  307. falseForkContext: ForkContext.newEmpty(this.forkContext),
  308. qqForkContext: ForkContext.newEmpty(this.forkContext),
  309. processed: false
  310. };
  311. }
  312. /**
  313. * Pops the last choice context and finalizes it.
  314. * @returns {ChoiceContext} The popped context.
  315. */
  316. popChoiceContext() {
  317. const context = this.choiceContext;
  318. this.choiceContext = context.upper;
  319. const forkContext = this.forkContext;
  320. const headSegments = forkContext.head;
  321. switch (context.kind) {
  322. case "&&":
  323. case "||":
  324. case "??":
  325. /*
  326. * If any result were not transferred from child contexts,
  327. * this sets the head segments to both cases.
  328. * The head segments are the path of the right-hand operand.
  329. */
  330. if (!context.processed) {
  331. context.trueForkContext.add(headSegments);
  332. context.falseForkContext.add(headSegments);
  333. context.qqForkContext.add(headSegments);
  334. }
  335. /*
  336. * Transfers results to upper context if this context is in
  337. * test chunk.
  338. */
  339. if (context.isForkingAsResult) {
  340. const parentContext = this.choiceContext;
  341. parentContext.trueForkContext.addAll(context.trueForkContext);
  342. parentContext.falseForkContext.addAll(context.falseForkContext);
  343. parentContext.qqForkContext.addAll(context.qqForkContext);
  344. parentContext.processed = true;
  345. return context;
  346. }
  347. break;
  348. case "test":
  349. if (!context.processed) {
  350. /*
  351. * The head segments are the path of the `if` block here.
  352. * Updates the `true` path with the end of the `if` block.
  353. */
  354. context.trueForkContext.clear();
  355. context.trueForkContext.add(headSegments);
  356. } else {
  357. /*
  358. * The head segments are the path of the `else` block here.
  359. * Updates the `false` path with the end of the `else`
  360. * block.
  361. */
  362. context.falseForkContext.clear();
  363. context.falseForkContext.add(headSegments);
  364. }
  365. break;
  366. case "loop":
  367. /*
  368. * Loops are addressed in popLoopContext().
  369. * This is called from popLoopContext().
  370. */
  371. return context;
  372. /* istanbul ignore next */
  373. default:
  374. throw new Error("unreachable");
  375. }
  376. // Merges all paths.
  377. const prevForkContext = context.trueForkContext;
  378. prevForkContext.addAll(context.falseForkContext);
  379. forkContext.replaceHead(prevForkContext.makeNext(0, -1));
  380. return context;
  381. }
  382. /**
  383. * Makes a code path segment of the right-hand operand of a logical
  384. * expression.
  385. * @returns {void}
  386. */
  387. makeLogicalRight() {
  388. const context = this.choiceContext;
  389. const forkContext = this.forkContext;
  390. if (context.processed) {
  391. /*
  392. * This got segments already from the child choice context.
  393. * Creates the next path from own true/false fork context.
  394. */
  395. let prevForkContext;
  396. switch (context.kind) {
  397. case "&&": // if true then go to the right-hand side.
  398. prevForkContext = context.trueForkContext;
  399. break;
  400. case "||": // if false then go to the right-hand side.
  401. prevForkContext = context.falseForkContext;
  402. break;
  403. case "??": // Both true/false can short-circuit, so needs the third path to go to the right-hand side. That's qqForkContext.
  404. prevForkContext = context.qqForkContext;
  405. break;
  406. default:
  407. throw new Error("unreachable");
  408. }
  409. forkContext.replaceHead(prevForkContext.makeNext(0, -1));
  410. prevForkContext.clear();
  411. context.processed = false;
  412. } else {
  413. /*
  414. * This did not get segments from the child choice context.
  415. * So addresses the head segments.
  416. * The head segments are the path of the left-hand operand.
  417. */
  418. switch (context.kind) {
  419. case "&&": // the false path can short-circuit.
  420. context.falseForkContext.add(forkContext.head);
  421. break;
  422. case "||": // the true path can short-circuit.
  423. context.trueForkContext.add(forkContext.head);
  424. break;
  425. case "??": // both can short-circuit.
  426. context.trueForkContext.add(forkContext.head);
  427. context.falseForkContext.add(forkContext.head);
  428. break;
  429. default:
  430. throw new Error("unreachable");
  431. }
  432. forkContext.replaceHead(forkContext.makeNext(-1, -1));
  433. }
  434. }
  435. /**
  436. * Makes a code path segment of the `if` block.
  437. * @returns {void}
  438. */
  439. makeIfConsequent() {
  440. const context = this.choiceContext;
  441. const forkContext = this.forkContext;
  442. /*
  443. * If any result were not transferred from child contexts,
  444. * this sets the head segments to both cases.
  445. * The head segments are the path of the test expression.
  446. */
  447. if (!context.processed) {
  448. context.trueForkContext.add(forkContext.head);
  449. context.falseForkContext.add(forkContext.head);
  450. context.qqForkContext.add(forkContext.head);
  451. }
  452. context.processed = false;
  453. // Creates new path from the `true` case.
  454. forkContext.replaceHead(
  455. context.trueForkContext.makeNext(0, -1)
  456. );
  457. }
  458. /**
  459. * Makes a code path segment of the `else` block.
  460. * @returns {void}
  461. */
  462. makeIfAlternate() {
  463. const context = this.choiceContext;
  464. const forkContext = this.forkContext;
  465. /*
  466. * The head segments are the path of the `if` block.
  467. * Updates the `true` path with the end of the `if` block.
  468. */
  469. context.trueForkContext.clear();
  470. context.trueForkContext.add(forkContext.head);
  471. context.processed = true;
  472. // Creates new path from the `false` case.
  473. forkContext.replaceHead(
  474. context.falseForkContext.makeNext(0, -1)
  475. );
  476. }
  477. //--------------------------------------------------------------------------
  478. // ChainExpression
  479. //--------------------------------------------------------------------------
  480. /**
  481. * Push a new `ChainExpression` context to the stack.
  482. * This method is called on entering to each `ChainExpression` node.
  483. * This context is used to count forking in the optional chain then merge them on the exiting from the `ChainExpression` node.
  484. * @returns {void}
  485. */
  486. pushChainContext() {
  487. this.chainContext = {
  488. upper: this.chainContext,
  489. countChoiceContexts: 0
  490. };
  491. }
  492. /**
  493. * Pop a `ChainExpression` context from the stack.
  494. * This method is called on exiting from each `ChainExpression` node.
  495. * This merges all forks of the last optional chaining.
  496. * @returns {void}
  497. */
  498. popChainContext() {
  499. const context = this.chainContext;
  500. this.chainContext = context.upper;
  501. // pop all choice contexts of this.
  502. for (let i = context.countChoiceContexts; i > 0; --i) {
  503. this.popChoiceContext();
  504. }
  505. }
  506. /**
  507. * Create a choice context for optional access.
  508. * This method is called on entering to each `(Call|Member)Expression[optional=true]` node.
  509. * This creates a choice context as similar to `LogicalExpression[operator="??"]` node.
  510. * @returns {void}
  511. */
  512. makeOptionalNode() {
  513. if (this.chainContext) {
  514. this.chainContext.countChoiceContexts += 1;
  515. this.pushChoiceContext("??", false);
  516. }
  517. }
  518. /**
  519. * Create a fork.
  520. * This method is called on entering to the `arguments|property` property of each `(Call|Member)Expression` node.
  521. * @returns {void}
  522. */
  523. makeOptionalRight() {
  524. if (this.chainContext) {
  525. this.makeLogicalRight();
  526. }
  527. }
  528. //--------------------------------------------------------------------------
  529. // SwitchStatement
  530. //--------------------------------------------------------------------------
  531. /**
  532. * Creates a context object of SwitchStatement and stacks it.
  533. * @param {boolean} hasCase `true` if the switch statement has one or more
  534. * case parts.
  535. * @param {string|null} label The label text.
  536. * @returns {void}
  537. */
  538. pushSwitchContext(hasCase, label) {
  539. this.switchContext = {
  540. upper: this.switchContext,
  541. hasCase,
  542. defaultSegments: null,
  543. defaultBodySegments: null,
  544. foundDefault: false,
  545. lastIsDefault: false,
  546. countForks: 0
  547. };
  548. this.pushBreakContext(true, label);
  549. }
  550. /**
  551. * Pops the last context of SwitchStatement and finalizes it.
  552. *
  553. * - Disposes all forking stack for `case` and `default`.
  554. * - Creates the next code path segment from `context.brokenForkContext`.
  555. * - If the last `SwitchCase` node is not a `default` part, creates a path
  556. * to the `default` body.
  557. * @returns {void}
  558. */
  559. popSwitchContext() {
  560. const context = this.switchContext;
  561. this.switchContext = context.upper;
  562. const forkContext = this.forkContext;
  563. const brokenForkContext = this.popBreakContext().brokenForkContext;
  564. if (context.countForks === 0) {
  565. /*
  566. * When there is only one `default` chunk and there is one or more
  567. * `break` statements, even if forks are nothing, it needs to merge
  568. * those.
  569. */
  570. if (!brokenForkContext.empty) {
  571. brokenForkContext.add(forkContext.makeNext(-1, -1));
  572. forkContext.replaceHead(brokenForkContext.makeNext(0, -1));
  573. }
  574. return;
  575. }
  576. const lastSegments = forkContext.head;
  577. this.forkBypassPath();
  578. const lastCaseSegments = forkContext.head;
  579. /*
  580. * `brokenForkContext` is used to make the next segment.
  581. * It must add the last segment into `brokenForkContext`.
  582. */
  583. brokenForkContext.add(lastSegments);
  584. /*
  585. * A path which is failed in all case test should be connected to path
  586. * of `default` chunk.
  587. */
  588. if (!context.lastIsDefault) {
  589. if (context.defaultBodySegments) {
  590. /*
  591. * Remove a link from `default` label to its chunk.
  592. * It's false route.
  593. */
  594. removeConnection(context.defaultSegments, context.defaultBodySegments);
  595. makeLooped(this, lastCaseSegments, context.defaultBodySegments);
  596. } else {
  597. /*
  598. * It handles the last case body as broken if `default` chunk
  599. * does not exist.
  600. */
  601. brokenForkContext.add(lastCaseSegments);
  602. }
  603. }
  604. // Pops the segment context stack until the entry segment.
  605. for (let i = 0; i < context.countForks; ++i) {
  606. this.forkContext = this.forkContext.upper;
  607. }
  608. /*
  609. * Creates a path from all brokenForkContext paths.
  610. * This is a path after switch statement.
  611. */
  612. this.forkContext.replaceHead(brokenForkContext.makeNext(0, -1));
  613. }
  614. /**
  615. * Makes a code path segment for a `SwitchCase` node.
  616. * @param {boolean} isEmpty `true` if the body is empty.
  617. * @param {boolean} isDefault `true` if the body is the default case.
  618. * @returns {void}
  619. */
  620. makeSwitchCaseBody(isEmpty, isDefault) {
  621. const context = this.switchContext;
  622. if (!context.hasCase) {
  623. return;
  624. }
  625. /*
  626. * Merge forks.
  627. * The parent fork context has two segments.
  628. * Those are from the current case and the body of the previous case.
  629. */
  630. const parentForkContext = this.forkContext;
  631. const forkContext = this.pushForkContext();
  632. forkContext.add(parentForkContext.makeNext(0, -1));
  633. /*
  634. * Save `default` chunk info.
  635. * If the `default` label is not at the last, we must make a path from
  636. * the last `case` to the `default` chunk.
  637. */
  638. if (isDefault) {
  639. context.defaultSegments = parentForkContext.head;
  640. if (isEmpty) {
  641. context.foundDefault = true;
  642. } else {
  643. context.defaultBodySegments = forkContext.head;
  644. }
  645. } else {
  646. if (!isEmpty && context.foundDefault) {
  647. context.foundDefault = false;
  648. context.defaultBodySegments = forkContext.head;
  649. }
  650. }
  651. context.lastIsDefault = isDefault;
  652. context.countForks += 1;
  653. }
  654. //--------------------------------------------------------------------------
  655. // TryStatement
  656. //--------------------------------------------------------------------------
  657. /**
  658. * Creates a context object of TryStatement and stacks it.
  659. * @param {boolean} hasFinalizer `true` if the try statement has a
  660. * `finally` block.
  661. * @returns {void}
  662. */
  663. pushTryContext(hasFinalizer) {
  664. this.tryContext = {
  665. upper: this.tryContext,
  666. position: "try",
  667. hasFinalizer,
  668. returnedForkContext: hasFinalizer
  669. ? ForkContext.newEmpty(this.forkContext)
  670. : null,
  671. thrownForkContext: ForkContext.newEmpty(this.forkContext),
  672. lastOfTryIsReachable: false,
  673. lastOfCatchIsReachable: false
  674. };
  675. }
  676. /**
  677. * Pops the last context of TryStatement and finalizes it.
  678. * @returns {void}
  679. */
  680. popTryContext() {
  681. const context = this.tryContext;
  682. this.tryContext = context.upper;
  683. if (context.position === "catch") {
  684. // Merges two paths from the `try` block and `catch` block merely.
  685. this.popForkContext();
  686. return;
  687. }
  688. /*
  689. * The following process is executed only when there is the `finally`
  690. * block.
  691. */
  692. const returned = context.returnedForkContext;
  693. const thrown = context.thrownForkContext;
  694. if (returned.empty && thrown.empty) {
  695. return;
  696. }
  697. // Separate head to normal paths and leaving paths.
  698. const headSegments = this.forkContext.head;
  699. this.forkContext = this.forkContext.upper;
  700. const normalSegments = headSegments.slice(0, headSegments.length / 2 | 0);
  701. const leavingSegments = headSegments.slice(headSegments.length / 2 | 0);
  702. // Forwards the leaving path to upper contexts.
  703. if (!returned.empty) {
  704. getReturnContext(this).returnedForkContext.add(leavingSegments);
  705. }
  706. if (!thrown.empty) {
  707. getThrowContext(this).thrownForkContext.add(leavingSegments);
  708. }
  709. // Sets the normal path as the next.
  710. this.forkContext.replaceHead(normalSegments);
  711. /*
  712. * If both paths of the `try` block and the `catch` block are
  713. * unreachable, the next path becomes unreachable as well.
  714. */
  715. if (!context.lastOfTryIsReachable && !context.lastOfCatchIsReachable) {
  716. this.forkContext.makeUnreachable();
  717. }
  718. }
  719. /**
  720. * Makes a code path segment for a `catch` block.
  721. * @returns {void}
  722. */
  723. makeCatchBlock() {
  724. const context = this.tryContext;
  725. const forkContext = this.forkContext;
  726. const thrown = context.thrownForkContext;
  727. // Update state.
  728. context.position = "catch";
  729. context.thrownForkContext = ForkContext.newEmpty(forkContext);
  730. context.lastOfTryIsReachable = forkContext.reachable;
  731. // Merge thrown paths.
  732. thrown.add(forkContext.head);
  733. const thrownSegments = thrown.makeNext(0, -1);
  734. // Fork to a bypass and the merged thrown path.
  735. this.pushForkContext();
  736. this.forkBypassPath();
  737. this.forkContext.add(thrownSegments);
  738. }
  739. /**
  740. * Makes a code path segment for a `finally` block.
  741. *
  742. * In the `finally` block, parallel paths are created. The parallel paths
  743. * are used as leaving-paths. The leaving-paths are paths from `return`
  744. * statements and `throw` statements in a `try` block or a `catch` block.
  745. * @returns {void}
  746. */
  747. makeFinallyBlock() {
  748. const context = this.tryContext;
  749. let forkContext = this.forkContext;
  750. const returned = context.returnedForkContext;
  751. const thrown = context.thrownForkContext;
  752. const headOfLeavingSegments = forkContext.head;
  753. // Update state.
  754. if (context.position === "catch") {
  755. // Merges two paths from the `try` block and `catch` block.
  756. this.popForkContext();
  757. forkContext = this.forkContext;
  758. context.lastOfCatchIsReachable = forkContext.reachable;
  759. } else {
  760. context.lastOfTryIsReachable = forkContext.reachable;
  761. }
  762. context.position = "finally";
  763. if (returned.empty && thrown.empty) {
  764. // This path does not leave.
  765. return;
  766. }
  767. /*
  768. * Create a parallel segment from merging returned and thrown.
  769. * This segment will leave at the end of this finally block.
  770. */
  771. const segments = forkContext.makeNext(-1, -1);
  772. for (let i = 0; i < forkContext.count; ++i) {
  773. const prevSegsOfLeavingSegment = [headOfLeavingSegments[i]];
  774. for (let j = 0; j < returned.segmentsList.length; ++j) {
  775. prevSegsOfLeavingSegment.push(returned.segmentsList[j][i]);
  776. }
  777. for (let j = 0; j < thrown.segmentsList.length; ++j) {
  778. prevSegsOfLeavingSegment.push(thrown.segmentsList[j][i]);
  779. }
  780. segments.push(
  781. CodePathSegment.newNext(
  782. this.idGenerator.next(),
  783. prevSegsOfLeavingSegment
  784. )
  785. );
  786. }
  787. this.pushForkContext(true);
  788. this.forkContext.add(segments);
  789. }
  790. /**
  791. * Makes a code path segment from the first throwable node to the `catch`
  792. * block or the `finally` block.
  793. * @returns {void}
  794. */
  795. makeFirstThrowablePathInTryBlock() {
  796. const forkContext = this.forkContext;
  797. if (!forkContext.reachable) {
  798. return;
  799. }
  800. const context = getThrowContext(this);
  801. if (context === this ||
  802. context.position !== "try" ||
  803. !context.thrownForkContext.empty
  804. ) {
  805. return;
  806. }
  807. context.thrownForkContext.add(forkContext.head);
  808. forkContext.replaceHead(forkContext.makeNext(-1, -1));
  809. }
  810. //--------------------------------------------------------------------------
  811. // Loop Statements
  812. //--------------------------------------------------------------------------
  813. /**
  814. * Creates a context object of a loop statement and stacks it.
  815. * @param {string} type The type of the node which was triggered. One of
  816. * `WhileStatement`, `DoWhileStatement`, `ForStatement`, `ForInStatement`,
  817. * and `ForStatement`.
  818. * @param {string|null} label A label of the node which was triggered.
  819. * @returns {void}
  820. */
  821. pushLoopContext(type, label) {
  822. const forkContext = this.forkContext;
  823. const breakContext = this.pushBreakContext(true, label);
  824. switch (type) {
  825. case "WhileStatement":
  826. this.pushChoiceContext("loop", false);
  827. this.loopContext = {
  828. upper: this.loopContext,
  829. type,
  830. label,
  831. test: void 0,
  832. continueDestSegments: null,
  833. brokenForkContext: breakContext.brokenForkContext
  834. };
  835. break;
  836. case "DoWhileStatement":
  837. this.pushChoiceContext("loop", false);
  838. this.loopContext = {
  839. upper: this.loopContext,
  840. type,
  841. label,
  842. test: void 0,
  843. entrySegments: null,
  844. continueForkContext: ForkContext.newEmpty(forkContext),
  845. brokenForkContext: breakContext.brokenForkContext
  846. };
  847. break;
  848. case "ForStatement":
  849. this.pushChoiceContext("loop", false);
  850. this.loopContext = {
  851. upper: this.loopContext,
  852. type,
  853. label,
  854. test: void 0,
  855. endOfInitSegments: null,
  856. testSegments: null,
  857. endOfTestSegments: null,
  858. updateSegments: null,
  859. endOfUpdateSegments: null,
  860. continueDestSegments: null,
  861. brokenForkContext: breakContext.brokenForkContext
  862. };
  863. break;
  864. case "ForInStatement":
  865. case "ForOfStatement":
  866. this.loopContext = {
  867. upper: this.loopContext,
  868. type,
  869. label,
  870. prevSegments: null,
  871. leftSegments: null,
  872. endOfLeftSegments: null,
  873. continueDestSegments: null,
  874. brokenForkContext: breakContext.brokenForkContext
  875. };
  876. break;
  877. /* istanbul ignore next */
  878. default:
  879. throw new Error(`unknown type: "${type}"`);
  880. }
  881. }
  882. /**
  883. * Pops the last context of a loop statement and finalizes it.
  884. * @returns {void}
  885. */
  886. popLoopContext() {
  887. const context = this.loopContext;
  888. this.loopContext = context.upper;
  889. const forkContext = this.forkContext;
  890. const brokenForkContext = this.popBreakContext().brokenForkContext;
  891. // Creates a looped path.
  892. switch (context.type) {
  893. case "WhileStatement":
  894. case "ForStatement":
  895. this.popChoiceContext();
  896. makeLooped(
  897. this,
  898. forkContext.head,
  899. context.continueDestSegments
  900. );
  901. break;
  902. case "DoWhileStatement": {
  903. const choiceContext = this.popChoiceContext();
  904. if (!choiceContext.processed) {
  905. choiceContext.trueForkContext.add(forkContext.head);
  906. choiceContext.falseForkContext.add(forkContext.head);
  907. }
  908. if (context.test !== true) {
  909. brokenForkContext.addAll(choiceContext.falseForkContext);
  910. }
  911. // `true` paths go to looping.
  912. const segmentsList = choiceContext.trueForkContext.segmentsList;
  913. for (let i = 0; i < segmentsList.length; ++i) {
  914. makeLooped(
  915. this,
  916. segmentsList[i],
  917. context.entrySegments
  918. );
  919. }
  920. break;
  921. }
  922. case "ForInStatement":
  923. case "ForOfStatement":
  924. brokenForkContext.add(forkContext.head);
  925. makeLooped(
  926. this,
  927. forkContext.head,
  928. context.leftSegments
  929. );
  930. break;
  931. /* istanbul ignore next */
  932. default:
  933. throw new Error("unreachable");
  934. }
  935. // Go next.
  936. if (brokenForkContext.empty) {
  937. forkContext.replaceHead(forkContext.makeUnreachable(-1, -1));
  938. } else {
  939. forkContext.replaceHead(brokenForkContext.makeNext(0, -1));
  940. }
  941. }
  942. /**
  943. * Makes a code path segment for the test part of a WhileStatement.
  944. * @param {boolean|undefined} test The test value (only when constant).
  945. * @returns {void}
  946. */
  947. makeWhileTest(test) {
  948. const context = this.loopContext;
  949. const forkContext = this.forkContext;
  950. const testSegments = forkContext.makeNext(0, -1);
  951. // Update state.
  952. context.test = test;
  953. context.continueDestSegments = testSegments;
  954. forkContext.replaceHead(testSegments);
  955. }
  956. /**
  957. * Makes a code path segment for the body part of a WhileStatement.
  958. * @returns {void}
  959. */
  960. makeWhileBody() {
  961. const context = this.loopContext;
  962. const choiceContext = this.choiceContext;
  963. const forkContext = this.forkContext;
  964. if (!choiceContext.processed) {
  965. choiceContext.trueForkContext.add(forkContext.head);
  966. choiceContext.falseForkContext.add(forkContext.head);
  967. }
  968. // Update state.
  969. if (context.test !== true) {
  970. context.brokenForkContext.addAll(choiceContext.falseForkContext);
  971. }
  972. forkContext.replaceHead(choiceContext.trueForkContext.makeNext(0, -1));
  973. }
  974. /**
  975. * Makes a code path segment for the body part of a DoWhileStatement.
  976. * @returns {void}
  977. */
  978. makeDoWhileBody() {
  979. const context = this.loopContext;
  980. const forkContext = this.forkContext;
  981. const bodySegments = forkContext.makeNext(-1, -1);
  982. // Update state.
  983. context.entrySegments = bodySegments;
  984. forkContext.replaceHead(bodySegments);
  985. }
  986. /**
  987. * Makes a code path segment for the test part of a DoWhileStatement.
  988. * @param {boolean|undefined} test The test value (only when constant).
  989. * @returns {void}
  990. */
  991. makeDoWhileTest(test) {
  992. const context = this.loopContext;
  993. const forkContext = this.forkContext;
  994. context.test = test;
  995. // Creates paths of `continue` statements.
  996. if (!context.continueForkContext.empty) {
  997. context.continueForkContext.add(forkContext.head);
  998. const testSegments = context.continueForkContext.makeNext(0, -1);
  999. forkContext.replaceHead(testSegments);
  1000. }
  1001. }
  1002. /**
  1003. * Makes a code path segment for the test part of a ForStatement.
  1004. * @param {boolean|undefined} test The test value (only when constant).
  1005. * @returns {void}
  1006. */
  1007. makeForTest(test) {
  1008. const context = this.loopContext;
  1009. const forkContext = this.forkContext;
  1010. const endOfInitSegments = forkContext.head;
  1011. const testSegments = forkContext.makeNext(-1, -1);
  1012. // Update state.
  1013. context.test = test;
  1014. context.endOfInitSegments = endOfInitSegments;
  1015. context.continueDestSegments = context.testSegments = testSegments;
  1016. forkContext.replaceHead(testSegments);
  1017. }
  1018. /**
  1019. * Makes a code path segment for the update part of a ForStatement.
  1020. * @returns {void}
  1021. */
  1022. makeForUpdate() {
  1023. const context = this.loopContext;
  1024. const choiceContext = this.choiceContext;
  1025. const forkContext = this.forkContext;
  1026. // Make the next paths of the test.
  1027. if (context.testSegments) {
  1028. finalizeTestSegmentsOfFor(
  1029. context,
  1030. choiceContext,
  1031. forkContext.head
  1032. );
  1033. } else {
  1034. context.endOfInitSegments = forkContext.head;
  1035. }
  1036. // Update state.
  1037. const updateSegments = forkContext.makeDisconnected(-1, -1);
  1038. context.continueDestSegments = context.updateSegments = updateSegments;
  1039. forkContext.replaceHead(updateSegments);
  1040. }
  1041. /**
  1042. * Makes a code path segment for the body part of a ForStatement.
  1043. * @returns {void}
  1044. */
  1045. makeForBody() {
  1046. const context = this.loopContext;
  1047. const choiceContext = this.choiceContext;
  1048. const forkContext = this.forkContext;
  1049. // Update state.
  1050. if (context.updateSegments) {
  1051. context.endOfUpdateSegments = forkContext.head;
  1052. // `update` -> `test`
  1053. if (context.testSegments) {
  1054. makeLooped(
  1055. this,
  1056. context.endOfUpdateSegments,
  1057. context.testSegments
  1058. );
  1059. }
  1060. } else if (context.testSegments) {
  1061. finalizeTestSegmentsOfFor(
  1062. context,
  1063. choiceContext,
  1064. forkContext.head
  1065. );
  1066. } else {
  1067. context.endOfInitSegments = forkContext.head;
  1068. }
  1069. let bodySegments = context.endOfTestSegments;
  1070. if (!bodySegments) {
  1071. /*
  1072. * If there is not the `test` part, the `body` path comes from the
  1073. * `init` part and the `update` part.
  1074. */
  1075. const prevForkContext = ForkContext.newEmpty(forkContext);
  1076. prevForkContext.add(context.endOfInitSegments);
  1077. if (context.endOfUpdateSegments) {
  1078. prevForkContext.add(context.endOfUpdateSegments);
  1079. }
  1080. bodySegments = prevForkContext.makeNext(0, -1);
  1081. }
  1082. context.continueDestSegments = context.continueDestSegments || bodySegments;
  1083. forkContext.replaceHead(bodySegments);
  1084. }
  1085. /**
  1086. * Makes a code path segment for the left part of a ForInStatement and a
  1087. * ForOfStatement.
  1088. * @returns {void}
  1089. */
  1090. makeForInOfLeft() {
  1091. const context = this.loopContext;
  1092. const forkContext = this.forkContext;
  1093. const leftSegments = forkContext.makeDisconnected(-1, -1);
  1094. // Update state.
  1095. context.prevSegments = forkContext.head;
  1096. context.leftSegments = context.continueDestSegments = leftSegments;
  1097. forkContext.replaceHead(leftSegments);
  1098. }
  1099. /**
  1100. * Makes a code path segment for the right part of a ForInStatement and a
  1101. * ForOfStatement.
  1102. * @returns {void}
  1103. */
  1104. makeForInOfRight() {
  1105. const context = this.loopContext;
  1106. const forkContext = this.forkContext;
  1107. const temp = ForkContext.newEmpty(forkContext);
  1108. temp.add(context.prevSegments);
  1109. const rightSegments = temp.makeNext(-1, -1);
  1110. // Update state.
  1111. context.endOfLeftSegments = forkContext.head;
  1112. forkContext.replaceHead(rightSegments);
  1113. }
  1114. /**
  1115. * Makes a code path segment for the body part of a ForInStatement and a
  1116. * ForOfStatement.
  1117. * @returns {void}
  1118. */
  1119. makeForInOfBody() {
  1120. const context = this.loopContext;
  1121. const forkContext = this.forkContext;
  1122. const temp = ForkContext.newEmpty(forkContext);
  1123. temp.add(context.endOfLeftSegments);
  1124. const bodySegments = temp.makeNext(-1, -1);
  1125. // Make a path: `right` -> `left`.
  1126. makeLooped(this, forkContext.head, context.leftSegments);
  1127. // Update state.
  1128. context.brokenForkContext.add(forkContext.head);
  1129. forkContext.replaceHead(bodySegments);
  1130. }
  1131. //--------------------------------------------------------------------------
  1132. // Control Statements
  1133. //--------------------------------------------------------------------------
  1134. /**
  1135. * Creates new context for BreakStatement.
  1136. * @param {boolean} breakable The flag to indicate it can break by
  1137. * an unlabeled BreakStatement.
  1138. * @param {string|null} label The label of this context.
  1139. * @returns {Object} The new context.
  1140. */
  1141. pushBreakContext(breakable, label) {
  1142. this.breakContext = {
  1143. upper: this.breakContext,
  1144. breakable,
  1145. label,
  1146. brokenForkContext: ForkContext.newEmpty(this.forkContext)
  1147. };
  1148. return this.breakContext;
  1149. }
  1150. /**
  1151. * Removes the top item of the break context stack.
  1152. * @returns {Object} The removed context.
  1153. */
  1154. popBreakContext() {
  1155. const context = this.breakContext;
  1156. const forkContext = this.forkContext;
  1157. this.breakContext = context.upper;
  1158. // Process this context here for other than switches and loops.
  1159. if (!context.breakable) {
  1160. const brokenForkContext = context.brokenForkContext;
  1161. if (!brokenForkContext.empty) {
  1162. brokenForkContext.add(forkContext.head);
  1163. forkContext.replaceHead(brokenForkContext.makeNext(0, -1));
  1164. }
  1165. }
  1166. return context;
  1167. }
  1168. /**
  1169. * Makes a path for a `break` statement.
  1170. *
  1171. * It registers the head segment to a context of `break`.
  1172. * It makes new unreachable segment, then it set the head with the segment.
  1173. * @param {string} label A label of the break statement.
  1174. * @returns {void}
  1175. */
  1176. makeBreak(label) {
  1177. const forkContext = this.forkContext;
  1178. if (!forkContext.reachable) {
  1179. return;
  1180. }
  1181. const context = getBreakContext(this, label);
  1182. /* istanbul ignore else: foolproof (syntax error) */
  1183. if (context) {
  1184. context.brokenForkContext.add(forkContext.head);
  1185. }
  1186. forkContext.replaceHead(forkContext.makeUnreachable(-1, -1));
  1187. }
  1188. /**
  1189. * Makes a path for a `continue` statement.
  1190. *
  1191. * It makes a looping path.
  1192. * It makes new unreachable segment, then it set the head with the segment.
  1193. * @param {string} label A label of the continue statement.
  1194. * @returns {void}
  1195. */
  1196. makeContinue(label) {
  1197. const forkContext = this.forkContext;
  1198. if (!forkContext.reachable) {
  1199. return;
  1200. }
  1201. const context = getContinueContext(this, label);
  1202. /* istanbul ignore else: foolproof (syntax error) */
  1203. if (context) {
  1204. if (context.continueDestSegments) {
  1205. makeLooped(this, forkContext.head, context.continueDestSegments);
  1206. // If the context is a for-in/of loop, this effects a break also.
  1207. if (context.type === "ForInStatement" ||
  1208. context.type === "ForOfStatement"
  1209. ) {
  1210. context.brokenForkContext.add(forkContext.head);
  1211. }
  1212. } else {
  1213. context.continueForkContext.add(forkContext.head);
  1214. }
  1215. }
  1216. forkContext.replaceHead(forkContext.makeUnreachable(-1, -1));
  1217. }
  1218. /**
  1219. * Makes a path for a `return` statement.
  1220. *
  1221. * It registers the head segment to a context of `return`.
  1222. * It makes new unreachable segment, then it set the head with the segment.
  1223. * @returns {void}
  1224. */
  1225. makeReturn() {
  1226. const forkContext = this.forkContext;
  1227. if (forkContext.reachable) {
  1228. getReturnContext(this).returnedForkContext.add(forkContext.head);
  1229. forkContext.replaceHead(forkContext.makeUnreachable(-1, -1));
  1230. }
  1231. }
  1232. /**
  1233. * Makes a path for a `throw` statement.
  1234. *
  1235. * It registers the head segment to a context of `throw`.
  1236. * It makes new unreachable segment, then it set the head with the segment.
  1237. * @returns {void}
  1238. */
  1239. makeThrow() {
  1240. const forkContext = this.forkContext;
  1241. if (forkContext.reachable) {
  1242. getThrowContext(this).thrownForkContext.add(forkContext.head);
  1243. forkContext.replaceHead(forkContext.makeUnreachable(-1, -1));
  1244. }
  1245. }
  1246. /**
  1247. * Makes the final path.
  1248. * @returns {void}
  1249. */
  1250. makeFinal() {
  1251. const segments = this.currentSegments;
  1252. if (segments.length > 0 && segments[0].reachable) {
  1253. this.returnedForkContext.add(segments);
  1254. }
  1255. }
  1256. }
  1257. module.exports = CodePathState;