TernarySearchTree.deleteSuperstr deletes unrelated sibling keys
- Dominant language
- TypeScript
- Stars
- 193k
- Forks
- 42.4k
- PR merge metrics
- PR metrics pending
Description
### Bug description
`TernarySearchTree.deleteSuperstr` (`src/vs/base/common/ternarySearchTree.ts`) clears all three child links when it finds the node holding the prefix:
```ts
if (superStr) {
// removing children, reset height
node.left = undefined;
node.mid = undefined;
node.right = undefined;
```
Only the `mid` chain holds superstrings (keys extending the prefix). `left` and `right` hold unrelated keys that merely sort around that character position, so wiping them deletes entries that are not superstrings of the deleted prefix at all. The repo's own tests already pin the intended semantics elsewhere (`deleteSuperstr('/user/fo')` must be a no-op for `/user/foo`, and sibling survival is asserted in other scenarios), but no test covers a sibling sitting at the terminal node.
Minimal repro with a forStrings trie:
1. `set('d', 1); set('e', 2);`
2. `deleteSuperstr('d')`
3. The trie now holds only `d`; `e` is gone.
With config-shaped keys: after `set('config.editor.fontSize')`, `set('config.editor.formatOnSave')`, `set('config.files.autoSave')`, calling `deleteSuperstr('config.editor')` empties the whole trie instead of keeping `config.files.autoSave`.
### Steps to reproduce
Run the three-line script above against any build, or observe context key values: the sole production caller (`contextKeyService.ts`) calls `deleteSuperstr` on the cached `config.*` trie whenever non-default-source settings change, which drops unrelated cached values, omits them from the fired change event's key list, and leaves them missing from `collectAllValues()` until something recomputes them.
### Expected behavior
Only the `mid` subtree is removed; `left` and `right` siblings stay intact.
Contributor guide
Assessment
This issue has not been assessed yet.