# 目录树发现层设计

> 状态：方案定稿，实现进行中（分支 `tui-tree-discovery`）。

## 问题

cdh 的候选池严格等于历史（`history_raw ∪ history_uniq`；代码中唯一的文件系统访问 `is_dir()` 只删不加）。由此产生三个后果：

1. 没 `cd` 过的目录永远搜不到；
2. 零历史新用户在 `controller.rs` 里直接 `return 2`，TUI 根本不开——最需要它的人反而用不上；
3. 用户实际记得的是「大概的关键字」而非完整路径，「知道路径但没去过」与「想发现新目录」在真实使用中本来就是同一个需求。

现有工具没有填这个空白：z / autojump / zoxide 纯历史；fzf 纯文件系统、无排序智能。

## 核心思路

候选池 = 历史 ∪ 目录树；排序融合算法不变。

所需的「推荐 + 模糊」融合能力已经存在——`Filter::run` 本身就是「nucleo 模糊分为主、frecency 为次」的排序。这不是一套新算法，而是给现有算法喂更多候选。

## 扫描模型

遍历采用 BFS（浅先深后），默认无深度上限；边界 = 候选数 cap 50,000 + 全局时间预算约 5s。深度上限只是工作量的代理指标，而我们直接约束工作量本身。

实测：去掉深度上限只多约 0.4s / 1.9 万候选（名字剪枝生效后：深度 8 = 39,193 个 / 1.40s，无限制 = 57,823 个 / 1.80s，单线程热缓存）。BFS 保证截断时丢的是「最深、最不可能」的尾部，而不是在某一层画一条武断的线（深度上限会为了保住 3.9 万个浅层而丢掉一个深度 9 的真实项目）。

### 关键修正（实测驱动）

BFS 的 frontier 跨所有根**全局共享、按深度排序出队**——所有根的第 1 层先于任何根的第 2 层。

动机：9p 挂载实测冷热几乎无差别：

- `/mnt/d/DevTools`（深度 4、3800 目录）：冷 6.69s vs 热 3.89s，仅 1.7×；
- `/mnt/d/Software`（深度 3、640 目录）：冷 0.85s vs 热 0.71s。

瓶颈是协议往返约 1ms/目录，即 `/mnt`「永远慢」而非「冷时慢」。顺序级联 + 全局预算会让单个大 `/mnt` 锚点（`DevTools` 一家就 4–7s）独占预算、饿死其余；全局深度序下每个锚点的浅层都保证在预算内到达，截断只丢「最慢挂载的最深层」。同深度内本地根先于慢挂载根（按 `/mnt`、`/media`、`/Volumes` 前缀识别）。

`/mnt` 深层的覆盖每次启动都只是部分的——这是接受的边界，不是 bug。

### 根

根 = `$HOME` + 自适应锚点。

自适应锚点 = 所有历史条目的父目录（去重、验证存在；实测 96 个存在的锚点根浅扫一层耗 94ms、产出 955 个「常用目录的兄弟」）。锚点覆盖两类地方：

- `$HOME` 之外（用户 18% 的历史落在 `/mnt/c`、`/mnt/d`）；
- 特别深的位置。

配合闭环（见「两个结构性性质」）形成棘轮：任何深处去过一次，cdh 从此认识那一带。

### 剪枝

剪枝是性能的第一支柱——垃圾子树占 78% 的遍历 I/O；不剪枝全树 216,424 个 / 12.91s。

按名字全局不下降剪枝：`node_modules` `.git` `.hg` `.svn` `.cache` `__pycache__` `site-packages` `.venv` `venv` `.tox` `.mypy_cache` `.pytest_cache` `.cargo` `.rustup` `.npm` `.pnpm-store` `.gradle` `.m2`。

按绝对路径剪枝：`~/.local/share/{containers,fnm,pipx}`（实测 39,471 + 18,933 + 6,162 = 6.4 万目录，全是工具存储）。

