ephemeris_documents/toml/

order.rs

//! Table order and positions that make a merge converge.

use toml_edit::{Item, Table};

use super::decor::prefix_str;

/// One table, in walk order.
struct Slot {
    depth: usize,
    old: Option<isize>,
    prints_header: bool,
    has_glued_comment: bool,
    rank: usize,
    blank_before: bool,
}

impl Slot {
    fn of(table: &Table, depth: usize) -> Self {
        Self {
            depth,
            old: table.position(),
            prints_header: !table.is_implicit() || Self::has_values(table),
            has_glued_comment: prefix_str(table.decor())
                .is_some_and(|prefix| !prefix.is_empty() && !prefix.starts_with(['\n', '\r'])),
            rank: 0,
            blank_before: false,
        }
    }

    fn has_values(table: &Table) -> bool {
        table.iter().any(|(_, item)| match item {
            Item::Table(child) => child.is_dotted(),
            Item::ArrayOfTables(_) => false,
            Item::Value(_) | Item::None => true,
        })
    }

    const fn is_new(&self) -> bool {
        self.old.is_none()
    }
}

/// The positions the tables of a merged tree get.
///
/// Existing tables keep their relative source order. A table without a
/// position is new and goes after the last table of its parent's subtree, so
/// it ends up at the end of its parent.
pub(super) struct TableOrder(Vec<Slot>);

impl TableOrder {
    /// Plan the order of every table under `root`, including `root`.
    pub(super) fn of(root: &mut Table) -> Self {
        let mut slots = Vec::new();
        let root_has_values = Slot::has_values(root);
        Self::walk(root, 0, &mut |table, depth| {
            slots.push(Slot::of(table, depth));
        });
        Self::place_root_first(&mut slots, root_has_values);
        let order = Self::ordered(&slots);
        for (rank, &index) in order.iter().enumerate() {
            let blank_before = Self::needs_blank(&slots, &order, rank);
            if let Some(slot) = slots.get_mut(index) {
                slot.rank = rank;
                slot.blank_before = blank_before;
            }
        }
        Self(slots)
    }

    /// The root has no header, so it only prints when it holds values.
    const fn place_root_first(slots: &mut [Slot], has_values: bool) {
        if let Some(root) = slots.first_mut() {
            root.old = None;
            root.prints_header = has_values;
        }
    }

    /// Walk indices in final order: existing tables by old position, then
    /// every new table after the last table of its parent's subtree.
    fn ordered(slots: &[Slot]) -> Vec<usize> {
        let mut order: Vec<usize> = (0..slots.len())
            .filter(|&index| slots.get(index).is_some_and(|slot| !slot.is_new()))
            .collect();
        order.sort_by_key(|&index| (slots.get(index).and_then(|slot| slot.old), index));
        for (index, slot) in slots.iter().enumerate() {
            if slot.is_new() {
                let after = Self::slot_after_subtree(slots, &order, index);
                order.insert(after, index);
            }
        }
        order
    }

    /// The place for the new table at `index`. It goes right before its own
    /// first existing descendant. Without one, it goes after the last table
    /// of its parent's subtree. The root goes to the front.
    fn slot_after_subtree(slots: &[Slot], order: &[usize], index: usize) -> usize {
        let own = index.saturating_add(1)..Self::subtree_end(slots, index);
        if let Some(at) = order.iter().position(|other| own.contains(other)) {
            return at;
        }
        let depth = slots.get(index).map_or(0, |slot| slot.depth);
        let Some(parent) = slots
            .get(..index)
            .and_then(|before| before.iter().rposition(|slot| slot.depth < depth))
        else {
            return 0;
        };
        let family = parent..Self::subtree_end(slots, parent);
        order
            .iter()
            .rposition(|other| family.contains(other))
            .map_or(0, |at| at.saturating_add(1))
    }

    /// The walk index after the last descendant of the table at `index`.
    fn subtree_end(slots: &[Slot], index: usize) -> usize {
        let depth = slots.get(index).map_or(0, |slot| slot.depth);
        slots
            .iter()
            .enumerate()
            .skip(index.saturating_add(1))
            .find(|(_, slot)| slot.depth <= depth)
            .map_or(slots.len(), |(at, _)| at)
    }

    /// Whether the table at `rank` needs a blank line before its decor. That
    /// holds for an existing table that directly follows a new table that
    /// prints a header, other than the root. It also holds for a new table
    /// that brings a comment, which replaces the blank line a table gets by
    /// default, when something is printed before it.
    fn needs_blank(slots: &[Slot], order: &[usize], rank: usize) -> bool {
        let slot = order.get(rank).and_then(|&index| slots.get(index));
        let is_existing = slot.is_some_and(|slot| !slot.is_new());
        let is_commented_header = rank > 0
            && slot
                .is_some_and(|slot| slot.is_new() && slot.prints_header && slot.has_glued_comment)
            && Self::prints_before(slots, order, rank);
        let follows_new_header = rank
            .checked_sub(1)
            .and_then(|before| order.get(before))
            .is_some_and(|&before| {
                before != 0
                    && slots
                        .get(before)
                        .is_some_and(|previous| previous.is_new() && previous.prints_header)
            });
        (is_existing && follows_new_header) || is_commented_header
    }

    /// Whether any table or value before `rank` prints a line.
    fn prints_before(slots: &[Slot], order: &[usize], rank: usize) -> bool {
        order
            .iter()
            .take(rank)
            .any(|&index| slots.get(index).is_some_and(|slot| slot.prints_header))
    }

    /// Number the tables under `root`, which must be the tree this order was
    /// planned for, and separate a header that follows a new one by a blank
    /// line.
    pub(super) fn apply(&self, root: &mut Table) {
        let mut index = 0usize;
        Self::walk(root, 0, &mut |table, _| {
            let slot = self.0.get(index);
            let rank = slot.map_or(0, |slot| slot.rank);
            table.set_position(isize::try_from(rank).ok());
            if slot.is_some_and(|slot| slot.blank_before) {
                let prefix = prefix_str(table.decor())
                    .filter(|prefix| !prefix.starts_with(['\n', '\r']))
                    .map(|prefix| format!("\n{prefix}"));
                if let Some(prefix) = prefix {
                    table.decor_mut().set_prefix(prefix);
                }
            }
            index = index.saturating_add(1);
        });
    }

    /// Drop the positions of every table in `item`. Positions that come from
    /// another document mean nothing in this one.
    pub(super) fn forget(item: &mut Item) {
        match item {
            Item::Table(table) => {
                table.set_position(None);
                for (_, child) in table.iter_mut() {
                    Self::forget(child);
                }
            }
            Item::ArrayOfTables(tables) => {
                for table in tables.iter_mut() {
                    table.set_position(None);
                    for (_, child) in table.iter_mut() {
                        Self::forget(child);
                    }
                }
            }
            Item::None | Item::Value(_) => {}
        }
    }

    /// Visit `table` and every table below it, parents first. Dotted tables
    /// have no header and no position, so they are only descended into.
    fn walk(table: &mut Table, depth: usize, visit: &mut impl FnMut(&mut Table, usize)) {
        let depth = if table.is_dotted() {
            depth
        } else {
            visit(table, depth);
            depth.saturating_add(1)
        };
        for (_, item) in table.iter_mut() {
            match item {
                Item::Table(child) => Self::walk(child, depth, visit),
                Item::ArrayOfTables(children) => {
                    for child in children.iter_mut() {
                        Self::walk(child, depth, visit);
                    }
                }
                Item::None | Item::Value(_) => {}
            }
        }
    }
}