atmos/os_lib/css/

rule_index.rs

//! セレクタ右端キーによるルールインデックス（カスケード高速化）。
//!
//! ## 背景
//! カスケードは「全ルール × 全ノード」を総当たりで `matches_selector` に掛けていた。
//! 実サイト（www.sugi-lab.net）では Font Awesome を含めて **2403 ルール**あり、
//! ノード数 365 との組み合わせで 1 回のレイアウトに約 50 秒かかっていた。
//! JS タイマーが毎フレーム DOM を dirty にするため、この 50 秒が延々と繰り返され、
//! ページが一度も描画完了しない状態になっていた。
//!
//! ## 手法
//! ブラウザ実装と同じく、セレクタの**右端コンパウンド**から絞り込みキーを 1 つ取り、
//! `#id` / `.class` / `tag` のバケットへ振り分けておく。ある要素に対しては
//! 「その要素の id / class / タグ名に対応するバケット」＋「ユニバーサルバケット」
//! だけを照合すればよく、`.fa-xxx` のような数千件のアイコンルールは
//! 対象要素がそのクラスを持たない限り一切触らない。
//!
//! キーの選択は右端コンパウンド内で **id > class > tag > universal** の順。
//! 右端が `:hover` や `[attr]` だけで id/class/tag を持たない場合は
//! **必ず universal 扱い**にする（絞り込みで取りこぼすと描画が壊れるため、
//! 判断がつかないものは常に照合する側へ倒す）。
//!
//! 本モジュールはグローバル状態にもハードウェアにも依存しない純粋ロジックのみで構成し、
//! ホスト側の単体試験で契約を固定する。

extern crate alloc;

use super::types::{Rule, Selector, SimpleSelector};
use alloc::collections::BTreeMap;
use alloc::string::{String, ToString};
use alloc::vec::Vec;

/// ルールを振り分けるバケットの種類。
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub enum RuleKey {
    /// 右端が `#id` を含む。
    Id(String),
    /// 右端が `.class` を含む（id は含まない）。最初のクラスを代表キーにする。
    Class(String),
    /// 右端がタグ名のみ（id/class 無し）。
    Tag(String),
    /// 右端から絞り込みキーを決められない（`*`、擬似クラスのみ、属性のみ 等）。
    /// このバケットのルールは全要素に対して照合する。
    Universal,
}

/// インデックス操作の引数が不正だった場合のエラー。
#[derive(Debug, PartialEq, Eq, Clone)]
pub enum IndexError {
    /// 要素のタグ名が空。要素ノードには必ずタグ名がある前提が崩れている。
    EmptyTagName,
}

/// 右端コンパウンドから絞り込みキーを決める。
fn key_from_simple(s: &SimpleSelector) -> RuleKey {
    if let Some(id) = &s.id {
        if !id.is_empty() {
            return RuleKey::Id(id.clone());
        }
    }
    if let Some(c) = s.class.iter().find(|c| !c.is_empty()) {
        return RuleKey::Class(c.clone());
    }
    if let Some(t) = &s.tag_name {
        if !t.is_empty() {
            // HTML のタグ名は大文字小文字を区別しないので正規化する。
            return RuleKey::Tag(t.to_lowercase());
        }
    }
    // `*` / 擬似クラスのみ / 属性のみ → 絞り込めないので全件照合側へ。
    RuleKey::Universal
}

/// セレクタ 1 本の絞り込みキーを返す。チェーンなら**右端**のステップを見る。
pub fn rightmost_key(sel: &Selector) -> RuleKey {
    match sel {
        Selector::Simple(s) => key_from_simple(s),
        Selector::Chain(steps) => match steps.last() {
            Some(step) => key_from_simple(&step.simple),
            // 空チェーンは本来あり得ないが、取りこぼすより全件照合が安全。
            None => RuleKey::Universal,
        },
    }
}

/// スタイルシート内のルールを右端キーで振り分けた索引。
/// 保持するのは元の `rules` スライスに対する**添字**のみで、ルール本体は複製しない。
#[derive(Debug, Default)]
pub struct RuleIndex {
    by_id: BTreeMap<String, Vec<usize>>,
    by_class: BTreeMap<String, Vec<usize>>,
    by_tag: BTreeMap<String, Vec<usize>>,
    universal: Vec<usize>,
    rule_count: usize,
    /// ルールごとの動的疑似クラス使用ビット（bit0=hover, bit1=focus, bit2=active）。
    ///
    /// 「そのルールが `:hover` を使うか」は**ノードに依存しない**。
    /// 以前はカスケードがノードごとに候補ルール全部へ `rule_uses_state` を
    /// 呼んでおり、同じ答えを N×C 回計算し直していた。
    /// 索引を作るのと同じ 1 回の走査で求めておく。
    state_masks: Vec<u8>,
}

/// `state_masks` のビット位置。
pub const STATE_HOVER: u8 = 1 << 0;
pub const STATE_FOCUS: u8 = 1 << 1;
pub const STATE_ACTIVE: u8 = 1 << 2;

