ShapeField.encodeTriangle moves an edge flag when it flips a clockwise triangle, so LatLonShape and XYShape CONTAINS queries return wrong hits

LatLonShape and XYShape index a polygon as tessellation triangles and store, for each triangle edge, a flag that says whether the edge belongs to the polygon's outline. CONTAINS queries ("does the indexed shape fully contain my box, polygon, line or circle?") rely on those flags: crossing a flagged edge means the query leaves the shape, crossing only unflagged edges means it stays inside. ShapeField.encodeTriangle makes a clockwise triangle counter-clockwise by swapping vertices b and c, but then gives the new first edge the flag of the old edge b-c instead of the old edge c-a (ab = bc; at ShapeField.java:221; it should be ab = ca;). Whenever those two flags differ, a polygon edge is stored as internal (CONTAINS then says yes for areas that stick out through it, in one test a box 99.9998% outside) or an internal diagonal as outline (CONTAINS says no for boxes well inside). XYShape triangles can be clockwise in the stored coordinates even for small integer polygons, because the stored values are sortable float bits; LatLonShape triangles become clockwise when quantization flips a thin triangle. The wrong flags are written into the index, survive merges and pass CheckIndex. The line dates from LUCENE-9642, released in 8.8.0 (2021), which changed the swap from a-c to b-c but kept the flag assignment of the a-c swap; every release since is affected, and a one-line fix passes the whole :lucene:core test suite.

• Tessellation triangle: LatLonShape and XYShape cut a polygon into triangles and index each one as a point field. The tessellator labels each triangle edge as part of the polygon's outline or as an internal cut (Tessellator.Triangle.isEdgefromPolygon, Tessellator.java:1724).
• Edge flags: three booleans ab, bc, ca stored with each triangle (bits 3-5 of the packed value, ShapeField.java:275-277, read back at :367-369; only a triangle that collapses to a line or a point gets merged flags, :374-400). Each one "represent[s] if edge ab|bc|ca belongs to original shape" (ShapeField.java:434-441).
• CONTAINS: QueryRelation.CONTAINS matches a document whose shape fully contains the query geometry. Per triangle, crossing a flagged edge gives NOTWITHIN and crossing only unflagged edges gives CANDIDATE (Component2D.java:101-115; LatLon boxes: SpatialQuery.java:947-1001; XY boxes: Rectangle2D.java:180; a circle query gives NOTWITHIN on a flagged edge and CANDIDATE when its centre lies in the triangle, Circle2D.java:196-214); a document matches if a triangle is CANDIDATE and none is NOTWITHIN (SpatialQuery.java:591-645).

1. encodeTriangle first rotates the triangle so that the minimum-x vertex comes first (ShapeField.java:157-212). That shifts the flags cyclically with their edges, which is correct.
2. If the triangle is then clockwise (GeoUtils.orient(...) == -1, :215), it swaps vertices b and c (:216-227). The new vertex order is a, old c, old b, so the new edge a-b is the old edge c-a, the new b-c is the old b-c reversed, and the new c-a is the old a-b.
3. The code sets ab = bc; (:221, under the comment "ab becomes bc"), leaves bc alone and sets ca = old ab. The first assignment should be ab = ca;. So the old c-a flag is lost and the old b-c flag is stored on two edges, whenever the two differ. In a grid check, 912 of 1,824 clockwise inputs and 0 of 1,824 counter-clockwise inputs decode with a wrong flag.
4. An outline edge that loses its flag fails open: a query crossing it is treated as staying inside (CONTAINS false positive). An internal diagonal that gains the flag fails closed (CONTAINS false negative).

• XYShape: easily, even for small integer polygons (no rate on real data was measured). Coordinates are stored as NumericUtils.floatToSortableInt (XYEncodingUtils.java:50-52), which keeps the order of values but not their distances: 0 is stored as 0, 1 as 1,065,353,216, 3 as 1,077,936,128, 6 as 1,086,324,736 and 8 as 1,090,519,040. Both triangles of the polygon (6,0) (-1,7) (-8,8) (0,1), and the triangle (1,8) (3,3) (6,0) of the polygon (3,3) (6,0) (8,5) (1,8), are counter-clockwise in float coordinates and clockwise in the stored ones. In the first polygon the outline edge (-1,7)-(-8,8) is stored as internal; in the second the diagonal (6,0)-(1,8) is stored as outline.
• LatLonShape: when quantization (4.19e-8 degrees latitude, 8.38e-8 longitude, LatLonShape.java:72-74) flips a thin, nearly collinear triangle, for example along a densified straight edge.

