Debug assert in IntervalTree.h:209 (is_valid) whenever 64+ URLs are autodetected

[steffen-heil-secforge]

Windows Terminal version

Self-built Debug x64 from main (reproduced on 1282d56a3 and on current d0263b86a)

Windows build number

10.0.26100.0

Other Software

No response

Steps to reproduce

assert(is_valid().first) in oss/interval_tree/IntervalTree.h:209 fires in Debug builds as soon as the pattern interval tree holds 64 or more intervals, i.e. whenever 64+ URLs are autodetected on/around the screen.

In the app:

1. Build Debug|x64 and deploy CascadiaPackage.
2. Leave Automatically detect URLs and make them clickable at its default (on).
3. Emit at least 64 URLs, e.g. in cmd.exe:

   for /l %i in (1,1,80) do @echo https://example.com/%i
   

4. The assertion dialog appears as soon as Terminal::UpdatePatternsUnderLock rebuilds the tree.

Minimal standalone repro (no Terminal build needed — real til::point, real vendored header):

#define USE_INTERVAL_TREE_NAMESPACE
#include <til/point.h>
#include <IntervalTree.h>

using PointTree = interval_tree::IntervalTree<til::point, size_t>;

PointTree::interval_vector intervals;
for (int y = 0; y < 64; ++y)                        // 63 passes, 64 asserts
{
    intervals.push_back(PointTree::interval({ 0, y }, { 10, y }, 0));
}
PointTree tree{ std::move(intervals) };             // <-- assert fires here

Printing the sentinels first shows the cause directly:

std::numeric_limits<til::point>::is_specialized = false
std::numeric_limits<til::point>::max() = {0,0}
std::numeric_limits<til::point>::min() = {0,0}

Expected Behavior

The tree's own consistency check should pass for a correctly built tree. Terminal::_getPatterns produces a perfectly valid tree — a corrected validator accepts it across 300+ randomised interval sets plus shaped cases (one URL per row, several per row, URLs wrapping across rows) — so nothing should assert.

Actual Behavior

Assertion failed!

Program: ...Microsoft.Terminal.Control.dll
File: ...\oss\interval_tree\IntervalTree.h
Line: 209

Expression: is_valid().first

Release builds are unaffected (assert compiles out), and the tree itself is structurally sound, so this is a false alarm rather than corruption — but it makes Debug builds unusable for anyone whose screen contains a page of links.

Analysis

is_valid() seeds its bounds accumulators with std::numeric_limits<Scalar>::max() / ::min():

std::pair<bool, std::pair<Scalar, Scalar>> result = { true, { std::numeric_limits<Scalar>::max(),
                                                              std::numeric_limits<Scalar>::min() } };

We instantiate the tree with Scalar = til::point, which has no std::numeric_limits specialization. The unspecialized primary template returns a default-constructed value from both max() and min(), so both sentinels are til::point{0,0} (verified above: is_specialized == false).

result.second.second is therefore {0,0}, and the right-subtree constraint check

if (valid.second.first <= center) { result.first = false; return result; }

evaluates {0,0} <= center, which is true for essentially any real tree — so is_valid() returns false and the assert fires.

The tree only builds children when it holds at least minbucket (64) intervals, which is why the threshold is exactly 64 — 63 intervals stay in a single leaf bucket and pass. Terminal::UpdatePatternsUnderLock scans roughly three viewport-heights of buffer, so 64 matches is easy to reach.

There is a second, independent bug in the same function. Lines 344/351/367 use std::min where the running maximum stop is intended:

result.second.second = std::min(result.second.second, minmaxStop.second->stop);

This is why upstream never trips over it: with a real numeric_limits, result.second.second stays pinned at numeric_limits<Scalar>::min() forever, and the max-stop half of the validation silently degrades into a no-op. So even a std::numeric_limits<til::point> specialization would only paper over the assert while leaving that check dead.

Provenance

To be fair to both sides of the vendoring boundary ("upstream" below always means the third-party library ekg/intervaltree, never this repo):

• is_valid() in oss/interval_tree/IntervalTree.h is character-for-character identical (whitespace-normalised) to ekg/intervaltree master, and that master is byte-identical (11829 bytes) to the commit pinned in cgmanifest.json, aa5937755000f1cd007402d03b6f7ce4427c5d21. The defective function is third-party code, unchanged by us.
• However, our vendored copy is not the unmodified wholesale import that MAINTAINER_README.md describes. Comparing the two files at token level (comments and whitespace stripped) yields exactly 10 semantic differences, and all 10 come from the still-open ekg/intervaltree PR #31 — "Allow user-defined structs as keys to the interval tree", opened 2020-10-01 by @PankajBhojwani: == 0 → == Scalar{} in six places, center() instead of center(0), and the added Interval(), operator== and operator!=. ekg/intervaltree master still reads Scalar leftextent = 0 / if (leftextent == 0 && ...).
• That adaptation is what makes a non-arithmetic Scalar such as til::point usable at all — but it did not update is_valid(), which still assumes an arithmetic Scalar. So the failure mode is third-party code reached through a local, never-upstreamed adaptation.

Two practical consequences for whoever picks this up:

• cgmanifest.json pins a commit whose content does not match the vendored file, so the provenance data does not describe what actually ships. Worth correcting alongside the fix.
• Following MAINTAINER_README.md literally — re-importing IntervalTree.h wholesale from ekg/intervaltree — would silently revert PR Background color reverted when clicking 'Properties' #31's struct-key support and break the build, since til::point cannot be compared against 0. That trap is worth writing down in the README regardless of how this bug is fixed. (The 2022 "Update IntervalTree.h dependency" Update IntervalTree.h dependency #14148 avoided it only because it was a one-line cherry-pick of #include <limits> rather than a re-import.)

Waiting for a third-party fix to ingest does not look viable: ekg/intervaltree's last commit is 2021-03-11, it has 7 open PRs (the oldest from 2014) and open issues back to 2016, and PR #31 has had no review comment in nearly six years. Note also that its last commit is upstream PR #32 (include <limits> for numeric_limits), which is exactly what #14148 already cherry-picked — so this repo is already current with everything ekg/intervaltree has ever shipped. There is nothing left to ingest.

I could not find an existing report of this in either repository.

Possible fixes

1. Fix is_valid() in the vendored header: drop the numeric_limits sentinels (track emptiness explicitly) and use std::max for the running max-stop, then record the deviation in MAINTAINER_README.md alongside PR Background color reverted when clicking 'Properties' #31's. I have this working locally — the assert passes and the check becomes genuinely meaningful (confirmed non-vacuous by inverting the constraint and observing it fail). Since the file already deviates from ekg/intervaltree by ten PR-Background color reverted when clicking 'Properties' #31 tokens, this documents an existing divergence rather than creating the first one.
2. Specialize std::numeric_limits<til::point> and leave the vendored header untouched. Silences the assert but, per the std::min bug above, leaves the max-stop check a permanent no-op.

Happy to send a PR for whichever you prefer.