TernarySearchTree.has reports true for strict prefixes of stored keys
- Dominant language
- TypeScript
- Stars
- 193k
- Forks
- 42.4k
- PR merge metrics
- PR metrics pending
Description
### Bug description
`TernarySearchTree.has` (`src/vs/base/common/ternarySearchTree.ts`) returns:
```ts
return !(node?.value === undefined && node?.mid === undefined);
```
A key that is a strict prefix of a stored key lands on an intermediate node with `value === undefined` but `mid !== undefined`, and `has` reports true even though `get` returns undefined for that key. The separate `hasElementOrSubtree` method exists precisely for subtree-existence semantics, so exact-key membership is what `has` was meant to provide.
Minimal repro with a forStrings trie: `set('foobar', 1)` then `has('foo') === true`, `has('f') === true`, while `get('foo') === undefined`.
### Steps to reproduce
Two reachable effects:
1. `contextKeyService.ts` uses the trie for cached `config.*` context values and takes a `has` shortcut before falling back to the settings object: asking for `config.editor` after only `config.editor.fontSize` was cached yields `undefined` instead of the composed settings value.
2. `parcelWatcher.ts` classifies a request path as already watched when it is merely a prefix of another stored watch path, adding a redundant recursive watcher (request `/a/b` while `/a` and `/a/b/c` are stored).
### Expected behavior
`has(key)` agrees with `get(key) !== undefined`: only stored keys count.
Contributor guide
Assessment
This issue has not been assessed yet.