formualizer_eval/engine/graph/

sheets.rs

use super::ast_utils::update_internal_sheet_references;
use super::*;
use formualizer_common::{ExcelError, ExcelErrorKind, LiteralValue};

const TOMBSTONE_SHEET_PREFIX: &str = "__FZ_MISSING_SHEET__";

impl DependencyGraph {
    /// Add a new sheet to the workbook.
    ///
    /// Creates a new sheet with the given name. If a sheet with this name
    /// already exists, returns its ID without error (idempotent operation).
    pub fn add_sheet(&mut self, name: &str) -> Result<SheetId, ExcelError> {
        if let Some(id) = self.sheet_reg.get_id(name) {
            return Ok(id);
        }

        let sheet_id = self.sheet_reg.id_for(name);
        self.sheet_indexes.entry(sheet_id).or_default();

        // Heal formulas that were waiting on this sheet name.
        self.heal_orphaned_formulas(name);
        self.resolve_pending_symbol("sheet", name);
        Ok(sheet_id)
    }

    /// Remove a sheet from the workbook.
    pub fn remove_sheet(&mut self, sheet_id: SheetId) -> Result<(), ExcelError> {
        let result = self.remove_sheet_impl(sheet_id);
        if result.is_ok() {
            self.drop_retired_ids_of_sheet(sheet_id);
        }
        self.authority_end_structural();
        result
    }

