[d565449] | 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 : */
|
---|