保留隐藏目录——用户历史里 `.claude-ctf-workspace` 出现 15 次、`.codex` 出现 13 次。垃圾按名字点名，而不按「是否隐藏」这个属性一刀切（实测数据：955 候选实验中的噪音源是 `/mnt/c/Users/Jason` 85 个、`/tmp` 51 个、`~/.config` 50 个，而非构建产物）。

不跟随符号链接；无权限静默跳过。

### 环境变量

- `CDH_DISCOVER=0`：总开关；
- `CDH_SCAN_ROOTS`（冒号分隔）：覆盖根；
- `CDH_SCAN_DEPTH`：可选硬上限，默认不设。

用户真实访问深度：中位 3、p90 = 5、p99 = 6、最大 7（n = 146）——但据此设默认上限的方案被否决，见「被否决的方案」。

## 性能

### 已实测（本机热缓存）

扫描数字见「扫描模型」。匹配侧：`fzf --filter` 在 5.4 万条真实路径上单次全量打分 20–40ms（含进程开销；查询 `ws` / `cdh` / `workspace` / `repos` / `billing` / `xyz` 均落在此区间），nucleo 进程内预期 10–25ms——踩在 30ms 预算边缘，无余量。

### 缓解阶梯（各有明确触发条件）

1. 高亮推迟到可见行——**无条件做**。现在 `Filter::run` 对每个匹配候选跑两遍（打分 + `fuzzy_indices`），命中上万条时全算高亮是纯浪费，可见的只有约 19 行；
2. 追加式增量过滤（追加字符只重打旧匹配集，退格才全量）——实测 >30ms 才做；
3. 过滤挪到 worker 线程——前两条不够才考虑；
4. `PathDisplay` 惰性化（现在急切构造 home 缩写 + Unicode 宽度 × 全池）——启动或并入卡顿才做。

### 批次并入的隐患

每批到达都重过滤 ≈ 100 批 × 平均 2.5 万池 ≈ 250 万次打分摊在填充期。对策：每轮事件循环 drain 全部待处理批次后只重过滤一次。

### 内存

5 万候选 × 约 100–200B ≈ 10MB 量级（急切 `PathDisplay` 则 25–30MB）。

### 缓存问题

`$HOME`（ext4）冷缓存测不了（无 root），估 2–5×；日常形态是每天首调冷、之后内核 dentry cache 全热、每次扫描自动回暖。`/mnt`（9p）缓存无关紧要（见「关键修正」）。

### 验收门

- 启动首帧与现状无差；
- 按键到重绘 @ 全池 <30ms；
- 全树热扫 <2s 单线程；
- 填充期打字无感知卡顿；
- 内存 <30MB；
- 非交互路径零变化。

## 数据与排序

`Candidate` 增加 `source` 枚举（`History` | `Discovered`），这是唯一的结构改动。去重：路径规范化后字符串比较，历史胜出；`Discovered` 的 `exists = true`、`last_visit = None`。

排序键：模糊分 ↓ → 来源（`History` 先）→ frecency ↓。即在现有的「模糊分 ↓ → frecency ↓」中插入一层。不给树候选伪造 frecency。

发现层内部排序键 = 父目录推荐分（实测该信号跨 0.003..306 五个数量级，60 个根中 42 个非零；最热 `/home/jason` = 306.6、`workspace/labs` = 30.1，零分根如 `/mnt/d/Software` 产出 40 个纯噪音候选——这也是「只扫 frecency>0 的根」曾被考虑的原因，后随全树方案吸收）→ 次键路径字典序。

空查询零回归：历史（frecency 序）在前，逐像素与现状一致；发现层在后。有查询时真融合：名字匹配更好的未访问目录可以合法排到弱匹配历史之前，打平时历史优先。深层垃圾的保险：逃过剪枝的深层目录父 frecency 必然为 0 → 沉在发现层底部，只有名字真命中才浮上来。

## 交互

