Skip to content

Beautiful Open-Source Form Builder

7.1 KB
Raw Blame
<?php

namespace App\Service\Formulas;

class DependencyResolver
{
    private array $nodes = [];
    private array $dependents = [];

    public function addVariable(array $variable): void
    {
        $dependencies = Validator::extractFieldReferences($variable['formula'] ?? '');

        $this->nodes[$variable['id']] = [
            'id' => $variable['id'],
            'name' => $variable['name'] ?? '',
            'formula' => $variable['formula'] ?? '',
            'dependencies' => $dependencies,
        ];

        // Update reverse dependency map
        foreach ($dependencies as $depId) {
            if (!isset($this->dependents[$depId])) {
                $this->dependents[$depId] = [];
            }
            $this->dependents[$depId][] = $variable['id'];
        }
    }

    public function removeVariable(string $variableId): void
    {
        $node = $this->nodes[$variableId] ?? null;
        if (!$node) {
            return;
        }

        // Remove from dependents map
        foreach ($node['dependencies'] as $depId) {
            if (isset($this->dependents[$depId])) {
                $this->dependents[$depId] = array_filter(
                    $this->dependents[$depId],
                    fn ($id) => $id !== $variableId
                );
            }
        }

        unset($this->nodes[$variableId]);
        unset($this->dependents[$variableId]);
    }

    public function detectCycles(): array
    {
        $cycles = [];
        $visited = [];
        $recursionStack = [];
        $path = [];

        $dfs = function ($nodeId) use (&$dfs, &$cycles, &$visited, &$recursionStack, &$path) {
            if (isset($recursionStack[$nodeId])) {
                // Found a cycle
                $cycleStart = array_search($nodeId, $path);
                $cycle = array_slice($path, $cycleStart);
                $cycle[] = $nodeId;
                $cycles[] = $cycle;
                return true;
            }

            if (isset($visited[$nodeId])) {
                return false;
            }

            $visited[$nodeId] = true;
            $recursionStack[$nodeId] = true;
            $path[] = $nodeId;

            $node = $this->nodes[$nodeId] ?? null;
            if ($node) {
                foreach ($node['dependencies'] as $depId) {
                    // Only check dependencies that are computed variables
                    if (isset($this->nodes[$depId])) {
                        $dfs($depId);
                    }
                }
            }

            array_pop($path);
            unset($recursionStack[$nodeId]);
            return false;
        };

        foreach (array_keys($this->nodes) as $nodeId) {
            if (!isset($visited[$nodeId])) {
                $dfs($nodeId);
            }
        }

        return $cycles;
    }

    public function getEvaluationOrder(): array
    {
        $cycles = $this->detectCycles();
        if (!empty($cycles)) {
            $cycleStr = implode(' → ', $cycles[0]);
            throw new FormulaException("Circular dependency detected: {$cycleStr}");
        }

        $sorted = [];
        $visited = [];
        $temp = [];

        $visit = function ($nodeId) use (&$visit, &$sorted, &$visited, &$temp) {
            if (isset($visited[$nodeId])) {
                return;
            }
            if (isset($temp[$nodeId])) {
                return; // Already being processed
            }

            $temp[$nodeId] = true;

            $node = $this->nodes[$nodeId] ?? null;
            if ($node) {
                foreach ($node['dependencies'] as $depId) {
                    if (isset($this->nodes[$depId])) {
                        $visit($depId);
                    }
                }
            }

            unset($temp[$nodeId]);
            $visited[$nodeId] = true;
            $sorted[] = $nodeId;
        };

        foreach (array_keys($this->nodes) as $nodeId) {
            $visit($nodeId);
        }

        return $sorted;
    }

    public function getDependents(string $id): array
    {
        $result = [];
        $queue = [$id];
        $seen = [];

        while (!empty($queue)) {
            $current = array_shift($queue);
            $deps = $this->dependents[$current] ?? [];

            foreach ($deps as $depId) {
                if (!isset($seen[$depId])) {
                    $seen[$depId] = true;
                    $result[] = $depId;
                    $queue[] = $depId;
                }
            }
        }

        return $result;
    }

    public function getAllDependencies(string $variableId): array
    {
        $result = [];
        $queue = [$variableId];
        $visited = [];

        while (!empty($queue)) {
            $current = array_shift($queue);
            if (isset($visited[$current])) {
                continue;
            }
            $visited[$current] = true;

            $node = $this->nodes[$current] ?? null;
            if ($node) {
                foreach ($node['dependencies'] as $depId) {
                    $result[] = $depId;
                    if (isset($this->nodes[$depId])) {
                        $queue[] = $depId;
                    }
                }
            }
        }

        return array_unique($result);
    }

    public static function fromVariables(array $variables): self
    {
        $resolver = new self();

        foreach ($variables as $variable) {
            $resolver->addVariable($variable);
        }

        return $resolver;
    }

    public function wouldCreateCycle(array $variable): bool
    {
        // Create a temporary resolver with the new/updated variable
        $tempResolver = new self();

        // Add all existing nodes except the one being updated
        foreach ($this->nodes as $id => $node) {
            if ($id !== $variable['id']) {
                $tempResolver->addVariable($node);
            }
        }

        // Add the new/updated variable
        $tempResolver->addVariable($variable);

        return !empty($tempResolver->detectCycles());
    }

    /**
     * Get the maximum dependency chain depth.
     * Returns the longest path length in the dependency graph.
     */
    public function getMaxChainDepth(): int
    {
        $memo = [];

        $getDepth = function (string $nodeId) use (&$getDepth, &$memo): int {
            if (isset($memo[$nodeId])) {
                return $memo[$nodeId];
            }

            $node = $this->nodes[$nodeId] ?? null;
            if (!$node) {
                return 0;
            }

            $maxChildDepth = 0;
            foreach ($node['dependencies'] as $depId) {
                // Only count dependencies that are computed variables
                if (isset($this->nodes[$depId])) {
                    $childDepth = $getDepth($depId);
                    $maxChildDepth = max($maxChildDepth, $childDepth);
                }
            }

            $memo[$nodeId] = $maxChildDepth + 1;

            return $memo[$nodeId];
        };

        $maxDepth = 0;
        foreach (array_keys($this->nodes) as $nodeId) {
            $depth = $getDepth($nodeId);
            $maxDepth = max($maxDepth, $depth);
        }

        return $maxDepth;
    }
}