[BUG]: findEmpties throws "iterated with no new neighbors" for large NaN regions in contour (double-precision underflow)

Commencez dans src/traces/heatmap/find_empties.js, en vous concentrant sur le calcul du poids du flood-fill et sur la garde en l’absence de voisin décrite dans l’issue. Reproduisez l’échec avec la bande 5 x 251 fournie, puis ajoutez une couverture à côté des cas existants dans test/jasmine/tests/heatmap_test.js. Le travail est terminé lorsque les grandes régions vides connectées se terminent sans lever d’exception, tandis que le comportement d’interpolation existant reste couvert.

Description

findEmpties() (used by contour, heatmap with connectgaps, surface with connectgaps, and
contourcarpet) throws

findEmpties iterated with no new neighbors

for large empty (NaN) regions, even though every empty cell is connected to real data. The cause
is a double-precision underflow of the internal "fractional neighbour count" weight, which the code
then misreads as "this cell has no neighbours".

Inside the flood-fill loop the weight is recomputed once per layer as

neighborCount = ((neighborHash[[i - 1, j]] || blank)[2] +
    (neighborHash[[i + 1, j]] || blank)[2] +
    (neighborHash[[i, j - 1]] || blank)[2] +
    (neighborHash[[i, j + 1]] || blank)[2]) / 20;   // src/traces/heatmap/find_empties.js, L70-L73

if(neighborCount) {                                  // L75: 0 is treated as "no neighbour"
    newNeighborHash[thisPt] = [i, j, neighborCount];
    noNeighborList.splice(p, 1);
    foundNewNeighbors = true;
}

so the weight decays geometrically. With n already-filled neighbours per layer, after k layers
w ≈ w0 * (n / 20)^k. Once w falls below Number.MIN_VALUE (≈ 4.94e-324, the smallest positive
double) it becomes exactly 0, the if(neighborCount) guard fails, no cell is marked as filled in
that round, foundNewNeighbors stays false, and the function throws.

The number of layers until underflow is 324 / log10(20 / n):

already-filled neighbours per layer	layers until the weight becomes 0	typical geometry
1	249	a 1-cell-wide propagation channel
2	324	diagonal / corner of a 2-D front
4	463	interior of a 2-D island

Numeric evidence: 20 ** -248 === 1.9763e-323 (still representable) but 20 ** -249 === 0
(exactly zero, verified in Node/Chrome).

So the real limit is the depth of contiguous empty cells along the propagation direction
(roughly 250-330), not the amount of missing data and not connectivity. Note also that a lot of
missing data is fine as long as it is shallow:

• a 5 x 251 grid whose column 0 is data and columns 1-250 are NaN (only 1250 empty cells) throws;
• a 200 x 200 grid of data with a 100 x 100 NaN hole (10000 empty cells) renders fine.

Screenshots/Video

Console output for the reproducer below (plotly.js 3.7.0, unminified):

Uncaught findEmpties iterated with no new neighbors

Note that the exception is thrown synchronously out of Plotly.newPlot(), so it is not
delivered as a promise rejection and cannot be handled with .catch().

Steps to reproduce

Minimal, no browser required (the function body is copied verbatim from
src/traces/heatmap/find_empties.js; run with node repro.js):

// NOTE: plotly passes z through clean2dArray, whose cleanZvalue() maps any non-numeric
// value to undefined (`if(!isNumeric(v)) return undefined;`), so NaN reaches findEmpties
// as undefined - that is what "empty" means here.
var maxRowLength = function(z) { var m = 0; for (var k = 0; k < z.length; k++) if (z[k].length > m) m = z[k].length; return m; };

function findEmpties(z) { /* exact copy of src/traces/heatmap/find_empties.js, see file above */ }

// 5 rows, column 0 is data, columns 1..250 are empty  -> THROWS
function strip(rows, nanCount) {
    var z = [], r, i, j;
    for(i = 0; i < rows; i++) { r = [1]; for(j = 0; j < nanCount; j++) r.push(undefined); z.push(r); }
    return z;
}

findEmpties(strip(5, 250));  // Uncaught findEmpties iterated with no new neighbors
findEmpties(strip(5, 249));  // fine - one column less

End-to-end in the browser / CodePen (also verified through Plotly.newPlot with jsdom against the
real 3.7.0 bundle - the same exception is thrown synchronously):