impl RuleIndex {
    /// 与えられた候補ルール群が使う動的疑似クラスのビットを OR して返す。
    ///
    /// 範囲外の添字が混ざっていたら `None`。呼び出し側は
    /// 「全状態を計算する」へフォールバックする（取りこぼしより遅い方を選ぶ）。
    ///
    /// 計算量: **O(C)**。
    ///
    /// 【2026-08-05】グローバルの `ACTIVE` を介さずに問い合わせられるよう、
    /// `active_states_of` から本体をこちらへ移した。
    /// 試験がグローバル状態に依存していたため、**並列実行される他の試験が
    /// `clear_active()` した瞬間に `None` が返って落ちていた**
    /// （実測: 8 回に 1 回程度。`spec/logging_policy.md` T-1 の再発）。
    /// 索引そのものの性質は索引だけで確かめられる。
    pub fn states_of(&self, cands: &[usize]) -> Option<u8> {
        let mut m = 0u8;
        for &i in cands {
            match self.state_masks.get(i) {
                Some(bits) => m |= bits,
                None => return None,
            }
            if m == STATE_HOVER | STATE_FOCUS | STATE_ACTIVE {
                break;
            }
        }
        Some(m)
    }

    /// ルール列から索引を構築する。
    ///
    /// 1 ルールが複数セレクタ（`a, b, c`）を持つ場合、**いずれか**のセレクタが
    /// マッチすればそのルールは適用対象なので、全セレクタのキーへ登録する。
    pub fn build(rules: &[Rule]) -> Self {
        let mut idx = RuleIndex {
            rule_count: rules.len(),
            ..Default::default()
        };
        idx.state_masks = rules
            .iter()
            .map(|r| {
                let mut m = 0u8;
                if super::pseudo_state::rule_uses_state(r, "hover") {
                    m |= STATE_HOVER;
                }
                if super::pseudo_state::rule_uses_state(r, "focus") {
                    m |= STATE_FOCUS;
                }
                if super::pseudo_state::rule_uses_state(r, "active") {
                    m |= STATE_ACTIVE;
                }
                m
            })
            .collect();
        for (i, rule) in rules.iter().enumerate() {
            if rule.selectors.is_empty() {
                // セレクタが無いルールは判定不能。取りこぼさないよう全件照合側へ。
                idx.universal.push(i);
                continue;
            }
            for sel in &rule.selectors {
                match rightmost_key(sel) {
                    RuleKey::Id(v) => push_unique(idx.by_id.entry(v).or_default(), i),
                    RuleKey::Class(v) => push_unique(idx.by_class.entry(v).or_default(), i),
                    RuleKey::Tag(v) => push_unique(idx.by_tag.entry(v).or_default(), i),
                    RuleKey::Universal => push_unique(&mut idx.universal, i),
                }
            }
        }
        idx
    }

    /// 索引が対象としているルール総数。
    pub fn rule_count(&self) -> usize {
        self.rule_count
    }

    /// 常時照合が必要な（絞り込めなかった）ルール数。
    /// これが総数に近いほど索引の効果は薄い。
    pub fn universal_count(&self) -> usize {
        self.universal.len()
    }

    /// ある要素について照合すべきルールの添字を**昇順・重複なし**で返す。
    /// 昇順なのはカスケードの後勝ち規則（同特異度なら後のルールが勝つ）を
    /// 元の宣言順のまま保つため。
    ///
    /// 引数が不正（タグ名が空）なときは黙って戻らず、エラーログを出して `Err` を返す。
    /// 呼び出し側は「全ルールを照合する」従来動作へフォールバックすること
    /// （絞り込みを誤って描画が欠けるより、遅くても正しい方を選ぶ）。
    pub fn candidates(
        &self,
        tag: &str,
        id: Option<&str>,
        classes: &[String],
    ) -> Result<Vec<usize>, IndexError> {
        if tag.trim().is_empty() {
            crate::error!(
                "[CSS][RULEIDX] 要素のタグ名が空です (id={:?} classes={})。全ルール照合へフォールバックします",
                id,
                classes.len()
            );
            return Err(IndexError::EmptyTagName);
        }

        let mut list: Vec<usize> = Vec::with_capacity(self.universal.len() + 16);
        list.extend_from_slice(&self.universal);

        if let Some(id) = id {
            if !id.is_empty() {
                if let Some(v) = self.by_id.get(id) {
                    list.extend_from_slice(v);
                }
            }
        }
        for c in classes {
            if !c.is_empty() {
                if let Some(v) = self.by_class.get(c) {
                    list.extend_from_slice(v);
                }
            }
        }
        if let Some(v) = self.by_tag.get(&tag.to_lowercase()) {
            list.extend_from_slice(v);
        }

        list.sort_unstable();
        list.dedup();

        Ok(list)
    }
}

/// 既に末尾にある添字は積まない（同一ルールが複数セレクタで同じバケットへ来る場合）。
fn push_unique(v: &mut Vec<usize>, i: usize) {
    if v.last() != Some(&i) {
        v.push(i);
    }
}

/// `RuleKey` を人が読める文字列にする（診断ログ用）。
impl RuleKey {
    pub fn describe(&self) -> String {
        match self {
            RuleKey::Id(v) => {
                let mut s = String::from("#");
                s.push_str(v);
                s
            }
            RuleKey::Class(v) => {
                let mut s = String::from(".");
                s.push_str(v);
                s
            }
            RuleKey::Tag(v) => v.clone(),
            RuleKey::Universal => "*".to_string(),
        }
    }
}