atmos/os_lib/layout/

multicol.rs

//! CSS 多段組（`column-count` / `column-width` / `columns` / `column-gap`）の
//! 列幾何計算（純粋モジュール）。
//!
//! ハードウェアにもグローバル状態にも依存しない算術だけなので、
//! QEMU 抜きでホスト側から検証できる。
//!
//! # 仕様の要点（CSS Multi-column Layout Level 1）
//!
//! - `column-count` は列数の指定、`column-width` は 1 列の**最小**目安幅。
//!   両方指定されたときは「`column-width` から求まる列数」と
//!   `column-count` の**小さい方**を採る（`column-count` は上限として働く）。
//! - `column-gap` の既定は `normal`＝`1em` 相当。ここでは呼び出し側が
//!   解決したピクセル値を受け取る。
//! - 列は等幅で、`gap` は列と列の**間だけ**に入る（外側には入らない）。
//!   よって `列幅 = (使用可能幅 - gap * (列数 - 1)) / 列数`。
//!
//! # 割り切り
//!
//! 段抜き（`column-span`）・段区切り（`break-inside`）・段罫線
//! （`column-rule`）は扱わない。本モジュールは「何列で、各列はどの
//! x 座標にどの幅で並ぶか」だけを決める。

extern crate alloc;
use alloc::vec::Vec;

/// 多段組の指定。いずれも解決済みのピクセル値／個数。
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct MultiColSpec {
    /// `column-count`。未指定は `None`。
    pub count: Option<i32>,
    /// `column-width`（1 列の最小目安幅、px）。未指定は `None`。
    pub width: Option<i32>,
    /// `column-gap`（px）。`normal` は呼び出し側で 1em 相当へ解決しておく。
    pub gap: i32,
}

/// 列の位置と幅。
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Column {
    /// コンテンツボックス左端からの x オフセット（px）。
    pub x: i32,
    /// 列の幅（px）。
    pub width: i32,
}

/// 実際に使う列数を決める（純粋関数）。
///
/// - どちらも未指定なら 1 列（多段組ではない）。
/// - `count` だけなら その値（1 未満は 1 に切り上げ）。
/// - `width` だけなら 使用可能幅から入るだけ詰める。
/// - 両方あれば **小さい方**（`count` が上限）。
///
/// `avail_w` が 0 以下、または `width` が 0 以下のときは 1 列へ倒す
/// （ゼロ除算と無限列を防ぐ）。
pub fn resolve_column_count(spec: &MultiColSpec, avail_w: i32) -> i32 {
    if avail_w <= 0 {
        return 1;
    }
    // `column-width` から入る列数を求める。gap も 1 列分ずつ消費する。
    let from_width = spec.width.and_then(|w| {
        if w <= 0 {
            return None;
        }
        // n 列入る条件: n*w + (n-1)*gap <= avail_w
        //            → n <= (avail_w + gap) / (w + gap)
        let denom = w.saturating_add(spec.gap.max(0));
        if denom <= 0 {
            return None;
        }
        let n = (avail_w.saturating_add(spec.gap.max(0))) / denom;
        Some(n.max(1))
    });
    let from_count = spec.count.map(|c| c.max(1));

    match (from_count, from_width) {
        (None, None) => 1,
        (Some(c), None) => c,
        (None, Some(w)) => w,
        // 仕様上 `column-count` は上限として働く。
        (Some(c), Some(w)) => c.min(w),
    }
}

