2 Copyright (C) 2012-2013 Yusuke Suzuki <utatane.tea@gmail.com>
3 Copyright (C) 2012 Ariya Hidayat <ariya.hidayat@gmail.com>
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are met:
8 * Redistributions of source code must retain the above copyright
9 notice, this list of conditions and the following disclaimer.
10 * Redistributions in binary form must reproduce the above copyright
11 notice, this list of conditions and the following disclaimer in the
12 documentation and/or other materials provided with the distribution.
14 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
15 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 ARE DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
18 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
19 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
20 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
21 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 /*jslint vars:false, bitwise:true*/
27 /*global exports:true*/
28 (function clone(exports) {
38 function deepCopy(obj) {
39 var ret = {}, key, val;
41 if (obj.hasOwnProperty(key)) {
43 if (typeof val === 'object' && val !== null) {
44 ret[key] = deepCopy(val);
53 // based on LLVM libc++ upper_bound / lower_bound
56 function upperBound(array, func) {
57 var diff, len, i, current;
65 if (func(array[current])) {
76 AssignmentExpression: 'AssignmentExpression',
77 AssignmentPattern: 'AssignmentPattern',
78 ArrayExpression: 'ArrayExpression',
79 ArrayPattern: 'ArrayPattern',
80 ArrowFunctionExpression: 'ArrowFunctionExpression',
81 AwaitExpression: 'AwaitExpression', // CAUTION: It's deferred to ES7.
82 BlockStatement: 'BlockStatement',
83 BinaryExpression: 'BinaryExpression',
84 BreakStatement: 'BreakStatement',
85 CallExpression: 'CallExpression',
86 CatchClause: 'CatchClause',
87 ChainExpression: 'ChainExpression',
88 ClassBody: 'ClassBody',
89 ClassDeclaration: 'ClassDeclaration',
90 ClassExpression: 'ClassExpression',
91 ComprehensionBlock: 'ComprehensionBlock', // CAUTION: It's deferred to ES7.
92 ComprehensionExpression: 'ComprehensionExpression', // CAUTION: It's deferred to ES7.
93 ConditionalExpression: 'ConditionalExpression',
94 ContinueStatement: 'ContinueStatement',
95 DebuggerStatement: 'DebuggerStatement',
96 DirectiveStatement: 'DirectiveStatement',
97 DoWhileStatement: 'DoWhileStatement',
98 EmptyStatement: 'EmptyStatement',
99 ExportAllDeclaration: 'ExportAllDeclaration',
100 ExportDefaultDeclaration: 'ExportDefaultDeclaration',
101 ExportNamedDeclaration: 'ExportNamedDeclaration',
102 ExportSpecifier: 'ExportSpecifier',
103 ExpressionStatement: 'ExpressionStatement',
104 ForStatement: 'ForStatement',
105 ForInStatement: 'ForInStatement',
106 ForOfStatement: 'ForOfStatement',
107 FunctionDeclaration: 'FunctionDeclaration',
108 FunctionExpression: 'FunctionExpression',
109 GeneratorExpression: 'GeneratorExpression', // CAUTION: It's deferred to ES7.
110 Identifier: 'Identifier',
111 IfStatement: 'IfStatement',
112 ImportExpression: 'ImportExpression',
113 ImportDeclaration: 'ImportDeclaration',
114 ImportDefaultSpecifier: 'ImportDefaultSpecifier',
115 ImportNamespaceSpecifier: 'ImportNamespaceSpecifier',
116 ImportSpecifier: 'ImportSpecifier',
118 LabeledStatement: 'LabeledStatement',
119 LogicalExpression: 'LogicalExpression',
120 MemberExpression: 'MemberExpression',
121 MetaProperty: 'MetaProperty',
122 MethodDefinition: 'MethodDefinition',
123 ModuleSpecifier: 'ModuleSpecifier',
124 NewExpression: 'NewExpression',
125 ObjectExpression: 'ObjectExpression',
126 ObjectPattern: 'ObjectPattern',
127 PrivateIdentifier: 'PrivateIdentifier',
129 Property: 'Property',
130 PropertyDefinition: 'PropertyDefinition',
131 RestElement: 'RestElement',
132 ReturnStatement: 'ReturnStatement',
133 SequenceExpression: 'SequenceExpression',
134 SpreadElement: 'SpreadElement',
136 SwitchStatement: 'SwitchStatement',
137 SwitchCase: 'SwitchCase',
138 TaggedTemplateExpression: 'TaggedTemplateExpression',
139 TemplateElement: 'TemplateElement',
140 TemplateLiteral: 'TemplateLiteral',
141 ThisExpression: 'ThisExpression',
142 ThrowStatement: 'ThrowStatement',
143 TryStatement: 'TryStatement',
144 UnaryExpression: 'UnaryExpression',
145 UpdateExpression: 'UpdateExpression',
146 VariableDeclaration: 'VariableDeclaration',
147 VariableDeclarator: 'VariableDeclarator',
148 WhileStatement: 'WhileStatement',
149 WithStatement: 'WithStatement',
150 YieldExpression: 'YieldExpression'
154 AssignmentExpression: ['left', 'right'],
155 AssignmentPattern: ['left', 'right'],
156 ArrayExpression: ['elements'],
157 ArrayPattern: ['elements'],
158 ArrowFunctionExpression: ['params', 'body'],
159 AwaitExpression: ['argument'], // CAUTION: It's deferred to ES7.
160 BlockStatement: ['body'],
161 BinaryExpression: ['left', 'right'],
162 BreakStatement: ['label'],
163 CallExpression: ['callee', 'arguments'],
164 CatchClause: ['param', 'body'],
165 ChainExpression: ['expression'],
167 ClassDeclaration: ['id', 'superClass', 'body'],
168 ClassExpression: ['id', 'superClass', 'body'],
169 ComprehensionBlock: ['left', 'right'], // CAUTION: It's deferred to ES7.
170 ComprehensionExpression: ['blocks', 'filter', 'body'], // CAUTION: It's deferred to ES7.
171 ConditionalExpression: ['test', 'consequent', 'alternate'],
172 ContinueStatement: ['label'],
173 DebuggerStatement: [],
174 DirectiveStatement: [],
175 DoWhileStatement: ['body', 'test'],
177 ExportAllDeclaration: ['source'],
178 ExportDefaultDeclaration: ['declaration'],
179 ExportNamedDeclaration: ['declaration', 'specifiers', 'source'],
180 ExportSpecifier: ['exported', 'local'],
181 ExpressionStatement: ['expression'],
182 ForStatement: ['init', 'test', 'update', 'body'],
183 ForInStatement: ['left', 'right', 'body'],
184 ForOfStatement: ['left', 'right', 'body'],
185 FunctionDeclaration: ['id', 'params', 'body'],
186 FunctionExpression: ['id', 'params', 'body'],
187 GeneratorExpression: ['blocks', 'filter', 'body'], // CAUTION: It's deferred to ES7.
189 IfStatement: ['test', 'consequent', 'alternate'],
190 ImportExpression: ['source'],
191 ImportDeclaration: ['specifiers', 'source'],
192 ImportDefaultSpecifier: ['local'],
193 ImportNamespaceSpecifier: ['local'],
194 ImportSpecifier: ['imported', 'local'],
196 LabeledStatement: ['label', 'body'],
197 LogicalExpression: ['left', 'right'],
198 MemberExpression: ['object', 'property'],
199 MetaProperty: ['meta', 'property'],
200 MethodDefinition: ['key', 'value'],
202 NewExpression: ['callee', 'arguments'],
203 ObjectExpression: ['properties'],
204 ObjectPattern: ['properties'],
205 PrivateIdentifier: [],
207 Property: ['key', 'value'],
208 PropertyDefinition: ['key', 'value'],
209 RestElement: [ 'argument' ],
210 ReturnStatement: ['argument'],
211 SequenceExpression: ['expressions'],
212 SpreadElement: ['argument'],
214 SwitchStatement: ['discriminant', 'cases'],
215 SwitchCase: ['test', 'consequent'],
216 TaggedTemplateExpression: ['tag', 'quasi'],
218 TemplateLiteral: ['quasis', 'expressions'],
220 ThrowStatement: ['argument'],
221 TryStatement: ['block', 'handler', 'finalizer'],
222 UnaryExpression: ['argument'],
223 UpdateExpression: ['argument'],
224 VariableDeclaration: ['declarations'],
225 VariableDeclarator: ['id', 'init'],
226 WhileStatement: ['test', 'body'],
227 WithStatement: ['object', 'body'],
228 YieldExpression: ['argument']
242 function Reference(parent, key) {
243 this.parent = parent;
247 Reference.prototype.replace = function replace(node) {
248 this.parent[this.key] = node;
251 Reference.prototype.remove = function remove() {
252 if (Array.isArray(this.parent)) {
253 this.parent.splice(this.key, 1);
261 function Element(node, path, wrap, ref) {
268 function Controller() { }
271 // return property path array from root to current node
272 Controller.prototype.path = function path() {
273 var i, iz, j, jz, result, element;
275 function addToPath(result, path) {
276 if (Array.isArray(path)) {
277 for (j = 0, jz = path.length; j < jz; ++j) {
278 result.push(path[j]);
286 if (!this.__current.path) {
290 // first node is sentinel, second node is root element
292 for (i = 2, iz = this.__leavelist.length; i < iz; ++i) {
293 element = this.__leavelist[i];
294 addToPath(result, element.path);
296 addToPath(result, this.__current.path);
301 // return type of current node
302 Controller.prototype.type = function () {
303 var node = this.current();
304 return node.type || this.__current.wrap;
308 // return array of parent elements
309 Controller.prototype.parents = function parents() {
312 // first node is sentinel
314 for (i = 1, iz = this.__leavelist.length; i < iz; ++i) {
315 result.push(this.__leavelist[i].node);
322 // return current node
323 Controller.prototype.current = function current() {
324 return this.__current.node;
327 Controller.prototype.__execute = function __execute(callback, element) {
328 var previous, result;
332 previous = this.__current;
333 this.__current = element;
336 result = callback.call(this, element.node, this.__leavelist[this.__leavelist.length - 1].node);
338 this.__current = previous;
344 // notify control skip / break
345 Controller.prototype.notify = function notify(flag) {
350 // skip child nodes of current node
351 Controller.prototype.skip = function () {
357 Controller.prototype['break'] = function () {
363 Controller.prototype.remove = function () {
367 Controller.prototype.__initialize = function(root, visitor) {
368 this.visitor = visitor;
370 this.__worklist = [];
371 this.__leavelist = [];
372 this.__current = null;
374 this.__fallback = null;
375 if (visitor.fallback === 'iteration') {
376 this.__fallback = Object.keys;
377 } else if (typeof visitor.fallback === 'function') {
378 this.__fallback = visitor.fallback;
381 this.__keys = VisitorKeys;
383 this.__keys = Object.assign(Object.create(this.__keys), visitor.keys);
387 function isNode(node) {
391 return typeof node === 'object' && typeof node.type === 'string';
394 function isProperty(nodeType, key) {
395 return (nodeType === Syntax.ObjectExpression || nodeType === Syntax.ObjectPattern) && 'properties' === key;
398 function candidateExistsInLeaveList(leavelist, candidate) {
399 for (var i = leavelist.length - 1; i >= 0; --i) {
400 if (leavelist[i].node === candidate) {
407 Controller.prototype.traverse = function traverse(root, visitor) {
421 this.__initialize(root, visitor);
426 worklist = this.__worklist;
427 leavelist = this.__leavelist;
430 worklist.push(new Element(root, null, null, null));
431 leavelist.push(new Element(null, null, null, null));
433 while (worklist.length) {
434 element = worklist.pop();
436 if (element === sentinel) {
437 element = leavelist.pop();
439 ret = this.__execute(visitor.leave, element);
441 if (this.__state === BREAK || ret === BREAK) {
449 ret = this.__execute(visitor.enter, element);
451 if (this.__state === BREAK || ret === BREAK) {
455 worklist.push(sentinel);
456 leavelist.push(element);
458 if (this.__state === SKIP || ret === SKIP) {
463 nodeType = node.type || element.wrap;
464 candidates = this.__keys[nodeType];
466 if (this.__fallback) {
467 candidates = this.__fallback(node);
469 throw new Error('Unknown node type ' + nodeType + '.');
473 current = candidates.length;
474 while ((current -= 1) >= 0) {
475 key = candidates[current];
476 candidate = node[key];
481 if (Array.isArray(candidate)) {
482 current2 = candidate.length;
483 while ((current2 -= 1) >= 0) {
484 if (!candidate[current2]) {
488 if (candidateExistsInLeaveList(leavelist, candidate[current2])) {
492 if (isProperty(nodeType, candidates[current])) {
493 element = new Element(candidate[current2], [key, current2], 'Property', null);
494 } else if (isNode(candidate[current2])) {
495 element = new Element(candidate[current2], [key, current2], null, null);
499 worklist.push(element);
501 } else if (isNode(candidate)) {
502 if (candidateExistsInLeaveList(leavelist, candidate)) {
506 worklist.push(new Element(candidate, key, null, null));
513 Controller.prototype.replace = function replace(root, visitor) {
528 function removeElem(element) {
534 if (element.ref.remove()) {
535 // When the reference is an element of an array.
536 key = element.ref.key;
537 parent = element.ref.parent;
539 // If removed from array, then decrease following items' keys.
542 nextElem = worklist[i];
543 if (nextElem.ref && nextElem.ref.parent === parent) {
544 if (nextElem.ref.key < key) {
553 this.__initialize(root, visitor);
558 worklist = this.__worklist;
559 leavelist = this.__leavelist;
565 element = new Element(root, null, null, new Reference(outer, 'root'));
566 worklist.push(element);
567 leavelist.push(element);
569 while (worklist.length) {
570 element = worklist.pop();
572 if (element === sentinel) {
573 element = leavelist.pop();
575 target = this.__execute(visitor.leave, element);
577 // node may be replaced with null,
578 // so distinguish between undefined and null in this place
579 if (target !== undefined && target !== BREAK && target !== SKIP && target !== REMOVE) {
581 element.ref.replace(target);
584 if (this.__state === REMOVE || target === REMOVE) {
588 if (this.__state === BREAK || target === BREAK) {
594 target = this.__execute(visitor.enter, element);
596 // node may be replaced with null,
597 // so distinguish between undefined and null in this place
598 if (target !== undefined && target !== BREAK && target !== SKIP && target !== REMOVE) {
600 element.ref.replace(target);
601 element.node = target;
604 if (this.__state === REMOVE || target === REMOVE) {
609 if (this.__state === BREAK || target === BREAK) {
619 worklist.push(sentinel);
620 leavelist.push(element);
622 if (this.__state === SKIP || target === SKIP) {
626 nodeType = node.type || element.wrap;
627 candidates = this.__keys[nodeType];
629 if (this.__fallback) {
630 candidates = this.__fallback(node);
632 throw new Error('Unknown node type ' + nodeType + '.');
636 current = candidates.length;
637 while ((current -= 1) >= 0) {
638 key = candidates[current];
639 candidate = node[key];
644 if (Array.isArray(candidate)) {
645 current2 = candidate.length;
646 while ((current2 -= 1) >= 0) {
647 if (!candidate[current2]) {
650 if (isProperty(nodeType, candidates[current])) {
651 element = new Element(candidate[current2], [key, current2], 'Property', new Reference(candidate, current2));
652 } else if (isNode(candidate[current2])) {
653 element = new Element(candidate[current2], [key, current2], null, new Reference(candidate, current2));
657 worklist.push(element);
659 } else if (isNode(candidate)) {
660 worklist.push(new Element(candidate, key, null, new Reference(node, key)));
668 function traverse(root, visitor) {
669 var controller = new Controller();
670 return controller.traverse(root, visitor);
673 function replace(root, visitor) {
674 var controller = new Controller();
675 return controller.replace(root, visitor);
678 function extendCommentRange(comment, tokens) {
681 target = upperBound(tokens, function search(token) {
682 return token.range[0] > comment.range[0];
685 comment.extendedRange = [comment.range[0], comment.range[1]];
687 if (target !== tokens.length) {
688 comment.extendedRange[1] = tokens[target].range[0];
693 comment.extendedRange[0] = tokens[target].range[1];
699 function attachComments(tree, providedComments, tokens) {
700 // At first, we should calculate extended comment ranges.
701 var comments = [], comment, len, i, cursor;
704 throw new Error('attachComments needs range information');
707 // tokens array is empty, we attach comments to tree as 'leadingComments'
708 if (!tokens.length) {
709 if (providedComments.length) {
710 for (i = 0, len = providedComments.length; i < len; i += 1) {
711 comment = deepCopy(providedComments[i]);
712 comment.extendedRange = [0, tree.range[0]];
713 comments.push(comment);
715 tree.leadingComments = comments;
720 for (i = 0, len = providedComments.length; i < len; i += 1) {
721 comments.push(extendCommentRange(deepCopy(providedComments[i]), tokens));
724 // This is based on John Freeman's implementation.
727 enter: function (node) {
730 while (cursor < comments.length) {
731 comment = comments[cursor];
732 if (comment.extendedRange[1] > node.range[0]) {
736 if (comment.extendedRange[1] === node.range[0]) {
737 if (!node.leadingComments) {
738 node.leadingComments = [];
740 node.leadingComments.push(comment);
741 comments.splice(cursor, 1);
747 // already out of owned node
748 if (cursor === comments.length) {
749 return VisitorOption.Break;
752 if (comments[cursor].extendedRange[0] > node.range[1]) {
753 return VisitorOption.Skip;
760 leave: function (node) {
763 while (cursor < comments.length) {
764 comment = comments[cursor];
765 if (node.range[1] < comment.extendedRange[0]) {
769 if (node.range[1] === comment.extendedRange[0]) {
770 if (!node.trailingComments) {
771 node.trailingComments = [];
773 node.trailingComments.push(comment);
774 comments.splice(cursor, 1);
780 // already out of owned node
781 if (cursor === comments.length) {
782 return VisitorOption.Break;
785 if (comments[cursor].extendedRange[0] > node.range[1]) {
786 return VisitorOption.Skip;
794 exports.Syntax = Syntax;
795 exports.traverse = traverse;
796 exports.replace = replace;
797 exports.attachComments = attachComments;
798 exports.VisitorKeys = VisitorKeys;
799 exports.VisitorOption = VisitorOption;
800 exports.Controller = Controller;
801 exports.cloneEnvironment = function () { return clone({}); };
805 /* vim: set sw=4 ts=4 et tw=80 : */