atmos/os_lib/js/

cycle_gc.rs

//! 参照カウントでは回収できない循環ゴミの回収（試行削除 / trial deletion）。
//!
//! 【2026-10-19】JS の値は `Rc<RefCell<…>>` の参照カウントで管理しており、
//! 「関数呼び出しのスコープ → 中で作った関数 → そのスコープ」のような循環は
//! ページを閉じるまで解放されなかった。YouTube の視聴ページ（kevlar_base 10.8MB）の
//! 実行中に 512MB のヒープを使い切っていた。
//!
//! ## 方式
//! 生きている `Obj` と `Scope` をすべて台帳（[`Registry`]）に登録しておき、回収時に
//! 1. 台帳の全節点について、節点どうしの参照（辺）の本数を数える（内部参照数）。
//! 2. 強参照数 − 内部参照数 > 0 の節点は、台帳の外（Rust のスタック・大域・DOM 側の
//!    リスナ等）から参照されている「根」。
//! 3. 根から辺をたどって届く節点に印を付ける。印の無い節点は外から届かない循環ゴミ。
//! 4. ゴミの中身（プロパティ・変数・原型など）を空にして循環を断ち、参照カウントで
//!    解放させる。
//!
//! ## 安全性
//! - 数える辺は「実在する強参照」だけ（数え漏れは安全側: その先の節点が根に見える）。
//!   共有され得る中間の `Rc`（Promise の状態など）の先は数えない。
//! - 借用中で中身を読めない節点は根として扱い、その先も数えない（同じく安全側）。
//! - Rust のスタックが保持している値は強参照数に表れるので、実行の途中でも回収できる。
//! - JS は 1 つのスレッド（ブラウザのアプリのプロセス）でしか動かない前提。台帳自体は
//!   spin ロックで守るが、回収は台帳の全節点を触るので、別スレッドで同時に JS が動く
//!   構成になったら台帳をスレッドごとに分ける必要がある。
//! - `Obj`・`Scope` を `Rc` から取り出したり、中身ごと入れ替えたりしてはならない
//!   （台帳の番地と中身の番号がずれる）。

use alloc::rc::Rc;
use alloc::vec::Vec;
use core::cell::RefCell;

use super::interp::Scope;
use super::value::{Obj, ObjKind, Value};

use core::sync::atomic::{AtomicUsize, Ordering};

/// 前回の回収から登録した数。
static MADE: AtomicUsize = AtomicUsize::new(0);
/// 次に回収する登録数（前回の生存数に比例させ、回収の手間を償却で O(1) にする）。
static NEXT_AT: AtomicUsize = AtomicUsize::new(MIN_INTERVAL);
/// 回収の最小間隔（登録数）。
const MIN_INTERVAL: usize = 100_000;

/// 回収する頃合いか（呼び出し経路から頻繁に呼ぶので原子変数だけ見る）。
pub fn should_collect() -> bool {
    MADE.load(Ordering::Relaxed) >= NEXT_AT.load(Ordering::Relaxed)
}

/// 頃合いなら回収する。
pub fn maybe_collect() -> Option<GcStats> {
    if !should_collect() {
        return None;
    }
    let st = collect(true);
    let live = (st.objs + st.scopes).saturating_sub(st.garbage_objs + st.garbage_scopes);
    NEXT_AT.store(MIN_INTERVAL + live, Ordering::Relaxed);
    Some(st)
}

/// 未登録を表す台帳の番号。
pub const NO_SLOT: u32 = u32::MAX;

/// 生きている `Obj`・`Scope` の台帳（`Rc::as_ptr` の番地。空きは 0）。
struct Registry {
    objs: Vec<usize>,
    obj_free: Vec<u32>,
    scopes: Vec<usize>,
    scope_free: Vec<u32>,
}

static REGISTRY: spin::Mutex<Registry> = spin::Mutex::new(Registry {
    objs: Vec::new(),
    obj_free: Vec::new(),
    scopes: Vec::new(),
    scope_free: Vec::new(),
});

fn put(list: &mut Vec<usize>, free: &mut Vec<u32>, p: usize) -> u32 {
    if let Some(i) = free.pop() {
        if let Some(e) = list.get_mut(i as usize) {
            *e = p;
            return i;
        }
    }
    list.push(p);
    (list.len() - 1) as u32
}

/// 作った `Obj` を台帳に載せる（`value.rs` の構築関数が呼ぶ）。
pub fn track_obj(rc: Rc<RefCell<Obj>>) -> Rc<RefCell<Obj>> {
    MADE.fetch_add(1, Ordering::Relaxed);
    let p = Rc::as_ptr(&rc) as usize;
    let slot = {
        let mut r = REGISTRY.lock();
        let Registry { objs, obj_free, .. } = &mut *r;
        put(objs, obj_free, p)
    };
    if let Ok(mut b) = rc.try_borrow_mut() {
        b.gc_slot = slot;
    }
    rc
}

