Repository Public
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