SPB Git

Repository Public

DependencyTracer.swift 17.4 KB 375 lines swift

1// =============================================================================2//                  SP BOUCHER | SOFTWARE & RESEARCH3//             ARTIFICIAL INTELLIGENCE • FINANCE • ENGINEERING4// =============================================================================5//6// PROJECT METADATA7// -----------------------------------------------------------------------------8// Project          : ORIX Sheet9// File             : Packages/SheetAnalytics/Sources/Audit/Formula/DependencyTracer.swift10// Module           : Audit11// Repository       : https://git.spboucher.ai/orix-sheet12// Created          : 2026-11-2113// Last Modified    : 2026-11-2114//15// =============================================================================16// AUTHOR & PROFESSIONAL AFFILIATION17// =============================================================================18//19// Author           : Simon-Pierre Boucher20// Position         : Professor of Finance21// Institution      : Université du Québec en Outaouais (UQO)22// Department       : Département des sciences administratives23// Organization     : SP Boucher24//25// Website          : https://spboucher.ai26// Git              : https://git.spboucher.ai27//28// =============================================================================29// OFFICIAL CONTACT DIRECTORY30// =============================================================================31//32// General          : info@spboucher.ai33// Professional     : contact@spboucher.ai34// Direct           : simon@spboucher.ai35// Research         : research@spboucher.ai36// Development      : dev@spboucher.ai37// Support          : support@spboucher.ai38// Security/Admin   : admin@spboucher.ai39// Notifications    : notifications@spboucher.ai40//41// Preferred Contact: support@spboucher.ai42//43// =============================================================================44// COPYRIGHT & INTELLECTUAL PROPERTY45// =============================================================================46//47// Copyright (c) 202648// Simon-Pierre Boucher49//50// All rights reserved where applicable.51//52// This file is governed by the applicable project license,53// copyright notices, institutional agreements and relevant law.54//55// Unless expressly authorized by the applicable license or56// rights holder, copying, redistribution, sublicensing,57// publication and commercial exploitation are not permitted.58//59// Existing third-party rights and notices remain unaffected.60//61// =============================================================================62// CONFIDENTIALITY & SECURITY63// =============================================================================64//65// Classification   : Public66// Distribution     : Public repository; use is governed by the project license67// Security Contact : admin@spboucher.ai68//69// Access to this source does not independently grant permission70// to redistribute or disclose confidential materials.71//72// Do not embed credentials, private keys, access tokens,73// certificates or confidential personal information.74//75// =============================================================================76// LICENSE & MAINTENANCE77// =============================================================================78//79// License          : None specified (no license file in this repository)80// Maintainer       : Simon-Pierre Boucher81// Technical Contact: dev@spboucher.ai82//83// =============================================================================84// END OF SP BOUCHER SOURCE HEADER85// =============================================================================8687import Foundation88import SheetCore8990/// A cell or range in a dependency graph.91public struct DependencyNode: Hashable, Sendable, Codable, Identifiable {92    /// "Sheet1!B3" or "Sheet1!A1:A10".93    public var id: String94    public var sheet: String95    public var sheetIndex: Int96    public var range: RangeRef97    public var isRange: Bool98    /// Short display form of the current value (for ranges: size and first values).99    public var valuePreview: String100    /// Formula text with "=", nil for constants, blanks and ranges.101    public var formula: String?102    public var isError: Bool103    /// Distance from the root (0 = the traced cell).104    public var depth: Int105    /// True when the node has further precedents/dependents that were not followed (depth or size limit).106    public var isTruncated: Bool107}108109/// Directed edge in the direction of data flow: `from` is read by `to`.110public struct DependencyEdge: Hashable, Sendable, Codable {111    public var from: String112    public var to: String113}114115/// Position of a node in the layered drawing.116public struct DependencyNodePosition: Hashable, Sendable, Codable {117    /// Layer index: 0 holds the nodes without incoming edges; data flows towards higher layers.118    public var layer: Int119    /// Position inside the layer (0-based, unique per layer).120    public var order: Int121    public var x: Double122    public var y: Double123}124125/// Layered (Sugiyama-style) layout: longest-path layering, then barycentric ordering inside layers.126public struct DependencyLayout: Hashable, Sendable, Codable {127    public var positions: [String: DependencyNodePosition]128    /// Node ids per layer, in drawing order.129    public var layers: [[String]]130    public var width: Double131    public var height: Double132    /// Edges that close a cycle (ignored for layering; draw them as back edges).133    public var backEdges: [DependencyEdge]134}135136public struct DependencyGraph: Hashable, Sendable, Codable {137    public enum Direction: String, Sendable, Codable { case precedents, dependents, both }138    public var root: String139    public var direction: Direction140    public var nodes: [DependencyNode]141    public var edges: [DependencyEdge]142    /// True when the trace met a circular dependency.143    public var hasCycle: Bool144    /// True when the node limit stopped the trace.145    public var isTruncated: Bool146    public var layout: DependencyLayout147148    public func node(_ id: String) -> DependencyNode? { nodes.first { $0.id == id } }149    public func predecessors(of id: String) -> [String] { edges.filter { $0.to == id }.map(\.from) }150    public func successors(of id: String) -> [String] { edges.filter { $0.from == id }.map(\.to) }151}152153/// Builds precedent / dependent graphs around a cell, ready for drawing.154public struct DependencyTracer {155    public struct Options: Sendable, Hashable {156        /// How many levels to follow.157        public var maxDepth = 3158        /// The trace stops adding nodes beyond this count (`isTruncated` is set).159        public var maxNodes = 400160        /// Multi-cell ranges with at most this many cells are opened: their formula cells become nodes161        /// that are traced further. Larger ranges stay opaque leaves.162        public var expandRangesUpTo = 32163        /// Horizontal distance between layers and vertical distance between nodes of a layer.164        public var layerSpacing = 180.0165        public var nodeSpacing = 56.0166        /// Barycentric ordering sweeps.167        public var orderingSweeps = 8168        public init() {}169    }170171    public let engine: CalcEngine172    public var options: Options173174    public init(engine: CalcEngine, options: Options = Options()) { self.engine = engine; self.options = options }175176    /// Cells and ranges the cell reads, directly and indirectly, down to `maxDepth` levels.177    public func precedents(sheet: Int, cell: CellRef, depth: Int? = nil) -> DependencyGraph { trace(sheet, cell, .precedents, depth) }178    /// Formula cells that read the cell, directly and indirectly.179    public func dependents(sheet: Int, cell: CellRef, depth: Int? = nil) -> DependencyGraph { trace(sheet, cell, .dependents, depth) }180    /// Both directions around the cell.181    public func neighbourhood(sheet: Int, cell: CellRef, depth: Int? = nil) -> DependencyGraph { trace(sheet, cell, .both, depth) }182183    // MARK: Tracing184185    private struct Key: Hashable { var sheet: Int; var range: RangeRef }186187    private final class Builder {188        var nodes = [Key: DependencyNode]()189        var order = [Key]()190        var edges = [DependencyEdge]()191        var edgeSet = Set<DependencyEdge>()192        var truncated = false193    }194195    private func trace(_ si: Int, _ cell: CellRef, _ direction: DependencyGraph.Direction, _ depth: Int?) -> DependencyGraph {196        let wb = engine.workbook197        if engine.hasPendingWork { engine.recalculate() }198        let maxDepth = max(0, depth ?? options.maxDepth)199        let b = Builder()200        let rootKey = Key(sheet: si, range: RangeRef(cell))201        guard si >= 0, si < wb.sheets.count else {202            return DependencyGraph(root: "", direction: direction, nodes: [], edges: [], hasCycle: false, isTruncated: false,203                                   layout: DependencyLayout(positions: [:], layers: [], width: 0, height: 0, backEdges: []))204        }205        _ = add(b, rootKey, depth: 0)206        if direction != .dependents { walk(b, rootKey, 0, maxDepth, up: true) }207        if direction != .precedents { walk(b, rootKey, 0, maxDepth, up: false) }208        let nodes = b.order.compactMap { b.nodes[$0] }209        let layout = DependencyTracer.layout(nodes: nodes.map(\.id), edges: b.edges, options: options)210        return DependencyGraph(root: b.nodes[rootKey]!.id, direction: direction, nodes: nodes, edges: b.edges,211                               hasCycle: !layout.backEdges.isEmpty, isTruncated: b.truncated, layout: layout)212    }213214    /// Adds a node if new. Returns false when the node limit prevents it.215    private func add(_ b: Builder, _ key: Key, depth: Int) -> Bool {216        if b.nodes[key] != nil { return true }217        guard b.nodes.count < options.maxNodes else { b.truncated = true; return false }218        let sheet = engine.workbook.sheets[key.sheet]219        var node = DependencyNode(id: FormulaIntel.address(sheet.name, key.range), sheet: sheet.name, sheetIndex: key.sheet, range: key.range,220                                  isRange: !key.range.isSingleCell, valuePreview: "", formula: nil, isError: false, depth: depth, isTruncated: false)221        if key.range.isSingleCell {222            let c = sheet.cell(key.range.r0, key.range.c0)223            let v = c?.computed ?? .blank224            node.valuePreview = FormulaIntel.preview(v, limit: 40)225            node.isError = v.isError226            if let f = c?.formula { node.formula = "=" + f.expr.formulaText() }227        } else {228            var count = 0, errors = 0229            sheet.cells.forEach(in: key.range) { _, _, c in230                if c.hasContent { count += 1 }231                if c.computed.isError { errors += 1 }232            }233            let dims = key.range.isWholeColumns || key.range.isWholeRows ? "whole " + (key.range.isWholeColumns ? "columns" : "rows") : "\(key.range.rows)×\(key.range.cols)"234            node.valuePreview = "\(dims), \(count) filled" + (errors > 0 ? ", \(errors) errors" : "")235            node.isError = errors > 0236        }237        b.nodes[key] = node238        b.order.append(key)239        return true240    }241242    private func link(_ b: Builder, from: Key, to: Key) {243        guard let f = b.nodes[from], let t = b.nodes[to] else { return }244        let e = DependencyEdge(from: f.id, to: t.id)245        if b.edgeSet.insert(e).inserted { b.edges.append(e) }246    }247248    private func hasMore(_ key: Key, up: Bool) -> Bool {249        guard key.range.isSingleCell else { return false }250        if up { return !engine.precedents(sheet: key.sheet, row: key.range.r0, col: key.range.c0).isEmpty }251        return !engine.dependents(sheet: key.sheet, row: key.range.r0, col: key.range.c0).isEmpty252    }253254    private func walk(_ b: Builder, _ start: Key, _ startDepth: Int, _ maxDepth: Int, up: Bool) {255        var queue = [(Key, Int)]()256        var expanded = Set<Key>()257        queue.append((start, startDepth))258        var head = 0259        while head < queue.count {260            let (key, d) = queue[head]261            head += 1262            guard expanded.insert(key).inserted else { continue }263            if d >= maxDepth {264                if hasMore(key, up: up) { b.nodes[key]?.isTruncated = true }265                continue266            }267            var next = [Key]()268            if up {269                if key.range.isSingleCell {270                    for a in engine.precedents(sheet: key.sheet, row: key.range.r0, col: key.range.c0) { next.append(Key(sheet: a.sheet, range: a.range)) }271                } else if key.range.count <= options.expandRangesUpTo {272                    // open the range: its formula cells feed it273                    var cells = [CellRef]()274                    engine.workbook.sheets[key.sheet].cells.forEach(in: key.range) { r, c, cell in if cell.formula != nil { cells.append(CellRef(r, c)) } }275                    for c in cells.sorted() { next.append(Key(sheet: key.sheet, range: RangeRef(c))) }276                }277            } else if key.range.isSingleCell {278                for dep in engine.dependents(sheet: key.sheet, row: key.range.r0, col: key.range.c0) { next.append(Key(sheet: dep.sheet, range: RangeRef(dep.cell))) }279            }280            for n in next {281                guard add(b, n, depth: d + 1) else { b.nodes[key]?.isTruncated = true; continue }282                if up { link(b, from: n, to: key) } else { link(b, from: key, to: n) }283                queue.append((n, d + 1))284            }285        }286    }287288    // MARK: Layout289290    /// Layered layout of an arbitrary directed graph. Cycles are tolerated: edges that would close a291    /// cycle (found by depth-first search in node order) are set aside as `backEdges`.292    /// Coordinates: x grows with the layer (data flows left → right), y with the order inside the layer;293    /// layers are centred vertically on each other.294    public static func layout(nodes: [String], edges: [DependencyEdge], options: Options = Options()) -> DependencyLayout {295        let index = Dictionary(uniqueKeysWithValues: nodes.enumerated().map { ($1, $0) })296        let n = nodes.count297        var succ = [[Int]](repeating: [], count: n), pred = [[Int]](repeating: [], count: n)298        var forward = [(Int, Int)]()299        var back = [DependencyEdge]()300        // 1. remove back edges (iterative DFS, colours: 0 new, 1 on stack, 2 done)301        var out = [[Int]](repeating: [], count: n)302        for e in edges { if let a = index[e.from], let b = index[e.to] { out[a].append(b) } }303        var colour = [UInt8](repeating: 0, count: n)304        var isBack = Set<Int64>()305        for s in 0..<n where colour[s] == 0 {306            var stack = [(s, 0)]307            colour[s] = 1308            while let (v, k) = stack.last {309                if k < out[v].count {310                    stack[stack.count - 1].1 = k + 1311                    let w = out[v][k]312                    if colour[w] == 1 { isBack.insert(Int64(v) << 32 | Int64(w)) }313                    else if colour[w] == 0 { colour[w] = 1; stack.append((w, 0)) }314                } else {315                    colour[v] = 2316                    stack.removeLast()317                }318            }319        }320        for e in edges {321            guard let a = index[e.from], let b = index[e.to] else { continue }322            if a == b || isBack.contains(Int64(a) << 32 | Int64(b)) { back.append(e); continue }323            succ[a].append(b); pred[b].append(a); forward.append((a, b))324        }325        // 2. longest-path layering (Kahn order)326        var indeg = pred.map(\.count)327        var layer = [Int](repeating: 0, count: n)328        var ready = (0..<n).filter { indeg[$0] == 0 }329        var head = 0330        while head < ready.count {331            let v = ready[head]; head += 1332            for w in succ[v] {333                layer[w] = max(layer[w], layer[v] + 1)334                indeg[w] -= 1335                if indeg[w] == 0 { ready.append(w) }336            }337        }338        let layerCount = (layer.max() ?? -1) + 1339        var layers = [[Int]](repeating: [], count: layerCount)340        for v in 0..<n { layers[layer[v]].append(v) }341        // 3. barycentric ordering sweeps342        var pos = [Double](repeating: 0, count: n)343        func renumber(_ l: Int) { for (k, v) in layers[l].enumerated() { pos[v] = Double(k) } }344        for l in 0..<layerCount { renumber(l) }345        func sweep(_ l: Int, using neighbours: [[Int]]) {346            var bary = [Int: Double]()347            for v in layers[l] {348                let ns = neighbours[v]349                bary[v] = ns.isEmpty ? pos[v] : ns.reduce(0.0) { $0 + pos[$1] } / Double(ns.count)350            }351            let before = Dictionary(uniqueKeysWithValues: layers[l].enumerated().map { ($1, $0) })352            layers[l].sort { (bary[$0]!, before[$0]!) < (bary[$1]!, before[$1]!) }353            renumber(l)354        }355        if layerCount > 1 {356            for _ in 0..<max(0, options.orderingSweeps) {357                for l in 1..<layerCount { sweep(l, using: pred) }358                for l in stride(from: layerCount - 2, through: 0, by: -1) { sweep(l, using: succ) }359            }360        }361        // 4. coordinates362        let tallest = layers.map(\.count).max() ?? 0363        var positions = [String: DependencyNodePosition]()364        for (l, members) in layers.enumerated() {365            let offset = Double(tallest - members.count) / 2 * options.nodeSpacing366            for (k, v) in members.enumerated() {367                positions[nodes[v]] = DependencyNodePosition(layer: l, order: k, x: Double(l) * options.layerSpacing, y: offset + Double(k) * options.nodeSpacing)368            }369        }370        return DependencyLayout(positions: positions, layers: layers.map { $0.map { nodes[$0] } },371                                width: Double(max(0, layerCount - 1)) * options.layerSpacing,372                                height: Double(max(0, tallest - 1)) * options.nodeSpacing, backEdges: back)373    }374}375
Files main
Menu

Theme