/// 作った `Scope` を台帳に載せる。
pub fn track_scope(rc: Rc<RefCell<Scope>>) -> Rc<RefCell<Scope>> {
    MADE.fetch_add(1, Ordering::Relaxed);
    let p = Rc::as_ptr(&rc) as usize;
    let slot = {
        let mut r = REGISTRY.lock();
        let Registry { scopes, scope_free, .. } = &mut *r;
        put(scopes, scope_free, p)
    };
    if let Ok(mut b) = rc.try_borrow_mut() {
        b.gc_slot = slot;
    }
    rc
}

/// `Obj` の解放時に台帳から外す。
pub fn untrack_obj(slot: u32) {
    if slot == NO_SLOT {
        return;
    }
    let mut r = REGISTRY.lock();
    if let Some(e) = r.objs.get_mut(slot as usize) {
        *e = 0;
        r.obj_free.push(slot);
    }
}

/// `Scope` の解放時に台帳から外す。
pub fn untrack_scope(slot: u32) {
    if slot == NO_SLOT {
        return;
    }
    let mut r = REGISTRY.lock();
    if let Some(e) = r.scopes.get_mut(slot as usize) {
        *e = 0;
        r.scope_free.push(slot);
    }
}


/// 台帳の節点（一時的に強参照を 1 本持つ）。
enum Node {
    O(Rc<RefCell<Obj>>),
    S(Rc<RefCell<Scope>>),
}

impl Node {
    fn strong(&self) -> usize {
        match self {
            Node::O(r) => Rc::strong_count(r),
            Node::S(r) => Rc::strong_count(r),
        }
    }
}

/// 節点が直接持つ強参照の先（節点番号）を `out` に積む。読めなければ false。
/// 節点番号は `Obj` が台帳の番号、`Scope` が `n_objs + 台帳の番号`。
/// 番号を読めない（借用中・未登録の）先は積まない（安全側）。
fn children(n: &Node, n_objs: usize, out: &mut Vec<usize>) -> bool {
    let obj = |o: &Rc<RefCell<Obj>>, out: &mut Vec<usize>| {
        if let Ok(b) = o.try_borrow() {
            if b.gc_slot != NO_SLOT {
                out.push(b.gc_slot as usize);
            }
        }
    };
    let scope = |s: &Rc<RefCell<Scope>>, out: &mut Vec<usize>| {
        if let Ok(b) = s.try_borrow() {
            if b.gc_slot != NO_SLOT {
                out.push(n_objs + b.gc_slot as usize);
            }
        }
    };
    let val = |v: &Value, out: &mut Vec<usize>| {
        if let Value::Object(o) = v {
            obj(o, out);
        }
    };
    match n {
        Node::S(s) => {
            let Ok(b) = s.try_borrow() else { return false };
            if let Some(p) = &b.parent {
                scope(p, out);
            }
            for v in b.vars.values() {
                val(v, out);
            }
            true
        }
        Node::O(o) => {
            let Ok(b) = o.try_borrow() else { return false };
            if let Some(p) = &b.proto {
                obj(p, out);
            }
            for v in b.props.values() {
                val(v, out);
            }
            for (_, a) in b.accessors.iter() {
                if let Some(g) = &a.get {
                    val(g, out);
                }
                if let Some(s) = &a.set {
                    val(s, out);
                }
            }
            match &b.kind {
                ObjKind::Array(items) | ObjKind::SetObj(items) => {
                    for v in items {
                        val(v, out);
                    }
                }
                ObjKind::MapObj(entries) => {
                    for (k, v) in entries {
                        val(k, out);
                        val(v, out);
                    }
                }
                ObjKind::Function(f) => {
                    scope(&f.closure, out);
                    if let Some(bt) = &f.bound_this {
                        val(bt, out);
                    }
                }
                ObjKind::Proxy { target, handler } => {
                    obj(target, out);
                    obj(handler, out);
                }
                ObjKind::Bound { target, bound_this, bound_args } => {
                    val(target, out);
                    val(bound_this, out);
                    for v in bound_args {
                        val(v, out);
                    }
                }
                // Promise・Generator・RegExp 等は共有され得る中間の Rc 越しなので数えない（安全側）。
                _ => {}
            }
            true
        }
    }
}

/// 回収の結果。
#[derive(Debug, Default, Clone, Copy)]
pub struct GcStats {
    pub objs: usize,
    pub scopes: usize,
    pub garbage_objs: usize,
    pub garbage_scopes: usize,
}

