Skip to content

Iterator/stream: fix reverse-prefix bug + Spliterator SORTED contract, add coverage - #292

Open
bernardladenthin wants to merge 2 commits into
lmdbjava:iterator-performancefrom
bernardladenthin:feat/iterator-perf-followup
Open

Iterator/stream: fix reverse-prefix bug + Spliterator SORTED contract, add coverage#292
bernardladenthin wants to merge 2 commits into
lmdbjava:iterator-performancefrom
bernardladenthin:feat/iterator-perf-followup

Conversation

@bernardladenthin

Copy link
Copy Markdown

Follow-up work stacked on the iterator-performance branch (targets that branch, not master). It fixes two correctness/contract issues in the new iterator/stream code, adds the missing unit/integration coverage for the gh-269 helpers, and tidies a few related items. All changes are additive or self-contained; the design decisions on the branch (see "Deliberately left open" below) are untouched.

Fixes

1. Reverse prefix iteration silently drops rows when the prefix ends in 0xFF

BufferProxy.incrementLeastSignificantByte computed the "prefix successor" by incrementing the least-significant non-0xFF byte but keeping the trailing 0xFF bytes — e.g. {0x01,0xFF}{0x02,0xFF} instead of the tight {0x02}.

In LmdbPrefixReversedIterator/LmdbPrefixReversedSpliterator the successor is used to MDB_SET_RANGE past the prefix range and step back. When it over-shoots, an unrelated higher key that sorts between the last prefix match and the over-shot successor is landed on, the containsPrefix check fails, and iteration wrongly yields nothing.

  • Reproduced by LmdbPrefixReversedSuccessorTest (keys {0x01,0xFF}, {0x01,0xFF,0x05}, {0x02,0x00}; reverse-prefix {0x01,0xFF} returned [] before the fix).
  • Fixed by truncating trailing 0xFF (tight successor) across all four proxies' big-endian byte-string branch (ByteArray, ByteBuffer, DirectBuffer, Netty). The little-endian/integer-key branch is left as-is — prefix scans operate on big-endian byte strings.

2. LmdbStream Spliterator advertised SORTED with a null comparator

createEntryComparator/createReversedEntryComparator returned null (real body commented out), yet every spliterator reported ORDERED | DISTINCT | SORTED | NONNULL and getComparator() returned that null. A SORTED spliterator with a null comparator implies natural ordering, but KeyVal is not Comparable.

  • Dropped SORTED and DISTINCT (DUPSORT can repeat keys) → ORDERED | NONNULL.
  • getComparator() now throws IllegalStateException, as required for a non-sorted spliterator.
  • Removed the dead entryComparator plumbing (also clears the "useless rangeComparator parameter" scan alerts).
  • Note: a real Comparator<KeyVal<T>> + SORTED isn't safe without first emitting per-element snapshots, because the spliterator emits a single reused KeyVal (collect(toList()) returns one aliased instance for every row). That's a larger design change and is left to the maintainers.

3. KeyRange.getType() returned null for builder-created ranges

The private constructors used by KeyRange.builder() never set type, so getType() returned null and would NPE the legacy CursorIterable path. Builder/empty ranges now derive the equivalent KeyRangeType. Prefix ranges still have no KeyRangeType (documented) as they are only consumed by the new iterators.

Tidy-ups

  • Dbi.stream()/newIterate() javadoc now warns that entries are a single reused KeyVal holder (so collect/sorted/distinct observe aliased entries) and that the stream is ORDERED but not SORTED.
  • Dbi.getNameAsString(Charset): removed a dead try/catch and misleading "assume UTF8" comment (new String(byte[], Charset) never throws).
  • Fixed a stale javadoc link CursorIterable.JavaRangeComparatorJavaRangeComparator.

