Heatmap faceting throws InvalidShapeException for a box that ends at the world's east or north edge in a non-geo (Web Mercator) context

PrefixTreeStrategy.calcFacets (spatial-extras) returns a heatmap: a grid of counts that covers a box at a given prefix-tree level. In a non-geo SpatialContext whose world bounds make the quad tree's computed cell edges inexact doubles (so a cell's width can come out one ulp off), such as Web Mercator in metres (+/-20037508.34 or +/-pi*6378137), a box whose max X or max Y equals the world's max edge can make it throw InvalidShapeException instead. calcRowsOrCols divides the distance from the corner cell to the box's end by the corner cell's width, which is one double below its nominal value, gets a result a hair above a whole number (14.000000000000002 for the example) and Math.ceil adds a column. That column lies past the world's edge; the half-cell snap cannot absorb it, the branch commented "wraps dateline (won't happen if !geo)" makes maxX negative, and the shape factory rejects the region. About 20-40% of edge boxes throw; boxes inside the world, the default geo context and integer or power-of-two bounds never did in any scan. The call fails before the index is read, so it returns nothing and leaves the index alone. Present since heatmaps were added in 5.1.0, through 10.6.0 and main; a small cap on the column and row counts fixes it.

1. Cell size from the corner cell. calcFacets finds the level-5 cell holding the box's corner (3,000,000, 0) (:113-121): x [2,504,688.5425, 3,757,032.8137499997]. cellWidth = cornerRect.getWidth() (:125) is 1252344.2712499998, one double below 40,075,016.68 / 32 = 1,252,344.27125.
2. One column too many. calcRowsOrCols (:341-361) computes range = requestRange + (requestMin - cellMin) = 17,037,508.34 + 495,311.4575 = 17,532,819.7975 (:346), exactly 14 cells to the east edge, then Math.ceil(range / cellRange) (:350): 14.000000000000002, so 15. The only cap is the whole-world count, Math.round(worldRange / cellRange) = 32 (:354-360, "possibly due to rounding/edge issue"), not the 14 cells left before the edge. In other cases the computed range is one ulp high instead; the effect is the same.
3. The snap misses a whole cell. heatMaxX = heatMinX + columns * cellWidth = 21,289,852.61 (:158), a full cell past the edge; the "numeric conditioning issue" snap only fires within half a cell (:159-160).
4. The dateline branch runs in a non-geo context. else if (heatMaxX > worldRect.getMaxX()) { // wraps dateline (won't happen if !geo) (:161-162) subtracts the world width: heatMaxX = -18,785,164.06875. For Y there is no wrap branch (:165-168), so heatMaxY stays at 21,289,852.61, outside the world.
5. The region is rejected. ctx.getShapeFactory().rect(heatMinX, heatMaxX, heatMinY, heatMaxY) (:170-172) throws InvalidShapeException ("maxX must be >= minX", or "Y values [...] not in boundary"), before any term is read, so even an empty reader reproduces it.

LFV-316 is a related rounding bug in QuadPrefixTree / PackedQuadPrefixTree cell edges for non-power-of-two bounds (same family as #9800). With its fix applied the minimal test still fails, and across 3,792 round-number calls the exceptions go from 698 (stock) to 943 (LFV-316's fix) to 0 (this fix).

• Who. PrefixTreeStrategy.calcFacets / HeatmapFacetCounter.calcFacets users with a non-geo context whose world bounds make the quad tree's cell edges inexact doubles: both Web Mercator extents (+/-pi*6378137 and the rounded +/-20037508.34), with QuadPrefixTree and PackedQuadPrefixTree. Not affected in any scan: the default geo context and bounds such as +/-180, +/-1000, +/-1024, +/-2^25, +/-2e7 or the zero-based ENVELOPE(0,700000,1300000,0) of #9800.
• An ordinary trigger. spatial4j rejects non-geo boxes outside the world, so a client whose map viewport reaches past the east or north edge has to shrink the box; a client that clamps it to the world sends a box ending exactly at the edge. Passing null (the whole world) works.
• How often. 777 of 1,989 random east-edge boxes throw for +/-pi*6378137 and 412 of 1,993 for +/-20037508.34 (levels 1-10); 144 of 416 round-number boxes at the east or north edge (levels 1-8); 1,396 of 5,056 edge boxes in a second scan, where all 5,056 boxes ending 1 m inside returned.
• What goes wrong. An undocumented unchecked exception instead of a heatmap, for that request only. In a 10,112-call probe every call that returned gave a region covering the box and inside the world (no silent wrong result), the index is not read or changed, later calls are unaffected, and assertions make no difference.
• Workaround. Inset the box's max X/Y slightly from the world's max edge (1 m worked in every scan that tried it).
• Likelihood. Plausible: a map client in such a setup hits it without doing anything unusual, but such setups seem rare and the searches found no earlier report. HeatmapFacetCounter is @lucene.experimental.

Same package as Lucene's TestHeatmapFacetCounter (the file carries the Apache license header). The seed only picks the test framework's settings, which the test does not use; 20 of 20 random-seed iterations fail the same way. The same test is the suggested regression test.

The follow-up's version-portable main() (four edge boxes and the 1-m-inside control) is the evidence for the older releases (section History); it is not part of the repro.

cp $REPRO/org/apache/lucene/spatial/prefix/TestHeatmapBoxAtWorldEastEdgeNonGeo.java \
   $LUCENE/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/
cd $LUCENE && ./gradlew :lucene:spatial-extras:test \
  --tests org.apache.lucene.spatial.prefix.TestHeatmapBoxAtWorldEastEdgeNonGeo \
  -Ptests.seed=DEADBEEF -Ptests.asserts=true
# also with -Ptests.asserts=false (same failure); the test uses no randomness

# gradle, main 645d4fe14a20, -Ptests.seed=DEADBEEF, -Ptests.asserts=true (identical with =false)
TestHeatmapBoxAtWorldEastEdgeNonGeo > testBoxEndingAtWorldEastEdge FAILED
    org.locationtech.spatial4j.exception.InvalidShapeException: maxX must be >= minX: 2504688.5425 to -1.878516406875E7
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:4427E2D0B808582C]:0)
        at app/spatial4j@0.8/org.locationtech.spatial4j.shape.impl.ShapeFactoryImpl.rect(ShapeFactoryImpl.java:121)
        at app//org.apache.lucene.spatial.prefix.HeatmapFacetCounter.calcFacets(HeatmapFacetCounter.java:172)
        at app//org.apache.lucene.spatial.prefix.PrefixTreeStrategy.calcFacets(PrefixTreeStrategy.java:227)
        at app//org.apache.lucene.spatial.prefix.TestHeatmapBoxAtWorldEastEdgeNonGeo.testBoxEndingAtWorldEastEdge(TestHeatmapBoxAtWorldEastEdgeNonGeo.java:41)

