microsoft / microsoft/vscode

TernarySearchTree.deleteSuperstr deletes unrelated sibling keys

Open
#332,715 0 comments 0 reactions 1 assignee Claimed by @ulugbekna View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.