PackedQuadPrefixTree in a geo context stores a point at longitude +180 in the -180 edge cell but looks it up in the +180 edge cell, so a query for that same point misses the document

With PackedQuadPrefixTree in a geo SpatialContext, a document indexed at longitude exactly +180 is not found by a query for that same point. For one document at Pt(180, 10) and an 8-level tree, RPT Intersects (with pointsOnly=false), RPT Contains and CompositeSpatialStrategy Intersects return 0 hits instead of 1; the same point at -180, QuadPrefixTree and a rectangle query that touches +180 find it. Indexing and querying use two different point-to-cell rules. PrefixTreeIterator stores the point in the first cell in Z order whose rectangle relate()s to it, and a geo rectangle treats +180 as -180, so the point lands in the cells at the -180 edge. A point query descends with getCell, a mid-point walk that LUCENE-8755 introduced in 8.3.0, and that walk sends x = +180 to the cells at the +180 edge. Every release from 8.3.0 to 10.5.2 and main is affected, with no error and the index intact; 8.2.0 passes. A small fix in getCell (one if: treat +180 as -180 in a geo context) makes the query look where the document is, needs no reindexing, and passes the repro and the module's tests.

• Prefix tree (grid): PackedQuadPrefixTree splits the world into 4 cells per level (a quad tree) and stores each cell as a term. RecursivePrefixTreeStrategy (RPT) indexes a shape as the terms of the cells it touches; a point is stored as one path of cells, from the top level down to a leaf at the tree's maximum level.
• Z order: the four children of a cell are visited as NW, NE, SW, SE.
• Geo wrap: in SpatialContext.GEO, longitude +180 and -180 are the same meridian, and a spatial4j rectangle that starts at -180 relates to x = +180 as if it were -180.

PackedQuadPrefixTree.getTreeCellIterator (PackedQuadPrefixTree.java:183-190 at a9779ef3c193) returns a PrefixTreeIterator. Its hasNext (:468-503) walks the children in Z order, keeps the first whose rectangle relate()s to the shape (:476), and for a Point stops at the first leaf (:489-491). On main, [-180,0] x [0,90] relate Pt(180,10) is CONTAINS, and so is [0,180] x [0,90]. NW comes first, so the point goes west, and in every later level the westmost child again relates first.

A point query descends with LegacyCell.getNextLevelCells(Point) (LegacyCell.java:134-143), which calls getSubCell(point), here PackedQuadPrefixTree.getCell(p, level + 1) (PackedQuadPrefixTree.java:342-345). getCell (:90-128) compares the point with each cell's mid-point using QuadPrefixTree.battenberg (QuadPrefixTree.java:223-235): xmid >= xp goes west, otherwise east. 180 is greater than every mid-point, so the walk goes east at every level.

