commit d4d3b5c989f4a522a5355dadf70c98d7c4077c14
parent f7582fd34f26ccdedac6ec391d503c3f8b699abe
Author: Florian Dold <florian@dold.me>
Date: Tue, 3 Feb 2026 19:02:52 +0100
idb-bridge: fix/simplify index iteration
Diffstat:
3 files changed, 484 insertions(+), 123 deletions(-)
diff --git a/packages/idb-bridge/src/MemoryBackend.ts b/packages/idb-bridge/src/MemoryBackend.ts
@@ -1592,6 +1592,427 @@ export class MemoryBackend implements Backend {
}
}
+interface Boundary {
+ key: Key;
+ inclusive: boolean;
+}
+
+function getRangeEndBoundary(
+ forward: boolean,
+ range: IDBKeyRange | undefined | null,
+): Boundary | undefined {
+ let endRangeKey: Uint8Array | undefined = undefined;
+ let endRangeInclusive: boolean = false;
+ if (range) {
+ if (forward && range.upper != null) {
+ endRangeKey = range.upper;
+ endRangeInclusive = !range.upperOpen;
+ } else if (!forward && range.lower != null) {
+ endRangeKey = range.lower;
+ endRangeInclusive = !range.lowerOpen;
+ }
+ }
+ if (endRangeKey) {
+ return {
+ inclusive: endRangeInclusive,
+ key: endRangeKey,
+ };
+ }
+ return undefined;
+}
+
+function isOutsideBoundary(
+ forward: boolean,
+ endRange: Boundary,
+ currentKey: Key,
+): boolean {
+ const cmp = compareKeys(currentKey, endRange.key);
+ if (forward && endRange.inclusive && cmp > 0) {
+ return true;
+ } else if (forward && !endRange.inclusive && cmp >= 0) {
+ return true;
+ } else if (!forward && endRange.inclusive && cmp < 0) {
+ return true;
+ } else if (!forward && !endRange.inclusive && cmp <= 0) {
+ return true;
+ }
+ return false;
+}
+
+interface IndexIterPos {
+ objectPos: Key;
+ indexPos: Key;
+}
+
+type IndexData = ISortedMapF<IDBValidKey, IndexRecord>;
+
+function startIndex(req: {
+ indexData: IndexData;
+ forward: boolean;
+ unique: boolean;
+}): IndexIterPos | undefined {
+ const { forward, unique, indexData } = req;
+ if (forward) {
+ const indexPos = indexData.minKey();
+ if (indexPos != null) {
+ const indexEntry = indexData.get(indexPos);
+ if (!indexEntry) {
+ throw Error("data error");
+ }
+ const objectPos = indexEntry.primaryKeys.minKey();
+ if (objectPos != null) {
+ return { indexPos, objectPos };
+ }
+ }
+ } else {
+ const indexPos = indexData.maxKey();
+ if (indexPos != null) {
+ const indexEntry = indexData.get(indexPos);
+ if (!indexEntry) {
+ throw Error("data error");
+ }
+ let objectPos: Key | undefined;
+ if (unique) {
+ objectPos = indexEntry.primaryKeys.minKey();
+ } else {
+ objectPos = indexEntry.primaryKeys.maxKey();
+ }
+
+ if (objectPos != null) {
+ return { indexPos, objectPos };
+ }
+ }
+ }
+ return undefined;
+}
+
+function continueIndexForwardInclusive(
+ indexData: IndexData,
+ targetIndexKey: Key,
+ targetObjectKey: Key,
+): IndexIterPos | undefined {
+ let indexEntry = indexData.get(targetIndexKey);
+ if (indexEntry) {
+ if (indexEntry.primaryKeys.has(targetObjectKey)) {
+ return {
+ indexPos: targetIndexKey,
+ objectPos: targetObjectKey,
+ };
+ } else {
+ const objectPos = indexEntry.primaryKeys.nextHigherKey(targetObjectKey);
+ if (!objectPos) {
+ return undefined;
+ }
+ return { indexPos: targetIndexKey, objectPos };
+ }
+ }
+
+ const pair = indexData.nextHigherPair(targetIndexKey);
+ if (!pair) {
+ return undefined;
+ }
+
+ indexEntry = pair[1];
+ const indexPos = pair[0];
+
+ const objectPos = indexEntry.primaryKeys.minKey();
+ if (!objectPos) {
+ return undefined;
+ }
+
+ return { indexPos, objectPos };
+}
+
+function continueIndexForwardInclusiveUnique(
+ indexData: IndexData,
+ targetIndexKey: Key,
+): IndexIterPos | undefined {
+ const indexEntry = indexData.get(targetIndexKey);
+ if (indexEntry) {
+ const objectPos = indexEntry.primaryKeys.minKey();
+ if (!objectPos) {
+ return undefined;
+ }
+ return {
+ indexPos: targetIndexKey,
+ objectPos,
+ };
+ }
+ const pair = indexData.nextHigherPair(targetIndexKey);
+ if (!pair) {
+ return undefined;
+ }
+ const objectPos = pair[1].primaryKeys.minKey();
+ if (!objectPos) {
+ return undefined;
+ }
+ return {
+ indexPos: pair[0],
+ objectPos,
+ };
+}
+
+function continueIndexForwardStrict(
+ indexData: IndexData,
+ targetIndexKey: Key,
+ targetObjectKey: Key,
+): IndexIterPos | undefined {
+ let indexEntry = indexData.get(targetIndexKey);
+ if (indexEntry) {
+ const objectPos = indexEntry.primaryKeys.nextHigherKey(targetObjectKey);
+ if (!objectPos) {
+ return undefined;
+ }
+ return { indexPos: targetIndexKey, objectPos };
+ }
+
+ const pair = indexData.nextHigherPair(targetIndexKey);
+ if (!pair) {
+ return undefined;
+ }
+
+ indexEntry = pair[1];
+ const indexPos = pair[0];
+
+ const objectPos = indexEntry.primaryKeys.minKey();
+ if (!objectPos) {
+ return undefined;
+ }
+
+ return { indexPos, objectPos };
+}
+
+function continueIndexForwardStrictUnique(
+ indexData: IndexData,
+ targetIndexKey: Key,
+): IndexIterPos | undefined {
+ const pair = indexData.nextHigherPair(targetIndexKey);
+ if (!pair) {
+ return undefined;
+ }
+ const objectPos = pair[1].primaryKeys.minKey();
+ if (!objectPos) {
+ return undefined;
+ }
+ return {
+ indexPos: pair[0],
+ objectPos,
+ };
+}
+
+function continueIndexBackwardInclusive(
+ indexData: IndexData,
+ targetIndexKey: Key,
+ targetObjectKey: Key,
+): IndexIterPos | undefined {
+ let indexEntry = indexData.get(targetIndexKey);
+ if (indexEntry) {
+ if (indexEntry.primaryKeys.has(targetObjectKey)) {
+ return {
+ indexPos: targetIndexKey,
+ objectPos: targetObjectKey,
+ };
+ } else {
+ const objectPos = indexEntry.primaryKeys.nextLowerKey(targetObjectKey);
+ if (!objectPos) {
+ return undefined;
+ }
+ return { indexPos: targetIndexKey, objectPos };
+ }
+ }
+
+ const pair = indexData.nextLowerPair(targetIndexKey);
+ if (!pair) {
+ return undefined;
+ }
+
+ indexEntry = pair[1];
+ const indexPos = pair[0];
+
+ const objectPos = indexEntry.primaryKeys.maxKey();
+ if (!objectPos) {
+ return undefined;
+ }
+
+ return { indexPos, objectPos };
+}
+
+function continueIndexBackwardInclusiveUnique(
+ indexData: IndexData,
+ targetIndexKey: Key,
+): IndexIterPos | undefined {
+ const indexEntry = indexData.get(targetIndexKey);
+ if (indexEntry) {
+ // Backwards iteration, but still use minKey for object pos
+ const objectPos = indexEntry.primaryKeys.minKey();
+ if (!objectPos) {
+ return undefined;
+ }
+ return {
+ indexPos: targetIndexKey,
+ objectPos,
+ };
+ }
+ const pair = indexData.nextLowerPair(targetIndexKey);
+ if (!pair) {
+ return undefined;
+ }
+ // Backwards iteration, but still use minKey for object pos
+ const objectPos = pair[1].primaryKeys.minKey();
+ if (!objectPos) {
+ return undefined;
+ }
+ return {
+ indexPos: pair[0],
+ objectPos,
+ };
+}
+
+function continueIndexBackwardStrict(
+ indexData: IndexData,
+ targetIndexKey: Key,
+ targetObjectKey: Key,
+): IndexIterPos | undefined {
+ let indexEntry = indexData.get(targetIndexKey);
+ if (indexEntry) {
+ const objectPos = indexEntry.primaryKeys.nextLowerKey(targetObjectKey);
+ if (!objectPos) {
+ return undefined;
+ }
+ return { indexPos: targetIndexKey, objectPos };
+ }
+
+ const pair = indexData.nextLowerPair(targetIndexKey);
+ if (!pair) {
+ return undefined;
+ }
+
+ indexEntry = pair[1];
+ const indexPos = pair[0];
+
+ const objectPos = indexEntry.primaryKeys.maxKey();
+ if (!objectPos) {
+ return undefined;
+ }
+
+ return { indexPos, objectPos };
+}
+
+function continueIndexBackwardStrictUnique(
+ indexData: IndexData,
+ targetIndexKey: Key,
+): IndexIterPos | undefined {
+ const pair = indexData.nextLowerPair(targetIndexKey);
+ if (!pair) {
+ return undefined;
+ }
+ const objectPos = pair[1].primaryKeys.minKey();
+ if (!objectPos) {
+ return undefined;
+ }
+ return {
+ indexPos: pair[0],
+ objectPos,
+ };
+}
+
+/**
+ * Continue past targetIndexKey (and optionally targetObjectKey)
+ * in the direction specified by "forward".
+ * Do nothing if the current position is already past the
+ * target position.
+ */
+function continueIndex(req: {
+ indexData: ISortedMapF<IDBValidKey, IndexRecord>;
+ currentPos?: IndexIterPos;
+ unique: boolean;
+ inclusive: boolean;
+ forward: boolean;
+ targetIndexKey: Key;
+ targetObjectKey?: Key;
+}): IndexIterPos | undefined {
+ const currentPos = req.currentPos;
+ const forward = req.forward;
+ const inclusive = req.inclusive;
+ const dir = forward ? 1 : -1;
+ if (currentPos) {
+ // Check that the target position after the current position.
+ // If not, we just stay at the current position.
+ const indexCmp = compareKeys(currentPos.indexPos, req.targetIndexKey);
+ if (dir * indexCmp > 0) {
+ return currentPos;
+ }
+ if (indexCmp === 0) {
+ if (req.targetObjectKey != null) {
+ const objectCmp = compareKeys(
+ currentPos.objectPos,
+ req.targetObjectKey,
+ );
+ if (req.inclusive && objectCmp === 0) {
+ return currentPos;
+ }
+ if (dir * objectCmp > 0) {
+ return currentPos;
+ }
+ } else if (req.inclusive) {
+ return currentPos;
+ }
+ }
+ }
+ const indexData = req.indexData;
+ if (forward) {
+ if (req.unique || req.targetObjectKey == null) {
+ if (inclusive) {
+ return continueIndexForwardInclusiveUnique(
+ indexData,
+ req.targetIndexKey,
+ );
+ } else {
+ return continueIndexForwardStrictUnique(indexData, req.targetIndexKey);
+ }
+ } else {
+ if (inclusive) {
+ return continueIndexForwardInclusive(
+ indexData,
+ req.targetIndexKey,
+ req.targetObjectKey,
+ );
+ } else {
+ return continueIndexForwardStrict(
+ indexData,
+ req.targetIndexKey,
+ req.targetObjectKey,
+ );
+ }
+ }
+ } else {
+ if (req.unique || req.targetObjectKey == null) {
+ if (inclusive) {
+ return continueIndexBackwardInclusiveUnique(
+ indexData,
+ req.targetIndexKey,
+ );
+ } else {
+ return continueIndexBackwardStrictUnique(indexData, req.targetIndexKey);
+ }
+ } else {
+ if (inclusive) {
+ return continueIndexBackwardInclusive(
+ indexData,
+ req.targetIndexKey,
+ req.targetObjectKey,
+ );
+ } else {
+ return continueIndexBackwardStrict(
+ indexData,
+ req.targetIndexKey,
+ req.targetObjectKey,
+ );
+ }
+ }
+ }
+}
+
function getIndexRecords(req: {
indexData: ISortedMapF<IDBValidKey, IndexRecord>;
storeData: ISortedMapF<IDBValidKey, ObjectStoreRecord>;
@@ -1609,14 +2030,7 @@ function getIndexRecords(req: {
const indexKeys: Key[] = [];
const primaryKeys: Key[] = [];
const values: Value[] = [];
- const { unique, range, forward, indexData } = req;
-
- function nextIndexEntry(prevPos: IDBValidKey): IndexRecord | undefined {
- const res: [IDBValidKey, IndexRecord] | undefined = forward
- ? indexData.nextHigherPair(prevPos)
- : indexData.nextLowerPair(prevPos);
- return res ? res[1] : undefined;
- }
+ const { unique, forward, indexData } = req;
function packResult(): RecordGetResponse {
// Collect the values based on the primary keys,
@@ -1642,145 +2056,93 @@ function getIndexRecords(req: {
};
}
- let firstIndexPos = req.lastIndexPosition;
- {
- const rangeStart = forward ? range.lower : range.upper;
- const dataStart = forward ? indexData.minKey() : indexData.maxKey();
- firstIndexPos = furthestKey(forward, firstIndexPos, rangeStart);
- firstIndexPos = furthestKey(forward, firstIndexPos, dataStart);
- }
-
- if (firstIndexPos == null) {
- return packResult();
- }
-
- let objectStorePos: IDBValidKey | undefined = undefined;
- let indexEntry: IndexRecord | undefined = undefined;
+ const endRange = getRangeEndBoundary(forward, req.range);
- // Now we align at indexPos and after objectStorePos
+ let currentPos = startIndex({
+ forward,
+ indexData,
+ unique,
+ });
- indexEntry = indexData.get(firstIndexPos);
- if (!indexEntry) {
- // We're not aligned to an index key, go to next index entry
- indexEntry = nextIndexEntry(firstIndexPos);
- if (!indexEntry) {
- return packResult();
- }
- objectStorePos = nextKey(true, indexEntry.primaryKeys, undefined);
- } else if (
- req.lastIndexPosition != null &&
- compareKeys(req.lastIndexPosition, indexEntry.indexKey) !== 0
- ) {
- // We're already past the desired lastIndexPosition, don't use
- // lastObjectStorePosition.
- objectStorePos = nextKey(true, indexEntry.primaryKeys, undefined);
- } else {
- objectStorePos = nextKey(
- true,
- indexEntry.primaryKeys,
- req.lastObjectStorePosition,
- );
+ if (currentPos == null) {
+ return packResult();
}
- // Now skip lower/upper bound of open ranges
-
- if (
- forward &&
- range.lowerOpen &&
- range.lower != null &&
- compareKeys(range.lower, indexEntry.indexKey) === 0
- ) {
- indexEntry = nextIndexEntry(indexEntry.indexKey);
- if (!indexEntry) {
- return packResult();
- }
- objectStorePos = indexEntry.primaryKeys.minKey();
- }
+ if (req.advanceIndexKey != null) {
+ currentPos = continueIndex({
+ indexData,
+ unique,
+ inclusive: true,
+ currentPos,
+ forward,
+ targetIndexKey: req.advanceIndexKey,
+ targetObjectKey: req.advancePrimaryKey,
+ });
- if (
- !forward &&
- range.upperOpen &&
- range.upper != null &&
- compareKeys(range.upper, indexEntry.indexKey) === 0
- ) {
- indexEntry = nextIndexEntry(indexEntry.indexKey);
- if (!indexEntry) {
+ if (currentPos == null) {
return packResult();
}
- objectStorePos = indexEntry.primaryKeys.minKey();
}
- // If requested, return only unique results
-
- if (
- unique &&
- req.lastIndexPosition != null &&
- compareKeys(indexEntry.indexKey, req.lastIndexPosition) === 0
- ) {
- indexEntry = nextIndexEntry(indexEntry.indexKey);
- if (!indexEntry) {
+ if (req.lastIndexPosition != null) {
+ currentPos = continueIndex({
+ indexData,
+ unique,
+ inclusive: false,
+ currentPos,
+ forward,
+ targetIndexKey: req.lastIndexPosition,
+ targetObjectKey: req.lastObjectStorePosition,
+ });
+ if (!currentPos) {
return packResult();
}
- objectStorePos = indexEntry.primaryKeys.minKey();
}
- if (req.advanceIndexKey != null) {
- const ik = furthestKey(forward, indexEntry.indexKey, req.advanceIndexKey)!;
- indexEntry = indexData.get(ik);
- if (!indexEntry) {
- indexEntry = nextIndexEntry(ik);
+ if (req.range != null) {
+ const targetKeyObj = forward ? req.range.lower : req.range.upper;
+ if (targetKeyObj != null) {
+ const targetKey = targetKeyObj;
+ const inclusive = forward ? !req.range.lowerOpen : !req.range.upperOpen;
+ currentPos = continueIndex({
+ indexData,
+ unique,
+ inclusive,
+ currentPos,
+ forward,
+ targetIndexKey: targetKey,
+ });
}
- if (!indexEntry) {
+ if (!currentPos) {
return packResult();
}
}
- // Use advancePrimaryKey if necessary
- if (
- req.advanceIndexKey != null &&
- req.advancePrimaryKey &&
- compareKeys(indexEntry.indexKey, req.advanceIndexKey) == 0
- ) {
- if (
- objectStorePos == null ||
- compareKeys(req.advancePrimaryKey, objectStorePos) > 0
- ) {
- objectStorePos = nextKey(
- true,
- indexEntry.primaryKeys,
- req.advancePrimaryKey,
- );
- }
- }
-
while (1) {
if (req.limit != 0 && numResults == req.limit) {
break;
}
- if (!range.includes(indexEntry.indexKey)) {
+ if (currentPos == null) {
break;
}
- if (indexEntry === undefined) {
+ if (endRange && isOutsideBoundary(forward, endRange, currentPos.indexPos)) {
break;
}
- if (objectStorePos == null) {
- // We don't have any more records with the current index key.
- indexEntry = nextIndexEntry(indexEntry.indexKey);
- if (!indexEntry) {
- return packResult();
- }
- objectStorePos = indexEntry.primaryKeys.minKey();
- continue;
- }
- indexKeys.push(structuredClone(indexEntry.indexKey));
- primaryKeys.push(structuredClone(objectStorePos));
+ indexKeys.push(structuredClone(currentPos.indexPos));
+ primaryKeys.push(structuredClone(currentPos.objectPos));
+
numResults++;
- if (unique) {
- objectStorePos = undefined;
- } else {
- objectStorePos = indexEntry.primaryKeys.nextHigherKey(objectStorePos);
- }
+
+ currentPos = continueIndex({
+ indexData,
+ unique,
+ forward,
+ inclusive: false,
+ currentPos: undefined,
+ targetIndexKey: currentPos.indexPos,
+ targetObjectKey: currentPos.objectPos,
+ });
}
return packResult();
diff --git a/packages/idb-bridge/src/SqliteBackend.ts b/packages/idb-bridge/src/SqliteBackend.ts
@@ -416,7 +416,7 @@ export class SqliteBackend implements Backend {
console.log(`objectKey:`, deserializeKey(currentPos.objectPos));
}
- if (req.advanceIndexKey) {
+ if (req.advanceIndexKey != null) {
const advanceIndexKey = serializeKey(req.advanceIndexKey);
const advancePrimaryKey = req.advancePrimaryKey
? serializeKey(req.advancePrimaryKey)
@@ -436,7 +436,7 @@ export class SqliteBackend implements Backend {
}
}
- if (req.lastIndexPosition) {
+ if (req.lastIndexPosition != null) {
if (this.enableTracing) {
console.log("index query: seeking past last index position");
console.log("lastObjectPosition", req.lastObjectStorePosition);
diff --git a/packages/idb-bridge/src/testingdb.ts b/packages/idb-bridge/src/testingdb.ts
@@ -27,8 +27,7 @@ export async function initTestIndexedDB(): Promise<void> {
if (process.env.IDB_TEST_BACKEND == "memory") {
const memBackend = new MemoryBackend();
backend = memBackend;
- // backend.enableTracing = true;
- memBackend.enableTracing = false;
+ memBackend.enableTracing = true;
} else {
const sqlite3Impl = await createNodeHelperSqlite3Impl({
enableTracing: false,
