// Incremental recalculation: caller-owned state with AST-extracted dependency
// edges. Only the dirty closure of changed cells is re-evaluated. Cycles and
// parse errors fall back to a full rebuild: cycle marking depends on DFS suffix
// order and parse_errors on DFS discovery order, neither of which is
// reproducible incrementally (correctness first).
/// 增量重算状态(调用方持有,单所有者)。由 `recalc_init` 创建,传给 `recalc_update`
/// 复用依赖图、AST 缓存与上次求值结果。
pub struct RecalcState {
priv precedents : Map[String, Array[String]]
priv dependents : Map[String, Array[String]]
priv mut raw : Map[String, Value]
priv circular : Map[String, Bool]
priv cache : ParseCache
priv mut has_cycle : Bool
priv mut range_fallback : Bool
}
/// 全量重算并建立增量状态;输出与 `recalc` 完全一致。
pub fn recalc_init(
grid : Grid,
options : EvalOptions
) -> (RecalcState, RecalcOutput) {
let state : RecalcState = {
precedents: Map::new(),
dependents: Map::new(),
raw: Map::new(),
circular: Map::new(),
cache: new_parse_cache(),
has_cycle: false,
range_fallback: false,
}
let out = full_rebuild(state, grid, options)
(state, out)
}
/// 增量重算:只重算 `changed` 的下游闭包,输出与 `recalc(grid, options)` 逐字段一致。
///
/// `changed` 必须列出相对上次调用网格内容发生变化的全部地址(含 Literal↔Formula
/// 切换与删除)。出现循环引用、解析错误或超大区域(>65536 格)时自动回退全量重算。
pub fn recalc_update(
state : RecalcState,
grid : Grid,
changed : Array[String],
options : EvalOptions
) -> RecalcOutput {
if state.has_cycle || state.range_fallback {
return full_rebuild(state, grid, options)
}
for key in changed {
remove_edges(state, key)
match grid.cells.get(key) {
Some(cell) => add_edges(state, key, cell)
None => ()
}
}
if state.range_fallback {
return full_rebuild(state, grid, options)
}
let dirty : Map[String, Bool] = Map::new()
let queue : Array[String] = []
for key in changed {
if !dirty.contains(key) {
dirty[key] = true
queue.push(key)
}
}
let mut i = 0
while i < queue.length() {
let key = queue[i]
match state.dependents.get(key) {
Some(deps) =>
for d in deps {
if !dirty.contains(d) {
dirty[d] = true
queue.push(d)
}
}
None => ()
}
i += 1
}
let ctx = new_ctx(grid, options, Some(state.cache.entries))
for key, v in state.raw {
if !dirty.contains(key) {
ctx.cache[key] = v
}
}
for key, cell in grid.cells {
if dirty.contains(key) {
match cell {
Formula(_) => {
let _ = cell_value(ctx, key)
}
Literal(_) => ()
}
}
}
if ctx.circular.length() > 0 {
return full_rebuild(state, grid, options)
}
for _, cell in grid.cells {
match cell {
Formula(src) =>
match state.cache.entries.get(src) {
Some(Bad(_)) => return full_rebuild(state, grid, options)
_ => ()
}
Literal(_) => ()
}
}
let out : Map[String, EvalOutput] = Map::new()
for key, cell in grid.cells {
match cell {
Formula(_) => {
let raw = ctx.cache.get(key).unwrap()
state.raw[key] = raw
state.circular.remove(key)
out[key] = { value: scalar_output(raw), circular: false }
}
Literal(_) => ()
}
}
{ cells: out, parse_errors: [] }
}
fn full_rebuild(
state : RecalcState,
grid : Grid,
options : EvalOptions
) -> RecalcOutput {
let (out, raw) = recalc_impl(grid, options, Some(state.cache.entries))
state.raw = raw
state.circular.clear()
state.has_cycle = false
for key, o in out.cells {
if o.circular {
state.circular[key] = true
state.has_cycle = true
}
}
state.precedents.clear()
state.dependents.clear()
state.range_fallback = false
for key, cell in grid.cells {
add_edges(state, key, cell)
}
out
}
fn add_edges(state : RecalcState, key : String, cell : Cell) -> Unit {
match cell {
Literal(_) => ()
Formula(src) => {
let refs : Array[String] = []
let ok = match state.cache.parse(src) {
Some(e) => expr_refs(e, refs, 65536)
None => true
}
if !ok {
state.range_fallback = true
return
}
let seen : Map[String, Bool] = Map::new()
let uniq : Array[String] = []
for r in refs {
if !seen.contains(r) {
seen[r] = true
uniq.push(r)
}
}
state.precedents[key] = uniq
for r in uniq {
match state.dependents.get(r) {
Some(arr) => arr.push(key)
None => state.dependents[r] = [key]
}
}
}
}
}
fn remove_edges(state : RecalcState, key : String) -> Unit {
match state.precedents.get(key) {
Some(refs) => {
for r in refs {
match state.dependents.get(r) {
Some(arr) => state.dependents[r] = arr.filter(x => x != key)
None => ()
}
}
state.precedents.remove(key)
}
None => ()
}
state.raw.remove(key)
state.circular.remove(key)
}
// Collect referenced cell keys from an AST (ranges expanded row-major).
// Returns false when the cap is exceeded; shared with iterative/explain.
fn expr_refs(e : @syntax.Expr, out : Array[String], cap : Int) -> Bool {
match e {
Lit(_) => true
Ref(addr) => {
out.push(addr.key())
out.length() <= cap
}
Range(lo, hi) => {
for r in lo.row..=hi.row {
for c in lo.col..=hi.col {
let a : CellAddr = { row: r, col: c, abs_row: false, abs_col: false }
out.push(a.key())
if out.length() > cap {
return false
}
}
}
true
}
Unary(_, sub) => expr_refs(sub, out, cap)
Binary(_, l, r) => expr_refs(l, out, cap) && expr_refs(r, out, cap)
Call(_, args) => {
for a in args {
if !expr_refs(a, out, cap) {
return false
}
}
true
}
}
}
/// 网格依赖图(AST 级提取,区域展开、去重):公式格 → 直接前驱 / 格 → 直接下游。
pub(all) struct DepGraph {
/// 公式格 → 引用的单元格地址。
precedents : Map[String, Array[String]]
/// 单元格 → 直接引用它的公式格。
dependents : Map[String, Array[String]]
} derive(Show, Debug)
/// 提取整网格依赖图;任一区域超过 65536 格时返回 `None`(调用方降级)。
pub fn dependency_graph(grid : Grid) -> DepGraph? {
let cache = new_parse_cache()
let g : DepGraph = { precedents: Map::new(), dependents: Map::new() }
for key, cell in grid.cells {
match cell {
Formula(src) => {
let refs : Array[String] = []
let ok = match cache.parse(src) {
Some(e) => expr_refs(e, refs, 65536)
None => true
}
if !ok {
return None
}
let seen : Map[String, Bool] = Map::new()
let uniq : Array[String] = []
for r in refs {
if !seen.contains(r) {
seen[r] = true
uniq.push(r)
}
}
g.precedents[key] = uniq
for r in uniq {
match g.dependents.get(r) {
Some(arr) => arr.push(key)
None => g.dependents[r] = [key]
}
}
}
Literal(_) => ()
}
}
Some(g)
}