Proposal for list diff algorithm

[livoras]

According to the for directive's diff algorithm, when vue diffs two arrays like:

oldFrags:  a, b, c ,d, e, f, g, h
newFrags:  b, c, d, e, f, g, h, a

it causes seven manipulations of DOM(the move function is called seven times), but the actual minimal amount is just two (remove a from the first place, and insert it to the last).

Vue's list diff algorithm is actually good at cases like inserting new items or moving items from back to front/middle. But cases that just simply moving a item from front to back/middle, it will cause a lot manipulations.

I didn't mean to make it minimal manipulations like levenshtein distance based algorithm does. But moving items from front to back/middle is quite common, so I think it's worth to optimalize.

Here is the pseudocode：

loop frags:
  if not a reused item
    if currentPrev !== targetPrev
      if removing the targetPrev makes currentPrev === elementAfterTargetPrev
        simply remove targetPrev // the removed element will be moved to the right place in future loop
      else
        move(frag, prevEl)
  else 
    simply insert it

It just needs one more if check.

[yyx990803]

Hmm, are you sure? Vue actually performs only 1 move call for the scenario you described.

[livoras]

@yyx990803 Code below is the scenario I described, you can have a try. I put a console.log in move, it's printed seven times.

import Vue from "vue"

var app = new Vue({
  el: "#content",
  data: {
    list: [
      {name: "a"},
      {name: "b"},
      {name: "c"},
      {name: "d"},
      {name: "e"},
      {name: "f"},
      {name: "g"},
      {name: "h"}
    ]
  }
})

setTimeout(function() {
  app.list = [
    {name: "b"},
    {name: "c"},
    {name: "d"},
    {name: "e"},
    {name: "f"},
    {name: "g"},
    {name: "h"},
    {name: "a"}
  ]
}, 2333)

  <div id="content">
    <div v-for="item in list" track-by="name">
      {{item.name}}
    </div>
  </div>

Here is the case perform 1 move:

import Vue from "vue"

var app = new Vue({
  el: "#content",
  data: {
    list: [
      {name: "a"},
      {name: "b"},
      {name: "c"},
      {name: "d"},
      {name: "e"},
      {name: "f"},
      {name: "g"},
      {name: "h"}
    ]
  }
})

setTimeout(function() {
  app.list = [
    {name: "h"},
    {name: "a"},
    {name: "b"},
    {name: "c"},
    {name: "d"},
    {name: "e"},
    {name: "f"},
    {name: "g"}
  ]
}, 2333)

[yyx990803]

@livoras you are replacing the entire list with fresh objects, therefore Vue is removing all old fragments and inserting all the new ones. In fact neither of your examples should call move. Both should call remove and insert 8 times.

If you add proper identity tracking with track-by="name", then you should see 1 move call in both cases.

[livoras]

@yyx990803 yes，I added track-by="name". I've shown it in my previous comment:

  <div id="content">
    <div v-for="item in list" track-by="name">
      {{item.name}}
    </div>
  </div>

[yyx990803]

I tested your exact code locally and got 1 move call. If it's making 7 calls for you, please provide a live demo...

[yyx990803]

Ah sorry, I was looking at the second snippet. Yes it is indeed making 7 calls.

[yyx990803]

@livoras thanks a lot for the suggestion! It actually optimizes all scenarios when only a single item is moved.

[livoras]

@yyx990803 Great job~! 👍 move now is only called once.

It actually optimizes scenarios that non-adjacent items are moved. :)