空历史自举：interactive 时照常开 TUI（`controller.rs` 的 `items.is_empty()` 门放行），picker 立即同步注入 `$PWD` 祖先链 + 一层子目录（字符串切分 + 一次 `read_dir`），完整扫描流式跟上；非交互仍 `return 2`，一字节不变。

分数条在 `Discovered` 行不画 0（会被误读为「很冷」）。新文案走 `picker_i18n` 的 `TextKey` 双语。README 环境变量表补三行。

### `Ctrl+D` = 排除，不是删除

第一版让 `Ctrl+D` 在 `Discovered` 行直接拒绝（"没有历史记录可删"），理由是不得损坏历史文件。这个理由成立，但结论错了：候选池涨到五万条之后，用户手上**没有任何能从 TUI 里驱动的降噪手段**，而 `CDH_IGNORE_RE` 当时根本不作用于发现层（它在 `recommend.rs` 里过滤，发现路径直接进 `ingest_discovered`，绕开了整条管线——等于对新候选池里 98% 的内容静默失效）。

改后的语义：

- **子树**，不是单个目录。`~/miniforge3` 一条抵六千多条；排掉父目录而子目录还在会显得像坏了。
- **持久**，写 `DATA/cdh/excludes`（行式路径 + 原子写，同 `history_uniq` 的形状）。原来的「会话内隐藏、下次启动以一个再也删不掉的发现行回来」是三种候选语义里最难解释的一种。
- **同时喂给扫描器当剪枝集合**，所以省的是 I/O 而不只是显示；根这一层要单独滤（`drop_excluded_roots`），因为 `prune_abs` 只挡子目录、挡不住根自己。
- 历史行额外删历史文件（否则记录仍参与 frecency，且 `CDH_DISCOVER=0` 时会照旧冒出来）；发现行只写清单，历史文件一字节不动。

`ignore_re` 同时补进 `ingest_discovered`，两条降噪路径从此都覆盖全池。

### 取消排除只能有一个入口

被排除的目录**不在候选池里**，所以没有任何一行可以让用户按键撤销——这不是懒得做，是结构上没有落点。因此有 `F4` 排除清单面板（`Mode::Excludes`）：列出条目、上下选择、`Ctrl+D` 删条目。

取消后必须**当场**把子树找回来。启动那轮扫描的剪枝集合在 spawn 时就定死了，不会回头补；不补扫的话撤销要等下次启动才生效——正是当初让删除语义显得别扭的那个「生效了，但要等到明天」。所以 `discover::spawn_subtree` 以该目录为唯一根跑一遍，结果并入同一条 `ingest_discovered` 路径。`App::discover_rx` 因此从单个 `Option` 改成 `Vec`：补扫可能和还没跑完的启动扫描并存。

## 流式架构

扫描在 worker 线程，约 512 条/批经 mpsc 入事件循环，参照 `PreviewWorker` 的 channel + drain + dirty 形状；`restore_selected_path` 保选中。

放弃语义而非取消：死挂载上 `read_dir` 不可中断、线程杀不掉，退出时 detach 丢结果（这一点曾被错误类比为 git 探测的 300ms 超时——那杀的是子进程，不适用于此）。

## 两个结构性性质

**闭环**：选中 `Discovered` 跳转 → shell hook 照常 `cdh log` → 自动转为历史。「发现路径绝不写 `history_raw`」零代码实现；跨机器同步历史干净；配合锚点成棘轮。

**架构边界**：`recommend.rs` 完全不动（非交互路径共用它，退出码语义不变）；发现层全在 picker 一侧。

## 被否决的方案（每条附否决理由）

本节是文档的核心价值，逐条保留。

