vnfmarket/src/main/webapp/vnfmarket/node_modules/escodegen/node_modules/estraverse/estraverse.js

   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, define:true*/
  28 (function (root, factory) {
  29     'use strict';
  30
  31     // Universal Module Definition (UMD) to support AMD, CommonJS/Node.js,
  32     // and plain browser loading,
  33     if (typeof define === 'function' && define.amd) {
  34         define(['exports'], factory);
  35     } else if (typeof exports !== 'undefined') {
  36         factory(exports);
  37     } else {
  38         factory((root.estraverse = {}));
  39     }
  40 }(this, function clone(exports) {
  41     'use strict';
  42
  43     var Syntax,
  44         isArray,
  45         VisitorOption,
  46         VisitorKeys,
  47         objectCreate,
  48         objectKeys,
  49         BREAK,
  50         SKIP,
  51         REMOVE;
  52
  53     function ignoreJSHintError() { }
  54
  55     isArray = Array.isArray;
  56     if (!isArray) {
  57         isArray = function isArray(array) {
  58             return Object.prototype.toString.call(array) === '[object Array]';
  59         };
  60     }
  61
  62     function deepCopy(obj) {
  63         var ret = {}, key, val;
  64         for (key in obj) {
  65             if (obj.hasOwnProperty(key)) {
  66                 val = obj[key];
  67                 if (typeof val === 'object' && val !== null) {
  68                     ret[key] = deepCopy(val);
  69                 } else {
  70                     ret[key] = val;
  71                 }
  72             }
  73         }
  74         return ret;
  75     }
  76
  77     function shallowCopy(obj) {
  78         var ret = {}, key;
  79         for (key in obj) {
  80             if (obj.hasOwnProperty(key)) {
  81                 ret[key] = obj[key];
  82             }
  83         }
  84         return ret;
  85     }
  86     ignoreJSHintError(shallowCopy);
  87
  88     // based on LLVM libc++ upper_bound / lower_bound
  89     // MIT License
  90
  91     function upperBound(array, func) {
  92         var diff, len, i, current;
  93
  94         len = array.length;
  95         i = 0;
  96
  97         while (len) {
  98             diff = len >>> 1;
  99             current = i + diff;
 100             if (func(array[current])) {
 101                 len = diff;
 102             } else {
 103                 i = current + 1;
 104                 len -= diff + 1;
 105             }
 106         }
 107         return i;
 108     }
 109
 110     function lowerBound(array, func) {
 111         var diff, len, i, current;
 112
 113         len = array.length;
 114         i = 0;
 115
 116         while (len) {
 117             diff = len >>> 1;
 118             current = i + diff;
 119             if (func(array[current])) {
 120                 i = current + 1;
 121                 len -= diff + 1;
 122             } else {
 123                 len = diff;
 124             }
 125         }
 126         return i;
 127     }
 128     ignoreJSHintError(lowerBound);
 129
 130     objectCreate = Object.create || (function () {
 131         function F() { }
 132
 133         return function (o) {
 134             F.prototype = o;
 135             return new F();
 136         };
 137     })();
 138
 139     objectKeys = Object.keys || function (o) {
 140         var keys = [], key;
 141         for (key in o) {
 142             keys.push(key);
 143         }
 144         return keys;
 145     };
 146
 147     function extend(to, from) {
 148         var keys = objectKeys(from), key, i, len;
 149         for (i = 0, len = keys.length; i < len; i += 1) {
 150             key = keys[i];
 151             to[key] = from[key];
 152         }
 153         return to;
 154     }
 155
 156     Syntax = {
 157         AssignmentExpression: 'AssignmentExpression',
 158         ArrayExpression: 'ArrayExpression',
 159         ArrayPattern: 'ArrayPattern',
 160         ArrowFunctionExpression: 'ArrowFunctionExpression',
 161         AwaitExpression: 'AwaitExpression', // CAUTION: It's deferred to ES7.
 162         BlockStatement: 'BlockStatement',
 163         BinaryExpression: 'BinaryExpression',
 164         BreakStatement: 'BreakStatement',
 165         CallExpression: 'CallExpression',
 166         CatchClause: 'CatchClause',
 167         ClassBody: 'ClassBody',
 168         ClassDeclaration: 'ClassDeclaration',
 169         ClassExpression: 'ClassExpression',
 170         ComprehensionBlock: 'ComprehensionBlock',  // CAUTION: It's deferred to ES7.
 171         ComprehensionExpression: 'ComprehensionExpression',  // CAUTION: It's deferred to ES7.
 172         ConditionalExpression: 'ConditionalExpression',
 173         ContinueStatement: 'ContinueStatement',
 174         DebuggerStatement: 'DebuggerStatement',
 175         DirectiveStatement: 'DirectiveStatement',
 176         DoWhileStatement: 'DoWhileStatement',
 177         EmptyStatement: 'EmptyStatement',
 178         ExportBatchSpecifier: 'ExportBatchSpecifier',
 179         ExportDeclaration: 'ExportDeclaration',
 180         ExportSpecifier: 'ExportSpecifier',
 181         ExpressionStatement: 'ExpressionStatement',
 182         ForStatement: 'ForStatement',
 183         ForInStatement: 'ForInStatement',
 184         ForOfStatement: 'ForOfStatement',
 185         FunctionDeclaration: 'FunctionDeclaration',
 186         FunctionExpression: 'FunctionExpression',
 187         GeneratorExpression: 'GeneratorExpression',  // CAUTION: It's deferred to ES7.
 188         Identifier: 'Identifier',
 189         IfStatement: 'IfStatement',
 190         ImportDeclaration: 'ImportDeclaration',
 191         ImportDefaultSpecifier: 'ImportDefaultSpecifier',
 192         ImportNamespaceSpecifier: 'ImportNamespaceSpecifier',
 193         ImportSpecifier: 'ImportSpecifier',
 194         Literal: 'Literal',
 195         LabeledStatement: 'LabeledStatement',
 196         LogicalExpression: 'LogicalExpression',
 197         MemberExpression: 'MemberExpression',
 198         MethodDefinition: 'MethodDefinition',
 199         ModuleSpecifier: 'ModuleSpecifier',
 200         NewExpression: 'NewExpression',
 201         ObjectExpression: 'ObjectExpression',
 202         ObjectPattern: 'ObjectPattern',
 203         Program: 'Program',
 204         Property: 'Property',
 205         ReturnStatement: 'ReturnStatement',
 206         SequenceExpression: 'SequenceExpression',
 207         SpreadElement: 'SpreadElement',
 208         SwitchStatement: 'SwitchStatement',
 209         SwitchCase: 'SwitchCase',
 210         TaggedTemplateExpression: 'TaggedTemplateExpression',
 211         TemplateElement: 'TemplateElement',
 212         TemplateLiteral: 'TemplateLiteral',
 213         ThisExpression: 'ThisExpression',
 214         ThrowStatement: 'ThrowStatement',
 215         TryStatement: 'TryStatement',
 216         UnaryExpression: 'UnaryExpression',
 217         UpdateExpression: 'UpdateExpression',
 218         VariableDeclaration: 'VariableDeclaration',
 219         VariableDeclarator: 'VariableDeclarator',
 220         WhileStatement: 'WhileStatement',
 221         WithStatement: 'WithStatement',
 222         YieldExpression: 'YieldExpression'
 223     };
 224
 225     VisitorKeys = {
 226         AssignmentExpression: ['left', 'right'],
 227         ArrayExpression: ['elements'],
 228         ArrayPattern: ['elements'],
 229         ArrowFunctionExpression: ['params', 'defaults', 'rest', 'body'],
 230         AwaitExpression: ['argument'], // CAUTION: It's deferred to ES7.
 231         BlockStatement: ['body'],
 232         BinaryExpression: ['left', 'right'],
 233         BreakStatement: ['label'],
 234         CallExpression: ['callee', 'arguments'],
 235         CatchClause: ['param', 'body'],
 236         ClassBody: ['body'],
 237         ClassDeclaration: ['id', 'body', 'superClass'],
 238         ClassExpression: ['id', 'body', 'superClass'],
 239         ComprehensionBlock: ['left', 'right'],  // CAUTION: It's deferred to ES7.
 240         ComprehensionExpression: ['blocks', 'filter', 'body'],  // CAUTION: It's deferred to ES7.
 241         ConditionalExpression: ['test', 'consequent', 'alternate'],
 242         ContinueStatement: ['label'],
 243         DebuggerStatement: [],
 244         DirectiveStatement: [],
 245         DoWhileStatement: ['body', 'test'],
 246         EmptyStatement: [],
 247         ExportBatchSpecifier: [],
 248         ExportDeclaration: ['declaration', 'specifiers', 'source'],
 249         ExportSpecifier: ['id', 'name'],
 250         ExpressionStatement: ['expression'],
 251         ForStatement: ['init', 'test', 'update', 'body'],
 252         ForInStatement: ['left', 'right', 'body'],
 253         ForOfStatement: ['left', 'right', 'body'],
 254         FunctionDeclaration: ['id', 'params', 'defaults', 'rest', 'body'],
 255         FunctionExpression: ['id', 'params', 'defaults', 'rest', 'body'],
 256         GeneratorExpression: ['blocks', 'filter', 'body'],  // CAUTION: It's deferred to ES7.
 257         Identifier: [],
 258         IfStatement: ['test', 'consequent', 'alternate'],
 259         ImportDeclaration: ['specifiers', 'source'],
 260         ImportDefaultSpecifier: ['id'],
 261         ImportNamespaceSpecifier: ['id'],
 262         ImportSpecifier: ['id', 'name'],
 263         Literal: [],
 264         LabeledStatement: ['label', 'body'],
 265         LogicalExpression: ['left', 'right'],
 266         MemberExpression: ['object', 'property'],
 267         MethodDefinition: ['key', 'value'],
 268         ModuleSpecifier: [],
 269         NewExpression: ['callee', 'arguments'],
 270         ObjectExpression: ['properties'],
 271         ObjectPattern: ['properties'],
 272         Program: ['body'],
 273         Property: ['key', 'value'],
 274         ReturnStatement: ['argument'],
 275         SequenceExpression: ['expressions'],
 276         SpreadElement: ['argument'],
 277         SwitchStatement: ['discriminant', 'cases'],
 278         SwitchCase: ['test', 'consequent'],
 279         TaggedTemplateExpression: ['tag', 'quasi'],
 280         TemplateElement: [],
 281         TemplateLiteral: ['quasis', 'expressions'],
 282         ThisExpression: [],
 283         ThrowStatement: ['argument'],
 284         TryStatement: ['block', 'handlers', 'handler', 'guardedHandlers', 'finalizer'],
 285         UnaryExpression: ['argument'],
 286         UpdateExpression: ['argument'],
 287         VariableDeclaration: ['declarations'],
 288         VariableDeclarator: ['id', 'init'],
 289         WhileStatement: ['test', 'body'],
 290         WithStatement: ['object', 'body'],
 291         YieldExpression: ['argument']
 292     };
 293
 294     // unique id
 295     BREAK = {};
 296     SKIP = {};
 297     REMOVE = {};
 298
 299     VisitorOption = {
 300         Break: BREAK,
 301         Skip: SKIP,
 302         Remove: REMOVE
 303     };
 304
 305     function Reference(parent, key) {
 306         this.parent = parent;
 307         this.key = key;
 308     }
 309
 310     Reference.prototype.replace = function replace(node) {
 311         this.parent[this.key] = node;
 312     };
 313
 314     Reference.prototype.remove = function remove() {
 315         if (isArray(this.parent)) {
 316             this.parent.splice(this.key, 1);
 317             return true;
 318         } else {
 319             this.replace(null);
 320             return false;
 321         }
 322     };
 323
 324     function Element(node, path, wrap, ref) {
 325         this.node = node;
 326         this.path = path;
 327         this.wrap = wrap;
 328         this.ref = ref;
 329     }
 330
 331     function Controller() { }
 332
 333     // API:
 334     // return property path array from root to current node
 335     Controller.prototype.path = function path() {
 336         var i, iz, j, jz, result, element;
 337
 338         function addToPath(result, path) {
 339             if (isArray(path)) {
 340                 for (j = 0, jz = path.length; j < jz; ++j) {
 341                     result.push(path[j]);
 342                 }
 343             } else {
 344                 result.push(path);
 345             }
 346         }
 347
 348         // root node
 349         if (!this.__current.path) {
 350             return null;
 351         }
 352
 353         // first node is sentinel, second node is root element
 354         result = [];
 355         for (i = 2, iz = this.__leavelist.length; i < iz; ++i) {
 356             element = this.__leavelist[i];
 357             addToPath(result, element.path);
 358         }
 359         addToPath(result, this.__current.path);
 360         return result;
 361     };
 362
 363     // API:
 364     // return type of current node
 365     Controller.prototype.type = function () {
 366         var node = this.current();
 367         return node.type || this.__current.wrap;
 368     };
 369
 370     // API:
 371     // return array of parent elements
 372     Controller.prototype.parents = function parents() {
 373         var i, iz, result;
 374
 375         // first node is sentinel
 376         result = [];
 377         for (i = 1, iz = this.__leavelist.length; i < iz; ++i) {
 378             result.push(this.__leavelist[i].node);
 379         }
 380
 381         return result;
 382     };
 383
 384     // API:
 385     // return current node
 386     Controller.prototype.current = function current() {
 387         return this.__current.node;
 388     };
 389
 390     Controller.prototype.__execute = function __execute(callback, element) {
 391         var previous, result;
 392
 393         result = undefined;
 394
 395         previous  = this.__current;
 396         this.__current = element;
 397         this.__state = null;
 398         if (callback) {
 399             result = callback.call(this, element.node, this.__leavelist[this.__leavelist.length - 1].node);
 400         }
 401         this.__current = previous;
 402
 403         return result;
 404     };
 405
 406     // API:
 407     // notify control skip / break
 408     Controller.prototype.notify = function notify(flag) {
 409         this.__state = flag;
 410     };
 411
 412     // API:
 413     // skip child nodes of current node
 414     Controller.prototype.skip = function () {
 415         this.notify(SKIP);
 416     };
 417
 418     // API:
 419     // break traversals
 420     Controller.prototype['break'] = function () {
 421         this.notify(BREAK);
 422     };
 423
 424     // API:
 425     // remove node
 426     Controller.prototype.remove = function () {
 427         this.notify(REMOVE);
 428     };
 429
 430     Controller.prototype.__initialize = function(root, visitor) {
 431         this.visitor = visitor;
 432         this.root = root;
 433         this.__worklist = [];
 434         this.__leavelist = [];
 435         this.__current = null;
 436         this.__state = null;
 437         this.__fallback = visitor.fallback === 'iteration';
 438         this.__keys = VisitorKeys;
 439         if (visitor.keys) {
 440             this.__keys = extend(objectCreate(this.__keys), visitor.keys);
 441         }
 442     };
 443
 444     function isNode(node) {
 445         if (node == null) {
 446             return false;
 447         }
 448         return typeof node === 'object' && typeof node.type === 'string';
 449     }
 450
 451     function isProperty(nodeType, key) {
 452         return (nodeType === Syntax.ObjectExpression || nodeType === Syntax.ObjectPattern) && 'properties' === key;
 453     }
 454
 455     Controller.prototype.traverse = function traverse(root, visitor) {
 456         var worklist,
 457             leavelist,
 458             element,
 459             node,
 460             nodeType,
 461             ret,
 462             key,
 463             current,
 464             current2,
 465             candidates,
 466             candidate,
 467             sentinel;
 468
 469         this.__initialize(root, visitor);
 470
 471         sentinel = {};
 472
 473         // reference
 474         worklist = this.__worklist;
 475         leavelist = this.__leavelist;
 476
 477         // initialize
 478         worklist.push(new Element(root, null, null, null));
 479         leavelist.push(new Element(null, null, null, null));
 480
 481         while (worklist.length) {
 482             element = worklist.pop();
 483
 484             if (element === sentinel) {
 485                 element = leavelist.pop();
 486
 487                 ret = this.__execute(visitor.leave, element);
 488
 489                 if (this.__state === BREAK || ret === BREAK) {
 490                     return;
 491                 }
 492                 continue;
 493             }
 494
 495             if (element.node) {
 496
 497                 ret = this.__execute(visitor.enter, element);
 498
 499                 if (this.__state === BREAK || ret === BREAK) {
 500                     return;
 501                 }
 502
 503                 worklist.push(sentinel);
 504                 leavelist.push(element);
 505
 506                 if (this.__state === SKIP || ret === SKIP) {
 507                     continue;
 508                 }
 509
 510                 node = element.node;
 511                 nodeType = element.wrap || node.type;
 512                 candidates = this.__keys[nodeType];
 513                 if (!candidates) {
 514                     if (this.__fallback) {
 515                         candidates = objectKeys(node);
 516                     } else {
 517                         throw new Error('Unknown node type ' + nodeType + '.');
 518                     }
 519                 }
 520
 521                 current = candidates.length;
 522                 while ((current -= 1) >= 0) {
 523                     key = candidates[current];
 524                     candidate = node[key];
 525                     if (!candidate) {
 526                         continue;
 527                     }
 528
 529                     if (isArray(candidate)) {
 530                         current2 = candidate.length;
 531                         while ((current2 -= 1) >= 0) {
 532                             if (!candidate[current2]) {
 533                                 continue;
 534                             }
 535                             if (isProperty(nodeType, candidates[current])) {
 536                                 element = new Element(candidate[current2], [key, current2], 'Property', null);
 537                             } else if (isNode(candidate[current2])) {
 538                                 element = new Element(candidate[current2], [key, current2], null, null);
 539                             } else {
 540                                 continue;
 541                             }
 542                             worklist.push(element);
 543                         }
 544                     } else if (isNode(candidate)) {
 545                         worklist.push(new Element(candidate, key, null, null));
 546                     }
 547                 }
 548             }
 549         }
 550     };
 551
 552     Controller.prototype.replace = function replace(root, visitor) {
 553         function removeElem(element) {
 554             var i,
 555                 key,
 556                 nextElem,
 557                 parent;
 558
 559             if (element.ref.remove()) {
 560                 // When the reference is an element of an array.
 561                 key = element.ref.key;
 562                 parent = element.ref.parent;
 563
 564                 // If removed from array, then decrease following items' keys.
 565                 i = worklist.length;
 566                 while (i--) {
 567                     nextElem = worklist[i];
 568                     if (nextElem.ref && nextElem.ref.parent === parent) {
 569                         if  (nextElem.ref.key < key) {
 570                             break;
 571                         }
 572                         --nextElem.ref.key;
 573                     }
 574                 }
 575             }
 576         }
 577
 578         var worklist,
 579             leavelist,
 580             node,
 581             nodeType,
 582             target,
 583             element,
 584             current,
 585             current2,
 586             candidates,
 587             candidate,
 588             sentinel,
 589             outer,
 590             key;
 591
 592         this.__initialize(root, visitor);
 593
 594         sentinel = {};
 595
 596         // reference
 597         worklist = this.__worklist;
 598         leavelist = this.__leavelist;
 599
 600         // initialize
 601         outer = {
 602             root: root
 603         };
 604         element = new Element(root, null, null, new Reference(outer, 'root'));
 605         worklist.push(element);
 606         leavelist.push(element);
 607
 608         while (worklist.length) {
 609             element = worklist.pop();
 610
 611             if (element === sentinel) {
 612                 element = leavelist.pop();
 613
 614                 target = this.__execute(visitor.leave, element);
 615
 616                 // node may be replaced with null,
 617                 // so distinguish between undefined and null in this place
 618                 if (target !== undefined && target !== BREAK && target !== SKIP && target !== REMOVE) {
 619                     // replace
 620                     element.ref.replace(target);
 621                 }
 622
 623                 if (this.__state === REMOVE || target === REMOVE) {
 624                     removeElem(element);
 625                 }
 626
 627                 if (this.__state === BREAK || target === BREAK) {
 628                     return outer.root;
 629                 }
 630                 continue;
 631             }
 632
 633             target = this.__execute(visitor.enter, element);
 634
 635             // node may be replaced with null,
 636             // so distinguish between undefined and null in this place
 637             if (target !== undefined && target !== BREAK && target !== SKIP && target !== REMOVE) {
 638                 // replace
 639                 element.ref.replace(target);
 640                 element.node = target;
 641             }
 642
 643             if (this.__state === REMOVE || target === REMOVE) {
 644                 removeElem(element);
 645                 element.node = null;
 646             }
 647
 648             if (this.__state === BREAK || target === BREAK) {
 649                 return outer.root;
 650             }
 651
 652             // node may be null
 653             node = element.node;
 654             if (!node) {
 655                 continue;
 656             }
 657
 658             worklist.push(sentinel);
 659             leavelist.push(element);
 660
 661             if (this.__state === SKIP || target === SKIP) {
 662                 continue;
 663             }
 664
 665             nodeType = element.wrap || node.type;
 666             candidates = this.__keys[nodeType];
 667             if (!candidates) {
 668                 if (this.__fallback) {
 669                     candidates = objectKeys(node);
 670                 } else {
 671                     throw new Error('Unknown node type ' + nodeType + '.');
 672                 }
 673             }
 674
 675             current = candidates.length;
 676             while ((current -= 1) >= 0) {
 677                 key = candidates[current];
 678                 candidate = node[key];
 679                 if (!candidate) {
 680                     continue;
 681                 }
 682
 683                 if (isArray(candidate)) {
 684                     current2 = candidate.length;
 685                     while ((current2 -= 1) >= 0) {
 686                         if (!candidate[current2]) {
 687                             continue;
 688                         }
 689                         if (isProperty(nodeType, candidates[current])) {
 690                             element = new Element(candidate[current2], [key, current2], 'Property', new Reference(candidate, current2));
 691                         } else if (isNode(candidate[current2])) {
 692                             element = new Element(candidate[current2], [key, current2], null, new Reference(candidate, current2));
 693                         } else {
 694                             continue;
 695                         }
 696                         worklist.push(element);
 697                     }
 698                 } else if (isNode(candidate)) {
 699                     worklist.push(new Element(candidate, key, null, new Reference(node, key)));
 700                 }
 701             }
 702         }
 703
 704         return outer.root;
 705     };
 706
 707     function traverse(root, visitor) {
 708         var controller = new Controller();
 709         return controller.traverse(root, visitor);
 710     }
 711
 712     function replace(root, visitor) {
 713         var controller = new Controller();
 714         return controller.replace(root, visitor);
 715     }
 716
 717     function extendCommentRange(comment, tokens) {
 718         var target;
 719
 720         target = upperBound(tokens, function search(token) {
 721             return token.range[0] > comment.range[0];
 722         });
 723
 724         comment.extendedRange = [comment.range[0], comment.range[1]];
 725
 726         if (target !== tokens.length) {
 727             comment.extendedRange[1] = tokens[target].range[0];
 728         }
 729
 730         target -= 1;
 731         if (target >= 0) {
 732             comment.extendedRange[0] = tokens[target].range[1];
 733         }
 734
 735         return comment;
 736     }
 737
 738     function attachComments(tree, providedComments, tokens) {
 739         // At first, we should calculate extended comment ranges.
 740         var comments = [], comment, len, i, cursor;
 741
 742         if (!tree.range) {
 743             throw new Error('attachComments needs range information');
 744         }
 745
 746         // tokens array is empty, we attach comments to tree as 'leadingComments'
 747         if (!tokens.length) {
 748             if (providedComments.length) {
 749                 for (i = 0, len = providedComments.length; i < len; i += 1) {
 750                     comment = deepCopy(providedComments[i]);
 751                     comment.extendedRange = [0, tree.range[0]];
 752                     comments.push(comment);
 753                 }
 754                 tree.leadingComments = comments;
 755             }
 756             return tree;
 757         }
 758
 759         for (i = 0, len = providedComments.length; i < len; i += 1) {
 760             comments.push(extendCommentRange(deepCopy(providedComments[i]), tokens));
 761         }
 762
 763         // This is based on John Freeman's implementation.
 764         cursor = 0;
 765         traverse(tree, {
 766             enter: function (node) {
 767                 var comment;
 768
 769                 while (cursor < comments.length) {
 770                     comment = comments[cursor];
 771                     if (comment.extendedRange[1] > node.range[0]) {
 772                         break;
 773                     }
 774
 775                     if (comment.extendedRange[1] === node.range[0]) {
 776                         if (!node.leadingComments) {
 777                             node.leadingComments = [];
 778                         }
 779                         node.leadingComments.push(comment);
 780                         comments.splice(cursor, 1);
 781                     } else {
 782                         cursor += 1;
 783                     }
 784                 }
 785
 786                 // already out of owned node
 787                 if (cursor === comments.length) {
 788                     return VisitorOption.Break;
 789                 }
 790
 791                 if (comments[cursor].extendedRange[0] > node.range[1]) {
 792                     return VisitorOption.Skip;
 793                 }
 794             }
 795         });
 796
 797         cursor = 0;
 798         traverse(tree, {
 799             leave: function (node) {
 800                 var comment;
 801
 802                 while (cursor < comments.length) {
 803                     comment = comments[cursor];
 804                     if (node.range[1] < comment.extendedRange[0]) {
 805                         break;
 806                     }
 807
 808                     if (node.range[1] === comment.extendedRange[0]) {
 809                         if (!node.trailingComments) {
 810                             node.trailingComments = [];
 811                         }
 812                         node.trailingComments.push(comment);
 813                         comments.splice(cursor, 1);
 814                     } else {
 815                         cursor += 1;
 816                     }
 817                 }
 818
 819                 // already out of owned node
 820                 if (cursor === comments.length) {
 821                     return VisitorOption.Break;
 822                 }
 823
 824                 if (comments[cursor].extendedRange[0] > node.range[1]) {
 825                     return VisitorOption.Skip;
 826                 }
 827             }
 828         });
 829
 830         return tree;
 831     }
 832
 833     exports.version = '1.8.1-dev';
 834     exports.Syntax = Syntax;
 835     exports.traverse = traverse;
 836     exports.replace = replace;
 837     exports.attachComments = attachComments;
 838     exports.VisitorKeys = VisitorKeys;
 839     exports.VisitorOption = VisitorOption;
 840     exports.Controller = Controller;
 841     exports.cloneEnvironment = function () { return clone({}); };
 842
 843     return exports;
 844 }));
 845 /* vim: set sw=4 ts=4 et tw=80 : */