One document per index, default IndexWriterConfig (LuceneTestCase picks the JUnit's codec from the seed; a framework-free main() with the default codec gives the same encoding and XY results). Encode/decode of the clockwise triangle (0,0) (0,10) (10,0) with only edge (0,10)-(10,0) flagged gives (0,0) (10,0) (0,10) with flags [true,true,false] instead of [false,true,false]. XY polygon (6,0) (-1,7) (-8,8) (0,1): CONTAINS for the box x [-4.75,-4.25], y [7.25,7.75] is 1 (expected 0), and stays 1 when the box is 100,000 tall (99.9998% outside), as a polygon or line query and for circles of radius 0.1 and 0.2 on the edge. XY polygon (3,3) (6,0) (8,5) (1,8): CONTAINS for [3.25,3.75] x [3.75,4.25] is 0 (expected 1). LatLon polygon with a densified north-east edge: CONTAINS is 1 for a box whose north-east corner is about 0.007 degrees outside, and still 1 with the box extended 10 degrees (about 1,100 km) north. INTERSECTS is 1 in every case.

• Who. Applications that index polygons with LatLonShape.createIndexableFields or XYShape.createIndexableFields (the default indexing path, default codec) and query them with QueryRelation.CONTAINS and a box, polygon, line or circle. By reading their default branches (not tested), Elasticsearch and OpenSearch pass a geo_shape query with relation contains to LatLonShape.newGeometryQuery, and Elasticsearch passes a shape contains query to XYShape.newGeometryQuery.
• Default or opt-in. The indexing path is the default; CONTAINS is an opt-in relation, used less than INTERSECTS.
• Not affected. INTERSECTS, WITHIN and DISJOINT do not read the flags; point CONTAINS ("which shapes contain this point") ignores them (in the security probe CONTAINS equalled INTERSECTS in all 7,600 point checks, and none of the 6,000 XY checks differed from the exact answer); Lucene's doc-values shape queries reject CONTAINS; points and lines are encoded with all flags set.
• How often. Unmeasured on real data. Edge-biased searches (boxes centred on edges and diagonals, so not population rates): for XYShape, 1 of 298 random convex quadrilaterals with integer vertices in [-8,8] and 9 of 100 with mixed-magnitude coordinates gave a wrong CONTAINS answer (6 false positives and 37 false negatives in 9,471 box checks); for LatLonShape, the finder reported 3,455 of 19,859 generated star polygons (half with one densified edge) with at least one wrong flag (raw output not kept).
• What the damage looks like. Silent (no exception, INTERSECTS still matches); large (a box 99.9998% outside matched); both directions (false positives and false negatives, so MUST_NOT CONTAINS exclusions can fail open); and persistent: the wrong flags are in the index, survive forceMerge(1), pass CheckIndex, and a fixed Lucene reading a 10.5.2 index still gives the wrong answers for the old documents, also after forceMerge(1). Current readers and merges do not repair them (executed for two XY polygons written by 10.5.2); reindexing the shapes from their source geometry is the practical repair.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: flagged edges of 0, 0 10, 0 0, 10 [true,true,false] expected:<[(0,10)-(10,0)]> but was:<[(0,0)-(10,0), (0,10)-(10,0)]>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:120)
       org.apache.lucene.document.TestEncodeTriangleClockwiseEdgeFlag.testClockwiseTriangleKeepsEdgeFlag(TestEncodeTriangleClockwiseEdgeFlag.java:35)

