packages/deriver/src/Deriver/Evaluator/Enumeration/Choices.php

1<?php
2
3declare(strict_types=1);
4
5namespace Deriver\Deriver\Evaluator\Enumeration;
6
7use Closure;
8use Deriver\Deriver\Evaluator\Term;
9use Deriver\Deriver\Evaluator\TermKind;
10use Generator;
11use WeakMap;
12
13/**
14 * Keeps branch and call-site correlations inside shared expression choices.
15 * @visibility parent
16 */
17final class Choices
18{
19    /**
20     * Shares proofs when distributing and folding alternatives.
21     */
22    public function __construct(private readonly \Deriver\Deriver\Evaluator\Evidence\Provenance $provenance = new \Deriver\Deriver\Evaluator\Evidence\Provenance(), private readonly ?\Deriver\Deriver\Evaluator\Search\Search $search = null)
23    {
24    }
25
26    /**
27     * @param list<array{Term, array<string, bool|string>}> $alternatives
28     */
29    public function make(array $alternatives): Term
30    {
31        if (count($alternatives) === 1 && $alternatives[0][1] === [] && $alternatives[0][0]->kind !== TermKind::Choice) {
32            return $alternatives[0][0];
33        }
34        $items = [];
35        foreach ($alternatives as [$value, $guard]) {
36            $attributes = [];
37            foreach ($guard as $condition => $selection) {
38                $attributes['guard:' . $condition] = $selection;
39            }
40            $items[] = new Term(TermKind::Alternative, operands: [$value], attributes: $attributes);
41        }
42        return new Term(TermKind::Choice, operands: $items);
43    }
44
45    /**
46
47     * @return Generator<int, array{Term, array<string, bool|string>}, void, void>
48
49     */
50    public function alternatives(Term $value): Generator
51    {
52        $cursor = new Enumerator($value);
53        while (($next = $cursor->next()) !== null) {
54            yield $next;
55        }
56    }
57
58    /**
59     * @param array<string, bool|string> $left
60     * @param array<string, bool|string> $right
61     * @return array<string, bool|string>|null
62     */
63    public function merge(array $left, array $right): ?array
64    {
65        foreach ($right as $key => $value) {
66            if (isset($left[$key]) && $left[$key] !== $value) {
67                return null;
68            }
69        }
70        return $left + $right;
71    }
72
73    /**
74     * Distributes small choices and retains large products as an expression DAG.
75     * @param list<Term> $operands
76     * @param callable(list<Term>): Term $evaluate
77     */
78    public function apply(string $operation, array $operands, callable $evaluate, int $limit): Term
79    {
80        $rows = [[[], []]];
81        foreach ($operands as $operand) {
82            $next = [];
83            foreach ($rows as [$values, $guard]) {
84                foreach ($this->alternatives($operand) as [$value, $conditions]) {
85                    $merged = $this->merge($guard, $conditions);
86                    if ($merged !== null) {
87                        $next[] = [[...$values, $value], $merged];
88                    }
89                    if (count($next) > $limit) {
90                        return new Term(TermKind::Operation, $operation, $operands, ['reason' => 'ENUMERATION_LIMIT']);
91                    }
92                }
93            }
94            $rows = $next;
95        }
96        $branches = array_map(fn (array $row): Closure => fn (): Term => $this->provenance->operation($evaluate($row[0]), $row[0], $operation), $rows);
97        $values = $this->search?->all($branches) ?? array_map(static fn (Closure $branch): Term => $branch(), $branches);
98        return $this->make(array_map(static fn (Term $value, array $row): array => [$value, $row[1]], $values, $rows));
99    }
100    /**
101     * Transforms each shared choice once per operation, preserving branch guards and distinct proofs.
102     * @param Closure(Term): Term $transform
103     */
104    public function map(Term $value, Closure $transform): Term
105    {
106        /** @var WeakMap<Term, Term> $memo */
107        $memo = new WeakMap();
108        /** @var list<array{Term, bool}> $pending */
109        $pending = [[$value, false]];
110        while ($pending !== []) {
111            [$node, $ready] = array_pop($pending);
112            if (isset($memo[$node])) {
113                continue;
114            }
115            if ($node->kind !== TermKind::Choice) {
116                $memo[$node] = $transform($node);
117            } elseif (!$ready) {
118                $pending[] = [$node, true];
119                foreach ($node->operands as $item) {
120                    $pending[] = [$item->operands[0], false];
121                }
122            } else {
123                $items = [];
124                foreach ($node->operands as $key => $item) {
125                    $items[$key] = new Term(TermKind::Alternative, operands: [$memo[$item->operands[0]]], attributes: $item->attributes);
126                }
127                $memo[$node] = new Term(TermKind::Choice, operands: $items);
128            }
129        }
130        return $memo[$value];
131    }
132}
133