Unnamed repository; edit this file 'description' to name the repository.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//! Like [`std::time::Instant`], but for memory.
//!
//! Measures the total size of all currently allocated objects.
use std::fmt;

use cfg_if::cfg_if;

#[derive(Copy, Clone)]
pub struct MemoryUsage {
    pub allocated: Bytes,
}

impl fmt::Display for MemoryUsage {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        self.allocated.fmt(f)
    }
}

impl std::ops::Sub for MemoryUsage {
    type Output = MemoryUsage;
    fn sub(self, rhs: MemoryUsage) -> MemoryUsage {
        MemoryUsage { allocated: self.allocated - rhs.allocated }
    }
}

impl MemoryUsage {
    pub fn now() -> MemoryUsage {
        cfg_if! {
            if #[cfg(all(feature = "jemalloc", not(target_env = "msvc")))] {
                jemalloc_ctl::epoch::advance().unwrap();
                MemoryUsage {
                    allocated: Bytes(jemalloc_ctl::stats::allocated::read().unwrap() as isize),
                }
            } else if #[cfg(all(target_os = "linux", target_env = "gnu"))] {
                memusage_linux()
            } else if #[cfg(windows)] {
                // There doesn't seem to be an API for determining heap usage, so we try to
                // approximate that by using the Commit Charge value.

                use windows_sys::Win32::System::{Threading::*, ProcessStatus::*};
                use std::mem::{MaybeUninit, size_of};

                let proc = unsafe { GetCurrentProcess() };
                let mut mem_counters = MaybeUninit::uninit();
                let cb = size_of::<PROCESS_MEMORY_COUNTERS>();
                let ret = unsafe { GetProcessMemoryInfo(proc, mem_counters.as_mut_ptr(), cb as u32) };
                assert!(ret != 0);

                let usage = unsafe { mem_counters.assume_init().PagefileUsage };
                MemoryUsage { allocated: Bytes(usage as isize) }
            } else {
                MemoryUsage { allocated: Bytes(0) }
            }
        }
    }
}

#[cfg(all(target_os = "linux", target_env = "gnu", not(feature = "jemalloc")))]
fn memusage_linux() -> MemoryUsage {
    // Linux/glibc has 2 APIs for allocator introspection that we can use: mallinfo and mallinfo2.
    // mallinfo uses `int` fields and cannot handle memory usage exceeding 2 GB.
    // mallinfo2 is very recent, so its presence needs to be detected at runtime.
    // Both are abysmally slow.

    use std::sync::atomic::{AtomicUsize, Ordering};

    static MALLINFO2: AtomicUsize = AtomicUsize::new(1);

    let mut mallinfo2 = MALLINFO2.load(Ordering::Relaxed);
    if mallinfo2 == 1 {
        mallinfo2 = unsafe { libc::dlsym(libc::RTLD_DEFAULT, c"mallinfo2".as_ptr()) } as usize;
        // NB: races don't matter here, since they'll always store the same value
        MALLINFO2.store(mallinfo2, Ordering::Relaxed);
    }

    if mallinfo2 == 0 {
        // mallinfo2 does not exist, use mallinfo.
        let alloc = unsafe { libc::mallinfo() }.uordblks as isize;
        MemoryUsage { allocated: Bytes(alloc) }
    } else {
        let mallinfo2: fn() -> libc::mallinfo2 = unsafe { std::mem::transmute(mallinfo2) };
        let alloc = mallinfo2().uordblks as isize;
        MemoryUsage { allocated: Bytes(alloc) }
    }
}

#[derive(Default, PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy)]
pub struct Bytes(isize);

impl Bytes {
    pub fn new(bytes: isize) -> Bytes {
        Bytes(bytes)
    }
}

impl Bytes {
    pub fn megabytes(self) -> isize {
        self.0 / 1024 / 1024
    }
}

impl fmt::Display for Bytes {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let bytes = self.0;
        let mut value = bytes;
        let mut suffix = "b";
        if value.abs() > 4096 {
            value /= 1024;
            suffix = "kb";
            if value.abs() > 4096 {
                value /= 1024;
                suffix = "mb";
            }
        }
        f.pad(&format!("{value}{suffix}"))
    }
}

impl std::ops::AddAssign<usize> for Bytes {
    fn add_assign(&mut self, x: usize) {
        self.0 += x as isize;
    }
}

