array-splice.html calcEditDistance can cause browser out-of-memory exception if compared lists are too large

[gopherkhan]

I first encountered this bug when using an iron-list. See here:
PolymerElements/iron-list#518

Essentially, calcEditDistances creates an MxN diff space for compared arrays. If two arrays are sufficiently large, the algo can cause an out-of-memory exception in the browser.

In my tests, two 30,000 element lists became a 900,000,000 entity grid, and consumes 1gig of heap before crashing the browser.

                              old, oldStart, oldEnd) {
    // "Deletion" columns
    let rowCount = oldEnd - oldStart + 1;
    let columnCount = currentEnd - currentStart + 1;
    let distances = new Array(rowCount);

    // "Addition" rows. Initialize null column.
    for (let i = 0; i < rowCount; i++) { // crashes reliably here
      distances[i] = new Array(columnCount);
      distances[i][0] = i;
    }

Description

Live Demo

JsBin is not loading for me at the moment, but you can start here:
https://jsbin.com/lolekifale/4/edit?html,console,output

Tweak the click listener from:
list.splice('items', 49999, 0, ...items);

to

list.items = items;

Open your debugger to catch the OOM-exception in calcEditDistances

Alternatively you could supply two lists directly to the calcEditDistances function,

var listA = [30k elements];
var listB = [30k elements];
calcEditDistances(listA, 0, listA.length,
                              listB, 0, listB.length); 

And that should exhibit the same behavior.

I'm guessing some threshold should be in place for too-long comparisons, or that the algo should be skipped or somehow batched if the comparison space is too large.

Steps to Reproduce

See above.

Expected Results

No error is thrown

Actual Results

the whole page crashes.

Browsers Affected

• Chrome
• Firefox
• Edge
• Safari 9
• Safari 8
• IE 11

Versions

• Polymer: vX.X.X
• webcomponents: vX.X.X

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[stale]

This issue has been automatically closed after being marked stale. If you're still facing this problem with the above solution, please comment and we'll reopen!