Hacktoberfest 2026：メンテナが10月に向けて印を付けた、オープンで初心者向けの issue。 Hacktoberfest の issue を見る

BTreeIndex silently corrupts ordered storage when compareFn returns NaN

オープン
  • 何か問題がありますか？
#1,945 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

まだ誰も着手していません。

評価

難易度
4/5
見積もり時間
3〜5日
初心者へのやさしさ
72/100
issue の種類
バグ
明瞭さ
明確に書かれている
活発さ
活発
技術スタック
typescript
領域
databases

調査の方向性

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.

索引モデルが issue の本文から書いたものです。

説明

  • 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.
主要言語
TypeScript
スター
3.9k
フォーク
267
平均マージ
1日 7時間
マージ済み PR（30日）
104

環境構築

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

TanStack/db のほかの issue

TanStack/db の issue をすべて見る

似ている issue

TypeScript の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。