1 | /*
|
---|
2 | Copyright (C) 2012-2013 Yusuke Suzuki <utatane.tea@gmail.com>
|
---|
3 | Copyright (C) 2012 Ariya Hidayat <ariya.hidayat@gmail.com>
|
---|
4 |
|
---|
5 | Redistribution and use in source and binary forms, with or without
|
---|
6 | modification, are permitted provided that the following conditions are met:
|
---|
7 |
|
---|
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.
|
---|
13 |
|
---|
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.
|
---|
24 | */
|
---|
25 | /*jslint vars:false, bitwise:true*/
|
---|
26 | /*jshint indent:4*/
|
---|
27 | /*global exports:true*/
|
---|
28 | (function clone(exports) {
|
---|
29 | 'use strict';
|
---|
30 |
|
---|
31 | var Syntax,
|
---|
32 | VisitorOption,
|
---|
33 | VisitorKeys,
|
---|
34 | BREAK,
|
---|
35 | SKIP,
|
---|
36 | REMOVE;
|
---|
37 |
|
---|
38 | function deepCopy(obj) {
|
---|
39 | var ret = {}, key, val;
|
---|
40 | for (key in obj) {
|
---|
41 | if (obj.hasOwnProperty(key)) {
|
---|
42 | val = obj[key];
|
---|
43 | if (typeof val === 'object' && val !== null) {
|
---|
44 | ret[key] = deepCopy(val);
|
---|
45 | } else {
|
---|
46 | ret[key] = val;
|
---|
47 | }
|
---|
48 | }
|
---|
49 | }
|
---|
50 | return ret;
|
---|
51 | }
|
---|
52 |
|
---|
53 | // based on LLVM libc++ upper_bound / lower_bound
|
---|
54 | // MIT License
|
---|
55 |
|
---|
56 | function upperBound(array, func) {
|
---|
57 | var diff, len, i, current;
|
---|
58 |
|
---|
59 | len = array.length;
|
---|
60 | i = 0;
|
---|
61 |
|
---|
62 | while (len) {
|
---|
63 | diff = len >>> 1;
|
---|
64 | current = i + diff;
|
---|
65 | if (func(array[current])) {
|
---|
66 | len = diff;
|
---|
67 | } else {
|
---|
68 | i = current + 1;
|
---|
69 | len -= diff + 1;
|
---|
70 | }
|
---|
71 | }
|
---|
72 | return i;
|
---|
73 | }
|
---|
74 |
|
---|
75 | Syntax = {
|
---|
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',
|
---|
117 | Literal: 'Literal',
|
---|
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',
|
---|
128 | Program: 'Program',
|
---|
129 | Property: 'Property',
|
---|
130 | PropertyDefinition: 'PropertyDefinition',
|
---|
131 | RestElement: 'RestElement',
|
---|
132 | ReturnStatement: 'ReturnStatement',
|
---|
133 | SequenceExpression: 'SequenceExpression',
|
---|
134 | SpreadElement: 'SpreadElement',
|
---|
135 | Super: 'Super',
|
---|
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'
|
---|
151 | };
|
---|
152 |
|
---|
153 | VisitorKeys = {
|
---|
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'],
|
---|
166 | ClassBody: ['body'],
|
---|
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'],
|
---|
176 | EmptyStatement: [],
|
---|
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.
|
---|
188 | Identifier: [],
|
---|
189 | IfStatement: ['test', 'consequent', 'alternate'],
|
---|
190 | ImportExpression: ['source'],
|
---|
191 | ImportDeclaration: ['specifiers', 'source'],
|
---|
192 | ImportDefaultSpecifier: ['local'],
|
---|
193 | ImportNamespaceSpecifier: ['local'],
|
---|
194 | ImportSpecifier: ['imported', 'local'],
|
---|
195 | Literal: [],
|
---|
196 | LabeledStatement: ['label', 'body'],
|
---|
197 | LogicalExpression: ['left', 'right'],
|
---|
198 | MemberExpression: ['object', 'property'],
|
---|
199 | MetaProperty: ['meta', 'property'],
|
---|
200 | MethodDefinition: ['key', 'value'],
|
---|
201 | ModuleSpecifier: [],
|
---|
202 | NewExpression: ['callee', 'arguments'],
|
---|
203 | ObjectExpression: ['properties'],
|
---|
204 | ObjectPattern: ['properties'],
|
---|
205 | PrivateIdentifier: [],
|
---|
206 | Program: ['body'],
|
---|
207 | Property: ['key', 'value'],
|
---|
208 | PropertyDefinition: ['key', 'value'],
|
---|
209 | RestElement: [ 'argument' ],
|
---|
210 | ReturnStatement: ['argument'],
|
---|
211 | SequenceExpression: ['expressions'],
|
---|
212 | SpreadElement: ['argument'],
|
---|
213 | Super: [],
|
---|
214 | SwitchStatement: ['discriminant', 'cases'],
|
---|
215 | SwitchCase: ['test', 'consequent'],
|
---|
216 | TaggedTemplateExpression: ['tag', 'quasi'],
|
---|
217 | TemplateElement: [],
|
---|
218 | TemplateLiteral: ['quasis', 'expressions'],
|
---|
219 | ThisExpression: [],
|
---|
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']
|
---|
229 | };
|
---|
230 |
|
---|
231 | // unique id
|
---|
232 | BREAK = {};
|
---|
233 | SKIP = {};
|
---|
234 | REMOVE = {};
|
---|
235 |
|
---|
236 | VisitorOption = {
|
---|
237 | Break: BREAK,
|
---|
238 | Skip: SKIP,
|
---|
239 | Remove: REMOVE
|
---|
240 | };
|
---|
241 |
|
---|
242 | function Reference(parent, key) {
|
---|
243 | this.parent = parent;
|
---|
244 | this.key = key;
|
---|
245 | }
|
---|
246 |
|
---|
247 | Reference.prototype.replace = function replace(node) {
|
---|
248 | this.parent[this.key] = node;
|
---|
249 | };
|
---|
250 |
|
---|
251 | Reference.prototype.remove = function remove() {
|
---|
252 | if (Array.isArray(this.parent)) {
|
---|
253 | this.parent.splice(this.key, 1);
|
---|
254 | return true;
|
---|
255 | } else {
|
---|
256 | this.replace(null);
|
---|
257 | return false;
|
---|
258 | }
|
---|
259 | };
|
---|
260 |
|
---|
261 | function Element(node, path, wrap, ref) {
|
---|
262 | this.node = node;
|
---|
263 | this.path = path;
|
---|
264 | this.wrap = wrap;
|
---|
265 | this.ref = ref;
|
---|
266 | }
|
---|
267 |
|
---|
268 | function Controller() { }
|
---|
269 |
|
---|
270 | // API:
|
---|
271 | // return property path array from root to current node
|
---|
272 | Controller.prototype.path = function path() {
|
---|
273 | var i, iz, j, jz, result, element;
|
---|
274 |
|
---|
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]);
|
---|
279 | }
|
---|
280 | } else {
|
---|
281 | result.push(path);
|
---|
282 | }
|
---|
283 | }
|
---|
284 |
|
---|
285 | // root node
|
---|
286 | if (!this.__current.path) {
|
---|
287 | return null;
|
---|
288 | }
|
---|
289 |
|
---|
290 | // first node is sentinel, second node is root element
|
---|
291 | result = [];
|
---|
292 | for (i = 2, iz = this.__leavelist.length; i < iz; ++i) {
|
---|
293 | element = this.__leavelist[i];
|
---|
294 | addToPath(result, element.path);
|
---|
295 | }
|
---|
296 | addToPath(result, this.__current.path);
|
---|
297 | return result;
|
---|
298 | };
|
---|
299 |
|
---|
300 | // API:
|
---|
301 | // return type of current node
|
---|
302 | Controller.prototype.type = function () {
|
---|
303 | var node = this.current();
|
---|
304 | return node.type || this.__current.wrap;
|
---|
305 | };
|
---|
306 |
|
---|
307 | // API:
|
---|
308 | // return array of parent elements
|
---|
309 | Controller.prototype.parents = function parents() {
|
---|
310 | var i, iz, result;
|
---|
311 |
|
---|
312 | // first node is sentinel
|
---|
313 | result = [];
|
---|
314 | for (i = 1, iz = this.__leavelist.length; i < iz; ++i) {
|
---|
315 | result.push(this.__leavelist[i].node);
|
---|
316 | }
|
---|
317 |
|
---|
318 | return result;
|
---|
319 | };
|
---|
320 |
|
---|
321 | // API:
|
---|
322 | // return current node
|
---|
323 | Controller.prototype.current = function current() {
|
---|
324 | return this.__current.node;
|
---|
325 | };
|
---|
326 |
|
---|
327 | Controller.prototype.__execute = function __execute(callback, element) {
|
---|
328 | var previous, result;
|
---|
329 |
|
---|
330 | result = undefined;
|
---|
331 |
|
---|
332 | previous = this.__current;
|
---|
333 | this.__current = element;
|
---|
334 | this.__state = null;
|
---|
335 | if (callback) {
|
---|
336 | result = callback.call(this, element.node, this.__leavelist[this.__leavelist.length - 1].node);
|
---|
337 | }
|
---|
338 | this.__current = previous;
|
---|
339 |
|
---|
340 | return result;
|
---|
341 | };
|
---|
342 |
|
---|
343 | // API:
|
---|
344 | // notify control skip / break
|
---|
345 | Controller.prototype.notify = function notify(flag) {
|
---|
346 | this.__state = flag;
|
---|
347 | };
|
---|
348 |
|
---|
349 | // API:
|
---|
350 | // skip child nodes of current node
|
---|
351 | Controller.prototype.skip = function () {
|
---|
352 | this.notify(SKIP);
|
---|
353 | };
|
---|
354 |
|
---|
355 | // API:
|
---|
356 | // break traversals
|
---|
357 | Controller.prototype['break'] = function () {
|
---|
358 | this.notify(BREAK);
|
---|
359 | };
|
---|
360 |
|
---|
361 | // API:
|
---|
362 | // remove node
|
---|
363 | Controller.prototype.remove = function () {
|
---|
364 | this.notify(REMOVE);
|
---|
365 | };
|
---|
366 |
|
---|
367 | Controller.prototype.__initialize = function(root, visitor) {
|
---|
368 | this.visitor = visitor;
|
---|
369 | this.root = root;
|
---|
370 | this.__worklist = [];
|
---|
371 | this.__leavelist = [];
|
---|
372 | this.__current = null;
|
---|
373 | this.__state = 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;
|
---|
379 | }
|
---|
380 |
|
---|
381 | this.__keys = VisitorKeys;
|
---|
382 | if (visitor.keys) {
|
---|
383 | this.__keys = Object.assign(Object.create(this.__keys), visitor.keys);
|
---|
384 | }
|
---|
385 | };
|
---|
386 |
|
---|
387 | function isNode(node) {
|
---|
388 | if (node == null) {
|
---|
389 | return false;
|
---|
390 | }
|
---|
391 | return typeof node === 'object' && typeof node.type === 'string';
|
---|
392 | }
|
---|
393 |
|
---|
394 | function isProperty(nodeType, key) {
|
---|
395 | return (nodeType === Syntax.ObjectExpression || nodeType === Syntax.ObjectPattern) && 'properties' === key;
|
---|
396 | }
|
---|
397 |
|
---|
398 | function candidateExistsInLeaveList(leavelist, candidate) {
|
---|
399 | for (var i = leavelist.length - 1; i >= 0; --i) {
|
---|
400 | if (leavelist[i].node === candidate) {
|
---|
401 | return true;
|
---|
402 | }
|
---|
403 | }
|
---|
404 | return false;
|
---|
405 | }
|
---|
406 |
|
---|
407 | Controller.prototype.traverse = function traverse(root, visitor) {
|
---|
408 | var worklist,
|
---|
409 | leavelist,
|
---|
410 | element,
|
---|
411 | node,
|
---|
412 | nodeType,
|
---|
413 | ret,
|
---|
414 | key,
|
---|
415 | current,
|
---|
416 | current2,
|
---|
417 | candidates,
|
---|
418 | candidate,
|
---|
419 | sentinel;
|
---|
420 |
|
---|
421 | this.__initialize(root, visitor);
|
---|
422 |
|
---|
423 | sentinel = {};
|
---|
424 |
|
---|
425 | // reference
|
---|
426 | worklist = this.__worklist;
|
---|
427 | leavelist = this.__leavelist;
|
---|
428 |
|
---|
429 | // initialize
|
---|
430 | worklist.push(new Element(root, null, null, null));
|
---|
431 | leavelist.push(new Element(null, null, null, null));
|
---|
432 |
|
---|
433 | while (worklist.length) {
|
---|
434 | element = worklist.pop();
|
---|
435 |
|
---|
436 | if (element === sentinel) {
|
---|
437 | element = leavelist.pop();
|
---|
438 |
|
---|
439 | ret = this.__execute(visitor.leave, element);
|
---|
440 |
|
---|
441 | if (this.__state === BREAK || ret === BREAK) {
|
---|
442 | return;
|
---|
443 | }
|
---|
444 | continue;
|
---|
445 | }
|
---|
446 |
|
---|
447 | if (element.node) {
|
---|
448 |
|
---|
449 | ret = this.__execute(visitor.enter, element);
|
---|
450 |
|
---|
451 | if (this.__state === BREAK || ret === BREAK) {
|
---|
452 | return;
|
---|
453 | }
|
---|
454 |
|
---|
455 | worklist.push(sentinel);
|
---|
456 | leavelist.push(element);
|
---|
457 |
|
---|
458 | if (this.__state === SKIP || ret === SKIP) {
|
---|
459 | continue;
|
---|
460 | }
|
---|
461 |
|
---|
462 | node = element.node;
|
---|
463 | nodeType = node.type || element.wrap;
|
---|
464 | candidates = this.__keys[nodeType];
|
---|
465 | if (!candidates) {
|
---|
466 | if (this.__fallback) {
|
---|
467 | candidates = this.__fallback(node);
|
---|
468 | } else {
|
---|
469 | throw new Error('Unknown node type ' + nodeType + '.');
|
---|
470 | }
|
---|
471 | }
|
---|
472 |
|
---|
473 | current = candidates.length;
|
---|
474 | while ((current -= 1) >= 0) {
|
---|
475 | key = candidates[current];
|
---|
476 | candidate = node[key];
|
---|
477 | if (!candidate) {
|
---|
478 | continue;
|
---|
479 | }
|
---|
480 |
|
---|
481 | if (Array.isArray(candidate)) {
|
---|
482 | current2 = candidate.length;
|
---|
483 | while ((current2 -= 1) >= 0) {
|
---|
484 | if (!candidate[current2]) {
|
---|
485 | continue;
|
---|
486 | }
|
---|
487 |
|
---|
488 | if (candidateExistsInLeaveList(leavelist, candidate[current2])) {
|
---|
489 | continue;
|
---|
490 | }
|
---|
491 |
|
---|
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);
|
---|
496 | } else {
|
---|
497 | continue;
|
---|
498 | }
|
---|
499 | worklist.push(element);
|
---|
500 | }
|
---|
501 | } else if (isNode(candidate)) {
|
---|
502 | if (candidateExistsInLeaveList(leavelist, candidate)) {
|
---|
503 | continue;
|
---|
504 | }
|
---|
505 |
|
---|
506 | worklist.push(new Element(candidate, key, null, null));
|
---|
507 | }
|
---|
508 | }
|
---|
509 | }
|
---|
510 | }
|
---|
511 | };
|
---|
512 |
|
---|
513 | Controller.prototype.replace = function replace(root, visitor) {
|
---|
514 | var worklist,
|
---|
515 | leavelist,
|
---|
516 | node,
|
---|
517 | nodeType,
|
---|
518 | target,
|
---|
519 | element,
|
---|
520 | current,
|
---|
521 | current2,
|
---|
522 | candidates,
|
---|
523 | candidate,
|
---|
524 | sentinel,
|
---|
525 | outer,
|
---|
526 | key;
|
---|
527 |
|
---|
528 | function removeElem(element) {
|
---|
529 | var i,
|
---|
530 | key,
|
---|
531 | nextElem,
|
---|
532 | parent;
|
---|
533 |
|
---|
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;
|
---|
538 |
|
---|
539 | // If removed from array, then decrease following items' keys.
|
---|
540 | i = worklist.length;
|
---|
541 | while (i--) {
|
---|
542 | nextElem = worklist[i];
|
---|
543 | if (nextElem.ref && nextElem.ref.parent === parent) {
|
---|
544 | if (nextElem.ref.key < key) {
|
---|
545 | break;
|
---|
546 | }
|
---|
547 | --nextElem.ref.key;
|
---|
548 | }
|
---|
549 | }
|
---|
550 | }
|
---|
551 | }
|
---|
552 |
|
---|
553 | this.__initialize(root, visitor);
|
---|
554 |
|
---|
555 | sentinel = {};
|
---|
556 |
|
---|
557 | // reference
|
---|
558 | worklist = this.__worklist;
|
---|
559 | leavelist = this.__leavelist;
|
---|
560 |
|
---|
561 | // initialize
|
---|
562 | outer = {
|
---|
563 | root: root
|
---|
564 | };
|
---|
565 | element = new Element(root, null, null, new Reference(outer, 'root'));
|
---|
566 | worklist.push(element);
|
---|
567 | leavelist.push(element);
|
---|
568 |
|
---|
569 | while (worklist.length) {
|
---|
570 | element = worklist.pop();
|
---|
571 |
|
---|
572 | if (element === sentinel) {
|
---|
573 | element = leavelist.pop();
|
---|
574 |
|
---|
575 | target = this.__execute(visitor.leave, element);
|
---|
576 |
|
---|
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) {
|
---|
580 | // replace
|
---|
581 | element.ref.replace(target);
|
---|
582 | }
|
---|
583 |
|
---|
584 | if (this.__state === REMOVE || target === REMOVE) {
|
---|
585 | removeElem(element);
|
---|
586 | }
|
---|
587 |
|
---|
588 | if (this.__state === BREAK || target === BREAK) {
|
---|
589 | return outer.root;
|
---|
590 | }
|
---|
591 | continue;
|
---|
592 | }
|
---|
593 |
|
---|
594 | target = this.__execute(visitor.enter, element);
|
---|
595 |
|
---|
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) {
|
---|
599 | // replace
|
---|
600 | element.ref.replace(target);
|
---|
601 | element.node = target;
|
---|
602 | }
|
---|
603 |
|
---|
604 | if (this.__state === REMOVE || target === REMOVE) {
|
---|
605 | removeElem(element);
|
---|
606 | element.node = null;
|
---|
607 | }
|
---|
608 |
|
---|
609 | if (this.__state === BREAK || target === BREAK) {
|
---|
610 | return outer.root;
|
---|
611 | }
|
---|
612 |
|
---|
613 | // node may be null
|
---|
614 | node = element.node;
|
---|
615 | if (!node) {
|
---|
616 | continue;
|
---|
617 | }
|
---|
618 |
|
---|
619 | worklist.push(sentinel);
|
---|
620 | leavelist.push(element);
|
---|
621 |
|
---|
622 | if (this.__state === SKIP || target === SKIP) {
|
---|
623 | continue;
|
---|
624 | }
|
---|
625 |
|
---|
626 | nodeType = node.type || element.wrap;
|
---|
627 | candidates = this.__keys[nodeType];
|
---|
628 | if (!candidates) {
|
---|
629 | if (this.__fallback) {
|
---|
630 | candidates = this.__fallback(node);
|
---|
631 | } else {
|
---|
632 | throw new Error('Unknown node type ' + nodeType + '.');
|
---|
633 | }
|
---|
634 | }
|
---|
635 |
|
---|
636 | current = candidates.length;
|
---|
637 | while ((current -= 1) >= 0) {
|
---|
638 | key = candidates[current];
|
---|
639 | candidate = node[key];
|
---|
640 | if (!candidate) {
|
---|
641 | continue;
|
---|
642 | }
|
---|
643 |
|
---|
644 | if (Array.isArray(candidate)) {
|
---|
645 | current2 = candidate.length;
|
---|
646 | while ((current2 -= 1) >= 0) {
|
---|
647 | if (!candidate[current2]) {
|
---|
648 | continue;
|
---|
649 | }
|
---|
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));
|
---|
654 | } else {
|
---|
655 | continue;
|
---|
656 | }
|
---|
657 | worklist.push(element);
|
---|
658 | }
|
---|
659 | } else if (isNode(candidate)) {
|
---|
660 | worklist.push(new Element(candidate, key, null, new Reference(node, key)));
|
---|
661 | }
|
---|
662 | }
|
---|
663 | }
|
---|
664 |
|
---|
665 | return outer.root;
|
---|
666 | };
|
---|
667 |
|
---|
668 | function traverse(root, visitor) {
|
---|
669 | var controller = new Controller();
|
---|
670 | return controller.traverse(root, visitor);
|
---|
671 | }
|
---|
672 |
|
---|
673 | function replace(root, visitor) {
|
---|
674 | var controller = new Controller();
|
---|
675 | return controller.replace(root, visitor);
|
---|
676 | }
|
---|
677 |
|
---|
678 | function extendCommentRange(comment, tokens) {
|
---|
679 | var target;
|
---|
680 |
|
---|
681 | target = upperBound(tokens, function search(token) {
|
---|
682 | return token.range[0] > comment.range[0];
|
---|
683 | });
|
---|
684 |
|
---|
685 | comment.extendedRange = [comment.range[0], comment.range[1]];
|
---|
686 |
|
---|
687 | if (target !== tokens.length) {
|
---|
688 | comment.extendedRange[1] = tokens[target].range[0];
|
---|
689 | }
|
---|
690 |
|
---|
691 | target -= 1;
|
---|
692 | if (target >= 0) {
|
---|
693 | comment.extendedRange[0] = tokens[target].range[1];
|
---|
694 | }
|
---|
695 |
|
---|
696 | return comment;
|
---|
697 | }
|
---|
698 |
|
---|
699 | function attachComments(tree, providedComments, tokens) {
|
---|
700 | // At first, we should calculate extended comment ranges.
|
---|
701 | var comments = [], comment, len, i, cursor;
|
---|
702 |
|
---|
703 | if (!tree.range) {
|
---|
704 | throw new Error('attachComments needs range information');
|
---|
705 | }
|
---|
706 |
|
---|
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);
|
---|
714 | }
|
---|
715 | tree.leadingComments = comments;
|
---|
716 | }
|
---|
717 | return tree;
|
---|
718 | }
|
---|
719 |
|
---|
720 | for (i = 0, len = providedComments.length; i < len; i += 1) {
|
---|
721 | comments.push(extendCommentRange(deepCopy(providedComments[i]), tokens));
|
---|
722 | }
|
---|
723 |
|
---|
724 | // This is based on John Freeman's implementation.
|
---|
725 | cursor = 0;
|
---|
726 | traverse(tree, {
|
---|
727 | enter: function (node) {
|
---|
728 | var comment;
|
---|
729 |
|
---|
730 | while (cursor < comments.length) {
|
---|
731 | comment = comments[cursor];
|
---|
732 | if (comment.extendedRange[1] > node.range[0]) {
|
---|
733 | break;
|
---|
734 | }
|
---|
735 |
|
---|
736 | if (comment.extendedRange[1] === node.range[0]) {
|
---|
737 | if (!node.leadingComments) {
|
---|
738 | node.leadingComments = [];
|
---|
739 | }
|
---|
740 | node.leadingComments.push(comment);
|
---|
741 | comments.splice(cursor, 1);
|
---|
742 | } else {
|
---|
743 | cursor += 1;
|
---|
744 | }
|
---|
745 | }
|
---|
746 |
|
---|
747 | // already out of owned node
|
---|
748 | if (cursor === comments.length) {
|
---|
749 | return VisitorOption.Break;
|
---|
750 | }
|
---|
751 |
|
---|
752 | if (comments[cursor].extendedRange[0] > node.range[1]) {
|
---|
753 | return VisitorOption.Skip;
|
---|
754 | }
|
---|
755 | }
|
---|
756 | });
|
---|
757 |
|
---|
758 | cursor = 0;
|
---|
759 | traverse(tree, {
|
---|
760 | leave: function (node) {
|
---|
761 | var comment;
|
---|
762 |
|
---|
763 | while (cursor < comments.length) {
|
---|
764 | comment = comments[cursor];
|
---|
765 | if (node.range[1] < comment.extendedRange[0]) {
|
---|
766 | break;
|
---|
767 | }
|
---|
768 |
|
---|
769 | if (node.range[1] === comment.extendedRange[0]) {
|
---|
770 | if (!node.trailingComments) {
|
---|
771 | node.trailingComments = [];
|
---|
772 | }
|
---|
773 | node.trailingComments.push(comment);
|
---|
774 | comments.splice(cursor, 1);
|
---|
775 | } else {
|
---|
776 | cursor += 1;
|
---|
777 | }
|
---|
778 | }
|
---|
779 |
|
---|
780 | // already out of owned node
|
---|
781 | if (cursor === comments.length) {
|
---|
782 | return VisitorOption.Break;
|
---|
783 | }
|
---|
784 |
|
---|
785 | if (comments[cursor].extendedRange[0] > node.range[1]) {
|
---|
786 | return VisitorOption.Skip;
|
---|
787 | }
|
---|
788 | }
|
---|
789 | });
|
---|
790 |
|
---|
791 | return tree;
|
---|
792 | }
|
---|
793 |
|
---|
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({}); };
|
---|
802 |
|
---|
803 | return exports;
|
---|
804 | }(exports));
|
---|
805 | /* vim: set sw=4 ts=4 et tw=80 : */
|
---|