dom-repeat.html

<!--
@license
Copyright (c) 2015 The Polymer Project Authors. All rights reserved.
This code may only be used under the BSD style license found at http://polymer.github.io/LICENSE.txt
The complete set of authors may be found at http://polymer.github.io/AUTHORS.txt
The complete set of contributors may be found at http://polymer.github.io/CONTRIBUTORS.txt
Code distributed by Google as part of the polymer project is also
subject to an additional IP rights grant found at http://polymer.github.io/PATENTS.txt
-->

<!--

The `dom-repeat` element is a custom `HTMLTemplateElement` type extension that
automatically stamps and binds one instance of template content to each object
in a user-provided array.  `dom-repeat` accepts an `items` property, and one
instance of the template is stamped for each item into the DOM at the location
of the `dom-repeat` element.  The `item` property will be set on each instance's
binding scope, thus templates should bind to sub-properties of `item`.

Example:

```html
<dom-module id="employee-list">

  <template>

    <div> Employee list: </div>
    <template is="dom-repeat" items="{{employees}}">
        <div>First name: <span>{{item.first}}</span></div>
        <div>Last name: <span>{{item.last}}</span></div>
    </template>

  </template>

  <script>
    Polymer({
      is: 'employee-list',
      ready: function() {
        this.employees = [
            {first: 'Bob', last: 'Smith'},
            {first: 'Sally', last: 'Johnson'},
            ...
        ];
      }
    });
  </script>

</dom-module>
```

Notifications for changes to items sub-properties will be forwarded to template
instances, which will update via the normal structured data notification system.

Mutations to the `items` array itself should me made using the Array
mutation API's on `Polymer.Base` (`push`, `pop`, `splice`, `shift`,
`unshift`), and template instances will be kept in sync with the data in the
array.

Events caught by event handlers within the `dom-repeat` template will be
decorated with a `model` property, which represents the binding scope for
each template instance.  The model is an instance of Polymer.Base, and should
be used to manipulate data on the instance, for example
`event.model.set('item.checked', true);`.

Alternatively, the model for a template instance for an element stamped by
a `dom-repeat` can be obtained using the `modelForElement` API on the
`dom-repeat` that stamped it, for example
`this.$.domRepeat.modelForElement(event.target).set('item.checked', true);`.
This may be useful for manipulating instance data of event targets obtained
by event handlers on parents of the `dom-repeat` (event delegation).

A view-specific filter/sort may be applied to each `dom-repeat` by supplying a
`filter` and/or `sort` property.  This may be a string that names a function on
the host, or a function may be assigned to the property directly.  The functions
should implemented following the standard `Array` filter/sort API.

In order to re-run the filter or sort functions based on changes to sub-fields
of `items`, the `observe` property may be set as a space-separated list of
`item` sub-fields that should cause a re-filter/sort when modified.  If
the filter or sort function depends on properties not contained in `items`,
the user should observe changes to those properties and call `render` to update
the view based on the dependency change.

For example, for an `dom-repeat` with a filter of the following:

```js
isEngineer: function(item) {
    return item.type == 'engineer' || item.manager.type == 'engineer';
}
```

Then the `observe` property should be configured as follows:

```html
<template is="dom-repeat" items="{{employees}}"
          filter="isEngineer" observe="type manager.type">
```

-->

<link rel="import" href="templatizer.html">
<link rel="import" href="../collection.html">

