Operations.complement and minus return a wrong, non-deterministic automaton when an arc ends at Integer.MAX

The finding in 30 seconds

Background: automaton arcs and how complement works

A Lucene Automaton is a set of states joined by arcs. Each arc carries a label range [min, max] of code points (stored as int), so one arc can stand for many characters. Automata.makeCharRange(min, max) builds one arc from a start state to an accepting state.
Operations.complement accepts exactly the words its input rejects. It first makes the automaton deterministic and total: totalize adds an arc into one extra dead state for every label range a state does not handle. Then it flips every state's accept bit, so the dead state, which input words never reach, now accepts.
To find the uncovered ranges, totalize walks a state's arcs in order and remembers the first label not yet covered, t.max + 1. Whatever is left after the last arc, up to Character.MAX_CODE_POINT (1114111), goes to the dead state.

Diagram of the bug: the start state of makeCharRange('a', Integer.MAX_VALUE) has one arc, 97 to 2147483647, into an accepting state. totalize adds the gap arc 0 to 96 into a dead state; then t.max + 1 wraps to a negative number, so it also adds an arc 0 to 1114111 into the dead state, overlapping the real arc. complement flips the accept bits, the dead state becomes accepting, and the word a is accepted. — One state of `makeCharRange('a', Integer.MAX_VALUE)` before and after `totalize`. The real arc covers 97 to 2147483647. Because `t.max + 1` wraps, `totalize` also adds an arc over 0 to 1114111 into the dead state. After `complement` flips the accept bits, the dead state accepts, so `"a"` is accepted. Select the still to open it at full size. Generated with AI, checked against the code.

The finding, step by step

Build Automata.makeCharRange('a', Integer.MAX_VALUE): it accepts every one-character word from "a" (code point 97) upward, with Integer.MAX_VALUE as an open upper end, the value Lucene's own TestRegExpParsing uses in the expected automaton of [^c].
Call Operations.complement on it. You expect a deterministic automaton that rejects "a". With the upper end Character.MAX_CODE_POINT (1114111) that is exactly what you get.
Instead the complement accepts "a" and isDeterministic() is false, with assertions on or off and no error. Operations.minus(makeString("a"), thatRange) keeps "a" instead of returning the empty language.
Why: complement sends every label a state does not cover to a dead state, tracking the first uncovered label as t.max + 1. For 2147483647 that int sum wraps to -2147483648, so it also adds an arc 0 to 1114111 into the dead state, on top of the real arc. Flipping the accept bits makes the dead state accepting, and "a" reaches it.

Who is affected

Only application code that builds its own automaton with an arc ending at exactly Integer.MAX_VALUE (for example makeCharRange(min, Integer.MAX_VALUE) as an open upper end) and passes it to complement or minus. No configuration or scale needed. Regex queries are not hit: RegExp keeps every range within code points. Every release from 4.0.0-alpha to 10.6.0.

Mechanism, terms and numbers536 words

Operations.complement(a, limit) "Returns a (deterministic) automaton that accepts the complement of the language of the given automaton" (Operations.java:338-339 at 5adff78bb168). It determinizes, calls totalize (:351), which adds an arc to one dead state for every label a state does not handle, and flips every accept bit (:352-355). totalize keeps int maxi, the first label not yet covered (:1325), and updates it with if (t.max + 1 > maxi) maxi = t.max + 1; (:1333-1335). For an arc ending at Integer.MAX_VALUE, t.max + 1 wraps to Integer.MIN_VALUE, maxi stays behind, and the tail arc [maxi, 0x10FFFF] to the dead state (:1338-1340) is added on top of the real arc. After the flip the dead state accepts. So complement(makeCharRange('a', Integer.MAX_VALUE)) accepts "a", a word of its input, and reports isDeterministic() false, with assertions on and off; minus(a1, a2), which is intersection(a1, complement(a2)) (:383), keeps words it should remove. Upper ends 0x10FFFF, 0x110000 and Integer.MAX_VALUE - 1 give a deterministic complement that rejects "a". The wrap dates from 2010, when automaton labels went from char to int (LUCENE-2265); every release from 4.0.0-alpha to 10.6.0 has it. RegExp, the only caller of complement in Lucene's runtime code (outside the test framework), cannot create the label, and both methods are deprecated for removal in Lucene 12 on main and branch_11x (public and not deprecated in 10.6.0; the Operations class is tagged @lucene.experimental). The wrong result is demonstrated; whether a label above 0x10FFFF is inside the documented contract is disputed ("Why it looks unintended"), so the fix reads best as a robustness fix.

The mechanism (main `5adff78bb168`, `lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java`)

:351: complement runs totalize(determinize(a, limit)). For makeCharRange('a', Integer.MAX_VALUE), state 0 has one arc [97, 2147483647] -> 1; state 1 accepts.
:1325: int maxi = 0. :1330-1332: t.min = 97 > maxi, so the gap arc [0, 96] -> dead is added (correct).
:1333-1335 (the fix site): t.max + 1 is 2147483647 + 1, which wraps to -2147483648; t.max + 1 > maxi is false and maxi stays 0.
:1338-1340: maxi (0) <= 0x10FFFF, so the tail arc [0, 1114111] -> dead is added on top of [97, 2147483647] -> 1. When the result finishes state 0 (Automaton.finishCurrentState, called from addTransition once the arcs of state 1 start, Automaton.java:162-165), it finds the overlap and clears its deterministic flag (:300-305).
:352-355: the accept bits are flipped; the dead state loops on every code point (:1320-1321) and now accepts, so "a" can follow the tail arc into it.

The numbers

The complement's arcs, as the hunt's probe prints them: s0*: [0,1114111]->2 [97,2147483647]->1, s1: [0,1114111]->2, s2*: [0,1114111]->2 (* = accepting; state 2 is the former dead state); isDeterministic=false.
Upper end 0x10FFFF, 0x110000 or 2147483646: deterministic and rejects "b" for makeCharRange('b', hi); 2147483647: not deterministic, accepts "b".
minus(makeString("a"), makeCharRange('a', Integer.MAX_VALUE)) is not empty; with Character.MAX_CODE_POINT it is.
With char labels (before 2010) t.max + 1 was at most 65536 and could not wrap.

Exposure and likelihood209 words

Who. Application code that calls Operations.complement or Operations.minus (or the test framework's AutomatonTestUtil.minus, AutomatonTestUtil.java:74) on an automaton it built itself with an arc ending at exactly Integer.MAX_VALUE, via makeCharRange or addTransition. One arc is enough.
Not affected. RegExp's REGEXP_COMPLEMENT (RegExp.java:676-681), the only caller of complement in Lucene's runtime code (outside the test framework), complements negated character classes whose ranges are code points, so regex strings cannot reach it. determinize, CompiledAutomaton and complement with an upper end of Integer.MAX_VALUE - 1 handle such labels correctly.
Effect. A silently wrong language: the complement accepts words it must reject, and minus keeps words it must remove. The result also breaks the javadoc's "(deterministic)" promise, so new CharacterRunAutomaton(result) throws IllegalArgumentException "Automaton must be deterministic" (RunAutomaton.java:63-64; executed, assertions on and off).
API status. Both methods are @Deprecated ("will be removed in Lucene 12") on main (Operations.java:346-349, :372-375) and branch_11x (#15763, #15755); in 10.6.0 and earlier they are public and not deprecated (the Operations class is tagged @lucene.experimental, Operations.java:56, as on main).
Likelihood: rare. No matching public report was found in the recorded searches and no Lucene component builds the label, but whoever does gets the wrong language every time.

Minimal repro

One JUnit test method on the public API: complement makeCharRange('a', Integer.MAX_VALUE) and assert that the result, intersected with makeString("a"), is empty. Deterministic, single-threaded, about 1 s; it fails with assertions on and off.

TestComplementOfRangeEndingAtMaxValue.java (lucene/core, package org.apache.lucene.util.automaton, 1 test)31 lines

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.lucene.util.automaton;

import org.apache.lucene.tests.util.LuceneTestCase;

public class TestComplementOfRangeEndingAtMaxValue extends LuceneTestCase {

  public void testComplementRejectsWordOfInput() {
    // expected: the complement of [a, Integer.MAX_VALUE] rejects "a"; actual: it accepts "a"
    Automaton notA =
        Operations.complement(
            Automata.makeCharRange('a', Integer.MAX_VALUE),
            Operations.DEFAULT_DETERMINIZE_WORK_LIMIT);
    assertTrue(Operations.isEmpty(Operations.intersection(notA, Automata.makeString("a"))));
  }
}

Command

cp $REPRO/TestComplementOfRangeEndingAtMaxValue.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/automaton/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.automaton.TestComplementOfRangeEndingAtMaxValue -Ptests.seed=DEADBEEF
# and with -Ptests.asserts=false: the same failure

Expected: The complement rejects "a": its intersection with makeString("a") is empty.
Observed: It accepts "a": java.lang.AssertionError at line 29, assertions on and off.

All files of this repro: repro/LFV-1167/

More files, environment, full output139 words

TestComplementOfRangeEndingAtMaxValue (one method, extends LuceneTestCase, package org.apache.lucene.util.automaton of the lucene/core tests). The assertion has no message; a bare AssertionError at line 29 means the complement accepts "a".

As the regression test, the same method fits in TestAutomaton (next to testComplement), with @SuppressWarnings("deprecation") on main if the build asks for it.

Environment

lucene	`main 5adff78bb168 (12.0.0-SNAPSHOT): fails; 9.12.3, 10.6.0: the same test fails; 10.5.2: an equivalent test fails; 4.10.0, 4.10.4 and 8.11.4: an older-API form fails`
jdk	`OpenJDK 25.0.3 (build 25.0.3+9-LTS)`
os	`Linux aarch64 (nothing platform-specific)`

Command (environment)

cp $REPRO/TestComplementOfRangeEndingAtMaxValue.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/automaton/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.automaton.TestComplementOfRangeEndingAtMaxValue -Ptests.seed=DEADBEEF
# and with -Ptests.asserts=false: the same failure

Observed output

TestComplementOfRangeEndingAtMaxValue > testComplementRejectsWordOfInput FAILED
    java.lang.AssertionError
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:C97885DBF22CBB13]:0)
        at org.junit.Assert.fail(Assert.java:87)
        at org.junit.Assert.assertTrue(Assert.java:42)
        at org.junit.Assert.assertTrue(Assert.java:53)
        at org.apache.lucene.util.automaton.TestComplementOfRangeEndingAtMaxValue.testComplementRejectsWordOfInput(TestComplementOfRangeEndingAtMaxValue.java:29)

(gradle on main 5adff78bb168, seed DEADBEEF, assertions on; with -Ptests.asserts=false the same assertion)

Why it looks unintended

complement promises "a (deterministic) automaton that accepts the complement"; no javadoc states or checks an upper label bound.
Only Integer.MAX_VALUE fails, the wrong answer is on a valid code point ("a"), and Lucene's own TestRegExpParsing uses that value as an open upper end.
Disputed: the package describes a Unicode alphabet, so labels above 0x10FFFF may be outside the contract.

The full argument299 words

What is shown and what is disputed. The implementation defect is demonstrated: for the stored int intervals, totalize builds overlapping arcs and complement accepts words of its input. Whether an arc ending above 0x10FFFF is inside the documented contract is disputed (the devil's advocate below; the cross-model reviewer rated that defence strong). The points below are a judgement, not a settled fact.
Contract. complement: "Returns a (deterministic) automaton that accepts the complement of the language of the given automaton" (Operations.java:338-339); minus promises the same for intersection(a1, complement(a2)) (:360-362); totalize: "added transitions to a dead state so that from every state and every label there is a transition" (:1309-1310). Neither these nor makeCharRange ("accepts a single codepoint whose value is in the given interval", Automata.java:136-151) or addTransition state or validate an upper label bound.
Tests. TestRegExpParsing.testNegatedChar and testNegatedCharRange build the expected automata of [^c] and [^b-d] as unions whose upper part is makeCharRange('d', Integer.MAX_VALUE) and makeCharRange('e', Integer.MAX_VALUE) (TestRegExpParsing.java:190-194, :240-244). Caveat: those tests never complement these automata, and they compare languages through AutomatonTestUtil.sameLanguage / subsetOf (TestRegExpParsing.java:832-840), which ignores labels above Character.MAX_CODE_POINT; so they show the idiom in Lucene's own code, not a promise about what complement does above 0x10FFFF. Complementing the [^c] one accepts "e", a word in the Unicode range, and is not deterministic; complement(new RegExp("[^c]").toAutomaton()) rejects "e" (main and 10.6.0).
Neighbouring code guards the same overflow. AutomatonTestUtil.subsetOf caps at Character.MAX_CODE_POINT before computing max + 1 (AutomatonTestUtil.java:681-686); totalize has no such guard.
History. The line comes from the char-label code, where t.max + 1 could not wrap, and was kept unchanged when labels became int (LUCENE-2265, 2010). No commit, issue or PR found in the recorded searches discusses the wrap.

The devil's-advocate check191 words

The strongest case for "intended": the package documents a "DFA/NFA implementation with Unicode alphabet" (package-info.java:33) and makeCharRange speaks of code points, so an arc ending at Integer.MAX_VALUE is outside complement's domain; a maintainer once said a special label must be a valid Unicode character for UTF32ToUTF8 (#6094, LUCENE-5030). makeAnyChar, totalize and RegExp all bound labels by Character.MAX_CODE_POINT. The cross-model reviewer refuted the bug on exactly these grounds (medium confidence, and it rated this defence strong), while reproducing it and agreeing with the root cause and the fix.

Our answer (a judgement): no javadoc states the precondition and nothing enforces it; Lucene's own tests use Integer.MAX_VALUE as an open upper end (although only in expected automata, compared up to Character.MAX_CODE_POINT); other operations handle the label; and the wrong answer is on an in-alphabet word ("a"). That makes it a fair argument for Low priority and for framing the fix as hardening (or for clarifying the contract, fix C), rather than evidence that the behaviour is intended. The independent reproducer, the devil's-advocate verifier and the adjudication did not accept it as making the behaviour intended.

Suggested fix

Recommended Keep maxi as a long (fix A)

Keep maxi in totalize as a long (t.max + 1L, two (int) casts where it is passed on), so the sum cannot wrap. Nothing changes for arcs that do not end at Integer.MAX_VALUE. The repro passes with assertions on and off, and core's util.automaton test package runs 239 tests with 0 failures (2 skipped).

      long maxi = Character.MIN_CODE_POINT;
      ...
        if (t.min > maxi) {
          result.addTransition(i, deadState, (int) maxi, t.min - 1);
        }
        if (t.max + 1L > maxi) {
          maxi = t.max + 1L;
        }
      ...
      if (maxi <= Character.MAX_CODE_POINT) {
        result.addTransition(i, deadState, (int) maxi, Character.MAX_CODE_POINT);
      }

All options and trade-offs3 options · 431 words

Fix A was built and checked through gradle on 5adff78bb168; B and C were not run. On main the planned removal of complement and minus in Lucene 12 may make the fix moot there, but it still matters for branch_11x and 10.x, where totalize is byte-identical (10.6.0 Operations.java:1330-1363); 10.x users would get it only through a 10.6.x bugfix release or by upgrading (branch_10x was decommissioned, #16911). Since the label-domain question is disputed, fix A reads best as a robustness fix.

Keep maxi as a long (fix A) (validated by the checks) (recommended)

In Operations.totalize, declare long maxi (:1325), compare and assign t.max + 1L (:1333-1335), and cast maxi to int where it is passed to addTransition (:1331, :1339).

      long maxi = Character.MIN_CODE_POINT;
      ...
        if (t.min > maxi) {
          result.addTransition(i, deadState, (int) maxi, t.min - 1);
        }
        if (t.max + 1L > maxi) {
          maxi = t.max + 1L;
        }
      ...
      if (maxi <= Character.MAX_CODE_POINT) {
        result.addTransition(i, deadState, (int) maxi, Character.MAX_CODE_POINT);
      }

Trade-offs

Five changed lines, no new branch. The casts are safe: they run only when maxi < t.min or maxi <= 0x10FFFF, so maxi fits in an int. Arcs that do not end at Integer.MAX_VALUE get exactly the same dead-state arcs as before.

What the checks validated

Gradle in a scratch worktree at 5adff78bb168, seed DEADBEEF: the repro fails without the fix (assertions on, and -Ptests.asserts=false) and passes with it (both).
With the fix: the whole org.apache.lucene.util.automaton test package of core, 16 classes incl. the repro (TestAutomaton 85, TestRegExpParsing 63, TestOperations 23, TestCompiledAutomaton 14, ...): 239 tests, 0 failures, 2 skipped. checkGoogleJavaFormat on core passes. The full core suite was not run, and only OpenJDK 25.0.3 on Linux aarch64 was used.
Earlier: the hunt's shadow-class runs of the same change pass the repro (assertions on and off) and the other verifiers' own tests; the cross-model reviewer's run passed TestOperations (23) and TestRegExpParsing (63) with it.

Saturate instead of widening (fix B)

Keep int maxi and treat t.max == Integer.MAX_VALUE as "everything above is covered", for example by setting maxi = Integer.MAX_VALUE, which also skips the tail arc.

Trade-offs

Same effect without a long, but one more special case to read. Not run.

Reject labels above Character.MAX_CODE_POINT (fix C)

Validate the upper bound in makeCharRange and addTransition.

Trade-offs

A larger behaviour change: it breaks TestRegExpParsing's expected automata and any application that uses Integer.MAX_VALUE as an open upper end, and it adds a check to every arc that is built. Not run.

Downstream note

Downstream code that builds its own automata with Integer.MAX_VALUE as an open upper end and subtracts them with complement or minus gets silently wrong languages; automata built from regex strings are not affected.

How it was found

A proof-obligation audit of Operations.complement's contract: for every legal input the result must be deterministic and accept exactly the words the input rejects. The obligation fails at t.max + 1 in totalize for an arc ending at Integer.MAX_VALUE; a public-API JUnit test then witnessed the wrong language.

The method in full108 words

Method: semi-formal (a proof-obligation audit of a class's contract, witnessed by an executable repro).

The finder checked complement against its javadoc promise and totalize against its own ("from every state and every label there is a transition", with no overlap), over the full int label range that makeCharRange and addTransition accept, and found that t.max + 1 can wrap.
The finder then wrote a public-API JUnit test, a probe that prints the complement's arcs, and the long-maxi fix that makes them pass.
An independent reproducer, an executed cross-model review, a devil's-advocate verifier and an adjudication reproduced it with their own tests ("Prior reports, history and checks").

Prior reports, history and checks

Prior reports

No prior report found in apache/lucene issues, PRs and commits (incl. the JIRA archive), the mailing lists, downstream trackers or the web (searched 2026-11-03). Nearest: #15763 and #15755, which deprecated complement and minus for cost reasons without mentioning the wrap.

Searches3 searches

No matching public report was found in the documented searches. Nearest items, none a report of this bug: #15763 and #15755 (deprecate complement and minus, cost rationale; the Integer.MAX_VALUE there is the determinize work limit, not a label), #14193 (complementing a character class via totalize), #6814 (LUCENE-5752, moved totalize unchanged), #13706 / #13707 (isTotal), #14211 / #14212 (reverse() non-deterministic dead states, another method), #513 (LUCENE-10010, added the Integer.MAX_VALUE expected automata), #6094 (LUCENE-5030, context for the label-domain objection) and elastic/elasticsearch#158570 (cost of complement and totalize). Limits: keyword search; private or unindexed discussion is not covered.

What was searched, when, and what turned up
Where	When	How	Found
GitHub issues, PRs and commits (apache/lucene incl. the migrated JIRA archive)	2026-11-03; re-checked the same day	two scripted prior-report searches (32 issue/PR and 6 commit queries, 615 + 836 hits, every high- and medium-overlap hit read), 37 manual searches (totalize, `t.max + 1`, complement/minus/makeCharRange with MAX_VALUE, overflow, not deterministic, dead state), 7 extra JIRA queries	no report; the nearest items are listed above
Open and recent PRs	2026-11-03	the changed files of all 409 open apache/lucene PRs and of the 27 open PRs updated since 2026-11-01	none touches `Operations.java` or `Automata.java`
Mailing lists, downstream, web	2026-11-03	40 queries over dev@, java-user@, issues@ and commits@; Elasticsearch, OpenSearch, Solr and Lucene.NET trackers; 5 web queries incl. the original dk.brics library	nothing about this bug (dk.brics uses `char` labels, where `max + 1` cannot wrap)

History

Introduced in 2010 by LUCENE-2265 (5b74a4ec611), which widened automaton labels from char to int but kept t.max + 1 in totalize. First released in 4.0.0-alpha; present through 10.6.0 and main. Not fixed upstream.

Versions tested8 rows

Introduced by 5b74a4ec611 (2010-05-03, svn r940671), LUCENE-2265 (now #3341; commit message "cutover Fuzzy, Wildcard, Regexp queries to operate on Unicode UTF32 code point not UTF16 code units"; a patch by Robert Muir and Michael McCandless, committed by Michael McCandless). It widened transition labels and makeCharRange to int and kept if (t.max + 1 > maxi) maxi = t.max + 1; from the char-label totalize (b679816a700, 2010-04-06), where the sum is at most 65536. LUCENE-5752 (#6814, 6ac082fbe1d, 2014, first in 4.10.0) moved totalize into Operations unchanged.

In 4.0 to 4.9 the overlapping arc is always there, but whether the repro's check sees it depends on identity hash codes: those versions intersect with a singleton by following the first matching arc, whose order follows HashSet iteration. From 4.10.0 on, intersection is a product construction and the check fails every time. Upstream main 1c2072f0284 (2026-11-02) still has the line at Operations.java:1333.

Versions and branches executed, with results
Version or commit	Verdict	Result
main `5adff78bb168`	affected	gradle: fails with assertions on and off; passes with fix A
9.12.3, 10.6.0	affected	the JUnit test fails, assertions on and off
10.5.2	independent test	the complement accepts `"b"` for `makeCharRange('b', Integer.MAX_VALUE)`
4.10.0, 4.10.4, 8.11.4	older-API form	fails with assertions on and off; `isDeterministic()` false
4.0.0-alpha, 4.0.0, 4.9.1	older-API form	the overlapping arc is always present; the check passes or fails with identity hash codes (4.9.1: fails with assertions off)
commit `5b74a4ec611`	introducing	overlapping arc into the accepting dead state in 40 of 40 launches
commit `a3da4421208`	parent, char labels	passes 20 of 20 with assertions on and 20 of 20 off
3.6.2	API absent	compile error: no automaton package

Independent checks

A finder, an independent reproducer, an executed cross-model review (OpenAI GPT-5.6: reproduced, but not real on label-domain grounds, medium), a devil's-advocate verifier, an adjudication (confirmed, Low) and a final repro check reproduced it. This doc's gradle runs reproduced it on main and validated fix A.

Checks and verdicts257 words

The cross-model review ran on the older main ea57360912ed, where Operations.java is byte-identical to 5adff78bb168; its test was then re-run on 5adff78bb168 (4 tests, 2 failures, assertions off). Every other check ran on 5adff78bb168 or release jars.

Each independent check and its verdict
Check	Verdict	What it found
finder	reproduced	The JUnit test fails on main (assertions on and off), 10.6.0 and 9.12.3; the probe prints the two overlapping arcs and `isDeterministic=false`; the fix passes it and 86 tests of `TestOperations` and `TestRegExpParsing`.
independent reproducer	real	Own test (runs the determinized complement as a `CharacterRunAutomaton`: it accepts `"b"`) fails on main (on, off), 10.6.0, 10.5.2 and 9.12.3; controls at `0x10FFFF`, `0x110000` and `Integer.MAX_VALUE - 1` are correct; passes with the fix.
cross-model review, refute lens (OpenAI GPT-5.6, executed)	not real (medium)	Reproduced it (own test: 2 of 4 fail on main), agreed with the root cause, and the fix passes its tests; refuted only on the label-domain argument (see "Why it looks unintended").
devil's-advocate verifier	real	The complement of `TestRegExpParsing`'s own `[^c]` expected automaton accepts `"e"`; four "intended" defences (alphabet, deprecation, reach, upstream discussion) tried and rejected.
adjudication, separate re-runs, credibility audit and final repro check	confirmed (medium), Low	Re-runs on main fail with assertions on and off and pass with the fix; one minimal deterministic test.
this doc	reproduced; fix A validated	Gradle without the fix fails (on, off); with it, core's `util.automaton` package runs 239 tests, 0 failures (2 skipped).

Diagram file

The diagram as a still image, generated with AI and checked against the code. It is under 10 MB, the limit for a GitHub attachment.

PNG 477 KB

Sources and provenance

Finding record, Lucene and upstream sources, repro files and diagram notes1,610 words

Finding record

LFV-1167, snapshot of 2026-11-06

Registry title: Operations.complement and minus give a wrong, non-deterministic result for an automaton with an arc ending at Integer.MAX_VALUE, because totalize computes t.max + 1 in int and the wrap adds a dead-state arc that overlaps the real arc
Area: util / automaton (Operations.totalize, used by Operations.complement and Operations.minus)
Priority: Low, rank 919: Operations.complement and minus silently return a wrong, non-deterministic automaton for an input with an arc ending at exactly Integer.MAX_VALUE, in every release since 4.0.0-alpha. Only hand-built automata with that open upper end are hit, RegExp cannot produce one and the methods are deprecated for removal on main, so it is Low.
Impact class: minor
Impact note: Only application code that calls Operations.complement or Operations.minus (plain public API in every release through 10.6.0, @Deprecated for removal in Lucene 12 on main and branch_11x) or the test framework's AutomatonTestUtil.minus, on an automaton it built itself with an arc ending at exactly Integer.MAX_VALUE (for example makeCharRange(min, Integer.MAX_VALUE) as an open upper end, an idiom upstream's own TestRegExpParsing uses), is hit: the result silently accepts words of the input and reports isDeterministic() false, with -ea and -da and no scale; RegExp, the only in-tree production caller of complement, bounds every range by Character.MAX_CODE_POINT and cannot reach it, and arcs ending at 0x10FFFF, 0x110000 or Integer.MAX_VALUE - 1 are handled correctly; every release from 4.0.0-alpha to 10.6.0 and main.
Summary: You build Automata.makeCharRange('a', Integer.MAX_VALUE), which accepts every one-code-point word from "a" upward, and take its complement with Operations.complement; you expect a deterministic automaton (as the javadoc promises) that rejects "a". Instead the complement accepts "a" and is not deterministic, with no error: totalize, which complement uses to send every missing label to a dead state, computes t.max + 1 in int, the sum wraps to Integer.MIN_VALUE, so it also adds a dead-state arc over the whole code-point range on top of the real arc, and that dead state becomes accepting in the complement. Operations.minus, which subtracts through complement, likewise keeps words it should remove.
Introduced: 5b74a4ec611dd83f1a8214fc5258923c74d828d1 (trunk, svn r940671, 'LUCENE-2265: cutover Fuzzy, Wildcard, Regexp queries to operate on Unicode UTF32 code point not UTF16 code units'; a JIRA patch, no pull request; the issue is now apache/lucene#3341; patch by @rmuir, finished with and committed by @mikemccand) [read: git log -S 't.max + 1 > maxi' in the history clone; the parent a3da4421208 still has char labels] [exec: the parent passes 20 of 20 runs (-ea, -da) with the largest char label, Character.MAX_VALUE; 5b74a4ec611 has the overlapping arc into the accepting dead state in 40 of 40 launches]. It widened transition labels and makeCharRange to int and kept the line if (t.max + 1 > maxi) maxi = t.max + 1; from the char-label totalize (b679816a700, LUCENE-2370 flex reintegration, 2010-04-06), where t.max + 1 is at most 65536 and cannot wrap. LUCENE-5752 (#6814; 6ac082fbe1d, 2014-06-17, first in 4.10.0) moved totalize into Operations unchanged (2010-05-03 (author date = commit date of 5b74a4ec611, 2010-05-03T23:23:57Z))
First affected version: 4.0.0-alpha [exec: the complement's initial state has two arcs holding 'a', one into the accepting dead state, in 10 of 10 launches; the repro's own singleton-intersection check still passes there (5 of 5, -ea and -da), because 4.0-4.9 intersect a singleton by stepping the first matching arc, whose order follows identity hash codes]; the repro's check first fails deterministically in 4.10.0 [exec, -ea and -da]; 3.6.2 and earlier have no automaton package [exec: compile error]
Affected versions: every release from 4.0.0-alpha through 10.6.0, and main 5adff78bb168 [read: 5b74a4ec611 is in all 124 release tags 4.0.0-alpha..10.6.0 of the history clone, which lacks the 8.9-8.11.x tags; totalize is byte-identical between the clone's head 7cecf795236 and 5adff78bb168] [exec: the finder's one-test JUnit fails with -ea and -da on main and 10.6.0, and on 9.12.3; a main() form of the same check fails with -ea and -da on 4.10.0, 4.10.4 and 8.11.4 (all with isDeterministic() false); in 4.0.0-alpha to 4.9.x the overlapping arc is always present but the check's outcome depends on identity hash codes (passes on 4.0.0-alpha and 4.0.0, fails on 4.9.1 with -da and passes with -ea, flips with -XX:hashCode); the independent reproduction's own JUnit fails on main (-ea, -da), 10.6.0, 10.5.2 and 9.12.3; the intended-behaviour check's probe on main (-ea, -da) and 10.6.0]; not fixed upstream (main tip 1c2072f0284, 2026-11-02, still has if (t.max + 1 > maxi) at Operations.java:1333; last commit on the file 54283150a81, #16255, author and commit date 2026-06-14). complement and minus are not deprecated in 10.6.0 or any earlier release; they are @Deprecated ('will be removed in Lucene 12') only on main and branch_11x, by #15763 and #15755 (author date 2026-02-23). Not new in 10.6. All runs used JDK 25 on one aarch64 Linux host
Status: documented (brief, checks and a per-finding doc exist)
Verification: Confirmed by AI-run checks: an independent repro, a cross-model review that disputed it (the adjudication ruled it real), an intended-behaviour check, a prior-report search and a skeptical audit; not yet triaged by a person.
Found by: semi-formal: proof-obligation audit
Upstream and prior reports: none found (2026-11-03: a scripted prior-report search in two phrasings (32 apache/lucene issue/PR queries, 6 commit queries, 4 downstream-repo queries over Elasticsearch, OpenSearch and Solr, 40 queries over the dev@, java-user@, issues@ and commits@ lists, 8 JIRA-archive queries; 615 + 836 hits, every high- and medium-overlap hit read); 37 manual GitHub searches including Lucene.NET and items created or updated since 2026-10-30; the changed files of all 409 open apache/lucene PRs (none touches util/automaton/Operations.java); 7 extra JQL queries; 5 web queries including the original dk.brics library; the finder's, the independent reproduction's, the intended-behaviour check's and the adjudication's searches agree). Re-checked 2026-11-03: 'totalize' still matches only #14193 and #6814, '"Operations.complement"' only #15763 and #13732, no issue or PR mentioning complement or Operations.minus was updated since 2026-11-01 or 2026-10-31, 'makeCharRange "MAX_VALUE"' and '"Integer.MAX_VALUE" automaton created since 2026-10-31' have 0 hits, the only automaton PRs updated since then (#16801, #16564) do not touch Operations.java, none of the 27 open PRs updated since 2026-11-01 changes Operations.java or Automata.java, and upstream main 1c2072f0284 still computes t.max + 1 in int at Operations.java:1333. Nearest items, none of them this bug: #15763 and #15755 (2026-02-23, deprecate complement and minus for removal in Lucene 12, cost rationale only; the Integer.MAX_VALUE there is the determinize work limit, not a label), #14193 (complement of a character class as 'totalize() to one dead state'), #6814 (LUCENE-5752, moved totalize unchanged), #13706 and #13707 (isTotal), #14211 and #14212 (reverse() non-deterministic dead states, other method), #513 (LUCENE-10010, added the TestRegExpParsing expected automata that use makeCharRange('d', Integer.MAX_VALUE)), #6094 (LUCENE-5030, context: a special label must be a valid Unicode char for UTF32ToUTF8), elastic/elasticsearch#158570 (open, charges complement/totalize cost to a circuit breaker; cost only)
Lucene commit tested: main 5adff78bb168 (12.0.0-SNAPSHOT), OpenJDK 25.0.3 on Linux aarch64: this doc's gradle runs (the repro without the fix, assertions on and off: fail; with fix A: pass; core's util.automaton test package with fix A: 239 tests, 0 failures, 2 skipped) and the hunt's runs; release jars 9.12.3 and 10.6.0 (the same test fails, assertions on and off) and 10.5.2 (an equivalent test fails); main() forms of the same check on 4.0.0-alpha, 4.0.0, 4.9.1, 4.10.0, 4.10.4 and 8.11.4; commits a3da4421208 (clean) and 5b74a4ec611 (introducing). The cross-model review ran on ea57360912ed, whose Operations.java is byte-identical to 5adff78bb168, and was re-run on 5adff78bb168.

Lucene and upstream sources

Finding record: lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java:337-357 (at 5adff78bb168) (complement javadoc 'Returns a (deterministic) automaton that accepts the complement of the language of the given automaton', @Deprecated on main; totalize(determinize(a)) then flips every accept bit), :359-384 (minus = intersection(a1, complement(a2)), same promise), :1307-1345 (totalize: int maxi at :1325, gap arc to the dead state at :1330-1332, 'if (t.max + 1 > maxi) maxi = t.max + 1;' at :1333-1335, tail arc [maxi, MAX_CODE_POINT] at :1338-1340)
lucene/core/src/java/org/apache/lucene/util/automaton/Automata.java:136-151 (at 5adff78bb168) (makeCharRange(int, int): 'accepts a single codepoint whose value is in the given interval', no upper-bound check)
lucene/core/src/java/org/apache/lucene/util/automaton/RegExp.java:676-681 (at 5adff78bb168) (REGEXP_COMPLEMENT, the only in-tree production caller of complement; negated character classes only)
lucene/core/src/java/org/apache/lucene/util/automaton/package-info.java:33 (at 5adff78bb168) ('DFA/NFA implementation with Unicode alphabet', the cross-model review's label-domain argument)
lucene/core/src/test/org/apache/lucene/util/automaton/TestRegExpParsing.java:190-194 (at 5adff78bb168) and :240-244 (expected automata for [^c] and [^b-d] built with makeCharRange(..., Integer.MAX_VALUE))
lucene/test-framework/src/java/org/apache/lucene/tests/util/automaton/AutomatonTestUtil.java:74 (at 5adff78bb168) (AutomatonTestUtil.minus calls Operations.complement)
The finding in 30 seconds: lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java:337-357 (at 5adff78bb168) (complement), :359-384 (minus), :1308-1345 (totalize; int maxi :1325, gap arc :1330-1332, t.max + 1 :1333-1335, tail arc :1338-1340)
lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java:162-165 (at 5adff78bb168) (addTransition finishes the previous state when a new source state starts), :300-305 (finishCurrentState clears deterministic on overlapping arcs)
lucene/core/src/java/org/apache/lucene/util/automaton/Automata.java:136-151 (at 5adff78bb168) (makeCharRange, no upper-bound check)
Who is affected: lucene/core/src/java/org/apache/lucene/util/automaton/RegExp.java:676-681 (at 5adff78bb168) (REGEXP_COMPLEMENT, negated character classes only)
lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java:346-349, (at 5adff78bb168) :372-375 (@Deprecated on main)
lucene/core/src/java/org/apache/lucene/util/automaton/RunAutomaton.java:63-64 (at 5adff78bb168)
lucene/test-framework/src/java/org/apache/lucene/tests/util/automaton/AutomatonTestUtil.java:74 (at 5adff78bb168)
a Lucene clone releases/lucene/10.6.0 Operations.java:359, :382 (complement and minus without @Deprecated)
lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java:56 (at 5adff78bb168) (@lucene.experimental; the same in releases/lucene/10.6.0)
Why it looks unintended: lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java:338-339, (at 5adff78bb168) :360-362, :1309-1310
lucene/core/src/java/org/apache/lucene/util/automaton/Automata.java:136-151 (at 5adff78bb168)
lucene/core/src/java/org/apache/lucene/util/automaton/package-info.java:33 (at 5adff78bb168) ('Unicode alphabet')
lucene/core/src/test/org/apache/lucene/util/automaton/TestRegExpParsing.java:174-195, (at 5adff78bb168) :224-245
lucene/test-framework/src/java/org/apache/lucene/tests/util/automaton/AutomatonTestUtil.java:681-686 (at 5adff78bb168)
lucene/core/src/test/org/apache/lucene/util/automaton/TestRegExpParsing.java:832-840 (at 5adff78bb168) (assertSameLanguage via AutomatonTestUtil.sameLanguage); lucene/core/src/java/org/apache/lucene/util/automaton/Automata.java:104-106 (makeAnyChar = [MIN_CODE_POINT, MAX_CODE_POINT]); RegExp.java:1379, :1399, :1423 (ranges end at MAX_CODE_POINT)
Suggested fix: a Lucene clone releases/lucene/10.6.0 lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java:1330-1363 (totalize byte-identical to main)
Diagrams: lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java:1325-1340, (at 5adff78bb168) :352-355

Other statements trace to the hunt's working files (models, logs, reviews and briefs), which are not published.

Repro files

TestComplementOfRangeEndingAtMaxValue.java (lucene/core, package org.apache.lucene.util.automaton, 1 test): repro/LFV-1167/TestComplementOfRangeEndingAtMaxValue.java (31 lines)

About the diagrams

The diagram illustrates the repro's automaton (one arc, [97, 2147483647]), the arcs totalize adds at Operations.java:1330-1340, and the accept-bit flip at :352-355.

assets/LFV-1167/bug.png (477 KB)

Built 2026-11-06 from the hunt's record of this finding and its doc file. Lucene main under test in this hunt: ea57360912ed. Every listed finding was re-run on Lucene main e1faeba08bde on 2026-11-02.

The finding in 30 seconds

Background: automaton arcs and how complement works

The finding, step by step

Who is affected

The mechanism (main 5adff78bb168, lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java)

The numbers

Minimal repro

Environment

Observed output

Why it looks unintended

Suggested fix

Keep maxi as a long (fix A) (validated by the checks) (recommended)

Saturate instead of widening (fix B)

Reject labels above Character.MAX_CODE_POINT (fix C)

Downstream note

How it was found

Prior reports, history and checks

Prior reports

History

Independent checks

Diagram file

Sources and provenance

Finding record

Lucene and upstream sources

Repro files

About the diagrams

The mechanism (main `5adff78bb168`, `lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java`)