meta_language/
incremental.rs

1use std::collections::{BTreeMap, BTreeSet};
2use std::sync::Arc;
3
4use crate::{
5    tree_sitter_adapter, ByteRange, Link, LinkId, LinkMetadata, LinkNetwork, LinkType,
6    ParseConfiguration,
7};
8
9impl LinkNetwork {
10    /// Applies a byte-range source edit and reparses the network.
11    ///
12    /// Tree-sitter-backed languages use tree-sitter's incremental parse path;
13    /// other languages fall back to the built-in lossless parser. Links whose
14    /// source spans are outside the replaced byte range keep their identifiers.
15    pub fn apply_edit(&mut self, range: ByteRange, replacement: &str) -> bool {
16        self.apply_edit_with_configuration(range, replacement, ParseConfiguration::default())
17    }
18
19    /// Applies a byte-range source edit using an explicit parse configuration.
20    ///
21    /// Returns `false` when the range is outside the reconstructed source text,
22    /// splits a UTF-8 code point, or the network has no document language.
23    pub fn apply_edit_with_configuration(
24        &mut self,
25        range: ByteRange,
26        replacement: &str,
27        configuration: ParseConfiguration,
28    ) -> bool {
29        let old_text = self.reconstruct_text();
30        let Some(edited_text) = apply_text_edit(&old_text, range, replacement) else {
31            return false;
32        };
33        let Some(language) = document_language(self).map(ToOwned::to_owned) else {
34            return false;
35        };
36
37        let reparsed = tree_sitter_adapter::parse_incremental(
38            &old_text,
39            range,
40            replacement,
41            &language,
42            configuration,
43        )
44        .unwrap_or_else(|| Self::parse(&edited_text, &language, configuration));
45
46        let edit = AppliedEdit::new(range, replacement.len());
47        *self = remap_reparsed_network(self, &reparsed, edit);
48        true
49    }
50}
51
52fn document_language(network: &LinkNetwork) -> Option<&str> {
53    network
54        .links()
55        .find(|link| link.metadata().link_type() == Some(LinkType::Document))
56        .and_then(|link| link.metadata().language())
57}
58
59fn remap_reparsed_network(
60    old: &LinkNetwork,
61    reparsed: &LinkNetwork,
62    edit: AppliedEdit,
63) -> LinkNetwork {
64    let mut id_map = stable_id_map(old, reparsed, edit);
65    let mut used_targets = id_map.values().copied().collect::<BTreeSet<_>>();
66    let mut next_id = old.next_id.max(reparsed.next_id);
67
68    for link in reparsed.links() {
69        if id_map.contains_key(&link.id()) {
70            continue;
71        }
72
73        let target = if used_targets.contains(&link.id()) {
74            let fresh = next_unused_id(&mut next_id, &used_targets);
75            used_targets.insert(fresh);
76            fresh
77        } else {
78            used_targets.insert(link.id());
79            link.id()
80        };
81        id_map.insert(link.id(), target);
82    }
83
84    let mut links = BTreeMap::new();
85    for link in reparsed.links() {
86        let id = id_map[&link.id()];
87        let references = link
88            .references()
89            .iter()
90            .map(|reference| id_map[reference])
91            .collect::<Vec<_>>();
92        let candidate = Link {
93            id,
94            references: Arc::from(references),
95            metadata: link.metadata().clone(),
96        };
97
98        if let Some(shared) = old.links.get(&id) {
99            if shared.as_ref() == &candidate {
100                links.insert(id, Arc::clone(shared));
101                continue;
102            }
103        }
104
105        links.insert(id, Arc::new(candidate));
106    }
107
108    let terms = reparsed
109        .terms
110        .iter()
111        .filter_map(|(term, id)| id_map.get(id).map(|mapped| (Arc::clone(term), *mapped)))
112        .collect();
113    let next_id = used_targets
114        .iter()
115        .map(|id| id.as_u64())
116        .max()
117        .map_or(1, |id| id + 1);
118
119    LinkNetwork {
120        next_id,
121        links,
122        terms,
123        concept_syntax: reparsed.concept_syntax.clone(),
124        strings: reparsed.strings.clone(),
125    }
126}
127
128fn stable_id_map(
129    old: &LinkNetwork,
130    reparsed: &LinkNetwork,
131    edit: AppliedEdit,
132) -> BTreeMap<LinkId, LinkId> {
133    let old_links = old.links().collect::<Vec<_>>();
134    let mut mapped = BTreeMap::new();
135    let mut used_old = BTreeSet::new();
136
137    for new_link in reparsed.links() {
138        let Some(old_link) = old_links.iter().find(|old_link| {
139            !used_old.contains(&old_link.id())
140                && stable_span_or_point_match(old_link, new_link, edit)
141        }) else {
142            continue;
143        };
144        mapped.insert(new_link.id(), old_link.id());
145        used_old.insert(old_link.id());
146    }
147
148    loop {
149        let mut added = false;
150        for new_link in reparsed.links() {
151            if mapped.contains_key(&new_link.id()) || new_link.metadata().span().is_some() {
152                continue;
153            }
154            let Some(old_link) = old_links.iter().find(|old_link| {
155                !used_old.contains(&old_link.id())
156                    && stable_reference_match(old_link, new_link, &mapped)
157            }) else {
158                continue;
159            };
160            mapped.insert(new_link.id(), old_link.id());
161            used_old.insert(old_link.id());
162            added = true;
163        }
164        if !added {
165            break;
166        }
167    }
168
169    mapped
170}
171
172fn apply_text_edit(old_text: &str, range: ByteRange, replacement: &str) -> Option<String> {
173    if range.end() > old_text.len()
174        || !old_text.is_char_boundary(range.start())
175        || !old_text.is_char_boundary(range.end())
176    {
177        return None;
178    }
179
180    let mut edited =
181        String::with_capacity(old_text.len() - (range.end() - range.start()) + replacement.len());
182    edited.push_str(&old_text[..range.start()]);
183    edited.push_str(replacement);
184    edited.push_str(&old_text[range.end()..]);
185    Some(edited)
186}
187
188fn next_unused_id(next_id: &mut u64, used_targets: &BTreeSet<LinkId>) -> LinkId {
189    loop {
190        let candidate = LinkId(*next_id);
191        *next_id += 1;
192        if !used_targets.contains(&candidate) {
193            return candidate;
194        }
195    }
196}
197
198fn stable_span_or_point_match(old: &Link, new: &Link, edit: AppliedEdit) -> bool {
199    if !metadata_without_span_eq(old.metadata(), new.metadata()) {
200        return false;
201    }
202
203    match (old.metadata().span(), new.metadata().span()) {
204        (Some(old_span), Some(new_span)) => edit
205            .adjusted_range(old_span.byte_range())
206            .is_some_and(|range| range == new_span.byte_range()),
207        (None, None) => {
208            old.references() == new.references()
209                || (is_self_reference(old) && is_self_reference(new))
210        }
211        _ => false,
212    }
213}
214
215fn stable_reference_match(old: &Link, new: &Link, stable_map: &BTreeMap<LinkId, LinkId>) -> bool {
216    if old.metadata().span().is_some()
217        || new.metadata().span().is_some()
218        || !metadata_without_span_eq(old.metadata(), new.metadata())
219        || old.references().len() != new.references().len()
220    {
221        return false;
222    }
223
224    new.references()
225        .iter()
226        .zip(old.references())
227        .all(|(new_reference, old_reference)| stable_map.get(new_reference) == Some(old_reference))
228}
229
230fn metadata_without_span_eq(old: &LinkMetadata, new: &LinkMetadata) -> bool {
231    old.link_type() == new.link_type()
232        && old.is_named() == new.is_named()
233        && old.term() == new.term()
234        && old.definition() == new.definition()
235        && old.language() == new.language()
236        && old.flags() == new.flags()
237}
238
239fn is_self_reference(link: &Link) -> bool {
240    link.references() == [link.id()]
241}
242
243#[derive(Clone, Copy, Debug, PartialEq, Eq)]
244struct AppliedEdit {
245    old_start: usize,
246    old_end: usize,
247    new_end: usize,
248}
249
250impl AppliedEdit {
251    const fn new(range: ByteRange, replacement_len: usize) -> Self {
252        Self {
253            old_start: range.start(),
254            old_end: range.end(),
255            new_end: range.start() + replacement_len,
256        }
257    }
258
259    const fn adjusted_range(self, range: ByteRange) -> Option<ByteRange> {
260        if range.end() <= self.old_start {
261            return Some(range);
262        }
263        if range.start() < self.old_end {
264            return None;
265        }
266
267        let start = shift_byte(range.start(), self.old_end, self.new_end);
268        let end = shift_byte(range.end(), self.old_end, self.new_end);
269        Some(ByteRange::new(start, end))
270    }
271}
272
273const fn shift_byte(byte: usize, old_end: usize, new_end: usize) -> usize {
274    if new_end >= old_end {
275        byte + (new_end - old_end)
276    } else {
277        byte - (old_end - new_end)
278    }
279}
meta_language/incremental.rs

meta_language/
incremental.rs