Tree depth (executed at depths 1 to 8 for every strategy and operation; the scope below is at 8 and 26 levels). Contains misses at every depth, a 1-level tree included: ContainsPrefixTreeQuery starts at the world cell and descends with getNextLevelCells(point) (ContainsPrefixTreeQuery.java:88-89, 120), which picks the east level-1 cell. RPT Intersects (pointsOnly=false) finds the document on a 1-level tree, because the visiting queries clamp the scan level to maxLevels - 1 (AbstractVisitingPrefixTreeQuery.java:61) and scan the world cell with relate(), and misses from 2 levels on (the independent reproducer: 30 of 36 misses over levels 1, 2, 5, 12, 20, 29 and six latitudes, the north pole included; the south pole misses too in this doc's probes). The optimized composite Intersects, which uses RPT's default scan level maxLevels - 4 (RecursivePrefixTreeStrategy.java:62-63), finds the document up to 4 levels and misses from 5 on.

• RPT Intersects with a point (RecursivePrefixTreeStrategy.java:185-188, 216-237): with pointsOnly=true it builds a TermQuery from the index-side iterator and finds the document; with pointsOnly=false it builds an IntersectsPrefixTreeQuery, which descends with getNextLevelCells, and misses.
• RPT Contains (ContainsPrefixTreeQuery.java:106-142) descends with getNextLevelCells: misses with either pointsOnly value. RPT IsWithin finds the document.
• CompositeSpatialStrategy optimized Intersects, the default, builds IntersectsRPTVerifyQuery (CompositeSpatialStrategy.java:122-134), a visiting descent: misses with either value, as does composite Contains. Composite IsWithin, Equals, Overlaps and non-optimized Intersects take their candidates from RPT Intersects, so they miss only when the composite's RPT has pointsOnly=false.

QuadPrefixTree got the same mid-point getCell in the same commit, but it also indexes points with getCell (LegacyPrefixTree.java:62-83): one rule on both sides. Inside the world both rules break ties the same way (west on an x tie, north on a y tie) and the geo bounds are exact in binary, so only the wrap at +180 separates them. An SMT check (Z3, exact rationals) found the rules agree in every cell without the wrap and, on the level-1 split of the geo world, differ only at x = +180. Executed controls: -180, Math.nextDown(180), 179.9, 0 and 90 are found.

• Who. Applications that index points with RecursivePrefixTreeStrategy, or CompositeSpatialStrategy over it, on PackedQuadPrefixTree with a geo SpatialContext, and search for a point exactly at longitude +180.
• Exactly which queries miss (independent reproducer and this doc's probes, 8 and 26 levels; for smaller trees see the depth note in "What"): RPT Intersects with pointsOnly=false; RPT Contains with either pointsOnly value; the default (optimized) composite Intersects and composite Contains with either value; composite IsWithin, Equals, Overlaps and non-optimized Intersects only when the composite's RPT has pointsOnly=false.
• Not affected: RPT Intersects with pointsOnly=true, RPT IsWithin, TermQueryPrefixTreeStrategy, x = -180, Math.nextDown(180), QuadPrefixTree, geohash. Rectangle and circle queries showed no packed-quad-specific misses in the finder's lattice sweep; its exact-boundary misses (such as a line exactly on a circle's rim) occur in the same numbers with QuadPrefixTree.
• Opt-in, experimental. SpatialPrefixTreeFactory picks geohash for a geo context unless prefixTree names another tree (quad, packedQuad, s2, or a factory class name) (SpatialPrefixTreeFactory.java:45-66); the tree, RPT, ContainsPrefixTreeQuery and the composite strategy are @lucene.experimental. Otherwise default IndexWriterConfig, codec and searcher, any index size. A tree built by the factory from WKT input (26 levels, Intersects(POINT(180 10)) parsed by SpatialArgsParser) misses too, also with normWrapLongitude=true.
• Silent. No exception, no assertion, and the index is intact; the same with assertions off.
• Measured scope. This doc's side-effect probe: points at x = +/-180 for six latitudes, rectangles and circles touching or crossing the antimeridian, queried with points at +/-180 and two rectangles, three operations, RPT and composite, 8 and 26 levels. Of 552 combinations that should match, stock main misses 60, every one a document at exactly +180 queried with the same point. Its queries are points and rectangles (no circles), and with pointsOnly=true it ran Intersects on point documents only; a second probe covers Contains and IsWithin with pointsOnly=true (see the workaround).
• Downstream (code reading only, not executed): Solr exposes the tree as prefixTree="packedQuad"; two downstream search engines map their legacy geo_shape quadtree tree to it in a geo context with RPT pointsOnly=false by default. Whether they rewrite +180 first was not checked.
• How likely. Rare: it needs a document exactly on +180 and a point query at exactly that spot; no report of it was found since 8.3.0 (2019). Registry likelihood "rare", priority low.
• Workaround today: write longitude +180 as -180 on both sides, before indexing and before querying. On stock main a document at -180 queried with the same point is found in all 216 combinations tried: RPT with either pointsOnly value and the composite strategy (optimized and general, either value), each with Intersects, Contains and IsWithin, at six latitudes and 8 and 26 levels (the same set at +180: 144 misses).

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<1> but was:<0>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:647)
       org.junit.Assert.assertEquals(Assert.java:633)
       org.apache.lucene.spatial.prefix.TestPackedQuadPlus180Point.testIntersectsSamePointAtPlus180(TestPackedQuadPlus180Point.java:49)

