Code at the speed of thought – Zed is a high-performance, multiplayer code editor from the creators of Atom and Tree-sitter.
//! Bracket pair discovery for [`BufferSnapshot`]s.
//!
//! Bracket queries run per [`RowChunk`](super::row_chunk::RowChunk) and the results are
//! cached in [`TreeSitterData`](super::TreeSitterData) until the buffer is reparsed.
//! Tree-sitter error recovery can produce bogus or incomplete query matches, which are
//! repaired chunk-locally before caching, see [`ChunkBrackets`].
use std::{iter, ops::Range};
use collections::{HashMap, HashSet};
use text::{Bias, OffsetRangeExt, ToOffset};
use util::RangeExt;
use crate::{
BracketsConfig, BufferRow, BufferSnapshot, Grammar, GrammarId, TreeSitterOptions,
syntax_map::{MAX_BYTES_TO_QUERY, SyntaxLayer},
};
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct BracketMatch {
pub open_range: Range<usize>,
pub close_range: Range<usize>,
pub newline_only: bool,
pub syntax_layer_depth: usize,
pub color_index: Option<usize>,
}
impl BracketMatch {
pub fn bracket_ranges(self) -> (Range<usize>, Range<usize>) {
(self.open_range, self.close_range)
}
}
/// A single bracket pair candidate produced by a brackets query, before
/// bogus tree-sitter matches are repaired and color indices are assigned.
#[derive(Clone, Debug)]
struct BracketMatchCandidate {
bracket_match: BracketMatch,
pattern: BracketPatternKey,
rainbow_exclude: bool,
}
impl BracketMatchCandidate {
fn open_delimiter(&self) -> BracketDelimiter {
BracketDelimiter {
start: self.bracket_match.open_range.start,
end: self.bracket_match.open_range.end,
pattern: self.pattern,
}
}
fn close_delimiter(&self) -> BracketDelimiter {
BracketDelimiter {
start: self.bracket_match.close_range.start,
end: self.bracket_match.close_range.end,
pattern: self.pattern,
}
}
}
/// Identifies a brackets query pattern, unique across all grammars of a syntax map.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct BracketPatternKey {
grammar_index: usize,
pattern_index: usize,
}
/// One delimiter (open or close) of a bracket pair candidate.
/// Ordered by buffer position first, so sorting yields document order.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct BracketDelimiter {
start: usize,
end: usize,
pattern: BracketPatternKey,
}
type BracketDelimiterPair = (BracketDelimiter, BracketDelimiter);
impl BufferSnapshot {
/// Finds all [`super::row_chunk::RowChunks`] applicable to the given range, then returns all bracket pairs that intersect with those chunks.
/// Hence, may return more bracket pairs than the range contains.
///
/// Will omit known chunks.
/// The resulting bracket match collections are not ordered.
pub fn fetch_bracket_ranges(
&self,
range: Range<usize>,
known_chunks: Option<&HashSet<Range<BufferRow>>>,
) -> HashMap<Range<BufferRow>, Vec<BracketMatch>> {
let mut all_bracket_matches = HashMap::default();
if self
.language
.as_ref()
.is_none_or(|language| language.grammar().is_none())
{
return all_bracket_matches;
}
for chunk in self
.tree_sitter_data
.chunks
.applicable_chunks(&[range.to_point(self)])
{
if known_chunks.is_some_and(|chunks| chunks.contains(&chunk.row_range())) {
continue;
}
if let Some(cached_brackets) = self
.tree_sitter_data
.brackets_by_chunks
.lock()
.get(&chunk.id)
{
all_bracket_matches.insert(chunk.row_range(), cached_brackets.clone());
continue;
}
let chunk_range = chunk.anchor_range().to_offset(self);
let chunk_brackets = self.chunk_bracket_matches(chunk_range);
self.tree_sitter_data
.brackets_by_chunks
.lock()
.entry(chunk.id)
.or_insert_with(|| chunk_brackets.clone());
all_bracket_matches.insert(chunk.row_range(), chunk_brackets);
}
all_bracket_matches
}
fn chunk_bracket_matches(&self, chunk_range: Range<usize>) -> Vec<BracketMatch> {
let mut chunk_brackets = ChunkBrackets::new(self, chunk_range);
chunk_brackets.collect_queried_candidates(self);
chunk_brackets.recover_error_node_delimiters();
chunk_brackets.repair_bogus_patterns();
chunk_brackets.deduplicate_overlapping_patterns();
chunk_brackets.into_colorized_matches()
}
pub fn all_bracket_ranges(&self, range: Range<usize>) -> impl Iterator<Item = BracketMatch> {
self.fetch_bracket_ranges(range.clone(), None)
.into_values()
.flatten()
.filter(move |bracket_match| {
let bracket_range = bracket_match.open_range.start..bracket_match.close_range.end;
bracket_range.overlaps(&range)
})
}
/// Returns bracket range pairs overlapping or adjacent to `range`
pub fn bracket_ranges<T: ToOffset>(
&self,
range: Range<T>,
) -> impl Iterator<Item = BracketMatch> + '_ {
// Find bracket pairs that *inclusively* contain the given range.
let range = range.start.to_previous_offset(self)..range.end.to_next_offset(self);
self.all_bracket_ranges(range)
.filter(|pair| !pair.newline_only)
}
/// Returns enclosing bracket ranges containing the given range
pub fn enclosing_bracket_ranges<T: ToOffset>(
&self,
range: Range<T>,
) -> impl Iterator<Item = BracketMatch> + '_ {
let range = range.start.to_offset(self)..range.end.to_offset(self);
let result: Vec<_> = self.bracket_ranges(range.clone()).collect();
let max_depth = result
.iter()
.map(|mat| mat.syntax_layer_depth)
.max()
.unwrap_or(0);
result.into_iter().filter(move |pair| {
pair.open_range.start <= range.start
&& pair.close_range.end >= range.end
&& pair.syntax_layer_depth == max_depth
})
}
/// Returns the smallest enclosing bracket ranges containing the given range or None if no brackets contain range
///
/// Can optionally pass a range_filter to filter the ranges of brackets to consider
pub fn innermost_enclosing_bracket_ranges<T: ToOffset>(
&self,
range: Range<T>,
range_filter: Option<&dyn Fn(Range<usize>, Range<usize>) -> bool>,
) -> Option<(Range<usize>, Range<usize>)> {
let range = range.start.to_offset(self)..range.end.to_offset(self);
// Get the ranges of the innermost pair of brackets.
let mut result: Option<(Range<usize>, Range<usize>)> = None;
for pair in self.enclosing_bracket_ranges(range) {
if let Some(range_filter) = range_filter
&& !range_filter(pair.open_range.clone(), pair.close_range.clone())
{
continue;
}
let len = pair.close_range.end - pair.open_range.start;
if let Some((existing_open, existing_close)) = &result {
let existing_len = existing_close.end - existing_open.start;
if len > existing_len {
continue;
}
}
result = Some((pair.open_range, pair.close_range));
}
result
}
}
/// Bracket pair candidates of a single row chunk, in the middle of being repaired.
///
/// Tree-sitter error recovery makes bracket queries unreliable in two ways: a query
/// can match one open delimiter against several closes (bogus patterns), and it can
/// omit delimiters that only exist as concrete leaves inside ERROR nodes (incomplete
/// patterns). Affected patterns are re-paired chunk-locally, while trustworthy query
/// output is kept as is.
struct ChunkBrackets<'a> {
chunk_range: Range<usize>,
error_layers: Vec<SyntaxLayer<'a>>,
grammar_ids: Vec<GrammarId>,
configs: Vec<&'a BracketsConfig>,
candidates: Vec<BracketMatchCandidate>,
delimiter_kinds_by_pattern: HashMap<BracketPatternKey, (HashSet<u16>, HashSet<u16>)>,
syntax_layer_depths_by_delimiter: HashMap<BracketDelimiter, usize>,
bogus_patterns: HashSet<BracketPatternKey>,
incomplete_patterns: HashSet<BracketPatternKey>,
syntax_opens_by_pattern: HashMap<BracketPatternKey, HashSet<BracketDelimiter>>,
syntax_closes_by_pattern: HashMap<BracketPatternKey, HashSet<BracketDelimiter>>,
}
impl<'a> ChunkBrackets<'a> {
fn new(snapshot: &'a BufferSnapshot, chunk_range: Range<usize>) -> Self {
let error_layers = snapshot
.syntax
.layers_for_range(chunk_range.clone(), &snapshot.text, true)
.filter(|layer| layer.node().has_error())
.collect::<Vec<_>>();
Self {
chunk_range,
error_layers,
grammar_ids: Vec::new(),
configs: Vec::new(),
candidates: Vec::new(),
delimiter_kinds_by_pattern: HashMap::default(),
syntax_layer_depths_by_delimiter: HashMap::default(),
bogus_patterns: HashSet::default(),
incomplete_patterns: HashSet::default(),
syntax_opens_by_pattern: HashMap::default(),
syntax_closes_by_pattern: HashMap::default(),
}
}
/// Runs the bracket queries and collects pair candidates overlapping the chunk,
/// marking patterns that pair one open delimiter with several closes as bogus.
fn collect_queried_candidates(&mut self, snapshot: &'a BufferSnapshot) {
let bounded_query = (
self.chunk_range.clone(),
TreeSitterOptions {
max_bytes_to_query: Some(MAX_BYTES_TO_QUERY),
max_start_depth: None,
},
);
// The bounded query drops any pair spanning more than `MAX_BYTES_TO_QUERY`
// (tree-sitter's containing byte range requires full containment), which
// resets bracket depth at chunk boundaries. Every such pair encloses a
// chunk edge, so recover them with two point-sized unbounded queries that
// only traverse the syntax tree spine around each edge.
let boundary_queries = [self.chunk_range.start, self.chunk_range.end].map(|offset| {
(
snapshot.clip_offset(offset.saturating_sub(1), Bias::Left)
..snapshot.clip_offset(offset.saturating_add(1), Bias::Right),
TreeSitterOptions::default(),
)
});
let mut seen_pairs = HashSet::default();
// Track the close seen for each open delimiter: a second, different close
// for the same open means the pattern's matches cannot be trusted.
let mut close_by_open = HashMap::default();
for (query_range, options) in iter::once(bounded_query).chain(boundary_queries) {
let mut matches = snapshot.syntax.matches_with_options(
query_range,
&snapshot.text,
options,
|grammar| grammar.brackets_config.as_ref().map(|c| &c.query),
);
let grammar_indices = matches
.grammars()
.iter()
.map(|grammar| self.grammar_index(grammar))
.collect::<Vec<_>>();
while let Some(mat) = matches.peek() {
let mut open = None;
let mut close = None;
let syntax_layer_depth = mat.depth;
let grammar_index = grammar_indices[mat.grammar_index];
let pattern_key = BracketPatternKey {
grammar_index,
pattern_index: mat.pattern_index,
};
let config = self.configs[grammar_index];
let pattern = &config.patterns[mat.pattern_index];
for capture in mat.captures {
if capture.index == config.open_capture_ix {
open = Some((capture.node.byte_range(), capture.node.kind_id()));
} else if capture.index == config.close_capture_ix {
close = Some((capture.node.byte_range(), capture.node.kind_id()));
}
}
matches.advance();
let Some(((open_range, open_kind), (close_range, close_kind))) = open.zip(close)
else {
continue;
};
let bracket_range = open_range.start..=close_range.end;
if !bracket_range.overlaps(&self.chunk_range) {
continue;
}
let candidate = BracketMatchCandidate {
bracket_match: BracketMatch {
open_range,
close_range,
syntax_layer_depth,
newline_only: pattern.newline_only,
color_index: None,
},
pattern: pattern_key,
rainbow_exclude: pattern.rainbow_exclude,
};
if !self.error_layers.is_empty() {
let (open_kinds, close_kinds) = self
.delimiter_kinds_by_pattern
.entry(pattern_key)
.or_insert_with(|| (HashSet::default(), HashSet::default()));
open_kinds.insert(open_kind);
close_kinds.insert(close_kind);
}
if !seen_pairs.insert((candidate.open_delimiter(), candidate.close_delimiter())) {
continue;
}
if close_by_open
.insert(candidate.open_delimiter(), candidate.close_delimiter())
.is_some()
{
self.bogus_patterns.insert(pattern_key);
}
self.candidates.push(candidate);
}
}
}
fn grammar_index(&mut self, grammar: &'a Grammar) -> usize {
self.grammar_ids
.iter()
.position(|&id| id == grammar.id())
.unwrap_or_else(|| {
self.grammar_ids.push(grammar.id());
self.configs.push(grammar.brackets_config.as_ref().unwrap());
self.grammar_ids.len() - 1
})
}
/// Bracket queries can omit delimiters swallowed by tree-sitter error recovery.
/// Collects the concrete delimiter leaves inside ERROR nodes and marks the
/// patterns whose query output misses some of them as incomplete (and bogus).
fn recover_error_node_delimiters(&mut self) {
let unambiguous_kinds = self.unambiguous_delimiter_kinds();
self.collect_error_layer_delimiters(&unambiguous_kinds);
self.mark_incomplete_patterns(&unambiguous_kinds);
}
/// Patterns whose open and close delimiters map to exactly one distinct
/// syntax-node kind each, making their leaves recognizable inside ERROR nodes.
fn unambiguous_delimiter_kinds(&self) -> Vec<(BracketPatternKey, u16, u16)> {
self.delimiter_kinds_by_pattern
.iter()
.filter_map(|(pattern, (open_kinds, close_kinds))| {
// Kinds are observed from this chunk's matches only: a pattern
// alternating several delimiter tokens may pass this check when just
// one alternative occurs in the chunk, and a pattern whose every
// match was swallowed by an error is never recovered at all.
if open_kinds.len() != 1 || close_kinds.len() != 1 {
return None;
}
let open_kind = *open_kinds.iter().next()?;
let close_kind = *close_kinds.iter().next()?;
// Syntax leaves cannot distinguish the two roles of delimiters such as quotes.
(open_kind != close_kind).then_some((*pattern, open_kind, close_kind))
})
.collect()
}
fn collect_error_layer_delimiters(
&mut self,
unambiguous_kinds: &[(BracketPatternKey, u16, u16)],
) {
if unambiguous_kinds.is_empty() {
return;
}
for layer in &self.error_layers {
let Some(grammar) = layer.language.grammar() else {
continue;
};
let Some(grammar_index) = self.grammar_ids.iter().position(|&id| id == grammar.id())
else {
continue;
};
let relevant_patterns = unambiguous_kinds
.iter()
.filter(|(pattern, _, _)| pattern.grammar_index == grammar_index)
.collect::<Vec<_>>();
if relevant_patterns.is_empty() {
continue;
}
let root_node = layer.node();
let mut cursor = root_node.walk();
let mut nodes = vec![(root_node, false)];
while let Some((node, inside_error)) = nodes.pop() {
let node_range = node.byte_range();
if node_range.end <= self.chunk_range.start
|| node_range.start >= self.chunk_range.end
{
continue;
}
let inside_error = inside_error || node.is_error();
if !inside_error && !node.has_error() {
continue;
}
if node.child_count() == 0 {
if !inside_error
|| node_range.is_empty()
|| !self.chunk_range.contains(&node_range.start)
{
continue;
}
for (pattern, open_kind, close_kind) in &relevant_patterns {
let delimiters_by_pattern = if node.kind_id() == *open_kind {
&mut self.syntax_opens_by_pattern
} else if node.kind_id() == *close_kind {
&mut self.syntax_closes_by_pattern
} else {
continue;
};
let delimiter = BracketDelimiter {
start: node_range.start,
end: node_range.end,
pattern: *pattern,
};
delimiters_by_pattern
.entry(*pattern)
.or_default()
.insert(delimiter);
self.syntax_layer_depths_by_delimiter
.entry(delimiter)
.or_insert(layer.depth);
}
} else {
nodes.extend(
node.children(&mut cursor)
.map(|child| (child, inside_error)),
);
}
}
}
}
fn mark_incomplete_patterns(&mut self, unambiguous_kinds: &[(BracketPatternKey, u16, u16)]) {
for (pattern, _, _) in unambiguous_kinds {
// Recovery needs both delimiter roles inside this chunk's ERROR nodes;
// a pair split between an ERROR node and a regular node is left as queried.
let Some(syntax_opens) = self.syntax_opens_by_pattern.get(pattern) else {
continue;
};
let Some(syntax_closes) = self.syntax_closes_by_pattern.get(pattern) else {
continue;
};
// A count mismatch means some delimiter genuinely lacks a partner while the
// user is editing; repairing would invent one. Balanced counts can still pair
// unrelated stray delimiters, which is accepted as best-effort recovery.
if syntax_opens.len() != syntax_closes.len() {
continue;
}
let query_opens = self
.candidates
.iter()
.filter(|candidate| candidate.pattern == *pattern)
.map(|candidate| candidate.open_delimiter())
.filter(|open| self.chunk_range.contains(&open.start))
.collect::<HashSet<_>>();
let query_closes = self
.candidates
.iter()
.filter(|candidate| candidate.pattern == *pattern)
.map(|candidate| candidate.close_delimiter())
.filter(|close| self.chunk_range.contains(&close.start))
.collect::<HashSet<_>>();
let has_missing_open = !syntax_opens.is_subset(&query_opens);
let has_missing_close = !syntax_closes.is_subset(&query_closes);
if has_missing_open || has_missing_close {
self.bogus_patterns.insert(*pattern);
self.incomplete_patterns.insert(*pattern);
}
}
}
/// Certain patterns produce bogus or incomplete matches during error recovery.
/// Repairs only those patterns, keeping trustworthy grammar output intact:
/// clean patterns may legitimately pair an open in one chunk with a close in
/// another, and must not be dropped by the chunk-local repair.
fn repair_bogus_patterns(&mut self) {
if self.bogus_patterns.is_empty() {
return;
}
for candidate in bogus_candidates(&self.candidates, &self.bogus_patterns) {
let syntax_layer_depth = candidate.bracket_match.syntax_layer_depth;
self.syntax_layer_depths_by_delimiter
.entry(candidate.open_delimiter())
.or_insert(syntax_layer_depth);
self.syntax_layer_depths_by_delimiter
.entry(candidate.close_delimiter())
.or_insert(syntax_layer_depth);
}
let pair_counts = self.bogus_pair_counts();
let mut existing_pairs = bogus_candidates(&self.candidates, &self.bogus_patterns)
.map(|candidate| (candidate.open_delimiter(), candidate.close_delimiter()))
.collect::<HashSet<_>>();
let mut valid_pairs = self.stack_matched_pairs(&pair_counts, &mut existing_pairs);
self.trust_cross_chunk_pairs(&pair_counts, &mut valid_pairs);
self.replace_bogus_pairs(valid_pairs, existing_pairs);
}
/// A cross-product of bogus matches multiply pairs its delimiters, while
/// structural error-recovery pairs stay uniquely paired and can be trusted.
fn bogus_pair_counts(&self) -> DelimiterPairCounts {
let mut counts = DelimiterPairCounts::default();
for candidate in bogus_candidates(&self.candidates, &self.bogus_patterns) {
*counts
.opens
.entry(candidate.open_delimiter())
.or_insert(0_usize) += 1;
*counts
.closes
.entry(candidate.close_delimiter())
.or_insert(0_usize) += 1;
}
counts
}
// Tree-sitter represents missing error-recovery tokens as empty nodes.
fn is_concrete(&self, delimiter: &BracketDelimiter) -> bool {
delimiter.start < delimiter.end || !self.incomplete_patterns.contains(&delimiter.pattern)
}
/// The concrete delimiters of bogus patterns that lie within the chunk, augmented
/// with the ones recovered from ERROR nodes, sorted in document order.
fn repairable_delimiters(
&self,
mut delimiters: Vec<BracketDelimiter>,
syntax_delimiters_by_pattern: &HashMap<BracketPatternKey, HashSet<BracketDelimiter>>,
) -> Vec<BracketDelimiter> {
delimiters.retain(|delimiter| {
self.chunk_range.contains(&delimiter.start) && self.is_concrete(delimiter)
});
for pattern in &self.incomplete_patterns {
if let Some(syntax_delimiters) = syntax_delimiters_by_pattern.get(pattern) {
delimiters.extend(syntax_delimiters.iter().copied());
}
}
delimiters.sort_unstable();
delimiters.dedup();
delimiters
}
/// Re-pairs the chunk-local delimiters of bogus patterns with a stack walk in
/// document order. A close without any open on its stack gets one inferred right
/// before it, unless the grammar paired it with an open beyond the chunk.
fn stack_matched_pairs(
&mut self,
pair_counts: &DelimiterPairCounts,
existing_pairs: &mut HashSet<BracketDelimiterPair>,
) -> HashSet<BracketDelimiterPair> {
// Map each close to its expected open length (for inferring opens)
let close_to_open_len = bogus_candidates(&self.candidates, &self.bogus_patterns)
.map(|candidate| {
(
candidate.close_delimiter(),
candidate.bracket_match.open_range.len(),
)
})
.collect::<HashMap<_, _>>();
let sorted_opens = self.repairable_delimiters(
bogus_candidates(&self.candidates, &self.bogus_patterns)
.map(|candidate| candidate.open_delimiter())
.collect(),
&self.syntax_opens_by_pattern,
);
let unique_closes = self.repairable_delimiters(
bogus_candidates(&self.candidates, &self.bogus_patterns)
.map(|candidate| candidate.close_delimiter())
.collect(),
&self.syntax_closes_by_pattern,
);
let closes_with_cross_chunk_opens =
bogus_candidates(&self.candidates, &self.bogus_patterns)
.filter(|candidate| {
!self
.chunk_range
.contains(&candidate.bracket_match.open_range.start)
&& pair_counts.uniquely_paired(
&candidate.open_delimiter(),
&candidate.close_delimiter(),
)
})
.map(|candidate| candidate.close_delimiter())
.collect::<HashSet<_>>();
let mut valid_pairs = HashSet::default();
let mut open_stacks = HashMap::default();
let mut open_idx = 0;
for close in &unique_closes {
// Push all opens before this close onto stack
while open_idx < sorted_opens.len() && sorted_opens[open_idx].start < close.start {
let open = sorted_opens[open_idx];
open_stacks
.entry(open.pattern)
.or_insert_with(Vec::new)
.push(open);
open_idx += 1;
}
// Try to match with most recent open
if let Some(open) = open_stacks
.get_mut(&close.pattern)
.and_then(|open_stack| open_stack.pop())
{
valid_pairs.insert((open, *close));
} else if !closes_with_cross_chunk_opens.contains(close)
&& let Some(&open_len) = close_to_open_len.get(close)
{
// No open on stack and the grammar offers no open beyond the
// chunk either - infer one based on expected open_len
if close.start >= open_len {
let inferred = BracketDelimiter {
start: close.start - open_len,
end: close.start,
pattern: close.pattern,
};
valid_pairs.insert((inferred, *close));
existing_pairs.insert((inferred, *close));
let syntax_layer_depth = self
.syntax_layer_depths_by_delimiter
.get(close)
.copied()
.unwrap_or(0);
self.syntax_layer_depths_by_delimiter
.entry(inferred)
.or_insert(syntax_layer_depth);
let pattern = &self.configs[close.pattern.grammar_index].patterns
[close.pattern.pattern_index];
self.candidates.push(BracketMatchCandidate {
bracket_match: BracketMatch {
open_range: inferred.start..inferred.end,
close_range: close.start..close.end,
newline_only: pattern.newline_only,
syntax_layer_depth,
color_index: None,
},
pattern: close.pattern,
rainbow_exclude: pattern.rainbow_exclude,
});
}
}
}
valid_pairs
}
/// Pairs with a delimiter outside the chunk (boundary queries recover
/// those to keep bracket depth stable across chunks) cannot be verified
/// by the chunk-local stack: the delimiters beyond the chunk are unknown.
/// Trust grammar output for whichever remained unmatched, but only
/// uniquely paired ones: cross-product bogosity multiply pairs delimiters.
fn trust_cross_chunk_pairs(
&self,
pair_counts: &DelimiterPairCounts,
valid_pairs: &mut HashSet<BracketDelimiterPair>,
) {
let matched_opens = valid_pairs
.iter()
.map(|(open, _)| *open)
.collect::<HashSet<_>>();
let matched_closes = valid_pairs
.iter()
.map(|(_, close)| *close)
.collect::<HashSet<_>>();
for candidate in bogus_candidates(&self.candidates, &self.bogus_patterns) {
let open = candidate.open_delimiter();
let close = candidate.close_delimiter();
let open_inside = self.chunk_range.contains(&open.start);
let close_inside = self.chunk_range.contains(&close.start);
let crosses_chunk = !open_inside || !close_inside;
let unmatched = (!open_inside || !matched_opens.contains(&open))
&& (!close_inside || !matched_closes.contains(&close));
if crosses_chunk
&& unmatched
&& pair_counts.uniquely_paired(&open, &close)
&& self.is_concrete(&open)
&& self.is_concrete(&close)
{
valid_pairs.insert((open, close));
}
}
}
/// Drops the bogus candidates that did not survive the repair and adds
/// candidates for the repaired pairs that the queries never produced.
fn replace_bogus_pairs(
&mut self,
valid_pairs: HashSet<BracketDelimiterPair>,
existing_pairs: HashSet<BracketDelimiterPair>,
) {
let mut repaired_pairs = valid_pairs
.iter()
.filter(|pair| !existing_pairs.contains(*pair))
.copied()
.collect::<Vec<_>>();
repaired_pairs.sort_unstable();
for (open, close) in repaired_pairs {
let pattern =
&self.configs[open.pattern.grammar_index].patterns[open.pattern.pattern_index];
self.candidates.push(BracketMatchCandidate {
bracket_match: BracketMatch {
open_range: open.start..open.end,
close_range: close.start..close.end,
newline_only: pattern.newline_only,
syntax_layer_depth: self
.syntax_layer_depths_by_delimiter
.get(&open)
.copied()
.or_else(|| self.syntax_layer_depths_by_delimiter.get(&close).copied())
.unwrap_or(0),
color_index: None,
},
pattern: open.pattern,
rainbow_exclude: pattern.rainbow_exclude,
});
}
let bogus_patterns = &self.bogus_patterns;
self.candidates.retain(|candidate| {
!bogus_patterns.contains(&candidate.pattern)
|| valid_pairs.contains(&(candidate.open_delimiter(), candidate.close_delimiter()))
});
}
/// Overlapping query patterns can attribute one physical pair to several
/// patterns, both when queried and when repaired. Keeps the first match,
/// following the pattern order in the query.
fn deduplicate_overlapping_patterns(&mut self) {
let mut seen_ranges = HashSet::default();
self.candidates.retain(|candidate| {
seen_ranges.insert((
candidate.bracket_match.open_range.start,
candidate.bracket_match.open_range.end,
candidate.bracket_match.close_range.start,
candidate.bracket_match.close_range.end,
))
});
}
/// Assigns nesting-depth color indices and returns the matches sorted by open range.
fn into_colorized_matches(self) -> Vec<BracketMatch> {
let mut opens = Vec::new();
let mut color_pairs = Vec::new();
let mut all_brackets = self
.candidates
.into_iter()
.enumerate()
.map(|(index, candidate)| {
let bracket_match = candidate.bracket_match;
// Certain languages have "brackets" that are not brackets, e.g. tags. and such
// bracket will match the entire tag with all text inside.
// For now, avoid highlighting any pair that has more than single char in each bracket.
// We need to colorize `<Element/>` bracket pairs, so cannot make this check stricter.
let should_color = !candidate.rainbow_exclude
&& (bracket_match.open_range.len() == 1
|| bracket_match.close_range.len() == 1);
if should_color {
opens.push(bracket_match.open_range.clone());
color_pairs.push((
bracket_match.open_range.clone(),
bracket_match.close_range.clone(),
index,
));
}
bracket_match
})
.collect::<Vec<_>>();
opens.sort_unstable_by_key(|r| (r.start, r.end));
opens.dedup_by(|a, b| a.start == b.start && a.end == b.end);
color_pairs.sort_by_key(|(_, close, _)| close.end);
let mut open_stack = Vec::new();
let mut open_index = 0;
for (open, close, index) in color_pairs {
while open_index < opens.len() && opens[open_index].start < close.start {
open_stack.push(opens[open_index].clone());
open_index += 1;
}
if open_stack.last() == Some(&open) {
let depth_index = open_stack.len() - 1;
all_brackets[index].color_index = Some(depth_index);
open_stack.pop();
}
}
all_brackets.sort_by_key(|bracket_match| {
(bracket_match.open_range.start, bracket_match.open_range.end)
});
all_brackets
}
}
fn bogus_candidates<'a>(
candidates: &'a [BracketMatchCandidate],
bogus_patterns: &'a HashSet<BracketPatternKey>,
) -> impl Iterator<Item = &'a BracketMatchCandidate> {
candidates
.iter()
.filter(|candidate| bogus_patterns.contains(&candidate.pattern))
}
#[derive(Default)]
struct DelimiterPairCounts {
opens: HashMap<BracketDelimiter, usize>,
closes: HashMap<BracketDelimiter, usize>,
}
impl DelimiterPairCounts {
fn uniquely_paired(&self, open: &BracketDelimiter, close: &BracketDelimiter) -> bool {
self.opens.get(open) == Some(&1) && self.closes.get(close) == Some(&1)
}
}