Skip to content

Beautiful Open-Source Form Builder

6.5 KB
Raw Blame
import { FormulaError } from './types.js'
import { Validator } from './validator.js'

/**
 * Dependency graph for computed variables
 * Handles dependency resolution and cycle detection
 */
export class DependencyGraph {
  constructor() {
    this.nodes = new Map() // id -> { id, formula, dependencies: Set }
    this.dependents = new Map() // id -> Set of ids that depend on this
  }

  /**
   * Add a computed variable to the graph
   */
  addVariable(variable) {
    const dependencies = this.extractDependencies(variable.formula)
    
    this.nodes.set(variable.id, {
      id: variable.id,
      name: variable.name,
      formula: variable.formula,
      dependencies: new Set(dependencies)
    })

    // Update reverse dependency map
    for (const depId of dependencies) {
      if (!this.dependents.has(depId)) {
        this.dependents.set(depId, new Set())
      }
      this.dependents.get(depId).add(variable.id)
    }
  }

  /**
   * Remove a variable from the graph
   */
  removeVariable(variableId) {
    const node = this.nodes.get(variableId)
    if (!node) return

    // Remove from dependents map
    for (const depId of node.dependencies) {
      const deps = this.dependents.get(depId)
      if (deps) {
        deps.delete(variableId)
      }
    }

    this.nodes.delete(variableId)
    this.dependents.delete(variableId)
  }

  /**
   * Extract field/variable references from a formula
   */
  extractDependencies(formula) {
    return Validator.extractFieldReferences(formula)
  }

  /**
   * Check for circular dependencies
   * Returns array of cycles found, or empty array if none
   */
  detectCycles() {
    const cycles = []
    const visited = new Set()
    const recursionStack = new Set()
    const path = []

    const dfs = (nodeId) => {
      if (recursionStack.has(nodeId)) {
        // Found a cycle - extract the cycle path
        const cycleStart = path.indexOf(nodeId)
        const cycle = path.slice(cycleStart)
        cycle.push(nodeId)
        cycles.push(cycle)
        return true
      }

      if (visited.has(nodeId)) {
        return false
      }

      visited.add(nodeId)
      recursionStack.add(nodeId)
      path.push(nodeId)

      const node = this.nodes.get(nodeId)
      if (node) {
        for (const depId of node.dependencies) {
          // Only check dependencies that are computed variables
          if (this.nodes.has(depId)) {
            dfs(depId)
          }
        }
      }

      path.pop()
      recursionStack.delete(nodeId)
      return false
    }

    for (const nodeId of this.nodes.keys()) {
      if (!visited.has(nodeId)) {
        dfs(nodeId)
      }
    }

    return cycles
  }

  /**
   * Get topologically sorted order for evaluation
   * Throws if there are cycles
   */
  getEvaluationOrder() {
    const cycles = this.detectCycles()
    if (cycles.length > 0) {
      const cycleStr = cycles[0].join(' → ')
      throw new FormulaError(`Circular dependency detected: ${cycleStr}`)
    }

    const sorted = []
    const visited = new Set()
    const temp = new Set()

    const visit = (nodeId) => {
      if (visited.has(nodeId)) return
      if (temp.has(nodeId)) return // Already being processed

      temp.add(nodeId)

      const node = this.nodes.get(nodeId)
      if (node) {
        for (const depId of node.dependencies) {
          if (this.nodes.has(depId)) {
            visit(depId)
          }
        }
      }

      temp.delete(nodeId)
      visited.add(nodeId)
      sorted.push(nodeId)
    }

    for (const nodeId of this.nodes.keys()) {
      visit(nodeId)
    }

    return sorted
  }

  /**
   * Get variables that depend on a given field or variable
   */
  getDependents(id) {
    const result = new Set()
    const queue = [id]

    while (queue.length > 0) {
      const current = queue.shift()
      const deps = this.dependents.get(current)
      
      if (deps) {
        for (const depId of deps) {
          if (!result.has(depId)) {
            result.add(depId)
            queue.push(depId)
          }
        }
      }
    }

    return Array.from(result)
  }

  /**
   * Get all dependencies for a variable (including transitive)
   */
  getAllDependencies(variableId) {
    const result = new Set()
    const queue = [variableId]
    const visited = new Set()

    while (queue.length > 0) {
      const current = queue.shift()
      if (visited.has(current)) continue
      visited.add(current)

      const node = this.nodes.get(current)
      if (node) {
        for (const depId of node.dependencies) {
          result.add(depId)
          if (this.nodes.has(depId)) {
            queue.push(depId)
          }
        }
      }
    }

    return Array.from(result)
  }

  /**
   * Build graph from array of computed variables
   */
  static fromVariables(variables) {
    const graph = new DependencyGraph()
    
    for (const variable of variables) {
      graph.addVariable(variable)
    }

    return graph
  }

  /**
   * Validate that adding/updating a variable won't create cycles
   */
  wouldCreateCycle(variable) {
    // Create a temporary graph with the new/updated variable
    const tempGraph = new DependencyGraph()
    
    // Add all existing nodes except the one being updated
    for (const [id, node] of this.nodes) {
      if (id !== variable.id) {
        tempGraph.addVariable(node)
      }
    }
    
    // Add the new/updated variable
    tempGraph.addVariable(variable)
    
    return tempGraph.detectCycles().length > 0
  }

  /**
   * Get the maximum dependency chain depth.
   * Returns the longest path length in the dependency graph.
   */
  getMaxChainDepth() {
    const memo = new Map()

    const getDepth = (nodeId) => {
      if (memo.has(nodeId)) {
        return memo.get(nodeId)
      }

      const node = this.nodes.get(nodeId)
      if (!node) {
        return 0
      }

      let maxChildDepth = 0
      for (const depId of node.dependencies) {
        // Only count dependencies that are computed variables
        if (this.nodes.has(depId)) {
          const childDepth = getDepth(depId)
          maxChildDepth = Math.max(maxChildDepth, childDepth)
        }
      }

      const depth = maxChildDepth + 1
      memo.set(nodeId, depth)
      return depth
    }

    let maxDepth = 0
    for (const nodeId of this.nodes.keys()) {
      const depth = getDepth(nodeId)
      maxDepth = Math.max(maxDepth, depth)
    }

    return maxDepth
  }
}

/**
 * Build dependency graph from computed variables
 */
export function buildDependencyGraph(variables) {
  return DependencyGraph.fromVariables(variables)
}