• The contracts. DecodedTriangle.ab/bc/ca (ShapeField.java:434-441): "represent if edge ab|bc|ca belongs to original shape". The encodeTriangle javadoc (:139-144): "Triangles are encoded with CCW orientation and might be rotated"; re-orienting and rotating change the vertex order, not the edges. Component2D.WithinRelation (Component2D.java:101-115) defines CONTAINS through those per-edge flags. CHANGES 8.3.0 (LUCENE-8620): "Tessellator labels the edges of the generated triangles whether they belong to the original polygon. This information is added to the triangle encoding."
• Lucene's own test states the invariant. BaseShapeEncodingTestCase.verifyEncodingPermutations (:314-349) asserts [a,b,c] == [c,a,b] == [b,c,a] == [c,b,a] == [b,a,c] == [a,c,b], passing each flag with its own edge, but only with the single false on edge c-a (:321), where the swap happens to be harmless. With the false moved to edge a-b or b-c, the invariant fails 6 of 15 checks on stock and 0 of 15 with the fix; run over all 8 flag patterns, 9 tests in each of TestLatLonShapeEncoding and TestXYShapeEncoding fail on stock and pass with the fix.
• Why the tests missed it. The other encoding tests use all-true flags; the randomized CONTAINS oracles compute the expected answer from the same indexed, decoded triangles, so they share the bug. The unmodified upstream geo and shape suites pass on stock (27 classes); in a 45-class run that adds the new tests, the only failures are the 22 new assertions.
• History. In 8.3.0 to 8.7.0 the clockwise branch swapped a and c with ab = bcFromShape; bc = abFromShape; ca = caFromShape (8.7.0 ShapeField.java:122-132), correct for that swap. LUCENE-9642 (8.8.0) changed the swap to b-c to fix an orientation problem with degenerate triangles, but kept the a-c flag assignment (ab = bcFromShape became ab = bc) and added the comment "ab becomes bc" that describes it; 8.7.0 has no such comment. Its issue and review never mention edge flags; the test it added encodes all-true flags.
• Precedent. #12020 / #12022, a flag error in decodeTriangle with the same CONTAINS false-positive symptom, was accepted and fixed as a bug (9.5.0, 8.11.3).

The strongest case: "the comment ab becomes bc says it is meant; CONTAINS is approximate anyway because vertices are quantized; and CONTAINS is defined through the flags, so whatever the flags say is the answer."

Why it fails: the comment does not show a design decision. LUCENE-9642 wrote it in the same commit as the bug, and it restates the flag assignment that was right for the old a-c swap; the current code never uses the old ca flag at all and stores the bc flag on two edges, which no per-edge design can mean. Quantization does not explain it: XY encoding is exact for floats; the false-positive box sticks out 0.21 to 0.28 units past the outline edge and the false-negative box stays at least 0.51 units inside every edge; the LatLon corner is about 0.007 degrees out (five orders of magnitude above the quantum), and the false positive reaches 100,000 units (XY) and 10 degrees (LatLon) outside. The flags have their own contract, which the encoder breaks without any query. The inputs are legal: simple, counter-clockwise polygons (checked with exact rational arithmetic) that index with checkSelfIntersections=true through the public API.

What a maintainer could still raise: the public CONTAINS javadoc is thin (QueryRelation.CONTAINS is "used for CONTAINS Queries", ShapeField.java:126), and an upstream test leaves a dateline CONTAINS query commented out as "Not supported due to encoding" (TestLatLonShape.java:388); false negatives could be called conservative (the strongest of these, rated moderate by the cross-model fact check); and no report was found in almost six years. None of these covers wrong flags on exact XY coordinates: the per-edge flag contract is broken before any query runs, and the rejected box lies at least 0.51 units inside. Verdict: not intended, a defect.

One fix was built and validated; the other options are alternatives or explain why no read-side repair exists.

In ShapeField.encodeTriangle (ShapeField.java:214-228), the new edge a-b after the b-c swap is the old edge c-a, so it takes the old ca flag. The test part turns verifyEncodingPermutations into a loop over all 8 flag patterns, each checked by a private overload that passes every flag with its own edge in all six vertex orders (+29/-12 lines in BaseShapeEncodingTestCase.java; the public signature and its 9 callers are unchanged). A second patch file also adds the repro as a new test class.

       final boolean tempBool = ab;
-      // aX and aY do not change, ab becomes bc
-      ab = bc;
+      // aX and aY do not change, the new ab edge (a-c) is the old ca edge
+      ab = ca;
       bX = cX;
       bY = cY;