/// 循環ゴミを探す。`free` が真なら回収もする（偽なら数えるだけ）。
pub fn collect(free: bool) -> GcStats {
    // 1. 台帳の各節点に一時的な強参照を持つ。強参照を増やすだけで解放は起きないので、
    //    ロックを持ったまま行ってよい（解放時の台帳操作と競合しない）。
    let (nodes, n_objs) = {
        let r = REGISTRY.lock();
        MADE.store(0, Ordering::Relaxed);
        let n_objs = r.objs.len();
        let mut nodes: Vec<Option<Node>> = Vec::with_capacity(n_objs + r.scopes.len());
        for &p in &r.objs {
            nodes.push((p != 0).then(|| {
                // SAFETY: 台帳の番地は `Rc::as_ptr` で得たもので、解放（Drop）時に台帳から
                // 外す。ロック中なので外される途中の節点は無い。
                Node::O(unsafe {
                    let p = p as *const RefCell<Obj>;
                    Rc::increment_strong_count(p);
                    Rc::from_raw(p)
                })
            }));
        }
        for &p in &r.scopes {
            nodes.push((p != 0).then(|| {
                // SAFETY: 同上。
                Node::S(unsafe {
                    let p = p as *const RefCell<Scope>;
                    Rc::increment_strong_count(p);
                    Rc::from_raw(p)
                })
            }));
        }
        (nodes, n_objs)
    };
    let n = nodes.len();
    let mut stats = GcStats::default();
    for (i, x) in nodes.iter().enumerate() {
        if x.is_some() {
            if i < n_objs {
                stats.objs += 1;
            } else {
                stats.scopes += 1;
            }
        }
    }

    // 2. 内部参照数を数える。読めない節点は根にする。
    // 状態: 下位 31 ビットが内部参照数、最上位ビットが「根・到達済み」の印。
    const MARK: u32 = 1 << 31;
    let mut st: Vec<u32> = alloc::vec![0; n];
    let mut buf: Vec<usize> = Vec::new();
    for (i, x) in nodes.iter().enumerate() {
        let Some(x) = x else { continue };
        buf.clear();
        if !children(x, n_objs, &mut buf) {
            st[i] |= MARK;
            continue;
        }
        for &j in &buf {
            if j < n && nodes[j].is_some() && (st[j] & !MARK) < (MARK - 1) {
                st[j] += 1;
            }
        }
    }

    // 3. 根（外から参照がある、または読めない）から印を付ける。
    let mut stack: Vec<usize> = Vec::new();
    for (i, x) in nodes.iter().enumerate() {
        let Some(x) = x else { continue };
        // 強参照数には、ここで持っている一時的な 1 本が含まれる。
        let internal = (st[i] & !MARK) as usize;
        if st[i] & MARK != 0 || x.strong().saturating_sub(1) > internal {
            st[i] |= MARK;
            stack.push(i);
        }
    }
    while let Some(i) = stack.pop() {
        let Some(x) = &nodes[i] else { continue };
        buf.clear();
        if !children(x, n_objs, &mut buf) {
            continue;
        }
        for &j in &buf {
            if j < n && nodes[j].is_some() && st[j] & MARK == 0 {
                st[j] |= MARK;
                stack.push(j);
            }
        }
    }
    drop(stack);
    drop(buf);

    // 4. 印の無い節点がゴミ。中身を取り出して循環を断つ。
    let mut taken: Vec<Value> = Vec::new();
    let mut taken_scopes: Vec<Rc<RefCell<Scope>>> = Vec::new();
    let mut taken_kinds: Vec<ObjKind> = Vec::new();
    for (i, x) in nodes.iter().enumerate() {
        let Some(x) = x else { continue };
        if st[i] & MARK != 0 {
            continue;
        }
        match x {
            Node::O(o) => {
                stats.garbage_objs += 1;
                if free {
                    if let Ok(mut b) = o.try_borrow_mut() {
                        if let Some(p) = b.proto.take() {
                            taken.push(Value::Object(p));
                        }
                        let props = core::mem::take(&mut b.props);
                        taken.extend(props.into_iter().map(|(_, v)| v));
                        let acc = core::mem::take(&mut b.accessors);
                        for (_, a) in acc {
                            taken.extend(a.get);
                            taken.extend(a.set);
                        }
                        taken_kinds.push(core::mem::replace(&mut b.kind, ObjKind::Plain));
                    }
                }
            }
            Node::S(s) => {
                stats.garbage_scopes += 1;
                if free {
                    if let Ok(mut b) = s.try_borrow_mut() {
                        if let Some(p) = b.parent.take() {
                            taken_scopes.push(p);
                        }
                        let vars = core::mem::take(&mut b.vars);
                        taken.extend(vars.into_values());
                    }
                }
            }
        }
    }
    drop(st);
    // 取り出した参照とゴミの節点を手放す（ここで参照カウントが 0 になり解放される）。
    drop(taken);
    drop(taken_scopes);
    drop(taken_kinds);
    // 節点の一時的な強参照を手放す。ゴミはここで解放され、Drop が台帳から外す
    // （ロックは持っていない）。
    drop(nodes);
    stats
}