Hacktoberfest 2026 : les issues que les mainteneurs ont marquées pour octobre, ouvertes et accessibles aux débutants. Parcourir les issues Hacktoberfest

BTreeIndex silently corrupts ordered storage when compareFn returns NaN

Ouverte
  • Quelque chose ne va pas ?
#1,945 0 commentaires 0 réactions 0 personnes assignées Voir sur GitHub

Les mainteneurs répondent en général sous 1 jour

Personne n'a encore pris cette issue.

Évaluation

Difficulté
4/5
Temps estimé
3-5 jours
Accessibilité débutants
72/100
Type d'issue
Bug
Clarté
Clairement spécifiée
Activité
Active
Stack technique
typescript
Domaine
databases

Piste de recherche

Start with packages/db/src/utils/btree.ts, especially BNode.indexOf, and reproduce the NaN comparator behavior through BTree. Then inspect packages/db/tests/index-update.property.test.ts and docs/contributing/oracle-coverage.md. Done means invalid comparison results fail clearly on the first write or read, no partial tree is observable, and the changeset documents the behavior change.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Description

  • I've validated the bug against the latest version of DB packages (origin/main at ae2eb3fb)

Describe the bug

BTreeIndex silently corrupts its ordered storage when a custom compareFn returns NaN. The index does not throw. Ordered reads then drop rows.

A comparator such as (a, b) => a - b returns NaN for string values. The vendored B+ tree in packages/db/src/utils/btree.ts handles a NaN comparison in indexOf like this:

// c is NaN or otherwise invalid
if (key === key)
  // at least the search key is not NaN
  return keys.length
else throw new Error(`BTree: NaN was used as a key`)

A non-negative return value means "key found". So every lookup reports a match one position past the end of the node. As a result:

  • set treats each new key as an overwrite, so size does not grow and the rows are not stored in order.
  • get returns undefined for inserted keys.
  • has returns true for keys that were never inserted.
  • delete returns true and decrements size, but removes nothing.

The throw only happens when the search key itself is NaN. A comparator that returns NaN is a contract breach by the caller. Per AGENTS.md ("Separate Valid Edge Cases from Contract Contradictions"), the index should reject it at the boundary instead of degrading silently.

To Reproduce

Public API (BTreeIndex is exported from @tanstack/db):

import { BTreeIndex, IR } from '@tanstack/db'

const index = new BTreeIndex<number>(1, new IR.PropRef(['name']), undefined, {
  compareFn: (a, b) => a - b, // NaN for strings
})
for (const [id, name] of [[1, 'ann'], [2, 'bob'], [3, 'cy']] as const)
  index.add(id, { id, name })

index.takeFromStart(10) // [1]  expected [1, 2, 3]
index.lookup('eq', 'bob') // [2] (equality is served separately, so it looks fine)

With the default comparator, takeFromStart(10) returns [1, 2, 3].

The B+ tree directly:

import { BTree } from './src/utils/btree' // internal

const tree = new BTree<any, string>((a, b) => a - b)
for (const k of ['a', 'b', 'c']) tree.set(k, k)
tree.size // 1   expected 3
tree.has('zzz') // true (never inserted)
tree.delete('zzz') // true, and size becomes 0
tree.get('a') // undefined

Expected behavior

An invalid comparison result should fail fast with a clear error, for example BTree: comparator returned NaN, at the first set, get, or delete that sees it. The index should never accept writes into a corrupted tree.

Scope and limits of this report

  • This behavior is old. It comes from the vendored sorted-btree code and is present on main. It was found during a code-weight review of the vendored B+ tree. That trim keeps the behavior unchanged on purpose, so the fix can be its own behavior change.
  • Live queries using the same index returned correct rows in a quick probe. They appear to re-filter or avoid this path. The corruption is directly observable through BTreeIndex ordered reads (take*, range queries). I have not mapped every public query shape that reaches it.
  • The default comparator (makeComparator) never returns NaN, so only custom compareFn values are affected.

Suggested fix and test

  • In BNode.indexOf, throw whenever the comparison result is not < 0, > 0, or === 0, instead of returning keys.length.
  • Add a law to the index refinement oracle (packages/db/tests/index-update.property.test.ts, owner listed under "Structural values and ordered primitives" in docs/contributing/oracle-coverage.md): a comparator that returns NaN must cause the first write to throw, and no later read may observe a partial tree. Calibrate it against the current return keys.length behavior.
  • Add a changeset: users with broken comparators will see a new error where they previously got silently wrong results.
Langage dominant
TypeScript
Étoiles
3.9k
Forks
267
Merge moyen
1 j 7 h
PR mergées (30 j)
104

Préparer son environnement

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Autres issues de TanStack/db

Toutes les issues de TanStack/db

Issues similaires

Plus d'issues TypeScript

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.