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