<script>

  Polymer({

    is: 'dom-repeat',
    extends: 'template',

    /**
     * Fired whenever DOM is added or removed by this template (by
     * default, rendering occurs lazily).  To force immediate rendering, call
     * `render`.
     *
     * @event dom-change
     */

    properties: {

      /**
       * An array containing items determining how many instances of the template
       * to stamp and that that each template instance should bind to.
       */
      items: {
        type: Array
      },

      /**
       * The name of the variable to add to the binding scope for the array
       * element associated with a given template instance.
       */
      as: {
        type: String,
        value: 'item'
      },

      /**
       * The name of the variable to add to the binding scope with the index
       * for the inst.  If `sort` is provided, the index will reflect the
       * sorted order (rather than the original array order).
       */
      indexAs: {
        type: String,
        value: 'index'
      },

      /**
       * A function that should determine the sort order of the items.  This
       * property should either be provided as a string, indicating a method
       * name on the element's host, or else be an actual function.  The
       * function should match the sort function passed to `Array.sort`.
       * Using a sort function has no effect on the underlying `items` array.
       */
      sort: {
        type: Function,
        observer: '_sortChanged'
      },

      /**
       * A function that can be used to filter items out of the view.  This
       * property should either be provided as a string, indicating a method
       * name on the element's host, or else be an actual function.  The
       * function should match the sort function passed to `Array.filter`.
       * Using a filter function has no effect on the underlying `items` array.
       */
      filter: {
        type: Function,
        observer: '_filterChanged'
      },

      /**
       * When using a `filter` or `sort` function, the `observe` property
       * should be set to a space-separated list of the names of item
       * sub-fields that should trigger a re-sort or re-filter when changed.
       * These should generally be fields of `item` that the sort or filter
       * function depends on.
       */
      observe: {
        type: String,
        observer: '_observeChanged'
      },

      /**
       * When using a `filter` or `sort` function, the `delay` property
       * determines a debounce time after a change to observed item
       * properties that must pass before the filter or sort is re-run.
       * This is useful in rate-limiting shuffing of the view when
       * item changes may be frequent.
       */
      delay: Number,

      /**
       * Defines an initial count of template instances to render after setting
       * the `items` array, before the next paint, and puts the `dom-repeat`
       * into "chunking mode".  The remaining items will be created and rendered
       * incrementally at each animation frame therof until all instances have
       * been rendered.
       */
      initialCount: {
        type: Number,
        observer: '_initializeChunking'
      },

      /**
       * When `initialCount` is used, this property defines a frame rate to
       * target by throttling the number of instances rendered each frame to
       * not exceed the budget for the target frame rate.  Setting this to a
       * higher number will allow lower latency and higher throughput for
       * things like event handlers, but will result in a longer time for the
       * remaining items to complete rendering.
       */
      targetFramerate: {
        type: Number,
        value: 20
      },

      _targetFrameTime: {
        computed: '_computeFrameTime(targetFramerate)'
      }

    },

    behaviors: [
      Polymer.Templatizer
    ],

    observers: [
      '_itemsChanged(items.*)'
    ],

    created: function() {
      this._instances = [];
      this._pool = [];
      this._limit = Infinity;
      var self = this;
      this._boundRenderChunk = function() {
        self._renderChunk();
      };
    },

    detached: function() {
      for (var i=0; i<this._instances.length; i++) {
        this._detachInstance(i);
      }
    },

    attached: function() {
      var parent = Polymer.dom(Polymer.dom(this).parentNode);
      for (var i=0; i<this._instances.length; i++) {
        this._attachInstance(i, parent);
      }
    },

    ready: function() {
      // Template instance props that should be excluded from forwarding
      this._instanceProps = {
        __key__: true
      };
      this._instanceProps[this.as] = true;
      this._instanceProps[this.indexAs] = true;
      // Templatizing (generating the instance constructor) needs to wait
      // until ready, since won't have its template content handed back to
      // it until then
      if (!this.ctor) {
        this.templatize(this);
      }
    },

    _sortChanged: function(sort) {
      var dataHost = this._getRootDataHost();
      this._sortFn = sort && (typeof sort == 'function' ? sort :
        function() { return dataHost[sort].apply(dataHost, arguments); });
      this._needFullRefresh = true;
      if (this.items) {
        this._debounceTemplate(this._render);
      }
    },

    _filterChanged: function(filter) {
      var dataHost = this._getRootDataHost();
      this._filterFn = filter && (typeof filter == 'function' ? filter :
        function() { return dataHost[filter].apply(dataHost, arguments); });
      this._needFullRefresh = true;
      if (this.items) {
        this._debounceTemplate(this._render);
      }
    },

    _computeFrameTime: function(rate) {
      return Math.ceil(1000/rate);
    },

    _initializeChunking: function() {
      if (this.initialCount) {
        this._limit = this.initialCount;
        this._chunkCount = this.initialCount;
        this._lastChunkTime = performance.now();
      }
    },

    _tryRenderChunk: function() {
      // Debounced so that multiple calls through `_render` between animation
      // frames only queue one new rAF (e.g. array mutation & chunked render)
      if (this.items && this._limit < this.items.length) {
        this.debounce('renderChunk', this._requestRenderChunk);
      }
    },

    _requestRenderChunk: function() {
      requestAnimationFrame(this._boundRenderChunk);
    },

    _renderChunk: function() {
      // Simple auto chunkSize throttling algorithm based on feedback loop:
      // measure actual time between frames and scale chunk count by ratio
      // of target/actual frame time
      var lastChunkTime = this._lastChunkTime;
      var currChunkTime = performance.now();
      var ratio = this._targetFrameTime / (currChunkTime - lastChunkTime);
      this._chunkCount = Math.round(this._chunkCount * ratio) || 1;
      this._limit += this._chunkCount;
      this._lastChunkTime = currChunkTime;
      this._debounceTemplate(this._render);
    },

    _observeChanged: function() {
      this._observePaths = this.observe &&
        this.observe.replace('.*', '.').split(' ');
    },

    _itemsChanged: function(change) {
      if (change.path == 'items') {
        if (Array.isArray(this.items)) {
          this.collection = Polymer.Collection.get(this.items);
        } else if (!this.items) {
          this.collection = null;
        } else {
          this._error(this._logf('dom-repeat', 'expected array for `items`,' +
            ' found', this.items));
        }
        this._keySplices = [];
        this._indexSplices = [];
        this._needFullRefresh = true;
        this._initializeChunking();
        this._debounceTemplate(this._render);
      } else if (change.path == 'items.splices') {
        this._keySplices = this._keySplices.concat(change.value.keySplices);
        this._indexSplices = this._indexSplices.concat(change.value.indexSplices);
        this._debounceTemplate(this._render);
      } else { // items.*
        // slice off 'items.' ('items.'.length == 6)
        var subpath = change.path.slice(6);
        this._forwardItemPath(subpath, change.value);
        this._checkObservedPaths(subpath);
      }
    },

    _checkObservedPaths: function(path) {
      if (this._observePaths) {
        path = path.substring(path.indexOf('.') + 1);
        var paths = this._observePaths;
        for (var i=0; i<paths.length; i++) {
          if (path.indexOf(paths[i]) === 0) {
            // TODO(kschaaf): interim solution: ideally this is just an incremental
            // insertion sort of the changed item
            this._needFullRefresh = true;
            if (this.delay) {
              this.debounce('render', this._render, this.delay);
            } else {
              this._debounceTemplate(this._render);
            }
            return;
          }
        }
      }
    },

    /**
     * Forces the element to render its content. Normally rendering is
     * asynchronous to a provoking change. This is done for efficiency so
     * that multiple changes trigger only a single render. The render method
     * should be called if, for example, template rendering is required to
     * validate application state.
     */
    render: function() {
      // Queue this repeater, then flush all in order
      this._needFullRefresh = true;
      this._debounceTemplate(this._render);
      this._flushTemplates();
    },

    _render: function() {
      var c = this.collection;
      // Choose rendering path: full vs. incremental using splices
      if (this._needFullRefresh) {
        // Full refresh when items, sort, or filter change, or when render() called
        this._applyFullRefresh();
        this._needFullRefresh = false;
      } else if (this._keySplices.length) {
        // Incremental refresh when splices were queued
        if (this._sortFn) {
          this._applySplicesUserSort(this._keySplices);
        } else {
          if (this._filterFn) {
            // TODK(kschaaf): Filtering using array sort takes slow path
            this._applyFullRefresh();
          } else {
            this._applySplicesArrayOrder(this._indexSplices);
          }
        }
      } else {
        // Otherwise only limit changed; no change to instances, just need to
        // upgrade more placeholders to instances
      }
      this._keySplices = [];
      this._indexSplices = [];
      // Update final _keyToInstIdx, instance indices, and replace placeholders
      var keyToIdx = this._keyToInstIdx = {};
      for (var i=this._instances.length-1; i>=0; i--) {
        var inst = this._instances[i];
        if (inst.isPlaceholder && i<this._limit) {
          inst = this._upgradePlaceholder(i, inst.__key__);
        } else if (!inst.isPlaceholder && i>=this._limit) {
          inst = this._downgradeInstance(i, inst.__key__);
        }
        keyToIdx[inst.__key__] = i;
        if (!inst.isPlaceholder) {
          inst.__setProperty(this.indexAs, i, true);
        }
      }
      // Reset the pool
      // TODO(kschaaf): Reuse pool across turns and nested templates
      // Requires updating parentProps and dealing with the fact that path
      // notifications won't reach instances sitting in the pool, which
      // could result in out-of-sync instances since simply re-setting
      // `item` may not be sufficient if the pooled instance happens to be
      // the same item.
      this._pool.length = 0;
      // Notify users
      this.fire('dom-change');
      // Check to see if we need to render more items
      this._tryRenderChunk();
    },

    // Render method 1: full refesh
    // ----
    // Full list of keys is pulled from the collection, then sorted, filtered,
    // and iterated to create (or reuse) existing instances
    _applyFullRefresh: function() {
      var c = this.collection;
      // Start with unordered keys for user sort,
      // or get them in array order for array order
      var keys;
      if (this._sortFn) {
        keys = c ? c.getKeys() : [];
      } else {
        keys = [];
        var items = this.items;
        if (items) {
          for (var i=0; i<items.length; i++) {
            keys.push(c.getKey(items[i]));
          }
        }
      }
      // Apply user filter to keys
      if (this._filterFn) {
        keys = keys.filter(function(a) {
          return this._filterFn(c.getItem(a));
        }, this);
      }
      // Apply user sort to keys
      if (this._sortFn) {
        keys.sort(function(a, b) {
          return this._sortFn(c.getItem(a), c.getItem(b));
        }.bind(this));
      }
      // Generate instances and assign items and keys
      for (var i=0; i<keys.length; i++) {
        var key = keys[i];
        var inst = this._instances[i];
        if (inst) {
          inst.__key__ = key;
          if (!inst.isPlaceholder && i < this._limit) {
            inst.__setProperty(this.as, c.getItem(key), true);
          }
        } else {
          this._insertPlaceholder(i, key);
        }
      }
      // Remove any extra instances from previous state
      for (var j=this._instances.length-1; j>=i; j--) {
        this._detachAndRemoveInstance(j);
      }
    },

    _keySort: function(a, b) {
      return this.collection.getKey(a) - this.collection.getKey(b);
    },

    _numericSort: function(a, b) {
      return a - b;
    },

    // Render method 2: incremental update using splices with user sort applied
    // ----
    // Removed/added keys are deduped, all removed rows are detached and pooled
    // first, and added rows are insertion-sorted into place using user sort
    _applySplicesUserSort: function(splices) {
      var c = this.collection;
      var instances = this._instances;
      var keyMap = {};
      var sortFn = this._sortFn || this._keySort.bind(this);
      // Dedupe added and removed keys to a final added/removed map
      splices.forEach(function(s) {
        for (var i=0; i<s.removed.length; i++) {
          var key = s.removed[i];
          keyMap[key] = keyMap[key] ? null : -1;
        }
        for (var i=0; i<s.added.length; i++) {
          var key = s.added[i];
          keyMap[key] = keyMap[key] ? null : 1;
        }
      }, this);
      // Convert added/removed key map to added/removed arrays
      var removedIdxs = [];
      var addedKeys = [];
      for (var key in keyMap) {
        if (keyMap[key] === -1) {
          removedIdxs.push(this._keyToInstIdx[key]);
        }
        if (keyMap[key] === 1) {
          addedKeys.push(key);
        }
      }
      // Remove & pool removed instances
      if (removedIdxs.length) {
        // Sort removed instances idx's then remove backwards,
        // so we don't invalidate instance index
        // use numeric sort, default .sort is alphabetic
        removedIdxs.sort(this._numericSort);
        for (var i=removedIdxs.length-1; i>=0 ; i--) {
          var idx = removedIdxs[i];
          // Removed idx may be undefined if item was previously filtered out
          if (idx !== undefined) {
            this._detachAndRemoveInstance(idx);
          }
        }
      }
      // Add instances for added keys
      if (addedKeys.length) {
        // Filter added keys
        if (this._filterFn) {
          addedKeys = addedKeys.filter(function(a) {
            return this._filterFn(c.getItem(a));
          }, this);
        }
        // Sort added keys
        addedKeys.sort(function(a, b) {
          return this._sortFn(c.getItem(a), c.getItem(b));
        }.bind(this));
        // Insertion-sort new instances into place (from pool or newly created)
        var start = 0;
        for (var i=0; i<addedKeys.length; i++) {
          start = this._insertRowUserSort(start, addedKeys[i]);
        }
      }
    },

    _insertRowUserSort: function(start, key) {
      var c = this.collection;
      var item = c.getItem(key);
      var end = this._instances.length - 1;
      var idx = -1;
      var sortFn = this._sortFn || this._keySort.bind(this);
      // Binary search for insertion point
      while (start <= end) {
        var mid = (start + end) >> 1;
        var midKey = this._instances[mid].__key__;
        var cmp = sortFn(c.getItem(midKey), item);
        if (cmp < 0) {
          start = mid + 1;
        } else if (cmp > 0) {
          end = mid - 1;
        } else {
          idx = mid;
          break;
        }
      }
      if (idx < 0) {
        idx = end + 1;
      }
      // Insert instance at insertion point
      this._insertPlaceholder(idx, key);
      return idx;
    },

    // Render method 3: incremental update using splices with array order
    // ----
    // Splices are processed in order; removed rows are pooled, and added
    // rows are as placeholders, and placeholders are updated to
    // actual rows at the end to take full advantage of removed rows
    _applySplicesArrayOrder: function(splices) {
      var c = this.collection;
      splices.forEach(function(s) {
        // Detach & pool removed instances
        for (var i=0; i<s.removed.length; i++) {
          this._detachAndRemoveInstance(s.index);
        }
        for (var i=0; i<s.addedKeys.length; i++) {
          this._insertPlaceholder(s.index+i, s.addedKeys[i]);
        }
      }, this);
    },

    _detachInstance: function(idx) {
      var inst = this._instances[idx];
      if (!inst.isPlaceholder) {
        for (var i=0; i<inst._children.length; i++) {
          var el = inst._children[i];
          Polymer.dom(inst.root).appendChild(el);
        }
        return inst;
      }
    },

    _attachInstance: function(idx, parent) {
      var inst = this._instances[idx];
      if (!inst.isPlaceholder) {
        parent.insertBefore(inst.root, this);
      }
    },

    _detachAndRemoveInstance: function(idx) {
      var inst = this._detachInstance(idx);
      if (inst) {
        this._pool.push(inst);
      }
      this._instances.splice(idx, 1);
    },

    _insertPlaceholder: function(idx, key) {
      this._instances.splice(idx, 0, {
        isPlaceholder: true,
        __key__: key
      });
    },

    _generateInstance: function(idx, key) {
      var model = {
        __key__: key
      };
      model[this.as] = this.collection.getItem(key);
      model[this.indexAs] = idx;
      return this.stamp(model);
    },

    _upgradePlaceholder: function(idx, key) {
      var inst = this._pool.pop();
      if (inst) {
        // TODO(kschaaf): If the pool is shared across turns, parentProps
        // need to be re-set to reused instances in addition to item/key
        inst.__setProperty(this.as, this.collection.getItem(key), true);
        inst.__setProperty('__key__', key, true);
      } else {
        inst = this._generateInstance(idx, key);
      }
      var beforeRow = this._instances[idx + 1 ];
      var beforeNode = beforeRow && !beforeRow.isPlaceholder ? beforeRow._children[0] : this;
      var parentNode = Polymer.dom(this).parentNode;
      Polymer.dom(parentNode).insertBefore(inst.root, beforeNode);
      this._instances[idx] = inst;
      return inst;
    },

    _downgradeInstance: function(idx, key) {
      var inst = this._detachInstance(idx);
      if (inst) {
        this._pool.push(inst);
      }
      inst = {
        isPlaceholder: true,
        __key__: key
      };
      this._instances[idx] = inst;
      return inst;
    },

    // Implements extension point from Templatizer mixin
    _showHideChildren: function(hidden) {
      for (var i=0; i<this._instances.length; i++) {
        this._instances[i]._showHideChildren(hidden);
      }
    },

    // Called as a side effect of a template item change, responsible
    // for notifying items.<key-for-inst> change up to host
    _forwardInstanceProp: function(inst, prop, value) {
      if (prop == this.as) {
        var idx;
        if (this._sortFn || this._filterFn) {
          // Known slow lookup: when sorted/filtered, there is no way to
          // efficiently memoize the array index and keep it in sync with array
          // mutations, so we need to look the item up in the array
          // This can happen e.g. when array of strings is repeated into inputs
          idx = this.items.indexOf(this.collection.getItem(inst.__key__));
        } else {
          // When there is no sort/filter, the view index is the array index
          idx = inst[this.indexAs];
        }
        this.set('items.' + idx, value);
      }
    },

    // Implements extension point from Templatizer
    // Called as a side effect of a template instance path change, responsible
    // for notifying items.<key-for-inst>.<path> change up to host
    _forwardInstancePath: function(inst, path, value) {
      if (path.indexOf(this.as + '.') === 0) {
        this._notifyPath('items.' + inst.__key__ + '.' +
          path.slice(this.as.length + 1), value);
      }
    },

    // Implements extension point from Templatizer mixin
    // Called as side-effect of a host property change, responsible for
    // notifying parent path change on each inst
    _forwardParentProp: function(prop, value) {
      for (var i=0, i$=this._instances, il=i$.length; i<il; i++) {
        var inst = i$[i];
        if (!inst.isPlaceholder) {
          inst.__setProperty(prop, value, true);
        }
      }
    },

    // Implements extension point from Templatizer
    // Called as side-effect of a host path change, responsible for
    // notifying parent path change on each inst
    _forwardParentPath: function(path, value) {
      for (var i=0, i$=this._instances, il=i$.length; i<il; i++) {
        var inst = i$[i];
        if (!inst.isPlaceholder) {
          inst._notifyPath(path, value, true);
        }
      }
    },

    // Called as a side effect of a host items.<key>.<path> path change,
    // responsible for notifying item.<path> changes to inst for key
    _forwardItemPath: function(path, value) {
      if (this._keyToInstIdx) {
        var dot = path.indexOf('.');
        var key = path.substring(0, dot < 0 ? path.length : dot);
        var idx = this._keyToInstIdx[key];
        var inst = this._instances[idx];
        if (inst && !inst.isPlaceholder) {
          if (dot >= 0) {
            path = this.as + '.' + path.substring(dot+1);
            inst._notifyPath(path, value, true);
          } else {
            inst.__setProperty(this.as, value, true);
          }
        }
      }
    },

    /**
     * Returns the item associated with a given element stamped by
     * this `dom-repeat`.
     *
     * Note, to modify sub-properties of the item,
     * `modelForElement(el).set('item.<sub-prop>', value)`
     * should be used.
     *
     * @method itemForElement
     * @param {HTMLElement} el Element for which to return the item.
     * @return {any} Item associated with the element.
     */
    itemForElement: function(el) {
      var instance = this.modelForElement(el);
      return instance && instance[this.as];
    },

    /**
     * Returns the `Polymer.Collection` key associated with a given
     * element stamped by this `dom-repeat`.
     *
     * @method keyForElement
     * @param {HTMLElement} el Element for which to return the key.
     * @return {any} Key associated with the element.
     */
    keyForElement: function(el) {
      var instance = this.modelForElement(el);
      return instance && instance.__key__;
    },

    /**
     * Returns the inst index for a given element stamped by this `dom-repeat`.
     * If `sort` is provided, the index will reflect the sorted order (rather
     * than the original array order).
     *
     * @method indexForElement
     * @param {HTMLElement} el Element for which to return the index.
     * @return {any} Row index associated with the element (note this may
     *   not correspond to the array index if a user `sort` is applied).
     */
    indexForElement: function(el) {
      var instance = this.modelForElement(el);
      return instance && instance[this.indexAs];
    }

  });


</script>