microsoft / microsoft/vscode

TernarySearchTree.has reports true for strict prefixes of stored keys

Open
#332,721 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.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

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.