DateRangePrefixTree prints [1990 TO 1999] as "[1990 TO 1000]": a range end on the last year of a thousand-year block is printed as the block's first year

DateRangePrefixTree (spatial-extras, @lucene.experimental) indexes date ranges. When a range's end is the last year of a thousand-year block (1999, 2999, ..., 9999, at any precision down to 1999-12-31T23:59:59.999) or of a million-year block (2 BC), the range normalization stores that end as the whole block, and toString prints the block as its first year. So [1990 TO 1999] prints as "[1990 TO 1000]", which parseShape rejects with Wrong order, and [* TO 1999-12-31] prints as "[* TO 1000]", which parses to a range that ends 999 years early. The shape object is right, so matching, equality and the index are unaffected; the wrong text shows in the prefix-tree queries' toString, in logs, and in any code that stores or forwards a range as text and parses it again. In every release since 5.0.0.

1. The tree. Level 1 has 586 million-year cells, level 2 has 1,000 thousand-year cells in each, level 3 has 1,000 years in each (only the cells at the tree's maximum date are partial, getNumSubCells, DateRangePrefixTree.java:172-177), then months, days, hours, minutes, seconds and milliseconds (DateRangePrefixTree.java:128-140, YEAR_LEVEL = 3 at :102). The year count is offset by a whole number of million years (:153-154), so the thousand-year cells hold the years 0-999, 1000-1999, 2000-2999, ... (toShape, :315-322). 1999 is year 999, the last, of the cell 1000-1999.
2. Parsing. parseShape("[1990 TO 1999]") parses both ends as cells and calls toRangeShape (NumberRangePrefixTree.java:205-215).
3. Normalization. toRangeShape replaces each end with the coarsest equivalent cell: "this normalization/optimization process is actually REQUIRED based on assumptions elsewhere." (:118-119). truncateEndVals (:124, "chops off trailing max-vals"; :160-166) walks up while a value is the last one of its parent, so the end 1999 becomes the level-2 cell 1000-1999. The same holds for 1999-12, 1999-12-31 and so on down to 1999-12-31T23:59:59.999. An end of ISO year -1 (2 BC) or 999999 is the last year of a million-year cell and becomes that level-1 cell ([1 TO 999999] prints "[0001 TO 0000]", executed by the hunt's probe). The shape [1990, 1000-1999] covers exactly 1990-01-01 to 1999-12-31.
4. Printing. SpanUnitsNRShape.toString prints both ends with the same per-cell printer (:399-406): "[" + toString(minLV) + " TO " + toString(maxLV) + "]".
5. The per-cell printer. DateRangePrefixTree.toString(UnitNRShape) is toString(toCalendar(lv)) (DateRangePrefixTree.java:380-383). toCalendar adds up only the values the cell has (:357-363), so a level-2 cell gives the block's first year, at year precision (:364-370). The end 1000-1999 prints as 1000. For a range start that is right: [1000 TO 1998] round-trips.
6. Re-parsing. parseShape("[1990 TO 1000]") throws IllegalArgumentException("Wrong order: ...") (NumberRangePrefixTree.java:126-129, documented at :114-115). If the start lies at or before the block's first year (*, 0500, 1000-03), there is no error and the range now ends on the last day of the block's first year: 999 years early, or about a million years for a million-year end cell.

IntersectsPrefixTreeQuery built from [* TO 1999-12-31] and from its printed text both print queryShape=[* TO 1000], and equals is false. With the fix every row round-trips ([-9999 TO -1] prints "[-9999 TO -0001]", [* TO 1999-12-31] prints "[* TO 1999]"), and the two queries print queryShape=[* TO 1999] and are equal.

Not part of this bug: a range that is exactly one block ([2000 TO 2999]) normalizes to a single cell and prints as "2000", which parses back as the single year 2000. The date syntax has no token for such a cell and an upstream test accepts a date-like string for a bare coarse cell, so that may be intended; the fix leaves it unchanged.

• Who. Applications that use DateRangePrefixTree from the opt-in spatial-extras module (@lucene.experimental), for example through NumberRangePrefixTreeStrategy. Downstream, Apache Solr's DateRangeField is built on it (read from Solr's code, not run).
• Trigger. Either built-in calendar (DEFAULT_CAL or JAVA_UTIL_TIME_COMPAT_CAL) and ordinary input: decades or centuries ending in a year X999, [* TO 1999-12-31], and far-future open-end values such as 2999-12-31T23:59:59.999 or 9999. Deterministic, assertions on or off.
• Misleading text. A query over [* TO 1999-12-31] prints queryShape=[* TO 1000] in IntersectsPrefixTreeQuery, ContainsPrefixTreeQuery and WithinPrefixTreeQuery toString; logs and debug output show a range that is not the one searched, and two different queries print identically.
• Broken round trip. Code that keeps a range as toString() text and parses it later gets IllegalArgumentException when the start lies inside the end's block after its first year, and otherwise a range that silently ends 999 years early (about a million years for a million-year end cell: [* TO -1] prints "[* TO -1000000]", which parses without error). Over 452,984 legal ranges in two trees (the default and the java.time-compatible calendar; grids of 434 and 839 edge values), the hunt's exhaustive check found 10,430 silent interval mismatches and 4,655 parse exceptions, all with a block end (default tree: 2,464 and 1,477), and none with the fix (the grids are not a usage frequency).
• Downstream reach (read, not run). Solr stores the client's input string for a DateRangeField value and uses shape.toString() only for values that arrive as a Shape object through the Java API; an atomic update of such a document re-parses that stored text.
• Not affected. Matching, query equals/hashCode, caching and the index (CheckIndex passes on an index with the affected ranges). No extra cost: a parse-print-re-parse cycle takes 5.8 to 11.1 microseconds, flat.
• How likely: plausible. Such range ends are ordinary, but the harmful half needs code that re-parses the text, and nothing was reported in the 11 years since 5.0.0.

The test asserts that parseShape(shape.toString()) equals the shape. On a stock build it fails with the IllegalArgumentException that parseShape throws on the printed string, so the message Wrong order: 1990 TO 1000 shows the printed end (1000, expected 1999). With the fix the assertEquals runs and passes. It failed with both seeds run (DEADBEEF, 5EED1234); all lines are within 100 columns.

Regression test: this same class; it passes with the recommended fix.

cp $REPRO/TestDateRangeBlockEndToString.java $LUCENE/lucene/spatial-extras/src/test/org/apache/lucene/spatial/prefix/tree/
cd $LUCENE && ./gradlew :lucene:spatial-extras:test --tests TestDateRangeBlockEndToString -Ptests.seed=DEADBEEF -Ptests.asserts=true
# assertions off fails the same way: -Ptests.asserts=false

# gradle, stock 645d4fe14a20, -Ptests.seed=DEADBEEF -Ptests.asserts=true (suite output trimmed; -Ptests.asserts=false identical)
TestDateRangeBlockEndToString > testRangeEndingOnLastYearOfMillennium FAILED
    java.lang.IllegalArgumentException: Wrong order: 1990 TO 1000
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:ACD30FF6D2086A48]:0)
        at org.apache.lucene.spatial.prefix.tree.NumberRangePrefixTree.toRangeShape(NumberRangePrefixTree.java:128)
        at org.apache.lucene.spatial.prefix.tree.NumberRangePrefixTree.parseShape(NumberRangePrefixTree.java:215)
        at org.apache.lucene.spatial.prefix.tree.TestDateRangeBlockEndToString.testRangeEndingOnLastYearOfMillennium(TestDateRangeBlockEndToString.java:28)

