Skip to main content

oneyaml_syntax/tree/
attach.rs

1//! Comment attachment: the one owner of every comment, decided by
2//! the numbered rules of `docs/comment-attachment.md` (the normative
3//! rulebook; each [`AttachRule`] names one of its rules).
4//!
5//! **One tree.** Owners are read from the syntax tree's own
6//! tokens: comments are [`SyntaxKind::Comment`](super::SyntaxKind::Comment) tokens, lines end at
7//! [`SyntaxKind::LineBreak`](super::SyntaxKind::LineBreak) tokens or at a block scalar's text (which
8//! ends with its line break), and columns are counted over the tokens of
9//! a line. There is no second scanner over the source text, so an edited
10//! tree is read exactly as a parsed one.
11//!
12//! **On demand.** No owner is computed or stored while parsing:
13//! [`SyntaxTree::comment_attachment`] decides one comment in
14//! O(depth + log + its line) from the comment-run index (`runs.rs`:
15//! per-arena facts computed with the arena, and treap sums; P and N,
16//! the documents around a stray `...`, siblings past comment lines, and
17//! rule 13's floor without walking the run), plus, for a header owner, the
18//! blank lines after it in its run; [`SyntaxTree::comment_attachments`]
19//! and [`SyntaxTree::document_comment_attachments`] decide every comment
20//! in one O(n) pass that computes each run's context once (the run's
21//! neighbours, the block collections that close in it, its document) and
22//! shares it among the run's comments. No decision scans a document's
23//! children: it reads the kinds of the neighbouring tokens and of the
24//! document children holding them. The passes never scan the
25//! stream's elements per comment either (they table the documents around
26//! each stream-level element once). Both paths call the same decision
27//! code, so they always agree (pinned by tests over the yaml-test-suite
28//! corpus, a differential fuzz, and `tests/comment_index.rs` for long
29//! runs and edited trees).
30//!
31//! **No recursion.** Every walk here is a loop over tokens or ancestors;
32//! nothing recurses.
33
34use super::{Node, SyntaxKind as K, SyntaxTree};
35
36/// The numbered rule of `docs/comment-attachment.md` that decided a
37/// comment's owner. Rule numbers are stable once published (stability policy);
38/// rule 8 (blank-line counts) decides no owner and has
39/// no variant.
40#[non_exhaustive]
41#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
42pub enum AttachRule {
43    /// Rule 1: an own-line comment before the document's `---` (directives
44    /// included) is document header.
45    HeaderBeforeStart,
46    /// Rule 2: an own-line comment before the root with a blank line after
47    /// it (before the root), or in a document without visible content, is
48    /// document header.
49    HeaderBlankLine,
50    /// Rule 3: an own-line comment before the root with no blank line
51    /// after it leads the first entry, item, or node the root opens with.
52    FirstNodeLeading,
53    /// Rule 4: an own-line comment above a node (blank lines between
54    /// allowed), at or right of its column, leads that node (for a key or
55    /// `-`, the entry or item).
56    Leading,
57    /// Rule 5: a comment after content on its line trails the entry or
58    /// item that content belongs to (or the root, or the document marker's
59    /// header or footer).
60    Trailing,
61    /// Rule 6: an own-line comment after a block collection's last child,
62    /// right of the column of what follows, is that collection's footer.
63    CollectionFooter,
64    /// Rule 7: an own-line comment after the root at root column (or after
65    /// the last document) is document footer.
66    DocumentFooter,
67    /// Rule 9: an own-line comment inside a flow collection leads the next
68    /// item, or is the collection's footer before its closing bracket.
69    Flow,
70    /// Rule 10: an own-line comment left of the column of the block node
71    /// that follows it still leads that node.
72    ShallowLeading,
73    /// Rule 11: an own-line comment directly above the `:` of an explicit
74    /// (`? `) entry leads that entry's value.
75    ExplicitValue,
76    /// Rule 12: an own-line comment followed by a property, a block scalar
77    /// header, or error bytes inside a node leads the innermost node
78    /// holding them.
79    Inside,
80    /// Rule 13: within one run of comment lines owners only move outward;
81    /// a comment whose other rules would give it a deeper owner than an
82    /// earlier comment of its run takes the owner of the comment before it.
83    RunOrder,
84}
85
86impl AttachRule {
87    /// The rule's number in `docs/comment-attachment.md` (stable).
88    #[must_use]
89    pub const fn number(self) -> u8 {
90        match self {
91            Self::HeaderBeforeStart => 1,
92            Self::HeaderBlankLine => 2,
93            Self::FirstNodeLeading => 3,
94            Self::Leading => 4,
95            Self::Trailing => 5,
96            Self::CollectionFooter => 6,
97            Self::DocumentFooter => 7,
98            Self::Flow => 9,
99            Self::ShallowLeading => 10,
100            Self::ExplicitValue => 11,
101            Self::Inside => 12,
102            Self::RunOrder => 13,
103        }
104    }
105}
106
107/// Who owns a comment.
108///
109/// A mapping **entry** is named by its key node, a sequence **item** by
110/// its node; a key's leading and trailing comments are its entry's.
111#[non_exhaustive]
112#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
113pub enum CommentOwner<'t> {
114    /// The header of this [`SyntaxKind::Document`](super::SyntaxKind::Document) (the
115    /// [`SyntaxKind::Stream`](super::SyntaxKind::Stream) when the input has no document).
116    DocumentHeader(Node<'t>),
117    /// The footer of this [`SyntaxKind::Document`](super::SyntaxKind::Document).
118    DocumentFooter(Node<'t>),
119    /// A leading comment of this entry (key), item, or node.
120    Leading(Node<'t>),
121    /// The trailing (same-line) comment of this entry (key), item, or
122    /// node.
123    Trailing(Node<'t>),
124    /// The footer of this collection.
125    Footer(Node<'t>),
126}
127
128/// A comment's owner, the rule that decided it, and the blank lines above
129/// it (rule 8 of the comment rulebook).
130#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
131pub struct Attachment<'t> {
132    owner: CommentOwner<'t>,
133    rule: AttachRule,
134    blank_lines_before: usize,
135    document: Option<Node<'t>>,
136}
137
138impl<'t> Attachment<'t> {
139    /// The owner.
140    #[must_use]
141    pub const fn owner(&self) -> CommentOwner<'t> {
142        self.owner
143    }
144
145    /// The rule that decided the owner.
146    #[must_use]
147    pub const fn rule(&self) -> AttachRule {
148        self.rule
149    }
150
151    /// Blank lines between the previous non-blank line and the comment's
152    /// line (rule 8); 0 for a same-line comment. Blank lines that are a
153    /// block scalar's content (kept by `|+`) are not counted.
154    #[must_use]
155    pub const fn blank_lines_before(&self) -> usize {
156        self.blank_lines_before
157    }
158
159    /// The [`SyntaxKind::Document`](super::SyntaxKind::Document) the comment belongs to; `None` only
160    /// when the input has no document.
161    #[must_use]
162    pub const fn document(&self) -> Option<Node<'t>> {
163        self.document
164    }
165}
166
167impl SyntaxTree {
168    /// The attachment of `comment`, a [`SyntaxKind::Comment`](super::SyntaxKind::Comment)
169    /// token of this tree; `None` for any other element.
170    ///
171    /// Cost: O(depth + log + its line) from the comment-run
172    /// index, plus, for a comment whose owner is a document header or the
173    /// first node (rules 2/3), the blank lines and comments after it in its
174    /// run. Columns beyond `u32` and recovered input with both header and
175    /// footer owners in one run replay the run (O(the run)).
176    #[must_use]
177    pub fn comment_attachment<'t>(&'t self, comment: Node<'t>) -> Option<Attachment<'t>> {
178        if comment.kind() != K::Comment || !core::ptr::eq(comment.tree(), self) {
179            return None;
180        }
181        let around = Around::Scan;
182        let a = match line_of(comment) {
183            Line::Same(p) => same_line(locate(p), &around),
184            Line::Own(end) => match self.decide_indexed(comment, end, Want::Attachment) {
185                Some(Decided::Attachment(a)) => a,
186                _ => self.replay(comment)?,
187            },
188        };
189        Some(a)
190    }
191
192    /// The document [`SyntaxTree::comment_attachment`] gives `comment`
193    /// ([`Attachment::document`]): the outer `None` when `comment` is not a
194    /// [`SyntaxKind::Comment`](super::SyntaxKind::Comment) token of this
195    /// tree. O(depth + log) with the comment-run index,
196    /// never the run around it or the stream-level elements between it
197    /// and its neighbouring documents (the rules' document never depends
198    /// on the blank lines after a comment, which its header owner may).
199    #[must_use]
200    pub fn comment_document<'t>(&'t self, comment: Node<'t>) -> Option<Option<Node<'t>>> {
201        if comment.kind() != K::Comment || !core::ptr::eq(comment.tree(), self) {
202            return None;
203        }
204        match line_of(comment) {
205            Line::Same(p) => Some(same_line(locate(p), &Around::Scan).document),
206            Line::Own(end) => match self.decide_indexed(comment, end, Want::Document) {
207                Some(Decided::Document(d)) => Some(d),
208                Some(Decided::Attachment(a)) => Some(a.document),
209                None => self.replay(comment).map(|a| a.document),
210            },
211        }
212    }
213
214    /// The last content token before `n` in source order (a token with
215    /// bytes that is not trivia: what the rulebook calls content; comments,
216    /// white space, line breaks and zero-width tokens are skipped); `None`
217    /// at the start of the text or for another tree's element.
218    /// O(log) with the comment-run index, never the comment lines
219    /// before `n`.
220    #[must_use]
221    pub fn prev_content_token<'t>(&'t self, n: Node<'t>) -> Option<Node<'t>> {
222        core::ptr::eq(n.tree(), self)
223            .then(|| prev_visible(n))
224            .flatten()
225    }
226
227    /// The first content token after `n` in source order (inside `n` for a
228    /// node with content), as [`SyntaxTree::prev_content_token`].
229    #[must_use]
230    pub fn next_content_token<'t>(&'t self, n: Node<'t>) -> Option<Node<'t>> {
231        core::ptr::eq(n.tree(), self)
232            .then(|| next_visible(n))
233            .flatten()
234    }
235
236    /// The last own-line comment of the run after block collection
237    /// `collection` (the comment lines between its last content token and
238    /// the next one) whose owner is the footer of `collection` or of a
239    /// collection whose span lies within its span (rules 6 and 13: those
240    /// comments open the run, each owner's together); `None` when there is
241    /// none, or `collection` is not a block collection of this tree.
242    ///
243    /// O(depth + log) with the comment-run index, plus the
244    /// blank lines before the next comment, never the footer's length:
245    /// what `oneyaml`'s `Document::push_footer` appends after.
246    #[must_use]
247    pub fn last_footer_comment<'t>(&'t self, collection: Node<'t>) -> Option<Node<'t>> {
248        if !is_block(collection.kind()) || !core::ptr::eq(collection.tree(), self) {
249            return None;
250        }
251        let p = last_visible_in(collection)?;
252        let n = next_visible(p);
253        let around = Around::Scan;
254        let ahead = Ahead {
255            next: n,
256            last_blank: None,
257        };
258        let plan = make_plan(self, Some(locate(p)), &ahead, &around);
259        if !cols_fit(&plan) {
260            return self.last_footer_comment_walk(collection, p, &plan);
261        }
262        let i = plan.footer.iter().position(|(k, _)| *k == collection)?;
263        let span = collection.span();
264        let within = |y: Node<'_>| {
265            let s = y.span();
266            span.start <= s.start && s.end <= span.end
267        };
268        // The deepest rank whose owner lies within `collection` (ranks up
269        // to `i` are collections inside it).
270        let mut j = i;
271        while plan
272            .footer
273            .get(j.saturating_add(1))
274            .is_some_and(|(k, _)| within(*k))
275        {
276            j = j.saturating_add(1);
277        }
278        // The first own-line comment ranked deeper than `j` ends them.
279        let cut = cut_below(&plan, j.saturating_add(1))?;
280        let stop = self.run_hit(p.slot(), cut);
281        let stop = stop.and_then(|s| self.node_at_slot(s));
282        // Back over the trivia before it (no comment lies between).
283        let mut at = match stop {
284            Some(s) => prev_token(s),
285            None => last_token(self),
286        };
287        while let Some(t) = at {
288            if t == p || visible(t) {
289                return None;
290            }
291            if t.kind() == K::Comment {
292                return matches!(line_of(t), Line::Own(_)).then_some(t);
293            }
294            at = prev_token(t);
295        }
296        None
297    }
298
299    /// [`SyntaxTree::last_footer_comment`] by deciding the run (columns
300    /// beyond the index's range).
301    fn last_footer_comment_walk<'t>(
302        &'t self,
303        collection: Node<'t>,
304        p: Node<'t>,
305        plan: &Plan<'t>,
306    ) -> Option<Node<'t>> {
307        let span = collection.span();
308        let within = |y: Node<'_>| {
309            let s = y.span();
310            span.start <= s.start && s.end <= span.end
311        };
312        let mut floor = None;
313        let mut last = None;
314        let mut at = next_token(p);
315        while let Some(t) = at {
316            if visible(t) {
317                break;
318            }
319            if t.kind() == K::Comment {
320                if let Line::Own(end) = line_of(t) {
321                    let a = decide(plan, t, col_of(t), blank_before(end), &mut floor);
322                    match a.owner {
323                        CommentOwner::Footer(y) if within(y) => last = Some(t),
324                        _ => break,
325                    }
326                }
327            }
328            at = next_token(t);
329        }
330        last
331    }
332
333    /// The attachment (or only the document, `want`) of own-line comment
334    /// `c` (the previous line ending with `end`) from the comment-run
335    /// index: P and N found in O(log), and rule 13's floor —
336    /// the deepest rank among the run's comments before `c`, which is the
337    /// rank of the smallest column among them — found by asking for the
338    /// first comment below each rank's column (O(log footer) questions).
339    /// `None` where the index does not decide: a header owner whose run
340    /// also has footer ranks (only recovered input has them), columns
341    /// beyond `u32`.
342    fn decide_indexed<'t>(
343        &'t self,
344        c: Node<'t>,
345        end: Option<Node<'t>>,
346        want: Want,
347    ) -> Option<Decided<'t>> {
348        let p = prev_visible(c);
349        let n = next_visible(c);
350        let around = Around::Scan;
351        let ahead = Ahead {
352            next: n,
353            last_blank: None,
354        };
355        let mut plan = make_plan(self, p.map(locate), &ahead, &around);
356        if !cols_fit(&plan) {
357            return None;
358        }
359        let outer = plan.footer.len();
360        let header = matches!(plan.otherwise, Otherwise::Header { .. });
361        let col = col_of(c);
362        let floor = self.floor_rank(&plan, p, c)?;
363        if let Want::Document = want {
364            let rank = floor.max(own_rank(&plan, col));
365            let doc = if rank < outer {
366                plan.footer_document
367            } else {
368                plan.document
369            };
370            return Some(Decided::Document(doc));
371        }
372        if header && outer > 0 {
373            return None;
374        }
375        if let Otherwise::Header { last_blank, .. } = &mut plan.otherwise {
376            // Only the blank lines after `c` matter to it (O(the rest of
377            // the run)); the run's own decision reads them from its first
378            // comment on, which finds the same ones after `c`.
379            *last_blank = scan_ahead(c).last_blank;
380        }
381        let blank = blank_before(end);
382        let (a, rank) = decide_one(&plan, c, col, blank);
383        if floor <= rank {
384            return Some(Decided::Attachment(a));
385        }
386        // Rule 13: the owner of the comment that set the floor.
387        let (owner, document) = match plan.footer.get(floor) {
388            Some((k, _)) => (CommentOwner::Footer(*k), plan.footer_document),
389            None => match plan.otherwise {
390                Otherwise::Fixed(o, _) => (o, plan.document),
391                Otherwise::Leading { target, .. } => (CommentOwner::Leading(target), plan.document),
392                Otherwise::Header { .. } => {
393                    // An invariant, never a panic: not
394                    // reached. A header plan with footer ranks returned
395                    // `None` above (`header && outer > 0`); without them
396                    // (`outer == 0`) `floor_rank` is 0, never above `rank`.
397                    // In release the run is replayed (`None`), the decision
398                    // the index stands in for, never a guess.
399                    debug_assert!(false, "rule 13 above a header owner");
400                    return None;
401                }
402            },
403        };
404        Some(Decided::Attachment(Attachment {
405            owner,
406            rule: AttachRule::RunOrder,
407            blank_lines_before: blank,
408            document,
409        }))
410    }
411
412    /// Rule 13's floor at own-line comment `c` after content token `p`:
413    /// the deepest rank of the run's own-line comments before `c` (0 for
414    /// none). Ranks are non-increasing in the column, so "rank at least
415    /// k" is "column below `cut_below(k)`", and the floor is the largest
416    /// k for which the index finds such a comment before `c`. O(log
417    /// footer) index questions.
418    fn floor_rank(&self, plan: &Plan<'_>, p: Option<Node<'_>>, c: Node<'_>) -> Option<usize> {
419        let outer = plan.footer.len();
420        if outer == 0 {
421            return Some(0);
422        }
423        let from = p.map_or(0, Node::slot);
424        let at = c.preorder_index();
425        let exists = |k: usize| -> Option<bool> {
426            let cut = cut_below(plan, k)?;
427            Some(
428                self.run_hit(from, cut)
429                    .and_then(|s| self.node_at_slot(s))
430                    .is_some_and(|h| h.preorder_index() < at),
431            )
432        };
433        // The largest k in 0..=outer with `exists(k)` (true at 0).
434        let (mut lo, mut hi) = (0usize, outer);
435        while lo < hi {
436            let mid = lo.saturating_add(hi.saturating_sub(lo).saturating_add(1) / 2);
437            if exists(mid)? {
438                lo = mid;
439            } else {
440                hi = mid.saturating_sub(1);
441            }
442        }
443        Some(lo)
444    }
445
446    /// [`SyntaxTree::comment_attachment`] of own-line `comment` by
447    /// replaying its run (the decision the index stands in for).
448    fn replay<'t>(&'t self, comment: Node<'t>) -> Option<Attachment<'t>> {
449        let around = Around::Scan;
450        // The run's comments up to this one, and P before them: the
451        // run is decided in order, as the pass decides it (rule 13).
452        let mut run = Vec::new();
453        let mut p = None;
454        let mut at = prev_token(comment);
455        while let Some(t) = at {
456            if visible(t) {
457                p = Some(t);
458                break;
459            }
460            if t.kind() == K::Comment {
461                run.push(t);
462            }
463            at = prev_token(t);
464        }
465        run.reverse();
466        run.push(comment);
467        let own: Vec<(Node<'t>, Option<Node<'t>>)> = run
468            .into_iter()
469            .filter_map(|r| match line_of(r) {
470                Line::Own(end) => Some((r, end)),
471                Line::Same(_) => None,
472            })
473            .collect();
474        let first = own.first().map_or(comment, |(r, _)| *r);
475        let plan = make_plan(self, p.map(locate), &scan_ahead(first), &around);
476        let mut floor = None;
477        let mut last = None;
478        for (r, end) in own {
479            last = Some(decide(&plan, r, col_of(r), blank_before(end), &mut floor));
480        }
481        last
482    }
483
484    /// The attachments of every comment of the **run** holding `comment` (a
485    /// [`SyntaxKind::Comment`](super::SyntaxKind::Comment) token of this
486    /// tree): the comments between the content token before it and the
487    /// content token after it, in source order, decided as
488    /// [`SyntaxTree::comment_attachments`] decides them (the same code).
489    /// Empty for any other element.
490    ///
491    /// The comments of one owner are
492    /// read, and a comment edit is checked, one run at a time, in
493    /// O(depth + the run + its lines); next to stray `...` markers between
494    /// documents, the documents around the run are found in O(log) with
495    /// the comment-run index, never by walking the stream-level
496    /// elements between them.
497    #[must_use]
498    pub fn comment_run_attachments<'t>(
499        &'t self,
500        comment: Node<'t>,
501    ) -> Vec<(Node<'t>, Attachment<'t>)> {
502        if comment.kind() != K::Comment || !core::ptr::eq(comment.tree(), self) {
503            return Vec::new();
504        }
505        // The run: back to P, then on to N (loops over tokens).
506        let mut run = Vec::new();
507        let mut p = None;
508        let mut at = prev_token(comment);
509        while let Some(t) = at {
510            if visible(t) {
511                p = Some(t);
512                break;
513            }
514            if t.kind() == K::Comment {
515                run.push(t);
516            }
517            at = prev_token(t);
518        }
519        run.reverse();
520        run.push(comment);
521        let mut at = next_token(comment);
522        while let Some(t) = at {
523            if visible(t) {
524                break;
525            }
526            if t.kind() == K::Comment {
527                run.push(t);
528            }
529            at = next_token(t);
530        }
531        let around = Around::Scan;
532        let from = p.map(locate);
533        let mut plan: Option<Plan<'t>> = None;
534        let mut floor = None;
535        let mut out = Vec::with_capacity(run.len());
536        for r in run {
537            let a = match line_of(r) {
538                Line::Same(q) => same_line(locate(q), &around),
539                Line::Own(end) => {
540                    // The plan is made at the run's first own-line comment,
541                    // as the pass makes it.
542                    let plan =
543                        plan.get_or_insert_with(|| make_plan(self, from, &scan_ahead(r), &around));
544                    decide(plan, r, col_of(r), blank_before(end), &mut floor)
545                }
546            };
547            out.push((r, a));
548        }
549        out
550    }
551
552    /// Every comment of the stream-level elements strictly between
553    /// documents `before` and `after` (`None`: the start, the end of the
554    /// stream), with their attachments, in source order, decided as
555    /// [`SyntaxTree::comment_attachments`] decides them (the same pass).
556    /// Empty when `before` or `after` is not a document of this tree, or
557    /// `after` does not follow `before`.
558    ///
559    /// The documents around the stretch are found once
560    /// for all of its runs, so a stretch of N stray `...` markers and
561    /// comments costs O(N), where deciding its N runs one at a time
562    /// ([`SyntaxTree::comment_run_attachments`]) walks the stretch for
563    /// each, O(N²).
564    #[must_use]
565    pub fn comment_attachments_between<'t>(
566        &'t self,
567        before: Option<Node<'t>>,
568        after: Option<Node<'t>>,
569    ) -> Vec<(Node<'t>, Attachment<'t>)> {
570        let is_doc = |d: Option<Node<'t>>| {
571            d.is_none_or(|d| {
572                d.kind() == K::Document
573                    && core::ptr::eq(d.tree(), self)
574                    && d.parent().is_some_and(|p| p.kind() == K::Stream)
575            })
576        };
577        if !is_doc(before) || !is_doc(after) {
578            return Vec::new();
579        }
580        let mut tops = Vec::new();
581        let mut at = match before {
582            Some(b) => b.next_sibling(),
583            None => self.root().first_child(),
584        };
585        // A loop over the stream's children.
586        while let Some(n) = at {
587            if Some(n) == after {
588                break;
589            }
590            tops.push(n);
591            at = n.next_sibling();
592        }
593        if at != after {
594            return Vec::new();
595        }
596        let start = tops.first().and_then(|f| prev_visible(*f)).map(locate);
597        pass(self, &tops, start, before, after, None)
598    }
599
600    /// Every comment of the tree with its attachment, in source order. One
601    /// O(n) pass (see the module docs); nothing is kept afterwards.
602    #[must_use]
603    pub fn comment_attachments(&self) -> Vec<(Node<'_>, Attachment<'_>)> {
604        let tops: Vec<Node<'_>> = self.root().children().collect();
605        pass(self, &tops, None, None, None, None)
606    }
607
608    /// The comments that belong to `document` (a
609    /// [`SyntaxKind::Document`](super::SyntaxKind::Document) of this tree),
610    /// with their attachments, in source order: its own and those between
611    /// it and its neighbouring documents that the rules give it. O(the
612    /// document and the stream-level elements around it), never the rest
613    /// of the stream; empty for any other element.
614    #[must_use]
615    pub fn document_comment_attachments<'t>(
616        &'t self,
617        document: Node<'t>,
618    ) -> Vec<(Node<'t>, Attachment<'t>)> {
619        if document.kind() != K::Document || !core::ptr::eq(document.tree(), self) {
620            return Vec::new();
621        }
622        // From the element after the previous document to the element
623        // before the next one: a comment outside that range belongs to
624        // another document.
625        let mut first = document;
626        let mut before = None;
627        while let Some(p) = first.prev_sibling() {
628            if p.kind() == K::Document {
629                before = Some(p);
630                break;
631            }
632            first = p;
633        }
634        let start = prev_visible(first).map(locate);
635        let mut tops = Vec::new();
636        let mut at = Some(first);
637        let mut after = None;
638        while let Some(n) = at {
639            if n.kind() == K::Document && n != document {
640                after = Some(n);
641                break;
642            }
643            tops.push(n);
644            at = n.next_sibling();
645        }
646        pass(self, &tops, start, before, after, Some(document))
647    }
648}
649
650/// The trivia tokens of document `doc` after its content token `p` (its
651/// last one), or before its first content token when `p` is `None`: in
652/// recovered input a document can end or begin with them, and their
653/// comments can belong to the neighbouring document. O(those
654/// tokens).
655fn edge_tokens<'t>(doc: Node<'t>, p: Option<Node<'t>>) -> Vec<Node<'t>> {
656    let mut out = Vec::new();
657    let mut at = match p {
658        Some(p) => next_token(p),
659        None => Some(first_token(doc)).filter(|t| t.is_token()),
660    };
661    while let Some(t) = at {
662        if visible(t) || !contains(doc, t) {
663            break;
664        }
665        out.push(t);
666        at = next_token(t);
667    }
668    out
669}
670
671/// A content token and where it sits: its document and the document's
672/// child that holds it (`None`, `None` at stream level).
673#[derive(Clone, Copy)]
674struct At<'t> {
675    tok: Node<'t>,
676    doc: Option<Node<'t>>,
677    child: Option<Node<'t>>,
678}
679
680/// Where `tok` sits (O(depth): a climb to its document).
681fn locate(tok: Node<'_>) -> At<'_> {
682    let mut below = tok;
683    for a in tok.ancestors() {
684        if a.kind() == K::Document {
685            return At {
686                tok,
687                doc: Some(a),
688                child: Some(below),
689            };
690        }
691        below = a;
692    }
693    At {
694        tok,
695        doc: None,
696        child: None,
697    }
698}
699
700/// The documents around a stream-level element (a stray `...` or an
701/// error region between documents).
702enum Around<'t> {
703    /// Found for one comment from the comment-run index (`runs.rs`:
704    /// O(log), never a walk over the stream's elements).
705    Scan,
706    /// Known to the pass for the stream-level element it is in (a
707    /// pass never walks siblings per comment).
708    Known {
709        prev: Option<Node<'t>>,
710        next: Option<Node<'t>>,
711    },
712}
713
714impl<'t> Around<'t> {
715    /// The last document before the stream-level element holding `x` (a
716    /// token outside every document, possibly inside a stream-level error
717    /// region).
718    fn prev_doc(&self, x: Node<'t>) -> Option<Node<'t>> {
719        match self {
720            Self::Known { prev, .. } => *prev,
721            // From the index (O(log)), never a walk over the
722            // stream's elements; the last document before `x` is the last
723            // one before the stream-level element holding it.
724            Self::Scan => x.tree().document_before(x.slot()),
725        }
726    }
727
728    /// The first document after the stream-level element holding `x`.
729    fn next_doc(&self, x: Node<'t>) -> Option<Node<'t>> {
730        match self {
731            Self::Known { next, .. } => *next,
732            Self::Scan => x.tree().document_after(x.slot()),
733        }
734    }
735}
736
737/// The attachments of the comments under `tops` (consecutive
738/// stream-level elements), from content token `start` on; `before` and
739/// `after` are the documents right outside `tops`; only those of document
740/// `want` when given. One pass (O(n)): each content token's
741/// document and document child are tracked, not climbed to; a run's
742/// [`Plan`] is made at its first own-line comment and shared by the rest;
743/// the documents around each stream-level element are tabled once.
744fn pass<'t>(
745    tree: &'t SyntaxTree,
746    tops: &[Node<'t>],
747    start: Option<At<'t>>,
748    before: Option<Node<'t>>,
749    after: Option<Node<'t>>,
750    want: Option<Node<'t>>,
751) -> Vec<(Node<'t>, Attachment<'t>)> {
752    let is_doc = |n: &Node<'t>| n.kind() == K::Document;
753    // The documents strictly before and after each top.
754    let mut prevs = Vec::with_capacity(tops.len());
755    let mut last = before;
756    for t in tops {
757        prevs.push(last);
758        if is_doc(t) {
759            last = Some(*t);
760        }
761    }
762    let mut nexts = vec![None; tops.len()];
763    let mut next = after;
764    for (t, slot) in tops.iter().zip(nexts.iter_mut()).rev() {
765        *slot = next;
766        if is_doc(t) {
767            next = Some(*t);
768        }
769    }
770    // Only for one document's pass (`want`): the trivia at the end of the
771    // document before and at the start of the document after the tops.
772    let tail = match (want, before, start) {
773        (Some(_), Some(b), Some(p)) if p.doc == Some(b) => edge_tokens(b, Some(p.tok)),
774        _ => Vec::new(),
775    };
776    let head = match (want, after) {
777        (Some(_), Some(a)) => edge_tokens(a, None),
778        _ => Vec::new(),
779    };
780    let mut out = Vec::new();
781    let mut p = start;
782    let mut plan: Option<Plan<'t>> = None;
783    let mut floor: Option<Floor<'t>> = None;
784    let mut step =
785        |t: Node<'t>, doc: Option<Node<'t>>, child: Option<Node<'t>>, around: &Around<'t>| {
786            if t.kind() == K::Comment {
787                let a = match line_of(t) {
788                    Line::Same(q) => {
789                        let at = match p {
790                            Some(x) if x.tok == q => x,
791                            _ => locate(q),
792                        };
793                        same_line(at, around)
794                    }
795                    Line::Own(end) => {
796                        let plan =
797                            plan.get_or_insert_with(|| make_plan(tree, p, &scan_ahead(t), around));
798                        decide(plan, t, col_of(t), blank_before(end), &mut floor)
799                    }
800                };
801                if want.is_none_or(|w| a.document == Some(w)) {
802                    out.push((t, a));
803                }
804            } else if visible(t) {
805                p = Some(At { tok: t, doc, child });
806                plan = None;
807                floor = None;
808            }
809        };
810    // The tail of `before`: P is its last content token, and the first
811    // document after it is the first top that is one (or `after`).
812    let first_next = tops.iter().copied().find(is_doc).or(after);
813    let tail_around = Around::Known {
814        prev: None,
815        next: first_next,
816    };
817    for t in tail {
818        step(t, before, None, &tail_around);
819    }
820    for ((top, prev), next) in tops.iter().zip(prevs).zip(nexts) {
821        let around = Around::Known { prev, next };
822        if is_doc(top) {
823            // Flat preorder loops, one per child of the document.
824            for ch in top.children() {
825                for t in ch.descendants() {
826                    step(t, Some(*top), Some(ch), &around);
827                }
828            }
829        } else {
830            for t in top.descendants() {
831                step(t, None, None, &around);
832            }
833        }
834    }
835    let last_doc = tops.iter().copied().rev().find(is_doc).or(before);
836    let head_around = Around::Known {
837        prev: last_doc,
838        next: after,
839    };
840    for t in head {
841        step(t, after, None, &head_around);
842    }
843    out
844}
845
846// ================================================================ kinds
847
848fn is_item(k: K) -> bool {
849    k.is_yaml_node() || k == K::Error
850}
851
852fn is_block(k: K) -> bool {
853    matches!(k, K::BlockMapping | K::BlockSequence)
854}
855
856fn is_map(k: K) -> bool {
857    matches!(k, K::BlockMapping | K::FlowMapping | K::FlowPair)
858}
859
860fn is_seq(k: K) -> bool {
861    matches!(k, K::BlockSequence | K::FlowSequence)
862}
863
864fn is_flow(k: K) -> bool {
865    matches!(k, K::FlowMapping | K::FlowSequence | K::FlowPair)
866}
867
868fn empty(n: Node<'_>) -> bool {
869    n.span().is_empty()
870}
871
872/// A token with bytes that is not trivia: what a line's content is made
873/// of.
874fn visible(t: Node<'_>) -> bool {
875    t.is_token() && !t.kind().is_trivia() && !empty(t)
876}
877
878/// A token that neither ends a line nor is content: white space, a byte
879/// order mark, a zero-width token.
880fn blankish(t: Node<'_>) -> bool {
881    matches!(t.kind(), K::Whitespace | K::ByteOrderMark) || (t.kind() != K::LineBreak && empty(t))
882}
883
884/// The token ends its line (a line break, or a block scalar's text).
885fn ends_line(t: Node<'_>) -> bool {
886    t.kind() == K::LineBreak || (!empty(t) && t.text().ends_with(['\n', '\r']))
887}
888
889// =========================================================== navigation
890
891fn prev_token(n: Node<'_>) -> Option<Node<'_>> {
892    let mut at = n.pred();
893    while let Some(x) = at {
894        if x.is_token() {
895            return Some(x);
896        }
897        at = x.pred();
898    }
899    None
900}
901
902fn next_token(n: Node<'_>) -> Option<Node<'_>> {
903    let mut at = n.succ();
904    while let Some(x) = at {
905        if x.is_token() {
906            return Some(x);
907        }
908        at = x.succ();
909    }
910    None
911}
912
913/// The last content token before `n` (comments, white space, line breaks,
914/// zero-width tokens skipped). From the comment-run index
915/// (`runs.rs`), O(log + `LONG_RUN`), never the run before `n`.
916fn prev_visible(n: Node<'_>) -> Option<Node<'_>> {
917    let t = n.tree();
918    t.visible_before(n.slot()).and_then(|s| t.node_at_slot(s))
919}
920
921/// The first content token after `n` in preorder (inside `n` for a node).
922/// From the comment-run index.
923fn next_visible(n: Node<'_>) -> Option<Node<'_>> {
924    let t = n.tree();
925    t.run_hit(n.slot(), 0).and_then(|s| t.node_at_slot(s))
926}
927
928/// The last content token of `n`'s subtree.
929fn last_visible_in(n: Node<'_>) -> Option<Node<'_>> {
930    let t = n.tree();
931    let leaf = t.node_at_slot(t.nav_last_leaf(n.slot())?)?;
932    let last = if visible(leaf) {
933        leaf
934    } else {
935        prev_visible(leaf)?
936    };
937    contains(n, last).then_some(last)
938}
939
940/// The tree's last token.
941fn last_token(tree: &SyntaxTree) -> Option<Node<'_>> {
942    let root = tree.root();
943    let leaf = tree.node_at_slot(tree.nav_last_leaf(root.slot())?)?;
944    if leaf.is_token() {
945        Some(leaf)
946    } else {
947        prev_token(leaf)
948    }
949}
950
951/// Own-line comment `c`'s column, `None` for a comment after content on
952/// its line (`runs.rs` reads what its arena cannot tell this way).
953pub(super) fn own_col(c: Node<'_>) -> Option<usize> {
954    match line_of(c) {
955        Line::Own(_) => Some(col_of(c)),
956        Line::Same(_) => None,
957    }
958}
959
960/// `n` lies in `a`'s subtree (or is `a`).
961fn contains(a: Node<'_>, n: Node<'_>) -> bool {
962    let ai = a.preorder_index();
963    let ni = n.preorder_index();
964    ai <= ni && ni < ai.saturating_add(a.descendants().len())
965}
966
967/// The column (characters from the line start) where token `t` starts. A
968/// byte order mark is not a column (§5.2): the parser counts columns
969/// after it, and so do the rules (a fuzz finding: rule 6 read the
970/// root of `\u{feff}k: v` as indented by one). White space before a mark
971/// still counts (the parser keeps that indentation and reports such a
972/// mark as an error).
973fn col_of(t: Node<'_>) -> usize {
974    let mut col = 0usize;
975    let mut at = prev_token(t);
976    while let Some(x) = at {
977        if x.kind() == K::ByteOrderMark {
978            at = prev_token(x);
979            continue;
980        }
981        let text = x.text();
982        if let Some(i) = text.rfind(['\n', '\r']) {
983            let tail = text.get(i.saturating_add(1)..).unwrap_or("");
984            return col.saturating_add(tail.chars().count());
985        }
986        col = col.saturating_add(text.chars().count());
987        at = prev_token(x);
988    }
989    col
990}
991
992/// The first token of `n`'s subtree (`n` itself for a token).
993fn first_token(n: Node<'_>) -> Node<'_> {
994    let mut at = n;
995    while let Some(c) = at.first_child() {
996        at = c;
997    }
998    at
999}
1000
1001/// The token where a block collection's first entry starts (its own
1002/// properties skipped): what its column is read from.
1003fn coll_start(c: Node<'_>) -> Node<'_> {
1004    let first = c
1005        .children()
1006        .find(|x| !x.kind().is_trivia() && !matches!(x.kind(), K::Anchor | K::Tag))
1007        .unwrap_or(c);
1008    first_token(first)
1009}
1010
1011/// The columns of `tokens`, given latest first (as the starts of nested
1012/// collections are, innermost first). Tokens on one line share one
1013/// backward scan of it (`- - - … x` nests a collection per `- `
1014/// on one line; a scan per collection would be quadratic).
1015fn cols_of(tokens: &[Node<'_>]) -> Vec<usize> {
1016    let mut out = vec![0usize; tokens.len()];
1017    let mut i = 0usize;
1018    while let Some(&t) = tokens.get(i) {
1019        // Chars from the scan position to `t`'s start, and, for each
1020        // token met on the way, the count when it was met.
1021        let mut acc = 0usize;
1022        let mut met = vec![(i, 0usize)];
1023        let mut j = i.saturating_add(1);
1024        let mut at = prev_token(t);
1025        while let Some(x) = at {
1026            let text = x.text();
1027            // (A byte order mark is no column, as in `col_of`.)
1028            let chars = if x.kind() == K::ByteOrderMark {
1029                0
1030            } else {
1031                text.chars().count()
1032            };
1033            let breaks = text.contains(['\n', '\r']);
1034            while tokens.get(j) == Some(&x) {
1035                if !breaks {
1036                    met.push((j, acc.saturating_add(chars)));
1037                    j = j.saturating_add(1);
1038                } else {
1039                    break;
1040                }
1041            }
1042            if let Some(k) = text.rfind(['\n', '\r']) {
1043                let tail = text.get(k.saturating_add(1)..).unwrap_or("");
1044                acc = acc.saturating_add(tail.chars().count());
1045                break;
1046            }
1047            acc = acc.saturating_add(chars);
1048            at = prev_token(x);
1049        }
1050        for (k, before) in met {
1051            if let Some(o) = out.get_mut(k) {
1052                *o = acc.saturating_sub(before);
1053            }
1054        }
1055        i = j.max(i.saturating_add(1));
1056    }
1057    out
1058}
1059
1060/// The next sibling of `x` that is not a trivia token. The
1061/// first such element after `x`'s subtree from the comment-run index
1062/// (O(log)), never a walk over the comment lines between siblings: it is
1063/// that sibling, or lies past the parent.
1064fn next_sig(x: Node<'_>) -> Option<Node<'_>> {
1065    let parent = x.parent()?;
1066    let t = x.tree();
1067    let last = t.nav_last_leaf(x.slot())?;
1068    let s = t.node_at_slot(t.solid_after(last)?)?;
1069    (s.parent() == Some(parent)).then_some(s)
1070}
1071
1072/// The previous sibling of `x` that is not a trivia token. The
1073/// last such element before `x` (from the comment-run index) lies in that
1074/// sibling's subtree, or is the parent.
1075fn prev_sig(x: Node<'_>) -> Option<Node<'_>> {
1076    let parent = x.parent()?;
1077    let t = x.tree();
1078    let mut s = t.node_at_slot(t.solid_before(x.slot())?)?;
1079    // A climb to the parent's child.
1080    loop {
1081        if s == parent {
1082            return None;
1083        }
1084        match s.parent() {
1085            Some(p) if p == parent => return Some(s),
1086            Some(p) => s = p,
1087            None => return None,
1088        }
1089    }
1090}
1091
1092/// The next sibling of `x` that is an item (trivia skipped in O(log),
1093/// from the comment-run index).
1094fn next_item(x: Node<'_>) -> Option<Node<'_>> {
1095    let mut at = next_sig(x);
1096    while let Some(s) = at {
1097        if is_item(s.kind()) {
1098            return Some(s);
1099        }
1100        at = next_sig(s);
1101    }
1102    None
1103}
1104
1105/// The previous sibling of `x` that is an item (trivia skipped in
1106/// O(log)).
1107fn prev_item(x: Node<'_>) -> Option<Node<'_>> {
1108    let mut at = prev_sig(x);
1109    while let Some(s) = at {
1110        if is_item(s.kind()) {
1111            return Some(s);
1112        }
1113        at = prev_sig(s);
1114    }
1115    None
1116}
1117
1118// ============================================================ entries
1119
1120/// Whether item `x` is a key of its mapping, read from its neighbours;
1121/// `None` when they cannot tell.
1122fn local_key(x: Node<'_>) -> Option<bool> {
1123    match prev_sig(x).map(Node::kind) {
1124        None | Some(K::MappingKey | K::FlowMappingOpen | K::FlowSequenceOpen | K::FlowEntry) => {
1125            return Some(true);
1126        }
1127        Some(K::MappingValue) => return Some(false),
1128        _ => {}
1129    }
1130    if next_sig(x).is_some_and(|s| s.kind() == K::MappingValue) {
1131        return Some(true);
1132    }
1133    match prev_sig(x) {
1134        Some(p) if is_item(p.kind()) => None,
1135        // The mapping's own properties or other tokens before a first key.
1136        _ => Some(true),
1137    }
1138}
1139
1140/// Whether item `x` is a key of its mapping: from its neighbours, then
1141/// from its previous item's (an empty value right after its key). Only
1142/// error recovery builds shapes neither can tell; `x` is then read as a key
1143/// (rulebook section 5, best effort), never by counting the mapping's items
1144/// (that would cost O(width) per comment).
1145fn is_key(x: Node<'_>) -> bool {
1146    if let Some(k) = local_key(x) {
1147        return k;
1148    }
1149    prev_item(x).and_then(local_key).is_none_or(|k| !k)
1150}
1151
1152/// The key naming the entry that item `x` of a mapping belongs to.
1153fn key_of(x: Node<'_>) -> Node<'_> {
1154    if is_key(x) {
1155        x
1156    } else {
1157        prev_item(x).unwrap_or(x)
1158    }
1159}
1160
1161/// The entry (its key) or item of collection `c` that its child `x` (a
1162/// content element) belongs to; `None` for the collection's own brackets
1163/// and properties.
1164fn entry_owner<'t>(c: Node<'t>, x: Node<'t>) -> Option<Node<'t>> {
1165    let k = x.kind();
1166    if matches!(
1167        k,
1168        K::FlowSequenceOpen
1169            | K::FlowSequenceClose
1170            | K::FlowMappingOpen
1171            | K::FlowMappingClose
1172            | K::Anchor
1173            | K::Tag
1174    ) {
1175        return None;
1176    }
1177    if is_seq(c.kind()) {
1178        return match k {
1179            _ if is_item(k) => Some(x),
1180            K::SequenceEntry => next_item(x),
1181            _ => prev_item(x),
1182        };
1183    }
1184    match k {
1185        _ if is_item(k) => Some(key_of(x)),
1186        K::MappingKey => next_item(x),
1187        K::MappingValue => prev_item(x),
1188        _ => prev_item(x).map(key_of),
1189    }
1190}
1191
1192/// The entry (its key) or item of collection `c` that its child `x`
1193/// **starts**: `x` is the `-`, the `?`, a key written without `?`, or an
1194/// item of a flow sequence.
1195fn entry_opened<'t>(c: Node<'t>, x: Node<'t>) -> Option<Node<'t>> {
1196    let k = x.kind();
1197    match c.kind() {
1198        K::BlockSequence => (k == K::SequenceEntry).then(|| next_item(x)).flatten(),
1199        K::FlowSequence => is_item(k).then_some(x),
1200        _ if is_map(c.kind()) => {
1201            if k == K::MappingKey {
1202                return next_item(x);
1203            }
1204            let after_q = prev_sig(x).is_some_and(|p| p.kind() == K::MappingKey);
1205            (is_item(k) && !after_q && is_key(x)).then_some(x)
1206        }
1207        _ => None,
1208    }
1209}
1210
1211/// What the next content token `n` opens.
1212#[derive(Clone, Copy, Debug)]
1213enum Opens {
1214    /// An entry (its key) or item.
1215    Entry,
1216    /// A node (a value, or a collection with properties).
1217    Node,
1218    /// The `:` of an explicit entry: the target is its value.
1219    ExplicitValue,
1220    /// Nothing: `n` is inside a node (a property after its first one, a
1221    /// block scalar header, error bytes); the target is that node.
1222    Inside,
1223}
1224
1225/// The target a comment right before content token `n` leads (rules 3,
1226/// 4, 9, 10, 11, 12): the innermost entry or item `n` starts, else the
1227/// outermost node it starts, else (for `:` of an explicit entry) that
1228/// entry's value, else the innermost node holding `n`; `fallback` when
1229/// nothing holds it.
1230fn target_of<'t>(n: Node<'t>, fallback: Node<'t>) -> (Node<'t>, Opens) {
1231    let s = n.span().start;
1232    let mut x = n;
1233    // A loop up the ancestors that start where `n` does.
1234    while let Some(a) = x.parent() {
1235        if is_map(a.kind()) || is_seq(a.kind()) {
1236            if let Some(e) = entry_opened(a, x) {
1237                return (e, Opens::Entry);
1238            }
1239        }
1240        if !is_item(a.kind()) || a.span().start != s {
1241            break;
1242        }
1243        x = a;
1244    }
1245    if is_item(x.kind()) {
1246        return (x, Opens::Node);
1247    }
1248    if x.kind() == K::MappingValue {
1249        if let Some(v) = next_item(x) {
1250            return (v, Opens::ExplicitValue);
1251        }
1252    }
1253    let holder = x
1254        .ancestors()
1255        .find(|a| is_item(a.kind()))
1256        .unwrap_or(fallback);
1257    (holder, Opens::Inside)
1258}
1259
1260// ======================================================= lines, blanks
1261
1262/// Where a comment's line puts it.
1263enum Line<'t> {
1264    /// First on its line; the token ending the previous line (`None` at
1265    /// the start of the text).
1266    Own(Option<Node<'t>>),
1267    /// After content: the last content token before it.
1268    Same(Node<'t>),
1269}
1270
1271fn line_of(c: Node<'_>) -> Line<'_> {
1272    let mut at = prev_token(c);
1273    while let Some(t) = at {
1274        if ends_line(t) {
1275            return Line::Own(Some(t));
1276        }
1277        if blankish(t) || t.kind() == K::Comment {
1278            at = prev_token(t);
1279            continue;
1280        }
1281        return Line::Same(t);
1282    }
1283    Line::Own(None)
1284}
1285
1286/// Blank lines above a line whose previous line ends with `end` (rule 8).
1287fn blank_before(end: Option<Node<'_>>) -> usize {
1288    let Some(mut at) = end else { return 0 };
1289    let mut count = 0usize;
1290    loop {
1291        if at.kind() != K::LineBreak {
1292            // A block scalar's text: its lines are content.
1293            return count;
1294        }
1295        let mut u = prev_token(at);
1296        while let Some(t) = u.filter(|t| blankish(*t)) {
1297            u = prev_token(t);
1298        }
1299        match u {
1300            None => return count.saturating_add(1),
1301            Some(t) if t.kind() == K::LineBreak => {
1302                count = count.saturating_add(1);
1303                at = t;
1304            }
1305            Some(t) if ends_line(t) => return count.saturating_add(1),
1306            Some(_) => return count,
1307        }
1308    }
1309}
1310
1311/// What follows an own-line comment up to the next content token.
1312struct Ahead<'t> {
1313    /// The next content token.
1314    next: Option<Node<'t>>,
1315    /// Where the last blank line before it starts.
1316    last_blank: Option<usize>,
1317}
1318
1319fn scan_ahead(c: Node<'_>) -> Ahead<'_> {
1320    let mut line_empty = false;
1321    let mut last_blank = None;
1322    let mut at = next_token(c);
1323    while let Some(t) = at {
1324        match t.kind() {
1325            K::LineBreak => {
1326                if line_empty {
1327                    last_blank = Some(t.span().start);
1328                }
1329                line_empty = true;
1330            }
1331            K::Comment => line_empty = false,
1332            _ if blankish(t) => {}
1333            _ => {
1334                return Ahead {
1335                    next: Some(t),
1336                    last_blank,
1337                };
1338            }
1339        }
1340        at = next_token(t);
1341    }
1342    Ahead {
1343        next: None,
1344        last_blank,
1345    }
1346}
1347
1348// ============================================================ decisions
1349
1350/// A document's child that comes before its content: a directive or the
1351/// `---` marker.
1352fn is_start(n: Node<'_>) -> bool {
1353    matches!(
1354        n.kind(),
1355        K::DocumentStartMarker | K::YamlDirective | K::TagDirective | K::ReservedDirective
1356    )
1357}
1358
1359/// The document begins with a directive or `---` (rule 1 applies before
1360/// it). O(1): a document never begins with trivia.
1361fn has_start(doc: Node<'_>) -> bool {
1362    doc.first_child().is_some_and(is_start)
1363}
1364
1365/// Rule 5: a comment after content token `p` on its line.
1366fn same_line<'t>(p: At<'t>, around: &Around<'t>) -> Attachment<'t> {
1367    let done = |owner, document| Attachment {
1368        owner,
1369        rule: AttachRule::Trailing,
1370        blank_lines_before: 0,
1371        document,
1372    };
1373    let mut x = p.tok;
1374    // A loop up the ancestors, to the innermost entry or item. The
1375    // loop ends at the stream, the only element without a parent.
1376    loop {
1377        let Some(a) = x.parent() else {
1378            // `x` is the stream: an input without documents.
1379            return done(CommentOwner::DocumentHeader(x), None);
1380        };
1381        let k = a.kind();
1382        if is_map(k) || is_seq(k) {
1383            if let Some(o) = entry_owner(a, x) {
1384                return done(CommentOwner::Trailing(o), p.doc);
1385            }
1386        } else if k == K::Document {
1387            // `x` is a child of the document: O(1) by its kind.
1388            return if is_start(x) {
1389                done(CommentOwner::DocumentHeader(a), Some(a))
1390            } else if is_item(x.kind()) {
1391                done(CommentOwner::Trailing(x), Some(a))
1392            } else {
1393                // `...`, or bytes skipped at document level (error
1394                // recovery, best effort).
1395                done(CommentOwner::DocumentFooter(a), Some(a))
1396            };
1397        } else if k == K::Stream {
1398            // A stray `...` or an error region between documents.
1399            if let Some(d) = around.next_doc(x) {
1400                return done(CommentOwner::DocumentHeader(d), Some(d));
1401            }
1402            return match around.prev_doc(x) {
1403                Some(d) => done(CommentOwner::DocumentFooter(d), Some(d)),
1404                None => done(CommentOwner::DocumentHeader(a), None),
1405            };
1406        }
1407        x = a;
1408    }
1409}
1410
1411/// What an own-line comment's owner is when it does not fall to rule 6.
1412enum Otherwise<'t> {
1413    Fixed(CommentOwner<'t>, AttachRule),
1414    /// Rules 2/3 for this document.
1415    Header {
1416        doc: Node<'t>,
1417        target: Node<'t>,
1418        last_blank: Option<usize>,
1419    },
1420    /// Rules 4/10/11/12.
1421    Leading {
1422        target: Node<'t>,
1423        opens: Opens,
1424        col: usize,
1425    },
1426}
1427
1428/// The decision context of one run of trivia (shared by its comments).
1429struct Plan<'t> {
1430    /// The block collections that close in the run, innermost first, with
1431    /// their columns (rule 6).
1432    footer: Vec<(Node<'t>, usize)>,
1433    /// Rule 6 needs a column right of this.
1434    threshold: usize,
1435    otherwise: Otherwise<'t>,
1436    /// The document of `otherwise`'s owner.
1437    document: Option<Node<'t>>,
1438    /// The document of the `footer` collections.
1439    footer_document: Option<Node<'t>>,
1440}
1441
1442impl<'t> Plan<'t> {
1443    fn fixed(owner: CommentOwner<'t>, rule: AttachRule, document: Option<Node<'t>>) -> Self {
1444        Self {
1445            footer: Vec::new(),
1446            threshold: 0,
1447            otherwise: Otherwise::Fixed(owner, rule),
1448            document,
1449            footer_document: document,
1450        }
1451    }
1452
1453    fn header(doc: Node<'t>, rule: AttachRule) -> Self {
1454        Self::fixed(CommentOwner::DocumentHeader(doc), rule, Some(doc))
1455    }
1456}
1457
1458/// The block collections among `p`'s ancestors below the first one
1459/// `stop` accepts (or below the document), innermost first, with their
1460/// columns: what closes between `p` and what follows.
1461fn closing<'t>(
1462    p: Node<'t>,
1463    stop: impl Fn(Node<'t>) -> bool,
1464) -> (Vec<(Node<'t>, usize)>, Option<Node<'t>>) {
1465    let mut colls = Vec::new();
1466    let mut at = p.parent();
1467    let mut lca = None;
1468    while let Some(a) = at {
1469        if stop(a) || matches!(a.kind(), K::Document | K::Stream) {
1470            lca = Some(a);
1471            break;
1472        }
1473        if is_block(a.kind()) {
1474            colls.push(a);
1475        }
1476        at = a.parent();
1477    }
1478    let starts: Vec<Node<'t>> = colls.iter().map(|c| coll_start(*c)).collect();
1479    let cols = cols_of(&starts);
1480    (colls.into_iter().zip(cols).collect(), lca)
1481}
1482
1483/// Rules 2/3 for document `d` whose root `r` starts with content token
1484/// `n`.
1485fn header_plan<'t>(d: Node<'t>, r: Node<'t>, n: Node<'t>, ahead: &Ahead<'t>) -> Plan<'t> {
1486    Plan {
1487        footer: Vec::new(),
1488        threshold: 0,
1489        otherwise: Otherwise::Header {
1490            doc: d,
1491            target: target_of(n, r).0,
1492            last_blank: ahead.last_blank,
1493        },
1494        document: Some(d),
1495        footer_document: Some(d),
1496    }
1497}
1498
1499/// The context of the run between content token `p` and `ahead.next`.
1500fn make_plan<'t>(
1501    tree: &'t SyntaxTree,
1502    p: Option<At<'t>>,
1503    ahead: &Ahead<'t>,
1504    around: &Around<'t>,
1505) -> Plan<'t> {
1506    let n = ahead.next.map(|n| match p {
1507        // In P's document: its child is P's, or found by a climb through
1508        // the nodes `n` opens (amortised O(1) per node over a pass).
1509        Some(At {
1510            doc: Some(d),
1511            child,
1512            ..
1513        }) if contains(d, n) => {
1514            let child = match child {
1515                Some(c) if contains(c, n) => Some(c),
1516                _ => {
1517                    let mut below = n;
1518                    while let Some(a) = below.parent().filter(|a| *a != d) {
1519                        below = a;
1520                    }
1521                    Some(below)
1522                }
1523            };
1524            At {
1525                tok: n,
1526                doc: Some(d),
1527                child,
1528            }
1529        }
1530        _ => locate(n),
1531    });
1532    match (p, n) {
1533        (
1534            Some(At {
1535                tok: pt,
1536                doc: Some(d),
1537                child: Some(xp),
1538            }),
1539            Some(At {
1540                tok: nt,
1541                doc: Some(e),
1542                child: Some(xn),
1543            }),
1544        ) if d == e => inside(d, pt, xp, nt, xn, ahead),
1545        _ => between(tree, p, n, ahead, around),
1546    }
1547}
1548
1549/// A run inside document `d`, between content token `p` (in `d`'s child
1550/// `xp`) and `n` (in `xn`).
1551fn inside<'t>(
1552    d: Node<'t>,
1553    p: Node<'t>,
1554    xp: Node<'t>,
1555    n: Node<'t>,
1556    xn: Node<'t>,
1557    ahead: &Ahead<'t>,
1558) -> Plan<'t> {
1559    // Rule 1: before `---` (or a directive before it).
1560    if is_start(xn) {
1561        return Plan::header(d, AttachRule::HeaderBeforeStart);
1562    }
1563    // After `---` or a directive, before any content: rules 2/3.
1564    if is_start(xp) {
1565        return if is_item(xn.kind()) && !empty(xn) {
1566            header_plan(d, xn, n, ahead)
1567        } else {
1568            Plan::header(d, AttachRule::HeaderBlankLine)
1569        };
1570    }
1571    if xp != xn || !is_item(xn.kind()) {
1572        // After the root, before `...` (or an error region after it):
1573        // rules 6/7.
1574        let (footer, _) = closing(p, |_| false);
1575        let threshold = footer.last().map_or(0, |(_, c)| *c);
1576        return Plan {
1577            footer,
1578            threshold,
1579            otherwise: Otherwise::Fixed(
1580                CommentOwner::DocumentFooter(d),
1581                AttachRule::DocumentFooter,
1582            ),
1583            document: Some(d),
1584            footer_document: Some(d),
1585        };
1586    }
1587    // Inside the root `xn`: rules 4, 6, 9, 10, 11, 12.
1588    let r = xn;
1589    let (footer, lca) = closing(p, |a| contains(a, n));
1590    let flow = lca
1591        .into_iter()
1592        .flat_map(|l| core::iter::once(l).chain(l.ancestors()))
1593        .take_while(|a| !matches!(a.kind(), K::Document | K::Stream))
1594        .find(|a| is_map(a.kind()) || is_seq(a.kind()))
1595        .is_some_and(|c| is_flow(c.kind()));
1596    if flow {
1597        return Plan::fixed(flow_owner(n, r), AttachRule::Flow, Some(d));
1598    }
1599    let col = col_of(n);
1600    let (target, opens) = target_of(n, r);
1601    Plan {
1602        footer,
1603        threshold: col,
1604        otherwise: Otherwise::Leading { target, opens, col },
1605        document: Some(d),
1606        footer_document: Some(d),
1607    }
1608}
1609
1610/// Rule 9: the item after the comment (commas skipped) or the footer of
1611/// the flow collection whose closing bracket follows.
1612fn flow_owner<'t>(n: Node<'t>, root: Node<'t>) -> CommentOwner<'t> {
1613    let mut t = n;
1614    while t.kind() == K::FlowEntry {
1615        match next_visible(t) {
1616            Some(x) => t = x,
1617            None => break,
1618        }
1619    }
1620    if matches!(t.kind(), K::FlowSequenceClose | K::FlowMappingClose) {
1621        if let Some(c) = t.parent() {
1622            return CommentOwner::Footer(c);
1623        }
1624    }
1625    CommentOwner::Leading(target_of(t, root).0)
1626}
1627
1628/// A run at stream level (outside every document), between content
1629/// tokens `p` and `n` (either may be missing, or a stray token).
1630fn between<'t>(
1631    tree: &'t SyntaxTree,
1632    p: Option<At<'t>>,
1633    n: Option<At<'t>>,
1634    ahead: &Ahead<'t>,
1635    around: &Around<'t>,
1636) -> Plan<'t> {
1637    // The documents before and after the run.
1638    let dp = p.and_then(|p| p.doc.or_else(|| around.prev_doc(p.tok)));
1639    let dn = n.and_then(|n| n.doc.or_else(|| around.next_doc(n.tok)));
1640    // P is in `dp` (which then ended without `...`), after its content.
1641    let content = p
1642        .and_then(|p| p.doc.and(p.child))
1643        .is_some_and(|xp| !is_start(xp) && xp.kind() != K::DocumentEndMarker);
1644    // P is `dp`'s `---` or a directive: `dp` has no content.
1645    let blank = p.and_then(|p| p.doc.and(p.child)).is_some_and(is_start);
1646    let dn_start = dn.is_some_and(has_start);
1647    let mut plan = match (dn, dp) {
1648        // Rule 1: a comment before a `---` is always its header.
1649        (Some(e), _) if dn_start => Plan::header(e, AttachRule::HeaderBeforeStart),
1650        (Some(e), _) => match n {
1651            Some(At {
1652                tok,
1653                doc: Some(_),
1654                child: Some(xn),
1655            }) if is_item(xn.kind()) && !empty(xn) => header_plan(e, xn, tok, ahead),
1656            _ => Plan::header(e, AttachRule::HeaderBlankLine),
1657        },
1658        // After a document with no content that ended without `...`: still
1659        // its header (rule 2).
1660        (None, Some(i)) if blank => Plan::header(i, AttachRule::HeaderBlankLine),
1661        (None, Some(i)) => Plan::fixed(
1662            CommentOwner::DocumentFooter(i),
1663            AttachRule::DocumentFooter,
1664            Some(i),
1665        ),
1666        (None, None) => Plan::fixed(
1667            CommentOwner::DocumentHeader(tree.root()),
1668            AttachRule::HeaderBlankLine,
1669            None,
1670        ),
1671    };
1672    // Rule 6 past an implicitly ended document's end, unless a `---`
1673    // follows (rule 1 wins).
1674    if content && !dn_start {
1675        if let Some(p) = p {
1676            let (footer, _) = closing(p.tok, |_| false);
1677            plan.threshold = footer.last().map_or(0, |(_, c)| *c);
1678            plan.footer = footer;
1679            plan.footer_document = dp;
1680        }
1681    }
1682    plan
1683}
1684
1685/// The deepest owner a run has reached so far (rule 13): its rank and the
1686/// attachment that set it.
1687#[derive(Clone, Copy)]
1688struct Floor<'t> {
1689    rank: usize,
1690    attachment: Attachment<'t>,
1691}
1692
1693/// An own-line comment `c` at column `col` with `blank` blank lines above
1694/// it, in the run `plan` describes, after the run's earlier comments left
1695/// `floor` (rule 13).
1696///
1697/// Ranks, deepest first: the closing collections innermost first (rule
1698/// 6), then everything past them (`plan.footer.len()`: the next node's
1699/// leading comment, the document footer or header, a flow owner). A
1700/// comment whose own rules give a lower rank than `floor` takes the owner
1701/// of the comment before it, so each owner's comments are contiguous in
1702/// the run.
1703fn decide<'t>(
1704    plan: &Plan<'t>,
1705    c: Node<'t>,
1706    col: usize,
1707    blank: usize,
1708    floor: &mut Option<Floor<'t>>,
1709) -> Attachment<'t> {
1710    let (a, rank) = decide_one(plan, c, col, blank);
1711    if let Some(f) = *floor {
1712        if rank < f.rank {
1713            return Attachment {
1714                owner: f.attachment.owner,
1715                rule: AttachRule::RunOrder,
1716                blank_lines_before: blank,
1717                document: f.attachment.document,
1718            };
1719        }
1720    }
1721    *floor = Some(Floor {
1722        rank,
1723        attachment: a,
1724    });
1725    a
1726}
1727
1728/// Rules 2–4, 6, 7, 9–12 for one own-line comment, with the owner's rank
1729/// (see [`decide`]).
1730fn decide_one<'t>(
1731    plan: &Plan<'t>,
1732    c: Node<'t>,
1733    col: usize,
1734    blank: usize,
1735) -> (Attachment<'t>, usize) {
1736    let done = |owner, rule, document| Attachment {
1737        owner,
1738        rule,
1739        blank_lines_before: blank,
1740        document,
1741    };
1742    let outer = plan.footer.len();
1743    let i = own_rank(plan, col);
1744    if i < outer {
1745        if let Some((k, _)) = plan.footer.get(i) {
1746            let a = done(
1747                CommentOwner::Footer(*k),
1748                AttachRule::CollectionFooter,
1749                plan.footer_document,
1750            );
1751            return (a, i);
1752        }
1753    }
1754    let a = match plan.otherwise {
1755        Otherwise::Fixed(owner, rule) => done(owner, rule, plan.document),
1756        Otherwise::Header {
1757            doc,
1758            target,
1759            last_blank,
1760        } => {
1761            if last_blank.is_some_and(|b| b > c.span().start) {
1762                done(
1763                    CommentOwner::DocumentHeader(doc),
1764                    AttachRule::HeaderBlankLine,
1765                    Some(doc),
1766                )
1767            } else {
1768                done(
1769                    CommentOwner::Leading(target),
1770                    AttachRule::FirstNodeLeading,
1771                    Some(doc),
1772                )
1773            }
1774        }
1775        Otherwise::Leading {
1776            target,
1777            opens,
1778            col: n,
1779        } => {
1780            let rule = if col < n {
1781                AttachRule::ShallowLeading
1782            } else {
1783                match opens {
1784                    Opens::Entry | Opens::Node => AttachRule::Leading,
1785                    Opens::ExplicitValue => AttachRule::ExplicitValue,
1786                    Opens::Inside => AttachRule::Inside,
1787                }
1788            };
1789            done(CommentOwner::Leading(target), rule, plan.document)
1790        }
1791    };
1792    (a, outer)
1793}
1794
1795/// The rank rules 2–4, 6, 7, 9–12 give an own-line comment at column `col` in
1796/// the run `plan` describes (see [`decide`]): the closing collection it is
1797/// right of, innermost first, else past them all (`plan.footer.len()`).
1798/// Non-increasing in `col` (the comment-run index relies on it: rule 13's floor
1799/// is the rank of the run's smallest column).
1800fn own_rank(plan: &Plan<'_>, col: usize) -> usize {
1801    let outer = plan.footer.len();
1802    if col > plan.threshold && outer > 0 {
1803        plan.footer
1804            .partition_point(|(_, kc)| *kc > col)
1805            .min(outer.saturating_sub(1))
1806    } else {
1807        outer
1808    }
1809}
1810
1811/// The smallest column whose rank is below `k` (`k >= 1`): a comment
1812/// ranks at least `k` exactly when its column is below it. `None` when it
1813/// does not fit the index's `u32` columns.
1814fn cut_below(plan: &Plan<'_>, k: usize) -> Option<u32> {
1815    // `big` ranks 0: right of the threshold and of every footer column.
1816    let big = plan
1817        .footer
1818        .iter()
1819        .map(|(_, c)| *c)
1820        .chain(core::iter::once(plan.threshold))
1821        .max()
1822        .unwrap_or(0)
1823        .checked_add(1)?;
1824    let (mut lo, mut hi) = (0usize, big);
1825    // A binary search for the first column ranked below `k`.
1826    while lo < hi {
1827        let mid = lo.saturating_add(hi.saturating_sub(lo) / 2);
1828        if own_rank(plan, mid) < k {
1829            hi = mid;
1830        } else {
1831            lo = mid.saturating_add(1);
1832        }
1833    }
1834    u32::try_from(lo).ok()
1835}
1836
1837/// The plan's columns fit the index's `u32` columns (with room for the
1838/// cut past them).
1839fn cols_fit(plan: &Plan<'_>) -> bool {
1840    let limit = col_limit();
1841    let fits = |c: usize| c < limit;
1842    fits(plan.threshold) && plan.footer.iter().all(|(_, c)| fits(*c))
1843}
1844
1845/// The columns the index decides: below `u32::MAX / 2`.
1846#[cfg(not(test))]
1847const fn col_limit() -> usize {
1848    (u32::MAX / 2) as usize
1849}
1850
1851/// The columns the index decides, lowered by tests: the
1852/// fallbacks for wider columns need lines of 2 GiB
1853/// otherwise).
1854#[cfg(test)]
1855fn col_limit() -> usize {
1856    tests::COL_LIMIT.with(core::cell::Cell::get)
1857}
1858
1859/// What [`SyntaxTree::decide_indexed`] is asked for.
1860#[derive(Clone, Copy)]
1861enum Want {
1862    Attachment,
1863    Document,
1864}
1865
1866/// What [`SyntaxTree::decide_indexed`] decided.
1867enum Decided<'t> {
1868    Attachment(Attachment<'t>),
1869    Document(Option<Node<'t>>),
1870}
1871
1872#[cfg(test)]
1873mod tests {
1874    #![allow(
1875        clippy::unwrap_used,
1876        clippy::indexing_slicing,
1877        clippy::arithmetic_side_effects
1878    )]
1879
1880    use super::*;
1881    use core::cell::Cell;
1882
1883    std::thread_local! {
1884        /// [`col_limit`] on this thread.
1885        pub(super) static COL_LIMIT: Cell<usize> = const { Cell::new((u32::MAX / 2) as usize) };
1886    }
1887
1888    /// Long runs of comment lines below nested collections at every
1889    /// column, stray `...`, a document after them; and the same trees
1890    /// after edits that cut the runs.
1891    fn trees() -> Vec<SyntaxTree> {
1892        let mut out = Vec::new();
1893        for depth in 1..5usize {
1894            let mut s = String::new();
1895            for i in 0..depth {
1896                s.push_str(&format!("{}k{i}:\n", " ".repeat(2 * i)));
1897            }
1898            s.push_str(&format!("{}leaf: 1\n", " ".repeat(2 * depth)));
1899            for i in 0..90 {
1900                // Deep first, shallower later (footers, then outer owners).
1901                s.push_str(&" ".repeat((2 * depth + 1).saturating_sub((i * 7) % 5 + i / 30)));
1902                s.push_str(&format!("# c{i}\n"));
1903                if i % 17 == 4 {
1904                    s.push('\n');
1905                }
1906            }
1907            if depth % 2 == 0 {
1908                s.push_str("z: 1\n");
1909            } else {
1910                s.push_str("...\n# s\n...\n# h\n--- y\n");
1911            }
1912            let mut t = SyntaxTree::parse(s.as_str());
1913            out.push(t.clone());
1914            let comments: Vec<_> = t
1915                .root()
1916                .descendants()
1917                .filter(|n| n.kind() == K::Comment)
1918                .map(Node::id)
1919                .collect();
1920            for (k, c) in comments.iter().enumerate().filter(|(k, _)| k % 5 == 1) {
1921                let _ = t.replace_token(*c, &format!("# r{k}"));
1922            }
1923            out.push(t);
1924        }
1925        out
1926    }
1927
1928    /// With the index's column range lowered
1929    /// (to none, and to a few columns), the fallbacks for columns beyond
1930    /// it — the run replay of [`SyntaxTree::comment_attachment`] and
1931    /// [`SyntaxTree::comment_document`], and
1932    /// [`SyntaxTree::last_footer_comment_walk`] — decide as the pass and
1933    /// as the index do.
1934    #[test]
1935    fn wide_column_fallbacks_decide_as_the_index() {
1936        let mut with_footers = 0;
1937        for t in trees() {
1938            let all = t.comment_attachments();
1939            let blocks: Vec<_> = t
1940                .root()
1941                .descendants()
1942                .filter(|x| is_block(x.kind()))
1943                .collect();
1944            let footers: Vec<_> = blocks.iter().map(|b| t.last_footer_comment(*b)).collect();
1945            with_footers += usize::from(footers.iter().any(Option::is_some));
1946            for limit in [0usize, 1, 2, 3, 5, 8] {
1947                COL_LIMIT.with(|c| c.set(limit));
1948                for (c, a) in &all {
1949                    assert_eq!(t.comment_attachment(*c).as_ref(), Some(a), "{limit}");
1950                    assert_eq!(t.comment_document(*c), Some(a.document()), "{limit}");
1951                }
1952                for (b, want) in blocks.iter().zip(&footers) {
1953                    assert_eq!(t.last_footer_comment(*b), *want, "{limit}");
1954                }
1955            }
1956            COL_LIMIT.with(|c| c.set((u32::MAX / 2) as usize));
1957        }
1958        assert!(with_footers >= 4, "{with_footers}");
1959    }
1960}