<script src="https://cdn.plot.ly/plotly-3.7.0.js"></script>
<div id="plot" style="width:900px;height:400px"></div>
<script>
var z = [], i, j, row;
for(i = 0; i < 5; i++) { row = [1]; for(j = 0; j < 250; j++) row.push(NaN); z.push(row); }

// throws synchronously; try/catch is required, .catch() on the promise is not enough
try {
    Plotly.newPlot('plot', [{ z: z, type: 'contour' }], {});
} catch(e) {
    console.log(e);   // findEmpties iterated with no new neighbors
}
</script>

CodePen: https://codepen.io/.../pen/... (see the attached example; button "Case 1" fails in < 1 s,
"Case 2" - a 325 x 325 grid whose only data are the centre 2 x 2 cells - fails after ~1 minute).

Suggested fix

The weight is only an ordering heuristic (see the file's own comment: "this is to give us an order
of points to evaluate for interpolation"), so it must not affect control flow. Testing the sum
instead of the quotient, and clamping the underflowed quotient to Number.MIN_VALUE, is enough:

--- a/src/traces/heatmap/find_empties.js
+++ b/src/traces/heatmap/find_empties.js
@@
-    var neighborCount;
+    var neighborCount;
+    var neighborSum;
@@
-            neighborCount = ((neighborHash[[i - 1, j]] || blank)[2] +
+            neighborSum = (neighborHash[[i - 1, j]] || blank)[2] +
                 (neighborHash[[i + 1, j]] || blank)[2] +
                 (neighborHash[[i, j - 1]] || blank)[2] +
-                (neighborHash[[i, j + 1]] || blank)[2]) / 20;
+                (neighborHash[[i, j + 1]] || blank)[2];
+
+            neighborCount = neighborSum / 20;
 
-            if(neighborCount) {
+            if(neighborSum) {
+                // neighborSum / 20 can underflow to 0 (once neighborSum <= ~1e-323),
+                // but this cell does have neighbours: keep a strictly positive weight
+                if(!neighborCount) neighborCount = Number.MIN_VALUE;
                 newNeighborHash[thisPt] = [i, j, neighborCount];
                 noNeighborList.splice(p, 1);
                 foundNewNeighbors = true;

Measured with this patch applied to the shipping implementation:

input	unpatched	patched
5 x 251 strip (1250 empty)	throws	fills all 1250, ~0.6 s
5 x 250 strip (1245 empty)	fills 1245	fills 1245 (unchanged)
324 x 324 centre island	fills 104972	fills 104972 (unchanged)
325 x 325 centre island	throws after ~60 s	fills all 105621
512 x 512 centre island	throws after ~134 s	fills all 262140
200 x 200 with a 60 x 60 hole	fills 3600	fills 3600 (unchanged)

The returned list is still sorted by descending weight (verified monotonic non-increasing), and in
the 325 x 325 case only a single cell ends up clamped to Number.MIN_VALUE, so the interpolation
order is not distorted. A regression test could be added next to the existing heatmap tests in
test/jasmine/tests/heatmap_test.js.

Two further suggestions, happy to open PRs for either:

1. Replace the weighted flood fill with a plain BFS over layer indices (w = 1 / (1 + layer)).
   This removes the underflow at the source and fixes the complexity: the current loop rescans
   every remaining empty cell on every round and uses string-keyed hash lookups plus
   Array#splice in the middle of a large array, so an input that fails can take minutes of
   wasted work first (measured ~60 s for a 325 x 325 grid and ~134 s for 512 x 512 on a desktop CPU).
2. throw 'findEmpties iterated with no new neighbors' throws a bare string, so it cannot be
   identified with instanceof Error. If a hard failure is really the intent (e.g. all-NaN z),
   please throw an Error with a message that points at the missing data instead.

Notes

• Affected traces: contour (findEmpties is called unconditionally), heatmap with
  connectgaps: true, surface (3D) with connectgaps: true, and contourcarpet.
• There is no configuration that avoids this; zsmooth, connectgaps: false etc. only change
  whether the code path is reached, not whether it can throw.
• Every empty cell in all reproducers above is 4-connected to real data, so the error message
  ("iterated with no new neighbors") is misleading - it suggests disconnected data where there is none.
• findEmpties only sees undefined cells because clean2dArray converts NaN to undefined
  first; this is why a repro that calls the function directly with a Float64Array filled with
  NaN silently returns [].

Examples

CodePen Link:

https://codepen.io/Czhaowu/pen/myWBYEW