New/updated tests

  • BufferProxyPrefixTestcontainsPrefix + incrementLeastSignificantByte across all four proxies, incl. edge cases (empty/oversized prefix, unsigned bytes, trailing-0xFF truncation, all-0xFF → null).
  • CompareAsIntegerKeysTest — length-mismatch guard + non-4/8-byte lexicographic fallback for the integer-key comparators.
  • KeyRangeBuilderTest — builder/prefix/inclusive accessors + derived KeyRangeType.
  • LmdbStreamCharacteristicsTest — locks in the corrected spliterator contract.
  • DbiIterateApiTestnewIterate(EntryConsumer) overloads, ranged stream, LmdbIterable single-use, getNameAsString, toString.
  • LmdbPrefixReversedSuccessorTest — the reverse-prefix regression above.

Verification

Full test suite (excluding the pre-existing, environment-flaky TestLmdbStreamBenchmark, which fails at Env.open unrelated to these changes): 1687 tests, 0 failures. mvn fmt:check is clean for all touched files. Java 8 source level unchanged.

Deliberately left open (branch decisions, not addressed here)

These came up while reviewing the branch and are for the maintainers, not this PR:

🤖 Generated with Claude Code

bernardladenthin and others added 2 commits July 24, 2026 14:09
Adds unit coverage for lmdbjavagh-269 iterator/stream helpers that had none, and
corrects the LmdbStream spliterator characteristics.

Tests:
- BufferProxyPrefixTest: containsPrefix + incrementLeastSignificantByte across
  all four proxies, with edge cases (empty/oversized prefix, unsigned bytes,
  trailing-0xFF carry, all-0xFF -> null).
- CompareAsIntegerKeysTest: length-mismatch guard and non-4/8-byte lexicographic
  fallback for the integer-key comparators.
- KeyRangeBuilderTest: builder/prefix/start-stop-inclusive accessors; also
  documents that getType() is null for builder()/prefix()-created ranges.
- LmdbStreamCharacteristicsTest: locks in the corrected spliterator contract.

Fix (LmdbStream):
- Drop the false SORTED and DISTINCT characteristics: entries are produced in key
  order but no KeyVal comparator is exposed, and DUPSORT can repeat keys.
- getComparator() now throws IllegalStateException (required for a non-SORTED
  spliterator) instead of returning null.
- Remove the dead entryComparator plumbing (stubbed factories returning null),
  which also clears the unused-parameter warnings.

The fuller alternative (real Comparator<KeyVal<T>> + SORTED) was investigated and
rejected: the spliterator emits a single reused KeyVal instance, so advertising
SORTED would be unsound without first emitting per-element snapshots.

Co-Authored-By: Claude Opus 4.8 (1M context) <[email protected]>
Fix (correctness):
- incrementLeastSignificantByte over-shot the prefix successor when the prefix
  ended in 0xFF: {0x01,0xFF} produced {0x02,0xFF} instead of the tight {0x02},
  keeping the trailing 0xFF. In reverse prefix iteration this seeks past the
  prefix range and steps back onto an unrelated higher key, so iteration wrongly
  yields nothing. Now truncates trailing 0xFF across all four proxies (big-endian
  byte-string branch). LmdbPrefixReversedSuccessorTest reproduces and guards it.

KeyRange:
- Builder/empty ranges now derive the equivalent KeyRangeType, so getType() is no
  longer null (a null type would NPE the legacy CursorIterable path). Prefix
  ranges still have no KeyRangeType (documented).

Dbi:
- Document that stream()/newIterate() emit a single reused KeyVal holder (so
  collect/sorted/distinct observe aliased entries) and that the stream is ORDERED
  but not SORTED.
- Simplify getNameAsString(Charset): drop the dead try/catch and misleading
  "assume UTF8" comment; new String(byte[], Charset) never throws.
- Fix stale javadoc link CursorIterable.JavaRangeComparator -> JavaRangeComparator.

Tests:
- DbiIterateApiTest: newIterate(EntryConsumer) overloads, ranged stream,
  LmdbIterable single-use, getNameAsString, toString.
- BufferProxyPrefixTest / KeyRangeBuilderTest updated for the corrected successor
  truncation and the derived KeyRangeType.

Full suite (excluding the pre-existing flaky TestLmdbStreamBenchmark) green: 1687
tests, 0 failures.

Co-Authored-By: Claude Opus 4.8 (1M context) <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant