use super::SyntaxKind as K;
use super::arena::Flat;
use super::facts::{LONG_RUN, StreamFacts};
use super::{NONE, Node, SyntaxTree};
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
struct Note {
slot: u32,
col: u32,
}
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
struct Tables {
segs: Vec<(u32, u32)>,
notes: Vec<Note>,
solids: Vec<u32>,
mins: Vec<u32>,
}
#[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
pub(super) struct RunFacts(Option<Box<Tables>>);
fn chars(text: &str) -> u32 {
u32::try_from(text.chars().count()).unwrap_or(u32::MAX)
}
pub(super) fn visible(flat: Flat<'_>, i: usize) -> bool {
flat.kind(i)
.is_some_and(|k| k.is_token() && !k.is_trivia() && !flat.token_span(i).is_empty())
}
fn ends_line(k: K, text: &str) -> bool {
k == K::LineBreak || (!text.is_empty() && text.ends_with(['\n', '\r']))
}
fn skipped(k: K, text: &str) -> bool {
matches!(k, K::Whitespace | K::ByteOrderMark | K::Comment)
|| (k != K::LineBreak && text.is_empty())
}
fn back(flat: Flat<'_>, c: usize, floor: usize) -> (u32, u32, bool) {
let mut acc = 0u32;
let mut j = c;
while j > floor {
j = j.saturating_sub(1);
let Some(k) = flat.kind(j) else { break };
if !k.is_token() || k == K::ByteOrderMark {
continue;
}
let text = flat.token_text(j);
let at = u32::try_from(j).unwrap_or(NONE);
if let Some(p) = text.rfind(['\n', '\r']) {
let tail = chars(text.get(p.saturating_add(1)..).unwrap_or(""));
return (acc.saturating_add(tail), at, ends_line(k, text));
}
if visible(flat, j) {
return (acc, at, false);
}
acc = acc.saturating_add(chars(text));
}
(acc, NONE, false)
}
impl RunFacts {
pub(super) fn of(flat: Flat<'_>) -> Self {
let n = flat.len();
let mut segs = Vec::new();
let mut start = 0usize;
let mut clear = 0usize;
while let Some(probe) = start.checked_add(LONG_RUN).filter(|p| *p < n) {
let mut j = probe.saturating_add(1);
let mut found = None;
while j > clear.max(start) {
j = j.saturating_sub(1);
if visible(flat, j) {
found = Some(j);
break;
}
}
if let Some(j) = found {
start = j.saturating_add(1);
clear = probe.saturating_add(1).max(start);
continue;
}
let mut e = probe.saturating_add(1);
while e < n && !visible(flat, e) {
e = e.saturating_add(1);
}
if let (Ok(a), Ok(b)) = (u32::try_from(start), u32::try_from(e)) {
segs.push((a, b));
}
start = e.saturating_add(1);
clear = start;
}
if segs.is_empty() {
return Self(None);
}
let (mut nc, mut sc) = (0usize, 0usize);
for &(a, b) in &segs {
for c in a as usize..b as usize {
match flat.kind(c) {
Some(K::Comment) => nc = nc.saturating_add(1),
Some(k) if !k.is_trivia() => sc = sc.saturating_add(1),
_ => {}
}
}
}
let mut notes = Vec::with_capacity(nc);
let mut solids = Vec::with_capacity(sc);
for &(a, b) in &segs {
let mut state: Option<u32> = None;
for c in a as usize..b as usize {
let Some(k) = flat.kind(c) else { continue };
match k {
K::Comment => {
let own = |col: u32| col.min(u32::MAX.saturating_sub(1));
let col = match state {
Some(col) => own(col),
None => match back(flat, c, 0) {
(col, NONE, _) | (col, _, true) => own(col),
(_, _, false) => u32::MAX,
},
};
notes.push(Note {
slot: u32::try_from(c).unwrap_or(NONE),
col,
});
}
K::LineBreak => state = Some(0),
K::Whitespace => {
if let Some(col) = state.as_mut() {
*col = col.saturating_add(chars(flat.token_text(c)));
}
}
_ if !k.is_trivia() => solids.push(u32::try_from(c).unwrap_or(NONE)),
_ => {}
}
}
}
let mut t = Tables {
segs,
notes,
solids,
mins: Vec::new(),
};
if !t.notes.is_empty() {
let cap = t.notes.len().next_power_of_two();
t.mins = vec![u32::MAX; cap];
let mut x = cap;
while x > 1 {
x = x.saturating_sub(1);
let l = t.val(x.saturating_mul(2));
let r = t.val(x.saturating_mul(2).saturating_add(1));
if let Some(m) = t.mins.get_mut(x) {
*m = l.min(r);
}
}
}
Self(Some(Box::new(t)))
}
#[cfg(test)]
pub(super) fn heap_bytes(&self) -> usize {
self.0.as_deref().map_or(0, |t| {
size_of::<Tables>()
.saturating_add(t.segs.capacity().saturating_mul(size_of::<(u32, u32)>()))
.saturating_add(t.notes.capacity().saturating_mul(size_of::<Note>()))
.saturating_add(t.mins.capacity().saturating_mul(4))
.saturating_add(t.solids.capacity().saturating_mul(4))
})
}
#[cfg(test)]
fn notes_len(&self) -> usize {
self.0.as_deref().map_or(0, |t| t.notes.len())
}
fn last_solid_in(&self, a: usize, b: usize) -> Option<usize> {
let solids = &self.0.as_deref()?.solids;
let hi = solids.partition_point(|s| (*s as usize) < b);
let s = *solids.get(hi.checked_sub(1)?)? as usize;
(s >= a).then_some(s)
}
fn first_solid_in(&self, a: usize, b: usize) -> Option<usize> {
let solids = &self.0.as_deref()?.solids;
let lo = solids.partition_point(|s| (*s as usize) < a);
let s = *solids.get(lo)? as usize;
(s < b).then_some(s)
}
fn segment_at(&self, i: usize) -> Option<(usize, usize)> {
let segs = &self.0.as_deref()?.segs;
let k = segs.partition_point(|(a, _)| (*a as usize) <= i);
let (a, b) = *segs.get(k.checked_sub(1)?)?;
(i < b as usize).then_some((a as usize, b as usize))
}
fn notes_from(&self, i: usize) -> usize {
self.0
.as_deref()
.map_or(0, |t| t.notes.partition_point(|n| (n.slot as usize) < i))
}
fn note(&self, k: usize) -> Option<Note> {
self.0.as_deref()?.notes.get(k).copied()
}
fn first_below(&self, lo: usize, hi: usize, v: u32) -> Option<usize> {
let t = self.0.as_deref()?;
let cap = t.cap();
let (mut l, mut r) = (
lo.saturating_add(cap),
hi.min(t.notes.len()).saturating_add(cap),
);
let mut right_hit = None;
while l < r {
if l % 2 == 1 {
if t.val(l) < v {
return t.descend(l, v);
}
l = l.saturating_add(1);
}
if r % 2 == 1 {
r = r.saturating_sub(1);
if t.val(r) < v {
right_hit = Some(r);
}
}
l /= 2;
r /= 2;
}
t.descend(right_hit?, v)
}
fn min_in(&self, lo: usize, hi: usize) -> u32 {
let Some(t) = self.0.as_deref() else {
return u32::MAX;
};
let cap = t.cap();
let (mut l, mut r) = (
lo.saturating_add(cap),
hi.min(t.notes.len()).saturating_add(cap),
);
let mut m = u32::MAX;
while l < r {
if l % 2 == 1 {
m = m.min(t.val(l));
l = l.saturating_add(1);
}
if r % 2 == 1 {
r = r.saturating_sub(1);
m = m.min(t.val(r));
}
l /= 2;
r /= 2;
}
m
}
}
impl Tables {
fn cap(&self) -> usize {
self.mins.len()
}
fn val(&self, x: usize) -> u32 {
let cap = self.cap();
if x >= cap {
self.notes
.get(x.saturating_sub(cap))
.map_or(u32::MAX, |n| n.col)
} else {
self.mins.get(x).copied().unwrap_or(u32::MAX)
}
}
fn descend(&self, mut x: usize, v: u32) -> Option<usize> {
let cap = self.cap();
while x < cap {
let l = x.saturating_mul(2);
x = if self.val(l) < v {
l
} else {
l.saturating_add(1)
};
}
x.checked_sub(cap)
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) struct LineState {
col: u32,
clean: bool,
}
impl LineState {
pub(super) const START: Self = Self {
col: 0,
clean: true,
};
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub(super) struct Marks {
pub(super) vis: bool,
pub(super) firm: bool,
pub(super) docs: bool,
brk: bool,
clean: Option<bool>,
w: u32,
exact: u32,
head: u32,
}
impl Marks {
pub(super) const NONE: Self = Self {
vis: false,
firm: false,
docs: false,
brk: false,
clean: None,
w: 0,
exact: u32::MAX,
head: u32::MAX,
};
pub(super) const CONTENT: Self = Self {
vis: true,
firm: true,
docs: false,
brk: false,
clean: None,
w: 0,
exact: 0,
head: 0,
};
#[cfg(test)]
pub(super) const fn for_test(
vis: bool,
firm: bool,
docs: bool,
(brk, clean, w): (bool, Option<bool>, u32),
(exact, head): (u32, u32),
) -> Self {
Self {
vis,
firm,
docs,
brk,
clean,
w,
exact,
head,
}
}
pub(super) fn then(self, r: Self) -> Self {
let carried = self.w.saturating_add(r.head);
let (to_exact, to_head) = match (self.clean, self.brk) {
(Some(false), _) => (u32::MAX, u32::MAX),
(Some(true), _) | (None, true) => (carried, u32::MAX),
(None, false) => (u32::MAX, carried),
};
Self {
vis: self.vis || r.vis,
firm: self.firm || r.firm,
docs: self.docs || r.docs,
brk: self.brk || r.brk,
clean: r.clean.or(self.clean),
w: if r.brk {
r.w
} else {
self.w.saturating_add(r.w)
},
exact: self.exact.min(r.exact).min(to_exact),
head: self.head.min(to_head),
}
}
pub(super) fn after(&self, s: LineState) -> LineState {
LineState {
col: if self.brk {
self.w
} else {
s.col.saturating_add(self.w)
},
clean: self.clean.unwrap_or(s.clean),
}
}
pub(super) fn hits(&self, s: LineState, v: u32) -> bool {
self.vis || self.exact < v || (s.clean && s.col.saturating_add(self.head) < v)
}
}
fn line_moves(flat: Flat<'_>, a: usize, b: usize) -> (bool, u32, Option<bool>) {
let mut acc = 0u32;
let mut i = b;
while i > a {
i = i.saturating_sub(1);
let Some(k) = flat.kind(i) else { break };
if !k.is_token() || k == K::ByteOrderMark {
continue;
}
let text = flat.token_text(i);
if ends_line(k, text) {
return (true, acc, Some(true));
}
if !skipped(k, text) {
return (true, acc, Some(false));
}
acc = acc.saturating_add(chars(text));
}
(false, acc, None)
}
pub(super) fn marks(
flat: Flat<'_>,
rf: &RunFacts,
sf: Option<&StreamFacts>,
a: u32,
b: u32,
) -> Marks {
let docs = sf.is_some_and(|s| s.holds_doc(flat, a, b));
let (a, b) = (a as usize, b as usize);
let (brk, w, clean) = line_moves(flat, a, b);
let mut m = Marks {
docs,
brk,
clean,
w,
..Marks::NONE
};
let content = Marks {
vis: true,
firm: true,
exact: u32::MAX,
head: u32::MAX,
..m
};
if b.saturating_sub(a) > LONG_RUN {
if !rf.segment_at(a).is_some_and(|(_, e)| e >= b) {
return content;
}
m.firm = rf.first_solid_in(a, b).is_some();
let (lo, hi) = (rf.notes_from(a), rf.notes_from(b));
if let Some(first) = rf.note(lo).filter(|_| lo < hi) {
match back(flat, first.slot as usize, a) {
(off, NONE, _) => m.head = off,
(col, _, true) => m.exact = col,
_ => {}
}
m.exact = m.exact.min(rf.min_in(lo.saturating_add(1), hi));
}
return m;
}
let mut col = 0u32;
let mut seen_brk = false;
let mut state: Option<bool> = None;
for i in a..b {
if visible(flat, i) {
return content;
}
let Some(k) = flat.kind(i) else { continue };
m.firm |= !k.is_trivia();
if !k.is_token() || k == K::ByteOrderMark {
continue;
}
if k == K::Comment {
match (state, seen_brk) {
(Some(false), _) => {}
(None, false) => m.head = m.head.min(col),
_ => m.exact = m.exact.min(col),
}
continue;
}
let text = flat.token_text(i);
if let Some(p) = text.rfind(['\n', '\r']) {
col = chars(text.get(p.saturating_add(1)..).unwrap_or(""));
seen_brk = true;
} else {
col = col.saturating_add(chars(text));
}
if ends_line(k, text) {
state = Some(true);
} else if !skipped(k, text) {
state = Some(false);
}
}
m
}
#[derive(Clone, Copy)]
pub(super) struct Piece {
pub(super) arena: u32,
pub(super) a: u32,
pub(super) b: u32,
pub(super) item: Option<u32>,
}
impl SyntaxTree {
fn piece_slot(p: Piece, i: usize) -> Option<u32> {
u32::try_from(i).ok().and_then(|i| p.arena.checked_add(i))
}
fn exact_col(&self, slot: u32) -> Option<usize> {
let n = self.node_at_slot(slot)?;
super::attach::own_col(n)
}
pub(super) fn run_hit(&self, slot: u32, v: u32) -> Option<u32> {
let (mut p, local) = self.piece_at(slot)?;
let mut from = local.checked_add(1)?;
loop {
if let Some(h) = self.scan_piece(p, from as usize, v) {
return Some(h);
}
let item = p.item?;
p = self.piece_after(item, v)?;
from = p.a;
}
}
fn scan_piece(&self, p: Piece, from: usize, v: u32) -> Option<u32> {
let (flat, rf) = self.arena_index(p.arena)?;
let (a, b) = (p.a as usize, p.b as usize);
let exact_hit = |i: usize| {
if v == 0 {
return None;
}
let s = Self::piece_slot(p, i)?;
self.exact_col(s)
.is_some_and(|c| c < v as usize)
.then_some(s)
};
let mut i = from;
while i < b {
if let Some((_, e)) = rf.segment_at(i) {
let end = e.min(b);
let hi = rf.notes_from(end);
let mut k = rf.notes_from(i);
if k < hi && k == rf.notes_from(a) {
if let Some(note) = rf.note(k) {
if back(flat, note.slot as usize, a).1 == NONE {
if let Some(h) = exact_hit(note.slot as usize) {
return Some(h);
}
k = k.saturating_add(1);
}
}
}
if let Some(j) = rf.first_below(k, hi, v) {
return rf
.note(j)
.and_then(|hit| Self::piece_slot(p, hit.slot as usize));
}
if end < b {
return Self::piece_slot(p, end);
}
return None;
}
if visible(flat, i) {
return Self::piece_slot(p, i);
}
if flat.kind(i) == Some(K::Comment) {
if let Some(h) = exact_hit(i) {
return Some(h);
}
}
i = i.saturating_add(1);
}
None
}
pub(super) fn visible_before(&self, slot: u32) -> Option<u32> {
let (mut p, local) = self.piece_at(slot)?;
let mut to = local as usize;
loop {
if let Some(h) = self.scan_back(p, to) {
return Some(h);
}
let item = p.item?;
p = self.piece_visible_before(item)?;
to = p.b as usize;
}
}
fn scan_back(&self, p: Piece, to: usize) -> Option<u32> {
let (flat, rf) = self.arena_index(p.arena)?;
let a = p.a as usize;
let mut i = to;
while i > a {
i = i.saturating_sub(1);
if let Some((s, _)) = rf.segment_at(i) {
if s > a {
return Self::piece_slot(p, s.saturating_sub(1));
}
return None;
}
if visible(flat, i) {
return Self::piece_slot(p, i);
}
}
None
}
pub(super) fn solid_before(&self, slot: u32) -> Option<u32> {
let (mut p, local) = self.piece_at(slot)?;
let mut to = local as usize;
loop {
if let Some(h) = self.solid_back(p, to) {
return Some(h);
}
let item = p.item?;
p = self.piece_firm(item, false)?;
to = p.b as usize;
}
}
fn solid_back(&self, p: Piece, to: usize) -> Option<u32> {
let (flat, rf) = self.arena_index(p.arena)?;
let a = p.a as usize;
let mut i = to;
while i > a {
i = i.saturating_sub(1);
if let Some((s, _)) = rf.segment_at(i) {
if let Some(x) = rf.last_solid_in(s.max(a), i.saturating_add(1)) {
return Self::piece_slot(p, x);
}
if s > a {
return Self::piece_slot(p, s.saturating_sub(1));
}
return None;
}
if flat.kind(i).is_some_and(|k| !k.is_trivia()) {
return Self::piece_slot(p, i);
}
}
None
}
pub(super) fn solid_after(&self, slot: u32) -> Option<u32> {
let (mut p, local) = self.piece_at(slot)?;
let mut from = local.checked_add(1)? as usize;
loop {
if let Some(h) = self.solid_forward(p, from) {
return Some(h);
}
let item = p.item?;
p = self.piece_firm(item, true)?;
from = p.a as usize;
}
}
fn solid_forward(&self, p: Piece, from: usize) -> Option<u32> {
let (flat, rf) = self.arena_index(p.arena)?;
let b = p.b as usize;
let mut i = from;
while i < b {
if let Some((_, e)) = rf.segment_at(i) {
let end = e.min(b);
if let Some(x) = rf.first_solid_in(i, end) {
return Self::piece_slot(p, x);
}
if end < b {
return Self::piece_slot(p, end);
}
return None;
}
if flat.kind(i).is_some_and(|k| !k.is_trivia()) {
return Self::piece_slot(p, i);
}
i = i.saturating_add(1);
}
None
}
pub(super) fn document_before(&self, slot: u32) -> Option<Node<'_>> {
let (mut p, local) = self.piece_at(slot)?;
let mut to = local;
loop {
if let (Some(sf), Some((flat, _))) =
(self.stream_facts_of(p.arena), self.arena_index(p.arena))
{
if let Some(d) = sf.last_doc_in(flat, p.a, to) {
return self.node_at_slot(p.arena.checked_add(d)?);
}
}
let item = p.item?;
p = self.piece_docs(item, false)?;
to = p.b;
}
}
pub(super) fn document_after(&self, slot: u32) -> Option<Node<'_>> {
let (mut p, local) = self.piece_at(slot)?;
let mut from = local.checked_add(1)?;
loop {
if let (Some(sf), Some((flat, _))) =
(self.stream_facts_of(p.arena), self.arena_index(p.arena))
{
if let Some(d) = sf.first_doc_in(flat, from, p.b) {
return self.node_at_slot(p.arena.checked_add(d)?);
}
}
let item = p.item?;
p = self.piece_docs(item, true)?;
from = p.a;
}
}
}
#[cfg(test)]
mod tests {
#![allow(
clippy::unwrap_used,
clippy::indexing_slicing,
clippy::arithmetic_side_effects
)]
use super::*;
use crate::tree::{NodeId, SyntaxTree};
#[test]
fn min_tree_agrees_with_a_scan() {
for count in [1usize, 2, 3, 77, 128, 300] {
let mut src = String::from("a:\n b: 1\n");
src.push_str(&"\n".repeat(70));
for i in 0..count {
src.push_str(&" ".repeat(i % 7));
src.push_str("# c\n");
}
src.push_str("z: 1\n");
let t = SyntaxTree::parse(src);
let rf = RunFacts::of(t.base_flat());
let tables = rf.0.as_deref().unwrap();
assert_eq!(tables.segs.len(), 1);
assert_eq!(tables.notes.len(), count);
assert_eq!(tables.notes.capacity(), count);
assert_eq!(tables.mins.len(), count.next_power_of_two());
let keys: Vec<u32> = tables.notes.iter().map(|n| n.col).collect();
let mut ranges = vec![(0, count), (0, 0), (count / 2, count)];
for lo in 0..count.min(9) {
for hi in lo..count.min(13) {
ranges.push((lo, hi));
}
}
for (lo, hi) in ranges {
for v in 0..9 {
let want = (lo..hi).find(|k| keys[*k] < v);
assert_eq!(rf.first_below(lo, hi, v), want, "{lo} {hi} {v}");
}
let want = keys[lo..hi].iter().copied().min().unwrap_or(u32::MAX);
assert_eq!(rf.min_in(lo, hi), want);
}
for n in &tables.notes {
let node = t.node_at_slot(n.slot).unwrap();
assert_eq!(super::super::attach::own_col(node), Some(n.col as usize));
}
}
}
fn line_inputs() -> Vec<String> {
let mut out = vec![
"\u{feff}# a\nk: v # t\n # b\n# c\n".to_owned(),
"a: |+\n x\n\n# c\n # d\nb: [1, # e\n 2]\n".to_owned(),
"- a\r\n # b\r\n# c\r\n- d\r\n".to_owned(),
"a: 1\r# b\r # c\rz: 2\r".to_owned(),
"--- # h\n# a\n...\n# s\n--- x\n\t# t\n".to_owned(),
"k: >\n folded\n # not a comment\n # c\n".to_owned(),
"\u{feff} # bom then indent\nx: 1\n".to_owned(),
];
let mut long = String::from("a:\n b:\n - 1\n");
for i in 0..150 {
long.push_str(&" ".repeat((i * 5) % 9));
long.push_str(&format!("# c{i}\n"));
if i % 11 == 3 {
long.push_str(" \n\n");
}
if i % 37 == 20 {
long.push_str(" - q # t\n");
}
}
long.push_str("z: 1\n...\n");
for i in 0..90 {
long.push_str(if i % 13 == 0 { "...\n" } else { " # s\n" });
}
out.push(long);
out
}
fn order(t: &SyntaxTree) -> Vec<u32> {
t.root().descendants().map(Node::slot).collect()
}
#[test]
fn line_summaries_compose_as_the_text_reads() {
for src in line_inputs() {
let t = SyntaxTree::parse(src.as_str());
let flat = t.base_flat();
let rf = RunFacts::of(flat);
let n = u32::try_from(flat.len()).unwrap();
let m = |a: u32, b: u32| marks(flat, &rf, Some(&t.facts), a, b);
let mut s = LineState::START;
for i in 0..n {
let node = t.node_at_slot(i).unwrap();
if node.kind() == K::Comment {
let own = super::super::attach::own_col(node);
if s.clean {
assert_eq!(own, Some(s.col as usize), "{src:?} at {i}");
} else {
assert_eq!(own, None, "{src:?} at {i}");
}
}
s = m(i, i + 1).after(s);
}
let step = (n / 40).max(1);
let points: Vec<u32> = (0..=n).step_by(step as usize).chain([n]).collect();
for (x, &a) in points.iter().enumerate() {
for &b in &points[x..] {
let whole = m(a, b);
for &c in points.iter().filter(|c| **c >= a && **c <= b) {
let parts = m(a, c).then(m(c, b));
assert_eq!(
(whole.vis, whole.firm, whole.docs),
(parts.vis, parts.firm, parts.docs)
);
assert_eq!(
(whole.brk, whole.w, whole.clean),
(parts.brk, parts.w, parts.clean),
"{src:?} {a}..{c}..{b}"
);
if !whole.vis {
assert_eq!(
(whole.exact, whole.head),
(parts.exact, parts.head),
"{src:?} {a}..{c}..{b}"
);
}
}
}
}
let all = m(0, n);
assert_eq!(Marks::NONE.then(all), all);
assert_eq!(all.then(Marks::NONE), all);
}
}
fn fragment_long_pieces(t: &SyntaxTree) -> usize {
let mut out = std::collections::BTreeSet::new();
for s in order(t) {
let (p, _) = t.piece_at(s).unwrap();
if p.arena != 0 && t.arena_index(p.arena).unwrap().1.notes_len() > 0 {
out.insert((p.arena, p.a));
}
}
out.len()
}
fn check_primitives(t: &SyntaxTree, what: &str) {
let slots = order(t);
let at = |s: u32| t.node_at_slot(s).unwrap();
let vis = |s: u32| {
let n = at(s);
n.is_token() && !n.kind().is_trivia() && !n.span().is_empty()
};
let own_col = |s: u32| {
let n = at(s);
if n.kind() == K::Comment {
super::super::attach::own_col(n)
} else {
None
}
};
let is_doc = |s: u32| at(s).kind() == K::Document;
let solid = |s: u32| !at(s).kind().is_trivia();
for (k, s) in slots.iter().enumerate() {
let before = slots[..k].iter().rev().find(|x| vis(**x)).copied();
assert_eq!(t.visible_before(*s), before, "{what} slot {s}");
for v in [0u32, 1, 3, 5, 9] {
let hit = slots[k + 1..]
.iter()
.find(|x| vis(**x) || own_col(**x).is_some_and(|c| c < v as usize))
.copied();
assert_eq!(t.run_hit(*s, v), hit, "{what} slot {s} v {v}");
}
let sb = slots[..k].iter().rev().find(|x| solid(**x)).copied();
assert_eq!(t.solid_before(*s), sb, "{what} slot {s}");
let sa = slots[k + 1..].iter().find(|x| solid(**x)).copied();
assert_eq!(t.solid_after(*s), sa, "{what} slot {s}");
let db = slots[..k].iter().rev().find(|x| is_doc(**x)).copied();
assert_eq!(t.document_before(*s).map(Node::slot), db, "{what}");
let da = slots[k + 1..].iter().find(|x| is_doc(**x)).copied();
assert_eq!(t.document_after(*s).map(Node::slot), da, "{what}");
}
}
fn fragment(text: &str) -> crate::tree::Fragment {
let f = SyntaxTree::parse(text);
let kids: Vec<_> = f.root().children().collect();
f.extract(kids[0].id(), kids[kids.len() - 1].id()).unwrap()
}
fn long_lines(k: usize, tag: &str) -> String {
let mut s = String::new();
for i in 0..k {
s.push_str(&" ".repeat((i * 3) % 7));
s.push_str(&format!("# {tag}{i}\n"));
}
s
}
fn ids(t: &SyntaxTree, kind: K) -> Vec<NodeId> {
t.root()
.descendants()
.filter(|n| n.kind() == kind)
.map(Node::id)
.collect()
}
#[test]
fn primitives_agree_with_walks() {
let mut src = String::from("a:\n b:\n - 1\n");
for i in 0..90 {
src.push_str(&" ".repeat((i * 7) % 6));
src.push_str(&format!("# c{i}\n"));
if i % 13 == 5 {
src.push('\n');
}
}
src.push_str("z: 1\n...\n");
for i in 0..80 {
src.push_str(if i % 9 == 0 { "...\n" } else { "# s\n" });
}
src.push_str("--- x\n...\n# t\n--- y\n");
let mut t = SyntaxTree::parse(src);
let pick = |v: &Vec<NodeId>, k: usize| v[(k * 37 + 11) % v.len()];
let mut long_seen = 0usize;
let mut removed = 0usize;
for step in 0..16usize {
check_primitives(&t, &format!("step {step}"));
long_seen = long_seen.max(fragment_long_pieces(&t));
if step % 5 == 2 {
check_primitives(&t.fork(), &format!("fork {step}"));
check_primitives(&t.clone(), &format!("clone {step}"));
}
let comments = ids(&t, K::Comment);
let breaks = ids(&t, K::LineBreak);
match step % 8 {
0 => {
t.replace_token(pick(&comments, step), "# rewritten")
.unwrap();
}
1 => {
let frag = fragment(&format!("{}# new\n", " ".repeat(step % 5)));
let mark = t.begin_group();
let _ = t.insert_after(pick(&breaks, step), frag.clone());
if step % 3 == 0 {
t.rollback_group(mark).unwrap();
} else {
t.end_group(mark).unwrap();
}
let _ = t.insert_after(pick(&breaks, step + 5), frag);
}
2 | 6 => {
let frag = fragment(&long_lines(40, &format!("f{step}-")));
let mark = t.begin_group();
let _ = t.insert_after(pick(&breaks, step + 1), frag.clone());
if step == 6 {
t.rollback_group(mark).unwrap();
let _ = t.insert_after(pick(&breaks, step + 9), frag);
} else {
t.end_group(mark).unwrap();
}
}
3 => {
let inserted: Vec<NodeId> = t
.root()
.descendants()
.filter(|n| n.kind() == K::Comment && n.text().contains("# f"))
.map(Node::id)
.collect();
for (k, c) in inserted.iter().enumerate().filter(|(k, _)| k % 6 == 2) {
let n = t.get(*c).unwrap();
match n.prev_sibling().filter(|w| w.kind() == K::Whitespace) {
Some(w) if k % 4 == 0 => {
let (w, len) = (w.id(), w.text().len());
t.replace_token(w, &" ".repeat(len % 5 + 1 + k % 3))
.unwrap();
}
_ => {
t.replace_token(*c, "# cut").unwrap();
}
}
}
}
4 => {
let c = t
.root()
.descendants()
.filter(|n| n.kind() == K::Comment && n.text() == "# cut")
.nth(1)
.unwrap();
let first = c
.prev_sibling()
.filter(|w| w.kind() == K::Whitespace)
.unwrap_or(c)
.id();
let mut last = c;
let mut lines = 0;
while lines < 5 {
let Some(x) = last.next_sibling() else { break };
last = x;
if last.kind() == K::LineBreak {
lines += 1;
}
}
let last = last.id();
let mark = t.begin_group();
if t.remove_range(first, last).is_ok() && lines == 5 {
removed += 1;
}
t.end_group(mark).unwrap();
}
5 => {
for c in comments.iter().take(60) {
let text = t.get(*c).unwrap().text().into_owned();
let _ = t.replace_token(*c, &text);
}
}
_ => {
let c = t.get(pick(&comments, step + 2)).unwrap();
let b = c.next_sibling().unwrap().id();
let c = c.id();
let _ = t.remove_range(c, b);
}
}
assert!(t == SyntaxTree::parse(t.emit()), "step {step}");
}
assert!(long_seen >= 2, "{long_seen} long fragment pieces");
assert!(removed >= 1, "no multi-piece removal");
}
#[test]
fn segments_are_the_maximal_long_runs() {
let mut inputs = line_inputs();
for gap in [20usize, 21, 22, 23, 43, 44, 45] {
for lead in [0usize, 1, 2] {
let mut s = "# x\n".repeat(lead * gap);
for k in 0..4 {
s.push_str(&format!("k{k}: v\n"));
s.push_str(&" # c\n".repeat(gap + k % 2));
}
inputs.push(s);
}
}
for src in inputs {
let t = SyntaxTree::parse(src.as_str());
let flat = t.base_flat();
let mut want = Vec::new();
let mut start = None;
for i in 0..=flat.len() {
if i == flat.len() || visible(flat, i) {
if let Some(a) = start.take() {
if i - a > LONG_RUN {
want.push((a as u32, i as u32));
}
}
} else if start.is_none() {
start = Some(i);
}
}
let rf = RunFacts::of(flat);
let got = rf.0.as_deref().map_or(Vec::new(), |t| t.segs.clone());
assert_eq!(got, want, "{src:?}");
}
}
#[test]
fn primitives_agree_without_a_document_list() {
let mut src = String::from("--- a\n");
src.push_str(&long_lines(30, "h"));
src.push_str("...\n");
src.push_str(&long_lines(30, "s"));
src.push_str("--- b: 1\n...\n# t\n---\n- c\n");
let mut t = SyntaxTree::parse(src);
assert!(!t.facts.has_doc_list());
let pick = |v: &Vec<NodeId>, k: usize| v[(k * 37 + 11) % v.len()];
let mut inserted = 0;
for step in 0..8usize {
check_primitives(&t, &format!("no list, step {step}"));
let breaks = ids(&t, K::LineBreak);
let comments = ids(&t, K::Comment);
let text = match step % 4 {
0 => "--- z\n".to_owned(),
1 => "...\n# stray\n".to_owned(),
2 => long_lines(25, &format!("n{step}-")),
_ => {
let c = t.get(pick(&comments, step)).unwrap();
let b = c.next_sibling().unwrap().id();
let c = c.id();
let _ = t.remove_range(c, b);
continue;
}
};
let at = breaks
.iter()
.copied()
.filter(|b| {
t.get(*b)
.unwrap()
.parent()
.is_some_and(|p| p.kind() == K::Stream)
})
.nth(step % 3);
if let Some(at) = at {
inserted += usize::from(t.insert_after(at, fragment(&text)).is_ok());
}
assert!(t == SyntaxTree::parse(t.emit()), "step {step}");
}
check_primitives(&t, "no list, end");
assert!(inserted >= 3, "{inserted} insertions");
}
#[test]
fn short_runs_allocate_nothing() {
let t = SyntaxTree::parse("a: 1 # c\n# d\nb: 2\n");
let rf = RunFacts::of(t.base_flat());
assert_eq!(rf, RunFacts::default());
assert_eq!(rf.heap_bytes(), 0);
assert_eq!(size_of::<RunFacts>(), 8);
assert_eq!(size_of::<Marks>(), 20);
}
#[test]
fn long_run_tables_are_exactly_sized() {
for n in [100usize, 1000, 1025, 75_000] {
let mut src = String::from("a:\n b: 1\n");
for i in 0..n {
src.push_str(&format!(" # comment line {i}\n"));
}
src.push_str("z: 1\n");
let t = SyntaxTree::parse(src);
let rf = RunFacts::of(t.base_flat());
let fixed = size_of::<Tables>() + 4 * 8;
let bytes = rf.heap_bytes();
assert!(bytes <= fixed + 16 * n, "{n} comments: {bytes} bytes");
assert!(bytes >= 12 * n, "{n} comments: {bytes} bytes");
}
}
}