impl std::ops::Sub for Bytes {
    type Output = Bytes;
    fn sub(self, rhs: Bytes) -> Bytes {
        Bytes(self.0 - rhs.0)
    }
}
97' href='#n297'>297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367
//! Implementation of applying changes to a syntax tree.

use std::{cmp::Ordering, collections::VecDeque, ops::RangeInclusive};

use rowan::TextRange;
use rustc_hash::FxHashMap;

use crate::{
    syntax_editor::{mapping::MissingMapping, Change, ChangeKind, PositionRepr},
    SyntaxElement, SyntaxNode, SyntaxNodePtr,
};

use super::{SyntaxEdit, SyntaxEditor};

pub(super) fn apply_edits(editor: SyntaxEditor) -> SyntaxEdit {
    // Algorithm overview:
    //
    // - Sort changes by (range, type)
    //   - Ensures that parent edits are before child edits
    //   - Ensures that inserts will be guaranteed to be inserted at the right range
    // - Validate changes
    //   - Checking for invalid changes is easy since the changes will be sorted by range
    // - Fixup change targets
    //   - standalone change? map to original syntax tree
    //   - dependent change?
    //     - try to map to parent change (either independent or another dependent)
    //     - note: need to keep track of a parent change stack, since a change can be a parent of multiple changes
    // - Apply changes
    //   - find changes to apply to real tree by applying nested changes first
    //   - changed nodes become part of the changed node set (useful for the formatter to only change those parts)
    // - Propagate annotations

    let SyntaxEditor { root, mut changes, mappings, annotations } = editor;

    let mut node_depths = FxHashMap::<SyntaxNode, usize>::default();
    let mut get_node_depth = |node: SyntaxNode| {
        *node_depths.entry(node).or_insert_with_key(|node| node.ancestors().count())
    };

    // Sort changes by range, then depth, then change kind, so that we can:
    // - ensure that parent edits are ordered before child edits
    // - ensure that inserts will be guaranteed to be inserted at the right range
    // - easily check for disjoint replace ranges
    changes.sort_by(|a, b| {
        a.target_range()
            .start()
            .cmp(&b.target_range().start())
            .then_with(|| {
                let a_target = a.target_parent();
                let b_target = b.target_parent();

                if a_target == b_target {
                    return Ordering::Equal;
                }

                get_node_depth(a_target).cmp(&get_node_depth(b_target))
            })
            .then(a.change_kind().cmp(&b.change_kind()))
    });

    let disjoint_replaces_ranges = changes
        .iter()
        .zip(changes.iter().skip(1))
        .filter(|(l, r)| {
            // We only care about checking for disjoint replace ranges
            matches!(
                (l.change_kind(), r.change_kind()),
                (
                    ChangeKind::Replace | ChangeKind::ReplaceRange,
                    ChangeKind::Replace | ChangeKind::ReplaceRange
                )
            )
        })
        .all(|(l, r)| {
            get_node_depth(l.target_parent()) != get_node_depth(r.target_parent())
                || l.target_range().intersect(r.target_range()).is_none()
        });

    if stdx::never!(
        !disjoint_replaces_ranges,
        "some replace change ranges intersect: {:?}",
        changes
    ) {
        return SyntaxEdit {
            old_root: root.clone(),
            new_root: root,
            annotations: Default::default(),
            changed_elements: vec![],
        };
    }

    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
    struct DependentChange {
        parent: u32,
        child: u32,
    }

    // Build change tree
    let mut changed_ancestors: VecDeque<ChangedAncestor> = VecDeque::new();
    let mut dependent_changes = vec![];
    let mut independent_changes = vec![];

    for (change_index, change) in changes.iter().enumerate() {
        // Check if this change is dependent on another change (i.e. it's contained within another range)
        if let Some(index) = changed_ancestors
            .iter()
            .rev()
            .position(|ancestor| ancestor.affected_range().contains_range(change.target_range()))
        {
            // Pop off any ancestors that aren't applicable
            changed_ancestors.drain((index + 1)..);

            // FIXME: Resolve changes that depend on a range of elements
            let ancestor = &changed_ancestors[index];

            dependent_changes.push(DependentChange {
                parent: ancestor.change_index as u32,
                child: change_index as u32,
            });
        } else {
            // This change is independent of any other change

            // Drain the changed ancestors since we're no longer in a set of dependent changes
            changed_ancestors.drain(..);

            independent_changes.push(change_index as u32);
        }

        // Add to changed ancestors, if applicable
        match change {
            Change::Insert(_, _) | Change::InsertAll(_, _) => {}
            Change::Replace(target, _) | Change::ReplaceWithMany(target, _) => {
                changed_ancestors.push_back(ChangedAncestor::single(target, change_index))
            }
            Change::ReplaceAll(range, _) => {
                changed_ancestors.push_back(ChangedAncestor::multiple(range, change_index))
            }
        }
    }

    // Map change targets to the correct syntax nodes
    let tree_mutator = TreeMutator::new(&root);
    let mut changed_elements = vec![];

    for index in independent_changes {
        match &mut changes[index as usize] {
            Change::Insert(target, _) | Change::InsertAll(target, _) => {
                match &mut target.repr {
                    PositionRepr::FirstChild(parent) => {
                        *parent = tree_mutator.make_syntax_mut(parent);
                    }
                    PositionRepr::After(child) => {
                        *child = tree_mutator.make_element_mut(child);
                    }
                };
            }
            Change::Replace(target, _) | Change::ReplaceWithMany(target, _) => {
                *target = tree_mutator.make_element_mut(target);
            }
            Change::ReplaceAll(range, _) => {
                let start = tree_mutator.make_element_mut(range.start());
                let end = tree_mutator.make_element_mut(range.end());

                *range = start..=end;
            }
        }

        // Collect changed elements
        match &changes[index as usize] {
            Change::Insert(_, element) => changed_elements.push(element.clone()),
            Change::InsertAll(_, elements) => changed_elements.extend(elements.iter().cloned()),
            Change::Replace(_, Some(element)) => changed_elements.push(element.clone()),
            Change::Replace(_, None) => {}
            Change::ReplaceWithMany(_, elements) => {
                changed_elements.extend(elements.iter().cloned())
            }
            Change::ReplaceAll(_, elements) => changed_elements.extend(elements.iter().cloned()),
        }
    }

    for DependentChange { parent, child } in dependent_changes.into_iter() {
        let (input_ancestor, output_ancestor) = match &changes[parent as usize] {
            // No change will depend on an insert since changes can only depend on nodes in the root tree
            Change::Insert(_, _) | Change::InsertAll(_, _) => unreachable!(),
            Change::Replace(target, Some(new_target)) => {
                (to_owning_node(target), to_owning_node(new_target))
            }
            // Silently drop outdated change
            Change::Replace(_, None) => continue,
            Change::ReplaceAll(_, _) | Change::ReplaceWithMany(_, _) => {
                unimplemented!("cannot resolve changes that depend on replacing many elements")
            }
        };

        let upmap_target_node = |target: &SyntaxNode| {
            match mappings.upmap_child(target, &input_ancestor, &output_ancestor) {
                Ok(it) => it,
                Err(MissingMapping(current)) => unreachable!("no mappings exist between {current:?} (ancestor of {input_ancestor:?}) and {output_ancestor:?}"),
            }
        };

        let upmap_target = |target: &SyntaxElement| {
            match mappings.upmap_child_element(target, &input_ancestor, &output_ancestor) {
                Ok(it) => it,
                Err(MissingMapping(current)) => unreachable!("no mappings exist between {current:?} (ancestor of {input_ancestor:?}) and {output_ancestor:?}"),
            }
        };

        match &mut changes[child as usize] {
            Change::Insert(target, _) | Change::InsertAll(target, _) => match &mut target.repr {
                PositionRepr::FirstChild(parent) => {
                    *parent = upmap_target_node(parent);
                }
                PositionRepr::After(child) => {
                    *child = upmap_target(child);
                }
            },
            Change::Replace(target, _) | Change::ReplaceWithMany(target, _) => {
                *target = upmap_target(target);
            }
            Change::ReplaceAll(range, _) => {
                *range = upmap_target(range.start())..=upmap_target(range.end());
            }
        }
    }

    // Apply changes
    let mut root = tree_mutator.mutable_clone;

    for change in changes {
        match change {
            Change::Insert(position, element) => {
                let (parent, index) = position.place();
                parent.splice_children(index..index, vec![element]);
            }
            Change::InsertAll(position, elements) => {
                let (parent, index) = position.place();
                parent.splice_children(index..index, elements);
            }
            Change::Replace(target, None) => {
                target.detach();
            }
            Change::Replace(SyntaxElement::Node(target), Some(new_target)) if target == root => {
                root = new_target.into_node().expect("root node replacement should be a node");
            }
            Change::Replace(target, Some(new_target)) => {
                let parent = target.parent().unwrap();
                parent.splice_children(target.index()..target.index() + 1, vec![new_target]);
            }
            Change::ReplaceWithMany(target, elements) => {
                let parent = target.parent().unwrap();
                parent.splice_children(target.index()..target.index() + 1, elements);
            }
            Change::ReplaceAll(range, elements) => {
                let start = range.start().index();
                let end = range.end().index();
                let parent = range.start().parent().unwrap();
                parent.splice_children(start..end + 1, elements);
            }
        }
    }

    // Propagate annotations
    let annotations = annotations.into_iter().filter_map(|(element, annotation)| {
        match mappings.upmap_element(&element, &root) {
            // Needed to follow the new tree to find the resulting element
            Some(Ok(mapped)) => Some((mapped, annotation)),
            // Element did not need to be mapped
            None => Some((element, annotation)),
            // Element did not make it to the final tree
            Some(Err(_)) => None,
        }
    });

    let mut annotation_groups = FxHashMap::default();

    for (element, annotation) in annotations {
        annotation_groups.entry(annotation).or_insert(vec![]).push(element);
    }

    SyntaxEdit {
        old_root: tree_mutator.immutable,
        new_root: root,
        changed_elements,
        annotations: annotation_groups,
    }
}

