text: var _ = require('../util')
  var isObject = _.isObject
  var isPlainObject = _.isPlainObject
  var textParser = require('../parsers/text')
  var expParser = require('../parsers/expression')
  var templateParser = require('../parsers/template')
  var compiler = require('../compiler')
  var uid = 0
  
  // async component resolution states
  var UNRESOLVED = 0
  var PENDING = 1
  var RESOLVED = 2
  var ABORTED = 3
  
  module.exports = {
  
    /**
     * Setup.
     */
  
    bind: function () {
      // uid as a cache identifier
      this.id = '__v_repeat_' + (++uid)
      // setup anchor nodes
      this.start = _.createAnchor('v-repeat-start')
      this.end = _.createAnchor('v-repeat-end')
      _.replace(this.el, this.end)
      _.before(this.start, this.end)
      // check if this is a block repeat
      this.template = _.isTemplate(this.el)
        ? templateParser.parse(this.el, true)
        : this.el
      // check other directives that need to be handled
      // at v-repeat level
      this.checkIf()
      this.checkRef()
      this.checkComponent()
      // check for trackby param
      this.idKey =
        this._checkParam('track-by') ||
        this._checkParam('trackby') // 0.11.0 compat
      // check for transition stagger
      var stagger = +this._checkParam('stagger')
      this.enterStagger = +this._checkParam('enter-stagger') || stagger
      this.leaveStagger = +this._checkParam('leave-stagger') || stagger
      this.cache = Object.create(null)
    },
  
    /**
     * Warn against v-if usage.
     */
  
    checkIf: function () {
      if (_.attr(this.el, 'if') !== null) {
        _.warn(
          'Don\'t use v-if with v-repeat. ' +
          'Use v-show or the "filterBy" filter instead.'
        )
      }
    },
  
    /**
     * Check if v-ref/ v-el is also present.
     */
  
    checkRef: function () {
      var refID = _.attr(this.el, 'ref')
      this.refID = refID
        ? this.vm.$interpolate(refID)
        : null
      var elId = _.attr(this.el, 'el')
      this.elId = elId
        ? this.vm.$interpolate(elId)
        : null
    },
  
    /**
     * Check the component constructor to use for repeated
     * instances. If static we resolve it now, otherwise it
     * needs to be resolved at build time with actual data.
     */
  
    checkComponent: function () {
      this.componentState = UNRESOLVED
      var options = this.vm.$options
      var id = _.checkComponent(this.el, options)
      if (!id) {
        // default constructor
        this.Ctor = _.Vue
        // inline repeats should inherit
        this.inherit = true
        // important: transclude with no options, just
        // to ensure block start and block end
        this.template = compiler.transclude(this.template)
        var copy = _.extend({}, options)
        copy._asComponent = false
        this._linkFn = compiler.compile(this.template, copy)
      } else {
        this.Ctor = null
        this.asComponent = true
        // check inline-template
        if (this._checkParam('inline-template') !== null) {
          // extract inline template as a DocumentFragment
          this.inlineTemplate = _.extractContent(this.el, true)
        }
        var tokens = textParser.parse(id)
        if (tokens) {
          // dynamic component to be resolved later
          var ctorExp = textParser.tokensToExp(tokens)
          this.ctorGetter = expParser.parse(ctorExp).get
        } else {
          // static
          this.componentId = id
          this.pendingData = null
        }
      }
    },
  
    resolveComponent: function () {
      this.componentState = PENDING
      this.vm._resolveComponent(this.componentId, _.bind(function (Ctor) {
        if (this.componentState === ABORTED) {
          return
        }
        this.Ctor = Ctor
        this.componentState = RESOLVED
        this.realUpdate(this.pendingData)
        this.pendingData = null
      }, this))
    },
  
      /**
     * Resolve a dynamic component to use for an instance.
     * The tricky part here is that there could be dynamic
     * components depending on instance data.
     *
     * @param {Object} data
     * @param {Object} meta
     * @return {Function}
     */
  
    resolveDynamicComponent: function (data, meta) {
      // create a temporary context object and copy data
      // and meta properties onto it.
      // use _.define to avoid accidentally overwriting scope
      // properties.
      var context = Object.create(this.vm)
      var key
      for (key in data) {
        _.define(context, key, data[key])
      }
      for (key in meta) {
        _.define(context, key, meta[key])
      }
      var id = this.ctorGetter.call(context, context)
      var Ctor = _.resolveAsset(this.vm.$options, 'components', id)
      _.assertAsset(Ctor, 'component', id)
      if (!Ctor.options) {
        _.warn(
          'Async resolution is not supported for v-repeat ' +
          '+ dynamic component. (component: ' + id + ')'
        )
        return _.Vue
      }
      return Ctor
    },
  
    /**
     * Update.
     * This is called whenever the Array mutates. If we have
     * a component, we might need to wait for it to resolve
     * asynchronously.
     *
     * @param {Array|Number|String} data
     */
  
    update: function (data) {
      if (this.componentId) {
        var state = this.componentState
        if (state === UNRESOLVED) {
          this.pendingData = data
          // once resolved, it will call realUpdate
          this.resolveComponent()
        } else if (state === PENDING) {
          this.pendingData = data
        } else if (state === RESOLVED) {
          this.realUpdate(data)
        }
      } else {
        this.realUpdate(data)
      }
    },
  
    /**
     * The real update that actually modifies the DOM.
     *
     * @param {Array|Number|String} data
     */
  
    realUpdate: function (data) {
      this.vms = this.diff(data, this.vms)
      // update v-ref
      if (this.refID) {
        this.vm.$[this.refID] = this.converted
          ? toRefObject(this.vms)
          : this.vms
      }
      if (this.elId) {
        this.vm.$$[this.elId] = this.vms.map(function (vm) {
          return vm.$el
        })
      }
    },
  
    /**
     * Diff, based on new data and old data, determine the
     * minimum amount of DOM manipulations needed to make the
     * DOM reflect the new data Array.
     *
     * The algorithm diffs the new data Array by storing a
     * hidden reference to an owner vm instance on previously
     * seen data. This allows us to achieve O(n) which is
     * better than a levenshtein distance based algorithm,
     * which is O(m * n).
     *
     * @param {Array} data
     * @param {Array} oldVms
     * @return {Array}
     */
  
    diff: function (data, oldVms) {
      var idKey = this.idKey
      var converted = this.converted
      var start = this.start
      var end = this.end
      var inDoc = _.inDoc(start)
      var alias = this.arg
      var init = !oldVms
      var vms = new Array(data.length)
      var obj, raw, vm, i, l, primitive
      // First pass, go through the new Array and fill up
      // the new vms array. If a piece of data has a cached
      // instance for it, we reuse it. Otherwise build a new
      // instance.
      for (i = 0, l = data.length; i < l; i++) {
        obj = data[i]
        raw = converted ? obj.$value : obj
        primitive = !isObject(raw)
        vm = !init && this.getVm(raw, i, converted ? obj.$key : null)
        if (vm) { // reusable instance
          vm._reused = true
          vm.$index = i // update $index
          // update data for track-by or object repeat,
          // since in these two cases the data is replaced
          // rather than mutated.
          if (idKey || converted || primitive) {
            if (alias) {
              vm[alias] = raw
            } else if (_.isPlainObject(raw)) {
              vm.$data = raw
            } else {
              vm.$value = raw
            }
          }
        } else { // new instance
          vm = this.build(obj, i, true)
          vm._reused = false
        }
        vms[i] = vm
        // insert if this is first run
        if (init) {
          vm.$before(end)
        }
      }
      // if this is the first run, we're done.
      if (init) {
        return vms
      }
      // Second pass, go through the old vm instances and
      // destroy those who are not reused (and remove them
      // from cache)
      var removalIndex = 0
      var totalRemoved = oldVms.length - vms.length
      for (i = 0, l = oldVms.length; i < l; i++) {
        vm = oldVms[i]
        if (!vm._reused) {
          this.uncacheVm(vm)
          vm.$destroy(false, true) // defer cleanup until removal
          this.remove(vm, removalIndex++, totalRemoved, inDoc)
        }
      }
      // final pass, move/insert new instances into the
      // right place.
      var targetPrev, prevEl, currentPrev
      var insertionIndex = 0
      for (i = 0, l = vms.length; i < l; i++) {
        vm = vms[i]
        // this is the vm that we should be after
        targetPrev = vms[i - 1]
        prevEl = targetPrev
          ? targetPrev._staggerCb
            ? targetPrev._staggerAnchor
            : targetPrev._blockEnd || targetPrev.$el
          : start
        if (vm._reused && !vm._staggerCb) {
          currentPrev = findPrevVm(vm, start, this.id)
          if (currentPrev !== targetPrev) {
            this.move(vm, prevEl)
          }
        } else {
          // new instance, or still in stagger.
          // insert with updated stagger index.
          this.insert(vm, insertionIndex++, prevEl, inDoc)
        }
        vm._reused = false
      }
      return vms
    },
  
    /**
     * Build a new instance and cache it.
     *
     * @param {Object} data
     * @param {Number} index
     * @param {Boolean} needCache
     */
  
    build: function (data, index, needCache) {
      var meta = { $index: index }
      if (this.converted) {
        meta.$key = data.$key
      }
      var raw = this.converted ? data.$value : data
      var alias = this.arg
      if (alias) {
        data = {}
        data[alias] = raw
      } else if (!isPlainObject(raw)) {
        // non-object values
        data = {}
        meta.$value = raw
      } else {
        // default
        data = raw
      }
      // resolve constructor
      var Ctor = this.Ctor || this.resolveDynamicComponent(data, meta)
      var parent = this._host || this.vm
      var vm = parent.$addChild({
        el: templateParser.clone(this.template),
        data: data,
        inherit: this.inherit,
        template: this.inlineTemplate,
        // repeater meta, e.g. $index, $key
        _meta: meta,
        // mark this as an inline-repeat instance
        _repeat: this.inherit,
        // is this a component?
        _asComponent: this.asComponent,
        // linker cachable if no inline-template
        _linkerCachable: !this.inlineTemplate && Ctor !== _.Vue,
        // pre-compiled linker for simple repeats
        _linkFn: this._linkFn,
        // identifier, shows that this vm belongs to this collection
        _repeatId: this.id,
        // transclusion content owner
        _context: this.vm
      }, Ctor)
      // cache instance
      if (needCache) {
        this.cacheVm(raw, vm, index, this.converted ? meta.$key : null)
      }
      // sync back changes for two-way bindings of primitive values
      var type = typeof raw
      var dir = this
      if (
        this.rawType === 'object' &&
        (type === 'string' || type === 'number')
      ) {
        vm.$watch(alias || '$value', function (val) {
          if (dir.filters) {
            _.warn(
              'You seem to be mutating the $value reference of ' +
              'a v-repeat instance (likely through v-model) ' +
              'and filtering the v-repeat at the same time. ' +
              'This will not work properly with an Array of ' +
              'primitive values. Please use an Array of ' +
              'Objects instead.'
            )
          }
          dir._withLock(function () {
            if (dir.converted) {
              dir.rawValue[vm.$key] = val
            } else {
              dir.rawValue.$set(vm.$index, val)
            }
          })
        })
      }
      return vm
    },
  
    /**
     * Unbind, teardown everything
     */
  
    unbind: function () {
      this.componentState = ABORTED
      if (this.refID) {
        this.vm.$[this.refID] = null
      }
      if (this.vms) {
        var i = this.vms.length
        var vm
        while (i--) {
          vm = this.vms[i]
          this.uncacheVm(vm)
          vm.$destroy()
        }
      }
    },
  
    /**
     * Cache a vm instance based on its data.
     *
     * If the data is an object, we save the vm's reference on
     * the data object as a hidden property. Otherwise we
     * cache them in an object and for each primitive value
     * there is an array in case there are duplicates.
     *
     * @param {Object} data
     * @param {Vue} vm
     * @param {Number} index
     * @param {String} [key]
     */
  
    cacheVm: function (data, vm, index, key) {
      var idKey = this.idKey
      var cache = this.cache
      var primitive = !isObject(data)
      var id
      if (key || idKey || primitive) {
        id = idKey
          ? idKey === '$index'
            ? index
            : data[idKey]
          : (key || index)
        if (!cache[id]) {
          cache[id] = vm
        } else if (!primitive && idKey !== '$index') {
          _.warn('Duplicate track-by key in v-repeat: ' + id)
        }
      } else {
        id = this.id
        if (data.hasOwnProperty(id)) {
          if (data[id] === null) {
            data[id] = vm
          } else {
            _.warn(
              'Duplicate objects are not supported in v-repeat ' +
              'when using components or transitions.'
            )
          }
        } else {
          _.define(data, id, vm)
        }
      }
      vm._raw = data
    },
  
    /**
     * Try to get a cached instance from a piece of data.
     *
     * @param {Object} data
     * @param {Number} index
     * @param {String} [key]
     * @return {Vue|undefined}
     */
  
    getVm: function (data, index, key) {
      var idKey = this.idKey
      var primitive = !isObject(data)
      if (key || idKey || primitive) {
        var id = idKey
          ? idKey === '$index'
            ? index
            : data[idKey]
          : (key || index)
        return this.cache[id]
      } else {
        return data[this.id]
      }
    },
  
    /**
     * Delete a cached vm instance.
     *
     * @param {Vue} vm
     */
  
    uncacheVm: function (vm) {
      var data = vm._raw
      var idKey = this.idKey
      var index = vm.$index
      // fix #948: avoid accidentally fall through to
      // a parent repeater which happens to have $key.
      var key = vm.hasOwnProperty('$key') && vm.$key
      var primitive = !isObject(data)
      if (idKey || key || primitive) {
        var id = idKey
          ? idKey === '$index'
            ? index
            : data[idKey]
          : (key || index)
        this.cache[id] = null
      } else {
        data[this.id] = null
        vm._raw = null
      }
    },
  
    /**
     * Pre-process the value before piping it through the
     * filters, and convert non-Array objects to arrays.
     *
     * This function will be bound to this directive instance
     * and passed into the watcher.
     *
     * @param {*} value
     * @return {Array}
     * @private
     */
  
    _preProcess: function (value) {
      // regardless of type, store the un-filtered raw value.
      this.rawValue = value
      var type = this.rawType = typeof value
      if (!isPlainObject(value)) {
        this.converted = false
        if (type === 'number') {
          value = range(value)
        } else if (type === 'string') {
          value = _.toArray(value)
        }
        return value || []
      } else {
        // convert plain object to array.
        var keys = Object.keys(value)
        var i = keys.length
        var res = new Array(i)
        var key
        while (i--) {
          key = keys[i]
          res[i] = {
            $key: key,
            $value: value[key]
          }
        }
        this.converted = true
        return res
      }
    },
  
    /**
     * Insert an instance.
     *
     * @param {Vue} vm
     * @param {Number} index
     * @param {Node} prevEl
     * @param {Boolean} inDoc
     */
  
    insert: function (vm, index, prevEl, inDoc) {
      if (vm._staggerCb) {
        vm._staggerCb.cancel()
        vm._staggerCb = null
      }
      var staggerAmount = this.getStagger(vm, index, null, 'enter')
      if (inDoc && staggerAmount) {
        // create an anchor and insert it synchronously,
        // so that we can resolve the correct order without
        // worrying about some elements not inserted yet
        var anchor = vm._staggerAnchor
        if (!anchor) {
          anchor = vm._staggerAnchor = _.createAnchor('stagger-anchor')
          anchor.__vue__ = vm
        }
        _.after(anchor, prevEl)
        var op = vm._staggerCb = _.cancellable(function () {
          vm._staggerCb = null
          vm.$before(anchor)
          _.remove(anchor)
        })
        setTimeout(op, staggerAmount)
      } else {
        vm.$after(prevEl)
      }
    },
  
    /**
     * Move an already inserted instance.
     *
     * @param {Vue} vm
     * @param {Node} prevEl
     */
  
    move: function (vm, prevEl) {
      vm.$after(prevEl, null, false)
    },
  
    /**
     * Remove an instance.
     *
     * @param {Vue} vm
     * @param {Number} index
     * @param {Boolean} inDoc
     */
  
    remove: function (vm, index, total, inDoc) {
      if (vm._staggerCb) {
        vm._staggerCb.cancel()
        vm._staggerCb = null
        // it's not possible for the same vm to be removed
        // twice, so if we have a pending stagger callback,
        // it means this vm is queued for enter but removed
        // before its transition started. Since it is already
        // destroyed, we can just leave it in detached state.
        return
      }
      var staggerAmount = this.getStagger(vm, index, total, 'leave')
      if (inDoc && staggerAmount) {
        var op = vm._staggerCb = _.cancellable(function () {
          vm._staggerCb = null
          remove()
        })
        setTimeout(op, staggerAmount)
      } else {
        remove()
      }
      function remove () {
        vm.$remove(function () {
          vm._cleanup()
        })
      }
    },
  
    /**
     * Get the stagger amount for an insertion/removal.
     *
     * @param {Vue} vm
     * @param {Number} index
     * @param {String} type
     * @param {Number} total
     */
  
    getStagger: function (vm, index, total, type) {
      type = type + 'Stagger'
      var transition = vm.$el.__v_trans
      var hooks = transition && transition.hooks
      var hook = hooks && (hooks[type] || hooks.stagger)
      return hook
        ? hook.call(vm, index, total)
        : index * this[type]
    }
  
  }
  
  /**
   * Helper to find the previous element that is an instance
   * root node. This is necessary because a destroyed vm's
   * element could still be lingering in the DOM before its
   * leaving transition finishes, but its __vue__ reference
   * should have been removed so we can skip them.
   *
   * If this is a block repeat, we want to make sure we only
   * return vm that is bound to this v-repeat. (see #929)
   *
   * @param {Vue} vm
   * @param {Comment|Text} anchor
   * @return {Vue}
   */
  
  function findPrevVm (vm, anchor, id) {
    var el = vm.$el.previousSibling
    while (
      (!el.__vue__ || el.__vue__.$options._repeatId !== id) &&
      el !== anchor
    ) {
      el = el.previousSibling
    }
    return el.__vue__
  }
  
  /**
   * Create a range array from given number.
   *
   * @param {Number} n
   * @return {Array}
   */
  
  function range (n) {
    var i = -1
    var ret = new Array(n)
    while (++i < n) {
      ret[i] = i
    }
    return ret
  }
  
  /**
   * Convert a vms array to an object ref for v-ref on an
   * Object value.
   *
   * @param {Array} vms
   * @return {Object}
   */
  
  function toRefObject (vms) {
    var ref = {}
    for (var i = 0, l = vms.length; i < l; i++) {
      ref[vms[i].$key] = vms[i]
    }
    return ref
  }
  