/// 列の x 座標と幅を計算する（純粋関数）。
///
/// `gap` は列間にだけ入る。端数は最後の列へ寄せず、各列を等幅にしたうえで
/// 余りぶんだけ最終列を広げる（合計が `avail_w` を超えないようにする）。
/// 列幅が負になる（gap が広すぎる）場合は 0 幅の列を返し、パニックしない。
pub fn layout_columns(spec: &MultiColSpec, avail_w: i32) -> Vec<Column> {
    let n = resolve_column_count(spec, avail_w);
    let gap = spec.gap.max(0);
    if n <= 1 {
        return alloc::vec![Column {
            x: 0,
            width: avail_w.max(0),
        }];
    }
    let total_gap = gap.saturating_mul(n - 1);
    let usable = avail_w.saturating_sub(total_gap);
    if usable <= 0 {
        // gap だけで埋まってしまう場合。列は作るが幅 0 にする。
        return (0..n)
            .map(|i| Column {
                x: (gap.saturating_add(0)).saturating_mul(i),
                width: 0,
            })
            .collect();
    }
    let base = usable / n;
    let mut cols = Vec::with_capacity(n as usize);
    let mut x = 0;
    for i in 0..n {
        // 端数（usable % n）は最終列で吸収し、合計が avail_w を超えないようにする。
        let w = if i == n - 1 { usable - base * (n - 1) } else { base };
        cols.push(Column { x, width: w });
        x = x.saturating_add(w).saturating_add(gap);
    }
    cols
}

/// `columns` ショートハンドを `column-width` と `column-count` へ分解する。
///
/// 仕様上、値は「長さ」と「整数」が任意順で高々 1 つずつ。
/// `auto` は「その成分は未指定」を意味する。
/// 解決できない字句は無視する（不正値でページ全体を壊さない）。
///
/// 長さの解決（`px` 以外の単位）は呼び出し側の責務。ここでは
/// **末尾が `px` か単位無しの数値**だけを長さとして受け取り、
/// 整数だけの値は列数として扱う。
pub fn parse_columns_shorthand(s: &str) -> (Option<i32>, Option<i32>) {
    let mut width = None;
    let mut count = None;
    for tok in s.split_whitespace() {
        let t = tok.trim();
        if t.is_empty() || t.eq_ignore_ascii_case("auto") {
            continue;
        }
        if let Some(px) = t.strip_suffix("px") {
            if let Ok(v) = px.trim().parse::<f32>() {
                if v.is_finite() && v > 0.0 {
                    width = Some(v as i32);
                }
            }
            continue;
        }
        // 単位無しの整数は列数。小数や負数は無視する。
        if let Ok(v) = t.parse::<i32>() {
            if v > 0 {
                count = Some(v);
            }
            continue;
        }
        // それ以外（`2em` 等の未対応単位）は長さとして扱えないので無視する。
    }
    (width, count)
}

/// `column-fill` プロパティ値（W3C CSS Multi-column Layout Level 1 §7）。
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ColumnFill {
    /// 各列の高さを均等にバランスさせ、左列から順に配置する（既定値）。
    Balance,
    /// コンテナの高さまで順番に各列を埋める。
    Auto,
}

/// `column-fill` 文字列をパースする（純粋関数）。
pub fn parse_column_fill(s: &str) -> ColumnFill {
    if s.trim().eq_ignore_ascii_case("auto") {
        ColumnFill::Auto
    } else {
        ColumnFill::Balance
    }
}

/// 子ボックスを列へ振り分けた結果。
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Placement {
    /// 何列目へ入れるか（0 起点）。
    pub col: usize,
    /// その列の中での上端オフセット（px）。
    pub y: i32,
}

