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