Hacktoberfest 2026：维护者为十月标记出来的 issue，仍然开放、适合新手。 浏览 Hacktoberfest issue

BTreeIndex silently corrupts ordered storage when compareFn returns NaN

未关闭
  • 哪里不对？
#1,945 0 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看

维护者通常 1 天内回复

还没有人认领这个 Issue。

评估

难度
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 小时
30 天内合并 PR
104

环境准备

从这里开始

  1. 先读完整个 Issue，再读项目的贡献指南。
  2. 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
  3. Fork 仓库，在一个分支上完成修改。
  4. 提交 Pull Request，并在描述里引用这个 Issue 编号。

TanStack/db 的其他 Issue

查看 TanStack/db 的全部 Issue

相似的 Issue

更多 TypeScript Issue

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。