Augmented interval tree for efficient range queries over buffer decorations.
Backed by an AVL-balanced binary search tree where each node stores an
interval {start, end} keyed by the start position, and is augmented
with the maximum end position in its subtree. This augmentation enables
O(log n + k) stabbing and overlap queries, where n is the total number
of intervals and k is the number of results.
Interval representation
Intervals use {line, col} tuple positions, compared lexicographically.
Start is inclusive, end is exclusive: [start, end). This matches the
convention used by tree-sitter, LSP, and Zed's decoration system.
Performance characteristics
- Insert: O(log n) amortized (AVL rebalancing)
- Delete: O(log n) amortized
- Overlap query ("all intervals intersecting [qstart, qend)"): O(log n + k)
- Stabbing query ("all intervals containing point p"): O(log n + k)
- Bulk rebuild: O(n log n) from a list of intervals
The tree is optimized for the read path (queries every frame at 60fps) over the write path (decorations change on edits and sync, not every frame).
Design decisions
- Pure Elixir, no NIFs. The BEAM's per-process GC handles tree nodes without global pauses.
- AVL balancing (not red-black) for simpler implementation with the same O(log n) guarantees. The constant factor difference is irrelevant for our workload (thousands of nodes, not millions).
- Immutable: every mutation returns a new tree. This is the Elixir way and enables safe concurrent reads from the render pipeline while the buffer process updates decorations.
Summary
Types
An interval stored in the tree. start is inclusive, end_ is exclusive.
id is a unique reference for deletion. value is the associated data
(e.g., a highlight range struct).
A node in the AVL tree.
A position in the buffer: {line, col}, both 0-indexed.
Compared lexicographically (line first, then col).
The tree: either nil (empty) or a node.
Functions
Deletes the interval with the given ID from the tree.
Returns true if the tree is empty.
Builds an interval tree from a list of intervals.
Inserts an interval into the tree. Returns the new tree.
Applies a transformation function to every interval in the tree and rebuilds it. Used for bulk anchor adjustment after buffer edits.
Returns an empty interval tree.
Returns all intervals that overlap with the query range [query_start, query_end).
Returns all intervals that intersect any line in the range [start_line, end_line]
(both inclusive).
Returns the number of intervals in the tree.
Returns all intervals that contain the given point (stabbing query).
Converts the tree to a sorted list of intervals (in-order traversal).
Types
An interval stored in the tree. start is inclusive, end_ is exclusive.
id is a unique reference for deletion. value is the associated data
(e.g., a highlight range struct).
@type node_t() :: %{ interval: interval(), max_end: position(), left: t(), right: t(), height: non_neg_integer() }
A node in the AVL tree.
interval: the interval stored at this nodemax_end: the maximumend_position in this node's entire subtreeleft,right: child subtreesheight: AVL height for balance factor computation
@type position() :: {non_neg_integer(), non_neg_integer()}
A position in the buffer: {line, col}, both 0-indexed.
Compared lexicographically (line first, then col).
@type t() :: node_t() | nil
The tree: either nil (empty) or a node.
Functions
Deletes the interval with the given ID from the tree.
Returns the new tree. No-op if the ID is not found.
Returns true if the tree is empty.
Builds an interval tree from a list of intervals.
More efficient than repeated insert/2 calls: sorts once, then builds
a balanced tree via median splitting. O(n log n).
Inserts an interval into the tree. Returns the new tree.
The interval must have :id, :start, :end_, and :value keys.
Duplicate IDs are not checked; callers should ensure uniqueness.
Applies a transformation function to every interval in the tree and rebuilds it. Used for bulk anchor adjustment after buffer edits.
The function receives an interval and returns either {:keep, updated_interval}
or :remove (if the edit invalidated the interval, e.g., its entire
range was deleted).
Rebuilds from scratch via from_list/1 after transformation, which is
O(n log n). This is appropriate for edit-time updates (not per-frame).
@spec new() :: t()
Returns an empty interval tree.
Returns all intervals that overlap with the query range [query_start, query_end).
An interval [s, e) overlaps [qs, qe) when s < qe AND e > qs.
Runs in O(log n + k) where k is the number of results, thanks to the
max_end augmentation that prunes entire subtrees.
@spec query_lines(t(), non_neg_integer(), non_neg_integer()) :: [interval()]
Returns all intervals that intersect any line in the range [start_line, end_line]
(both inclusive).
This is the primary query for the render pipeline: "give me all decorations
that touch lines 50-80." It's a range query where the query range spans
from {start_line, 0} to {end_line + 1, 0}.
@spec size(t()) :: non_neg_integer()
Returns the number of intervals in the tree.
Returns all intervals that contain the given point (stabbing query).
A point p is contained by interval [s, e) when s <= p AND e > p.
This is equivalent to query(tree, p, {line, col + 1}) but expressed
more clearly for point queries.
Converts the tree to a sorted list of intervals (in-order traversal).