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