    /// Formula vertices with a cell or range reference to `sheet_id` in
    /// their text (names are handled through their definitions).
    fn formulas_referencing_sheet(&self, sheet_id: SheetId) -> Vec<VertexId> {
        use crate::engine::refs::{self, SemanticReference};
        struct Probe<'a> {
            graph: &'a DependencyGraph,
            sheet_id: SheetId,
            hit: bool,
        }
        fn visit(
            p: &mut Probe<'_>,
            r: SemanticReference<'_>,
            key: Option<SheetId>,
        ) -> Result<(), ExcelError> {
            let name = match &r {
                SemanticReference::Cell(c) => c.sheet.name(),
                SemanticReference::FiniteRange(rg) | SemanticReference::OpenRange(rg) => {
                    rg.sheet.name()
                }
                _ => return Ok(()),
            };
            let id = match (key, name) {
                (Some(id), _) => Some(id),
                (None, Some(n)) => p.graph.sheet_id(n),
                (None, None) => None,
            };
            if id == Some(p.sheet_id) {
                p.hit = true;
            }
            Ok(())
        }
        let mut out = Vec::new();
        for (v, f) in self.vertex_formulas.iter() {
            // Sheet references do not change under relocation: a member's
            // template names the member's sheets.
            let ast = f.root();
            let mut probe = Probe {
                graph: self,
                sheet_id,
                hit: false,
            };
            let _ = refs::visit_arena_references_keyed(
                ast,
                &mut probe,
                |p| p.graph.data_store(),
                |p| p.graph.sheet_reg(),
                visit,
            );
            if probe.hit {
                out.push(v);
            }
        }
        out.sort_unstable();
        out
    }

    fn remove_sheet_impl(&mut self, sheet_id: SheetId) -> Result<(), ExcelError> {
        self.authority_note_structural(true);
        let old_name = self.sheet_reg.name(sheet_id).to_string();
        if old_name.is_empty() {
            return Err(ExcelError::new(ExcelErrorKind::Value).with_message("Sheet does not exist"));
        }

        let sheet_count = self.sheet_reg.all_sheets().len();
        if sheet_count <= 1 {
            return Err(
                ExcelError::new(ExcelErrorKind::Value).with_message("Cannot remove the last sheet")
            );
        }

        self.begin_batch();

        // Symbol vertices are not sheet residents: workbook names would otherwise be
        // destroyed whenever the default sheet was removed. Sheet-scoped names on this
        // sheet are retired below, through the name registry that owns them.
        let vertices_to_delete: Vec<VertexId> = self
            .grid_vertices_in_sheet(sheet_id)
            .map(|(id, _)| id)
            .collect();

        // Formulas that reference this sheet: every cell or range reference
        // whose sheet is this one, from the formula text (legacy read its
        // edges and compressed range deps; same set).
        let formulas_to_update = self.formulas_referencing_sheet(sheet_id);

        for &formula_id in &formulas_to_update {
            self.tombstone_registry
                .add_orphan(old_name.clone(), formula_id);
            self.rewrite_formula_sheet_to_tombstone(formula_id, &old_name);
        }

        for formula_id in formulas_to_update {
            self.mark_as_ref_error(formula_id);
        }

        // Invalidate defined names that reference the removed sheet.
        //
        // In canonical (Arrow-truth) mode, cell/formula vertices do not cache values in the graph,
        // so we cannot rely on graph-stored ref errors. We must explicitly dirty name vertices and
        // their dependents so that subsequent evaluation updates Arrow overlays.
        let ref_err = LiteralValue::Error(ExcelError::new(ExcelErrorKind::Ref));
        let mut name_vertices_to_update: Vec<VertexId> = Vec::new();
        let mut dirty_vertices: Vec<VertexId> = Vec::new();

        for nr in self.named_ranges.values_mut() {
            match &nr.definition {
                NamedDefinition::Cell(c) if c.sheet_id == sheet_id => {
                    nr.definition = NamedDefinition::Literal(ref_err.clone());
                    name_vertices_to_update.push(nr.vertex);
                    dirty_vertices.push(nr.vertex);
                }
                NamedDefinition::Range(r)
                    if r.start.sheet_id == sheet_id || r.end.sheet_id == sheet_id =>
                {
                    nr.definition = NamedDefinition::Literal(ref_err.clone());
                    name_vertices_to_update.push(nr.vertex);
                    dirty_vertices.push(nr.vertex);
                }
                _ => {}
            }
        }
        for nr in self.sheet_named_ranges.values_mut() {
            match &nr.definition {
                NamedDefinition::Cell(c) if c.sheet_id == sheet_id => {
                    nr.definition = NamedDefinition::Literal(ref_err.clone());
                    name_vertices_to_update.push(nr.vertex);
                    dirty_vertices.push(nr.vertex);
                }
                NamedDefinition::Range(r)
                    if r.start.sheet_id == sheet_id || r.end.sheet_id == sheet_id =>
                {
                    nr.definition = NamedDefinition::Literal(ref_err.clone());
                    name_vertices_to_update.push(nr.vertex);
                    dirty_vertices.push(nr.vertex);
                }
                _ => {}
            }
        }

        // Update cached values for name vertices after the map borrows end.
        for vid in name_vertices_to_update {
            self.update_vertex_value_ref(vid, &ref_err);
        }
        for &vid in &dirty_vertices {
            self.mark_vertex_dirty(vid);
        }
        // Their readers, through the names' closure (after the resync).
        self.mark_dirty_many(&dirty_vertices);

        for vertex_id in vertices_to_delete {
            if let Some(cell_ref) = self.get_cell_ref_for_vertex(vertex_id) {
                self.cell_to_vertex.remove(&cell_ref);
            }

            self.remove_all_edges(vertex_id);

            if let Some(coord) = self.store.grid_addr(vertex_id)
                && let Some(index) = self.sheet_indexes.get_mut(&sheet_id)
            {
                index.remove_vertex(coord, vertex_id);
            }

            self.clear_pending_name_references(vertex_id);
            self.vertex_formulas.remove(&vertex_id);
            self.vertex_values.remove(&vertex_id);

            self.mark_deleted(vertex_id, true);
        }

        let sheet_names_to_remove: Vec<(SheetId, String)> = self
            .sheet_named_ranges
            .keys()
            .filter(|(sid, _)| *sid == sheet_id)
            .cloned()
            .collect();

        for key in sheet_names_to_remove {
            if let Some(named_range) = self.sheet_named_ranges.remove(&key) {
                if !self.config.case_sensitive_names {
                    let normalized = key.1.to_lowercase();
                    self.sheet_named_ranges_lookup
                        .remove(&(sheet_id, normalized));
                } else {
                    self.sheet_named_ranges_lookup.remove(&key);
                }
                self.mark_named_vertex_deleted(&named_range);
            }
        }

        self.sheet_indexes.remove(&sheet_id);

        if self.default_sheet_id == sheet_id
            && let Some(&new_default) = self.sheet_indexes.keys().next()
        {
            self.default_sheet_id = new_default;
        }

        self.sheet_reg.remove(sheet_id)?;
        self.end_batch();

        Ok(())
    }

    fn tombstone_marker(sheet_name: &str) -> String {
        format!("{TOMBSTONE_SHEET_PREFIX}{sheet_name}")
    }

    /// Whether `sheet_name` is a removed sheet's tombstone marker. Such a
    /// reference stays a preparation failure (`#REF!`) under either
    /// preparation policy: the tombstone registry heals it when the sheet
    /// returns, and `heal_orphaned_formulas` relies on the formula staying
    /// in the ref-error set until every removed sheet is back.
    pub(crate) fn is_tombstone_sheet(sheet_name: &str) -> bool {
        sheet_name.starts_with(TOMBSTONE_SHEET_PREFIX)
    }

    fn rewrite_formula_sheet_to_tombstone(&mut self, vertex_id: VertexId, sheet_name: &str) {
        let Some(ast) = self.get_formula(vertex_id) else {
            return;
        };

        let marker = Self::tombstone_marker(sheet_name);
        let mut updated_ast = ast.clone();
        updated_ast.update_sheet_references(Some(sheet_name), &marker);

        if updated_ast != ast {
            let updated_ast_id = self.data_store.store_ast(&updated_ast, &self.sheet_reg);
            self.materialize_vertex(vertex_id);
            self.vertex_formulas.insert(vertex_id, updated_ast_id);
        }
    }

    fn heal_orphaned_formulas(&mut self, sheet_name: &str) {
        let orphans = self.tombstone_registry.take_orphans(sheet_name);
        let marker = Self::tombstone_marker(sheet_name);

        for vertex_id in orphans {
            let Some(ast) = self.get_formula(vertex_id) else {
                continue;
            };

            // If the formula was edited while the sheet was missing, it may no longer
            // be in #REF! state; skip stale orphan entries in that case.
            if !self.is_ref_error(vertex_id) {
                continue;
            }

            // Heal only references that were explicitly tombstoned for this sheet.
            let mut updated_ast = ast.clone();
            updated_ast.update_sheet_references(Some(&marker), sheet_name);

            if updated_ast == ast {
                // Stale orphan entry (formula changed while sheet was missing).
                continue;
            }

            let updated_ast_id = self.data_store.store_ast(&updated_ast, &self.sheet_reg);
            self.materialize_vertex(vertex_id);
            self.vertex_formulas.insert(vertex_id, updated_ast_id);
            self.rebuild_formula_dependencies(vertex_id, &updated_ast);
        }
    }
    /// Rename an existing sheet.
    pub fn rename_sheet(&mut self, sheet_id: SheetId, new_name: &str) -> Result<(), ExcelError> {
        let result = self.rename_sheet_impl(sheet_id, new_name);
        self.authority_end_structural();
        result
    }

    fn rename_sheet_impl(&mut self, sheet_id: SheetId, new_name: &str) -> Result<(), ExcelError> {
        self.authority_note_structural(true);
        if new_name.is_empty() || new_name.len() > 255 {
            return Err(ExcelError::new(ExcelErrorKind::Value).with_message("Invalid sheet name"));
        }

        let old_name = self.sheet_reg.name(sheet_id).to_string();

        if old_name.is_empty() {
            return Err(ExcelError::new(ExcelErrorKind::Value).with_message("Sheet does not exist"));
        }

        if let Some(existing_id) = self.sheet_reg.get_id(new_name) {
            if existing_id != sheet_id {
                return Err(ExcelError::new(ExcelErrorKind::Value)
                    .with_message(format!("Sheet '{new_name}' already exists")));
            }
            return Ok(());
        }

        self.sheet_reg.rename(sheet_id, new_name)?;
        // Name formulas are not rewritten by a rename (legacy): one that
        // spells the old name kept its edges to this sheet's cells, so an
        // edit there re-evaluates it (to #REF!). The authority keeps that
        // edge through this alias; a sheet that takes the name ends it.
        let old_key = old_name.to_ascii_lowercase();
        self.renamed_sheet_aliases
            .retain(|k, _| *k != new_name.to_ascii_lowercase());
        self.renamed_sheet_aliases.insert(old_key, sheet_id);

        self.begin_batch();

        // Rescue formulas that were waiting for this exact sheet name to reappear.
        self.heal_orphaned_formulas(new_name);

        // Update still-valid references that explicitly mentioned the renamed sheet.
        let formulas_to_update: Vec<VertexId> = self.vertex_formulas.keys().collect();
        for formula_id in formulas_to_update {
            if let Some(ast) = self.get_formula(formula_id) {
                let mut updated_ast = ast.clone();
                updated_ast.update_sheet_references(Some(&old_name), new_name);

                if ast != updated_ast {
                    self.rebuild_formula_dependencies(formula_id, &updated_ast);
                    let updated_ast_id = self.data_store.store_ast(&updated_ast, &self.sheet_reg);
                    self.vertex_formulas.insert(formula_id, updated_ast_id);
                }
            }
        }

        self.end_batch();
        Ok(())
    }

    /// Duplicate an existing sheet.
    pub fn duplicate_sheet(
        &mut self,
        source_sheet_id: SheetId,
        new_name: &str,
    ) -> Result<SheetId, ExcelError> {
        let result = self.duplicate_sheet_impl(source_sheet_id, new_name);
        self.authority_end_structural();
        result
    }

    fn duplicate_sheet_impl(
        &mut self,
        source_sheet_id: SheetId,
        new_name: &str,
    ) -> Result<SheetId, ExcelError> {
        self.authority_note_structural(true);
        if new_name.is_empty() || new_name.len() > 255 {
            return Err(ExcelError::new(ExcelErrorKind::Value).with_message("Invalid sheet name"));
        }

        let source_name = self.sheet_reg.name(source_sheet_id).to_string();
        if source_name.is_empty() {
            return Err(
                ExcelError::new(ExcelErrorKind::Value).with_message("Source sheet does not exist")
            );
        }

        if self.sheet_reg.get_id(new_name).is_some() {
            return Err(ExcelError::new(ExcelErrorKind::Value)
                .with_message(format!("Sheet '{new_name}' already exists")));
        }

        let new_sheet_id = self.add_sheet(new_name)?;

        self.begin_batch();

        let source_vertices: Vec<(VertexId, GridAddr)> =
            self.grid_vertices_in_sheet(source_sheet_id).collect();

        let mut vertex_mapping = FxHashMap::default();

        for (old_id, coord) in &source_vertices {
            let row = coord.row();
            let col = coord.col();
            let kind = self.store.kind(*old_id);

            let new_id = self
                .store
                .allocate(VertexAddr::grid(*coord), new_sheet_id, 0x01);
            #[cfg(any(test, feature = "legacy_oracle"))]
            {
                self.edges.add_vertex(VertexAddr::grid(*coord), new_id.0);
                self.oracle_cell_vertex_created((new_sheet_id, coord.row(), coord.col()), new_id);
            }
            self.sheet_index_mut(new_sheet_id)
                .add_vertex(*coord, new_id);

            self.store.set_kind(new_id, kind);

            if let Some(&value_ref) = self.vertex_values.get(old_id) {
                self.vertex_values.insert(new_id, value_ref);
            }

            vertex_mapping.insert(*old_id, new_id);

            let cell_ref = CellRef::new(new_sheet_id, Coord::new(row, col, true, true));
            self.cell_to_vertex.insert(cell_ref, new_id);
        }

        let sheet_names: Vec<(String, NamedRange)> = self
            .sheet_named_ranges
            .iter()
            .filter(|((sid, _), _)| *sid == source_sheet_id)
            .map(|((_, name), range)| (name.clone(), range.clone()))
            .collect();

        for (name, mut named_range) in sheet_names {
            named_range.scope = NameScope::Sheet(new_sheet_id);

            match &mut named_range.definition {
                NamedDefinition::Cell(cell_ref) if cell_ref.sheet_id == source_sheet_id => {
                    cell_ref.sheet_id = new_sheet_id;
                }
                NamedDefinition::Range(range_ref) => {
                    if range_ref.start.sheet_id == source_sheet_id {
                        range_ref.start.sheet_id = new_sheet_id;
                        range_ref.end.sheet_id = new_sheet_id;
                    }
                }
                _ => {}
            }

            #[cfg(any(test, feature = "legacy_oracle"))]
            named_range.dependents.clear();
            let name_vertex = self.allocate_name_vertex(named_range.scope);
            if matches!(named_range.definition, NamedDefinition::Range(_)) {
                self.store.set_kind(name_vertex, VertexKind::NamedArray);
            } else {
                self.store.set_kind(name_vertex, VertexKind::NamedScalar);
            }
            named_range.vertex = name_vertex;

            let referenced_names = self.rebuild_name_dependencies(
                name_vertex,
                &named_range.definition,
                named_range.scope,
            )?;
            if !referenced_names.is_empty() {
                self.attach_vertex_to_names(name_vertex, &referenced_names);
            }

            self.sheet_named_ranges
                .insert((new_sheet_id, name.clone()), named_range);
            self.sheet_named_ranges_lookup
                .insert((new_sheet_id, self.name_lookup_key(&name)), name.clone());
            self.name_vertex_lookup
                .insert(name_vertex, (NameScope::Sheet(new_sheet_id), name));
        }

        for (old_id, _) in &source_vertices {
            if let Some(&new_id) = vertex_mapping.get(old_id)
                && let Some(ast) = self.get_formula(*old_id)
            {
                let updated_ast = update_internal_sheet_references(
                    &ast,
                    &source_name,
                    new_name,
                    source_sheet_id,
                    new_sheet_id,
                );

                let new_ast_id = self.data_store.store_ast(&updated_ast, &self.sheet_reg);
                self.vertex_formulas.insert(new_id, new_ast_id);

                if let Ok((deps, range_deps, vertexless, name_vertices)) =
                    self.extract_dependencies(&updated_ast, new_sheet_id)
                {
                    let mapped_deps: Vec<VertexId> = deps
                        .iter()
                        .map(|&dep_id| vertex_mapping.get(&dep_id).copied().unwrap_or(dep_id))
                        .collect();

                    self.add_dependent_edges(new_id, &mapped_deps);
                    self.note_vertexless_deps(
                        new_id,
                        vertexless
                            .iter()
                            .map(|c| (c.sheet_id, c.coord.row(), c.coord.col())),
                    );
                    self.add_range_dependent_edges(new_id, &range_deps, new_sheet_id);

                    if !name_vertices.is_empty() {
                        self.attach_vertex_to_names(new_id, &name_vertices);
                    }
                }
            }
        }

        self.end_batch();

        Ok(new_sheet_id)
    }
}