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 ClassBody: 'ClassBody',
88 ClassDeclaration: 'ClassDeclaration',
89 ClassExpression: 'ClassExpression',
90 ComprehensionBlock: 'ComprehensionBlock', // CAUTION: It's deferred to ES7.
91 ComprehensionExpression: 'ComprehensionExpression', // CAUTION: It's deferred to ES7.
92 ConditionalExpression: 'ConditionalExpression',
93 ContinueStatement: 'ContinueStatement',
94 DebuggerStatement: 'DebuggerStatement',
95 DirectiveStatement: 'DirectiveStatement',
96 DoWhileStatement: 'DoWhileStatement',
97 EmptyStatement: 'EmptyStatement',
98 ExportAllDeclaration: 'ExportAllDeclaration',
99 ExportDefaultDeclaration: 'ExportDefaultDeclaration',
100 ExportNamedDeclaration: 'ExportNamedDeclaration',
101 ExportSpecifier: 'ExportSpecifier',
102 ExpressionStatement: 'ExpressionStatement',
103 ForStatement: 'ForStatement',
104 ForInStatement: 'ForInStatement',
105 ForOfStatement: 'ForOfStatement',
106 FunctionDeclaration: 'FunctionDeclaration',
107 FunctionExpression: 'FunctionExpression',
108 GeneratorExpression: 'GeneratorExpression', // CAUTION: It's deferred to ES7.
109 Identifier: 'Identifier',
110 IfStatement: 'IfStatement',
111 ImportExpression: 'ImportExpression',
112 ImportDeclaration: 'ImportDeclaration',
113 ImportDefaultSpecifier: 'ImportDefaultSpecifier',
114 ImportNamespaceSpecifier: 'ImportNamespaceSpecifier',
115 ImportSpecifier: 'ImportSpecifier',
117 LabeledStatement: 'LabeledStatement',
118 LogicalExpression: 'LogicalExpression',
119 MemberExpression: 'MemberExpression',
120 MetaProperty: 'MetaProperty',
121 MethodDefinition: 'MethodDefinition',
122 ModuleSpecifier: 'ModuleSpecifier',
123 NewExpression: 'NewExpression',
124 ObjectExpression: 'ObjectExpression',
125 ObjectPattern: 'ObjectPattern',
127 Property: 'Property',
128 RestElement: 'RestElement',
129 ReturnStatement: 'ReturnStatement',
130 SequenceExpression: 'SequenceExpression',
131 SpreadElement: 'SpreadElement',
133 SwitchStatement: 'SwitchStatement',
134 SwitchCase: 'SwitchCase',
135 TaggedTemplateExpression: 'TaggedTemplateExpression',
136 TemplateElement: 'TemplateElement',
137 TemplateLiteral: 'TemplateLiteral',
138 ThisExpression: 'ThisExpression',
139 ThrowStatement: 'ThrowStatement',
140 TryStatement: 'TryStatement',
141 UnaryExpression: 'UnaryExpression',
142 UpdateExpression: 'UpdateExpression',
143 VariableDeclaration: 'VariableDeclaration',
144 VariableDeclarator: 'VariableDeclarator',
145 WhileStatement: 'WhileStatement',
146 WithStatement: 'WithStatement',
147 YieldExpression: 'YieldExpression'
151 AssignmentExpression: ['left', 'right'],
152 AssignmentPattern: ['left', 'right'],
153 ArrayExpression: ['elements'],
154 ArrayPattern: ['elements'],
155 ArrowFunctionExpression: ['params', 'body'],
156 AwaitExpression: ['argument'], // CAUTION: It's deferred to ES7.
157 BlockStatement: ['body'],
158 BinaryExpression: ['left', 'right'],
159 BreakStatement: ['label'],
160 CallExpression: ['callee', 'arguments'],
161 CatchClause: ['param', 'body'],
163 ClassDeclaration: ['id', 'superClass', 'body'],
164 ClassExpression: ['id', 'superClass', 'body'],
165 ComprehensionBlock: ['left', 'right'], // CAUTION: It's deferred to ES7.
166 ComprehensionExpression: ['blocks', 'filter', 'body'], // CAUTION: It's deferred to ES7.
167 ConditionalExpression: ['test', 'consequent', 'alternate'],
168 ContinueStatement: ['label'],
169 DebuggerStatement: [],
170 DirectiveStatement: [],
171 DoWhileStatement: ['body', 'test'],
173 ExportAllDeclaration: ['source'],
174 ExportDefaultDeclaration: ['declaration'],
175 ExportNamedDeclaration: ['declaration', 'specifiers', 'source'],
176 ExportSpecifier: ['exported', 'local'],
177 ExpressionStatement: ['expression'],
178 ForStatement: ['init', 'test', 'update', 'body'],
179 ForInStatement: ['left', 'right', 'body'],
180 ForOfStatement: ['left', 'right', 'body'],
181 FunctionDeclaration: ['id', 'params', 'body'],
182 FunctionExpression: ['id', 'params', 'body'],
183 GeneratorExpression: ['blocks', 'filter', 'body'], // CAUTION: It's deferred to ES7.
185 IfStatement: ['test', 'consequent', 'alternate'],
186 ImportExpression: ['source'],
187 ImportDeclaration: ['specifiers', 'source'],
188 ImportDefaultSpecifier: ['local'],
189 ImportNamespaceSpecifier: ['local'],
190 ImportSpecifier: ['imported', 'local'],
192 LabeledStatement: ['label', 'body'],
193 LogicalExpression: ['left', 'right'],
194 MemberExpression: ['object', 'property'],
195 MetaProperty: ['meta', 'property'],
196 MethodDefinition: ['key', 'value'],
198 NewExpression: ['callee', 'arguments'],
199 ObjectExpression: ['properties'],
200 ObjectPattern: ['properties'],
202 Property: ['key', 'value'],
203 RestElement: [ 'argument' ],
204 ReturnStatement: ['argument'],
205 SequenceExpression: ['expressions'],
206 SpreadElement: ['argument'],
208 SwitchStatement: ['discriminant', 'cases'],
209 SwitchCase: ['test', 'consequent'],
210 TaggedTemplateExpression: ['tag', 'quasi'],
212 TemplateLiteral: ['quasis', 'expressions'],
214 ThrowStatement: ['argument'],
215 TryStatement: ['block', 'handler', 'finalizer'],
216 UnaryExpression: ['argument'],
217 UpdateExpression: ['argument'],
218 VariableDeclaration: ['declarations'],
219 VariableDeclarator: ['id', 'init'],
220 WhileStatement: ['test', 'body'],
221 WithStatement: ['object', 'body'],
222 YieldExpression: ['argument']
236 function Reference(parent, key) {
237 this.parent = parent;
241 Reference.prototype.replace = function replace(node) {
242 this.parent[this.key] = node;
245 Reference.prototype.remove = function remove() {
246 if (Array.isArray(this.parent)) {
247 this.parent.splice(this.key, 1);
255 function Element(node, path, wrap, ref) {
262 function Controller() { }
265 // return property path array from root to current node
266 Controller.prototype.path = function path() {
267 var i, iz, j, jz, result, element;
269 function addToPath(result, path) {
270 if (Array.isArray(path)) {
271 for (j = 0, jz = path.length; j < jz; ++j) {
272 result.push(path[j]);
280 if (!this.__current.path) {
284 // first node is sentinel, second node is root element
286 for (i = 2, iz = this.__leavelist.length; i < iz; ++i) {
287 element = this.__leavelist[i];
288 addToPath(result, element.path);
290 addToPath(result, this.__current.path);
295 // return type of current node
296 Controller.prototype.type = function () {
297 var node = this.current();
298 return node.type || this.__current.wrap;
302 // return array of parent elements
303 Controller.prototype.parents = function parents() {
306 // first node is sentinel
308 for (i = 1, iz = this.__leavelist.length; i < iz; ++i) {
309 result.push(this.__leavelist[i].node);
316 // return current node
317 Controller.prototype.current = function current() {
318 return this.__current.node;
321 Controller.prototype.__execute = function __execute(callback, element) {
322 var previous, result;
326 previous = this.__current;
327 this.__current = element;
330 result = callback.call(this, element.node, this.__leavelist[this.__leavelist.length - 1].node);
332 this.__current = previous;
338 // notify control skip / break
339 Controller.prototype.notify = function notify(flag) {
344 // skip child nodes of current node
345 Controller.prototype.skip = function () {
351 Controller.prototype['break'] = function () {
357 Controller.prototype.remove = function () {
361 Controller.prototype.__initialize = function(root, visitor) {
362 this.visitor = visitor;
364 this.__worklist = [];
365 this.__leavelist = [];
366 this.__current = null;
368 this.__fallback = null;
369 if (visitor.fallback === 'iteration') {
370 this.__fallback = Object.keys;
371 } else if (typeof visitor.fallback === 'function') {
372 this.__fallback = visitor.fallback;
375 this.__keys = VisitorKeys;
377 this.__keys = Object.assign(Object.create(this.__keys), visitor.keys);
381 function isNode(node) {
385 return typeof node === 'object' && typeof node.type === 'string';
388 function isProperty(nodeType, key) {
389 return (nodeType === Syntax.ObjectExpression || nodeType === Syntax.ObjectPattern) && 'properties' === key;
392 function candidateExistsInLeaveList(leavelist, candidate) {
393 for (var i = leavelist.length - 1; i >= 0; --i) {
394 if (leavelist[i].node === candidate) {
401 Controller.prototype.traverse = function traverse(root, visitor) {
415 this.__initialize(root, visitor);
420 worklist = this.__worklist;
421 leavelist = this.__leavelist;
424 worklist.push(new Element(root, null, null, null));
425 leavelist.push(new Element(null, null, null, null));
427 while (worklist.length) {
428 element = worklist.pop();
430 if (element === sentinel) {
431 element = leavelist.pop();
433 ret = this.__execute(visitor.leave, element);
435 if (this.__state === BREAK || ret === BREAK) {
443 ret = this.__execute(visitor.enter, element);
445 if (this.__state === BREAK || ret === BREAK) {
449 worklist.push(sentinel);
450 leavelist.push(element);
452 if (this.__state === SKIP || ret === SKIP) {
457 nodeType = node.type || element.wrap;
458 candidates = this.__keys[nodeType];
460 if (this.__fallback) {
461 candidates = this.__fallback(node);
463 throw new Error('Unknown node type ' + nodeType + '.');
467 current = candidates.length;
468 while ((current -= 1) >= 0) {
469 key = candidates[current];
470 candidate = node[key];
475 if (Array.isArray(candidate)) {
476 current2 = candidate.length;
477 while ((current2 -= 1) >= 0) {
478 if (!candidate[current2]) {
482 if (candidateExistsInLeaveList(leavelist, candidate[current2])) {
486 if (isProperty(nodeType, candidates[current])) {
487 element = new Element(candidate[current2], [key, current2], 'Property', null);
488 } else if (isNode(candidate[current2])) {
489 element = new Element(candidate[current2], [key, current2], null, null);
493 worklist.push(element);
495 } else if (isNode(candidate)) {
496 if (candidateExistsInLeaveList(leavelist, candidate)) {
500 worklist.push(new Element(candidate, key, null, null));
507 Controller.prototype.replace = function replace(root, visitor) {
522 function removeElem(element) {
528 if (element.ref.remove()) {
529 // When the reference is an element of an array.
530 key = element.ref.key;
531 parent = element.ref.parent;
533 // If removed from array, then decrease following items' keys.
536 nextElem = worklist[i];
537 if (nextElem.ref && nextElem.ref.parent === parent) {
538 if (nextElem.ref.key < key) {
547 this.__initialize(root, visitor);
552 worklist = this.__worklist;
553 leavelist = this.__leavelist;
559 element = new Element(root, null, null, new Reference(outer, 'root'));
560 worklist.push(element);
561 leavelist.push(element);
563 while (worklist.length) {
564 element = worklist.pop();
566 if (element === sentinel) {
567 element = leavelist.pop();
569 target = this.__execute(visitor.leave, element);
571 // node may be replaced with null,
572 // so distinguish between undefined and null in this place
573 if (target !== undefined && target !== BREAK && target !== SKIP && target !== REMOVE) {
575 element.ref.replace(target);
578 if (this.__state === REMOVE || target === REMOVE) {
582 if (this.__state === BREAK || target === BREAK) {
588 target = this.__execute(visitor.enter, element);
590 // node may be replaced with null,
591 // so distinguish between undefined and null in this place
592 if (target !== undefined && target !== BREAK && target !== SKIP && target !== REMOVE) {
594 element.ref.replace(target);
595 element.node = target;
598 if (this.__state === REMOVE || target === REMOVE) {
603 if (this.__state === BREAK || target === BREAK) {
613 worklist.push(sentinel);
614 leavelist.push(element);
616 if (this.__state === SKIP || target === SKIP) {
620 nodeType = node.type || element.wrap;
621 candidates = this.__keys[nodeType];
623 if (this.__fallback) {
624 candidates = this.__fallback(node);
626 throw new Error('Unknown node type ' + nodeType + '.');
630 current = candidates.length;
631 while ((current -= 1) >= 0) {
632 key = candidates[current];
633 candidate = node[key];
638 if (Array.isArray(candidate)) {
639 current2 = candidate.length;
640 while ((current2 -= 1) >= 0) {
641 if (!candidate[current2]) {
644 if (isProperty(nodeType, candidates[current])) {
645 element = new Element(candidate[current2], [key, current2], 'Property', new Reference(candidate, current2));
646 } else if (isNode(candidate[current2])) {
647 element = new Element(candidate[current2], [key, current2], null, new Reference(candidate, current2));
651 worklist.push(element);
653 } else if (isNode(candidate)) {
654 worklist.push(new Element(candidate, key, null, new Reference(node, key)));
662 function traverse(root, visitor) {
663 var controller = new Controller();
664 return controller.traverse(root, visitor);
667 function replace(root, visitor) {
668 var controller = new Controller();
669 return controller.replace(root, visitor);
672 function extendCommentRange(comment, tokens) {
675 target = upperBound(tokens, function search(token) {
676 return token.range[0] > comment.range[0];
679 comment.extendedRange = [comment.range[0], comment.range[1]];
681 if (target !== tokens.length) {
682 comment.extendedRange[1] = tokens[target].range[0];
687 comment.extendedRange[0] = tokens[target].range[1];
693 function attachComments(tree, providedComments, tokens) {
694 // At first, we should calculate extended comment ranges.
695 var comments = [], comment, len, i, cursor;
698 throw new Error('attachComments needs range information');
701 // tokens array is empty, we attach comments to tree as 'leadingComments'
702 if (!tokens.length) {
703 if (providedComments.length) {
704 for (i = 0, len = providedComments.length; i < len; i += 1) {
705 comment = deepCopy(providedComments[i]);
706 comment.extendedRange = [0, tree.range[0]];
707 comments.push(comment);
709 tree.leadingComments = comments;
714 for (i = 0, len = providedComments.length; i < len; i += 1) {
715 comments.push(extendCommentRange(deepCopy(providedComments[i]), tokens));
718 // This is based on John Freeman's implementation.
721 enter: function (node) {
724 while (cursor < comments.length) {
725 comment = comments[cursor];
726 if (comment.extendedRange[1] > node.range[0]) {
730 if (comment.extendedRange[1] === node.range[0]) {
731 if (!node.leadingComments) {
732 node.leadingComments = [];
734 node.leadingComments.push(comment);
735 comments.splice(cursor, 1);
741 // already out of owned node
742 if (cursor === comments.length) {
743 return VisitorOption.Break;
746 if (comments[cursor].extendedRange[0] > node.range[1]) {
747 return VisitorOption.Skip;
754 leave: function (node) {
757 while (cursor < comments.length) {
758 comment = comments[cursor];
759 if (node.range[1] < comment.extendedRange[0]) {
763 if (node.range[1] === comment.extendedRange[0]) {
764 if (!node.trailingComments) {
765 node.trailingComments = [];
767 node.trailingComments.push(comment);
768 comments.splice(cursor, 1);
774 // already out of owned node
775 if (cursor === comments.length) {
776 return VisitorOption.Break;
779 if (comments[cursor].extendedRange[0] > node.range[1]) {
780 return VisitorOption.Skip;
788 exports.Syntax = Syntax;
789 exports.traverse = traverse;
790 exports.replace = replace;
791 exports.attachComments = attachComments;
792 exports.VisitorKeys = VisitorKeys;
793 exports.VisitorOption = VisitorOption;
794 exports.Controller = Controller;
795 exports.cloneEnvironment = function () { return clone({}); };
799 /* vim: set sw=4 ts=4 et tw=80 : */