matchhighlight PassageFormatter closes crossing highlights in the wrong order, so per-highlight end tags cross

PassageFormatter, the matchhighlight package's passage formatter, takes the start and end strings either as constants or as functions of each highlight (PassageFormatter(String, Function<OffsetRange,String>, Function<OffsetRange,String>)). When two highlights in a passage overlap without one containing the other, it keeps the output nested: where the first one ends, it closes the second, closes the first and re-opens the second. It closes them in the wrong order, outer first, so foo bar baz with [0,7) as <a> and [4,11) as <b> comes out <a>foo <b>bar</a></b><b> baz</b> instead of <a>foo <b>bar</b></a><b> baz</b>, which an XML parser rejects.

The text, the highlighted characters and the balance of start and end strings are right; only the order of the end strings where highlights cross is wrong (two in this example; a chain of three crossing highlights puts three in opening order). With one shared end string, which every Lucene caller and test uses, both orders print the same bytes, so Lucene's own callers and tests cannot show the defect, and have not since the class was added in 9.0.0. A one-line change, closing from the top of the stack down, fixes it and leaves shared-end-string output byte-identical.

1. format(StringBuilder, CharSequence, Passage) (:110-135) handles 0 and 1 markers inline and sends 2 or more to multipleMarkers ("Multiple markers, possibly overlapping or nested.", :127-131).
2. slicePoints (:175-201) makes a START and an END point per marker, sorted by offset; at one offset ends come before starts (END(1), START(2), :204-206), "Longer start slice points come first" (:190) and "Shorter end slice points come first" (:193): the inner marker ends first.
3. multipleMarkers (:138-173) keeps markerStack, the open markers in opening order. START (:147-150) pushes the marker and appends its start string. END (:152-161):

int markerIndex = markerStack.lastIndexOf(currentMarker);          // :153
for (int k = markerIndex; k < markerStack.size(); k++) {           // :154  bottom-up: outer first
  b.append(markerEnd.apply(markerStack.get(k)));
}
markerStack.remove(markerIndex);                                   // :157
for (int k = markerIndex; k < markerStack.size(); k++) {           // :158  re-open, bottom-up (correct)
  b.append(markerStart.apply(markerStack.get(k)));
}

The markers above markerIndex were opened after the ending marker and are still open: they sit above it on the stack ([4,11) starts inside [0,7) but is not contained in it). Closing and re-opening them keeps the output nested only if they are closed top of the stack down. The re-open loop correctly runs bottom-up; the close loop runs bottom-up as well, and that is the bug.

Result: <a>foo <b>bar</a></b><b> baz</b>; with the fix <a>foo <b>bar</b></a><b> baz</b>.

• Only for crossing markers: a nested marker is on top of the stack when it ends, so the close loop runs once. Longer crossing chains put more end strings out of order: abcdefghi with [0,5) as <a>, [2,7) as <b> and [4,9) as <c> gives <a>ab<b>cd<c>e</a></b></c><b><c>fg</b></c><c>hi</c>, three end strings in opening order at offset 5; with the fix <a>ab<b>cd<c>e</c></b></a><b><c>fg</c></b><c>hi</c> (executed, assertions on and off).
• Only when end strings differ: the String constructor (:42-44) maps every marker to the same end string, and the same strings in another order are the same bytes. With a shared <m>/</m> the crossing case prints <m>foo <m>bar</m></m><m> baz</m>, well nested and identical with the fix (executed).

• Who. Users of PassageFormatter(String, Function<OffsetRange,String>, Function<OffsetRange,String>) (PassageFormatter.java:46-53) whose end strings differ per marker, for example <q1>/<q2> or <em>/<strong> per query, the use case LUCENE-9461 (#10501) names: "there can be more than one query at one time and they should highlight the same content (with different colors)". Paths: a direct PassageFormatter.format call, or MatchHighlighter with FieldValueHighlighters.highlighted(maxPassageWindow, maxPassages, passageFormatter, matchFields) (FieldValueHighlighters.java:91-115), where the application supplies the formatter.
• Opt-in, not default. The String constructor and every in-tree caller share one end string (FieldValueHighlighters.java:59 uses ""; the tests use ">"/"<" or "<span>"/"</span>"). The upstream per-query example varies only the start string and shares "</span>" (TestMatchHighlighter.java:734-742).
• Trigger. Two matches in one passage that overlap without nesting. No index size, codec, analyzer setting or concurrency is involved; it is deterministic and the same with assertions on and off.
• Effect (a probe of 95,919 random passages with 2-5 markers, main with assertions on and off and 10.5.2): the buggy and the fixed output have the same characters and length in every case and differ in order in 37,680. A strict XML parser rejects all 37,680; the fixed output is always well formed. With inline highlight tags (four sweeps, 76,744 of the passages), HTML parsing (jsoup's HTML parser; no browser run) recovers the intended highlighting when every marker has its own tag name (0 differences in 19,215 passages); with one tag per query, where several markers share a tag name, part of one highlight is lost in 135 of 19,205 (em/mark) and 309 of 19,132 (mark/span) passages, and in none of 19,192 (b/i). With these inline tags a highlight is never added and the text never changes. A fifth sweep with block-level tags (div, p) as markers, not a realistic highlight setup (19,175 passages), loses labels in both outputs (buggy 4,089, fixed 3,983); only the buggy output also gains labels (1,798) and has its parsed text moved (3).
• Reach. GitHub code search (best effort) found no use of the matchhighlight package in Solr, Elasticsearch or OpenSearch. #16820 (2026-10-12) proposes deprecating the classic and fast-vector highlighters and points users to "the matches highlighter components" for bespoke needs.

The test sits in org.apache.lucene.search.matchhighlight by upstream convention and uses only public API (PassageFormatter, Passage, OffsetRange); the marker functions pick the tag from the range's start offset. The same test is the suggested regression test: it passes with the fix and passes the highlighter lint checks as written.

Not asserted here (shown by the verification runs): the end-to-end MatchHighlighter case with two phrase queries, the XML parser's rejection, that the text is preserved, and that a shared end string hides the order.

# stock main 645d4fe14a20, gradle, seed DEADBEEF (identical with -Ptests.asserts=false); abridged
TestPassageFormatterCrossingMarkers > testCrossingMarkersCloseInnermostFirst FAILED
    org.junit.ComparisonFailure: expected:<<a>foo <b>bar</[b></a]><b> baz</b>> but was:<<a>foo <b>bar</[a></b]><b> baz</b>>
        ...
        at app//org.apache.lucene.search.matchhighlight.TestPassageFormatterCrossingMarkers.testCrossingMarkersCloseInnermostFirst(TestPassageFormatterCrossingMarkers.java:31)
BUILD FAILED

# 10.6.0 release jars, standalone JUnit run, assertions on and off: the same ComparisonFailure

# with the fix (asserts true and false)
:lucene:highlighter:test (SUCCESS): 1 test
BUILD SUCCESSFUL

• The API invites per-marker end strings. PassageFormatter(String, Function<OffsetRange, String> markerStart, Function<OffsetRange, String> markerEnd) (PassageFormatter.java:46-53), present since the class was added (150a8dacb59), with no restriction anywhere that end strings be equal.
• Crossing markers are legal input. Passage.java:23-24: "The markers can be overlapping or nested, but they're always contained within the passage." PassageFormatter.java:128: "Multiple markers, possibly overlapping or nested."; :137: "Handle multiple markers, possibly overlapping or nested."
• The class resolves overlaps. PassageFormatter.java:29-33: "Formats a collection of passages over a given string, cleaning up and resolving restrictions concerning overlaps, ..."; "Passages are demarcated with constructor-provided ellipsis and start/end marker sequences."
• The design is nesting. The re-open loop runs bottom-up, the order that keeps nesting, and the slice-point comparator puts the inner marker's end first when two ends fall on one offset ("Shorter end slice points come first", :193). TestPassageSelector#checkOddOverlaps (TestPassageSelector.java:64-72) pins the close-and-re-open shape, foo >bar >baz<<> abc< xyz, with one shared end string, so it cannot see the order.
• Stated intent. The class's author wrote on LUCENE-9439 (#10479, 2020-07-31) that hit ranges go to the "passage selector and a simple test-only formatter - these clean up potential overlaps and nesting problems (which is useful for HTML, for example)", with constant >/< markers. LUCENE-9461 (#10501) asks for several queries highlighting the same content "with different colors".
• History. No issue, PR, test or CHANGES entry records the order as intended, and the loop has not changed since it was written.

Strongest case (a cross-model refute review and an intended-behaviour devil's advocate): no sentence promises well-nested output; the marker strings are opaque; MatchHighlighter calls itself "An example highlighter" (MatchHighlighter.java:38); and every in-tree caller and test shares one end string, so the order cannot be observed in documented usage. A committer could call per-marker end strings over crossing markers unspecified.

Why it fails: the per-marker Function constructor exists to vary the strings and says nothing against it; crossing markers are explicitly allowed; the close-and-re-open step only makes sense for nesting, and its own re-open loop and comparator follow the nesting order; and the fix changes nothing for users with one shared end string. No documented valid-HTML or XML guarantee exists; the case rests on the constructor, the Passage javadoc and the close-and-re-open design.

The first option is the recommended, validated fix. The other two (document the restriction; remove crossings before formatting) are listed for completeness and were not run.

In the END branch of multipleMarkers (PassageFormatter.java:154), run the close loop from markerStack.size() - 1 down to markerIndex. The re-open loop stays bottom-up. The comment line is optional.

         case END:
           int markerIndex = markerStack.lastIndexOf(currentMarker);
-          for (int k = markerIndex; k < markerStack.size(); k++) {
+          // Close the markers opened after this one first (innermost first), then this one.
+          for (int k = markerStack.size() - 1; k >= markerIndex; k--) {
             b.append(markerEnd.apply(markerStack.get(k)));
           }
           markerStack.remove(markerIndex);

Trade-offs

• None found for marker functions without side effects (every in-tree one, and every one in the probes). The same strings are appended the same number of times; only their order changes, and only where markers cross and end strings differ.
• Output with one shared end string, the String constructor and every in-tree use, is byte-identical, so no in-tree caller or test sees a change.
• The order in which markerEnd is called at a crossing changes too; only a stateful marker function could notice.
• The regression test's exact expected string pins this option's close-and-re-open shape; removing crossings before formatting would need a different expected string.

What the checks validated

• Scratch worktree of 645d4fe14a20, gradle --offline, seed DEADBEEF. Stock: the repro fails with -Ptests.asserts=true and false. With the fix: it passes with both.
• :lucene:highlighter:test --tests 'org.apache.lucene.search.matchhighlight.*' (TestMatchHighlighter, TestMatchRegionRetriever, TestPassageSelector and the repro): 49 tests, 0 failures, with asserts true and false.
• :lucene:highlighter:test, the whole module (35 suites, asserts true): 723 tests, 0 failures, 0 skipped.
• Lint (checkGoogleJavaFormat, ecjLintMain, ecjLintTest, forbiddenApisMain, forbiddenApisTest on the highlighter module, the repro test included): BUILD SUCCESSFUL.
• Earlier: a reference copy of the formatter with only this loop reversed had 0 nesting failures in 1,671,813 exhaustive calls (every ordered list of 1-3 markers on values up to 9 characters, constant, per-marker and per-query labels: chains of three crossing markers, shared starts and ends, identical ranges with different labels); the fixed output was well formed in all 95,919 passages of the random probe.
• Edge cases on the real class (assertions on and off): the three-marker chain [0,5), [2,7), [4,9) comes out well nested with the fix; two identical ranges with different labels are well nested stock and fixed, and with a third range crossing them only this bug shows, which the fix nests.
• Not run: the module with asserts false, other modules, x86.

State in the javadoc that crossing markers come out with crossed end strings unless all end strings are equal.

Trade-offs

• No behaviour change, but per-marker end strings stay unusable for overlapping matches, the use case LUCENE-9461 names, and the close-and-re-open step keeps doing work that no longer achieves anything.

Merge crossing markers, as LUCENE-8446 (#9492) did for the unified highlighter's DefaultPassageFormatter, or emit non-overlapping fragments, the (AAA)(C)(BBB) shape Dawid Weiss sketched on LUCENE-8401 (#9448, 2018).

Trade-offs

• A larger change: it would also change the output for constant markers, whose close-and-re-open shape TestPassageSelector#checkOddOverlaps pins, and merging into today's single-range markers loses which query matched the overlap unless the merged marker keeps both.

• Method. Bounded-exhaustive translation validation of the real formatter on the stock jars: every passage of a value of up to 10 characters and every ordered list of 1-3 markers inside it (overlapping, nested, duplicate), under three label schemes (constant strings, one label per marker, one label per query). Five relations were checked against an exact reference: F1 stripping the markers gives the passage text, F2 every end string closes the most recently opened still-open marker, F3 the open labels at each character equal the markers covering it, F4 (soft) no empty element, F5 nothing left open.
• Result. At length up to 10, 3,685,968 calls (three label schemes, 1,228,656 each): F1, F3 and F5 never failed; F2 failed 500,214 times (one label per marker) and 369,226 times (one label per query). A copy of the formatter with only the close loop reversed had 0 F2 failures in 1,671,813 calls (length up to 9), which shows both that the check can pass and that the one-line fix is enough for nesting. An end-to-end tier (1,641 documents x 21 queries through MatchHighlighter) showed the same nesting failure in 168,206 and 159,602 passages (position gap 0 and 1), over 5,684,424 highlighted document results each.
• Origin. The close order was first suspected by reading the code while writing the reference; the exhaustive check then witnessed it. The hunt classes this as semi-formal.
• Reduction. The hunt reduced it to a deterministic public-API JUnit (2026-10-26); the minimal-repro step cut that to the one-method test shown here (2026-10-29).