-      // bc does not change, ca becomes ab
+      // bc does not change (same edge, reversed), the new ca edge (b-a) is the old ab edge
       cX = tempX;
       cY = tempY;
       ca = tempBool;

Trade-offs

• No query-time cost; the encoded layout and the index format are unchanged.
• It does not repair existing indexes: shapes indexed by 8.8.0 or later keep their wrong flags (executed for two XY polygons: a 10.5.2 index read by the fixed jar, also after forceMerge(1)). The CHANGES entry should tell CONTAINS users to reindex.
• No benchmark was run (one assignment changes).

What the checks validated

• Scratch worktree at ea57360912ed, JDK 25, gradle: on stock, the repro fails 4 of 4 (assertions on and off) and the strengthened permutation test fails 18 tests; the 45 shape and geo classes (393 tests) fail exactly those 22.
• With the fix: the same 393 tests pass (seed DEADBEEF with assertions on, seed CAFEBABE with assertions off); the whole :lucene:core suite passes (8,869 tests as gradle counts them, 0 failures, 322 skipped; one seed); :lucene:core:check -x test passes, and tidy leaves the fix unchanged.
• Through the repro harness: the finder's test, an independent reproducer's 6-test JUnit, the 5-test security probe and the triangle dump pass; 27 upstream geo and shape suites pass; a Z3 check of a hand-written model of the rotate/flip step shows that the fixed step keeps every flag on its own edge for all distinct-vertex inputs, whatever the orientation test returns (stock: a counterexample).
• All runs used one JDK (OpenJDK 25.0.3) and one platform (Linux aarch64).

Name the three old flags first (oldAB, oldBC, oldCA) and assign ab = oldCA; bc = oldBC; ca = oldAB; next to the vertex swap, so the mapping is visible.

Trade-offs

Same behaviour as the recommended fix, a slightly larger diff. A straight revert to the 8.7.0 order (re-orient, then rotate) would bring back the LUCENE-9642 problem: rotating after re-orienting could undo the orientation of a degenerate triangle. Any other order must keep the stored triangle counter-clockwise.

The stored bits do not say whether a triangle was flipped, and the lost c-a flag is not stored anywhere.

Trade-offs

decodeTriangle and the queries cannot correct a stored triangle on its own. Rebuilding the outline from all triangles of a document was not explored; reindexing from the source geometry is the practical repair.

Do not base access or compliance decisions on shape CONTAINS alone; re-check containment exactly against the original geometry for the returned candidates.

Trade-offs

Extra work per hit, and it catches only false positives; false negatives stay missing.

Method: bounded-exhaustive translation validation of the stock jar's ShapeField.encodeTriangle and decodeTriangle against exact per-edge flag semantics (the hunt's "semi-formal" tier), a hunt unit (geo tessellator and shapes), 2026-10-25, main ea57360912ed.

• Small scope: every ordered vertex triple over {-2..2}^2 with all 8 flag patterns, 125,000 checks: 25,776 flag mismatches, all on clockwise inputs (exactly half of the clockwise inputs). Extended scope: an 11-value set including the int extremes, 14,172,488 checks: 3,394,812 flag mismatches, all clockwise. The per-edge flag oracle applies to the triples with three distinct vertices. The extended run also counted 16,680 inputs at the int extremes whose decoded triangle has the wrong orientation by exact integer arithmetic, a separate effect, most likely of GeoUtils.orient computing in doubles (GeoUtils.java:203); it is not this bug and was not analysed further.
• The root cause was then read from the code. An SMT check (Z3) of the flag invariant on a hand-written model of the rotate/flip step (a proof about the model, not the compiled Java), with the orientation result left free, is satisfiable (a counterexample) for the stock code and unsatisfiable for the one-line fix.
• Search harnesses over XY and LatLon polygons found the end-to-end CONTAINS false positives and false negatives and minimised the LatLon case; the finder then wrote the JUnit test.
• Before filing it as a candidate, a reviewer from another model family (OpenAI GPT-5.6) tried to refute it and reproduced it with its own XY tests. Then an independent reproducer, a works-as-designed review, an intended-behaviour devil's advocate and an adjudication checked it; a follow-up traced its history over 35 runs, searched for prior reports and probed the security reach; this doc's brief validated the fix with gradle.