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 : */