1. **磁盘索引/缓存路径**：亚秒扫描 + 流式已够；缓存与「找新目录」直接冲突——目标恰恰是五分钟前刚 clone 的仓库；索引带来失效/刷新/格式三种负债。曾考虑「每根扫描耗时缓存到 `state_dir`」，随全树 + 全局 BFS 方案一并否决（活动部件 -1）。
2. **`ignore` crate / 依赖 fd**：实测 fd 快的主因是剪枝而非并行魔法（fd 全量 0.66s vs find 12.91s，但 find + 剪枝 2.62s）；固定名单覆盖 78% I/O；gitignore 语义在此甚至是错的——会排掉用户想去的 `build/`、`data/`；保住零依赖单二进制（安装 = 下载一个二进制）。
3. **硬深度上限默认 8**：曾是方案主体（按用户 p99 = 6 校准），后发现它是工作量的代理指标且边际收益小（仅省 0.4s / 1.9 万候选），被 BFS + count cap 取代，降级为可选逃生口。
4. **只扫「历史父目录一层」（955 候选的浅扫方案）**：曾是主方案，被用户否决——「希望树是我所有的目录结构」；实测证明全树可行后吸收为锚点优先级第一级。
5. **加权融合两层分数**：frecency（0.003..306）与模糊分不可通约，加权公式是假精度且无 ground truth 可调；改为排序插层。
6. **trie / 倒排索引**：模糊匹配是子序列匹配（`bln` 命中 `billing-engine`），前缀结构无用；nucleo 线性扫描处理百万级无压力。
7. **补光式第二光源**（来自立方体工作的教训，方法论条目）：直觉方案需实测检验——本项目多次出现直觉与实测相反的情况。
8. **跳过全部隐藏目录**：曾提议（可省至 34,622 个 / 0.81s），被用户否决——隐藏目录有真实 `cd` 目标；实测确认（`.claude-ctf-workspace` 15 次），改为按名字点名剪枝。

## 已知边界（诚实清单）

- 剪枝名单内的子树不可见（刻意）；
- 病态大树由 count cap 截最深尾部（失败模式是「最不可能的 5 万名之后不存在」，而非「某层以下一律不存在」）；
- `$HOME` 和锚点之外的世界不存在（全盘找路径仍是 fd + fzf 的活，cdh 不抢——候选集小、所以排序有意义，这是 cdh 的核心价值，灌整个文件系统会毁掉它）；
- 冷缓存 / 慢挂载首批到达慢（流式保证历史层秒开）；
- `/mnt` 深层每次启动部分覆盖；
- 发现层的正确用法是打字过滤，而非翻页浏览 4 万行；
- **补扫的 count cap 是每次扫描独立的，候选池总量没有全局上界**：`spawn_subtree` 用的
  `CANDIDATE_CAP` 是单次扫描的上限，启动扫描已经吃满 5 万时再取消一次排除，池子可以涨到
  10 万，多次取消可以继续叠。实践上被撤销的子树都不大（用户点名撤销的东西自己心里有数），
  但「取消排除 `~`」这种操作没有任何东西拦着。要设全局上界的话，得先想清楚超限时丢谁——
  丢补扫结果会让撤销显得没生效，丢已有候选又会动到用户正在看的列表，所以暂不做，先记在这里。
- 排除清单的补扫按单根跑：取消排除时不重跑整轮扫描（启动那轮的剪枝集合在 spawn 时就定死了，且整轮重扫要再花一个 5 秒预算），只以该目录为根扫一遍。代价是它拿不到「历史锚点兄弟」那类跨根的优先级偏置——但那批本来就已经在池子里了。

## 测试与验证要求

- 扫描器用 tempdir 造树，验证剪枝 / BFS 顺序 / count cap / 隐藏保留 / 不跟随符号链接；
- 排序分层、去重、空查询顺序不变、批次并入保选中、`Ctrl+D` 安全、非交互退 2；
- 至少两条变异验证（破坏实现以确认测试真会失败——本项目已两次吃过「断言两向都过」的亏：防裁切测试曾对任意尺寸恒真、光照测试曾把缺陷编码为正确）；
- 空历史自举用 tmux 真终端实测；
- 性能数字实测对账验收门。