New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Nodes removed/reinserted when they are simply shifted #3442

Closed
yjbanov opened this Issue Aug 1, 2015 · 11 comments

Comments

Projects
None yet
8 participants
@yjbanov
Contributor

yjbanov commented Aug 1, 2015

There are reports that *ng-for removes and then reinserts nodes when their indices shift. We should make sure that we are not doing that.

@yjbanov

This comment has been minimized.

Show comment
Hide comment
@yjbanov

yjbanov Aug 1, 2015

Contributor

/cc @skybrian

Contributor

yjbanov commented Aug 1, 2015

/cc @skybrian

@skybrian

This comment has been minimized.

Show comment
Hide comment
@skybrian

skybrian Aug 1, 2015

Here is my (perhaps unrealistic) test code. I don't know that any real apps suffer from this.

https://gist.github.com/skybrian/faf783906317d2d0fb12

skybrian commented Aug 1, 2015

Here is my (perhaps unrealistic) test code. I don't know that any real apps suffer from this.

https://gist.github.com/skybrian/faf783906317d2d0fb12

@naomiblack naomiblack removed this from the alpha-36 milestone Aug 17, 2015

@mhevery

This comment has been minimized.

Show comment
Hide comment
@mhevery

mhevery Aug 20, 2015

Member

This may be intentional. Could we have a plunker which demonstrates it? How do you determine that something is reinserted?

Member

mhevery commented Aug 20, 2015

This may be intentional. Could we have a plunker which demonstrates it? How do you determine that something is reinserted?

@skybrian

This comment has been minimized.

Show comment
Hide comment
@skybrian

skybrian Aug 21, 2015

I don't know what a plunker is. I profiled the test code (above) in Chrome Dev Tools and found that most of the time spent was in functions in NgFor. Internal discussion:
https://groups.google.com/a/google.com/forum/#!topic/dart-angular/_YYS6liombQ

A good heuristic is to find common prefixes and suffixes starting from both the beginning and ends of the lists, and then run a more sophisticated algorithm on whatever is left in the middle. In the common case where there is only one change, this is optimal.

I looked at the diff algorithm a while ago, and it looked like it would handle common prefixes well but not common suffixes.

More ideas about cheap diff heuristics here:
https://neil.fraser.name/writing/diff/

skybrian commented Aug 21, 2015

I don't know what a plunker is. I profiled the test code (above) in Chrome Dev Tools and found that most of the time spent was in functions in NgFor. Internal discussion:
https://groups.google.com/a/google.com/forum/#!topic/dart-angular/_YYS6liombQ

A good heuristic is to find common prefixes and suffixes starting from both the beginning and ends of the lists, and then run a more sophisticated algorithm on whatever is left in the middle. In the common case where there is only one change, this is optimal.

I looked at the diff algorithm a while ago, and it looked like it would handle common prefixes well but not common suffixes.

More ideas about cheap diff heuristics here:
https://neil.fraser.name/writing/diff/

@yjbanov

This comment has been minimized.

Show comment
Hide comment
@yjbanov

yjbanov Aug 21, 2015

Contributor

Longest increasing subsequence (LIS) would be able to identify minimal moves in N*log(N). It's not too hard to implement, but we also need to find the shortest list length past which LIS is faster than a simpler approach. Certainly for lists of 0-2 we should just use ad hoc functions instead of generic list differ.

@mhevery why do you need plunker? @skybrian provided a repro sample in a github gist.

Contributor

yjbanov commented Aug 21, 2015

Longest increasing subsequence (LIS) would be able to identify minimal moves in N*log(N). It's not too hard to implement, but we also need to find the shortest list length past which LIS is faster than a simpler approach. Certainly for lists of 0-2 we should just use ad hoc functions instead of generic list differ.

@mhevery why do you need plunker? @skybrian provided a repro sample in a github gist.

@vicb

This comment has been minimized.

Show comment
Hide comment
@vicb

vicb Aug 21, 2015

Member

The current algorithm outputs added, removed & moved elements (not sure about how it would handle common suffix vs common prefix).

It's probably more how the directive deals with changes that is to blame here ?
1 - remove the view for removed & moved nodes (removes DOM nodes),
2 - add views for inserted nodes.

At this point we have the final number of views but their context might be wrong.

3 - Loop on all the views to set their context (that the index + the element).

First step would be to investigate if the diff algo or the directive code is to blame.

/cc @rkirov

Member

vicb commented Aug 21, 2015

The current algorithm outputs added, removed & moved elements (not sure about how it would handle common suffix vs common prefix).

It's probably more how the directive deals with changes that is to blame here ?
1 - remove the view for removed & moved nodes (removes DOM nodes),
2 - add views for inserted nodes.

At this point we have the final number of views but their context might be wrong.

3 - Loop on all the views to set their context (that the index + the element).

First step would be to investigate if the diff algo or the directive code is to blame.

/cc @rkirov

@bertrandg

This comment has been minimized.

Show comment
Hide comment
@bertrandg

bertrandg Oct 27, 2015

I have a plunker showing this behavior (with alpha 44) here:
http://plnkr.co/edit/HLbOaD?p=preview

  1. Remove the first element
  2. Add a new element
  3. See that order in the view is not right and not identical as inside the console log
  4. Click 2 times on "SHOW/HIDE" button
  5. See that order in the view is now correct

Like someone said on stackoverflow, this occurs only with syntax:

<template ng-for #m [ng-for-of]="group.children" #i="index">...</template>

Not with this syntax:

<div *ng-for="#m of group.children; #i=index">...</div>

(posted on stackoverflow first)

bertrandg commented Oct 27, 2015

I have a plunker showing this behavior (with alpha 44) here:
http://plnkr.co/edit/HLbOaD?p=preview

  1. Remove the first element
  2. Add a new element
  3. See that order in the view is not right and not identical as inside the console log
  4. Click 2 times on "SHOW/HIDE" button
  5. See that order in the view is now correct

Like someone said on stackoverflow, this occurs only with syntax:

<template ng-for #m [ng-for-of]="group.children" #i="index">...</template>

Not with this syntax:

<div *ng-for="#m of group.children; #i=index">...</div>

(posted on stackoverflow first)

@yjbanov

This comment has been minimized.

Show comment
Hide comment
@yjbanov

yjbanov Nov 12, 2015

Contributor

Bumping priority on this. I saw this briefly while debugging an app. The wrong insertion order was triggered by non-idempotent expression bound to ng-for. Making it idempotent fixed the issue, however, it shouldn't have. Even with non-idempotent expressions we should still render the list correctly.

/cc @naomiblack for coordination

Contributor

yjbanov commented Nov 12, 2015

Bumping priority on this. I saw this briefly while debugging an app. The wrong insertion order was triggered by non-idempotent expression bound to ng-for. Making it idempotent fixed the issue, however, it shouldn't have. Even with non-idempotent expressions we should still render the list correctly.

/cc @naomiblack for coordination

@yjbanov yjbanov added P1: urgent and removed P2: required labels Nov 12, 2015

@rkirov

This comment has been minimized.

Show comment
Hide comment
@rkirov

rkirov Nov 14, 2015

Contributor

There are two things conflated in this issue:

  • when objects in the ng-for array are moved, what should be the corresponding mutations to the DOM. This is a question of efficiency. #1377 captures this issue it a lot better, so I suggest we continue the discussion there.
  • reports for actual bugs in the ng-for implementation by @bertrandg but the repro case is quite involved. @bertrandg can you simplify it a bit, I think the minimal repro involves an ng-for wrapping ng-if. It is very off that with the *ng-for syntax the bug disappears.

btw, I ported @skybrian's demo to plunker -http://plnkr.co/edit/h5Q5EtxB0aqNnGVg6AVo?p=preview for future reference.

Contributor

rkirov commented Nov 14, 2015

There are two things conflated in this issue:

  • when objects in the ng-for array are moved, what should be the corresponding mutations to the DOM. This is a question of efficiency. #1377 captures this issue it a lot better, so I suggest we continue the discussion there.
  • reports for actual bugs in the ng-for implementation by @bertrandg but the repro case is quite involved. @bertrandg can you simplify it a bit, I think the minimal repro involves an ng-for wrapping ng-if. It is very off that with the *ng-for syntax the bug disappears.

btw, I ported @skybrian's demo to plunker -http://plnkr.co/edit/h5Q5EtxB0aqNnGVg6AVo?p=preview for future reference.

@bertrandg

This comment has been minimized.

Show comment
Hide comment
@bertrandg

bertrandg Nov 16, 2015

@rkirov Here is a simpler demo:
http://plnkr.co/edit/AV412r?p=preview

It happens only with NgIf inside the NgFor template tag syntax.

bertrandg commented Nov 16, 2015

@rkirov Here is a simpler demo:
http://plnkr.co/edit/AV412r?p=preview

It happens only with NgIf inside the NgFor template tag syntax.

@tbosch

This comment has been minimized.

Show comment
Hide comment
@tbosch

tbosch Feb 11, 2016

Member

The bug of @bertrandg is a dupe of #6304 and is solved in #6878.
And as the performance problems is tracked in #1377 I am closing this issue.

Member

tbosch commented Feb 11, 2016

The bug of @bertrandg is a dupe of #6304 and is solved in #6878.
And as the performance problems is tracked in #1377 I am closing this issue.

@tbosch tbosch closed this Feb 11, 2016

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment