DirectoryTaxonomyWriter gives a facet label with an unpaired surrogate a second ordinal once its cache is refilled from the index

A facet label can contain an unpaired surrogate, for example a tag cut by String.substring in the middle of an emoji ("x😀".substring(0, 2) is "x\uD83D"). The taxonomy index stores each category as UTF-8, and UTF-8 encoding replaces the unpaired surrogate with U+FFFD, as IndexWriter.addDocument documents. DirectoryTaxonomyWriter's cache, however, compares the label's Java strings. When a writer session fills its cache from the index (by default after 11 cache misses), the cached key is the stored form x�, the original x\uD83D misses, and because the cache now counts as complete the writer indexes the label again: ordinal 14 instead of 2. commit() persists two category documents for one taxonomy term, facet counts for the value split into two entries with the same label, label lookups see only the first copy, every later session can add one more copy, and once both copies sit in one taxonomy segment (after later sessions merge the taxonomy's segments, or when both are made in one session) a TaxonomyMergeUtils.merge drops the value from documents on the duplicate (or throws EOFException with DiskOrdinalMap). CheckIndex calls the taxonomy clean. It affects the default configuration in 9.5.0 to 10.5.2 and main (and 3.4.0 to 7.0.1); from 9.5.0 the cross-session case needs a taxonomy that fits in the 4,000-entry cache. Labels with neither an unpaired surrogate nor U+FFFD are never affected; a well-formed label containing U+FFFD can get a second ordinal only when an ill-formed label with the same stored form is also added.

• Taxonomy and ordinal. Taxonomy facets store each label, such as dim/v0, once in a side index, as one document whose doc ID is the label's ordinal; main-index documents store ordinals, and counts are kept per ordinal. Categories are never deleted (TaxonomyReader.java:33-35).
• Unpaired surrogate. Java strings are UTF-16; an emoji such as 😀 (U+1F600) takes two chars, a surrogate pair. Cutting by char count can keep only the first half: "x😀".substring(0, 2) is "x\uD83D". UTF-8 has no encoding for a lone half, so Lucene writes U+FFFD (bytes EF BF BD) instead: "the invalid characters are silently replaced with the Unicode replacement character U+FFFD" (IndexWriter.java:1483-1485; UnicodeUtil.java:231-235).
• Writer cache. DirectoryTaxonomyWriter remembers label -> ordinal in a cache, by default LruTaxonomyWriterCache(4000) keyed by the FacetLabel, whose equals compares Java strings (DirectoryTaxonomyWriter.java:89, :273-276; NameIntCacheLRU.java:71-74; FacetLabel.java:122-139).

1. addCategory asks the cache first (DirectoryTaxonomyWriter.java:385); on a miss findCategory either trusts the cache, when it counts as complete (:326-329), or looks the label up in the index by its UTF-8 term (:354-357).
2. In a reopened taxonomy the cache starts empty and incomplete. After cacheMissesUntilFill = 11 misses (:101, :331), perhapsFillCache reads every term into the cache under new FacetLabel(FacetsConfig.stringToPath(t.utf8ToString())), the U+FFFD form (:633), and sets cacheIsComplete = !aborted (:652); it aborts only when the cache is full (:626, :640).
3. x\uD83D does not equal the cached x�, the complete cache answers "absent", and addCategoryDocument writes a second document for the same term (:397, :452-482), against the writer's own comment "Since we guarantee uniqueness of categories, each term has exactly one document" (:628-632).
4. A new taxonomy starts with a complete cache (:181-182), so in one fresh session x\uD83D, x� and x\uDE00 get ordinals 2, 3 and 4, while a reader resolves all three to 2 (DirectoryTaxonomyReader.java:299-306, the first document of the term). This holds while the cache stays complete: once a put evicts entries (at 4,000 by default), addToCache sets cacheIsComplete = false (:484-492) and later labels are looked up in the index again.
5. Readers list both copies as children (x� (1) twice); lookups of the duplicated path (getOrdinal, getSpecificValue, getTopChildren(dim, path)) see only the first copy, while a unique child's full path below the second copy still resolves; drill-down uses path terms and matches both documents.
6. addTaxonomy maps only the first document of each term per segment (DirectoryTaxonomyWriter.java:717-721), though OrdinalMap expects one mapping per document (:743-746). Once both copies share a taxonomy segment, MemoryOrdinalMap leaves the second at 0, the root (:770-784), so that document loses its value in the merged index; DiskOrdinalMap throws EOFException.

Default writer, cache and FacetsConfig; session 1 indexes dim/x\uD83D (ordinal 2) and dim/v0 to dim/v10 (3 to 13); session 2 indexes the same 12 values. After the 11th miss the cache holds all 14 categories and counts as complete; dim/x\uD83D then gets ordinal 14, the term dim + 1F 78 EF BF BD has documents 2 and 14, getTopChildren(100, "dim") gives value=24 childCount=13 with x� (1) twice, getSpecificValue("dim", "x\uD83D") is 1, drill-down matches 2 documents and CheckIndex reports the taxonomy clean. With the normalizing fix: ordinal 2, one entry x� (2). Same with assertions on and off.

• Who is exposed. Taxonomy-facet users with the default DirectoryTaxonomyWriter and cache (default IndexWriterConfig, codec and Directory) whose labels can keep an unpaired surrogate: a tag or category cut by char count inside an emoji, or a decoded JSON \uD83D escape (executed with one parser only, jackson-core 2.17.1, whose byte and char parsers both keep the lone \uD83D). Nothing in the facet API rejects such a label: FacetField.verifyLabel checks null and empty (FacetField.java:64-73), FacetLabel.checkComponents null, empty and length (FacetLabel.java:81-100).
• When. From 9.5.0: the same label again in a later writer session after 11 cache misses in that session (any 11 labels not yet cached), while the taxonomy fits in the 4,000-entry cache: with 11 or 3,990 filler labels (taxonomies of 14 and 3,993 categories before the re-add) the label is duplicated, with 4,100 or 20,000 (4,103 and 20,003 categories) it is not. Or two labels with the same stored form in a new taxonomy or after a fill, while the cache is complete. In 3.4.0 to 7.0.1 the default cache never reports full, so by code reading any taxonomy size is affected.
• Effect. Split and duplicated facet entries for the value; lookups of that label see only the first copy; one more copy per affected session (6 sessions gave 6 copies); once both copies sit in one taxonomy segment, TaxonomyMergeUtils merges drop the value from documents or throw EOFException (while they sit in different segments, a merge into a new taxonomy joins them). All of it is committed, and CheckIndex calls the taxonomy clean.
• Not affected. Labels with neither an unpaired surrogate nor U+FFFD: a bounded-exhaustive check of 66,822 short labels found that only the 58,080 ill-formed ones change on the way to the index and no two well-formed labels share a term. A well-formed label containing U+FFFD can still be hit next to an ill-formed label of the same stored form: in one session x\uD83D gets 2 and the well-formed x� gets 3, which the reader resolves to 2. Search hits and drill-down stay correct, and SortedSetDocValuesFacetField gives one entry for the same value across two sessions.
• Scale and likelihood. No scale needed (15 categories). Rare: every case needs a label with an unpaired surrogate; the same-label case also needs a later session after the fill and, from 9.5.0, a taxonomy that fits in the cache, while two different labels with one stored form collide even in one fresh session. No public report was found in the searches described below.
• Repair. Neither fix repairs existing duplicates; that takes rebuilding the taxonomy and re-indexing. Damage shows as two taxonomy ordinals with the same path.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: ordinal of the same label in a later session expected:<2> but was:<13>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:647)
       org.apache.lucene.facet.taxonomy.directory.TestTaxonomyUnpairedSurrogateLabel.testSameLabelKeepsOrdinalAfterCacheFill(TestTaxonomyUnpairedSurrogateLabel.java:38)

• Contract. TaxonomyWriter.java:52-53: "addCategory() adds a category with a given path name to the taxonomy, and returns its ordinal. If the category was already present in the taxonomy, its existing ordinal is returned." The writer-only test breaks it with one unchanged label.
• The writer's invariants. "Since we guarantee uniqueness of categories, each term has exactly one document" (DirectoryTaxonomyWriter.java:628-632); "if the term was found, we know it has exactly one document" (:366). The default LRU_STRING cache is "always correct" as opposed to LRU_HASHED, where a hash collision means "your document will get an incorrect facet" (LruTaxonomyWriterCache.java:28-41); that promise is about exact label keys, not about agreeing with the index's UTF-8 form.
• Core semantics. IndexWriter.java:1483-1485 documents that malformed surrogate pairs are accepted and stored as U+FFFD (LUCENE-510), and TestIndexWriterUnicode.testInvalidUTF16 asserts it. So the index's identity of such a label is its replaced form; taxonomy drill-down and SSDV facets already behave that way.
• Tests. TestTaxonomyCombined.testWriterTwice2 and testWriterTwice3 assert that re-added categories keep their ordinals across writer sessions and across the cache fill. Facet tests draw labels from generators that make only valid UTF-16, so no test uses an unpaired surrogate.
• History. 7.1.0 to 9.4.2 defaulted to UTF8TaxonomyWriterCache (LUCENE-7975), keyed by the same UTF-8 bytes as the index, and did not show the bug. #12093 / #12092 replaced it because of a ThreadLocal leak (#12000); neither discusses label identity. LUCENE-7891 (#8942), a cache-key bug that gave documents wrong facets, was fixed as a bug.

Strongest case (the devil's-advocate checker; a cross-model reviewer rated it moderate): a string with an unpaired surrogate is not Unicode text, BytesRef(CharSequence) says "This must be well-formed unicode text, with no unpaired surrogates" (BytesRef.java:74-79), FacetLabel is @lucene.internal and the writer @lucene.experimental, and in the review of PR #15900 (for the related #15899) one committer first called half surrogates from char truncation expected, something callers must be prepared for (the merged #15900, in 10.5.0, then added code-point truncation and deprecated the char-only constructor): garbage in, garbage out.

What to concede: Lucene could reasonably reject such labels, or only document that labels must be well-formed UTF-16; normalizing is one consistent choice, not the only one, and for the one-session pair (x\uD83D vs x�) merging them into one category is a policy choice. Why it fails as a defence of today's behaviour: the BytesRef precondition binds the writer's own internal call, while the user goes through the public FacetField API, which accepts the label; IndexWriter documents accepting such text; and the failure is self-inconsistent: the same unchanged label gets one ordinal or two depending only on whether a hidden cache heuristic has fired, and the writer breaks its own uniqueness invariant. Garbage in would justify an exception, not a silently duplicated category. Verdict: a defect.

Options A and B were built and validated with gradle in a scratch worktree; C and D were not run. Until a fix lands, applications can replace unpaired surrogates with U+FFFD (the form the index stores anyway) or reject such labels before building a FacetField, and truncate labels by code point rather than by char.

One file, DirectoryTaxonomyWriter.java: addCategory first maps the label through toIndexedForm, which copies the components only if one changes and replaces every unpaired surrogate by U+FFFD, exactly as UTF-8 encoding does. Cache and index then share one identity. The logic is the finder's sketch, with an explicit replacement instead of a round trip through BytesRef(CharSequence), whose javadoc forbids unpaired surrogates.

categoryPath = toIndexedForm(categoryPath); // in addCategory, right after ensureOpen()
private static String replaceUnpairedSurrogates(String s) {
  char[] chars = null;
  for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    if (Character.isHighSurrogate(c) && i + 1 < s.length() && Character.isLowSurrogate(s.charAt(i + 1))) {
      i++; // a well-formed pair
    } else if (Character.isSurrogate(c)) {
      if (chars == null) chars = s.toCharArray();
      chars[i] = (char) UnicodeUtil.UNI_REPLACEMENT_CHAR;
    }
  }
  return chars == null ? s : new String(chars);
}

Trade-offs

• Semantics: x\uD83D, x\uDE00 and x� become one category, as the reader, drill-down, SSDV facets and the 7.1.0 to 9.4.2 default cache already treat them; enrichOrdinalDocument receives the normalized label.
• Cost: an extra scan of the label's chars on every addCategory call, cache hits included; an allocation only for labels that change. Not benchmarked.
• Scope: a subclass that calls the protected findCategory with a raw label is not covered (it could normalize there too). Existing duplicates are not repaired.

What the checks validated

• Scratch worktree at a9779ef3c193, gradle, JDK 25: the new test fails 4 of 6 on stock and passes 6 of 6 with the fix, assertions on and off; with TestDirectoryTaxonomyWriter, TestTaxonomyCombined, TestAddTaxonomy, TestConcurrentFacetedIndexing and TestDirectoryTaxonomyReader: 66 tests, 0 failures (3 nightly tests skipped).
• The whole facet module: 40 suites, 312 tests (306 upstream + 6 new), 0 failures, assertions on (7 skipped) and off (8 skipped); :lucene:facet:check -x test (google-java-format, ecjLint, forbiddenApis) passes.
• Standalone runner with the patched class: the new test (on and off), the finder's JUnit (3 of 3), the independent reproducer's (5 of 5) and the follow-up's 13-test probe, merge cases included, pass.

Throw IllegalArgumentException in addCategory when a component has an unpaired surrogate (+23 lines in DirectoryTaxonomyWriter.java).

Trade-offs

A behaviour change: documents with such labels now fail in FacetsConfig.build, so applications that index them today must clean labels first. Matches BytesRef's precondition and the first view in the #15900 review (half surrogates from char truncation are the caller's concern). Rejecting in FacetField or FacetLabel instead would also hit SSDV facets and reader-side lookups, which work today (not run).

What the checks validated

The new test passes 6 of 6, the 66 closest-suite tests and the whole facet module (312 tests, assertions on) pass, and check -x test passes. The finder's JUnit fails 1 of 3 with it: its facet test does not expect the exception.

Normalize inside the LRU cache's key (for example NameIntCacheLRU.key). Not run.

Trade-offs

Fixes only the built-in cache; a custom TaxonomyWriterCache would still disagree with the index.

Map each document of a term to the new ordinal (DirectoryTaxonomyWriter.java:717-721), so merging a damaged taxonomy repairs it instead of dropping values or throwing EOFException. Not run.

Trade-offs

Does not prevent the duplicate; helps taxonomies already damaged.

Method: code reading, then a bounded-exhaustive check (the study's "non-formal" tier), in a hunt unit on concurrent adds to the taxonomy writer.

• While writing a TLA+ model of DirectoryTaxonomyWriter's cache, the finder read perhapsFillCache and saw that the refilled keys come from decoded index terms. The model treats labels as atoms, so it cannot and did not witness this bug.
• A bounded-exhaustive check on the stock jar enumerated all 66,822 labels of 1-2 components of 1-3 chars over {a, U+D83D, U+DE00, U+FFFD, U+001F, U+001E}: label -> term -> label changes exactly the 58,080 ill-formed labels, and no two well-formed labels share a term. It characterizes the lossy mapping, not the duplicate ordinal itself.
• The finder then wrote a JUnit on the stock jars (facet counts through the public FacetField API), and an independent reproducer, reviewers from another model family (OpenAI GPT-5.6, reading only), a devil's advocate, an adjudication and an audit checked it.