1use super::stored::Stored;
72use std::borrow::Cow;
73use std::collections::{BTreeMap, BTreeSet};
74
75use oneyaml_core::{Code, Diagnostic, Settings, Span};
76
77use super::arena::{Arena, Flat};
78use super::facts::{LONG_RUN, StreamFacts};
79use super::fragment::Fragment;
80use super::runs::{Marks, Piece, RunFacts, marks};
81use super::seq::{Run, RunAt, Seq};
82use super::slab::Slab;
83use super::validate::Removed;
84use super::{Extra, NONE, NodeId, StaleNode, SyntaxKind, SyntaxTree, cost};
85
86#[non_exhaustive]
92#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
93pub enum TreeEditError {
94 Stale(StaleNode),
96 NotANode {
98 kind: SyntaxKind,
100 },
101 NotAToken {
103 kind: SyntaxKind,
105 },
106 NoParent,
109 NotSiblings,
112 Position {
114 position: usize,
116 len: usize,
118 },
119 ReadOnly {
127 kind: SyntaxKind,
129 },
130 Misplaced {
133 kind: SyntaxKind,
135 parent: SyntaxKind,
137 },
138 TagContext,
141 InvalidToken {
144 kind: SyntaxKind,
146 },
147 Syntax {
149 code: Code,
151 },
152 EmptyFragment,
154 NotWellFormed,
159 Limit {
166 code: Code,
168 },
169 Capacity,
172 Internal,
174}
175
176impl core::fmt::Display for TreeEditError {
177 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
178 match self {
179 Self::Stale(s) => write!(f, "{s}"),
180 Self::NotANode { kind } => write!(f, "a {kind:?} token has no children"),
181 Self::NotAToken { kind } => write!(f, "a {kind:?} node is not a token"),
182 Self::NoParent => f.write_str("the stream root cannot be removed or given siblings"),
183 Self::NotSiblings => f.write_str("the range ends are not siblings in order"),
184 Self::Position { position, len } => {
185 write!(f, "position {position} is past the end ({len})")
186 }
187 Self::ReadOnly { kind } => write!(f, "a {kind:?} cannot be edited this way"),
188 Self::Misplaced { kind, parent } => {
189 write!(f, "a {kind:?} cannot be a child of a {parent:?}")
190 }
191 Self::TagContext => f.write_str(
192 "the fragment's tags were resolved under other %TAG directives than the target \
193 document's",
194 ),
195 Self::InvalidToken { kind } => {
196 write!(f, "the text does not read as exactly one {kind:?} token")
197 }
198 Self::Syntax { code } => write!(f, "the fragment text does not parse: {code}"),
199 Self::EmptyFragment => f.write_str("an empty fragment cannot be inserted"),
200 Self::NotWellFormed => f.write_str(
201 "the edit is not well-formed: its text would not read back as the edited tree",
202 ),
203 Self::Limit { code } => write!(f, "the edit would exceed a limit of the tree ({code})"),
204 Self::Capacity => f.write_str("the tree's element or byte capacity is exhausted"),
205 Self::Internal => f.write_str("internal error in the syntax tree (a bug)"),
206 }
207 }
208}
209
210impl std::error::Error for TreeEditError {}
211
212impl From<StaleNode> for TreeEditError {
213 fn from(s: StaleNode) -> Self {
214 Self::Stale(s)
215 }
216}
217
218#[non_exhaustive]
221#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
222pub struct Inserted {
223 pub first: NodeId,
225 pub last: NodeId,
227}
228
229#[non_exhaustive]
231#[must_use = "the removed elements are only kept in `removed`"]
232#[derive(Clone, Debug, PartialEq, Eq, Hash)]
233pub struct Replaced {
234 pub removed: Fragment,
236 pub inserted: Inserted,
238}
239
240#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
242pub(super) struct Links {
243 first: u32,
244 last: u32,
245 next: u32,
246 prev: u32,
247}
248
249#[derive(Clone, Debug)]
251pub(super) struct Grafted {
252 parent: u32,
254 arena: Arena,
255 facts: StreamFacts,
257 runs: RunFacts,
259}
260
261#[derive(Clone, Debug)]
264pub(super) struct Edits {
265 arenas: BTreeMap<u32, u32>,
278 grafts: Slab<Grafted>,
286 seq: Seq,
287 runs: BTreeMap<u32, u32>,
289 links: BTreeMap<u32, Links>,
292 dropped: BTreeSet<(u32, u32)>,
302 next_slot: u32,
303}
304
305impl Edits {
306 pub(super) const fn next_slot(&self) -> u32 {
308 self.next_slot
309 }
310
311 fn run_start(&self, item: u32) -> Option<u32> {
314 let run = self.seq.run(item)?;
315 run.arena.checked_add(run.a)
316 }
317
318 #[cfg(test)]
330 pub(super) fn heap_bytes(&self) -> usize {
331 use core::mem::size_of;
332 let entry = |k: usize, v: usize| k.saturating_add(v).saturating_add(16);
333 let times = |n: usize, each: usize| n.saturating_mul(each);
334 let mut parts = vec![
335 self.seq.heap_bytes(),
336 times(self.runs.len(), entry(4, 4)),
337 times(self.links.len(), entry(4, size_of::<Links>())),
338 times(self.dropped.len(), entry(8, 0)),
339 times(self.arenas.len(), entry(4, 4)),
340 self.grafts.heap_bytes(),
341 ];
342 for g in self.grafts.iter() {
343 let a = &g.arena;
344 parts.extend([
345 a.source.capacity(),
346 a.kinds.capacity(),
347 times(a.parents.capacity(), 4),
348 times(a.words.capacity(), 4),
349 times(a.extras.capacity(), size_of::<(u32, Extra)>()),
350 times(a.diagnostics.capacity(), size_of::<(u32, Stored)>()),
351 g.facts.heap_bytes(),
352 g.runs.heap_bytes(),
353 ]);
354 parts.extend(
355 a.diagnostics
356 .iter()
357 .map(|(_, d)| d.heap_bytes(diagnostic_heap_bytes)),
358 );
359 }
360 parts.into_iter().fold(0, usize::saturating_add)
361 }
362
363 pub(super) fn live_in(&self, lo: u32, hi: u32) -> bool {
366 let Some((&start, &item)) = self.runs.range(..hi).next_back() else {
367 return false;
368 };
369 let count = self.seq.run(item).map_or(0, |r| r.b.saturating_sub(r.a));
370 start.saturating_add(count) > lo
371 }
372
373 fn release(&mut self, doomed: &[(u32, Run)]) {
378 for &(key, run) in doomed {
379 let end = key.saturating_add(run.b.saturating_sub(run.a));
380 let dead: Vec<u32> = self.links.range(key..end).map(|(s, _)| *s).collect();
381 for s in dead {
382 self.links.remove(&s);
383 }
384 if !self.dropped.is_empty() {
385 let gone: Vec<(u32, u32)> =
386 self.dropped.range((key, 0)..(end, 0)).copied().collect();
387 for d in gone {
388 self.dropped.remove(&d);
389 }
390 }
391 if run.arena == 0 {
392 continue;
393 }
394 let len = self.graft(run.arena).map_or(0, |g| g.arena.kinds.len());
395 let limit = u32::try_from(len)
396 .ok()
397 .and_then(|l| run.arena.checked_add(l))
398 .unwrap_or(NONE);
399 if self.runs.range(run.arena..limit).next().is_none() {
400 self.drop_graft(run.arena, true);
401 }
402 }
403 }
404
405 fn graft(&self, first: u32) -> Option<&Grafted> {
407 cost::count(cost::Step::Lookup);
408 let at = *self.arenas.get(&first)?;
409 self.graft_at(at)
410 }
411
412 fn graft_at(&self, at: u32) -> Option<&Grafted> {
414 self.grafts.get(at)
415 }
416
417 fn add_graft(&mut self, first: u32, g: Grafted) -> Option<u32> {
421 let at = self.grafts.insert(g)?;
422 self.arenas.insert(first, at);
423 Some(at)
424 }
425
426 fn drop_graft(&mut self, first: u32, compact: bool) {
439 let Some(at) = self.arenas.remove(&first) else {
440 return;
441 };
442 let _ = self.grafts.remove(at);
443 let free = self.grafts.free_len();
444 let bound = self.arenas.len().max(16).max(self.seq.items_len() / 4);
445 if compact && free > bound {
446 let (grafts, map) = std::mem::take(&mut self.grafts).compacted();
447 self.grafts = grafts;
448 for at in self.arenas.values_mut() {
449 if let Some(&n) = map.get(*at as usize) {
450 *at = n;
451 }
452 }
453 self.seq.remap_grafts(&map);
454 }
455 }
456
457 fn merge_at(&mut self, slot: u32) {
460 let Some(&item) = self.runs.get(&slot) else {
461 return;
462 };
463 let (Some(right), Some(left_item)) = (self.seq.run(item), self.seq.prev(item)) else {
464 return;
465 };
466 let Some(left) = self.seq.run(left_item) else {
467 return;
468 };
469 if left.arena == right.arena && left.b == right.a {
470 let marks = left.marks.then(right.marks);
473 let merged = Run {
474 b: right.b,
475 bytes: left.bytes.saturating_add(right.bytes),
476 diags: left.diags.saturating_add(right.diags),
477 trivia: left.trivia && right.trivia,
478 marks,
479 ..left
480 };
481 self.seq.set_run(left_item, merged);
482 self.seq.remove(item);
483 self.runs.remove(&slot);
484 }
485 }
486}
487
488pub(super) enum Jump {
491 Step,
493 Past(Option<u32>),
495}
496
497#[derive(Default)]
500struct Undo {
501 created: bool,
503 after: Option<u32>,
508 doomed: Vec<(u32, Run)>,
510 grafted: Option<u32>,
512 arena_pushed: bool,
513 next_slot: u32,
514 links: Vec<(u32, Option<Links>)>,
516 cuts: Vec<u32>,
519 documents: usize,
521 errors: usize,
522 dropped: Vec<(u32, u32)>,
524}
525
526#[derive(Default)]
529pub(super) struct Group {
530 depth: usize,
531 log: Vec<(Undo, Vec<u32>)>,
532}
533
534#[must_use = "an edit group is closed with end_group or rollback_group"]
537#[derive(Clone, Copy, Debug, PartialEq, Eq)]
538pub struct GroupMark {
539 tree: u64,
542 at: usize,
543 depth: usize,
544}
545
546#[derive(Clone, Copy)]
548pub(super) struct Loc<'a> {
549 pub(super) local: usize,
550 pub(super) flat: Flat<'a>,
551 first: u32,
553 attach: u32,
555}
556
557impl Loc<'_> {
558 fn slot(&self, local: usize) -> Option<u32> {
559 u32::try_from(local)
560 .ok()
561 .and_then(|l| self.first.checked_add(l))
562 }
563}
564
565pub(super) struct DiagAt<'a> {
569 pub(super) rank: u64,
571 pub(super) start: u64,
572 pub(super) diagnostic: &'a Stored,
573 pub(super) from: usize,
574 pub(super) to: usize,
575}
576
577pub(super) type Spliced = (Option<Fragment>, Option<(u32, u32)>);
580
581pub(super) struct SpliceArgs {
584 pub(super) parent: u32,
585 pub(super) prev: Option<u32>,
586 pub(super) removed: Vec<u32>,
587 pub(super) fragment: Option<Fragment>,
588}
589
590struct Check {
592 parent: u32,
593 prev: Option<u32>,
594 next: Option<u32>,
595 what: Removed,
596}
597
598struct Applied {
600 taken: Option<Fragment>,
601 span: Option<(u32, u32)>,
602 undo: Undo,
603 check: Check,
604}
605
606#[derive(Clone, Copy)]
608struct Plan {
609 parent: u32,
610 prev: Option<u32>,
611 next: Option<u32>,
612 cut: Option<u32>,
614 new_first: Option<u32>,
616}
617
618const REPLACEABLE: &[SyntaxKind] = &[
620 SyntaxKind::PlainScalar,
621 SyntaxKind::SingleQuotedScalar,
622 SyntaxKind::DoubleQuotedScalar,
623 SyntaxKind::AliasName,
624 SyntaxKind::Anchor,
625 SyntaxKind::Comment,
626 SyntaxKind::Whitespace,
627 SyntaxKind::LineBreak,
628];
629
630const fn is_directive(k: SyntaxKind) -> bool {
631 matches!(
632 k,
633 SyntaxKind::YamlDirective | SyntaxKind::TagDirective | SyntaxKind::ReservedDirective
634 )
635}
636
637const fn is_node_property(k: SyntaxKind) -> bool {
640 matches!(k, SyntaxKind::Tag | SyntaxKind::BlockScalarHeader)
641}
642
643impl SyntaxTree {
644 pub(super) fn base_flat(&self) -> Flat<'_> {
647 Flat {
648 source: &self.source,
649 tiled: self.source.len(),
650 kinds: &self.kinds,
651 parents: &self.parents,
652 words: &self.words,
653 wraps: &self.wraps,
654 extras: &self.extras,
655 diagnostics: &self.diagnostics,
656 }
657 }
658
659 #[must_use]
664 pub const fn error_count(&self) -> usize {
665 self.errors
666 }
667
668 #[must_use]
670 pub fn is_edited(&self) -> bool {
671 self.edits.is_some()
672 }
673
674 #[inline]
678 pub(super) fn locate(&self, slot: u32) -> Option<Loc<'_>> {
679 if (slot as usize) < self.kinds.len() {
680 return Some(Loc {
681 local: slot as usize,
682 flat: self.base_flat(),
683 first: 0,
684 attach: NONE,
685 });
686 }
687 self.locate_grafted(slot)
688 }
689
690 #[inline]
693 fn locate_grafted(&self, slot: u32) -> Option<Loc<'_>> {
694 let e = self.edits.as_deref()?;
695 cost::count(cost::Step::Lookup);
698 let (&first, &at) = e.arenas.range(..=slot).next_back()?;
699 let ins = e.graft_at(at)?;
700 let local = slot.checked_sub(first)? as usize;
701 (local < ins.arena.kinds.len()).then(|| Loc {
702 local,
703 flat: ins.arena.flat(),
704 first,
705 attach: ins.parent,
706 })
707 }
708
709 pub(super) fn facts_at(&self, slot: u32) -> Option<(&StreamFacts, usize, u32)> {
712 if (slot as usize) < self.kinds.len() {
713 return Some((&self.facts, slot as usize, 0));
714 }
715 let e = self.edits.as_deref()?;
716 cost::count(cost::Step::Lookup);
717 let (&first, &at) = e.arenas.range(..=slot).next_back()?;
718 let ins = e.graft_at(at)?;
719 let local = slot.checked_sub(first)? as usize;
720 (local < ins.arena.kinds.len()).then_some((&ins.facts, local, first))
721 }
722
723 pub(super) fn trivia_run_start(&self, p: u32) -> u32 {
731 let Some((facts, local, first)) = self.facts_at(p) else {
732 return p;
733 };
734 let Some(a) = facts.run_start(local) else {
735 return p;
736 };
737 let lo = match self.run_item(p) {
738 Some((_, run, _)) => a.max(run.a as usize),
739 None if self.edits.is_none() => a,
740 None => return p,
741 };
742 u32::try_from(lo)
743 .ok()
744 .and_then(|l| first.checked_add(l))
745 .filter(|s| *s <= p)
746 .unwrap_or(p)
747 }
748
749 pub(super) fn trivia_run_end(&self, p: u32) -> u32 {
755 let Some((facts, local, first)) = self.facts_at(p) else {
756 return p;
757 };
758 let Some(b) = facts.run_end(local) else {
759 return p;
760 };
761 let hi = match self.run_item(p) {
762 Some((_, run, _)) => b.min((run.b as usize).saturating_sub(1)),
763 None if self.edits.is_none() => b,
764 None => return p,
765 };
766 u32::try_from(hi)
767 .ok()
768 .and_then(|h| first.checked_add(h))
769 .filter(|s| *s >= p)
770 .unwrap_or(p)
771 }
772
773 pub(super) fn jump_trivia(&self, s: u32, forward: bool) -> Result<Jump, TreeEditError> {
783 let Some(e) = self.edits.as_deref() else {
784 return Ok(Jump::Step);
785 };
786 let (item, run, start) = self.run_item(s).ok_or(TreeEditError::Internal)?;
787 let at_edge = if forward {
788 run.b
789 .checked_sub(run.a)
790 .and_then(|n| start.checked_add(n))
791 .and_then(|end| end.checked_sub(1))
792 == Some(s)
793 } else {
794 start == s
795 };
796 let neighbour = if forward {
797 e.seq.next(item)
798 } else {
799 e.seq.prev(item)
800 };
801 let trivia_next = neighbour
802 .and_then(|n| e.seq.run(n))
803 .is_some_and(|r| r.trivia);
804 if !at_edge || !trivia_next {
805 return Ok(Jump::Step);
806 }
807 let solid = if forward {
808 e.seq.next_solid(item)
809 } else {
810 e.seq.prev_solid(item)
811 };
812 let Some(j) = solid else {
813 return Ok(Jump::Past(None));
814 };
815 let r = e.seq.run(j).ok_or(TreeEditError::Internal)?;
816 if forward {
817 let first = r.arena.checked_add(r.a).ok_or(TreeEditError::Internal)?;
818 return Ok(Jump::Past(Some(first)));
819 }
820 let mut y =
821 r.b.checked_sub(1)
822 .and_then(|l| r.arena.checked_add(l))
823 .ok_or(TreeEditError::Internal)?;
824 loop {
827 match self.nav_parent(y) {
828 Some(0) => return Ok(Jump::Past(Some(y))),
829 Some(p) => y = p,
830 None if y == 0 => return Ok(Jump::Past(None)),
831 None => return Err(TreeEditError::Internal),
832 }
833 }
834 }
835
836 fn stream_trivia(&self, arena: u32, a: u32, b: u32) -> bool {
840 let Some((flat, _, attach)) = self.arena_flat(arena) else {
841 return false;
842 };
843 let facts = if arena == 0 {
844 &self.facts
845 } else {
846 match self.edits.as_deref().and_then(|e| e.graft(arena)) {
847 Some(g) => &g.facts,
848 None => return false,
849 }
850 };
851 (arena == 0 || attach == 0) && all_stream_trivia(flat, facts, arena == 0, a, b)
852 }
853
854 fn run_marks(&self, arena: u32, a: u32, b: u32) -> Marks {
857 match self.arena_index(arena) {
858 Some((flat, rf)) => marks(flat, rf, self.stream_facts_of(arena), a, b),
859 None => Marks::CONTENT,
862 }
863 }
864
865 pub(super) fn arena_index(&self, arena: u32) -> Option<(Flat<'_>, &RunFacts)> {
867 if arena == 0 {
868 return Some((self.base_flat(), &self.run_facts));
869 }
870 let g = self.edits.as_deref()?.graft(arena)?;
871 Some((g.arena.flat(), &g.runs))
872 }
873
874 pub(super) fn stream_facts_of(&self, arena: u32) -> Option<&StreamFacts> {
877 if arena == 0 {
878 return Some(&self.facts);
879 }
880 let g = self.edits.as_deref()?.graft(arena)?;
881 (g.parent == 0).then_some(&g.facts)
882 }
883
884 pub(super) fn piece_at(&self, slot: u32) -> Option<(Piece, u32)> {
887 if self.edits.is_none() {
888 let len = u32::try_from(self.kinds.len()).ok()?;
889 let p = Piece {
890 arena: 0,
891 a: 0,
892 b: len,
893 item: None,
894 };
895 return (slot < len).then_some((p, slot));
896 }
897 let (item, run, start) = self.run_item(slot)?;
898 let local = run.a.checked_add(slot.checked_sub(start)?)?;
899 let p = Piece {
900 arena: run.arena,
901 a: run.a,
902 b: run.b,
903 item: Some(item),
904 };
905 Some((p, local))
906 }
907
908 fn piece_of_item(&self, item: u32) -> Option<Piece> {
910 let run = self.edits.as_deref()?.seq.run(item)?;
911 Some(Piece {
912 arena: run.arena,
913 a: run.a,
914 b: run.b,
915 item: Some(item),
916 })
917 }
918
919 pub(super) fn piece_after(&self, item: u32, v: u32) -> Option<Piece> {
922 let next = self.edits.as_deref()?.seq.next_low(item, v)?;
923 self.piece_of_item(next)
924 }
925
926 pub(super) fn piece_visible_before(&self, item: u32) -> Option<Piece> {
929 let prev = self.edits.as_deref()?.seq.prev_visible(item)?;
930 self.piece_of_item(prev)
931 }
932
933 pub(super) fn piece_firm(&self, item: u32, forward: bool) -> Option<Piece> {
936 let at = self.edits.as_deref()?.seq.near_firm(item, forward)?;
937 self.piece_of_item(at)
938 }
939
940 pub(super) fn piece_docs(&self, item: u32, forward: bool) -> Option<Piece> {
943 let e = self.edits.as_deref()?;
944 let at = if forward {
945 e.seq.next_docs(item)?
946 } else {
947 e.seq.prev_docs(item)?
948 };
949 self.piece_of_item(at)
950 }
951
952 fn arena_flat(&self, id: u32) -> Option<(Flat<'_>, u32, u32)> {
953 if id == 0 {
954 return Some((self.base_flat(), 0, NONE));
955 }
956 let e = self.edits.as_deref()?;
957 let ins = e.graft(id)?;
958 Some((ins.arena.flat(), id, ins.parent))
959 }
960
961 pub(super) fn run_flat(&self, run: &Run) -> Option<(Flat<'_>, u32, u32)> {
964 self.graft_flat(run.arena, run.graft)
965 }
966
967 #[inline(always)]
970 fn graft_flat(&self, arena: u32, graft: u32) -> Option<(Flat<'_>, u32, u32)> {
971 if arena == 0 {
972 return Some((self.base_flat(), 0, NONE));
973 }
974 let ins = self.edits.as_deref()?.graft_at(graft)?;
975 Some((ins.arena.flat(), arena, ins.parent))
976 }
977
978 pub(super) fn run_item(&self, slot: u32) -> Option<(u32, Run, u32)> {
980 let e = self.edits.as_deref()?;
981 cost::count(cost::Step::Lookup);
982 let (&start, &item) = e.runs.range(..=slot).next_back()?;
983 let run = e.seq.run(item)?;
984 let count = run.b.checked_sub(run.a)?;
985 (slot < start.checked_add(count)?).then_some((item, run, start))
986 }
987
988 pub(super) fn is_live(&self, slot: u32) -> bool {
990 if self.edits.is_none() {
991 return (slot as usize) < self.kinds.len();
992 }
993 self.run_item(slot).is_some()
994 }
995
996 pub(super) fn kind_of(&self, slot: u32) -> Option<SyntaxKind> {
997 let loc = self.locate(slot)?;
998 loc.flat.kind(loc.local)
999 }
1000
1001 fn default_links(loc: &Loc<'_>) -> Links {
1006 let f = &loc.flat;
1007 let l = loc.local;
1008 let s = |x: Option<usize>| x.and_then(|x| loc.slot(x)).unwrap_or(NONE);
1009 Links {
1010 first: s(f.first_child(l)),
1011 last: s(f.last_child(l)),
1012 next: s(f.next_sibling(l)),
1013 prev: s(f.prev_sibling(l)),
1014 }
1015 }
1016
1017 fn override_of(&self, slot: u32) -> Option<&Links> {
1018 let e = self.edits.as_deref()?;
1019 cost::count(cost::Step::Lookup);
1020 e.links.get(&slot)
1021 }
1022
1023 fn links_of(&self, slot: u32) -> Links {
1025 if let Some(l) = self.override_of(slot) {
1026 return *l;
1027 }
1028 self.locate(slot).map_or(
1029 Links {
1030 first: NONE,
1031 last: NONE,
1032 next: NONE,
1033 prev: NONE,
1034 },
1035 |loc| Self::default_links(&loc),
1036 )
1037 }
1038
1039 fn some(x: u32) -> Option<u32> {
1040 (x != NONE).then_some(x)
1041 }
1042
1043 fn nav_link(
1047 &self,
1048 slot: u32,
1049 pick: fn(&Links) -> u32,
1050 local: impl FnOnce(&Flat<'_>, usize) -> Option<usize>,
1051 ) -> Option<u32> {
1052 if let Some(l) = self.override_of(slot) {
1053 return Self::some(pick(l));
1054 }
1055 let loc = self.locate(slot)?;
1056 local(&loc.flat, loc.local).and_then(|x| loc.slot(x))
1057 }
1058
1059 pub(super) fn nav_parent(&self, slot: u32) -> Option<u32> {
1060 if (slot as usize) < self.kinds.len() {
1061 return self
1063 .parent_of(slot as usize)
1064 .and_then(|p| u32::try_from(p).ok());
1065 }
1066 let loc = self.locate(slot)?;
1067 match loc.flat.parent(loc.local) {
1068 Some(p) => loc.slot(p),
1069 None => Self::some(loc.attach),
1070 }
1071 }
1072
1073 pub(super) fn nav_first(&self, slot: u32) -> Option<u32> {
1075 self.nav_link(slot, |l| l.first, |f, i| f.first_child(i))
1076 }
1077
1078 pub(super) fn nav_last(&self, slot: u32) -> Option<u32> {
1080 self.nav_link(slot, |l| l.last, |f, i| f.last_child(i))
1081 }
1082
1083 pub(super) fn nav_next(&self, slot: u32) -> Option<u32> {
1085 self.nav_link(slot, |l| l.next, |f, i| f.next_sibling(i))
1086 }
1087
1088 pub(super) fn nav_prev(&self, slot: u32) -> Option<u32> {
1090 self.nav_link(slot, |l| l.prev, |f, i| f.prev_sibling(i))
1091 }
1092
1093 pub(super) fn nav_succ(&self, slot: u32) -> Option<u32> {
1095 let Some(e) = self.edits.as_deref() else {
1096 let n = slot.checked_add(1)?;
1097 return ((n as usize) < self.kinds.len()).then_some(n);
1098 };
1099 let (item, run, start) = self.run_item(slot)?;
1100 let n = slot.checked_add(1)?;
1101 if n < start.checked_add(run.b.checked_sub(run.a)?)? {
1102 return Some(n);
1103 }
1104 let next = e.seq.next(item)?;
1105 let r = e.seq.run(next)?;
1106 let first = r.arena;
1107 first.checked_add(r.a)
1108 }
1109
1110 pub(super) fn nav_pred(&self, slot: u32) -> Option<u32> {
1112 let Some(e) = self.edits.as_deref() else {
1113 return slot.checked_sub(1);
1114 };
1115 let (item, _, start) = self.run_item(slot)?;
1116 if slot > start {
1117 return slot.checked_sub(1);
1118 }
1119 let prev = e.seq.prev(item)?;
1120 let r = e.seq.run(prev)?;
1121 let first = r.arena;
1122 first.checked_add(r.b.checked_sub(1)?)
1123 }
1124
1125 #[inline(always)]
1153 pub(super) fn run_hinted(&self, slot: u32, hint: u32) -> Option<(RunAt, u32)> {
1154 if hint != NONE {
1155 if let Some(r) = self.edits.as_deref().and_then(|e| e.seq.at(hint)) {
1156 let start = r.arena.checked_add(r.a)?;
1157 let end = r.arena.checked_add(r.b)?;
1158 if start <= slot && slot < end {
1159 return Some((r, start));
1160 }
1161 }
1162 }
1163 let (item, run, start) = self.run_item(slot)?;
1164 let r = RunAt {
1165 item,
1166 arena: run.arena,
1167 graft: run.graft,
1168 a: run.a,
1169 b: run.b,
1170 };
1171 Some((r, start))
1172 }
1173
1174 #[inline]
1177 pub(super) fn run_slots(&self, item: u32) -> (u32, u32) {
1178 let bounds = self.edits.as_deref().and_then(|e| e.seq.bounds(item));
1179 let Some((arena, a, b)) = bounds else {
1180 return (0, 0);
1181 };
1182 match (arena.checked_add(a), arena.checked_add(b)) {
1183 (Some(s), Some(t)) => (s, t),
1184 _ => (0, 0),
1185 }
1186 }
1187
1188 pub(super) fn run_after(&self, item: u32) -> Option<(u32, u32, u32)> {
1191 let next = self.edits.as_deref()?.seq.next(item)?;
1192 let (s, t) = self.run_slots(next);
1193 (t > s).then_some((next, s, t))
1194 }
1195
1196 #[inline]
1200 fn base_run(&self, slot: u32, hint: u32) -> Option<(usize, usize)> {
1201 if hint == NONE || (slot as usize) >= self.kinds.len() {
1202 return None;
1203 }
1204 let (arena, a, b) = self.edits.as_deref()?.seq.bounds(hint)?;
1205 (arena == 0 && a <= slot && slot < b).then_some((a as usize, b as usize))
1206 }
1207
1208 #[inline]
1211 pub(super) fn parent_slot(&self, slot: u32, hint: u32) -> Option<u32> {
1212 if (slot as usize) < self.kinds.len() {
1213 return self
1214 .parent_of(slot as usize)
1215 .and_then(|p| u32::try_from(p).ok());
1216 }
1217 self.nav_parent_hinted(slot, hint).map(|(p, _)| p)
1218 }
1219
1220 #[cfg(test)]
1223 pub(super) fn limit_arenas(&mut self, spare: usize) {
1224 if let Some(e) = self.edits.as_deref_mut() {
1225 let n = e.grafts.len().saturating_add(spare);
1226 e.grafts.limit_entries(n);
1227 }
1228 }
1229
1230 #[cfg(test)]
1233 pub(super) fn arena_counts(&self) -> (usize, usize) {
1234 self.edits
1235 .as_deref()
1236 .map_or((0, 0), |e| (e.arenas.len(), e.grafts.free_len()))
1237 }
1238
1239 #[cfg(test)]
1242 pub(super) fn run_lengths(&self) -> (Vec<u32>, usize) {
1243 let Some(e) = self.edits.as_deref() else {
1244 return (Vec::new(), 0);
1245 };
1246 let mut out = Vec::new();
1247 let mut at = e.seq.first();
1248 while let Some(x) = at {
1249 out.extend(e.seq.run(x).map(|r| r.b.saturating_sub(r.a)));
1250 at = e.seq.next(x);
1251 }
1252 (out, e.runs.len())
1253 }
1254
1255 pub(super) fn hint_of(&self, slot: u32) -> u32 {
1258 if self.edits.is_none() {
1259 return NONE;
1260 }
1261 self.run_item(slot).map_or(NONE, |(item, _, _)| item)
1262 }
1263
1264 #[inline(always)]
1266 fn loc_in_run(&self, run: &RunAt, slot: u32) -> Option<Loc<'_>> {
1267 let (flat, first, attach) = self.graft_flat(run.arena, run.graft)?;
1268 Some(Loc {
1269 local: slot.checked_sub(first)? as usize,
1270 flat,
1271 first,
1272 attach,
1273 })
1274 }
1275
1276 #[inline(never)]
1279 pub(super) fn locate_hinted(&self, slot: u32, hint: u32) -> Option<Loc<'_>> {
1280 if (slot as usize) < self.kinds.len() || hint == NONE {
1281 return self.locate(slot);
1282 }
1283 match self.run_hinted(slot, hint) {
1284 Some((run, _)) => self.loc_in_run(&run, slot),
1285 None => self.locate(slot),
1286 }
1287 }
1288
1289 pub(super) fn kind_hinted(&self, slot: u32, hint: u32) -> Option<SyntaxKind> {
1292 if let Some(k) = self.kind_at(slot as usize) {
1293 return Some(k);
1294 }
1295 let e = self.edits.as_deref()?;
1297 if let Some(r) = e.seq.at(hint) {
1298 let start = r.arena.checked_add(r.a)?;
1299 let end = r.arena.checked_add(r.b)?;
1300 if start <= slot && slot < end {
1301 let g = e.graft_at(r.graft)?;
1302 return g
1303 .arena
1304 .kinds
1305 .get(slot.checked_sub(r.arena)? as usize)
1306 .copied();
1307 }
1308 }
1309 let loc = self.locate(slot)?;
1310 loc.flat.kind(loc.local)
1311 }
1312
1313 #[inline(always)]
1315 fn at_hinted(&self, slot: u32, hint: u32) -> Option<(u32, RunAt, Loc<'_>)> {
1316 let (run, _) = self.run_hinted(slot, hint)?;
1317 let loc = self.loc_in_run(&run, slot)?;
1318 Some((run.item, run, loc))
1319 }
1320
1321 fn hint_after(&self, item: u32, slot: u32) -> u32 {
1325 let Some(e) = self.edits.as_deref() else {
1326 return NONE;
1327 };
1328 e.seq
1329 .next(item)
1330 .filter(|n| e.run_start(*n) == Some(slot))
1331 .unwrap_or(NONE)
1332 }
1333
1334 pub(super) fn nav_succ_hinted(&self, slot: u32, hint: u32) -> Option<(u32, u32)> {
1337 let Some(e) = self.edits.as_deref() else {
1338 return self.nav_succ(slot).map(|s| (s, NONE));
1339 };
1340 let (run, start) = self.run_hinted(slot, hint)?;
1341 let item = run.item;
1342 let n = slot.checked_add(1)?;
1343 if n < start.checked_add(run.b.checked_sub(run.a)?)? {
1344 return Some((n, item));
1345 }
1346 let next = e.seq.next(item)?;
1347 let r = e.seq.run(next)?;
1348 Some((r.arena.checked_add(r.a)?, next))
1349 }
1350
1351 pub(super) fn nav_pred_hinted(&self, slot: u32, hint: u32) -> Option<(u32, u32)> {
1353 let Some(e) = self.edits.as_deref() else {
1354 return self.nav_pred(slot).map(|s| (s, NONE));
1355 };
1356 let (run, start) = self.run_hinted(slot, hint)?;
1357 let item = run.item;
1358 if slot > start {
1359 return Some((slot.checked_sub(1)?, item));
1360 }
1361 let prev = e.seq.prev(item)?;
1362 let r = e.seq.run(prev)?;
1363 Some((r.arena.checked_add(r.b.checked_sub(1)?)?, prev))
1364 }
1365
1366 pub(super) fn nav_parent_hinted(&self, slot: u32, hint: u32) -> Option<(u32, u32)> {
1369 if hint == NONE || self.edits.is_none() {
1370 return self.nav_parent(slot).map(|p| (p, NONE));
1371 }
1372 if let Some((a, _)) = self.base_run(slot, hint) {
1373 let p = self.parent_of(slot as usize)?;
1374 let h = if p >= a { hint } else { NONE };
1375 return Some((u32::try_from(p).ok()?, h));
1376 }
1377 let (item, run, loc) = self.at_hinted(slot, hint)?;
1378 match loc.flat.parent(loc.local) {
1379 Some(p) => Some((loc.slot(p)?, if p >= run.a as usize { item } else { NONE })),
1382 None => Self::some(loc.attach).map(|p| (p, NONE)),
1383 }
1384 }
1385
1386 pub(super) fn nav_first_hinted(&self, slot: u32, hint: u32) -> Option<(u32, u32)> {
1388 if self.edits.is_none() || hint == NONE {
1391 return self.nav_first(slot).map(|s| (s, NONE));
1392 }
1393 if let Some((_, b)) = self.base_run(slot, hint) {
1394 let i = slot as usize;
1395 let c = i.checked_add(1)?;
1396 if c < b {
1397 return (c < self.end_of(i))
1399 .then(|| u32::try_from(c).ok())
1400 .flatten()
1401 .map(|c| (c, hint));
1402 }
1403 let c = self.nav_first(slot)?;
1406 return Some((c, self.hint_after(hint, c)));
1407 }
1408 let (item, run, loc) = self.at_hinted(slot, hint)?;
1409 let next = loc.local.checked_add(1)?;
1410 if next < run.b as usize {
1411 return loc
1414 .flat
1415 .first_child(loc.local)
1416 .and_then(|c| loc.slot(c))
1417 .map(|c| (c, item));
1418 }
1419 let c = self.nav_first(slot)?;
1420 Some((c, self.hint_after(item, c)))
1421 }
1422
1423 pub(super) fn nav_next_hinted(&self, slot: u32, hint: u32) -> Option<(u32, u32)> {
1426 if self.edits.is_none() || hint == NONE {
1429 return self.nav_next(slot).map(|s| (s, NONE));
1430 }
1431 if let Some((_, b)) = self.base_run(slot, hint) {
1432 let i = slot as usize;
1433 let after = self.end_of(i);
1434 if after < b {
1435 let limit = self
1437 .parent_of(i)
1438 .map_or(self.kinds.len(), |p| self.end_of(p));
1439 return (after < limit && after > i)
1440 .then(|| u32::try_from(after).ok())
1441 .flatten()
1442 .map(|s| (s, hint));
1443 }
1444 let s = self.nav_next(slot)?;
1447 let h = if after == b {
1448 self.hint_after(hint, s)
1449 } else {
1450 NONE
1451 };
1452 return Some((s, h));
1453 }
1454 let (item, run, loc) = self.at_hinted(slot, hint)?;
1455 let end = loc.flat.end(loc.local);
1456 if end < run.b as usize {
1457 return loc
1460 .flat
1461 .next_sibling(loc.local)
1462 .and_then(|s| loc.slot(s))
1463 .map(|s| (s, item));
1464 }
1465 let s = self.nav_next(slot)?;
1466 let h = if end == run.b as usize {
1468 self.hint_after(item, s)
1469 } else {
1470 NONE
1471 };
1472 Some((s, h))
1473 }
1474
1475 pub(super) fn nav_prev_hinted(&self, slot: u32, hint: u32) -> Option<(u32, u32)> {
1478 if self.edits.is_none() || hint == NONE {
1481 return self.nav_prev(slot).map(|s| (s, NONE));
1482 }
1483 let (item, run, loc) = self.at_hinted(slot, hint)?;
1484 if loc.local > run.a as usize {
1485 return loc.flat.prev_sibling(loc.local).and_then(|s| {
1488 let h = if s >= run.a as usize { item } else { NONE };
1489 Some((loc.slot(s)?, h))
1490 });
1491 }
1492 self.nav_prev(slot).map(|s| (s, NONE))
1493 }
1494
1495 pub(super) fn nav_last_hinted(&self, slot: u32, hint: u32) -> Option<(u32, u32)> {
1498 if self.edits.is_none() || hint == NONE {
1501 return self.nav_last(slot).map(|s| (s, NONE));
1502 }
1503 let (item, run, loc) = self.at_hinted(slot, hint)?;
1504 if loc.flat.end(loc.local) < run.b as usize {
1505 return loc
1506 .flat
1507 .last_child(loc.local)
1508 .and_then(|c| loc.slot(c))
1509 .map(|c| (c, item));
1510 }
1511 self.nav_last(slot).map(|s| (s, NONE))
1512 }
1513
1514 pub(super) fn nav_rank_hinted(&self, slot: u32, hint: u32) -> Option<(u64, u64)> {
1517 let Some(e) = self.edits.as_deref() else {
1518 return self.nav_rank(slot);
1519 };
1520 let (item, run, loc) = self.at_hinted(slot, hint)?;
1521 let (pc, pb) = e.seq.prefix(item);
1522 let within = u64::try_from(loc.local.checked_sub(run.a as usize)?).ok()?;
1523 let bytes = loc
1524 .flat
1525 .start(loc.local)
1526 .checked_sub(loc.flat.start(run.a as usize))?;
1527 Some((
1528 pc.checked_add(within)?,
1529 pb.checked_add(u64::try_from(bytes).ok()?)?,
1530 ))
1531 }
1532
1533 pub(super) fn nav_span_hinted(&self, slot: u32, hint: u32) -> Span {
1535 let Some((_, start)) = self.nav_rank_hinted(slot, hint) else {
1536 return Span::empty(0);
1537 };
1538 let end = self
1539 .nav_after(slot)
1540 .and_then(|a| self.nav_rank(a))
1541 .map_or(self.nav_total().1, |(_, b)| b);
1542 let start = usize::try_from(start).unwrap_or(usize::MAX);
1543 let end = usize::try_from(end).unwrap_or(usize::MAX).max(start);
1544 Span::new(start, end)
1545 }
1546
1547 pub(super) fn edited_text_hinted(&self, slot: u32, hint: u32) -> Cow<'_, str> {
1550 let i = slot as usize;
1551 if self.kind_at(i).is_some_and(SyntaxKind::is_token) {
1552 let s = self.span_of(i);
1554 return Cow::Borrowed(self.source.get(s.start..s.end).unwrap_or(""));
1555 }
1556 if let Some(loc) = self.locate_hinted(slot, hint) {
1557 if loc.flat.kind(loc.local).is_some_and(SyntaxKind::is_token) {
1558 return Cow::Borrowed(loc.flat.token_text(loc.local));
1559 }
1560 }
1561 self.edited_text(slot)
1562 }
1563
1564 pub(super) fn nav_last_leaf(&self, slot: u32) -> Option<u32> {
1570 if self.nav_first(slot).is_none() {
1571 return self.is_live(slot).then_some(slot);
1572 }
1573 match self.nav_after(slot) {
1574 Some(a) => self.nav_pred(a),
1575 None => match self.edits.as_deref() {
1576 None => u32::try_from(self.kinds.len().checked_sub(1)?).ok(),
1577 Some(e) => {
1578 let r = e.seq.run(e.seq.last()?)?;
1579 let first = r.arena;
1580 first.checked_add(r.b.checked_sub(1)?)
1581 }
1582 },
1583 }
1584 }
1585
1586 pub(super) fn last_chain(&self, slot: u32) -> Vec<u32> {
1590 let mut chain = Vec::new();
1591 let Some(mut x) = self.nav_last_leaf(slot) else {
1592 chain.push(slot);
1593 return chain;
1594 };
1595 loop {
1597 chain.push(x);
1598 if x == slot {
1599 break;
1600 }
1601 match self.nav_parent(x) {
1602 Some(p) => x = p,
1603 None => {
1604 chain.clear();
1606 chain.push(slot);
1607 return chain;
1608 }
1609 }
1610 }
1611 chain.reverse();
1612 chain
1613 }
1614
1615 pub(super) fn nav_rank(&self, slot: u32) -> Option<(u64, u64)> {
1617 let Some(e) = self.edits.as_deref() else {
1618 let start = self.start_of(slot as usize);
1619 return Some((u64::from(slot), u64::try_from(start).ok()?));
1620 };
1621 let (item, run, start) = self.run_item(slot)?;
1622 let loc = self.locate(slot)?;
1623 let (pc, pb) = e.seq.prefix(item);
1624 let within = u64::from(slot.checked_sub(start)?);
1625 let a = run.a as usize;
1626 let bytes = loc.flat.start(loc.local).checked_sub(loc.flat.start(a))?;
1627 Some((
1628 pc.checked_add(within)?,
1629 pb.checked_add(u64::try_from(bytes).ok()?)?,
1630 ))
1631 }
1632
1633 pub(super) fn nav_total(&self) -> (u64, u64) {
1635 match self.edits.as_deref() {
1636 Some(e) => e.seq.total(),
1637 None => (
1638 u64::try_from(self.kinds.len()).unwrap_or(u64::MAX),
1639 u64::try_from(self.source.len()).unwrap_or(u64::MAX),
1640 ),
1641 }
1642 }
1643
1644 pub(super) fn nav_after(&self, slot: u32) -> Option<u32> {
1648 if self.edits.is_none() {
1649 let end = self.end_of(slot as usize);
1650 return u32::try_from(end)
1651 .ok()
1652 .filter(|e| (*e as usize) < self.kinds.len());
1653 }
1654 let loc = self.locate(slot)?;
1655 if let Some((_, run, _)) = self.run_item(slot) {
1656 let end = loc.flat.end(loc.local);
1657 if end > loc.local && end < run.b as usize {
1658 return loc.slot(end);
1659 }
1660 }
1661 let mut x = slot;
1662 loop {
1663 if let Some(n) = self.nav_next(x) {
1664 return Some(n);
1665 }
1666 x = self.nav_parent(x)?;
1667 }
1668 }
1669
1670 pub(super) fn nav_size(&self, slot: u32) -> u64 {
1672 let Some((r, _)) = self.nav_rank(slot) else {
1673 return 0;
1674 };
1675 let end = self
1676 .nav_after(slot)
1677 .and_then(|a| self.nav_rank(a))
1678 .map_or(self.nav_total().0, |(r, _)| r);
1679 end.saturating_sub(r)
1680 }
1681
1682 pub(super) fn nav_bytes(&self, slot: u32) -> Option<(u64, u64)> {
1684 let (_, start) = self.nav_rank(slot)?;
1685 let end = self
1686 .nav_after(slot)
1687 .and_then(|a| self.nav_rank(a))
1688 .map_or(self.nav_total().1, |(_, b)| b);
1689 Some((start, end.max(start)))
1690 }
1691
1692 pub(super) fn edited_text(&self, slot: u32) -> Cow<'_, str> {
1698 if let Some(loc) = self.locate(slot) {
1699 if loc.flat.kind(loc.local).is_some_and(SyntaxKind::is_token) {
1700 return Cow::Borrowed(loc.flat.token_text(loc.local));
1701 }
1702 }
1703 match self.nav_bytes(slot) {
1704 Some((a, b)) => self
1708 .try_text_range(a, b)
1709 .unwrap_or_else(|_| self.text_from_tokens(slot)),
1710 None => Cow::Borrowed(""),
1711 }
1712 }
1713
1714 pub(super) fn try_text_range(
1724 &self,
1725 start: u64,
1726 end: u64,
1727 ) -> Result<Cow<'_, str>, TreeEditError> {
1728 let Some(e) = self.edits.as_deref() else {
1729 let a = usize::try_from(start).map_err(|_| TreeEditError::Internal)?;
1730 let b = usize::try_from(end).map_err(|_| TreeEditError::Internal)?;
1731 if b <= a {
1732 return Ok(Cow::Borrowed(""));
1733 }
1734 return self
1735 .source
1736 .get(a..b)
1737 .map(Cow::Borrowed)
1738 .ok_or(TreeEditError::Internal);
1739 };
1740 if end <= start {
1741 return Ok(Cow::Borrowed(""));
1742 }
1743 let (mut item, mut off) = e.seq.find_byte(start).ok_or(TreeEditError::Internal)?;
1744 let mut left = end.saturating_sub(start);
1745 let mut out: Option<String> = None;
1746 loop {
1747 let piece = e.seq.run(item).and_then(|run| {
1748 let (flat, _, _) = self.run_flat(&run)?;
1749 let take = left.min(run.bytes.saturating_sub(off));
1750 let a = flat
1751 .start(run.a as usize)
1752 .checked_add(usize::try_from(off).ok()?)?;
1753 let b = a.checked_add(usize::try_from(take).ok()?)?;
1754 Some((flat.source.get(a..b)?, take))
1755 });
1756 let (piece, take) = piece.ok_or(TreeEditError::Internal)?;
1758 left = left.saturating_sub(take);
1759 if left == 0 && out.is_none() {
1760 return Ok(Cow::Borrowed(piece));
1761 }
1762 out.get_or_insert_with(String::new).push_str(piece);
1763 if left == 0 {
1764 break;
1765 }
1766 item = e.seq.next(item).ok_or(TreeEditError::Internal)?;
1767 off = 0;
1768 }
1769 Ok(Cow::Owned(out.unwrap_or_default()))
1770 }
1771
1772 fn text_from_tokens(&self, slot: u32) -> Cow<'_, str> {
1777 let mut out = String::new();
1778 let mut left = self.nav_size(slot);
1779 let mut at = Some(slot);
1780 while left > 0 {
1781 let Some(x) = at else { break };
1782 if let Some(loc) = self.locate(x) {
1783 if loc.flat.kind(loc.local).is_some_and(SyntaxKind::is_token) {
1784 out.push_str(loc.flat.token_text(loc.local));
1785 }
1786 }
1787 left = left.saturating_sub(1);
1788 at = self.nav_succ(x);
1789 }
1790 Cow::Owned(out)
1791 }
1792
1793 pub(super) fn byte_at(&self, offset: u64) -> Option<u8> {
1795 let Some(e) = self.edits.as_deref() else {
1796 return self
1797 .source
1798 .as_bytes()
1799 .get(usize::try_from(offset).ok()?)
1800 .copied();
1801 };
1802 let (item, off) = e.seq.find_byte(offset)?;
1803 let run = e.seq.run(item)?;
1804 let (flat, _, _) = self.run_flat(&run)?;
1805 let at = flat
1806 .start(run.a as usize)
1807 .checked_add(usize::try_from(off).ok()?)?;
1808 flat.source.as_bytes().get(at).copied()
1809 }
1810
1811 pub(super) fn column_at(&self, offset: u64) -> Option<usize> {
1824 let mut col = self.line_bytes_before(offset)?;
1825 let mut at = offset.checked_sub(u64::try_from(col).ok()?)?;
1826 while col >= 3
1827 && self.byte_at(at) == Some(0xef)
1828 && self.byte_at(at.saturating_add(1)) == Some(0xbb)
1829 && self.byte_at(at.saturating_add(2)) == Some(0xbf)
1830 {
1831 col = col.saturating_sub(3);
1832 at = at.saturating_add(3);
1833 }
1834 Some(col)
1835 }
1836
1837 fn line_bytes_before(&self, offset: u64) -> Option<usize> {
1840 let breaks = ['\n', '\r'];
1841 let Some(e) = self.edits.as_deref() else {
1842 let before = self.source.get(..usize::try_from(offset).ok()?)?;
1843 let line = before
1844 .rfind(breaks)
1845 .and_then(|i| before.get(i.checked_add(1)?..))
1846 .unwrap_or(before);
1847 return Some(line.len());
1848 };
1849 if offset == 0 {
1850 return Some(0);
1851 }
1852 let (mut item, mut last) = e.seq.find_byte(offset.checked_sub(1)?)?;
1853 let mut count = 0usize;
1854 loop {
1855 let run = e.seq.run(item)?;
1856 let (flat, _, _) = self.run_flat(&run)?;
1857 let a = flat.start(run.a as usize);
1858 let b = a.checked_add(usize::try_from(last.checked_add(1)?).ok()?)?;
1859 let piece = flat.source.get(a..b)?;
1860 if let Some(i) = piece.rfind(breaks) {
1861 let tail = piece.get(i.checked_add(1)?..)?;
1862 return Some(count.saturating_add(tail.len()));
1863 }
1864 count = count.saturating_add(piece.len());
1865 let mut p = e.seq.prev(item);
1866 loop {
1867 let Some(x) = p else { return Some(count) };
1868 let bytes = e.seq.run(x)?.bytes;
1869 if bytes > 0 {
1870 item = x;
1871 last = bytes.checked_sub(1)?;
1872 break;
1873 }
1874 p = e.seq.prev(x);
1875 }
1876 }
1877 }
1878
1879 pub(super) fn edited_emit(&self, e: &Edits) -> String {
1883 let (_, bytes) = e.seq.total();
1884 let mut out = String::with_capacity(usize::try_from(bytes).unwrap_or(0));
1885 let mut at = e.seq.first();
1886 while let Some(item) = at {
1887 if let Some(run) = e.seq.run(item) {
1888 if let Some((flat, _, _)) = self.run_flat(&run) {
1889 let a = flat.start(run.a as usize);
1890 let b = flat.start(run.b as usize).max(a);
1891 out.push_str(flat.source.get(a..b).unwrap_or(""));
1892 }
1893 }
1894 at = e.seq.next(item);
1895 }
1896 out
1897 }
1898
1899 pub(super) fn to_global(&self, slot: u32, span: Span) -> Span {
1901 let (Some(loc), Some((_, off))) = (self.locate(slot), self.nav_rank(slot)) else {
1902 return span;
1903 };
1904 let from = loc.flat.start(loc.local);
1905 super::arena::shift_span(span, from, usize::try_from(off).unwrap_or(usize::MAX))
1906 }
1907
1908 pub(super) fn diagnostics_of(&self, slot: u32) -> Vec<Cow<'_, Diagnostic>> {
1921 if self.edits.is_none() {
1922 let i = slot as usize;
1923 let lo = self.diagnostics.partition_point(|(n, _)| (*n as usize) < i);
1924 return self
1925 .diagnostics
1926 .get(lo..)
1927 .unwrap_or_default()
1928 .iter()
1929 .take_while(|(n, _)| *n as usize == i)
1930 .map(|(_, d)| d.view())
1931 .collect();
1932 }
1933 let (Some(loc), Some((_, off))) = (self.locate(slot), self.nav_rank(slot)) else {
1934 return Vec::new();
1935 };
1936 let from = loc.flat.start(loc.local);
1937 let to = usize::try_from(off).unwrap_or(usize::MAX);
1938 loc.flat
1939 .diagnostics_at(loc.local)
1940 .iter()
1941 .enumerate()
1942 .filter(|(n, _)| !self.is_dropped(slot, *n))
1943 .map(|(_, (_, d))| {
1944 let mut d = d.clone();
1945 d.shift(from, to);
1946 Cow::Owned(d.view().into_owned())
1947 })
1948 .collect()
1949 }
1950
1951 pub(super) fn for_each_diagnostic(&self, slot: u32, mut f: impl FnMut(&Stored, usize, usize)) {
1956 let Some(loc) = self.locate(slot) else {
1957 return;
1958 };
1959 if loc.flat.diagnostics.is_empty() {
1960 return;
1961 }
1962 let list = loc.flat.diagnostics_at(loc.local);
1963 if list.is_empty() {
1964 return;
1965 }
1966 let (from, to) = if self.edits.is_none() {
1967 (0, 0)
1968 } else {
1969 let Some((_, off)) = self.nav_rank(slot) else {
1970 return;
1971 };
1972 (
1973 loc.flat.start(loc.local),
1974 usize::try_from(off).unwrap_or(usize::MAX),
1975 )
1976 };
1977 for (n, (_, d)) in list.iter().enumerate() {
1978 if !self.is_dropped(slot, n) {
1979 f(d, from, to);
1980 }
1981 }
1982 }
1983
1984 pub(super) fn is_dropped(&self, slot: u32, n: usize) -> bool {
1988 self.edits.as_deref().is_some_and(|e| {
1989 !e.dropped.is_empty() && u32::try_from(n).is_ok_and(|n| e.dropped.contains(&(slot, n)))
1990 })
1991 }
1992
1993 fn list_dropped(&self, flat: &Flat<'_>, first: u32, at: usize) -> bool {
1996 let Some(e) = self.edits.as_deref() else {
1997 return false;
1998 };
1999 if e.dropped.is_empty() {
2000 return false;
2001 }
2002 let Some(&(l, _)) = flat.diagnostics.get(at) else {
2003 return false;
2004 };
2005 let group = flat.diagnostics.partition_point(|(x, _)| *x < l);
2006 self.is_dropped(first.saturating_add(l), at.saturating_sub(group))
2007 }
2008
2009 pub(super) fn scan_diagnostics(
2017 &self,
2018 slot: u32,
2019 forward: bool,
2020 bound: u64,
2021 mut f: impl FnMut(DiagAt<'_>) -> bool,
2022 ) {
2023 let Some(e) = self.edits.as_deref() else {
2024 let i = slot as usize;
2025 let len = self.kinds.len();
2026 let list = &self.diagnostics;
2027 let mut visit = |(n, d): &(u32, Stored)| {
2028 let n = *n as usize;
2029 let rank = u64::try_from(n).unwrap_or(u64::MAX);
2030 let inside = n < len && if forward { rank < bound } else { rank >= bound };
2031 inside
2032 && f(DiagAt {
2033 rank,
2034 start: u64::try_from(self.start_of(n)).unwrap_or(u64::MAX),
2035 diagnostic: d,
2036 from: 0,
2037 to: 0,
2038 })
2039 };
2040 if forward {
2041 let lo = list.partition_point(|(n, _)| (*n as usize) < i);
2042 for x in list.get(lo..).unwrap_or_default() {
2043 if !visit(x) {
2044 return;
2045 }
2046 }
2047 } else {
2048 let hi = list.partition_point(|(n, _)| (*n as usize) <= i);
2049 for x in list.get(..hi).unwrap_or_default().iter().rev() {
2050 if !visit(x) {
2051 return;
2052 }
2053 }
2054 }
2055 return;
2056 };
2057 let Some((mut item, first_run, start)) = self.run_item(slot) else {
2058 return;
2059 };
2060 let (mut count_at, mut bytes_at) = e.seq.prefix(item);
2061 let mut local = first_run.a.saturating_add(slot.saturating_sub(start));
2063 loop {
2064 let Some(run) = e.seq.run(item) else { return };
2065 let run_count = u64::from(run.b.saturating_sub(run.a));
2067 let outside = if forward {
2068 count_at >= bound
2069 } else {
2070 count_at.saturating_add(run_count) <= bound
2071 };
2072 if outside {
2073 return;
2074 }
2075 let flat = self.run_flat(&run).filter(|_| run_count > 0);
2076 if let Some((flat, first, _)) = flat {
2077 let run_from = flat.start(run.a as usize);
2078 let list = flat.diagnostics;
2079 let (lo, hi) = if forward {
2080 (
2081 list.partition_point(|(l, _)| *l < local),
2082 list.partition_point(|(l, _)| *l < run.b),
2083 )
2084 } else {
2085 (
2086 list.partition_point(|(l, _)| *l < run.a),
2087 list.partition_point(|(l, _)| *l <= local),
2088 )
2089 };
2090 let window = list.get(lo..hi.max(lo)).unwrap_or_default();
2091 let mut visit = |(l, d): &(u32, Stored)| {
2092 let rank = count_at.saturating_add(u64::from(l.saturating_sub(run.a)));
2093 let inside = if forward { rank < bound } else { rank >= bound };
2094 let from = flat.start(*l as usize);
2095 let start = u64::try_from(from.saturating_sub(run_from))
2096 .unwrap_or(u64::MAX)
2097 .saturating_add(bytes_at);
2098 inside
2099 && f(DiagAt {
2100 rank,
2101 start,
2102 diagnostic: d,
2103 from,
2104 to: usize::try_from(start).unwrap_or(usize::MAX),
2105 })
2106 };
2107 let gone = |k: usize| self.list_dropped(&flat, first, lo.saturating_add(k));
2109 if forward {
2110 for (k, x) in window.iter().enumerate() {
2111 if !gone(k) && !visit(x) {
2112 return;
2113 }
2114 }
2115 } else {
2116 for (k, x) in window.iter().enumerate().rev() {
2117 if !gone(k) && !visit(x) {
2118 return;
2119 }
2120 }
2121 }
2122 }
2123 let jump = if forward {
2127 e.seq.next_with_diags(item)
2128 } else {
2129 e.seq.prev_with_diags(item)
2130 };
2131 let Some(n) = jump else { return };
2132 let Some(nr) = e.seq.run(n) else { return };
2133 item = n;
2134 (count_at, bytes_at) = e.seq.prefix(n);
2135 local = if forward {
2136 nr.a
2137 } else {
2138 nr.b.saturating_sub(1).max(nr.a)
2140 };
2141 }
2142 }
2143
2144 pub(super) fn edited_diagnostics(&self, e: &Edits, within: Option<u32>) -> Vec<(u32, Stored)> {
2152 let mut out = Vec::new();
2153 let start = match within {
2154 Some(slot) => self
2155 .run_item(slot)
2156 .and_then(|(item, _, first)| Some((item, slot.checked_sub(first)?))),
2157 None => e.seq.first().map(|item| (item, 0)),
2158 };
2159 let size = match within {
2160 Some(slot) => self.nav_size(slot),
2161 None => e.seq.total().0,
2162 };
2163 if let Some((mut item, mut skip)) = start {
2164 let (run_rank, mut bytes_at) = e.seq.prefix(item);
2165 let end = run_rank
2167 .saturating_add(u64::from(skip))
2168 .saturating_add(size);
2169 let mut rank_at = run_rank;
2170 while rank_at < end {
2171 let Some(run) = e.seq.run(item) else { break };
2172 let Some((flat, first, _)) = self.run_flat(&run) else {
2173 break;
2174 };
2175 let a = run.a.saturating_add(skip);
2176 let n = u32::try_from(end.saturating_sub(rank_at))
2177 .unwrap_or(u32::MAX)
2178 .min(run.b.saturating_sub(run.a))
2179 .saturating_sub(skip);
2180 let b = a.saturating_add(n);
2181 let run_from = flat.start(run.a as usize);
2182 let lo = flat.diagnostics.partition_point(|(l, _)| *l < a);
2183 let list = flat.diagnostics.get(lo..).unwrap_or_default();
2184 for (k, (l, d)) in list.iter().take_while(|(l, _)| *l < b).enumerate() {
2185 if self.list_dropped(&flat, first, lo.saturating_add(k)) {
2187 continue;
2188 }
2189 let from = flat.start(*l as usize);
2190 let to = from
2191 .checked_sub(run_from)
2192 .and_then(|x| u64::try_from(x).ok())
2193 .and_then(|x| x.checked_add(bytes_at))
2194 .and_then(|x| usize::try_from(x).ok())
2195 .unwrap_or(usize::MAX);
2196 let mut d = d.clone();
2197 d.shift(from, to);
2198 out.push((first.saturating_add(*l), d));
2199 }
2200 skip = 0;
2201 match e.seq.next_with_diags(item) {
2204 Some(x) => {
2205 item = x;
2206 (rank_at, bytes_at) = e.seq.prefix(x);
2207 }
2208 None => break,
2209 }
2210 }
2211 }
2212 if within.is_none() {
2213 let base_len = self.kinds.len();
2216 let lo = self
2217 .diagnostics
2218 .partition_point(|(n, _)| (*n as usize) < base_len);
2219 let to = usize::try_from(e.seq.total().1).unwrap_or(usize::MAX);
2220 for (_, d) in self.diagnostics.get(lo..).unwrap_or_default() {
2221 let mut d = d.clone();
2222 d.shift(self.source.len(), to);
2223 out.push((NONE, d));
2224 }
2225 }
2226 out
2227 }
2228
2229 pub(super) fn document_of(&self, slot: u32) -> Option<u32> {
2233 let mut x = Some(slot);
2234 while let Some(s) = x {
2235 if self.kind_of(s) == Some(SyntaxKind::Document) {
2236 return Some(s);
2237 }
2238 x = self.nav_parent(s);
2239 }
2240 None
2241 }
2242
2243 pub(super) fn tag_context(&self, slot: u32) -> String {
2248 let mut out = String::new();
2249 let Some(doc) = self.document_of(slot) else {
2250 return out;
2251 };
2252 let mut c = self.nav_first(doc);
2253 while let Some(ch) = c {
2254 let Some(loc) = self.locate(ch) else { break };
2255 match loc.flat.kind(loc.local) {
2256 Some(SyntaxKind::TagDirective) => {
2257 out.push_str(loc.flat.token_text(loc.local));
2258 out.push('\n');
2259 }
2260 Some(k) if is_directive(k) || k.is_trivia() => {}
2261 _ => break,
2262 }
2263 c = self.nav_next(ch);
2264 }
2265 out
2266 }
2267
2268 pub(super) fn fragment_of(
2272 &self,
2273 roots: &[u32],
2274 context: u32,
2275 ) -> Result<Fragment, TreeEditError> {
2276 let (arena, has_tags) = self.copy_forest(roots)?;
2277 let context = if has_tags {
2278 self.tag_context(context)
2279 } else {
2280 String::new()
2281 };
2282 Ok(Fragment {
2283 arena,
2284 context,
2285 has_tags,
2286 })
2287 }
2288
2289 pub(super) fn copy_forest(&self, roots: &[u32]) -> Result<(Arena, bool), TreeEditError> {
2293 self.copy_forest_with(roots, true)
2294 }
2295
2296 fn copy_forest_with(
2300 &self,
2301 roots: &[u32],
2302 slices: bool,
2303 ) -> Result<(Arena, bool), TreeEditError> {
2304 let cap = |n: usize| u32::try_from(n).ok().filter(|n| *n < NONE);
2305 let mut out = Arena::default();
2306 let mut stack: Vec<(u32, u32, bool)> = Vec::new();
2308 let mut open_docs = 0usize;
2310 let mut prefixes: Vec<(usize, String)> = Vec::new();
2311 let mut has_tags = false;
2312 for &root in roots {
2313 if slices && self.copy_slice(root, &mut out, &mut prefixes, &mut has_tags)? {
2316 continue;
2317 }
2318 let count = self.nav_size(root);
2319 let mut x = Some(root);
2320 let mut left = count;
2321 while left > 0 {
2322 left = left.saturating_sub(1);
2323 let slot = x.ok_or(TreeEditError::Internal)?;
2324 x = self.nav_succ(slot);
2325 let loc = self.locate(slot).ok_or(TreeEditError::Internal)?;
2326 let kind = loc.flat.kind(loc.local).ok_or(TreeEditError::Internal)?;
2327 let parent = if slot == root {
2328 None
2329 } else {
2330 self.nav_parent(slot)
2331 };
2332 while let Some(&(g, local, doc)) = stack.last() {
2333 if Some(g) == parent {
2334 break;
2335 }
2336 stack.pop();
2337 if doc {
2338 open_docs = open_docs.saturating_sub(1);
2339 }
2340 let end = cap(out.kinds.len()).ok_or(TreeEditError::Capacity)?;
2341 *out.words
2342 .get_mut(local as usize)
2343 .ok_or(TreeEditError::Internal)? = end;
2344 }
2345 let index = cap(out.kinds.len()).ok_or(TreeEditError::Capacity)?;
2346 let at = out.source.len();
2347 out.kinds.push(kind);
2348 out.parents.push(stack.last().map_or(NONE, |(_, l, _)| *l));
2349 for (k, (_, d)) in loc.flat.diagnostics_at(loc.local).iter().enumerate() {
2350 if self.is_dropped(slot, k) {
2352 continue;
2353 }
2354 let mut d = d.clone();
2355 d.shift(loc.flat.start(loc.local), at);
2356 out.diagnostics.push((index, d));
2357 }
2358 if kind.is_token() {
2359 out.words.push(cap(at).ok_or(TreeEditError::Capacity)?);
2360 let text = loc.flat.token_text(loc.local);
2361 out.source.push_str(text);
2362 if kind == SyntaxKind::Tag && open_docs == 0 {
2363 has_tags = true;
2364 }
2365 if kind == SyntaxKind::BlockScalarHeader {
2366 let owner = stack.last().map(|(_, l, _)| *l);
2370 if let Some(e) = out.extras.last_mut().filter(|(i, _)| Some(*i) == owner) {
2371 if let Some(h) = e.1.block.as_mut() {
2372 h.span = Span::new(at, at.saturating_add(text.len()));
2373 }
2374 }
2375 }
2376 } else {
2377 let doc = kind == SyntaxKind::Document;
2378 out.words.push(index);
2379 stack.push((slot, index, doc));
2380 if doc {
2381 open_docs = open_docs.saturating_add(1);
2382 }
2383 if let Some(extra) = loc.flat.extra(loc.local) {
2384 if let Some(p) = extra.tag_prefix {
2385 let text = loc.flat.source.get(p..).unwrap_or("");
2386 let end = text.find([' ', '\t', '\n', '\r']).unwrap_or(text.len());
2387 prefixes
2388 .push((out.extras.len(), text.get(..end).unwrap_or("").to_owned()));
2389 }
2390 out.extras.push((
2391 index,
2392 Extra {
2393 tag_prefix: None,
2394 block: extra.block,
2395 },
2396 ));
2397 }
2398 }
2399 }
2400 while let Some((_, local, _)) = stack.pop() {
2401 let end = cap(out.kinds.len()).ok_or(TreeEditError::Capacity)?;
2402 *out.words
2403 .get_mut(local as usize)
2404 .ok_or(TreeEditError::Internal)? = end;
2405 }
2406 open_docs = 0;
2407 }
2408 out.tiled = out.source.len();
2409 for (e, text) in prefixes {
2410 let p = out.source.len();
2411 out.source.push_str(&text);
2412 out.source.push('\n');
2413 if let Some(x) = out.extras.get_mut(e) {
2414 x.1.tag_prefix = Some(p);
2415 }
2416 }
2417 cap(out.source.len()).ok_or(TreeEditError::Capacity)?;
2418 Ok((out, has_tags))
2419 }
2420
2421 fn copy_slice(
2430 &self,
2431 root: u32,
2432 out: &mut Arena,
2433 prefixes: &mut Vec<(usize, String)>,
2434 has_tags: &mut bool,
2435 ) -> Result<bool, TreeEditError> {
2436 let Some(loc) = self.locate(root) else {
2437 return Ok(false);
2438 };
2439 let flat = loc.flat;
2440 let l0 = loc.local;
2441 let Ok(count) = usize::try_from(self.nav_size(root)) else {
2442 return Ok(false);
2443 };
2444 let Some(l1) = l0.checked_add(count) else {
2445 return Ok(false);
2446 };
2447 if count == 0 || l1 > flat.len() || flat.end(l0) != l1 {
2448 return Ok(false);
2449 }
2450 if self.edits.is_some() {
2452 let Some((_, run, start)) = self.run_item(root) else {
2453 return Ok(false);
2454 };
2455 let end = run
2456 .b
2457 .checked_sub(run.a)
2458 .and_then(|n| start.checked_add(n))
2459 .and_then(|e| usize::try_from(e).ok());
2460 let last = usize::try_from(root)
2461 .ok()
2462 .and_then(|r| r.checked_add(count));
2463 if !matches!((last, end), (Some(l), Some(e)) if l <= e) {
2464 return Ok(false);
2465 }
2466 }
2467 let Some(kinds) = flat.kinds.get(l0..l1) else {
2468 return Ok(false);
2469 };
2470 if kinds.contains(&SyntaxKind::Document) {
2472 return Ok(false);
2473 }
2474 let tags = kinds.contains(&SyntaxKind::Tag);
2475 let cap = |n: usize| u32::try_from(n).ok().filter(|n| *n < NONE);
2476 let base = out.kinds.len();
2477 let at_base = out.source.len();
2478 let src_a = flat.start(l0);
2479 let src_b = flat.start(l1);
2480 let Some(text) = flat.source.get(src_a..src_b) else {
2481 return Ok(false);
2482 };
2483 cap(base.saturating_add(count)).ok_or(TreeEditError::Capacity)?;
2484 cap(at_base.saturating_add(text.len())).ok_or(TreeEditError::Capacity)?;
2485 let marks = (
2486 out.parents.len(),
2487 out.words.len(),
2488 out.extras.len(),
2489 out.diagnostics.len(),
2490 prefixes.len(),
2491 );
2492 let index = |i: usize| -> u32 {
2495 let x = base.saturating_add(i.saturating_sub(l0));
2496 u32::try_from(x).unwrap_or(NONE)
2497 };
2498 let offset = |at: usize| -> usize { at_base.saturating_add(at.saturating_sub(src_a)) };
2499 let mut tiled = src_a;
2503 let mut ok = true;
2504 let mut headers: Vec<(usize, usize, usize)> = Vec::new();
2505 out.parents.reserve(count);
2506 out.words.reserve(count);
2507 out.kinds.reserve(count);
2508 for (i, kind) in (l0..l1).zip(kinds.iter().copied()) {
2509 let parent = if i == l0 {
2510 NONE
2511 } else {
2512 match flat.parent(i) {
2513 Some(p) if p >= l0 && p < i => index(p),
2514 _ => {
2515 ok = false;
2516 break;
2517 }
2518 }
2519 };
2520 out.parents.push(parent);
2521 if kind.is_token() {
2522 let start = flat.token_start(i).min(flat.tiled);
2523 if start < tiled || start > src_b {
2524 ok = false;
2525 break;
2526 }
2527 tiled = start;
2528 let at = offset(start);
2529 out.words.push(u32::try_from(at).unwrap_or(NONE));
2530 if kind == SyntaxKind::BlockScalarHeader && i != l0 {
2531 headers.push((i, at, flat.token_span(i).len()));
2532 }
2533 } else {
2534 let end = flat.end(i);
2535 if end <= i || end > l1 {
2536 ok = false;
2537 break;
2538 }
2539 out.words.push(index(end));
2540 }
2541 }
2542 if ok {
2543 let lo = flat.extras.partition_point(|(n, _)| (*n as usize) < l0);
2545 let hi = flat.extras.partition_point(|(n, _)| (*n as usize) < l1);
2546 for (n, extra) in flat.extras.get(lo..hi).unwrap_or_default() {
2547 let n = *n as usize;
2548 if flat.kind(n).is_none_or(SyntaxKind::is_token) {
2549 continue;
2550 }
2551 if let Some(p) = extra.tag_prefix {
2552 let t = flat.source.get(p..).unwrap_or("");
2553 let end = t.find([' ', '\t', '\n', '\r']).unwrap_or(t.len());
2554 prefixes.push((out.extras.len(), t.get(..end).unwrap_or("").to_owned()));
2555 }
2556 out.extras.push((
2557 index(n),
2558 Extra {
2559 tag_prefix: None,
2560 block: extra.block,
2561 },
2562 ));
2563 }
2564 for (i, at, len) in headers {
2568 let (Some(p), here) = (flat.parent(i), index(i)) else {
2569 continue;
2570 };
2571 let owner = index(p);
2572 let k = out.extras.partition_point(|(n, _)| *n < here);
2573 let Some(e) = k.checked_sub(1).and_then(|k| out.extras.get_mut(k)) else {
2574 continue;
2575 };
2576 if e.0 == owner {
2577 if let Some(h) = e.1.block.as_mut() {
2578 h.span = Span::new(at, at.saturating_add(len));
2579 }
2580 }
2581 }
2582 let lo = flat
2584 .diagnostics
2585 .partition_point(|(n, _)| (*n as usize) < l0);
2586 let hi = flat
2587 .diagnostics
2588 .partition_point(|(n, _)| (*n as usize) < l1);
2589 let mut prev = usize::MAX;
2590 let mut k = 0usize;
2591 for (n, d) in flat.diagnostics.get(lo..hi).unwrap_or_default() {
2592 let n = *n as usize;
2593 k = if n == prev { k.saturating_add(1) } else { 0 };
2594 prev = n;
2595 let slot = u32::try_from(n.saturating_sub(l0))
2596 .ok()
2597 .and_then(|o| root.checked_add(o))
2598 .ok_or(TreeEditError::Internal)?;
2599 if self.is_dropped(slot, k) {
2600 continue;
2601 }
2602 let from = flat.start(n);
2603 let mut d = d.clone();
2604 d.shift(from, offset(from));
2605 out.diagnostics.push((index(n), d));
2606 }
2607 }
2608 if !ok {
2609 out.parents.truncate(marks.0);
2610 out.words.truncate(marks.1);
2611 out.extras.truncate(marks.2);
2612 out.diagnostics.truncate(marks.3);
2613 prefixes.truncate(marks.4);
2614 return Ok(false);
2615 }
2616 out.kinds.extend_from_slice(kinds);
2617 out.source.push_str(text);
2618 *has_tags |= tags;
2619 Ok(true)
2620 }
2621
2622 pub(super) fn live_slot(&self, id: NodeId) -> Result<u32, TreeEditError> {
2625 Ok(self.get(id)?.slot())
2626 }
2627
2628 pub(super) fn check_parent(&self, parent: u32) -> Result<SyntaxKind, TreeEditError> {
2630 let kind = self.kind_of(parent).ok_or(TreeEditError::Internal)?;
2631 if kind.is_token() {
2632 return Err(TreeEditError::NotANode { kind });
2633 }
2634 if matches!(
2635 kind,
2636 SyntaxKind::Scalar | SyntaxKind::Alias | SyntaxKind::Error
2637 ) {
2638 return Err(TreeEditError::ReadOnly { kind });
2639 }
2640 Ok(kind)
2641 }
2642
2643 pub(super) fn sibling_range(
2645 &self,
2646 first: u32,
2647 last: u32,
2648 ) -> Result<(u32, Vec<u32>), TreeEditError> {
2649 let parent = self.nav_parent(first).ok_or(TreeEditError::NoParent)?;
2650 if self.nav_parent(last) != Some(parent) {
2651 return Err(TreeEditError::NotSiblings);
2652 }
2653 let mut roots = vec![first];
2654 let mut x = first;
2655 while x != last {
2656 x = self.nav_next(x).ok_or(TreeEditError::NotSiblings)?;
2657 roots.push(x);
2658 }
2659 Ok((parent, roots))
2660 }
2661
2662 pub(super) fn check_removable(&self, roots: &[u32]) -> Result<(), TreeEditError> {
2664 for &r in roots {
2665 let kind = self.kind_of(r).ok_or(TreeEditError::Internal)?;
2666 if is_directive(kind) || is_node_property(kind) {
2667 return Err(TreeEditError::ReadOnly { kind });
2668 }
2669 }
2670 if self.error_count() > 0 {
2677 for &r in roots {
2678 if self.kind_of(r) == Some(SyntaxKind::Document) {
2679 continue;
2680 }
2681 let error = super::Node::new(self, r)
2682 .descendants()
2683 .any(|n| n.kind() == SyntaxKind::Error);
2684 if error {
2685 return Err(TreeEditError::ReadOnly {
2686 kind: SyntaxKind::Error,
2687 });
2688 }
2689 }
2690 }
2691 Ok(())
2692 }
2693
2694 pub(super) fn check_insertable(
2696 &self,
2697 parent: u32,
2698 parent_kind: SyntaxKind,
2699 fragment: &Fragment,
2700 ) -> Result<(), TreeEditError> {
2701 if fragment.is_empty() {
2702 return Err(TreeEditError::EmptyFragment);
2703 }
2704 for kind in fragment.root_kinds() {
2705 if is_directive(kind) || is_node_property(kind) {
2706 return Err(TreeEditError::ReadOnly { kind });
2707 }
2708 let fits = match (parent_kind, kind) {
2709 (_, SyntaxKind::Stream) => false,
2710 (SyntaxKind::Stream, k) => k == SyntaxKind::Document || k.is_token(),
2711 (_, SyntaxKind::Document) => false,
2712 _ => true,
2713 };
2714 if !fits {
2715 return Err(TreeEditError::Misplaced {
2716 kind,
2717 parent: parent_kind,
2718 });
2719 }
2720 }
2721 if fragment.has_tags && fragment.context != self.tag_context(parent) {
2722 return Err(TreeEditError::TagContext);
2723 }
2724 Ok(())
2725 }
2726
2727 fn ensure_edits(&mut self) -> Result<(), TreeEditError> {
2731 if self.edits.is_some() {
2732 return Ok(());
2733 }
2734 let len = u32::try_from(self.kinds.len()).map_err(|_| TreeEditError::Capacity)?;
2735 let bytes = u64::try_from(self.source.len()).map_err(|_| TreeEditError::Capacity)?;
2736 let diags = self.base_flat().diagnostics_in(0, len);
2737 let marks = marks(self.base_flat(), &self.run_facts, Some(&self.facts), 0, len);
2738 let seq = Seq::new(Run {
2739 arena: 0,
2740 graft: NONE,
2741 a: 0,
2742 b: len,
2743 bytes,
2744 diags,
2745 trivia: false,
2747 marks,
2748 });
2749 let mut runs = BTreeMap::new();
2750 runs.insert(0, seq.first().ok_or(TreeEditError::Internal)?);
2751 self.edits = Some(Box::new(Edits {
2752 arenas: BTreeMap::new(),
2753 grafts: Slab::default(),
2754 seq,
2755 runs,
2756 links: BTreeMap::new(),
2757 dropped: BTreeSet::new(),
2758 next_slot: len.max(self.slot_floor),
2761 }));
2762 Ok(())
2763 }
2764
2765 #[cfg(test)]
2768 fn cut_before(&mut self, slot: u32) -> Result<u32, TreeEditError> {
2769 self.cut_logged(slot, None)
2770 }
2771
2772 fn cut_logged(&mut self, slot: u32, undo: Option<&mut Undo>) -> Result<u32, TreeEditError> {
2774 let (item, run, start) = self.run_item(slot).ok_or(TreeEditError::Internal)?;
2775 let offset = slot.checked_sub(start).ok_or(TreeEditError::Internal)?;
2776 if offset == 0 {
2777 return Ok(item);
2778 }
2779 let (flat, _, _) = self.run_flat(&run).ok_or(TreeEditError::Internal)?;
2780 let mid = run.a.checked_add(offset).ok_or(TreeEditError::Internal)?;
2781 let left_bytes = flat
2782 .start(mid as usize)
2783 .checked_sub(flat.start(run.a as usize))
2784 .and_then(|b| u64::try_from(b).ok())
2785 .ok_or(TreeEditError::Internal)?;
2786 let left_diags = flat.diagnostics_in(run.a, mid);
2787 let (left_trivia, right_trivia) = if run.trivia {
2789 (true, true)
2790 } else {
2791 (
2792 self.stream_trivia(run.arena, run.a, mid),
2793 self.stream_trivia(run.arena, mid, run.b),
2794 )
2795 };
2796 let left_marks = self.run_marks(run.arena, run.a, mid);
2798 let right_marks = self.run_marks(run.arena, mid, run.b);
2799 let left = Run {
2800 b: mid,
2801 bytes: left_bytes,
2802 diags: left_diags,
2803 trivia: left_trivia,
2804 marks: left_marks,
2805 ..run
2806 };
2807 let right = Run {
2808 a: mid,
2809 bytes: run.bytes.saturating_sub(left_bytes),
2810 diags: run.diags.saturating_sub(left_diags),
2811 trivia: right_trivia,
2812 marks: right_marks,
2813 ..run
2814 };
2815 let e = self.edits.as_deref_mut().ok_or(TreeEditError::Internal)?;
2816 if !e.seq.can_insert(1) {
2818 return Err(TreeEditError::Capacity);
2819 }
2820 let new = e
2821 .seq
2822 .insert_after(Some(item), right)
2823 .ok_or(TreeEditError::Capacity)?;
2824 e.seq.set_run(item, left);
2825 e.runs.insert(slot, new);
2826 if let Some(u) = undo {
2827 u.cuts.push(slot);
2828 }
2829 Ok(new)
2830 }
2831
2832 fn set_links(
2833 &mut self,
2834 slot: u32,
2835 undo: &mut Undo,
2836 f: impl FnOnce(&mut Links),
2837 ) -> Result<(), TreeEditError> {
2838 let mut l = self.links_of(slot);
2839 f(&mut l);
2840 let e = self.edits.as_deref_mut().ok_or(TreeEditError::Internal)?;
2841 let old = e.links.insert(slot, l);
2842 undo.links.push((slot, old));
2843 Ok(())
2844 }
2845
2846 pub(super) fn splice(
2853 &mut self,
2854 parent: u32,
2855 prev: Option<u32>,
2856 removed: &[u32],
2857 fragment: Option<Fragment>,
2858 validate: bool,
2859 ) -> Result<Spliced, TreeEditError> {
2860 self.splice_dropping(parent, prev, removed, fragment, validate, &[])
2861 }
2862
2863 fn splice_dropping(
2867 &mut self,
2868 parent: u32,
2869 prev: Option<u32>,
2870 removed: &[u32],
2871 fragment: Option<Fragment>,
2872 validate: bool,
2873 drops: &[(u32, u32)],
2874 ) -> Result<Spliced, TreeEditError> {
2875 let mut a = self.splice_apply(parent, prev, removed, fragment, validate)?;
2876 if let Some(e) = self.edits.as_deref_mut() {
2877 for &d in drops {
2878 if e.dropped.insert(d) {
2879 a.undo.dropped.push(d);
2880 }
2881 }
2882 }
2883 if validate {
2884 let c = a.check;
2885 if let Err(err) = self.check_well_formed(c.parent, c.prev, c.next, a.span, c.what) {
2886 self.undo(a.undo)?;
2887 return Err(err);
2888 }
2889 }
2890 self.accept(a.undo);
2891 Ok((a.taken, a.span))
2892 }
2893
2894 fn accept(&mut self, undo: Undo) {
2897 let seams = self.seams(&undo);
2898 self.accept_with(undo, seams);
2899 }
2900
2901 fn accept_with(&mut self, undo: Undo, seams: Vec<u32>) {
2903 if self.group.depth > 0 {
2904 self.group.log.push((undo, seams));
2907 return;
2908 }
2909 self.coalesce(&seams);
2910 self.release(&undo);
2911 }
2912
2913 pub fn begin_group(&mut self) -> GroupMark {
2926 self.group.depth = self.group.depth.saturating_add(1);
2927 GroupMark {
2928 tree: self.stamp,
2929 at: self.group.log.len(),
2930 depth: self.group.depth,
2931 }
2932 }
2933
2934 fn check_mark(&self, mark: GroupMark) -> Result<(), TreeEditError> {
2936 if mark.tree != self.stamp
2937 || mark.depth != self.group.depth
2938 || mark.at > self.group.log.len()
2939 {
2940 return Err(TreeEditError::Internal);
2941 }
2942 Ok(())
2943 }
2944
2945 pub(super) fn settle_group_copy(&self, copy: &mut Self) {
2951 for (_, seams) in &self.group.log {
2952 copy.coalesce(seams);
2953 }
2954 for (undo, _) in &self.group.log {
2955 copy.release(undo);
2956 }
2957 }
2958
2959 pub fn end_group(&mut self, mark: GroupMark) -> Result<(), TreeEditError> {
2968 self.check_mark(mark)?;
2969 self.group.depth = self.group.depth.saturating_sub(1);
2970 if self.group.depth == 0 {
2971 let log = std::mem::take(&mut self.group.log);
2972 for (_, seams) in &log {
2973 self.coalesce(seams);
2974 }
2975 for (undo, _) in &log {
2976 self.release(undo);
2977 }
2978 }
2979 Ok(())
2980 }
2981
2982 pub fn rollback_group(&mut self, mark: GroupMark) -> Result<(), TreeEditError> {
2992 self.check_mark(mark)?;
2993 let high = self.next_slot();
2998 let undone = self.group.log.split_off(mark.at);
2999 self.group.depth = self.group.depth.saturating_sub(1);
3000 for (undo, _) in undone.into_iter().rev() {
3001 self.undo(undo)?;
3002 }
3003 match self.edits.as_deref_mut() {
3004 Some(e) => e.next_slot = e.next_slot.max(high),
3005 None => self.slot_floor = self.slot_floor.max(high),
3006 }
3007 if self.group.depth == 0 {
3008 let log = std::mem::take(&mut self.group.log);
3011 for (_, seams) in &log {
3012 self.coalesce(seams);
3013 }
3014 for (undo, _) in &log {
3015 self.release(undo);
3016 }
3017 }
3018 Ok(())
3019 }
3020
3021 #[must_use]
3023 pub fn in_group(&self) -> bool {
3024 self.group.depth > 0
3025 }
3026
3027 fn release(&mut self, u: &Undo) {
3030 if let Some(e) = self.edits.as_deref_mut() {
3031 e.release(&u.doomed);
3032 }
3033 }
3034
3035 pub(super) fn splice_pair(
3042 &mut self,
3043 first: SpliceArgs,
3044 second: impl FnOnce(&Self, Option<(u32, u32)>) -> Result<Option<SpliceArgs>, TreeEditError>,
3045 ) -> Result<(Spliced, Option<Spliced>), TreeEditError> {
3046 let a = self.splice_apply(
3047 first.parent,
3048 first.prev,
3049 &first.removed,
3050 first.fragment,
3051 true,
3052 )?;
3053 let plan = match second(self, a.span) {
3054 Ok(p) => p,
3055 Err(err) => {
3056 self.undo(a.undo)?;
3057 return Err(err);
3058 }
3059 };
3060 let b = match plan {
3061 Some(s) => match self.splice_apply(s.parent, s.prev, &s.removed, s.fragment, true) {
3062 Ok(b) => Some(b),
3063 Err(err) => {
3064 self.undo(a.undo)?;
3065 return Err(err);
3066 }
3067 },
3068 None => None,
3069 };
3070 let mut a = a;
3074 if let (Some(n), Some(b)) = (a.check.next, &b) {
3075 if !self.is_live(n) {
3076 a.check.next = b.span.map(|s| s.0).or(b.check.next);
3077 }
3078 }
3079 let mut what = a.check.what;
3084 let mut ordered = true;
3085 if let Some(b) = &b {
3086 let from = self.rank_after(&b.check, b.span);
3087 let adjacent = Some(self.rank_after(&a.check, a.span))
3096 == match b.span {
3097 Some((f, _)) => self.nav_rank(f).map(|r| r.0),
3098 None => Some(from),
3099 };
3100 let head = a.span.map(|s| s.0).or(a.check.next);
3101 let head_rank = head.and_then(|h| self.nav_rank(h)).map(|r| r.0);
3102 ordered = adjacent && head_rank.is_none_or(|h| h <= from);
3103 let more =
3104 i128::from(b.check.what.added).saturating_sub(i128::from(b.check.what.removed));
3105 what.later = Some((from, more));
3106 }
3107 debug_assert!(
3108 ordered,
3109 "splice_pair: the second splice precedes the first or is not next to it"
3110 );
3111 let mut checked = if ordered {
3112 let c = &a.check;
3113 self.check_well_formed(c.parent, c.prev, c.next, a.span, what)
3114 } else {
3115 Err(TreeEditError::Internal)
3116 };
3117 if let (Ok(()), Some(b)) = (&checked, &b) {
3118 let c = &b.check;
3119 checked = self.check_well_formed(c.parent, c.prev, c.next, b.span, c.what);
3120 }
3121 if let Err(err) = checked {
3122 if let Some(b) = b {
3123 self.undo(b.undo)?;
3124 }
3125 self.undo(a.undo)?;
3126 return Err(err);
3127 }
3128 let seams_a = self.seams(&a.undo);
3131 let spliced_a = (a.taken, a.span);
3132 let Some(b) = b else {
3133 self.accept_with(a.undo, seams_a);
3134 return Ok((spliced_a, None));
3135 };
3136 let seams_b = self.seams(&b.undo);
3137 self.accept_with(a.undo, seams_a);
3138 self.accept_with(b.undo, seams_b);
3139 Ok((spliced_a, Some((b.taken, b.span))))
3140 }
3141
3142 fn rank_after(&self, check: &Check, span: Option<(u32, u32)>) -> u64 {
3145 let x = match (span, check.next, check.prev) {
3146 (Some((_, l)), _, _) => self.nav_after(l),
3147 (None, Some(n), _) => Some(n),
3148 (None, None, Some(p)) => self.nav_after(p),
3149 (None, None, None) => self.nav_after(check.parent),
3150 };
3151 x.and_then(|x| self.nav_rank(x))
3152 .map_or(self.nav_total().0, |r| r.0)
3153 }
3154
3155 fn splice_apply(
3159 &mut self,
3160 parent: u32,
3161 prev: Option<u32>,
3162 removed: &[u32],
3163 fragment: Option<Fragment>,
3164 validate: bool,
3165 ) -> Result<Applied, TreeEditError> {
3166 let next = match removed.last() {
3168 Some(&l) => self.nav_next(l),
3169 None => match prev {
3170 Some(p) => self.nav_next(p),
3171 None => self.nav_first(parent),
3172 },
3173 };
3174 let cut = match removed.last() {
3176 Some(&l) => self.nav_after(l),
3177 None => match next {
3178 Some(n) => Some(n),
3179 None => self.nav_after(parent),
3180 },
3181 };
3182 let taken = if removed.is_empty() {
3183 None
3184 } else {
3185 Some(self.fragment_of(removed, parent)?)
3186 };
3187 let limits = self.settings.get_limits();
3194 let removed_bytes = taken.as_ref().map_or(0, |t| t.arena.tiled);
3195 let added_bytes = fragment.as_ref().map_or(0, |f| f.arena.tiled);
3196 let total = usize::try_from(self.nav_total().1).map_err(|_| TreeEditError::Capacity)?;
3197 let new_total = total
3198 .saturating_sub(removed_bytes)
3199 .saturating_add(added_bytes);
3200 if validate && new_total > limits.get_max_document_size() && new_total > total {
3201 return Err(TreeEditError::Limit {
3202 code: oneyaml_core::code::DOCUMENT_TOO_LARGE,
3203 });
3204 }
3205 let (docs_removed, docs_added) = if parent == 0 {
3206 (
3207 removed
3208 .iter()
3209 .filter(|&&r| self.kind_of(r) == Some(SyntaxKind::Document))
3210 .count(),
3211 fragment.as_ref().map_or(0, |f| {
3212 f.root_kinds()
3213 .filter(|k| *k == SyntaxKind::Document)
3214 .count()
3215 }),
3216 )
3217 } else {
3218 (0, 0)
3219 };
3220 let documents = self
3221 .documents
3222 .saturating_sub(docs_removed)
3223 .saturating_add(docs_added);
3224 let error_count = |a: &Arena| a.diagnostics.iter().filter(|(_, d)| d.is_error()).count();
3227 let errors = self
3228 .errors
3229 .saturating_sub(taken.as_ref().map_or(0, |t| error_count(&t.arena)))
3230 .saturating_add(fragment.as_ref().map_or(0, |f| error_count(&f.arena)));
3231 if validate && docs_added > 0 && documents > limits.get_max_documents() {
3232 return Err(TreeEditError::Limit {
3233 code: oneyaml_core::code::TOO_MANY_DOCUMENTS,
3234 });
3235 }
3236 let what = Removed {
3237 trivia_only: taken
3240 .as_ref()
3241 .is_none_or(|t| t.arena.diagnostics.is_empty())
3242 && removed.iter().all(|&r| {
3243 self.kind_of(r).is_some_and(|k| {
3244 matches!(
3245 k,
3246 SyntaxKind::Whitespace | SyntaxKind::LineBreak | SyntaxKind::Comment
3247 )
3248 })
3249 }),
3250 comment: removed
3251 .iter()
3252 .any(|&r| self.kind_of(r) == Some(SyntaxKind::Comment)),
3253 next_line_start: match removed.last() {
3255 Some(&r) => self.kind_of(r) == Some(SyntaxKind::LineBreak),
3256 None => match prev {
3258 Some(p) => self.kind_of(p) == Some(SyntaxKind::LineBreak),
3259 None => parent == 0,
3260 },
3261 },
3262 added: u64::try_from(added_bytes).map_err(|_| TreeEditError::Capacity)?,
3263 removed: u64::try_from(removed_bytes).map_err(|_| TreeEditError::Capacity)?,
3264 later: None,
3265 old_column: (validate
3267 && prev.is_none()
3268 && self.errors == 0
3269 && self.kind_of(parent) == Some(SyntaxKind::BlockMapping))
3270 .then(|| self.entry_column(parent))
3271 .flatten(),
3272 line_break: taken
3274 .as_ref()
3275 .is_some_and(|t| t.text().contains(['\n', '\r'])),
3276 };
3277 let mut new_first = None;
3278 if let Some(f) = &fragment {
3279 let next_slot = self.next_slot() as usize;
3281 let end = next_slot
3282 .checked_add(f.len())
3283 .ok_or(TreeEditError::Capacity)?;
3284 if u32::try_from(end).map_or(true, |e| e == NONE) {
3285 return Err(TreeEditError::Capacity);
3286 }
3287 new_first = Some(u32::try_from(next_slot).map_err(|_| TreeEditError::Capacity)?);
3288 }
3289
3290 let created = self.edits.is_none();
3292 self.ensure_edits()?;
3293 let mut undo = Undo {
3294 created,
3295 next_slot: self.edits.as_deref().map_or(0, |e| e.next_slot),
3296 documents: self.documents,
3297 errors: self.errors,
3298 ..Undo::default()
3299 };
3300 let plan = Plan {
3301 parent,
3302 prev,
3303 next,
3304 cut,
3305 new_first,
3306 };
3307 match self.apply(plan, removed, fragment, &mut undo) {
3308 Ok(span) => {
3309 self.documents = documents;
3310 self.errors = errors;
3311 Ok(Applied {
3312 taken,
3313 span,
3314 undo,
3315 check: Check {
3316 parent,
3317 prev,
3318 next,
3319 what,
3320 },
3321 })
3322 }
3323 Err(err) => {
3324 self.undo(undo)?;
3325 Err(err)
3326 }
3327 }
3328 }
3329
3330 fn apply(
3332 &mut self,
3333 plan: Plan,
3334 removed: &[u32],
3335 fragment: Option<Fragment>,
3336 undo: &mut Undo,
3337 ) -> Result<Option<(u32, u32)>, TreeEditError> {
3338 let Plan {
3339 parent,
3340 prev,
3341 next,
3342 cut,
3343 new_first,
3344 } = plan;
3345 if let Some(&first) = removed.first() {
3346 let from = self.cut_logged(first, Some(undo))?;
3347 let until = cut.map(|c| self.cut_logged(c, Some(undo))).transpose()?;
3348 let e = self.edits.as_deref_mut().ok_or(TreeEditError::Internal)?;
3349 undo.after = match e.seq.prev(from) {
3350 Some(item) => Some(e.run_start(item).ok_or(TreeEditError::Internal)?),
3351 None => None,
3352 };
3353 let mut doomed = Vec::new();
3354 let mut at = Some(from);
3355 while let Some(item) = at {
3356 if Some(item) == until {
3357 break;
3358 }
3359 doomed.push(item);
3360 at = e.seq.next(item);
3361 }
3362 for item in doomed {
3363 let run = e.seq.run(item).ok_or(TreeEditError::Internal)?;
3364 let key = run
3365 .arena
3366 .checked_add(run.a)
3367 .ok_or(TreeEditError::Internal)?;
3368 e.runs.remove(&key);
3369 e.seq.remove(item);
3370 undo.doomed.push((key, run));
3371 }
3372 }
3373 let mut span = None;
3374 if let (Some(fragment), Some(first)) = (fragment, new_first) {
3375 let before = match cut {
3376 Some(c) => Some(self.cut_logged(c, Some(undo))?),
3377 None => None,
3378 };
3379 let e = self.edits.as_deref_mut().ok_or(TreeEditError::Internal)?;
3380 let after = match before {
3381 Some(b) => e.seq.prev(b),
3382 None => e.seq.last(),
3383 };
3384 let len = u32::try_from(fragment.len()).map_err(|_| TreeEditError::Capacity)?;
3385 let bytes = u64::try_from(fragment.arena.tiled).map_err(|_| TreeEditError::Capacity)?;
3386 let id = first;
3389 let last_root = fragment.arena.flat().roots().last().unwrap_or(0);
3390 let last = first
3391 .checked_add(u32::try_from(last_root).map_err(|_| TreeEditError::Internal)?)
3392 .ok_or(TreeEditError::Internal)?;
3393 let next_slot = first.checked_add(len).ok_or(TreeEditError::Capacity)?;
3394 if !e.seq.can_insert(1) {
3396 return Err(TreeEditError::Capacity);
3397 }
3398 let facts = if parent == 0 {
3401 let flat = fragment.arena.flat();
3402 let errors = flat.diagnostics.iter().any(|(_, d)| d.is_error());
3403 StreamFacts::of(flat, flat.roots(), errors)
3404 } else {
3405 StreamFacts::default()
3406 };
3407 let trivia =
3409 parent == 0 && all_stream_trivia(fragment.arena.flat(), &facts, false, 0, len);
3410 let runs = RunFacts::of(fragment.arena.flat());
3413 let marks = marks(
3414 fragment.arena.flat(),
3415 &runs,
3416 (parent == 0).then_some(&facts),
3417 0,
3418 len,
3419 );
3420 let diags = fragment.arena.flat().diagnostics_in(0, len);
3421 let graft = e
3423 .add_graft(
3424 first,
3425 Grafted {
3426 parent,
3427 arena: fragment.arena,
3428 facts,
3429 runs,
3430 },
3431 )
3432 .ok_or(TreeEditError::Capacity)?;
3433 let run = Run {
3434 arena: id,
3435 graft,
3436 a: 0,
3437 b: len,
3438 bytes,
3439 diags,
3440 trivia,
3441 marks,
3442 };
3443 let Some(item) = e.seq.insert_after(after, run) else {
3444 e.drop_graft(first, false);
3445 return Err(TreeEditError::Capacity);
3446 };
3447 undo.grafted = Some(first);
3448 undo.arena_pushed = true;
3449 e.runs.insert(first, item);
3450 e.next_slot = next_slot;
3451 span = Some((first, last));
3452 }
3453
3454 let (head, tail) = match span {
3456 Some((f, l)) => (Some(f), Some(l)),
3457 None => (next, prev),
3458 };
3459 match prev {
3460 Some(p) => self.set_links(p, undo, |l| l.next = head.unwrap_or(NONE))?,
3461 None => self.set_links(parent, undo, |l| l.first = head.unwrap_or(NONE))?,
3462 }
3463 match next {
3464 Some(n) => self.set_links(n, undo, |l| l.prev = tail.unwrap_or(NONE))?,
3465 None => self.set_links(parent, undo, |l| l.last = tail.unwrap_or(NONE))?,
3466 }
3467 if let Some((f, l)) = span {
3468 self.set_links(f, undo, |x| x.prev = prev.unwrap_or(NONE))?;
3469 self.set_links(l, undo, |x| x.next = next.unwrap_or(NONE))?;
3470 }
3471 Ok(span)
3472 }
3473
3474 fn undo(&mut self, u: Undo) -> Result<(), TreeEditError> {
3478 self.documents = u.documents;
3479 self.errors = u.errors;
3480 if u.created {
3481 self.edits = None;
3482 return Ok(());
3483 }
3484 let e = self.edits.as_deref_mut().ok_or(TreeEditError::Internal)?;
3485 for d in &u.dropped {
3486 e.dropped.remove(d);
3487 }
3488 for (slot, old) in u.links.into_iter().rev() {
3489 match old {
3490 Some(l) => e.links.insert(slot, l),
3491 None => e.links.remove(&slot),
3492 };
3493 }
3494 if let Some(first) = u.grafted {
3495 let item = e.runs.remove(&first).ok_or(TreeEditError::Internal)?;
3496 e.seq.remove(item);
3497 if u.arena_pushed {
3498 e.drop_graft(first, false);
3499 }
3500 }
3501 e.next_slot = u.next_slot;
3502 let mut at = match u.after {
3503 Some(key) => Some(*e.runs.get(&key).ok_or(TreeEditError::Internal)?),
3504 None => None,
3505 };
3506 for (key, run) in u.doomed {
3507 let item = e.seq.insert_after(at, run).ok_or(TreeEditError::Internal)?;
3509 e.runs.insert(key, item);
3510 at = Some(item);
3511 }
3512 for slot in u.cuts.into_iter().rev() {
3515 e.merge_at(slot);
3516 }
3517 Ok(())
3518 }
3519
3520 fn seams(&self, u: &Undo) -> Vec<u32> {
3524 let mut out = u.cuts.clone();
3525 let Some(e) = self.edits.as_deref() else {
3526 return out;
3527 };
3528 if !u.doomed.is_empty() {
3529 let after = match u.after {
3530 Some(key) => e.runs.get(&key).and_then(|a| e.seq.next(*a)),
3531 None => e.seq.first(),
3532 };
3533 if let Some(key) = after.and_then(|item| e.run_start(item)) {
3534 out.push(key);
3535 }
3536 }
3537 out
3538 }
3539
3540 fn coalesce(&mut self, seams: &[u32]) {
3546 if let Some(e) = self.edits.as_deref_mut() {
3547 for &slot in seams {
3548 e.merge_at(slot);
3549 }
3550 }
3551 }
3552
3553 fn inserted(&self, span: Option<(u32, u32)>) -> Result<Inserted, TreeEditError> {
3554 let (f, l) = span.ok_or(TreeEditError::Internal)?;
3555 Ok(Inserted {
3556 first: self.id_of(f),
3557 last: self.id_of(l),
3558 })
3559 }
3560
3561 pub fn extract(&self, first: NodeId, last: NodeId) -> Result<Fragment, TreeEditError> {
3575 let (f, l) = (self.live_slot(first)?, self.live_slot(last)?);
3576 let (parent, roots) = self.sibling_range(f, l)?;
3577 self.fragment_of(&roots, parent)
3578 }
3579
3580 pub fn remove(&mut self, id: NodeId) -> Result<Fragment, TreeEditError> {
3587 self.remove_range(id, id)
3588 }
3589
3590 pub fn remove_range(&mut self, first: NodeId, last: NodeId) -> Result<Fragment, TreeEditError> {
3606 let (f, l) = (self.live_slot(first)?, self.live_slot(last)?);
3607 let (parent, roots) = self.sibling_range(f, l)?;
3608 self.check_parent(parent)?;
3609 self.check_removable(&roots)?;
3610 let prev = self.nav_prev(f);
3611 let (taken, _) = self.splice(parent, prev, &roots, None, true)?;
3615 taken.ok_or(TreeEditError::Internal)
3616 }
3617
3618 pub fn replace(&mut self, id: NodeId, with: Fragment) -> Result<Replaced, TreeEditError> {
3624 self.replace_range(id, id, with)
3625 }
3626
3627 pub fn replace_range(
3636 &mut self,
3637 first: NodeId,
3638 last: NodeId,
3639 with: Fragment,
3640 ) -> Result<Replaced, TreeEditError> {
3641 let (f, l) = (self.live_slot(first)?, self.live_slot(last)?);
3642 let (parent, roots) = self.sibling_range(f, l)?;
3643 let pk = self.check_parent(parent)?;
3644 self.check_removable(&roots)?;
3645 self.check_insertable(parent, pk, &with)?;
3646 let prev = self.nav_prev(f);
3647 let (taken, span) = self.splice_leaving_warnings(parent, prev, roots, Some(with))?;
3648 Ok(Replaced {
3649 removed: taken.ok_or(TreeEditError::Internal)?,
3650 inserted: self.inserted(span)?,
3651 })
3652 }
3653
3654 pub fn insert_before(
3667 &mut self,
3668 sibling: NodeId,
3669 fragment: Fragment,
3670 ) -> Result<Inserted, TreeEditError> {
3671 let s = self.live_slot(sibling)?;
3672 let parent = self.nav_parent(s).ok_or(TreeEditError::NoParent)?;
3673 let prev = self.nav_prev(s);
3674 self.insert_at(parent, prev, fragment)
3675 }
3676
3677 pub fn insert_after(
3683 &mut self,
3684 sibling: NodeId,
3685 fragment: Fragment,
3686 ) -> Result<Inserted, TreeEditError> {
3687 let s = self.live_slot(sibling)?;
3688 let parent = self.nav_parent(s).ok_or(TreeEditError::NoParent)?;
3689 self.insert_at(parent, Some(s), fragment)
3690 }
3691
3692 pub fn append_child(
3699 &mut self,
3700 parent: NodeId,
3701 fragment: Fragment,
3702 ) -> Result<Inserted, TreeEditError> {
3703 let p = self.live_slot(parent)?;
3704 self.check_parent(p)?;
3705 let prev = self.nav_last(p);
3706 self.insert_at(p, prev, fragment)
3707 }
3708
3709 #[doc(hidden)]
3717 pub fn insert_child(
3718 &mut self,
3719 parent: NodeId,
3720 position: usize,
3721 fragment: Fragment,
3722 ) -> Result<Inserted, TreeEditError> {
3723 let p = self.live_slot(parent)?;
3724 self.check_parent(p)?;
3725 let mut prev = None;
3726 let mut seen = 0usize;
3727 while seen < position {
3728 let next = match prev {
3729 None => self.nav_first(p),
3730 Some(x) => self.nav_next(x),
3731 };
3732 match next {
3733 Some(n) => prev = Some(n),
3734 None => {
3735 return Err(TreeEditError::Position {
3736 position,
3737 len: seen,
3738 });
3739 }
3740 }
3741 seen = seen.saturating_add(1);
3742 }
3743 self.insert_at(p, prev, fragment)
3744 }
3745
3746 fn insert_at(
3747 &mut self,
3748 parent: u32,
3749 prev: Option<u32>,
3750 fragment: Fragment,
3751 ) -> Result<Inserted, TreeEditError> {
3752 let pk = self.check_parent(parent)?;
3753 self.check_insertable(parent, pk, &fragment)?;
3754 let (_, span) = self.splice(parent, prev, &[], Some(fragment), true)?;
3755 self.inserted(span)
3756 }
3757
3758 pub fn replace_token(&mut self, id: NodeId, text: &str) -> Result<NodeId, TreeEditError> {
3777 let x = self.live_slot(id)?;
3778 let kind = self.kind_of(x).ok_or(TreeEditError::Internal)?;
3779 if !kind.is_token() {
3780 return Err(TreeEditError::NotAToken { kind });
3781 }
3782 if !REPLACEABLE.contains(&kind) {
3783 return Err(TreeEditError::ReadOnly { kind });
3784 }
3785 let parent = self.nav_parent(x).ok_or(TreeEditError::Internal)?;
3786 let flow = {
3787 let mut at = Some(parent);
3788 let mut flow = false;
3789 while let Some(a) = at {
3790 match self.kind_of(a) {
3791 Some(
3792 SyntaxKind::FlowMapping | SyntaxKind::FlowSequence | SyntaxKind::FlowPair,
3793 ) => {
3794 flow = true;
3795 break;
3796 }
3797 Some(SyntaxKind::Document | SyntaxKind::Stream) | None => break,
3798 _ => at = self.nav_parent(a),
3799 }
3800 }
3801 flow
3802 };
3803 let fragment = token_fragment(kind, text, flow, &self.settings)?;
3804 let validate = kind != SyntaxKind::Comment
3811 || self.error_count() > 0
3812 || !self.diagnostics_of(x).is_empty();
3813 let prev = self.nav_prev(x);
3814 let (_, span) = if validate {
3815 self.splice_leaving_warnings(parent, prev, vec![x], Some(fragment))?
3816 } else {
3817 self.splice(parent, prev, &[x], Some(fragment), false)?
3818 };
3819 Ok(self.inserted(span)?.first)
3820 }
3821
3822 fn splice_leaving_warnings(
3835 &mut self,
3836 parent: u32,
3837 prev: Option<u32>,
3838 roots: Vec<u32>,
3839 fragment: Option<Fragment>,
3840 ) -> Result<Spliced, TreeEditError> {
3841 let Some((next, nths)) = self.orphaned_warnings(&roots)? else {
3842 return self.splice(parent, prev, &roots, fragment, true);
3843 };
3844 match self.splice(parent, prev, &roots, fragment.clone(), true) {
3845 Err(TreeEditError::NotWellFormed) => {}
3846 done => return done,
3847 }
3848 let drops: Vec<(u32, u32)> = nths.into_iter().map(|n| (next, n)).collect();
3849 self.splice_dropping(parent, prev, &roots, fragment, true, &drops)
3850 }
3851
3852 fn orphaned_warnings(&self, roots: &[u32]) -> Result<Option<(u32, Vec<u32>)>, TreeEditError> {
3858 let (Some(&f), Some(&l)) = (roots.first(), roots.last()) else {
3859 return Ok(None);
3860 };
3861 let Some(next) = self.nav_after(l) else {
3862 return Ok(None);
3863 };
3864 let Some(loc) = self.locate(next) else {
3866 return Ok(None);
3867 };
3868 if loc.flat.diagnostics.is_empty() {
3869 return Ok(None);
3870 }
3871 let list = loc.flat.diagnostics_at(loc.local);
3872 if list.is_empty() {
3873 return Ok(None);
3874 }
3875 let lo = self.nav_bytes(f).ok_or(TreeEditError::Internal)?.0;
3876 let hi = self.nav_bytes(l).ok_or(TreeEditError::Internal)?.1;
3877 let mut nths = Vec::new();
3878 let from = loc.flat.start(loc.local);
3879 let to = self.nav_bytes(next).ok_or(TreeEditError::Internal)?.0;
3880 let to = usize::try_from(to).map_err(|_| TreeEditError::Internal)?;
3881 for (k, (_, d)) in list.iter().enumerate() {
3882 if self.is_dropped(next, k) {
3883 continue;
3884 }
3885 let s = super::arena::shift_span(Span::new(d.first_start(), d.last_end()), from, to);
3888 let inside = lo <= s.start as u64 && s.end as u64 <= hi;
3889 if d.severity() == oneyaml_core::Severity::Warning && inside {
3890 nths.push(u32::try_from(k).map_err(|_| TreeEditError::Capacity)?);
3891 }
3892 }
3893 Ok((!nths.is_empty()).then_some((next, nths)))
3894 }
3895}
3896
3897#[cfg(test)]
3900fn diagnostic_heap_bytes(d: &Diagnostic) -> usize {
3901 use core::mem::size_of;
3902 use oneyaml_core::{Label, PathSegment, Replacement, Suggestion};
3903 let label = |l: &Label| l.message.capacity();
3904 let mut n = d.message.capacity();
3905 n = n.saturating_add(label(&d.primary));
3906 n = n.saturating_add(d.secondary.capacity().saturating_mul(size_of::<Label>()));
3907 n = d.secondary.iter().map(label).fold(n, usize::saturating_add);
3908 n = n.saturating_add(d.help.as_ref().map_or(0, String::capacity));
3909 if let Some(p) = &d.path {
3910 n = n.saturating_add(p.segments().len().saturating_mul(size_of::<PathSegment>()));
3911 for s in p.segments() {
3912 if let PathSegment::Key(k) = s {
3913 n = n.saturating_add(k.capacity());
3914 }
3915 }
3916 }
3917 n = n.saturating_add(
3918 d.suggestions
3919 .capacity()
3920 .saturating_mul(size_of::<Suggestion>()),
3921 );
3922 for s in &d.suggestions {
3923 n = n.saturating_add(s.message.capacity());
3924 n = n.saturating_add(s.edits.capacity().saturating_mul(size_of::<Replacement>()));
3925 n = s
3926 .edits
3927 .iter()
3928 .map(|e| e.text.capacity())
3929 .fold(n, usize::saturating_add);
3930 }
3931 n
3932}
3933
3934fn all_stream_trivia(flat: Flat<'_>, facts: &StreamFacts, base: bool, a: u32, b: u32) -> bool {
3940 let (a, b) = (a as usize, b as usize);
3941 if b <= a {
3942 return true;
3943 }
3944 if b.saturating_sub(a) > LONG_RUN {
3945 return facts.run_start(b.saturating_sub(1)).is_some_and(|s| s <= a);
3946 }
3947 (a..b).all(|i| {
3948 let level = if base {
3949 flat.parent(i) == Some(0)
3950 } else {
3951 flat.parent(i).is_none()
3952 };
3953 level && flat.kind(i).is_some_and(|k| k.is_trivia() && k.is_token())
3954 })
3955}
3956
3957pub(super) fn token_fragment(
3960 kind: SyntaxKind,
3961 text: &str,
3962 flow: bool,
3963 settings: &Settings,
3964) -> Result<Fragment, TreeEditError> {
3965 let bad = TreeEditError::InvalidToken { kind };
3966 let scalarish = matches!(
3967 kind,
3968 SyntaxKind::PlainScalar
3969 | SyntaxKind::SingleQuotedScalar
3970 | SyntaxKind::DoubleQuotedScalar
3971 | SyntaxKind::AliasName
3972 | SyntaxKind::Anchor
3973 );
3974 let empty_plain = kind == SyntaxKind::PlainScalar && text.is_empty();
3975 let src = if empty_plain {
3976 "&x".to_owned()
3979 } else if flow && scalarish {
3980 format!("[{text}]")
3981 } else {
3982 text.to_owned()
3983 };
3984 let tree = SyntaxTree::parse_with(src, settings);
3985 if tree.has_errors() {
3986 return Err(bad);
3987 }
3988 let wrapped = flow && scalarish && !empty_plain;
3989 let mut found = None;
3990 for n in tree.root().descendants().filter(|n| n.is_token()) {
3991 let k = n.kind();
3992 if wrapped
3993 && matches!(
3994 k,
3995 SyntaxKind::FlowSequenceOpen | SyntaxKind::FlowSequenceClose
3996 )
3997 {
3998 continue;
3999 }
4000 if empty_plain && k != SyntaxKind::PlainScalar {
4001 continue;
4002 }
4003 if n.text().is_empty() && !empty_plain {
4004 continue;
4005 }
4006 if found.is_some() {
4007 return Err(bad);
4008 }
4009 found = Some(n);
4010 }
4011 let token = found.ok_or(bad)?;
4012 if token.kind() != kind || token.text() != text {
4013 return Err(bad);
4014 }
4015 let (arena, _) = tree.copy_forest(&[token.slot()])?;
4016 Ok(Fragment {
4017 arena,
4018 context: String::new(),
4019 has_tags: false,
4020 })
4021}
4022
4023#[cfg(test)]
4024mod tests {
4025 #![allow(
4026 clippy::unwrap_used,
4027 clippy::expect_used,
4028 clippy::indexing_slicing,
4029 clippy::arithmetic_side_effects
4030 )]
4031
4032 use super::*;
4033 use crate::tree::Fragment;
4034 use crate::tree::fragment::tags_outside_documents;
4035
4036 #[test]
4040 fn overlay_size_depends_on_edits_not_on_the_document() {
4041 for entries in [10usize, 10_000] {
4042 let src: String = (0..entries).map(|i| format!("k{i}: [a, b]\n")).collect();
4043 let mut tree = SyntaxTree::parse(src);
4044 let targets: Vec<NodeId> = tree
4045 .root()
4046 .descendants()
4047 .filter(|n| n.kind() == SyntaxKind::FlowSequence)
4048 .map(|n| n.id())
4049 .step_by((entries / 10).max(1))
4050 .take(10)
4051 .collect();
4052 let mut k = 0usize;
4053 for id in targets {
4054 let first = tree.get(id).unwrap().children().nth(1).unwrap().id();
4055 let f = Fragment::parse("zz").unwrap();
4056 let _ = tree.replace(first, f).unwrap();
4057 k += 1;
4058 let e = tree.edits.as_deref().unwrap();
4059 assert!(e.runs.len() <= 1 + 3 * k, "{} runs after {k}", e.runs.len());
4060 assert!(e.links.len() <= 4 * k, "{} links after {k}", e.links.len());
4061 }
4062 let slot = tree.root().first_child().unwrap().slot();
4064 let before = tree.edits.as_deref().unwrap().runs.len();
4065 let a = tree.cut_before(slot).unwrap();
4066 let b = tree.cut_before(slot).unwrap();
4067 assert_eq!(a, b);
4068 assert!(tree.edits.as_deref().unwrap().runs.len() <= before + 1);
4069 assert_eq!(tree.emit().matches("zz").count(), 10.min(entries));
4070 }
4071 }
4072
4073 fn toggle(tree: &mut SyntaxTree, n: usize) {
4075 let mut id = tree
4076 .root()
4077 .descendants()
4078 .find(|x| x.kind() == SyntaxKind::PlainScalar)
4079 .unwrap()
4080 .id();
4081 for i in 0..n {
4082 id = tree
4083 .replace_token(id, if i % 2 == 0 { "x" } else { "y" })
4084 .unwrap();
4085 }
4086 }
4087
4088 #[test]
4098 #[ignore = "slow: runs in CI"]
4099 fn toggles_retain_what_the_tree_holds_not_the_history() {
4100 let big: String = (0..300).map(|i| format!("key{i}: v\n")).collect();
4101 for src in ["a: [q, y]\nb: 1\n".to_owned(), format!("a: q\n{big}")] {
4102 let base = SyntaxTree::parse(src.as_str());
4103 let bytes = |t: &SyntaxTree| t.edits.as_deref().unwrap().heap_bytes();
4104 let mut few = base.clone();
4105 toggle(&mut few, 100);
4106 let mut many = base.clone();
4107 let first = many
4108 .root()
4109 .descendants()
4110 .find(|x| x.kind() == SyntaxKind::PlainScalar)
4111 .unwrap()
4112 .id();
4113 toggle(&mut many, 100_000);
4114 let (f, m) = (bytes(&few), bytes(&many));
4115 eprintln!("{} B: 100 toggles keep {f} B, 100k keep {m} B", src.len());
4116 assert!(
4117 m <= f + 256,
4118 "{} B: 100 toggles keep {f} B, 100k keep {m} B",
4119 src.len()
4120 );
4121 assert!(m < 2048, "{m} B retained");
4122 let e = many.edits.as_deref().unwrap();
4123 assert!(e.arenas.len() <= 1, "{} arenas", e.arenas.len());
4124 assert!(e.links.len() <= 4, "{} link overrides", e.links.len());
4125 assert!(many.get(first).is_err());
4128 let base_len = u32::try_from(many.kinds.len()).unwrap();
4129 let live: Vec<u32> = (base_len..e.next_slot())
4130 .filter(|s| many.kind_of(*s).is_some())
4131 .collect();
4132 assert_eq!(live.len(), 1, "{live:?}");
4133 assert!(many.is_live(live[0]));
4134 let fork = many.fork();
4136 assert!(bytes(&fork) <= m, "{} > {m}", bytes(&fork));
4137 assert_eq!(fork.emit(), many.emit());
4138 assert_eq!(many, SyntaxTree::parse(many.emit()));
4139 }
4140 }
4141
4142 #[test]
4147 fn reads_leave_the_overlay_untouched() {
4148 let src = "a:\n b:\n - [x, y]\n - z # c\nq: [1\n";
4149 let mut tree = SyntaxTree::parse(src);
4150 let x = tree
4151 .root()
4152 .descendants()
4153 .find(|n| n.kind() == SyntaxKind::PlainScalar && n.text() == "x")
4154 .unwrap()
4155 .id();
4156 tree.replace_token(x, "xx").unwrap();
4157 let before = format!("{:?}", tree.edits);
4158 let mut total = 0usize;
4159 for n in tree.root().descendants() {
4160 total += n.text().len() + n.span().len();
4161 total += n.ancestors().map(|a| a.text().len()).sum::<usize>();
4162 total += tree.diagnostics_within(n).count();
4163 total += usize::from(n.diagnostic().is_some());
4164 }
4165 total += tree.diagnostics().count();
4166 assert!(total > 0);
4167 assert_eq!(format!("{:?}", tree.edits), before);
4168 let seq = tree
4170 .root()
4171 .descendants()
4172 .find(|n| n.kind() == SyntaxKind::FlowSequence)
4173 .unwrap();
4174 assert!(matches!(seq.text(), Cow::Owned(_)));
4175 assert_eq!(seq.text(), "[xx, y]");
4176 let tok = seq.children().nth(1).unwrap().first_child().unwrap();
4177 assert!(matches!(tok.text(), Cow::Borrowed("xx")));
4178 }
4179
4180 #[test]
4183 fn copied_tag_flags_agree_with_a_scan() {
4184 for src in [
4185 "--- !t a\n--- [!t b]\n",
4186 "- !t [!u a, &x !v b]\n- c\n",
4187 "%TAG !e! tag:e,2000:\n--- !e!x\n- !e!y z\n",
4188 "!t\n",
4189 ] {
4190 let tree = SyntaxTree::parse(src);
4191 for n in tree.root().descendants() {
4192 let mut last = n;
4193 for _ in 0..3 {
4194 let (arena, has_tags) = tree.copy_forest(&[last.slot()]).unwrap();
4195 assert_eq!(has_tags, tags_outside_documents(&arena), "{src:?} {n:?}");
4196 match last.next_sibling() {
4197 Some(s) => last = s,
4198 None => break,
4199 }
4200 }
4201 let mut roots = vec![n.slot()];
4202 let mut at = n.next_sibling();
4203 while let Some(s) = at {
4204 roots.push(s.slot());
4205 at = s.next_sibling();
4206 }
4207 let (arena, has_tags) = tree.copy_forest(&roots).unwrap();
4208 assert_eq!(has_tags, tags_outside_documents(&arena), "{src:?} {n:?}");
4209 }
4210 }
4211 }
4212
4213 fn assert_slices_copy_as_the_walk(tree: &SyntaxTree, what: &str) -> usize {
4217 let mut sliced = 0;
4218 for n in tree.root().descendants() {
4219 let mut out = Arena::default();
4220 if tree
4221 .copy_slice(n.slot(), &mut out, &mut Vec::new(), &mut false)
4222 .unwrap()
4223 {
4224 sliced += 1;
4225 }
4226 let mut roots = vec![n.slot()];
4227 let mut at = n.next_sibling();
4228 for _ in 0..3 {
4229 let one = [*roots.last().unwrap()];
4230 for r in [&one[..], &roots[..]] {
4231 let fast = tree.copy_forest_with(r, true);
4232 let walk = tree.copy_forest_with(r, false);
4233 assert_eq!(fast, walk, "{what}: {n:?} {r:?}");
4234 }
4235 match at {
4236 Some(s) => {
4237 roots.push(s.slot());
4238 at = s.next_sibling();
4239 }
4240 None => break,
4241 }
4242 }
4243 }
4244 sliced
4245 }
4246
4247 #[test]
4253 fn slice_copies_equal_the_element_walk() {
4254 let dir = std::path::Path::new(env!("CARGO_MANIFEST_DIR"))
4255 .join("../test-suite/data/yaml-test-suite");
4256 let mut stack = vec![dir];
4257 let mut inputs = Vec::new();
4258 while let Some(d) = stack.pop() {
4259 for e in std::fs::read_dir(&d).unwrap() {
4260 let p = e.unwrap().path();
4261 if p.is_dir() {
4262 stack.push(p);
4263 } else if p.file_name().is_some_and(|n| n == "in.yaml") {
4264 inputs.push(std::fs::read_to_string(&p).unwrap());
4265 }
4266 }
4267 }
4268 assert!(inputs.len() > 300);
4269 inputs.extend(
4270 [
4271 "k: |+ # c\n x\n\n ",
4272 "- &a !t |2-\n x\n- >\n y\n- [!u a, b]\n",
4273 "%TAG !e! tag:e,2000:\n--- !e!x\n- !e!y z\n- {a: !e!w |\n q\n}\n",
4274 "k: a: b\nm: 1\nn: [x: y: z]\n",
4275 "a: [1, 2\nb: }\n- c\n",
4276 ]
4277 .iter()
4278 .map(|s| (*s).to_owned()),
4279 );
4280 inputs.push((0..200).map(|i| format!("k{i}: [a, {{b: c}}]\n")).collect());
4282 let lenient = Settings::new().lenient_inline_colons(true);
4283 let (mut parsed, mut cut) = (0, 0);
4284 for src in &inputs {
4285 for settings in [&Settings::new(), &lenient] {
4286 let mut tree = SyntaxTree::parse_with(src.as_str(), settings);
4287 parsed += assert_slices_copy_as_the_walk(&tree, src);
4288 let scalars: Vec<NodeId> = tree
4290 .root()
4291 .descendants()
4292 .filter(|n| n.kind() == SyntaxKind::Scalar)
4293 .map(|n| n.id())
4294 .collect();
4295 let mut edited = false;
4296 for (i, id) in scalars.iter().enumerate().take(6) {
4297 let ok = match i % 3 {
4298 0 => tree.remove(*id).is_ok(),
4299 1 => {
4300 let f = Fragment::parse("x").unwrap();
4301 tree.insert_after(*id, f).is_ok()
4302 }
4303 _ => {
4304 let f = Fragment::parse("yy").unwrap();
4305 tree.replace(*id, f).is_ok()
4306 }
4307 };
4308 edited |= ok;
4309 }
4310 if edited {
4311 cut += assert_slices_copy_as_the_walk(&tree, src);
4312 }
4313 }
4314 }
4315 assert!(parsed > 20_000 && cut > 5_000, "{parsed} {cut}");
4317 }
4318
4319 #[test]
4324 fn copying_a_whole_subtree_looks_up_a_constant() {
4325 let mut lookups = Vec::new();
4326 for n in [100usize, 10_000] {
4327 let mut src = String::from("a: 1\nbig:\n");
4328 for i in 0..n {
4329 src.push_str(&format!(" k{i}: [v, {{w: {i}}}] # c\n"));
4330 }
4331 let mut tree = SyntaxTree::parse(src.as_str());
4332 let one = tree
4333 .root()
4334 .descendants()
4335 .find(|x| x.kind() == SyntaxKind::Scalar && x.text() == "1")
4336 .unwrap()
4337 .id();
4338 let _ = tree.replace(one, Fragment::parse("2").unwrap()).unwrap();
4339 assert!(tree.is_edited());
4340 let big = tree
4341 .root()
4342 .descendants()
4343 .filter(|x| x.kind() == SyntaxKind::BlockMapping)
4344 .nth(1)
4345 .unwrap()
4346 .slot();
4347 cost::take();
4348 let fast = tree.copy_forest(&[big]).unwrap();
4349 let (l, _) = cost::take();
4350 lookups.push(l);
4351 let walk = tree.copy_forest_with(&[big], false).unwrap();
4352 let (w, _) = cost::take();
4353 assert_eq!(fast, walk);
4354 assert!(w as usize > n, "{w}");
4355 }
4356 assert!(lookups.iter().all(|l| *l <= 8), "{lookups:?}");
4357 }
4358
4359 #[test]
4362 fn capacity_failures_leave_the_tree_unchanged() {
4363 let src = "k: [a, b, c]\nv: {x: 1}\n";
4364 let mut tree = SyntaxTree::parse(src);
4365 let b = tree
4366 .root()
4367 .descendants()
4368 .find(|n| n.kind() == SyntaxKind::Scalar && n.text() == "b")
4369 .unwrap()
4370 .id();
4371 let c = tree
4373 .root()
4374 .descendants()
4375 .find(|n| n.kind() == SyntaxKind::Scalar && n.text() == "c")
4376 .unwrap()
4377 .id();
4378 let _ = tree.replace(c, Fragment::parse("cc").unwrap()).unwrap();
4379 let text = tree.emit();
4380 let all: Vec<(NodeId, Span)> = tree
4381 .root()
4382 .descendants()
4383 .map(|n| (n.id(), n.span()))
4384 .collect();
4385 let links = tree.edits.as_deref().unwrap().links.clone();
4386 for spare in [0, 1] {
4389 let seq = &mut tree.edits.as_deref_mut().unwrap().seq;
4390 seq.limit_items(seq.items_len() + spare);
4391 let r = tree.replace(b, Fragment::parse("[q]").unwrap());
4392 assert_eq!(r.err(), Some(TreeEditError::Capacity), "spare {spare}");
4393 assert_eq!(tree.emit(), text);
4394 for (id, span) in &all {
4395 assert_eq!(tree.get(*id).unwrap().span(), *span);
4396 }
4397 assert_eq!(tree.edits.as_deref().unwrap().links, links);
4398 assert!(tree.edits.as_deref().unwrap().arenas.len() == 1);
4399 }
4400 let seq = &mut tree.edits.as_deref_mut().unwrap().seq;
4401 seq.limit_items(seq.items_len() + 2);
4402 let _ = tree.replace(b, Fragment::parse("[q]").unwrap()).unwrap();
4403 assert_eq!(tree.emit(), "k: [a, [q], cc]\nv: {x: 1}\n");
4404 }
4405
4406 fn scanned(t: &SyntaxTree, slot: u32, forward: bool, bound: u64) -> Vec<(u64, String)> {
4409 let mut out = Vec::new();
4410 t.scan_diagnostics(slot, forward, bound, |x| {
4411 let mut d = x.diagnostic.clone();
4412 d.shift(x.from, x.to);
4413 out.push((x.start, format!("{} {:?}", d.code(), d.span())));
4414 true
4415 });
4416 out
4417 }
4418
4419 #[test]
4424 fn diagnostic_scans_agree_with_the_full_list() {
4425 let lenient = Settings::new().lenient_inline_colons(true);
4426 let src = "%YAML 1.1\n--- \na: b: c\nd: [e, f]\ng: h: i\n--- \nx: y: z\nk: [1\n...\nq: r\n";
4427 let mut tree = SyntaxTree::parse_with(src, &lenient);
4428 let check = |t: &SyntaxTree| {
4429 let all: Vec<(u64, u64, String)> = t
4430 .diagnostics_by_element()
4431 .filter_map(|(n, d)| {
4432 let n = n?;
4433 Some((
4434 n.preorder_index() as u64,
4435 n.span().start as u64,
4436 format!("{} {:?}", d.code, d.primary.span),
4437 ))
4438 })
4439 .collect();
4440 let total = t.nav_total().0;
4441 for n in t.root().descendants() {
4442 let rank = n.preorder_index() as u64;
4443 let fwd: Vec<(u64, String)> = all
4444 .iter()
4445 .filter(|(r, _, _)| *r >= rank)
4446 .map(|(_, s, d)| (*s, d.clone()))
4447 .collect();
4448 assert_eq!(scanned(t, n.slot(), true, total), fwd, "{n:?}");
4449 let back: Vec<(u64, String)> = all
4450 .iter()
4451 .rev()
4452 .filter(|(r, _, _)| *r <= rank)
4453 .map(|(_, s, d)| (*s, d.clone()))
4454 .collect();
4455 assert_eq!(scanned(t, n.slot(), false, 0), back, "{n:?}");
4456 let end = rank + n.descendants().len() as u64;
4458 let inside: Vec<(u64, String)> = all
4459 .iter()
4460 .filter(|(r, _, _)| *r >= rank && *r < end)
4461 .map(|(_, s, d)| (*s, d.clone()))
4462 .collect();
4463 assert_eq!(scanned(t, n.slot(), true, end), inside, "{n:?}");
4464 let errors = t
4465 .diagnostics_within(n)
4466 .any(|(_, d)| d.severity == oneyaml_core::Severity::Error);
4467 assert_eq!(t.has_errors_within(n.slot()), errors, "{n:?}");
4468 }
4469 };
4470 check(&tree);
4471 let find = |t: &SyntaxTree, text: &str| {
4472 t.root()
4473 .descendants()
4474 .find(|x| x.kind() == SyntaxKind::PlainScalar && x.text() == text)
4475 .unwrap()
4476 .id()
4477 };
4478 let e = find(&tree, "e");
4479 let _ = tree.replace_token(e, "ee").unwrap();
4480 check(&tree);
4481 let a = find(&tree, "a");
4482 let _ = tree.replace_token(a, "aaa").unwrap();
4483 check(&tree);
4484 let r = find(&tree, "r");
4485 let _ = tree.replace_token(r, "rr").unwrap();
4486 check(&tree);
4487 assert_eq!(tree, SyntaxTree::parse_with(tree.emit(), &lenient));
4488 }
4489
4490 #[test]
4494 fn errors_are_the_last_diagnostics_of_their_document() {
4495 let dir = std::path::Path::new(env!("CARGO_MANIFEST_DIR"))
4496 .join("../test-suite/data/yaml-test-suite");
4497 let mut stack = vec![dir];
4498 let mut inputs = Vec::new();
4499 while let Some(d) = stack.pop() {
4500 for e in std::fs::read_dir(&d).unwrap() {
4501 let p = e.unwrap().path();
4502 if p.is_dir() {
4503 stack.push(p);
4504 } else if p.file_name().is_some_and(|n| n == "in.yaml") {
4505 inputs.push(std::fs::read_to_string(&p).unwrap());
4506 }
4507 }
4508 }
4509 assert!(inputs.len() > 300);
4510 inputs.extend(DIRECTIVE_ERRORS.iter().map(|s| (*s).to_owned()));
4513 let mut docs_with_errors = 0;
4514 let mut directive_errors = 0;
4515 for settings in [Settings::new(), Settings::new().lenient_inline_colons(true)] {
4516 for src in &inputs {
4517 let tree = SyntaxTree::parse_with(src.as_str(), &settings);
4518 for doc in tree.root().children() {
4519 let marker = doc
4523 .children()
4524 .find(|c| c.kind() == SyntaxKind::DocumentStartMarker)
4525 .map_or(0, |m| m.preorder_index());
4526 let all: Vec<_> = tree
4527 .diagnostics_within(doc)
4528 .map(|(n, d)| (n.map_or(usize::MAX, |n| n.preorder_index()), d))
4529 .collect();
4530 let content: Vec<_> = all
4531 .iter()
4532 .filter(|(at, _)| *at > marker)
4533 .map(|(_, d)| d.severity)
4534 .collect();
4535 if let Some(i) = content
4536 .iter()
4537 .position(|s| *s == oneyaml_core::Severity::Error)
4538 {
4539 assert!(
4540 content[i..]
4541 .iter()
4542 .all(|s| *s == oneyaml_core::Severity::Error),
4543 "{src:?}: {content:?}"
4544 );
4545 }
4546 let early = all
4548 .iter()
4549 .any(|(at, d)| *at < marker && d.severity == oneyaml_core::Severity::Error);
4550 let recorded = doc.kind() == SyntaxKind::Document
4551 && tree
4552 .facts_at(doc.slot())
4553 .is_some_and(|(f, l, _)| f.directive_error(l));
4554 assert_eq!(early, recorded, "{src:?}");
4555 directive_errors += usize::from(early);
4556 let any = all
4557 .iter()
4558 .any(|(_, d)| d.severity == oneyaml_core::Severity::Error);
4559 docs_with_errors += usize::from(any);
4560 assert_eq!(tree.has_errors_within(doc.slot()), any, "{src:?}");
4561 }
4562 assert_eq!(tree.has_errors_within(0), tree.has_errors());
4563 }
4564 }
4565 assert!(docs_with_errors > 50, "{docs_with_errors}");
4566 assert!(
4567 directive_errors >= 2 * DIRECTIVE_ERRORS.len(),
4568 "{directive_errors}"
4569 );
4570 }
4571
4572 #[test]
4580 fn pair_edits_check_labels_in_each_splices_own_text() {
4581 let lenient = Settings::new().lenient_inline_colons(true);
4582 let inputs = [
4583 "a:\n b: 1\nc: d: e\n",
4584 "a:\n b: |\n x\nc: d: e\nf: g\n",
4585 "- k: v\n- p: q: r\n",
4586 "a:\n - x: y: z\n - w\nb: c: d\n",
4587 ];
4588 let withs = ["|\n new\n", "n: m: o\n", "9\n", ">-\n f\n\n"];
4589 let (mut accepted, mut pairs) = (0usize, 0usize);
4590 for src in inputs {
4591 let tree = SyntaxTree::parse_with(src, &lenient);
4592 assert!(tree.diagnostics().len() > 0, "{src:?}");
4593 for n in tree.root().descendants() {
4594 for with in withs {
4595 let Ok(f) = Fragment::parse_with(with, &lenient) else {
4596 continue;
4597 };
4598 for insert in [false, true] {
4599 let mut e = tree.fork();
4600 let arenas =
4601 |t: &SyntaxTree| t.edits.as_deref().map_or(0, |e| e.arenas.len());
4602 let r = if insert {
4603 e.insert_line_after(n.id(), f.clone()).map(|_| ())
4604 } else {
4605 e.replace_to_line_end(n.id(), n.id(), f.clone()).map(|_| ())
4606 };
4607 if r.is_ok() {
4608 accepted += 1;
4609 pairs += usize::from(arenas(&e) > 1);
4610 let again = SyntaxTree::parse_with(e.emit(), &lenient);
4611 assert_eq!(e, again, "{src:?} {n:?} {with:?} {insert}");
4612 }
4613 }
4614 }
4615 }
4616 }
4617 assert!(
4618 accepted > 20 && pairs > 5,
4619 "{accepted} accepted, {pairs} pairs"
4620 );
4621 }
4622
4623 const DIRECTIVE_ERRORS: &[&str] = &[
4626 "%YAML 2.0\n%FOO bar\n---\na: 1\n",
4627 "%TAG !a! x\n%TAG !a! y\n%FOO\n--- a\n",
4628 "%YAML 1.1\n%YAML 1.2\n%FOO\n---\nk: a: b\n",
4629 "a: 1\n...\n%YAML 2.0\n%FOO\n--- [b]\n",
4630 ];
4631
4632 #[test]
4636 fn directive_errors_never_cross() {
4637 for settings in [Settings::new(), Settings::new().lenient_inline_colons(true)] {
4638 for src in DIRECTIVE_ERRORS {
4639 let tree = SyntaxTree::parse_with(*src, &settings);
4640 let mut seen = 0;
4641 for (n, d) in tree.diagnostics_by_element() {
4642 let n = n.unwrap();
4643 let in_directives = n.kind() == SyntaxKind::Error
4644 && n.parent().is_some_and(|p| {
4645 p.kind() == SyntaxKind::Document
4646 && p.children().any(|c| {
4647 c.kind() == SyntaxKind::DocumentStartMarker
4648 && c.preorder_index() > n.preorder_index()
4649 })
4650 });
4651 if !in_directives {
4652 continue;
4653 }
4654 seen += 1;
4655 let at = n.span().start;
4656 assert!(n.span().is_empty(), "{src:?}");
4657 assert_eq!(d.primary.span, Span::empty(at), "{src:?}");
4658 assert!(d.secondary.iter().all(|l| l.span.start >= at));
4659 assert!(
4660 d.suggestions
4661 .iter()
4662 .all(|s| s.edits.iter().all(|e| e.span.start >= at))
4663 );
4664 }
4665 assert!(seen >= 1, "{src:?}");
4666 for n in tree.root().descendants() {
4670 if n.kind() != SyntaxKind::PlainScalar {
4671 continue;
4672 }
4673 let mut e = tree.fork();
4674 if e.replace_token(n.id(), "zz").is_ok() {
4675 assert_eq!(e, SyntaxTree::parse_with(e.emit(), &settings), "{src:?}");
4676 }
4677 }
4678 }
4679 }
4680 }
4681
4682 #[test]
4693 fn directive_codes_mark_directive_errors_only() {
4694 let root = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("..");
4695 let mut stack = vec![
4696 root.join("test-suite/data/yaml-test-suite"),
4697 root.join("fuzz/corpus"),
4698 root.join("fuzz/regressions"),
4699 ];
4700 let mut inputs: Vec<String> = DIRECTIVE_ERRORS.iter().map(|s| (*s).to_owned()).collect();
4701 inputs.extend(
4702 [
4703 "%YAML 1.2\n%YAML 1.2\n---\na: x\nb: ]\n",
4704 "%TAG !t! a\n%TAG !t! b\n---\n- [x\n",
4705 "%YAML 2.0\n---\n'x\n\u{feff}y\n",
4706 "a: [x\n---\n%YAML 1.2\n%YAML 1.2\n",
4707 "%YAML 0.2\n----\nm\n...\n%YAML 1.2\n%YAML 1.2\n---\n",
4708 ]
4709 .map(str::to_owned),
4710 );
4711 while let Some(d) = stack.pop() {
4712 for e in std::fs::read_dir(&d).unwrap() {
4713 let p = e.unwrap().path();
4714 if p.is_dir() {
4715 stack.push(p);
4716 } else if p.extension().is_none_or(|x| x != "md") {
4717 let b = std::fs::read(&p).unwrap();
4718 inputs.push(String::from_utf8_lossy(&b).into_owned());
4719 }
4720 }
4721 }
4722 assert!(inputs.len() > 3000, "{}", inputs.len());
4723 let mut seen = 0usize;
4724 let mut mixed_docs = 0usize;
4725 for settings in [Settings::new(), Settings::new().lenient_inline_colons(true)] {
4726 for src in &inputs {
4727 let tree = SyntaxTree::parse_with(src.as_str(), &settings);
4728 for doc in tree.root().children() {
4729 if doc.kind() != SyntaxKind::Document {
4730 continue;
4731 }
4732 let marker = doc
4733 .children()
4734 .find(|c| c.kind() == SyntaxKind::DocumentStartMarker)
4735 .map(|m| m.preorder_index());
4736 let all: Vec<_> = tree.diagnostics_within(doc).collect();
4737 let mut past_directive = false;
4741 let mut mixed = false;
4742 for (n, d) in all.iter().rev() {
4743 let directive = super::super::validate::is_directive_error(d.code);
4744 if d.severity != oneyaml_core::Severity::Error {
4745 continue;
4746 }
4747 if directive {
4748 seen += 1;
4749 let n = n.as_ref().unwrap();
4750 assert_eq!(n.kind(), SyntaxKind::Error, "{src:?}");
4751 assert!(n.span().is_empty(), "{src:?}");
4752 assert!(
4753 marker.is_some_and(|m| m > n.preorder_index()),
4754 "{src:?}: a directive code after the document's `---`"
4755 );
4756 past_directive = true;
4757 } else {
4758 mixed |= past_directive;
4759 }
4760 }
4761 let recorded = tree
4765 .facts_at(doc.slot())
4766 .is_some_and(|(f, l, _)| f.mixed_directive_error(l));
4767 assert_eq!(mixed, recorded, "{src:?}");
4768 mixed_docs += usize::from(mixed);
4769 }
4770 }
4771 }
4772 assert!(seen > 20, "{seen}");
4773 assert!(mixed_docs >= 2, "{mixed_docs}");
4774 }
4775
4776 #[test]
4780 fn refused_edits_leave_the_runs_as_they_were() {
4781 let src = "a: 1\nb: [x, y, z]\nc: 3\nd: {k: v}\n";
4782 let mut tree = SyntaxTree::parse(src);
4783 let colon = |t: &SyntaxTree, n: usize| {
4784 t.root()
4785 .descendants()
4786 .filter(|x| x.kind() == SyntaxKind::MappingValue)
4787 .nth(n)
4788 .unwrap()
4789 .id()
4790 };
4791 for n in 0..4 {
4793 assert_eq!(
4794 tree.remove(colon(&tree, n)),
4795 Err(TreeEditError::NotWellFormed)
4796 );
4797 assert!(!tree.is_edited());
4798 }
4799 let y = tree
4800 .root()
4801 .descendants()
4802 .find(|x| x.kind() == SyntaxKind::PlainScalar && x.text() == "y")
4803 .unwrap()
4804 .id();
4805 let _ = tree.replace_token(y, "yy").unwrap();
4806 let runs = tree.edits.as_deref().unwrap().runs.len();
4807 let mut items = None;
4810 let text = tree.emit();
4811 for round in 0..20 {
4812 for n in 0..4 {
4813 let r = tree.remove(colon(&tree, n));
4814 assert_eq!(r, Err(TreeEditError::NotWellFormed), "{round} {n}");
4815 }
4816 let comma = tree
4817 .root()
4818 .descendants()
4819 .find(|x| x.kind() == SyntaxKind::FlowEntry)
4820 .unwrap()
4821 .id();
4822 assert_eq!(tree.remove(comma), Err(TreeEditError::NotWellFormed));
4823 let e = tree.edits.as_deref().unwrap();
4824 assert_eq!(e.runs.len(), runs, "runs grew after refusals");
4825 assert_eq!(*items.get_or_insert(e.seq.items_len()), e.seq.items_len());
4826 }
4827 assert_eq!(tree.emit(), text);
4828 assert_eq!(tree, SyntaxTree::parse(tree.emit()));
4829 }
4830
4831 #[test]
4835 fn text_ranges_are_covered_or_an_error() {
4836 let mut tree = SyntaxTree::parse("a:\n b: [1, 2]\n c: |\n x\n# end\n");
4837 let one = tree
4838 .root()
4839 .descendants()
4840 .find(|x| x.kind() == SyntaxKind::PlainScalar && x.text() == "1")
4841 .unwrap()
4842 .id();
4843 let _ = tree.replace_token(one, "11").unwrap();
4844 let two = tree
4845 .root()
4846 .descendants()
4847 .find(|x| x.kind() == SyntaxKind::Scalar && x.text() == "2")
4848 .unwrap()
4849 .id();
4850 let _ = tree
4851 .replace(two, Fragment::parse("{z: 2}").unwrap())
4852 .unwrap();
4853 for n in tree.root().descendants() {
4854 let (a, b) = tree.nav_bytes(n.slot()).unwrap();
4855 let runs = tree.try_text_range(a, b).unwrap();
4856 assert_eq!(runs, tree.text_from_tokens(n.slot()), "{n:?}");
4857 assert_eq!(runs, n.text());
4858 }
4859 let total = tree.nav_total().1;
4860 assert_eq!(
4861 tree.try_text_range(total, total + 5),
4862 Err(TreeEditError::Internal)
4863 );
4864 assert_eq!(tree.try_text_range(0, total).unwrap(), tree.emit());
4865 assert_eq!(tree.byte_at(0), Some(b'a'));
4866 assert_eq!(tree.byte_at(total), None);
4867 }
4868
4869 #[test]
4873 fn columns_are_bytes_as_the_parser_counts_them() {
4874 let src = "\u{e9}\u{1f600}: [a, b]\n";
4875 let mut tree = SyntaxTree::parse(src);
4876 let seq_at = src.find('[').unwrap() as u64;
4877 assert_eq!(tree.column_at(seq_at), Some(8));
4878 let a = tree
4879 .root()
4880 .descendants()
4881 .find(|x| x.kind() == SyntaxKind::PlainScalar && x.text() == "a")
4882 .unwrap()
4883 .id();
4884 let _ = tree.replace_token(a, "\u{2603}").unwrap();
4885 let b_at = tree.emit().find('b').unwrap() as u64;
4886 assert_eq!(tree.column_at(seq_at), Some(8));
4887 assert_eq!(tree.column_at(b_at), Some(14));
4888 assert_eq!(tree.column_at(0), Some(0));
4889 }
4890
4891 #[test]
4894 fn columns_skip_a_byte_order_mark() {
4895 let src = "\u{feff}a: [b]\n--- \u{feff}\n";
4896 let mut tree = SyntaxTree::parse(src);
4897 assert_eq!(tree.column_at(3), Some(0));
4898 assert_eq!(tree.column_at(src.find('[').unwrap() as u64), Some(3));
4899 let b = tree
4900 .root()
4901 .descendants()
4902 .find(|x| x.kind() == SyntaxKind::PlainScalar && x.text() == "b")
4903 .unwrap()
4904 .id();
4905 let _ = tree.replace_token(b, "cc").unwrap();
4906 assert_eq!(tree.column_at(src.find('[').unwrap() as u64), Some(3));
4907 assert_eq!(tree.column_at(0), Some(0));
4908 }
4909
4910 #[test]
4913 fn last_chains_agree_with_last_children() {
4914 let mut tree = SyntaxTree::parse("a:\n b:\n - [x, {y: z}]\n - q\nc: []\n");
4915 let check = |t: &SyntaxTree| {
4916 for n in t.root().descendants() {
4917 let mut want = vec![n.slot()];
4918 let mut at = n.slot();
4919 while let Some(l) = t.nav_last(at) {
4920 want.push(l);
4921 at = l;
4922 }
4923 assert_eq!(t.last_chain(n.slot()), want, "{n:?}");
4924 assert_eq!(t.nav_last_leaf(n.slot()), want.last().copied());
4925 }
4926 };
4927 check(&tree);
4928 let q = tree
4929 .root()
4930 .descendants()
4931 .find(|x| x.kind() == SyntaxKind::Scalar && x.text() == "q")
4932 .unwrap()
4933 .id();
4934 let _ = tree
4935 .replace(q, Fragment::parse("[r, [s]]").unwrap())
4936 .unwrap();
4937 check(&tree);
4938 }
4939
4940 #[test]
4942 fn is_empty_agrees_with_len() {
4943 let mut tree = SyntaxTree::parse("[a]");
4944 assert!(!tree.is_empty());
4945 assert_eq!(tree.is_empty(), matches!(tree.len(), 0));
4946 let a = tree
4947 .root()
4948 .descendants()
4949 .find(|x| x.kind() == SyntaxKind::PlainScalar)
4950 .unwrap()
4951 .id();
4952 let _ = tree.replace_token(a, "b").unwrap();
4953 assert!(!tree.is_empty());
4954 assert_eq!(tree.is_empty(), matches!(tree.len(), 0));
4955 }
4956
4957 #[test]
4961 fn unwrap_root_keeps_warnings() {
4962 let warning = Diagnostic::warning(
4963 oneyaml_core::code::YAML_VERSION_1_1,
4964 "w",
4965 oneyaml_core::Label::new(Span::new(0, 1), ""),
4966 );
4967 let mut f = Fragment::parse("[a, b]").unwrap();
4968 f.arena.diagnostics.push((0, Stored::full(warning.clone())));
4969 let g = f.unwrap_root(0).unwrap();
4970 assert_eq!(g.arena.diagnostics.len(), 1);
4971 let at = g.arena.diagnostics[0].0 as usize;
4972 assert_eq!(at, 0);
4973 assert_eq!(g.arena.flat().kind(at), Some(SyntaxKind::FlowSequenceOpen));
4974 let mut f = Fragment::parse("x").unwrap();
4976 let arena = &mut f.arena;
4977 arena.kinds.insert(0, SyntaxKind::Alias);
4978 arena.parents.insert(0, NONE);
4979 arena.words.insert(0, 1);
4980 for p in arena.parents.iter_mut().skip(1) {
4981 if *p != NONE {
4982 *p += 1;
4983 }
4984 }
4985 for (i, w) in arena.words.iter_mut().enumerate().skip(1) {
4986 if !arena.kinds[i].is_token() {
4987 *w += 1;
4988 }
4989 }
4990 arena.diagnostics.push((0, Stored::full(warning)));
4991 assert_eq!(
4992 f.unwrap_root(0),
4993 Err(TreeEditError::ReadOnly {
4994 kind: SyntaxKind::Alias
4995 })
4996 );
4997 }
4998
4999 #[test]
5003 fn tag_context_reads_only_directives() {
5004 let src = format!("{}a: !t x\n", "# c\n".repeat(1000));
5005 let tree = SyntaxTree::parse(src);
5006 let doc = tree
5007 .root()
5008 .children()
5009 .find(|x| x.kind() == SyntaxKind::Document)
5010 .unwrap();
5011 assert_eq!(doc.first_child().unwrap().kind(), SyntaxKind::BlockMapping);
5012 assert_eq!(tree.tag_context(doc.slot()), "");
5013 let tree = SyntaxTree::parse("# c\n%TAG !e! tag:e,2000:\n# d\n--- !e!x a\n");
5014 let doc = tree
5015 .root()
5016 .children()
5017 .find(|x| x.kind() == SyntaxKind::Document)
5018 .unwrap();
5019 assert_eq!(doc.first_child().unwrap().kind(), SyntaxKind::TagDirective);
5020 assert_eq!(tree.tag_context(doc.slot()), "%TAG !e! tag:e,2000:\n");
5021 }
5022
5023 #[test]
5026 fn refused_edits_are_undone() {
5027 let src = "a: 1\nb: [x, y]\nc: 3\n";
5028 let mut tree = SyntaxTree::parse(src);
5029 let find = |t: &SyntaxTree, k: SyntaxKind, n: usize| {
5030 t.root()
5031 .descendants()
5032 .filter(|x| x.kind() == k)
5033 .nth(n)
5034 .unwrap()
5035 .id()
5036 };
5037 let colon = find(&tree, SyntaxKind::MappingValue, 0);
5039 assert_eq!(tree.remove(colon), Err(TreeEditError::NotWellFormed));
5040 assert!(!tree.is_edited());
5041 let y = find(&tree, SyntaxKind::Scalar, 4);
5042 let _ = tree.replace(y, Fragment::parse("yy").unwrap()).unwrap();
5043 let text = tree.emit();
5044 let all: Vec<(NodeId, Span)> = tree
5045 .root()
5046 .descendants()
5047 .map(|n| (n.id(), n.span()))
5048 .collect();
5049 let links = tree.edits.as_deref().unwrap().links.clone();
5050 let arenas = tree.edits.as_deref().unwrap().arenas.len();
5051 let comma = find(&tree, SyntaxKind::FlowEntry, 0);
5053 assert_eq!(tree.remove(comma), Err(TreeEditError::NotWellFormed));
5054 let map = find(&tree, SyntaxKind::BlockMapping, 0);
5055 assert_eq!(
5056 tree.append_child(map, Fragment::parse("x").unwrap()),
5057 Err(TreeEditError::NotWellFormed)
5058 );
5059 assert_eq!(tree.emit(), text);
5060 for (id, span) in &all {
5061 assert_eq!(tree.get(*id).unwrap().span(), *span);
5062 }
5063 let e = tree.edits.as_deref().unwrap();
5064 assert_eq!(e.links, links);
5065 assert_eq!(e.arenas.len(), arenas);
5066 let three = find(&tree, SyntaxKind::Scalar, 6);
5068 let _ = tree.replace(three, Fragment::parse("33").unwrap()).unwrap();
5069 assert_eq!(tree.emit(), "a: 1\nb: [x, yy]\nc: 33\n");
5070 assert_eq!(tree, SyntaxTree::parse(tree.emit()));
5071 }
5072
5073 fn assert_diag_sums(tree: &SyntaxTree) {
5076 let e = tree.edits.as_deref().unwrap();
5077 let mut at = e.seq.first();
5078 let mut total = 0u64;
5079 while let Some(item) = at {
5080 let run = e.seq.run(item).unwrap();
5081 let (flat, _, _) = tree.arena_flat(run.arena).unwrap();
5082 assert_eq!(run.diags, flat.diagnostics_in(run.a, run.b), "{run:?}");
5083 total += run.diags;
5084 at = e.seq.next(item);
5085 }
5086 let listed = tree
5087 .diagnostics_by_element()
5088 .filter(|(n, _)| n.is_some())
5089 .count();
5090 assert_eq!(total, (listed + e.dropped.len()) as u64);
5093 }
5094
5095 #[test]
5098 fn dropped_warnings_are_undone_and_released() {
5099 let settings = Settings::new().lenient_inline_colons(true);
5100 let mut tree = SyntaxTree::parse_with("k: a: b\nm: 1\n", &settings);
5101 let find = |t: &SyntaxTree, k: SyntaxKind, text: &str| {
5102 t.root()
5103 .descendants()
5104 .find(|x| x.kind() == k && x.text() == text)
5105 .unwrap()
5106 .id()
5107 };
5108 let v = find(&tree, SyntaxKind::PlainScalar, "a: b");
5109 let _ = tree.replace_token(v, "x").unwrap();
5110 let e = tree.edits.as_deref().unwrap();
5111 assert_eq!(e.dropped.len(), 1);
5112 assert_diag_sums(&tree);
5113 let colon = tree
5115 .root()
5116 .descendants()
5117 .find(|x| x.kind() == SyntaxKind::MappingValue)
5118 .unwrap()
5119 .id();
5120 assert_eq!(tree.remove(colon), Err(TreeEditError::NotWellFormed));
5121 assert_eq!(tree.edits.as_deref().unwrap().dropped.len(), 1);
5122 let brk = tree
5124 .root()
5125 .descendants()
5126 .find(|x| x.kind() == SyntaxKind::LineBreak)
5127 .unwrap()
5128 .id();
5129 let _ = tree.replace_token(brk, "\n").unwrap();
5130 assert!(tree.edits.as_deref().unwrap().dropped.is_empty());
5131 assert_diag_sums(&tree);
5132 assert_eq!(tree.diagnostics().count(), 0);
5133 assert_eq!(tree, SyntaxTree::parse_with(tree.emit(), &settings));
5134 let mut tree = SyntaxTree::parse_with("k: a: b\nm: 1\n", &settings);
5137 let node = tree
5138 .root()
5139 .descendants()
5140 .find(|x| x.kind() == SyntaxKind::Scalar && x.text() == "a: b")
5141 .unwrap()
5142 .id();
5143 let map = Fragment::parse("p: q").unwrap();
5144 assert_eq!(tree.replace(node, map), Err(TreeEditError::NotWellFormed));
5145 assert!(tree.edits.as_deref().is_none_or(|e| e.dropped.is_empty()));
5146 assert_eq!(tree.diagnostics().count(), 1);
5147 }
5148
5149 fn assert_trivia_flags(tree: &SyntaxTree) {
5153 let Some(e) = tree.edits.as_deref() else {
5154 return;
5155 };
5156 let mut at = e.seq.first();
5157 while let Some(item) = at {
5158 let run = e.seq.run(item).unwrap();
5159 let all = (run.a..run.b).all(|l| {
5160 let slot = run.arena + l;
5161 tree.nav_parent(slot) == Some(0)
5162 && tree.kind_of(slot).is_some_and(|k| k.is_trivia())
5163 });
5164 assert_eq!(run.trivia, all, "{run:?}");
5165 at = e.seq.next(item);
5166 }
5167 }
5168
5169 #[test]
5175 fn inserted_arenas_record_their_stream_facts() {
5176 let mut tree = SyntaxTree::parse("a: 1\n--- b\n");
5177 let doc_b = tree
5178 .root()
5179 .children()
5180 .filter(|x| x.kind() == SyntaxKind::Document)
5181 .nth(1);
5182 let doc_b = doc_b.unwrap().id();
5183 let comments = Fragment::parse(&"# c\n".repeat(40)).unwrap();
5184 assert_eq!(comments.len(), 80);
5185 let ins = tree.insert_before(doc_b, comments).unwrap();
5186 let first = tree.get(ins.first).unwrap().slot();
5187 let last = tree.get(ins.last).unwrap().slot();
5188 let (facts, local, _) = tree.facts_at(last).unwrap();
5189 assert_eq!(facts.run_start(local), Some(0));
5190 assert_eq!(facts.run_end(0), Some(79));
5191 assert_eq!(tree.trivia_run_start(last), first);
5192 assert_eq!(tree.trivia_run_end(first), last);
5193 assert_trivia_flags(&tree);
5194 let mid = tree
5196 .root()
5197 .children()
5198 .filter(|x| x.kind() == SyntaxKind::Comment)
5199 .nth(20)
5200 .unwrap();
5201 let (mid_slot, mid_id) = (mid.slot(), mid.id());
5202 let new = tree.replace_token(mid_id, "# d").unwrap();
5203 let new_slot = tree.get(new).unwrap().slot();
5204 assert_eq!(tree.trivia_run_start(last), mid_slot + 1);
5205 assert_eq!(tree.trivia_run_end(first), mid_slot - 1);
5206 assert_eq!(tree.trivia_run_start(new_slot), new_slot);
5207 assert_trivia_flags(&tree);
5208 let b = tree
5210 .root()
5211 .descendants()
5212 .find(|x| x.kind() == SyntaxKind::PlainScalar && x.text() == "b")
5213 .unwrap()
5214 .id();
5215 let _ = tree.replace_token(b, "bb").unwrap();
5216 assert_trivia_flags(&tree);
5217 assert_eq!(tree, SyntaxTree::parse(tree.emit()));
5218 let donor = SyntaxTree::parse("%YAML 2.0\n--- x\n");
5220 let bad = donor.root().first_child().unwrap();
5221 assert_eq!(bad.kind(), SyntaxKind::Document);
5222 let f = donor.extract(bad.id(), bad.id()).unwrap();
5223 let mut tree = SyntaxTree::parse("--- a\n...\n");
5226 let root = tree.root().id();
5227 let ins = tree.append_child(root, f).unwrap();
5228 let slot = tree.get(ins.first).unwrap().slot();
5229 let (facts, local, _) = tree.facts_at(slot).unwrap();
5230 assert!(facts.directive_error(local));
5231 assert!(tree.has_errors_within(slot));
5232 assert!(tree.has_errors());
5233 let first_doc = tree.root().first_child().unwrap().slot();
5234 assert!(!tree.has_errors_within(first_doc));
5235 assert_trivia_flags(&tree);
5236 assert_eq!(tree, SyntaxTree::parse(tree.emit()));
5237 }
5238
5239 #[test]
5244 fn trivia_flags_follow_every_edit() {
5245 let mut tree = SyntaxTree::parse(format!("a: 1\n{}--- b\n# t\n", "# c\n".repeat(70)));
5246 let mut rng = 0x5eed_u64;
5247 let mut next = |n: usize| {
5248 rng = rng.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
5249 (rng >> 33) as usize % n.max(1)
5250 };
5251 let pieces = ["# d\n", "\n", "--- z\n", "# e\n# f\n"];
5252 let mut accepted = 0usize;
5253 for round in 0..300 {
5254 let kids: Vec<NodeId> = tree.root().children().map(|x| x.id()).collect();
5255 let at = kids[next(kids.len())];
5256 match next(3) {
5257 0 => {
5258 let f = Fragment::parse(pieces[next(pieces.len())]).unwrap();
5259 accepted += usize::from(tree.insert_before(at, f).is_ok());
5260 }
5261 1 => accepted += usize::from(tree.remove(at).is_ok()),
5262 _ => {
5263 let n = tree.get(at).unwrap();
5264 if n.kind() == SyntaxKind::Comment {
5265 let r = tree.replace_token(at, &format!("# r{round}"));
5266 accepted += usize::from(r.is_ok());
5267 }
5268 }
5269 }
5270 assert_trivia_flags(&tree);
5271 let kids: Vec<u32> = tree.root().children().map(|x| x.slot()).collect();
5273 for (i, &k) in kids.iter().enumerate() {
5274 let is_trivia = |s: &&u32| !tree.kind_of(**s).unwrap().is_trivia();
5275 let before = kids[..i].iter().rev().find(is_trivia).copied();
5276 let after = kids[i..].iter().find(is_trivia).copied();
5277 assert_eq!(tree.content_before(k).unwrap(), before, "round {round}");
5278 assert_eq!(tree.content_after(k).unwrap(), after, "round {round}");
5279 }
5280 assert_eq!(tree, SyntaxTree::parse(tree.emit()), "round {round}");
5281 }
5282 assert!(accepted > 150, "{accepted}");
5283 let runs = tree.edits.as_deref().unwrap().runs.len();
5284 assert!(runs > 20, "{runs} runs");
5285 }
5286
5287 #[test]
5291 fn insert_remove_pairs_leave_no_runs_behind() {
5292 let src: String = (0..200).map(|i| format!("- e{i}\n")).collect();
5293 let mut tree = SyntaxTree::parse(src.as_str());
5294 let t = SyntaxTree::parse("- x\n- z");
5295 let seq = t.root().first_child().unwrap().first_child().unwrap();
5296 let kids: Vec<_> = seq.children().collect();
5297 let entry = t.extract(kids[3].id(), kids[6].id()).unwrap();
5298 let values: Vec<NodeId> = tree
5299 .root()
5300 .descendants()
5301 .filter(|n| n.kind() == SyntaxKind::Scalar)
5302 .map(|n| n.id())
5303 .collect();
5304 let mut stale = Vec::new();
5305 for (k, id) in values.iter().enumerate().step_by(7) {
5306 let ins = tree.insert_after(*id, entry.clone()).unwrap();
5307 let _ = tree.remove_range(ins.first, ins.last).unwrap();
5308 stale.push(ins.first);
5309 let e = tree.edits.as_deref().unwrap();
5310 assert_eq!(e.runs.len(), 1, "runs left behind after pair {k}");
5311 assert_eq!(e.seq.total().0 as usize, tree.len());
5312 }
5313 assert_eq!(tree.emit().as_bytes(), src.as_bytes());
5314 for id in &values {
5315 assert!(tree.get(*id).is_ok());
5316 }
5317 for id in stale {
5318 assert!(tree.get(id).is_err());
5319 }
5320 let _ = tree
5322 .replace(values[3], Fragment::parse("zz").unwrap())
5323 .unwrap();
5324 assert!(tree.edits.as_deref().unwrap().runs.len() <= 3);
5325 assert_eq!(tree, SyntaxTree::parse(tree.emit()));
5326 }
5327
5328 #[test]
5332 fn copies_made_inside_a_group_settle_its_edits() {
5333 let src: String = (0..20).map(|i| format!("k{i}: v\n")).collect();
5334 let mut tree = SyntaxTree::parse(src.as_str());
5335 let mut ended = tree.clone();
5336 let edit = |t: &mut SyntaxTree| {
5337 toggle(t, 40);
5338 let s = t
5339 .root()
5340 .descendants()
5341 .filter(|x| x.kind() == SyntaxKind::Scalar)
5342 .nth(5)
5343 .unwrap()
5344 .id();
5345 let ins = t.insert_after(s, Fragment::parse("# c").unwrap());
5346 if let Ok(ins) = ins {
5347 let _ = t.remove(ins.first).unwrap();
5348 }
5349 };
5350 let mark = tree.begin_group();
5351 edit(&mut tree);
5352 let m = ended.begin_group();
5353 edit(&mut ended);
5354 ended.end_group(m).unwrap();
5355 let shape = |t: &SyntaxTree| {
5356 let e = t.edits.as_deref().unwrap();
5357 (e.runs.len(), e.arenas.len(), e.links.len(), t.emit())
5358 };
5359 let held = shape(&tree);
5360 assert!(held.1 > shape(&ended).1, "{held:?}");
5361 for copy in [tree.clone(), tree.fork()] {
5362 assert!(!copy.in_group());
5363 assert_eq!(shape(©), shape(&ended));
5364 assert_eq!(copy, SyntaxTree::parse(copy.emit()));
5365 }
5366 assert_eq!(shape(&tree), held);
5367 tree.rollback_group(mark).unwrap();
5368 assert_eq!(tree.emit(), src);
5369 }
5370
5371 #[test]
5376 fn run_diagnostic_counts_follow_every_edit() {
5377 let settings = Settings::new().lenient_inline_colons(true);
5378 let src: String = (0..40)
5379 .map(|i| format!("k{i}: a: b\nv{i}: [x, y]\n"))
5380 .collect();
5381 let mut tree = SyntaxTree::parse_with(src.as_str(), &settings);
5382 assert!(tree.diagnostics().len() >= 40);
5383 let donor = SyntaxTree::parse_with("a: 1\nq: w: e\nr: 1\n", &settings);
5386 let map = donor.root().first_child().unwrap().first_child().unwrap();
5387 let kids: Vec<_> = map.children().collect();
5388 let with_warning = donor
5389 .extract(kids[4].id(), kids.last().unwrap().id())
5390 .unwrap();
5391 assert_eq!(with_warning.text(), "\nq: w: e\nr: 1");
5392 let mut inserted = Vec::new();
5393 for round in 0..30usize {
5394 let seqs: Vec<NodeId> = tree
5395 .root()
5396 .descendants()
5397 .filter(|n| n.kind() == SyntaxKind::FlowSequence)
5398 .map(|n| n.id())
5399 .collect();
5400 let s = seqs[round * 7 % seqs.len()];
5401 let x = tree.get(s).unwrap().children().nth(1).unwrap();
5402 let tok = x.first_child().unwrap().id();
5403 let _ = tree.replace_token(tok, &format!("x{round}")).unwrap();
5404 assert_diag_sums(&tree);
5405 inserted.push(tree.insert_after(s, with_warning.clone()).unwrap());
5407 assert_diag_sums(&tree);
5408 if round % 3 == 2 {
5409 let ins = inserted.remove(round % inserted.len());
5410 let _ = tree.remove_range(ins.first, ins.last).unwrap();
5411 assert_diag_sums(&tree);
5412 }
5413 let colon = tree
5415 .root()
5416 .descendants()
5417 .find(|n| n.kind() == SyntaxKind::MappingValue)
5418 .unwrap()
5419 .id();
5420 assert_eq!(tree.remove(colon), Err(TreeEditError::NotWellFormed));
5421 assert_diag_sums(&tree);
5422 assert_eq!(tree, SyntaxTree::parse_with(tree.emit(), &settings));
5423 }
5424 assert_eq!(tree.emit().matches("q: w: e").count(), 20);
5425 }
5426}