1 test completed, 1 failed

# standalone runner, seed DEADBEEF (summary of the runs)
main 645d4fe14a20  -ea: FAIL 1/1   -da: FAIL 1/1
10.6.0             -ea: FAIL 1/1   -da: FAIL 1/1
9.1.0              -ea: FAIL 1/1
message: java.lang.IllegalArgumentException: Wrong order: 1990 TO 1000

• Contract. NRShape#toString: "The result should be parseable by {@link #parseShape(String)}." (NumberRangePrefixTree.java:84). parseShape: the range syntax "is the same thing as the toString() of the range shape, notwithstanding range optimization." (:199). The per-cell printer: "A string representation of the UnitNRShape that is parse-able by {@link #parseUnitShape(String)}." (:174-178).
• Author's intent. On LUCENE-5648 (now #6710), David Smiley, who wrote the class, described a patch on 2014-05-21: "Parses calendar ranges. This means you can round-trip toString() and parseShape() wether it's a single Calendar value "2014-05" or a range "[- TO 2013]"." The NRShape#toString javadoc came with their refactoring of 2014-12-14.
• The optimizer test's examples keep the meaning. TestDateRangePrefixTree.testShapeRangeOptimizer (:262-280) asserts exact strings of optimized ranges (strings only, not containment), each denoting the input range ([2014-01-01 TO 2014-12-31] prints "2014"); none has a block as its end.
• An exact string exists. A thousand-year end block means "up to the end of its last year", which the syntax writes as 1999; the printer already gets the start case right ([1000 TO 1998] round-trips).
• No acceptance found. No upstream test, CHANGES.txt or MIGRATE.md entry accepts a lossy or unparseable range string, and the prior-art searches found no issue or list thread that does.

The strongest case for "intended": the thousand- and million-year levels are internal tree levels that ISO dates cannot express; "should be parseable" does not say "parses back to an equal shape"; "notwithstanding range optimization" admits a different string; the classes are @lucene.experimental; Lucene does not promise that Query#toString parses back; and TestDateRangePrefixTree.java:60 accepts a date-like string for a bare level-1 cell.