• Contract. SpatialArgs#getDistErrPct / #getDistErr: the error "effectively inflates the size of the shape but should not shrink it" (SpatialArgs.java:118-119, 134-135). PrefixTreeStrategy#setDistErrPct: "Points don't use this as they are always indexed at the configured maximum precision" (PrefixTreeStrategy.java:102-103), and for a Point query the distance error is 0 (SpatialArgs.java:60-61), so the query runs at the full depth (QuadPrefixTree.java:117-119). SpatialOperation.Intersects.evaluate(p, p) and Contains.evaluate(p, p) are true (the repro asserts it). CompositeSpatialStrategy: "RPT acts as an index to the precision available in SDV" (CompositeSpatialStrategy.java:38).
• Legal input. Pt(180, y) is inside the SpatialContext.GEO world bounds. spatial4j keeps x = 180: WKT POINT(180 10) gives x = 180, and with normWrapLongitude=true normX(180) and even normX(540) are 180. No Lucene javadoc asks callers to rewrite +180 as -180 (spatial4j's javadoc was not checked).
• Stated intent. In the review of apache/lucene-solr#824 (the PR behind LUCENE-8755), dsmiley, who then committed the change, asked to keep the old tokenization available because otherwise "some use-cases with existing indexes may break, like exact point lookup of itself should round-trip". Upstream testPackedQuadPointsOnlyBug indexes one point on a packed-quad tree and expects 1 hit for Intersects with that same point (non-geo world, one level, pointsOnly=true, the TermQuery path this bug does not break; TestRandomSpatialOpFuzzyPrefixTree.java:143-152); the randomized checks fail with "Should have matched" when an indexed shape is missed (:416).
• Precedent. In 2017 a packed-quad "index a point, search by the same point" failure with a different cause was fixed as a bug (LUCENE-7845, fixed by LUCENE-7859, 38741ece587).
• The rules used to agree. Before 8.3.0 getCell used the same "first relating cell in Z order" search as the iterator. LUCENE-8755 replaced it with the mid-point walk to fix an exception at high-precision cell edges in a non-geo world, and left the iterator unchanged; neither the issue nor the PR mentions the dateline or longitude 180.
• Why the tests missed it. The randomized packed-quad tests run in a non-geo [0, 256] x [-128, 128] world (TestRandomSpatialOpFuzzyPrefixTree.java:97-112, factory.geo = false); the only geo packed-quad test, TestDistanceStrategy (PackedQuadPrefixTree(ctx, 25) with SpatialContext.GEO, TestDistanceStrategy.java:43, 55), never uses longitude +180.

The strongest case for "works as designed": +180 and -180 are the same meridian and spatial4j's rectangle relate() deliberately treats them as one, so storing the point at the -180 edge is defensible; an application could normalize to -180; and the classes are @lucene.experimental, with approximate filtering.

Why it fails: no Lucene documentation states a normalization requirement, and spatial4j's own normalization keeps +180; the query uses the very same Point that was indexed, so the library disagrees with itself, not with the caller; a point query has zero distance error, so no documented approximation explains a miss; the change's committer named exact point round trip as something that must keep working; and the same tree finds -180 while QuadPrefixTree finds +180. @lucene.experimental lowers the severity, not the fact that a document cannot find itself. The intended-behaviour devil's advocate found no documented, accepted or misuse argument, and the intended-lens reviewer from another model family (OpenAI GPT-5.6) rated the "intended" argument weak.

One fix was applied in a scratch worktree at a9779ef3c193 and run through gradle (seed DEADBEEF) and through classpath probes; the alternatives were not run.

At the start of PackedQuadPrefixTree.getCell, map x = +180 to -180 when ctx.isGeo(). Point queries then descend into the -180 edge cells, where PrefixTreeIterator stored the point. The finder wrote this fix; the independent reproducer, the cross-model reviewers and the adjudication ran it.

--- a/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/PackedQuadPrefixTree.java
+++ b/lucene/spatial-extras/src/java/org/apache/lucene/spatial/prefix/tree/PackedQuadPrefixTree.java
@@ -93,6 +93,11 @@ public class PackedQuadPrefixTree extends QuadPrefixTree {
     double currentYmid = ymid;
     double xp = p.getX();
     double yp = p.getY();
+    if (ctx.isGeo() && xp == 180) {
+      // Geo rectangles treat longitude +180 as -180: PrefixTreeIterator (used to index points) puts
+      // such a point in the cell at the -180 edge, so look it up there too.
+      xp = -180;
+    }
     long term = 0L;

Trade-offs

• No reindexing: stored terms do not change, so existing indexes are found again at once.
• Same answers as the existing TermQuery shortcut. With pointsOnly=true, RPT Intersects already builds its term from the index-side iterator, so on stock main a +180 query matches both a +180 and a -180 document. After the fix RPT with pointsOnly=false gives the same answers: hits for (doc x, query x) = (+,+), (+,-), (-,+), (-,-) go from 0, 1, 0, 1 to 1, 1, 1, 1. A -180 document returned for a +180 query is an RPT candidate: RPT is documented as "a fast approximate spatial search filter" (PrefixTreeStrategy.java:39-40), and its pointsOnly TermQuery path already returns it today; the composite strategy checks the exact geometry and returns only exact matches (0 for mixed signs, before and after).
• A public method changes its answer at one coordinate: getCell(Point, int) is public; in a geo context it now returns the -180 edge cell for x = +180. Its callers inside spatial-extras are PackedQuadCell.getSubCell and LegacyPrefixTree.getDistanceForLevel (world centre, x = 0, unaffected). The survey covers Lucene's spatial-extras only: code outside Lucene that calls the public getCell and relies on the east cell for +180 would get the west cell.
• A special case for one meridian, matching what the indexer already does; only the geo wrap can make the two rules disagree. Cost: one comparison per call.
• A design choice for maintainers: spatial4j's geo rectangles treat +180 and -180 as one meridian, while exact point relations treat Pt(180, 10) and Pt(-180, 10) as different points. Maintainers may prefer a wider policy (normalize point longitudes in one place, or let the index follow getCell); this fix is the smallest change that keeps existing indexes working, not the only defensible design.
• Same method as another hunt fix: LFV-316 also changes getCell for a different cause (floating-point mid-point drift with non-power-of-two non-geo bounds); with its fix applied this bug still reproduces (3 of 6), so offer the two together or in sequence.

What the checks validated

• Stock (scratch worktree, gradle, seed DEADBEEF): the repro fails 3 of 6 with assertions on and off; the 8 closest suites (TestRandomSpatialOpFuzzyPrefixTree, TestDistanceStrategy, TestCompositeStrategy, TestSpatialPrefixTree, TestHeatmapFacetCounter, TestTermQueryPrefixGridStrategy, TestPortedSolr3, TestQueryEqualsHashCode) pass, 35 tests.
• With the fix: the repro passes 6 of 6 with assertions on and off; the 8 closest suites pass, 35 tests, 0 failures; the whole spatial-extras test suite with the repro in place passes, 123 tests, 5 skipped, 0 failures; TestRandomSpatialOpFuzzyPrefixTree with 20 iterations passes, 180 tests; ecjLintMain, ecjLintTest and checkGoogleJavaFormat of the module pass.
• Around the antimeridian (classpath probe, main jars with the fixed class shadowed): of 552 combinations that should match (points at +/-180 for six latitudes, rectangles and circles touching or crossing +/-180, the whole world; point and rectangle queries; Intersects, Contains, IsWithin; RPT and composite; 8 and 26 levels), stock misses 60 and the fix 0. No rectangle or circle document is missed before or after. Not covered: circle queries, and the heatmap and facet code at +180 (the module's heatmap and facet tests pass with the fix).
• Every strategy, operation and depth (resolution probe, main jars with the fixed class shadowed): doc = query at x = +/-180 for RPT (pointsOnly false and true) and the composite strategy (optimized and general, either value), Intersects, Contains and IsWithin, six latitudes, 8 and 26 levels: 432 of 432 found (stock: 144 misses, all at +180); depths 1 to 8 at (180, 10): every combination found.
• Cells: with the fix the looked-up leaf equals the indexed leaf for (180, 10) and (-180, 10) at 1, 2, 3 and 8 levels.
• Earlier hunt runs: the finder's repro passes 6 of 6 with the fix shadowed (seeds DEADBEEF, 5EEDF00D, A0D17004), the independent reproducer's 10 tests pass 10 of 10, the cross-model reviewers' own tests pass, and a clean worktree ran the whole module with the repro: 123 tests, 3 failures stock, 0 with the fix.

Make PrefixTreeIterator store a Point along the mid-point path (or pick the east cell for +180), so both sides use one rule, as QuadPrefixTree does.

Trade-offs

One rule everywhere, but existing indexes keep the -180 cells and must be reindexed; until then the pointsOnly TermQuery shortcut, which builds its term with the same iterator, would start missing the old documents too. It also changes the stored terms of new documents. Not run.

In getCell, use the old buildNotRobustly search (still in the class) when ctx.isGeo() and x = +180.

Trade-offs

Same answers as the recommended fix by construction (it is the indexer's rule), more code. Not run.

Rewrite longitude +180 as -180 before indexing and before querying. On stock main a document at -180 queried at -180 is found in all 216 combinations tried (RPT with either pointsOnly value, the composite strategy optimized and general with either value; Intersects, Contains, IsWithin; six latitudes; 8 and 26 levels).

Trade-offs

Querying at -180 alone finds a +180 document with RPT, but not with the composite strategy, whose exact check treats Pt(180, 10) and Pt(-180, 10) as different points; existing +180 documents need reindexing for the composite.

Method: bounded differential check of the stock main jars against exact geometry (semi-formal tier), in a hunt unit on spatial-extras composite and prefix-tree queries.

• A harness indexed a lattice of points, rectangles and circles in SpatialContext.GEO (including longitude +/-180 and the poles) and compared CompositeSpatialStrategy (optimized and general path), RecursivePrefixTreeStrategy and TermQueryPrefixTreeStrategy with SpatialOperation.evaluate on the stored shapes, over geohash, quad and packed-quad trees, levels, distErrPct, prune and prefixGridScanLevel settings.
• Both quad trees showed the same exact-boundary misses (for example a line lying exactly on a circle's rim, which RPT Contains misses with QuadPrefixTree too). On top of those, the packed-quad tree had extra RPT and composite false negatives and term-query vs RPT disagreements on points, for most classes exactly 192 more than the QuadPrefixTree control (the number of +180 point-query cases), and every printed example was a point query at x = +180; the control had none of these extras.
• A cell-level diagnosis printed the two different leaves, and an SMT check (Z3, exact rationals) showed the index-side and query-side point-to-cell rules agree in every cell without the longitude wrap and, on the level-1 split of the geo world, differ only at x = +180.
• The finding was reduced to a 6-method public-API JUnit and checked by an independent reproducer, an intended-behaviour devil's advocate, reviews by a model from another family (OpenAI GPT-5.6) that ran their own tests, an adjudication, a history, prior-report and security follow-up, and an audit. Found 2026-10-27 on main a9779ef3c193.