# standalone runner: the same failure on main (-ea, -da), 10.6.0 (-ea, -da), 10.5.2 (-ea) and 9.12.3 (-ea)
# side probe, same world and level: north-edge box -> InvalidShapeException: Y values [2504688.5425 to 2.128985261125E7] not in boundary ...
#                                   box ending 1 m inside the east edge -> 14 x 1, region covers the box
# with the fix: the test passes (assertions on and off); the edge box gets the same 14 x 1 heatmap

• The contract. HeatmapFacetCounter.java:86-90: "The actual heatmap area will usually be larger since the cells on the edge that overlap are returned. ... If null is given, the entire world is assumed." So the contract expects inputs that reach the world edge (null, the whole world, ends at both max edges), though it makes no explicit promise for every custom non-geo world. The javadoc names no exception: its only failure note, in @param maxCells, has been cut off at "If the cells exceed this count, an" (:92) since LUCENE-6650 (2015; it read "... an IllegalArgumentException is thrown."). The code throws its only deliberate exception, IllegalArgumentException, for too many cells (that note, :140-150) and for a too-large maxCells (:102-105); InvalidShapeException is a RuntimeException, not an IllegalArgumentException.
• The code states the assumption that breaks. :161 "wraps dateline (won't happen if !geo)"; the snaps at :159 and :166 ("numeric conditioning issue") and the cap at :354 ("possibly due to rounding/edge issue") show rounding at the edge was meant to be absorbed, but they cover only half a cell or the whole world.
• Tests. TestHeatmapFacetCounter.testQueryCircle (:94-99) uses geo=false with a [-90, 90] world, whose cell widths are exact; testRandom usually queries the world bounds (:192), but in a geo context. No test has a non-geo world with inexact cell widths.
• History. The code is unchanged since it was added (LUCENE-6191, 2015) apart from formatting and a rename; nothing restricts heatmaps to geo contexts or to boxes inside the edge.