/// 各アイテムの高さ列、列数、充填モード（`column-fill`）、コンテナ指定高さ（`max_h`）を受け取り、
/// ドキュメント順序を維持したまま各列へ配置する（純粋関数）。
pub fn assign_to_columns_balanced(
    heights: &[i32],
    n_cols: usize,
    fill: ColumnFill,
    max_h: Option<i32>,
) -> Vec<Placement> {
    let n = n_cols.max(1);
    if heights.is_empty() {
        return Vec::new();
    }
    if n == 1 {
        let mut y = 0i32;
        let mut out = Vec::with_capacity(heights.len());
        for &h in heights {
            out.push(Placement { col: 0, y });
            y = y.saturating_add(h.max(0));
        }
        return out;
    }

    match fill {
        ColumnFill::Auto => {
            let col_limit = max_h.unwrap_or(i32::MAX);
            let mut out = Vec::with_capacity(heights.len());
            let mut current_col = 0usize;
            let mut current_y = 0i32;

            for &h in heights {
                let item_h = h.max(0);
                if current_y > 0 && current_y.saturating_add(item_h) > col_limit && current_col + 1 < n {
                    current_col += 1;
                    current_y = 0;
                }
                out.push(Placement {
                    col: current_col,
                    y: current_y,
                });
                current_y = current_y.saturating_add(item_h);
            }
            out
        }
        ColumnFill::Balance => {
            let mut low = heights.iter().map(|&h| h.max(0)).max().unwrap_or(0);
            let mut high: i32 = heights
                .iter()
                .map(|&h| h.max(0))
                .fold(0i32, |acc, x| acc.saturating_add(x));
            if high <= 0 {
                return (0..heights.len()).map(|_| Placement { col: 0, y: 0 }).collect();
            }

            let can_partition = |cap: i32| -> bool {
                let mut cols_used = 1usize;
                let mut current_sum = 0i32;
                for &h in heights {
                    let item_h = h.max(0);
                    if current_sum > 0 && current_sum.saturating_add(item_h) > cap {
                        cols_used += 1;
                        current_sum = item_h;
                    } else {
                        current_sum = current_sum.saturating_add(item_h);
                    }
                }
                cols_used <= n
            };

            let mut best_cap = high;
            while low <= high {
                let mid = low + (high - low) / 2;
                if can_partition(mid) {
                    best_cap = mid;
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }

            let mut out = Vec::with_capacity(heights.len());
            let mut current_col = 0usize;
            let mut current_y = 0i32;
            let total_items = heights.len();

            for (i, &h) in heights.iter().enumerate() {
                let item_h = h.max(0);
                let remaining_items = total_items - i;
                let remaining_cols = n - current_col;

                if current_col + 1 < n {
                    let exceeds_cap = current_y > 0 && current_y.saturating_add(item_h) > best_cap;
                    let must_split_for_remaining = remaining_items <= remaining_cols && current_y > 0;
                    if exceeds_cap || must_split_for_remaining {
                        current_col += 1;
                        current_y = 0;
                    }
                }

                out.push(Placement {
                    col: current_col,
                    y: current_y,
                });
                current_y = current_y.saturating_add(item_h);
            }
            out
        }
    }
}

/// 子の高さ列を受け取り、各子をどの列のどの高さへ置くかを決める（純粋関数）。
///
/// 不変条件 M-6 のとおり「その時点で高さが最小の列」へ順に入れる貪欲法。
/// 同じ高さの列が複数あるときは**左の列を優先**する（見た目の安定のため。
/// 右から埋まると 1 件だけのときに不自然に右へ寄る）。
///
/// 返り値の長さは `heights` と同じ。列数が 0 のときは全て 0 列目へ倒す。
///
/// 計算量: **O(子数 × 列数)**。列数は高々数十なので実用上問題ない。
pub fn assign_to_columns(heights: &[i32], n_cols: usize) -> Vec<Placement> {
    let n = n_cols.max(1);
    let mut bottoms = alloc::vec![0i32; n];
    let mut out = Vec::with_capacity(heights.len());
    for &h in heights {
        // 最小の列を探す。`<` で比較するので同値なら先に見た（左の）列が残る。
        let mut min_i = 0usize;
        for i in 1..n {
            if bottoms[i] < bottoms[min_i] {
                min_i = i;
            }
        }
        out.push(Placement {
            col: min_i,
            y: bottoms[min_i],
        });
        bottoms[min_i] = bottoms[min_i].saturating_add(h.max(0));
    }
    out
}

/// 振り分け後の各列の高さを返す（純粋関数）。
pub fn column_heights_balanced(
    heights: &[i32],
    n_cols: usize,
    fill: ColumnFill,
    max_h: Option<i32>,
) -> Vec<i32> {
    let n = n_cols.max(1);
    let places = assign_to_columns_balanced(heights, n, fill, max_h);
    let mut cols_h = alloc::vec![0i32; n];
    for (idx, p) in places.into_iter().enumerate() {
        if p.col < n {
            let item_h = heights.get(idx).copied().unwrap_or(0).max(0);
            cols_h[p.col] = cols_h[p.col].max(p.y.saturating_add(item_h));
        }
    }
    cols_h
}

/// 振り分け後の各列の高さを返す（純粋関数）。
///
/// 多段組ブロック自身の高さは、この最大値になる。
pub fn column_heights(heights: &[i32], n_cols: usize) -> Vec<i32> {
    let n = n_cols.max(1);
    let mut bottoms = alloc::vec![0i32; n];
    for &h in heights {
        let mut min_i = 0usize;
        for i in 1..n {
            if bottoms[i] < bottoms[min_i] {
                min_i = i;
            }
        }
        bottoms[min_i] = bottoms[min_i].saturating_add(h.max(0));
    }
    bottoms
}

/// `column-gap`（または `gap`）の文字列値を解析してピクセル値へ解決する（純粋関数）。
/// 既定値 `normal` は `1em` 相当（`font_px`）。未指定または不正値は `font_px`（または 16px）。
pub fn resolve_column_gap(gap_str: Option<&str>, avail_w: i32, font_px: f32) -> i32 {
    let s = match gap_str {
        Some(v) => v.trim(),
        None => return (if font_px > 0.0 { font_px } else { 16.0 }) as i32,
    };
    if s.is_empty() || s.eq_ignore_ascii_case("normal") {
        return (if font_px > 0.0 { font_px } else { 16.0 }) as i32;
    }
    let font = if font_px > 0.0 { font_px } else { 16.0 };
    if let Some(pct) = s.strip_suffix('%') {
        let v = pct.trim().parse::<f32>().unwrap_or(0.0);
        (v * avail_w as f32 / 100.0).max(0.0) as i32
    } else if let Some(rem) = s.strip_suffix("rem") {
        (rem.trim().parse::<f32>().unwrap_or(0.0) * 16.0).max(0.0) as i32
    } else if let Some(em) = s.strip_suffix("em") {
        (em.trim().parse::<f32>().unwrap_or(0.0) * font).max(0.0) as i32
    } else if let Some(pt) = s.strip_suffix("pt") {
        (pt.trim().parse::<f32>().unwrap_or(0.0) * 4.0 / 3.0).max(0.0) as i32
    } else if let Some(px) = s.strip_suffix("px") {
        px.trim().parse::<f32>().unwrap_or(0.0).max(0.0) as i32
    } else if let Ok(v) = s.parse::<f32>() {
        v.max(0.0) as i32
    } else {
        font as i32
    }
}

/// 子要素の特性（通常フローで列内に入るか、全幅スパンするか）。
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ChildKind {
    ColumnItem { height: i32 },
    Spanner { height: i32 },
}

/// 子要素の最終配置結果。
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ChildPlacement {
    /// 何列目か（Spanner の場合は 0）。
    pub col: usize,
    /// 全幅スパンかどうか。
    pub is_span: bool,
    /// コンテナ内での上端 y 座標（px）。
    pub y: i32,
}

/// 子要素群を段抜き（`column-span: all`）および充填モード（`column-fill`）を考慮してセグメント化し配置する（純粋関数）。
/// W3C CSS Multi-column Layout Level 1 §6 / §7 準拠。
///
/// 戻り値: (各子の配置情報, 全セグメントおよび Spanner を合わせた合計高さ)
pub fn assign_children_with_spans_ex(
    items: &[ChildKind],
    n_cols: usize,
    fill: ColumnFill,
    max_h: Option<i32>,
) -> (Vec<ChildPlacement>, i32) {
    let mut out = Vec::with_capacity(items.len());
    let mut y_base = 0i32;

    let mut i = 0;
    while i < items.len() {
        match items[i] {
            ChildKind::Spanner { height } => {
                out.push(ChildPlacement {
                    col: 0,
                    is_span: true,
                    y: y_base,
                });
                y_base = y_base.saturating_add(height.max(0));
                i += 1;
            }
            ChildKind::ColumnItem { .. } => {
                // 次の Spanner までの ColumnItem 群（セグメント）を収集
                let seg_start = i;
                while i < items.len() {
                    if let ChildKind::Spanner { .. } = items[i] {
                        break;
                    }
                    i += 1;
                }
                let seg_heights: Vec<i32> = items[seg_start..i]
                    .iter()
                    .map(|it| match it {
                        ChildKind::ColumnItem { height } => *height,
                        _ => unreachable!(),
                    })
                    .collect();

                let seg_places = assign_to_columns_balanced(&seg_heights, n_cols, fill, max_h);
                let seg_col_heights = column_heights_balanced(&seg_heights, n_cols, fill, max_h);
                let seg_max_h = seg_col_heights.into_iter().max().unwrap_or(0);

                for p in seg_places {
                    out.push(ChildPlacement {
                        col: p.col,
                        is_span: false,
                        y: y_base.saturating_add(p.y),
                    });
                }
                y_base = y_base.saturating_add(seg_max_h);
            }
        }
    }

    (out, y_base)
}

/// 子要素群を段抜き（`column-span: all`）を考慮してセグメント化し配置する（純粋関数）。
/// W3C CSS Multi-column Layout Level 1 §6 準拠。
///
/// 戻り値: (各子の配置情報, 全セグメントおよび Spanner を合わせた合計高さ)
pub fn assign_children_with_spans(
    items: &[ChildKind],
    n_cols: usize,
) -> (Vec<ChildPlacement>, i32) {
    let mut out = Vec::with_capacity(items.len());
    let mut y_base = 0i32;

    let mut i = 0;
    while i < items.len() {
        match items[i] {
            ChildKind::Spanner { height } => {
                out.push(ChildPlacement {
                    col: 0,
                    is_span: true,
                    y: y_base,
                });
                y_base = y_base.saturating_add(height.max(0));
                i += 1;
            }
            ChildKind::ColumnItem { .. } => {
                // 次の Spanner までの ColumnItem 群（セグメント）を収集
                let seg_start = i;
                while i < items.len() {
                    if let ChildKind::Spanner { .. } = items[i] {
                        break;
                    }
                    i += 1;
                }
                let seg_heights: Vec<i32> = items[seg_start..i]
                    .iter()
                    .map(|it| match it {
                        ChildKind::ColumnItem { height } => *height,
                        _ => unreachable!(),
                    })
                    .collect();

                let seg_places = assign_to_columns(&seg_heights, n_cols);
                let seg_col_heights = column_heights(&seg_heights, n_cols);
                let seg_max_h = seg_col_heights.into_iter().max().unwrap_or(0);

                for p in seg_places {
                    out.push(ChildPlacement {
                        col: p.col,
                        is_span: false,
                        y: y_base.saturating_add(p.y),
                    });
                }
                y_base = y_base.saturating_add(seg_max_h);
            }
        }
    }

    (out, y_base)
}

/// 段罫線のスタイル種別。
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RuleStyle {
    None,
    Solid,
    Dashed,
    Dotted,
    Double,
    Hidden,
}

impl RuleStyle {
    pub fn parse(s: &str) -> Self {
        match s.trim().to_ascii_lowercase().as_str() {
            "solid" => RuleStyle::Solid,
            "dashed" => RuleStyle::Dashed,
            "dotted" => RuleStyle::Dotted,
            "double" => RuleStyle::Double,
            "hidden" => RuleStyle::Hidden,
            _ => RuleStyle::None,
        }
    }
}

/// 段罫線の解決済みスタイル指定。
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ColumnRuleStyle {
    pub width: i32,
    pub style: RuleStyle,
    pub color: u32,
}

/// 実際に描画される 1 本の段罫線の矩形情報。
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ColumnRuleRect {
    pub x: i32,
    pub y: i32,
    pub width: i32,
    pub height: i32,
    pub color: u32,
}

/// `column-rule` の太さを解析する（純粋関数）。
fn parse_rule_width(s: &str, font_px: f32) -> Option<i32> {
    match s.trim().to_ascii_lowercase().as_str() {
        "thin" => Some(1),
        "medium" => Some(3),
        "thick" => Some(5),
        _ => {
            let font = if font_px > 0.0 { font_px } else { 16.0 };
            let s = s.trim();
            if let Some(px) = s.strip_suffix("px") {
                px.trim().parse::<f32>().ok().filter(|f| f.is_finite() && *f >= 0.0).map(|f| f as i32)
            } else if let Some(em) = s.strip_suffix("em") {
                em.trim().parse::<f32>().ok().filter(|f| f.is_finite() && *f >= 0.0).map(|f| (f * font) as i32)
            } else if let Some(rem) = s.strip_suffix("rem") {
                rem.trim().parse::<f32>().ok().filter(|f| f.is_finite() && *f >= 0.0).map(|f| (f * 16.0) as i32)
            } else if let Some(pt) = s.strip_suffix("pt") {
                pt.trim().parse::<f32>().ok().filter(|f| f.is_finite() && *f >= 0.0).map(|f| (f * 4.0 / 3.0) as i32)
            } else if let Ok(v) = s.parse::<f32>() {
                if v.is_finite() && v >= 0.0 {
                    Some(v as i32)
                } else {
                    None
                }
            } else {
                None
            }
        }
    }
}

/// `column-rule`（ショートハンド）および個別ロングハンドをパースする（純粋関数）。
pub fn parse_column_rule(
    rule_shorthand: Option<&str>,
    width_val: Option<&str>,
    style_val: Option<&str>,
    color_val: Option<&str>,
    font_px: f32,
) -> Option<ColumnRuleStyle> {
    let mut width = None;
    let mut style = None;
    let mut color = None;

    // ショートハンドがあれば分解
    if let Some(sh) = rule_shorthand {
        for tok in sh.split_whitespace() {
            let t = tok.trim();
            if t.is_empty() {
                continue;
            }
            let st = RuleStyle::parse(t);
            if st != RuleStyle::None {
                style = Some(st);
                continue;
            }
            if t.eq_ignore_ascii_case("none") {
                style = Some(RuleStyle::None);
                continue;
            }
            if let Some(w) = parse_rule_width(t, font_px) {
                width = Some(w);
                continue;
            }
            if let Some(c) = crate::os_lib::css::parse_color(t) {
                color = Some(c);
                continue;
            }
        }
    }

    // 個別ロングハンドの上書き・補完
    if let Some(w_str) = width_val {
        if let Some(w) = parse_rule_width(w_str.trim(), font_px) {
            width = Some(w);
        }
    }
    if let Some(s_str) = style_val {
        style = Some(RuleStyle::parse(s_str.trim()));
    }
    if let Some(c_str) = color_val {
        if let Some(c) = crate::os_lib::css::parse_color(c_str.trim()) {
            color = Some(c);
        }
    }

    let final_style = style.unwrap_or(RuleStyle::None);
    if final_style == RuleStyle::None || final_style == RuleStyle::Hidden {
        return None;
    }
    let final_width = width.unwrap_or(3); // 既定 medium = 3px
    if final_width <= 0 {
        return None;
    }
    let final_color = color.unwrap_or(0xFF000000); // 既定黒

    Some(ColumnRuleStyle {
        width: final_width,
        style: final_style,
        color: final_color,
    })
}

/// 列一覧とギャップ、高さ、ルール定義から、各列間に引く段罫線の矩形一覧を計算する（純粋関数）。
pub fn compute_column_rules(
    cols: &[Column],
    gap: i32,
    y: i32,
    height: i32,
    rule: &ColumnRuleStyle,
) -> Vec<ColumnRuleRect> {
    if cols.len() <= 1 || rule.width <= 0 || height <= 0 {
        return Vec::new();
    }
    if rule.style == RuleStyle::None || rule.style == RuleStyle::Hidden {
        return Vec::new();
    }
    let mut out = Vec::with_capacity(cols.len() - 1);
    for i in 0..cols.len() - 1 {
        let left_edge = cols[i].x + cols[i].width;
        let right_edge = cols[i + 1].x;
        let center_x = if right_edge > left_edge {
            (left_edge + right_edge) / 2
        } else {
            left_edge + gap / 2
        };
        let x = center_x - rule.width / 2;
        out.push(ColumnRuleRect {
            x,
            y,
            width: rule.width,
            height,
            color: rule.color,
        });
    }
    out
}