review.tizen.org Git - platform/framework/web/crosswalk-tizen.git/blob

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