meta_language/
incremental.rs

1use std::collections::{BTreeMap, BTreeSet, VecDeque};
2use std::sync::Arc;
3
4use crate::{
5    ByteRange, Link, LinkId, LinkMetadata, LinkNetwork, LinkType, ParseConfiguration,
6    tree_sitter_adapter,
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    keep_tied_sibling_order(reparsed, &mut id_map, &mut used_targets, &mut next_id);
84
85    let mut links = BTreeMap::new();
86    for link in reparsed.links() {
87        let id = id_map[&link.id()];
88        let references = link
89            .references()
90            .iter()
91            .map(|reference| id_map[reference])
92            .collect::<Vec<_>>();
93        let candidate = Link {
94            id,
95            references: Arc::from(references),
96            metadata: link.metadata().clone(),
97        };
98
99        if let Some(shared) = old.links.get(&id)
100            && shared.as_ref() == &candidate
101        {
102            links.insert(id, Arc::clone(shared));
103            continue;
104        }
105
106        links.insert(id, Arc::new(candidate));
107    }
108
109    let terms = reparsed
110        .terms
111        .iter()
112        .filter_map(|(term, id)| id_map.get(id).map(|mapped| (Arc::clone(term), *mapped)))
113        .collect();
114    let next_id = used_targets
115        .iter()
116        .map(|id| id.as_u64())
117        .max()
118        .map_or(1, |id| id + 1);
119
120    LinkNetwork {
121        next_id,
122        links,
123        terms,
124        concept_syntax: reparsed.concept_syntax.clone(),
125        strings: reparsed.strings.clone(),
126    }
127}
128
129fn stable_id_map(
130    old: &LinkNetwork,
131    reparsed: &LinkNetwork,
132    edit: AppliedEdit,
133) -> BTreeMap<LinkId, LinkId> {
134    let mut old_links = OldLinkIndex::new(old, edit);
135    let mut mapped = BTreeMap::new();
136
137    for new_link in reparsed.links() {
138        let key = MatchKey::of(new_link.metadata());
139        let matched = match new_link.metadata().span() {
140            Some(span) => old_links.take_spanned(key, span.byte_range()),
141            None => old_links.take_unspanned(key, new_link),
142        };
143        if let Some(old_id) = matched {
144            mapped.insert(new_link.id(), old_id);
145        }
146    }
147
148    // A link without a span is recognized by the identifiers it references, so
149    // it can only be matched once everything it references has been. Repeat
150    // until a round maps nothing new.
151    let mut pending = reparsed
152        .links()
153        .filter(|link| link.metadata().span().is_none() && !mapped.contains_key(&link.id()))
154        .collect::<Vec<_>>();
155    while !pending.is_empty() {
156        let remaining = pending.len();
157        let mut unmatched = Vec::with_capacity(remaining);
158        for new_link in pending {
159            let matched = new_link
160                .references()
161                .iter()
162                .map(|reference| mapped.get(reference).copied())
163                .collect::<Option<Vec<_>>>()
164                .and_then(|references| {
165                    old_links.take_referencing(MatchKey::of(new_link.metadata()), references)
166                });
167            match matched {
168                Some(old_id) => {
169                    mapped.insert(new_link.id(), old_id);
170                }
171                None => unmatched.push(new_link),
172            }
173        }
174        if unmatched.len() == remaining {
175            break;
176        }
177        pending = unmatched;
178    }
179
180    mapped
181}
182
183/// Metadata two links must share to keep one identifier, shaped as a map key so
184/// that candidates can be looked up instead of searched for.
185#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
186struct MatchKey<'a> {
187    link_type: Option<LinkType>,
188    named: bool,
189    term: Option<&'a str>,
190    definition: Option<&'a str>,
191    language: Option<&'a str>,
192    /// Parse flags spelled out as booleans, because `LinkFlags` carries no
193    /// ordering of its own.
194    flags: (bool, bool, bool, bool),
195}
196
197impl<'a> MatchKey<'a> {
198    fn of(metadata: &'a LinkMetadata) -> Self {
199        let flags = metadata.flags();
200        Self {
201            link_type: metadata.link_type(),
202            named: metadata.is_named(),
203            term: metadata.term(),
204            definition: metadata.definition(),
205            language: metadata.language(),
206            flags: (
207                flags.is_error(),
208                flags.has_error(),
209                flags.is_missing(),
210                flags.is_extra(),
211            ),
212        }
213    }
214}
215
216/// Identifiers of the previous network's links, grouped by everything a match
217/// requires.
218///
219/// Reparsing produces about as many links as the previous parse held, so
220/// searching every old link for every new one costs `O(old * new)` and made a
221/// 15 KB edit take twenty seconds (issue #193). Every group keeps its links in
222/// ascending identifier order and hands them out from the front, which is the
223/// link a search over `old.links()` would have stopped at first.
224struct OldLinkIndex<'a> {
225    /// Links carrying a span, keyed by the span the edit moves them to.
226    spanned: BTreeMap<(MatchKey<'a>, usize, usize), VecDeque<LinkId>>,
227    /// Links carrying no span, keyed by the identifiers they reference.
228    referencing: BTreeMap<(MatchKey<'a>, Vec<LinkId>), VecDeque<LinkId>>,
229    /// Links carrying no span that reference themselves and nothing else.
230    self_referencing: BTreeMap<MatchKey<'a>, VecDeque<LinkId>>,
231    /// Links already handed out, which every group skips.
232    used: BTreeSet<LinkId>,
233}
234
235impl<'a> OldLinkIndex<'a> {
236    fn new(old: &'a LinkNetwork, edit: AppliedEdit) -> Self {
237        let mut index = Self {
238            spanned: BTreeMap::new(),
239            referencing: BTreeMap::new(),
240            self_referencing: BTreeMap::new(),
241            used: BTreeSet::new(),
242        };
243
244        for link in old.links() {
245            let key = MatchKey::of(link.metadata());
246            if let Some(span) = link.metadata().span() {
247                // Links the edit overlaps cannot keep their identifier.
248                if let Some(range) = edit.adjusted_range(span.byte_range()) {
249                    index
250                        .spanned
251                        .entry((key, range.start(), range.end()))
252                        .or_default()
253                        .push_back(link.id());
254                }
255                continue;
256            }
257
258            index
259                .referencing
260                .entry((key, link.references().to_vec()))
261                .or_default()
262                .push_back(link.id());
263            if is_self_reference(link) {
264                index
265                    .self_referencing
266                    .entry(key)
267                    .or_default()
268                    .push_back(link.id());
269            }
270        }
271
272        index
273    }
274
275    /// Identifier of an unused old link whose shifted span is `range`.
276    fn take_spanned(&mut self, key: MatchKey<'a>, range: ByteRange) -> Option<LinkId> {
277        let matched = Self::front(
278            self.spanned.get_mut(&(key, range.start(), range.end())),
279            &self.used,
280        )?;
281        self.used.insert(matched);
282        Some(matched)
283    }
284
285    /// Identifier of an unused old link that carries no span and either
286    /// references exactly what `new_link` references or, when `new_link`
287    /// references only itself, references only itself as well.
288    fn take_unspanned(&mut self, key: MatchKey<'a>, new_link: &Link) -> Option<LinkId> {
289        let by_references = Self::front(
290            self.referencing
291                .get_mut(&(key, new_link.references().to_vec())),
292            &self.used,
293        );
294        let by_self_reference = if is_self_reference(new_link) {
295            Self::front(self.self_referencing.get_mut(&key), &self.used)
296        } else {
297            None
298        };
299
300        // A search over `old.links()` would have stopped at whichever of the
301        // two candidates was inserted first, which is the smaller identifier.
302        let matched = by_references.into_iter().chain(by_self_reference).min()?;
303        self.used.insert(matched);
304        Some(matched)
305    }
306
307    /// Identifier of an unused old link that carries no span and references
308    /// exactly `references`.
309    fn take_referencing(&mut self, key: MatchKey<'a>, references: Vec<LinkId>) -> Option<LinkId> {
310        let matched = Self::front(self.referencing.get_mut(&(key, references)), &self.used)?;
311        self.used.insert(matched);
312        Some(matched)
313    }
314
315    /// First unused identifier in `group`, dropping the used ones it skips.
316    fn front(group: Option<&mut VecDeque<LinkId>>, used: &BTreeSet<LinkId>) -> Option<LinkId> {
317        let group = group?;
318        while group.front().is_some_and(|id| used.contains(id)) {
319            group.pop_front();
320        }
321        group.front().copied()
322    }
323}
324
325fn apply_text_edit(old_text: &str, range: ByteRange, replacement: &str) -> Option<String> {
326    if range.end() > old_text.len()
327        || !old_text.is_char_boundary(range.start())
328        || !old_text.is_char_boundary(range.end())
329    {
330        return None;
331    }
332
333    let mut edited =
334        String::with_capacity(old_text.len() - (range.end() - range.start()) + replacement.len());
335    edited.push_str(&old_text[..range.start()]);
336    edited.push_str(replacement);
337    edited.push_str(&old_text[range.end()..]);
338    Some(edited)
339}
340
341/// Siblings that share a span keep their order by identifier (a zero-width
342/// MISSING leaf before another at the same point), as the network orders
343/// siblings by span, then identifier. Where the kept identifiers would reverse
344/// two of them, the later one gets a fresh identifier.
345fn keep_tied_sibling_order(
346    reparsed: &LinkNetwork,
347    id_map: &mut BTreeMap<LinkId, LinkId>,
348    used_targets: &mut BTreeSet<LinkId>,
349    next_id: &mut u64,
350) {
351    let mut ties: BTreeMap<(Vec<LinkId>, usize, usize), Vec<LinkId>> = BTreeMap::new();
352    for link in reparsed.links() {
353        if let Some(span) = link.metadata().span() {
354            let range = span.byte_range();
355            ties.entry((link.references().to_vec(), range.start(), range.end()))
356                .or_default()
357                .push(link.id());
358        }
359    }
360    for group in ties.values().filter(|group| group.len() > 1) {
361        let mut last: Option<LinkId> = None;
362        for id in group {
363            let target = id_map[id];
364            if last.is_some_and(|last| target <= last) {
365                let fresh = next_unused_id(next_id, used_targets);
366                used_targets.insert(fresh);
367                id_map.insert(*id, fresh);
368                last = Some(fresh);
369            } else {
370                last = Some(target);
371            }
372        }
373    }
374}
375
376fn next_unused_id(next_id: &mut u64, used_targets: &BTreeSet<LinkId>) -> LinkId {
377    loop {
378        let candidate = LinkId(*next_id);
379        *next_id += 1;
380        if !used_targets.contains(&candidate) {
381            return candidate;
382        }
383    }
384}
385
386fn is_self_reference(link: &Link) -> bool {
387    link.references() == [link.id()]
388}
389
390#[derive(Clone, Copy, Debug, PartialEq, Eq)]
391struct AppliedEdit {
392    old_start: usize,
393    old_end: usize,
394    new_end: usize,
395}
396
397impl AppliedEdit {
398    const fn new(range: ByteRange, replacement_len: usize) -> Self {
399        Self {
400            old_start: range.start(),
401            old_end: range.end(),
402            new_end: range.start() + replacement_len,
403        }
404    }
405
406    const fn adjusted_range(self, range: ByteRange) -> Option<ByteRange> {
407        if range.end() <= self.old_start {
408            return Some(range);
409        }
410        if range.start() < self.old_end {
411            return None;
412        }
413
414        let start = shift_byte(range.start(), self.old_end, self.new_end);
415        let end = shift_byte(range.end(), self.old_end, self.new_end);
416        Some(ByteRange::new(start, end))
417    }
418}
419
420const fn shift_byte(byte: usize, old_end: usize, new_end: usize) -> usize {
421    if new_end >= old_end {
422        byte + (new_end - old_end)
423    } else {
424        byte - (old_end - new_end)
425    }
426}
meta_language/incremental.rs

meta_language/
incremental.rs