fn to_owning_node(element: &SyntaxElement) -> SyntaxNode {
    match element {
        SyntaxElement::Node(node) => node.clone(),
        SyntaxElement::Token(token) => token.parent().unwrap().clone(),
    }
}

struct ChangedAncestor {
    kind: ChangedAncestorKind,
    change_index: usize,
}

enum ChangedAncestorKind {
    Single { node: SyntaxNode },
    Range { _changed_elements: RangeInclusive<SyntaxElement>, _in_parent: SyntaxNode },
}

impl ChangedAncestor {
    fn single(element: &SyntaxElement, change_index: usize) -> Self {
        let kind = match element {
            SyntaxElement::Node(node) => ChangedAncestorKind::Single { node: node.clone() },
            SyntaxElement::Token(token) => {
                ChangedAncestorKind::Single { node: token.parent().unwrap() }
            }
        };

        Self { kind, change_index }
    }

    fn multiple(range: &RangeInclusive<SyntaxElement>, change_index: usize) -> Self {
        Self {
            kind: ChangedAncestorKind::Range {
                _changed_elements: range.clone(),
                _in_parent: range.start().parent().unwrap(),
            },
            change_index,
        }
    }

    fn affected_range(&self) -> TextRange {
        match &self.kind {
            ChangedAncestorKind::Single { node } => node.text_range(),
            ChangedAncestorKind::Range { _changed_elements: changed_nodes, _in_parent: _ } => {
                TextRange::new(
                    changed_nodes.start().text_range().start(),
                    changed_nodes.end().text_range().end(),
                )
            }
        }
    }
}

struct TreeMutator {
    immutable: SyntaxNode,
    mutable_clone: SyntaxNode,
}

impl TreeMutator {
    fn new(immutable: &SyntaxNode) -> TreeMutator {
        let immutable = immutable.clone();
        let mutable_clone = immutable.clone_for_update();
        TreeMutator { immutable, mutable_clone }
    }

    fn make_element_mut(&self, element: &SyntaxElement) -> SyntaxElement {
        match element {
            SyntaxElement::Node(node) => SyntaxElement::Node(self.make_syntax_mut(node)),
            SyntaxElement::Token(token) => {
                let parent = self.make_syntax_mut(&token.parent().unwrap());
                parent.children_with_tokens().nth(token.index()).unwrap()
            }
        }
    }

    fn make_syntax_mut(&self, node: &SyntaxNode) -> SyntaxNode {
        let ptr = SyntaxNodePtr::new(node);
        ptr.to_node(&self.mutable_clone)
    }
}