traverser.js 5.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195
  1. /**
  2. * @fileoverview Traverser to traverse AST trees.
  3. * @author Nicholas C. Zakas
  4. * @author Toru Nagashima
  5. */
  6. "use strict";
  7. //------------------------------------------------------------------------------
  8. // Requirements
  9. //------------------------------------------------------------------------------
  10. const vk = require("eslint-visitor-keys");
  11. const debug = require("debug")("eslint:traverser");
  12. //------------------------------------------------------------------------------
  13. // Helpers
  14. //------------------------------------------------------------------------------
  15. /**
  16. * Do nothing.
  17. * @returns {void}
  18. */
  19. function noop() {
  20. // do nothing.
  21. }
  22. /**
  23. * Check whether the given value is an ASTNode or not.
  24. * @param {any} x The value to check.
  25. * @returns {boolean} `true` if the value is an ASTNode.
  26. */
  27. function isNode(x) {
  28. return x !== null && typeof x === "object" && typeof x.type === "string";
  29. }
  30. /**
  31. * Get the visitor keys of a given node.
  32. * @param {Object} visitorKeys The map of visitor keys.
  33. * @param {ASTNode} node The node to get their visitor keys.
  34. * @returns {string[]} The visitor keys of the node.
  35. */
  36. function getVisitorKeys(visitorKeys, node) {
  37. let keys = visitorKeys[node.type];
  38. if (!keys) {
  39. keys = vk.getKeys(node);
  40. debug("Unknown node type \"%s\": Estimated visitor keys %j", node.type, keys);
  41. }
  42. return keys;
  43. }
  44. /**
  45. * The traverser class to traverse AST trees.
  46. */
  47. class Traverser {
  48. constructor() {
  49. this._current = null;
  50. this._parents = [];
  51. this._skipped = false;
  52. this._broken = false;
  53. this._visitorKeys = null;
  54. this._enter = null;
  55. this._leave = null;
  56. }
  57. // eslint-disable-next-line jsdoc/require-description
  58. /**
  59. * @returns {ASTNode} The current node.
  60. */
  61. current() {
  62. return this._current;
  63. }
  64. // eslint-disable-next-line jsdoc/require-description
  65. /**
  66. * @returns {ASTNode[]} The ancestor nodes.
  67. */
  68. parents() {
  69. return this._parents.slice(0);
  70. }
  71. /**
  72. * Break the current traversal.
  73. * @returns {void}
  74. */
  75. break() {
  76. this._broken = true;
  77. }
  78. /**
  79. * Skip child nodes for the current traversal.
  80. * @returns {void}
  81. */
  82. skip() {
  83. this._skipped = true;
  84. }
  85. /**
  86. * Traverse the given AST tree.
  87. * @param {ASTNode} node The root node to traverse.
  88. * @param {Object} options The option object.
  89. * @param {Object} [options.visitorKeys=DEFAULT_VISITOR_KEYS] The keys of each node types to traverse child nodes. Default is `./default-visitor-keys.json`.
  90. * @param {Function} [options.enter=noop] The callback function which is called on entering each node.
  91. * @param {Function} [options.leave=noop] The callback function which is called on leaving each node.
  92. * @returns {void}
  93. */
  94. traverse(node, options) {
  95. this._current = null;
  96. this._parents = [];
  97. this._skipped = false;
  98. this._broken = false;
  99. this._visitorKeys = options.visitorKeys || vk.KEYS;
  100. this._enter = options.enter || noop;
  101. this._leave = options.leave || noop;
  102. this._traverse(node, null);
  103. }
  104. /**
  105. * Traverse the given AST tree recursively.
  106. * @param {ASTNode} node The current node.
  107. * @param {ASTNode|null} parent The parent node.
  108. * @returns {void}
  109. * @private
  110. */
  111. _traverse(node, parent) {
  112. if (!isNode(node)) {
  113. return;
  114. }
  115. this._current = node;
  116. this._skipped = false;
  117. this._enter(node, parent);
  118. if (!this._skipped && !this._broken) {
  119. const keys = getVisitorKeys(this._visitorKeys, node);
  120. if (keys.length >= 1) {
  121. this._parents.push(node);
  122. for (let i = 0; i < keys.length && !this._broken; ++i) {
  123. const child = node[keys[i]];
  124. if (Array.isArray(child)) {
  125. for (let j = 0; j < child.length && !this._broken; ++j) {
  126. this._traverse(child[j], node);
  127. }
  128. } else {
  129. this._traverse(child, node);
  130. }
  131. }
  132. this._parents.pop();
  133. }
  134. }
  135. if (!this._broken) {
  136. this._leave(node, parent);
  137. }
  138. this._current = parent;
  139. }
  140. /**
  141. * Calculates the keys to use for traversal.
  142. * @param {ASTNode} node The node to read keys from.
  143. * @returns {string[]} An array of keys to visit on the node.
  144. * @private
  145. */
  146. static getKeys(node) {
  147. return vk.getKeys(node);
  148. }
  149. /**
  150. * Traverse the given AST tree.
  151. * @param {ASTNode} node The root node to traverse.
  152. * @param {Object} options The option object.
  153. * @param {Object} [options.visitorKeys=DEFAULT_VISITOR_KEYS] The keys of each node types to traverse child nodes. Default is `./default-visitor-keys.json`.
  154. * @param {Function} [options.enter=noop] The callback function which is called on entering each node.
  155. * @param {Function} [options.leave=noop] The callback function which is called on leaving each node.
  156. * @returns {void}
  157. */
  158. static traverse(node, options) {
  159. new Traverser().traverse(node, options);
  160. }
  161. /**
  162. * The default visitor keys.
  163. * @type {Object}
  164. */
  165. static get DEFAULT_VISITOR_KEYS() {
  166. return vk.KEYS;
  167. }
  168. }
  169. module.exports = Traverser;