use super::{Node, SyntaxKind as K, SyntaxTree};
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum AttachRule {
HeaderBeforeStart,
HeaderBlankLine,
FirstNodeLeading,
Leading,
Trailing,
CollectionFooter,
DocumentFooter,
Flow,
ShallowLeading,
ExplicitValue,
Inside,
RunOrder,
}
impl AttachRule {
#[must_use]
pub const fn number(self) -> u8 {
match self {
Self::HeaderBeforeStart => 1,
Self::HeaderBlankLine => 2,
Self::FirstNodeLeading => 3,
Self::Leading => 4,
Self::Trailing => 5,
Self::CollectionFooter => 6,
Self::DocumentFooter => 7,
Self::Flow => 9,
Self::ShallowLeading => 10,
Self::ExplicitValue => 11,
Self::Inside => 12,
Self::RunOrder => 13,
}
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum CommentOwner<'t> {
DocumentHeader(Node<'t>),
DocumentFooter(Node<'t>),
Leading(Node<'t>),
Trailing(Node<'t>),
Footer(Node<'t>),
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Attachment<'t> {
owner: CommentOwner<'t>,
rule: AttachRule,
blank_lines_before: usize,
document: Option<Node<'t>>,
}
impl<'t> Attachment<'t> {
#[must_use]
pub const fn owner(&self) -> CommentOwner<'t> {
self.owner
}
#[must_use]
pub const fn rule(&self) -> AttachRule {
self.rule
}
#[must_use]
pub const fn blank_lines_before(&self) -> usize {
self.blank_lines_before
}
#[must_use]
pub const fn document(&self) -> Option<Node<'t>> {
self.document
}
}
impl SyntaxTree {
#[must_use]
pub fn comment_attachment<'t>(&'t self, comment: Node<'t>) -> Option<Attachment<'t>> {
if comment.kind() != K::Comment || !core::ptr::eq(comment.tree(), self) {
return None;
}
let around = Around::Scan;
let a = match line_of(comment) {
Line::Same(p) => same_line(locate(p), &around),
Line::Own(end) => match self.decide_indexed(comment, end, Want::Attachment) {
Some(Decided::Attachment(a)) => a,
_ => self.replay(comment)?,
},
};
Some(a)
}
#[must_use]
pub fn comment_document<'t>(&'t self, comment: Node<'t>) -> Option<Option<Node<'t>>> {
if comment.kind() != K::Comment || !core::ptr::eq(comment.tree(), self) {
return None;
}
match line_of(comment) {
Line::Same(p) => Some(same_line(locate(p), &Around::Scan).document),
Line::Own(end) => match self.decide_indexed(comment, end, Want::Document) {
Some(Decided::Document(d)) => Some(d),
Some(Decided::Attachment(a)) => Some(a.document),
None => self.replay(comment).map(|a| a.document),
},
}
}
#[must_use]
pub fn prev_content_token<'t>(&'t self, n: Node<'t>) -> Option<Node<'t>> {
core::ptr::eq(n.tree(), self)
.then(|| prev_visible(n))
.flatten()
}
#[must_use]
pub fn next_content_token<'t>(&'t self, n: Node<'t>) -> Option<Node<'t>> {
core::ptr::eq(n.tree(), self)
.then(|| next_visible(n))
.flatten()
}
#[must_use]
pub fn last_footer_comment<'t>(&'t self, collection: Node<'t>) -> Option<Node<'t>> {
if !is_block(collection.kind()) || !core::ptr::eq(collection.tree(), self) {
return None;
}
let p = last_visible_in(collection)?;
let n = next_visible(p);
let around = Around::Scan;
let ahead = Ahead {
next: n,
last_blank: None,
};
let plan = make_plan(self, Some(locate(p)), &ahead, &around);
if !cols_fit(&plan) {
return self.last_footer_comment_walk(collection, p, &plan);
}
let i = plan.footer.iter().position(|(k, _)| *k == collection)?;
let span = collection.span();
let within = |y: Node<'_>| {
let s = y.span();
span.start <= s.start && s.end <= span.end
};
let mut j = i;
while plan
.footer
.get(j.saturating_add(1))
.is_some_and(|(k, _)| within(*k))
{
j = j.saturating_add(1);
}
let cut = cut_below(&plan, j.saturating_add(1))?;
let stop = self.run_hit(p.slot(), cut);
let stop = stop.and_then(|s| self.node_at_slot(s));
let mut at = match stop {
Some(s) => prev_token(s),
None => last_token(self),
};
while let Some(t) = at {
if t == p || visible(t) {
return None;
}
if t.kind() == K::Comment {
return matches!(line_of(t), Line::Own(_)).then_some(t);
}
at = prev_token(t);
}
None
}
fn last_footer_comment_walk<'t>(
&'t self,
collection: Node<'t>,
p: Node<'t>,
plan: &Plan<'t>,
) -> Option<Node<'t>> {
let span = collection.span();
let within = |y: Node<'_>| {
let s = y.span();
span.start <= s.start && s.end <= span.end
};
let mut floor = None;
let mut last = None;
let mut at = next_token(p);
while let Some(t) = at {
if visible(t) {
break;
}
if t.kind() == K::Comment {
if let Line::Own(end) = line_of(t) {
let a = decide(plan, t, col_of(t), blank_before(end), &mut floor);
match a.owner {
CommentOwner::Footer(y) if within(y) => last = Some(t),
_ => break,
}
}
}
at = next_token(t);
}
last
}
fn decide_indexed<'t>(
&'t self,
c: Node<'t>,
end: Option<Node<'t>>,
want: Want,
) -> Option<Decided<'t>> {
let p = prev_visible(c);
let n = next_visible(c);
let around = Around::Scan;
let ahead = Ahead {
next: n,
last_blank: None,
};
let mut plan = make_plan(self, p.map(locate), &ahead, &around);
if !cols_fit(&plan) {
return None;
}
let outer = plan.footer.len();
let header = matches!(plan.otherwise, Otherwise::Header { .. });
let col = col_of(c);
let floor = self.floor_rank(&plan, p, c)?;
if let Want::Document = want {
let rank = floor.max(own_rank(&plan, col));
let doc = if rank < outer {
plan.footer_document
} else {
plan.document
};
return Some(Decided::Document(doc));
}
if header && outer > 0 {
return None;
}
if let Otherwise::Header { last_blank, .. } = &mut plan.otherwise {
*last_blank = scan_ahead(c).last_blank;
}
let blank = blank_before(end);
let (a, rank) = decide_one(&plan, c, col, blank);
if floor <= rank {
return Some(Decided::Attachment(a));
}
let (owner, document) = match plan.footer.get(floor) {
Some((k, _)) => (CommentOwner::Footer(*k), plan.footer_document),
None => match plan.otherwise {
Otherwise::Fixed(o, _) => (o, plan.document),
Otherwise::Leading { target, .. } => (CommentOwner::Leading(target), plan.document),
Otherwise::Header { .. } => {
debug_assert!(false, "rule 13 above a header owner");
return None;
}
},
};
Some(Decided::Attachment(Attachment {
owner,
rule: AttachRule::RunOrder,
blank_lines_before: blank,
document,
}))
}
fn floor_rank(&self, plan: &Plan<'_>, p: Option<Node<'_>>, c: Node<'_>) -> Option<usize> {
let outer = plan.footer.len();
if outer == 0 {
return Some(0);
}
let from = p.map_or(0, Node::slot);
let at = c.preorder_index();
let exists = |k: usize| -> Option<bool> {
let cut = cut_below(plan, k)?;
Some(
self.run_hit(from, cut)
.and_then(|s| self.node_at_slot(s))
.is_some_and(|h| h.preorder_index() < at),
)
};
let (mut lo, mut hi) = (0usize, outer);
while lo < hi {
let mid = lo.saturating_add(hi.saturating_sub(lo).saturating_add(1) / 2);
if exists(mid)? {
lo = mid;
} else {
hi = mid.saturating_sub(1);
}
}
Some(lo)
}
fn replay<'t>(&'t self, comment: Node<'t>) -> Option<Attachment<'t>> {
let around = Around::Scan;
let mut run = Vec::new();
let mut p = None;
let mut at = prev_token(comment);
while let Some(t) = at {
if visible(t) {
p = Some(t);
break;
}
if t.kind() == K::Comment {
run.push(t);
}
at = prev_token(t);
}
run.reverse();
run.push(comment);
let own: Vec<(Node<'t>, Option<Node<'t>>)> = run
.into_iter()
.filter_map(|r| match line_of(r) {
Line::Own(end) => Some((r, end)),
Line::Same(_) => None,
})
.collect();
let first = own.first().map_or(comment, |(r, _)| *r);
let plan = make_plan(self, p.map(locate), &scan_ahead(first), &around);
let mut floor = None;
let mut last = None;
for (r, end) in own {
last = Some(decide(&plan, r, col_of(r), blank_before(end), &mut floor));
}
last
}
#[must_use]
pub fn comment_run_attachments<'t>(
&'t self,
comment: Node<'t>,
) -> Vec<(Node<'t>, Attachment<'t>)> {
if comment.kind() != K::Comment || !core::ptr::eq(comment.tree(), self) {
return Vec::new();
}
let mut run = Vec::new();
let mut p = None;
let mut at = prev_token(comment);
while let Some(t) = at {
if visible(t) {
p = Some(t);
break;
}
if t.kind() == K::Comment {
run.push(t);
}
at = prev_token(t);
}
run.reverse();
run.push(comment);
let mut at = next_token(comment);
while let Some(t) = at {
if visible(t) {
break;
}
if t.kind() == K::Comment {
run.push(t);
}
at = next_token(t);
}
let around = Around::Scan;
let from = p.map(locate);
let mut plan: Option<Plan<'t>> = None;
let mut floor = None;
let mut out = Vec::with_capacity(run.len());
for r in run {
let a = match line_of(r) {
Line::Same(q) => same_line(locate(q), &around),
Line::Own(end) => {
let plan =
plan.get_or_insert_with(|| make_plan(self, from, &scan_ahead(r), &around));
decide(plan, r, col_of(r), blank_before(end), &mut floor)
}
};
out.push((r, a));
}
out
}
#[must_use]
pub fn comment_attachments_between<'t>(
&'t self,
before: Option<Node<'t>>,
after: Option<Node<'t>>,
) -> Vec<(Node<'t>, Attachment<'t>)> {
let is_doc = |d: Option<Node<'t>>| {
d.is_none_or(|d| {
d.kind() == K::Document
&& core::ptr::eq(d.tree(), self)
&& d.parent().is_some_and(|p| p.kind() == K::Stream)
})
};
if !is_doc(before) || !is_doc(after) {
return Vec::new();
}
let mut tops = Vec::new();
let mut at = match before {
Some(b) => b.next_sibling(),
None => self.root().first_child(),
};
while let Some(n) = at {
if Some(n) == after {
break;
}
tops.push(n);
at = n.next_sibling();
}
if at != after {
return Vec::new();
}
let start = tops.first().and_then(|f| prev_visible(*f)).map(locate);
pass(self, &tops, start, before, after, None)
}
#[must_use]
pub fn comment_attachments(&self) -> Vec<(Node<'_>, Attachment<'_>)> {
let tops: Vec<Node<'_>> = self.root().children().collect();
pass(self, &tops, None, None, None, None)
}
#[must_use]
pub fn document_comment_attachments<'t>(
&'t self,
document: Node<'t>,
) -> Vec<(Node<'t>, Attachment<'t>)> {
if document.kind() != K::Document || !core::ptr::eq(document.tree(), self) {
return Vec::new();
}
let mut first = document;
let mut before = None;
while let Some(p) = first.prev_sibling() {
if p.kind() == K::Document {
before = Some(p);
break;
}
first = p;
}
let start = prev_visible(first).map(locate);
let mut tops = Vec::new();
let mut at = Some(first);
let mut after = None;
while let Some(n) = at {
if n.kind() == K::Document && n != document {
after = Some(n);
break;
}
tops.push(n);
at = n.next_sibling();
}
pass(self, &tops, start, before, after, Some(document))
}
}
fn edge_tokens<'t>(doc: Node<'t>, p: Option<Node<'t>>) -> Vec<Node<'t>> {
let mut out = Vec::new();
let mut at = match p {
Some(p) => next_token(p),
None => Some(first_token(doc)).filter(|t| t.is_token()),
};
while let Some(t) = at {
if visible(t) || !contains(doc, t) {
break;
}
out.push(t);
at = next_token(t);
}
out
}
#[derive(Clone, Copy)]
struct At<'t> {
tok: Node<'t>,
doc: Option<Node<'t>>,
child: Option<Node<'t>>,
}
fn locate(tok: Node<'_>) -> At<'_> {
let mut below = tok;
for a in tok.ancestors() {
if a.kind() == K::Document {
return At {
tok,
doc: Some(a),
child: Some(below),
};
}
below = a;
}
At {
tok,
doc: None,
child: None,
}
}
enum Around<'t> {
Scan,
Known {
prev: Option<Node<'t>>,
next: Option<Node<'t>>,
},
}
impl<'t> Around<'t> {
fn prev_doc(&self, x: Node<'t>) -> Option<Node<'t>> {
match self {
Self::Known { prev, .. } => *prev,
Self::Scan => x.tree().document_before(x.slot()),
}
}
fn next_doc(&self, x: Node<'t>) -> Option<Node<'t>> {
match self {
Self::Known { next, .. } => *next,
Self::Scan => x.tree().document_after(x.slot()),
}
}
}
fn pass<'t>(
tree: &'t SyntaxTree,
tops: &[Node<'t>],
start: Option<At<'t>>,
before: Option<Node<'t>>,
after: Option<Node<'t>>,
want: Option<Node<'t>>,
) -> Vec<(Node<'t>, Attachment<'t>)> {
let is_doc = |n: &Node<'t>| n.kind() == K::Document;
let mut prevs = Vec::with_capacity(tops.len());
let mut last = before;
for t in tops {
prevs.push(last);
if is_doc(t) {
last = Some(*t);
}
}
let mut nexts = vec![None; tops.len()];
let mut next = after;
for (t, slot) in tops.iter().zip(nexts.iter_mut()).rev() {
*slot = next;
if is_doc(t) {
next = Some(*t);
}
}
let tail = match (want, before, start) {
(Some(_), Some(b), Some(p)) if p.doc == Some(b) => edge_tokens(b, Some(p.tok)),
_ => Vec::new(),
};
let head = match (want, after) {
(Some(_), Some(a)) => edge_tokens(a, None),
_ => Vec::new(),
};
let mut out = Vec::new();
let mut p = start;
let mut plan: Option<Plan<'t>> = None;
let mut floor: Option<Floor<'t>> = None;
let mut step =
|t: Node<'t>, doc: Option<Node<'t>>, child: Option<Node<'t>>, around: &Around<'t>| {
if t.kind() == K::Comment {
let a = match line_of(t) {
Line::Same(q) => {
let at = match p {
Some(x) if x.tok == q => x,
_ => locate(q),
};
same_line(at, around)
}
Line::Own(end) => {
let plan =
plan.get_or_insert_with(|| make_plan(tree, p, &scan_ahead(t), around));
decide(plan, t, col_of(t), blank_before(end), &mut floor)
}
};
if want.is_none_or(|w| a.document == Some(w)) {
out.push((t, a));
}
} else if visible(t) {
p = Some(At { tok: t, doc, child });
plan = None;
floor = None;
}
};
let first_next = tops.iter().copied().find(is_doc).or(after);
let tail_around = Around::Known {
prev: None,
next: first_next,
};
for t in tail {
step(t, before, None, &tail_around);
}
for ((top, prev), next) in tops.iter().zip(prevs).zip(nexts) {
let around = Around::Known { prev, next };
if is_doc(top) {
for ch in top.children() {
for t in ch.descendants() {
step(t, Some(*top), Some(ch), &around);
}
}
} else {
for t in top.descendants() {
step(t, None, None, &around);
}
}
}
let last_doc = tops.iter().copied().rev().find(is_doc).or(before);
let head_around = Around::Known {
prev: last_doc,
next: after,
};
for t in head {
step(t, after, None, &head_around);
}
out
}
fn is_item(k: K) -> bool {
k.is_yaml_node() || k == K::Error
}
fn is_block(k: K) -> bool {
matches!(k, K::BlockMapping | K::BlockSequence)
}
fn is_map(k: K) -> bool {
matches!(k, K::BlockMapping | K::FlowMapping | K::FlowPair)
}
fn is_seq(k: K) -> bool {
matches!(k, K::BlockSequence | K::FlowSequence)
}
fn is_flow(k: K) -> bool {
matches!(k, K::FlowMapping | K::FlowSequence | K::FlowPair)
}
fn empty(n: Node<'_>) -> bool {
n.span().is_empty()
}
fn visible(t: Node<'_>) -> bool {
t.is_token() && !t.kind().is_trivia() && !empty(t)
}
fn blankish(t: Node<'_>) -> bool {
matches!(t.kind(), K::Whitespace | K::ByteOrderMark) || (t.kind() != K::LineBreak && empty(t))
}
fn ends_line(t: Node<'_>) -> bool {
t.kind() == K::LineBreak || (!empty(t) && t.text().ends_with(['\n', '\r']))
}
fn prev_token(n: Node<'_>) -> Option<Node<'_>> {
let mut at = n.pred();
while let Some(x) = at {
if x.is_token() {
return Some(x);
}
at = x.pred();
}
None
}
fn next_token(n: Node<'_>) -> Option<Node<'_>> {
let mut at = n.succ();
while let Some(x) = at {
if x.is_token() {
return Some(x);
}
at = x.succ();
}
None
}
fn prev_visible(n: Node<'_>) -> Option<Node<'_>> {
let t = n.tree();
t.visible_before(n.slot()).and_then(|s| t.node_at_slot(s))
}
fn next_visible(n: Node<'_>) -> Option<Node<'_>> {
let t = n.tree();
t.run_hit(n.slot(), 0).and_then(|s| t.node_at_slot(s))
}
fn last_visible_in(n: Node<'_>) -> Option<Node<'_>> {
let t = n.tree();
let leaf = t.node_at_slot(t.nav_last_leaf(n.slot())?)?;
let last = if visible(leaf) {
leaf
} else {
prev_visible(leaf)?
};
contains(n, last).then_some(last)
}
fn last_token(tree: &SyntaxTree) -> Option<Node<'_>> {
let root = tree.root();
let leaf = tree.node_at_slot(tree.nav_last_leaf(root.slot())?)?;
if leaf.is_token() {
Some(leaf)
} else {
prev_token(leaf)
}
}
pub(super) fn own_col(c: Node<'_>) -> Option<usize> {
match line_of(c) {
Line::Own(_) => Some(col_of(c)),
Line::Same(_) => None,
}
}
fn contains(a: Node<'_>, n: Node<'_>) -> bool {
let ai = a.preorder_index();
let ni = n.preorder_index();
ai <= ni && ni < ai.saturating_add(a.descendants().len())
}
fn col_of(t: Node<'_>) -> usize {
let mut col = 0usize;
let mut at = prev_token(t);
while let Some(x) = at {
if x.kind() == K::ByteOrderMark {
at = prev_token(x);
continue;
}
let text = x.text();
if let Some(i) = text.rfind(['\n', '\r']) {
let tail = text.get(i.saturating_add(1)..).unwrap_or("");
return col.saturating_add(tail.chars().count());
}
col = col.saturating_add(text.chars().count());
at = prev_token(x);
}
col
}
fn first_token(n: Node<'_>) -> Node<'_> {
let mut at = n;
while let Some(c) = at.first_child() {
at = c;
}
at
}
fn coll_start(c: Node<'_>) -> Node<'_> {
let first = c
.children()
.find(|x| !x.kind().is_trivia() && !matches!(x.kind(), K::Anchor | K::Tag))
.unwrap_or(c);
first_token(first)
}
fn cols_of(tokens: &[Node<'_>]) -> Vec<usize> {
let mut out = vec![0usize; tokens.len()];
let mut i = 0usize;
while let Some(&t) = tokens.get(i) {
let mut acc = 0usize;
let mut met = vec![(i, 0usize)];
let mut j = i.saturating_add(1);
let mut at = prev_token(t);
while let Some(x) = at {
let text = x.text();
let chars = if x.kind() == K::ByteOrderMark {
0
} else {
text.chars().count()
};
let breaks = text.contains(['\n', '\r']);
while tokens.get(j) == Some(&x) {
if !breaks {
met.push((j, acc.saturating_add(chars)));
j = j.saturating_add(1);
} else {
break;
}
}
if let Some(k) = text.rfind(['\n', '\r']) {
let tail = text.get(k.saturating_add(1)..).unwrap_or("");
acc = acc.saturating_add(tail.chars().count());
break;
}
acc = acc.saturating_add(chars);
at = prev_token(x);
}
for (k, before) in met {
if let Some(o) = out.get_mut(k) {
*o = acc.saturating_sub(before);
}
}
i = j.max(i.saturating_add(1));
}
out
}
fn next_sig(x: Node<'_>) -> Option<Node<'_>> {
let parent = x.parent()?;
let t = x.tree();
let last = t.nav_last_leaf(x.slot())?;
let s = t.node_at_slot(t.solid_after(last)?)?;
(s.parent() == Some(parent)).then_some(s)
}
fn prev_sig(x: Node<'_>) -> Option<Node<'_>> {
let parent = x.parent()?;
let t = x.tree();
let mut s = t.node_at_slot(t.solid_before(x.slot())?)?;
loop {
if s == parent {
return None;
}
match s.parent() {
Some(p) if p == parent => return Some(s),
Some(p) => s = p,
None => return None,
}
}
}
fn next_item(x: Node<'_>) -> Option<Node<'_>> {
let mut at = next_sig(x);
while let Some(s) = at {
if is_item(s.kind()) {
return Some(s);
}
at = next_sig(s);
}
None
}
fn prev_item(x: Node<'_>) -> Option<Node<'_>> {
let mut at = prev_sig(x);
while let Some(s) = at {
if is_item(s.kind()) {
return Some(s);
}
at = prev_sig(s);
}
None
}
fn local_key(x: Node<'_>) -> Option<bool> {
match prev_sig(x).map(Node::kind) {
None | Some(K::MappingKey | K::FlowMappingOpen | K::FlowSequenceOpen | K::FlowEntry) => {
return Some(true);
}
Some(K::MappingValue) => return Some(false),
_ => {}
}
if next_sig(x).is_some_and(|s| s.kind() == K::MappingValue) {
return Some(true);
}
match prev_sig(x) {
Some(p) if is_item(p.kind()) => None,
_ => Some(true),
}
}
fn is_key(x: Node<'_>) -> bool {
if let Some(k) = local_key(x) {
return k;
}
prev_item(x).and_then(local_key).is_none_or(|k| !k)
}
fn key_of(x: Node<'_>) -> Node<'_> {
if is_key(x) {
x
} else {
prev_item(x).unwrap_or(x)
}
}
fn entry_owner<'t>(c: Node<'t>, x: Node<'t>) -> Option<Node<'t>> {
let k = x.kind();
if matches!(
k,
K::FlowSequenceOpen
| K::FlowSequenceClose
| K::FlowMappingOpen
| K::FlowMappingClose
| K::Anchor
| K::Tag
) {
return None;
}
if is_seq(c.kind()) {
return match k {
_ if is_item(k) => Some(x),
K::SequenceEntry => next_item(x),
_ => prev_item(x),
};
}
match k {
_ if is_item(k) => Some(key_of(x)),
K::MappingKey => next_item(x),
K::MappingValue => prev_item(x),
_ => prev_item(x).map(key_of),
}
}
fn entry_opened<'t>(c: Node<'t>, x: Node<'t>) -> Option<Node<'t>> {
let k = x.kind();
match c.kind() {
K::BlockSequence => (k == K::SequenceEntry).then(|| next_item(x)).flatten(),
K::FlowSequence => is_item(k).then_some(x),
_ if is_map(c.kind()) => {
if k == K::MappingKey {
return next_item(x);
}
let after_q = prev_sig(x).is_some_and(|p| p.kind() == K::MappingKey);
(is_item(k) && !after_q && is_key(x)).then_some(x)
}
_ => None,
}
}
#[derive(Clone, Copy, Debug)]
enum Opens {
Entry,
Node,
ExplicitValue,
Inside,
}
fn target_of<'t>(n: Node<'t>, fallback: Node<'t>) -> (Node<'t>, Opens) {
let s = n.span().start;
let mut x = n;
while let Some(a) = x.parent() {
if is_map(a.kind()) || is_seq(a.kind()) {
if let Some(e) = entry_opened(a, x) {
return (e, Opens::Entry);
}
}
if !is_item(a.kind()) || a.span().start != s {
break;
}
x = a;
}
if is_item(x.kind()) {
return (x, Opens::Node);
}
if x.kind() == K::MappingValue {
if let Some(v) = next_item(x) {
return (v, Opens::ExplicitValue);
}
}
let holder = x
.ancestors()
.find(|a| is_item(a.kind()))
.unwrap_or(fallback);
(holder, Opens::Inside)
}
enum Line<'t> {
Own(Option<Node<'t>>),
Same(Node<'t>),
}
fn line_of(c: Node<'_>) -> Line<'_> {
let mut at = prev_token(c);
while let Some(t) = at {
if ends_line(t) {
return Line::Own(Some(t));
}
if blankish(t) || t.kind() == K::Comment {
at = prev_token(t);
continue;
}
return Line::Same(t);
}
Line::Own(None)
}
fn blank_before(end: Option<Node<'_>>) -> usize {
let Some(mut at) = end else { return 0 };
let mut count = 0usize;
loop {
if at.kind() != K::LineBreak {
return count;
}
let mut u = prev_token(at);
while let Some(t) = u.filter(|t| blankish(*t)) {
u = prev_token(t);
}
match u {
None => return count.saturating_add(1),
Some(t) if t.kind() == K::LineBreak => {
count = count.saturating_add(1);
at = t;
}
Some(t) if ends_line(t) => return count.saturating_add(1),
Some(_) => return count,
}
}
}
struct Ahead<'t> {
next: Option<Node<'t>>,
last_blank: Option<usize>,
}
fn scan_ahead(c: Node<'_>) -> Ahead<'_> {
let mut line_empty = false;
let mut last_blank = None;
let mut at = next_token(c);
while let Some(t) = at {
match t.kind() {
K::LineBreak => {
if line_empty {
last_blank = Some(t.span().start);
}
line_empty = true;
}
K::Comment => line_empty = false,
_ if blankish(t) => {}
_ => {
return Ahead {
next: Some(t),
last_blank,
};
}
}
at = next_token(t);
}
Ahead {
next: None,
last_blank,
}
}
fn is_start(n: Node<'_>) -> bool {
matches!(
n.kind(),
K::DocumentStartMarker | K::YamlDirective | K::TagDirective | K::ReservedDirective
)
}
fn has_start(doc: Node<'_>) -> bool {
doc.first_child().is_some_and(is_start)
}
fn same_line<'t>(p: At<'t>, around: &Around<'t>) -> Attachment<'t> {
let done = |owner, document| Attachment {
owner,
rule: AttachRule::Trailing,
blank_lines_before: 0,
document,
};
let mut x = p.tok;
loop {
let Some(a) = x.parent() else {
return done(CommentOwner::DocumentHeader(x), None);
};
let k = a.kind();
if is_map(k) || is_seq(k) {
if let Some(o) = entry_owner(a, x) {
return done(CommentOwner::Trailing(o), p.doc);
}
} else if k == K::Document {
return if is_start(x) {
done(CommentOwner::DocumentHeader(a), Some(a))
} else if is_item(x.kind()) {
done(CommentOwner::Trailing(x), Some(a))
} else {
done(CommentOwner::DocumentFooter(a), Some(a))
};
} else if k == K::Stream {
if let Some(d) = around.next_doc(x) {
return done(CommentOwner::DocumentHeader(d), Some(d));
}
return match around.prev_doc(x) {
Some(d) => done(CommentOwner::DocumentFooter(d), Some(d)),
None => done(CommentOwner::DocumentHeader(a), None),
};
}
x = a;
}
}
enum Otherwise<'t> {
Fixed(CommentOwner<'t>, AttachRule),
Header {
doc: Node<'t>,
target: Node<'t>,
last_blank: Option<usize>,
},
Leading {
target: Node<'t>,
opens: Opens,
col: usize,
},
}
struct Plan<'t> {
footer: Vec<(Node<'t>, usize)>,
threshold: usize,
otherwise: Otherwise<'t>,
document: Option<Node<'t>>,
footer_document: Option<Node<'t>>,
}
impl<'t> Plan<'t> {
fn fixed(owner: CommentOwner<'t>, rule: AttachRule, document: Option<Node<'t>>) -> Self {
Self {
footer: Vec::new(),
threshold: 0,
otherwise: Otherwise::Fixed(owner, rule),
document,
footer_document: document,
}
}
fn header(doc: Node<'t>, rule: AttachRule) -> Self {
Self::fixed(CommentOwner::DocumentHeader(doc), rule, Some(doc))
}
}
fn closing<'t>(
p: Node<'t>,
stop: impl Fn(Node<'t>) -> bool,
) -> (Vec<(Node<'t>, usize)>, Option<Node<'t>>) {
let mut colls = Vec::new();
let mut at = p.parent();
let mut lca = None;
while let Some(a) = at {
if stop(a) || matches!(a.kind(), K::Document | K::Stream) {
lca = Some(a);
break;
}
if is_block(a.kind()) {
colls.push(a);
}
at = a.parent();
}
let starts: Vec<Node<'t>> = colls.iter().map(|c| coll_start(*c)).collect();
let cols = cols_of(&starts);
(colls.into_iter().zip(cols).collect(), lca)
}
fn header_plan<'t>(d: Node<'t>, r: Node<'t>, n: Node<'t>, ahead: &Ahead<'t>) -> Plan<'t> {
Plan {
footer: Vec::new(),
threshold: 0,
otherwise: Otherwise::Header {
doc: d,
target: target_of(n, r).0,
last_blank: ahead.last_blank,
},
document: Some(d),
footer_document: Some(d),
}
}
fn make_plan<'t>(
tree: &'t SyntaxTree,
p: Option<At<'t>>,
ahead: &Ahead<'t>,
around: &Around<'t>,
) -> Plan<'t> {
let n = ahead.next.map(|n| match p {
Some(At {
doc: Some(d),
child,
..
}) if contains(d, n) => {
let child = match child {
Some(c) if contains(c, n) => Some(c),
_ => {
let mut below = n;
while let Some(a) = below.parent().filter(|a| *a != d) {
below = a;
}
Some(below)
}
};
At {
tok: n,
doc: Some(d),
child,
}
}
_ => locate(n),
});
match (p, n) {
(
Some(At {
tok: pt,
doc: Some(d),
child: Some(xp),
}),
Some(At {
tok: nt,
doc: Some(e),
child: Some(xn),
}),
) if d == e => inside(d, pt, xp, nt, xn, ahead),
_ => between(tree, p, n, ahead, around),
}
}
fn inside<'t>(
d: Node<'t>,
p: Node<'t>,
xp: Node<'t>,
n: Node<'t>,
xn: Node<'t>,
ahead: &Ahead<'t>,
) -> Plan<'t> {
if is_start(xn) {
return Plan::header(d, AttachRule::HeaderBeforeStart);
}
if is_start(xp) {
return if is_item(xn.kind()) && !empty(xn) {
header_plan(d, xn, n, ahead)
} else {
Plan::header(d, AttachRule::HeaderBlankLine)
};
}
if xp != xn || !is_item(xn.kind()) {
let (footer, _) = closing(p, |_| false);
let threshold = footer.last().map_or(0, |(_, c)| *c);
return Plan {
footer,
threshold,
otherwise: Otherwise::Fixed(
CommentOwner::DocumentFooter(d),
AttachRule::DocumentFooter,
),
document: Some(d),
footer_document: Some(d),
};
}
let r = xn;
let (footer, lca) = closing(p, |a| contains(a, n));
let flow = lca
.into_iter()
.flat_map(|l| core::iter::once(l).chain(l.ancestors()))
.take_while(|a| !matches!(a.kind(), K::Document | K::Stream))
.find(|a| is_map(a.kind()) || is_seq(a.kind()))
.is_some_and(|c| is_flow(c.kind()));
if flow {
return Plan::fixed(flow_owner(n, r), AttachRule::Flow, Some(d));
}
let col = col_of(n);
let (target, opens) = target_of(n, r);
Plan {
footer,
threshold: col,
otherwise: Otherwise::Leading { target, opens, col },
document: Some(d),
footer_document: Some(d),
}
}
fn flow_owner<'t>(n: Node<'t>, root: Node<'t>) -> CommentOwner<'t> {
let mut t = n;
while t.kind() == K::FlowEntry {
match next_visible(t) {
Some(x) => t = x,
None => break,
}
}
if matches!(t.kind(), K::FlowSequenceClose | K::FlowMappingClose) {
if let Some(c) = t.parent() {
return CommentOwner::Footer(c);
}
}
CommentOwner::Leading(target_of(t, root).0)
}
fn between<'t>(
tree: &'t SyntaxTree,
p: Option<At<'t>>,
n: Option<At<'t>>,
ahead: &Ahead<'t>,
around: &Around<'t>,
) -> Plan<'t> {
let dp = p.and_then(|p| p.doc.or_else(|| around.prev_doc(p.tok)));
let dn = n.and_then(|n| n.doc.or_else(|| around.next_doc(n.tok)));
let content = p
.and_then(|p| p.doc.and(p.child))
.is_some_and(|xp| !is_start(xp) && xp.kind() != K::DocumentEndMarker);
let blank = p.and_then(|p| p.doc.and(p.child)).is_some_and(is_start);
let dn_start = dn.is_some_and(has_start);
let mut plan = match (dn, dp) {
(Some(e), _) if dn_start => Plan::header(e, AttachRule::HeaderBeforeStart),
(Some(e), _) => match n {
Some(At {
tok,
doc: Some(_),
child: Some(xn),
}) if is_item(xn.kind()) && !empty(xn) => header_plan(e, xn, tok, ahead),
_ => Plan::header(e, AttachRule::HeaderBlankLine),
},
(None, Some(i)) if blank => Plan::header(i, AttachRule::HeaderBlankLine),
(None, Some(i)) => Plan::fixed(
CommentOwner::DocumentFooter(i),
AttachRule::DocumentFooter,
Some(i),
),
(None, None) => Plan::fixed(
CommentOwner::DocumentHeader(tree.root()),
AttachRule::HeaderBlankLine,
None,
),
};
if content && !dn_start {
if let Some(p) = p {
let (footer, _) = closing(p.tok, |_| false);
plan.threshold = footer.last().map_or(0, |(_, c)| *c);
plan.footer = footer;
plan.footer_document = dp;
}
}
plan
}
#[derive(Clone, Copy)]
struct Floor<'t> {
rank: usize,
attachment: Attachment<'t>,
}
fn decide<'t>(
plan: &Plan<'t>,
c: Node<'t>,
col: usize,
blank: usize,
floor: &mut Option<Floor<'t>>,
) -> Attachment<'t> {
let (a, rank) = decide_one(plan, c, col, blank);
if let Some(f) = *floor {
if rank < f.rank {
return Attachment {
owner: f.attachment.owner,
rule: AttachRule::RunOrder,
blank_lines_before: blank,
document: f.attachment.document,
};
}
}
*floor = Some(Floor {
rank,
attachment: a,
});
a
}
fn decide_one<'t>(
plan: &Plan<'t>,
c: Node<'t>,
col: usize,
blank: usize,
) -> (Attachment<'t>, usize) {
let done = |owner, rule, document| Attachment {
owner,
rule,
blank_lines_before: blank,
document,
};
let outer = plan.footer.len();
let i = own_rank(plan, col);
if i < outer {
if let Some((k, _)) = plan.footer.get(i) {
let a = done(
CommentOwner::Footer(*k),
AttachRule::CollectionFooter,
plan.footer_document,
);
return (a, i);
}
}
let a = match plan.otherwise {
Otherwise::Fixed(owner, rule) => done(owner, rule, plan.document),
Otherwise::Header {
doc,
target,
last_blank,
} => {
if last_blank.is_some_and(|b| b > c.span().start) {
done(
CommentOwner::DocumentHeader(doc),
AttachRule::HeaderBlankLine,
Some(doc),
)
} else {
done(
CommentOwner::Leading(target),
AttachRule::FirstNodeLeading,
Some(doc),
)
}
}
Otherwise::Leading {
target,
opens,
col: n,
} => {
let rule = if col < n {
AttachRule::ShallowLeading
} else {
match opens {
Opens::Entry | Opens::Node => AttachRule::Leading,
Opens::ExplicitValue => AttachRule::ExplicitValue,
Opens::Inside => AttachRule::Inside,
}
};
done(CommentOwner::Leading(target), rule, plan.document)
}
};
(a, outer)
}
fn own_rank(plan: &Plan<'_>, col: usize) -> usize {
let outer = plan.footer.len();
if col > plan.threshold && outer > 0 {
plan.footer
.partition_point(|(_, kc)| *kc > col)
.min(outer.saturating_sub(1))
} else {
outer
}
}
fn cut_below(plan: &Plan<'_>, k: usize) -> Option<u32> {
let big = plan
.footer
.iter()
.map(|(_, c)| *c)
.chain(core::iter::once(plan.threshold))
.max()
.unwrap_or(0)
.checked_add(1)?;
let (mut lo, mut hi) = (0usize, big);
while lo < hi {
let mid = lo.saturating_add(hi.saturating_sub(lo) / 2);
if own_rank(plan, mid) < k {
hi = mid;
} else {
lo = mid.saturating_add(1);
}
}
u32::try_from(lo).ok()
}
fn cols_fit(plan: &Plan<'_>) -> bool {
let limit = col_limit();
let fits = |c: usize| c < limit;
fits(plan.threshold) && plan.footer.iter().all(|(_, c)| fits(*c))
}
#[cfg(not(test))]
const fn col_limit() -> usize {
(u32::MAX / 2) as usize
}
#[cfg(test)]
fn col_limit() -> usize {
tests::COL_LIMIT.with(core::cell::Cell::get)
}
#[derive(Clone, Copy)]
enum Want {
Attachment,
Document,
}
enum Decided<'t> {
Attachment(Attachment<'t>),
Document(Option<Node<'t>>),
}
#[cfg(test)]
mod tests {
#![allow(
clippy::unwrap_used,
clippy::indexing_slicing,
clippy::arithmetic_side_effects
)]
use super::*;
use core::cell::Cell;
std::thread_local! {
pub(super) static COL_LIMIT: Cell<usize> = const { Cell::new((u32::MAX / 2) as usize) };
}
fn trees() -> Vec<SyntaxTree> {
let mut out = Vec::new();
for depth in 1..5usize {
let mut s = String::new();
for i in 0..depth {
s.push_str(&format!("{}k{i}:\n", " ".repeat(2 * i)));
}
s.push_str(&format!("{}leaf: 1\n", " ".repeat(2 * depth)));
for i in 0..90 {
s.push_str(&" ".repeat((2 * depth + 1).saturating_sub((i * 7) % 5 + i / 30)));
s.push_str(&format!("# c{i}\n"));
if i % 17 == 4 {
s.push('\n');
}
}
if depth % 2 == 0 {
s.push_str("z: 1\n");
} else {
s.push_str("...\n# s\n...\n# h\n--- y\n");
}
let mut t = SyntaxTree::parse(s.as_str());
out.push(t.clone());
let comments: Vec<_> = t
.root()
.descendants()
.filter(|n| n.kind() == K::Comment)
.map(Node::id)
.collect();
for (k, c) in comments.iter().enumerate().filter(|(k, _)| k % 5 == 1) {
let _ = t.replace_token(*c, &format!("# r{k}"));
}
out.push(t);
}
out
}
#[test]
fn wide_column_fallbacks_decide_as_the_index() {
let mut with_footers = 0;
for t in trees() {
let all = t.comment_attachments();
let blocks: Vec<_> = t
.root()
.descendants()
.filter(|x| is_block(x.kind()))
.collect();
let footers: Vec<_> = blocks.iter().map(|b| t.last_footer_comment(*b)).collect();
with_footers += usize::from(footers.iter().any(Option::is_some));
for limit in [0usize, 1, 2, 3, 5, 8] {
COL_LIMIT.with(|c| c.set(limit));
for (c, a) in &all {
assert_eq!(t.comment_attachment(*c).as_ref(), Some(a), "{limit}");
assert_eq!(t.comment_document(*c), Some(a.document()), "{limit}");
}
for (b, want) in blocks.iter().zip(&footers) {
assert_eq!(t.last_footer_comment(*b), *want, "{limit}");
}
}
COL_LIMIT.with(|c| c.set((u32::MAX / 2) as usize));
}
assert!(with_footers >= 4, "{with_footers}");
}
}