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',
128 Property: 'Property',
129 RestElement: 'RestElement',
130 ReturnStatement: 'ReturnStatement',
131 SequenceExpression: 'SequenceExpression',
132 SpreadElement: 'SpreadElement',
134 SwitchStatement: 'SwitchStatement',
135 SwitchCase: 'SwitchCase',
136 TaggedTemplateExpression: 'TaggedTemplateExpression',
137 TemplateElement: 'TemplateElement',
138 TemplateLiteral: 'TemplateLiteral',
139 ThisExpression: 'ThisExpression',
140 ThrowStatement: 'ThrowStatement',
141 TryStatement: 'TryStatement',
142 UnaryExpression: 'UnaryExpression',
143 UpdateExpression: 'UpdateExpression',
144 VariableDeclaration: 'VariableDeclaration',
145 VariableDeclarator: 'VariableDeclarator',
146 WhileStatement: 'WhileStatement',
147 WithStatement: 'WithStatement',
148 YieldExpression: 'YieldExpression'
152 AssignmentExpression: ['left', 'right'],
153 AssignmentPattern: ['left', 'right'],
154 ArrayExpression: ['elements'],
155 ArrayPattern: ['elements'],
156 ArrowFunctionExpression: ['params', 'body'],
157 AwaitExpression: ['argument'], // CAUTION: It's deferred to ES7.
158 BlockStatement: ['body'],
159 BinaryExpression: ['left', 'right'],
160 BreakStatement: ['label'],
161 CallExpression: ['callee', 'arguments'],
162 CatchClause: ['param', 'body'],
163 ChainExpression: ['expression'],
165 ClassDeclaration: ['id', 'superClass', 'body'],
166 ClassExpression: ['id', 'superClass', 'body'],
167 ComprehensionBlock: ['left', 'right'], // CAUTION: It's deferred to ES7.
168 ComprehensionExpression: ['blocks', 'filter', 'body'], // CAUTION: It's deferred to ES7.
169 ConditionalExpression: ['test', 'consequent', 'alternate'],
170 ContinueStatement: ['label'],
171 DebuggerStatement: [],
172 DirectiveStatement: [],
173 DoWhileStatement: ['body', 'test'],
175 ExportAllDeclaration: ['source'],
176 ExportDefaultDeclaration: ['declaration'],
177 ExportNamedDeclaration: ['declaration', 'specifiers', 'source'],
178 ExportSpecifier: ['exported', 'local'],
179 ExpressionStatement: ['expression'],
180 ForStatement: ['init', 'test', 'update', 'body'],
181 ForInStatement: ['left', 'right', 'body'],
182 ForOfStatement: ['left', 'right', 'body'],
183 FunctionDeclaration: ['id', 'params', 'body'],
184 FunctionExpression: ['id', 'params', 'body'],
185 GeneratorExpression: ['blocks', 'filter', 'body'], // CAUTION: It's deferred to ES7.
187 IfStatement: ['test', 'consequent', 'alternate'],
188 ImportExpression: ['source'],
189 ImportDeclaration: ['specifiers', 'source'],
190 ImportDefaultSpecifier: ['local'],
191 ImportNamespaceSpecifier: ['local'],
192 ImportSpecifier: ['imported', 'local'],
194 LabeledStatement: ['label', 'body'],
195 LogicalExpression: ['left', 'right'],
196 MemberExpression: ['object', 'property'],
197 MetaProperty: ['meta', 'property'],
198 MethodDefinition: ['key', 'value'],
200 NewExpression: ['callee', 'arguments'],
201 ObjectExpression: ['properties'],
202 ObjectPattern: ['properties'],
204 Property: ['key', 'value'],
205 RestElement: [ 'argument' ],
206 ReturnStatement: ['argument'],
207 SequenceExpression: ['expressions'],
208 SpreadElement: ['argument'],
210 SwitchStatement: ['discriminant', 'cases'],
211 SwitchCase: ['test', 'consequent'],
212 TaggedTemplateExpression: ['tag', 'quasi'],
214 TemplateLiteral: ['quasis', 'expressions'],
216 ThrowStatement: ['argument'],
217 TryStatement: ['block', 'handler', 'finalizer'],
218 UnaryExpression: ['argument'],
219 UpdateExpression: ['argument'],
220 VariableDeclaration: ['declarations'],
221 VariableDeclarator: ['id', 'init'],
222 WhileStatement: ['test', 'body'],
223 WithStatement: ['object', 'body'],
224 YieldExpression: ['argument']
238 function Reference(parent, key) {
239 this.parent = parent;
243 Reference.prototype.replace = function replace(node) {
244 this.parent[this.key] = node;
247 Reference.prototype.remove = function remove() {
248 if (Array.isArray(this.parent)) {
249 this.parent.splice(this.key, 1);
257 function Element(node, path, wrap, ref) {
264 function Controller() { }
267 // return property path array from root to current node
268 Controller.prototype.path = function path() {
269 var i, iz, j, jz, result, element;
271 function addToPath(result, path) {
272 if (Array.isArray(path)) {
273 for (j = 0, jz = path.length; j < jz; ++j) {
274 result.push(path[j]);
282 if (!this.__current.path) {
286 // first node is sentinel, second node is root element
288 for (i = 2, iz = this.__leavelist.length; i < iz; ++i) {
289 element = this.__leavelist[i];
290 addToPath(result, element.path);
292 addToPath(result, this.__current.path);
297 // return type of current node
298 Controller.prototype.type = function () {
299 var node = this.current();
300 return node.type || this.__current.wrap;
304 // return array of parent elements
305 Controller.prototype.parents = function parents() {
308 // first node is sentinel
310 for (i = 1, iz = this.__leavelist.length; i < iz; ++i) {
311 result.push(this.__leavelist[i].node);
318 // return current node
319 Controller.prototype.current = function current() {
320 return this.__current.node;
323 Controller.prototype.__execute = function __execute(callback, element) {
324 var previous, result;
328 previous = this.__current;
329 this.__current = element;
332 result = callback.call(this, element.node, this.__leavelist[this.__leavelist.length - 1].node);
334 this.__current = previous;
340 // notify control skip / break
341 Controller.prototype.notify = function notify(flag) {
346 // skip child nodes of current node
347 Controller.prototype.skip = function () {
353 Controller.prototype['break'] = function () {
359 Controller.prototype.remove = function () {
363 Controller.prototype.__initialize = function(root, visitor) {
364 this.visitor = visitor;
366 this.__worklist = [];
367 this.__leavelist = [];
368 this.__current = null;
370 this.__fallback = null;
371 if (visitor.fallback === 'iteration') {
372 this.__fallback = Object.keys;
373 } else if (typeof visitor.fallback === 'function') {
374 this.__fallback = visitor.fallback;
377 this.__keys = VisitorKeys;
379 this.__keys = Object.assign(Object.create(this.__keys), visitor.keys);
383 function isNode(node) {
387 return typeof node === 'object' && typeof node.type === 'string';
390 function isProperty(nodeType, key) {
391 return (nodeType === Syntax.ObjectExpression || nodeType === Syntax.ObjectPattern) && 'properties' === key;
394 function candidateExistsInLeaveList(leavelist, candidate) {
395 for (var i = leavelist.length - 1; i >= 0; --i) {
396 if (leavelist[i].node === candidate) {
403 Controller.prototype.traverse = function traverse(root, visitor) {
417 this.__initialize(root, visitor);
422 worklist = this.__worklist;
423 leavelist = this.__leavelist;
426 worklist.push(new Element(root, null, null, null));
427 leavelist.push(new Element(null, null, null, null));
429 while (worklist.length) {
430 element = worklist.pop();
432 if (element === sentinel) {
433 element = leavelist.pop();
435 ret = this.__execute(visitor.leave, element);
437 if (this.__state === BREAK || ret === BREAK) {
445 ret = this.__execute(visitor.enter, element);
447 if (this.__state === BREAK || ret === BREAK) {
451 worklist.push(sentinel);
452 leavelist.push(element);
454 if (this.__state === SKIP || ret === SKIP) {
459 nodeType = node.type || element.wrap;
460 candidates = this.__keys[nodeType];
462 if (this.__fallback) {
463 candidates = this.__fallback(node);
465 throw new Error('Unknown node type ' + nodeType + '.');
469 current = candidates.length;
470 while ((current -= 1) >= 0) {
471 key = candidates[current];
472 candidate = node[key];
477 if (Array.isArray(candidate)) {
478 current2 = candidate.length;
479 while ((current2 -= 1) >= 0) {
480 if (!candidate[current2]) {
484 if (candidateExistsInLeaveList(leavelist, candidate[current2])) {
488 if (isProperty(nodeType, candidates[current])) {
489 element = new Element(candidate[current2], [key, current2], 'Property', null);
490 } else if (isNode(candidate[current2])) {
491 element = new Element(candidate[current2], [key, current2], null, null);
495 worklist.push(element);
497 } else if (isNode(candidate)) {
498 if (candidateExistsInLeaveList(leavelist, candidate)) {
502 worklist.push(new Element(candidate, key, null, null));
509 Controller.prototype.replace = function replace(root, visitor) {
524 function removeElem(element) {
530 if (element.ref.remove()) {
531 // When the reference is an element of an array.
532 key = element.ref.key;
533 parent = element.ref.parent;
535 // If removed from array, then decrease following items' keys.
538 nextElem = worklist[i];
539 if (nextElem.ref && nextElem.ref.parent === parent) {
540 if (nextElem.ref.key < key) {
549 this.__initialize(root, visitor);
554 worklist = this.__worklist;
555 leavelist = this.__leavelist;
561 element = new Element(root, null, null, new Reference(outer, 'root'));
562 worklist.push(element);
563 leavelist.push(element);
565 while (worklist.length) {
566 element = worklist.pop();
568 if (element === sentinel) {
569 element = leavelist.pop();
571 target = this.__execute(visitor.leave, element);
573 // node may be replaced with null,
574 // so distinguish between undefined and null in this place
575 if (target !== undefined && target !== BREAK && target !== SKIP && target !== REMOVE) {
577 element.ref.replace(target);
580 if (this.__state === REMOVE || target === REMOVE) {
584 if (this.__state === BREAK || target === BREAK) {
590 target = this.__execute(visitor.enter, element);
592 // node may be replaced with null,
593 // so distinguish between undefined and null in this place
594 if (target !== undefined && target !== BREAK && target !== SKIP && target !== REMOVE) {
596 element.ref.replace(target);
597 element.node = target;
600 if (this.__state === REMOVE || target === REMOVE) {
605 if (this.__state === BREAK || target === BREAK) {
615 worklist.push(sentinel);
616 leavelist.push(element);
618 if (this.__state === SKIP || target === SKIP) {
622 nodeType = node.type || element.wrap;
623 candidates = this.__keys[nodeType];
625 if (this.__fallback) {
626 candidates = this.__fallback(node);
628 throw new Error('Unknown node type ' + nodeType + '.');
632 current = candidates.length;
633 while ((current -= 1) >= 0) {
634 key = candidates[current];
635 candidate = node[key];
640 if (Array.isArray(candidate)) {
641 current2 = candidate.length;
642 while ((current2 -= 1) >= 0) {
643 if (!candidate[current2]) {
646 if (isProperty(nodeType, candidates[current])) {
647 element = new Element(candidate[current2], [key, current2], 'Property', new Reference(candidate, current2));
648 } else if (isNode(candidate[current2])) {
649 element = new Element(candidate[current2], [key, current2], null, new Reference(candidate, current2));
653 worklist.push(element);
655 } else if (isNode(candidate)) {
656 worklist.push(new Element(candidate, key, null, new Reference(node, key)));
664 function traverse(root, visitor) {
665 var controller = new Controller();
666 return controller.traverse(root, visitor);
669 function replace(root, visitor) {
670 var controller = new Controller();
671 return controller.replace(root, visitor);
674 function extendCommentRange(comment, tokens) {
677 target = upperBound(tokens, function search(token) {
678 return token.range[0] > comment.range[0];
681 comment.extendedRange = [comment.range[0], comment.range[1]];
683 if (target !== tokens.length) {
684 comment.extendedRange[1] = tokens[target].range[0];
689 comment.extendedRange[0] = tokens[target].range[1];
695 function attachComments(tree, providedComments, tokens) {
696 // At first, we should calculate extended comment ranges.
697 var comments = [], comment, len, i, cursor;
700 throw new Error('attachComments needs range information');
703 // tokens array is empty, we attach comments to tree as 'leadingComments'
704 if (!tokens.length) {
705 if (providedComments.length) {
706 for (i = 0, len = providedComments.length; i < len; i += 1) {
707 comment = deepCopy(providedComments[i]);
708 comment.extendedRange = [0, tree.range[0]];
709 comments.push(comment);
711 tree.leadingComments = comments;
716 for (i = 0, len = providedComments.length; i < len; i += 1) {
717 comments.push(extendCommentRange(deepCopy(providedComments[i]), tokens));
720 // This is based on John Freeman's implementation.
723 enter: function (node) {
726 while (cursor < comments.length) {
727 comment = comments[cursor];
728 if (comment.extendedRange[1] > node.range[0]) {
732 if (comment.extendedRange[1] === node.range[0]) {
733 if (!node.leadingComments) {
734 node.leadingComments = [];
736 node.leadingComments.push(comment);
737 comments.splice(cursor, 1);
743 // already out of owned node
744 if (cursor === comments.length) {
745 return VisitorOption.Break;
748 if (comments[cursor].extendedRange[0] > node.range[1]) {
749 return VisitorOption.Skip;
756 leave: function (node) {
759 while (cursor < comments.length) {
760 comment = comments[cursor];
761 if (node.range[1] < comment.extendedRange[0]) {
765 if (node.range[1] === comment.extendedRange[0]) {
766 if (!node.trailingComments) {
767 node.trailingComments = [];
769 node.trailingComments.push(comment);
770 comments.splice(cursor, 1);
776 // already out of owned node
777 if (cursor === comments.length) {
778 return VisitorOption.Break;
781 if (comments[cursor].extendedRange[0] > node.range[1]) {
782 return VisitorOption.Skip;
790 exports.Syntax = Syntax;
791 exports.traverse = traverse;
792 exports.replace = replace;
793 exports.attachComments = attachComments;
794 exports.VisitorKeys = VisitorKeys;
795 exports.VisitorOption = VisitorOption;
796 exports.Controller = Controller;
797 exports.cloneEnvironment = function () { return clone({}); };
801 /* vim: set sw=4 ts=4 et tw=80 : */