The strongest case: the class is @lucene.experimental; heatmaps were designed and tested mostly for geo; in the LUCENE-6191 discussion (#7253) the author benchmarked a geo=false 360x360 world with the input "slightly inset so heatmap doesn't include a row just > 90 and just < 90"; and quad trees over non-power-of-two bounds are known to be numerically fragile (#9800).

Why it fails: the inset is an issue-comment workaround for an extra row inside the world, not a documented precondition, and gives no reason for an exception when the extra cell would lie outside the world; null means the whole world; the code itself says the wrap "won't happen if !geo"; the exception is not the IllegalArgumentException the code throws on purpose for bad requests; and #9800 was resolved as Fixed. The verifiers and the cross-model lenses rated the intended-behaviour case weak. Verdict: a defect.

One fix was validated in a scratch worktree of 645d4fe14a20 with gradle: the hunt's fix, with one line reflowed by google-java-format (whitespace only; the hunt's layout failed the format check). A tolerance before Math.ceil was considered but not run.

After calcRowsOrCols, for a non-geo context cap the column count at round((worldMaxX - heatMinX) / cellWidth), and cap the row count at round((worldMaxY - heatMinY) / cellHeight) (rows never wrap). Math.round absorbs the one-ulp error; Math.max(1, ...) keeps at least one cell. 1 file, +18/-7.

-    final int columns =
+    int columns =
         calcRowsOrCols(
             cellWidth, heatMinX, inputRect.getWidth(), inputRect.getMinX(), worldRect.getWidth());
+    if (!ctx.isGeo()) {
+      // FP rounding in calcRowsOrCols can add a column; there is none beyond the world's max edge
+      columns =
+          Math.max(
+              1, Math.min(columns, (int) Math.round((worldRect.getMaxX() - heatMinX) / cellWidth)));
+    }
     // (rows: the same cap, Math.round((worldRect.getMaxY() - heatMinY) / cellHeight), in geo too)

Trade-offs

• Scope. It only lowers a column or row count that would reach past the world's max edge. By code reading every such count ends in this exception today except one, which returns a valid result that the fix changes: when the extra column makes the count equal to the whole world's (a box starting inside column 1 and ending at the east edge), :155-157 moves the region to the world's min edge, so stock returns 2^level columns, the first of which the box does not reach. With the fix the region starts at the corner cell and has 2^level - 1 columns, as stock already returns at levels where rounding adds no column. Both contain the box, with no exception (executed by the fact check at levels 5 and 7, and 5, 7, 8 and 10, for the two Mercator extents). The PR should add a regression test for this case and state which result it intends.
• Geo X is left alone (crossing the dateline is legitimate there); rows have no wrap branch, so the row cap applies in geo too, where a row past the max edge would put maxY outside the world (code reading).
• Cost. One division and one compare per axis per call.
• A smaller formulation of the same cap (not run) passes worldMax - heatMin (the world width for geo X) as calcRowsOrCols's last argument, so its existing cap (:355) does the work.

What the checks validated

• Stock + test: fails, assertions on and off (gradle).
• + fix: the whole lucene/spatial-extras module passes with assertions on: 27 classes, 118 tests, 0 failures, 5 skipped (the new test 1/0, TestHeatmapFacetCounter 4/0).
• With assertions off: the same 27 classes, 118 tests, 0 failures.
• With the one line reflowed by google-java-format (the hunt's layout failed the format check), :lucene:spatial-extras:check -x test (google-java-format, ecjLint, forbiddenApis) passes, and the new test and TestHeatmapFacetCounter pass again.
• Earlier, on a9779ef3c193: every verifier's tests pass with it (finder 1/1, the independent reproduction 4/4, the intended-behaviour check 7/7, adjudication 4/4), the follow-up's history main() passes, and the edge-box scans drop to 0 exceptions.

Subtract a small relative epsilon from range / cellRange in calcRowsOrCols (:350).

Trade-offs

Needs an epsilon choice; a box that really extends a hair past a grid line would lose its last partial column (documents in that sliver not counted); leaves the non-geo wrap branch reachable for any other overshoot. Not recommended over the cap.

Callers inset the box's max X/Y slightly from the world's max edge (1 m worked for every control box in the scans), or pass null for the whole world.

Trade-offs

Useful until a fix ships; it does not fix the contract.

• Translation validation. A harness compared every cell of every calcFacets result on the real jar with a reference recomputed from the indexed terms, plus checks of the region's geometry, over small bounded input spaces. Extended to non-power-of-two (Web Mercator) non-geo worlds, it showed InvalidShapeException at HeatmapFacetCounter.calcFacets:172, which persisted with LFV-316's tree fix applied.
• Probes. Edge-touching and world-edge probes over ten world bounds isolated the trigger (a box ending at the world's max X or max Y edge) and measured the reach; 0 exceptions with the fix.
• Then a public-API JUnit, an independent reproducer, cross-model reviews (an independent reviewer from another model family, OpenAI GPT-5.6, executed mode), a devil's-advocate check and an adjudication. The method is semi-formal: targeted, bounded searches rather than a proof.