Why it fails: "[1990 TO 1000]" is not parseable at all, so even the weakest reading breaks; the optimization only replaces a range by an equivalent one, so it cannot license a string that means a shorter range; the author stated round-trip intent for ranges; and the line-60 test is a "test no underflow" check: level-1 cell 0 prints the full-precision minimum date -292269054-12-02T16:47:04.192 and only its BC sign is asserted, so it says nothing about range ends. Verifiers, the adjudication and the cross-model reviewer of the intended lens rejected the intended reading. Expect a maintainer to ask about the bare-block case; it is left out of this report on purpose.

One fix was written by the finder and validated again in a scratch worktree of 645d4fe14a20; another fix site is described but not written, and two variants are rejected.

The change is +26/-1 lines in NumberRangePrefixTree.java and DateRangePrefixTree.java. SpanUnitsNRShape.toString prints its end with a new protected toStringAsRangeEnd(UnitNRShape), which defaults to toString(lv). DateRangePrefixTree overrides it: a million- or thousand-year cell is filled down to the year level with each level's last child (getNumSubCells(...) - 1, which also handles the partial last million-year block) and printed as that year. [1990 TO 1999] then prints as itself, [-9999 TO -1] as "[-9999 TO -0001]", [* TO 1999-12-31] as the equivalent "[* TO 1999]".

// NumberRangePrefixTree: new hook; SpanUnitsNRShape.toString uses it for maxLV
protected String toStringAsRangeEnd(UnitNRShape lv) { return toString(lv); }
// DateRangePrefixTree (condensed)
@Override
protected String toStringAsRangeEnd(UnitNRShape lv) {
  if (lv.getLevel() > 0 && lv.getLevel() < YEAR_LEVEL) { // a block prints as its LAST year
    int[] vals = new int[YEAR_LEVEL];
    for (int level = 1; level <= lv.getLevel(); level++) vals[level - 1] = lv.getValAtLevel(level);
    for (int level = lv.getLevel(); level < YEAR_LEVEL; level++)
      vals[level] = getNumSubCells(toShape(vals.clone(), level)) - 1;
    return toString(toCalendar(toShape(vals, YEAR_LEVEL)));
  }
  return toString(lv);
}

Trade-offs

• Changes only the printed end of a SpanUnitsNRShape whose end is a million- or thousand-year cell; bare cells and range starts are unchanged, so TestDateRangePrefixTree.java:60 and the optimizer test still hold. Other NumberRangePrefixTree subclasses keep the default.
• Affects toString only; nothing on the indexing or search path.
• Adds one protected method to an @lucene.experimental class.

What the checks validated

Gradle in a scratch worktree of 645d4fe14a20, OpenJDK 25.0.3, seed DEADBEEF (2026-10-31). Stock: the minimal test fails with assertions on and off. With the fix:

• the minimal test passes with assertions on and off;
• TestDateRangePrefixTree, TestDateNRStrategy and TestNumberRangeFacets pass: 3 classes, 20 tests, 0 failures;
• the whole :lucene:spatial-extras:test passes: 26 classes, 117 tests, 0 failures, 5 skipped;
• checkGoogleJavaFormat, ecjLintMain and forbiddenApisMain for spatial-extras pass (the finder's diff as is failed only checkGoogleJavaFormat on one 101-column comment line, rewrapped and lightly reworded in this diff; the code is identical).

Earlier: the upstream date-tree suites passed 100 of 100 (5 iterations), a verifier's 7 tests pass 7 of 7 including the 2 BC end, and both mismatch kinds of the exhaustive check drop to 0 with it.

A maintainer may prefer a range-aware printer inside DateRangePrefixTree, or a SpanUnitsNRShape.toString that asks the tree for the last year of a cell (suggested by the adjudication and a verifier). That moves the code, not the behaviour. Any variant must keep toString(UnitNRShape) printing a bare cell as a unit, as its javadoc requires ("parse-able by parseUnitShape").

Printing a bare block as "[first TO last]" (the finder's first variant) breaks the upstream assertion at TestDateRangePrefixTree.java:60 and the unit-string contract of toString(UnitNRShape). Not truncating the end changes the stored shape, its equality and its indexed cells, and the normalization is "REQUIRED based on assumptions elsewhere" (NumberRangePrefixTree.java:118-119); not tried.

Bounded-exhaustive translation validation of the stock jar: for every legal [a TO b] range over 839 edge units of the java.time-compatible tree (31 years including BC, leap and >9999 years, at every precision; 356,472 ranges) and 434 edge units of the default tree (16 years from 1583; 96,512 ranges), 452,984 ranges in all, the harness re-parses toString() and compares the re-parsed interval with a proleptic-Gregorian java.time reference. It found 10,430 interval mismatches and 4,655 parse exceptions (default tree: 2,464 and 1,477), all with a thousand- or million-year END cell, with assertions on and off; both kinds disappear with the fix. The finder then wrote a three-line public-API JUnit, and the hunt later cut it to the one-input test shown here.

The harness's other mismatch kinds belong to other leads of the same hunt and are not part of this bug.