1<?php
2
3/* Copyright (c) 2019 Richard Klees <richard.klees@concepts-and-training.de> Extended GPL, see docs/LICENSE */
4
5namespace ILIAS\Setup;
6
7use ILIAS\Setup\Environment;
8use ILIAS\Setup\Objective;
9use ILIAS\Setup\UnachievableException;
10
11/**
12 * Tries to enumerate all preconditions for the given objective, where the ones that
13 * can be achieved (i.e. have no further preconditions on their own) will be
14 * returned first. Will also attempt to only return every objective once. This thus
15 * expects, that returned objectives will be achieved somehow.
16 */
17class ObjectiveIterator implements \Iterator
18{
19    /**
20     * @var	Environment
21     */
22    protected $environment;
23
24    /**
25     * @var Objective
26     */
27    protected $objective;
28
29    /**
30     * @var Objective[]
31     */
32    protected $stack;
33
34    /**
35     * @var Objective|null
36     */
37    protected $current;
38
39    /**
40     * @var array<string, bool>
41     */
42    protected $returned;
43
44    /**
45     * @var	array<string, bool>
46     */
47    protected $failed;
48
49    /**
50     * @var array<string, string[]>
51     */
52    protected $reverse_dependencies;
53
54
55    public function __construct(Environment $environment, Objective $objective)
56    {
57        $this->environment = $environment;
58        $this->objective = $objective;
59        $this->rewind();
60    }
61
62    public function setEnvironment(Environment $environment) : void
63    {
64        $this->environment = $environment;
65    }
66
67    public function markAsFailed(Objective $objective)
68    {
69        if (!isset($this->returned[$objective->getHash()])) {
70            throw new \LogicException(
71                "You may only mark objectives as failed that have been returned by this iterator."
72            );
73        }
74
75        $this->failed[$objective->getHash()] = true;
76    }
77
78    public function rewind()
79    {
80        $this->stack = [$this->objective];
81        $this->current = null;
82        $this->returned = [];
83        $this->failed = [];
84        $this->reverse_dependencies = [];
85        $this->next();
86    }
87
88    public function current()
89    {
90        if ($this->current === null) {
91            throw new \LogicException(
92                "Iterator is finished or wasn't initialized correctly internally."
93            );
94        }
95        return $this->current;
96    }
97
98    public function key()
99    {
100        return $this->current()->getHash();
101    }
102
103    public function next()
104    {
105        if (count($this->stack) === 0) {
106            $this->current = null;
107            return;
108        }
109
110        $cur = array_pop($this->stack);
111        $hash = $cur->getHash();
112
113        if (isset($this->returned[$hash]) || isset($this->filed[$hash])) {
114            $this->next();
115            return;
116        }
117
118        $preconditions = array_filter(
119            $cur->getPreconditions($this->environment),
120            function ($p) {
121                $h = $p->getHash();
122                return !isset($this->returned[$h]) || isset($this->failed[$h]);
123            }
124        );
125
126        $failed_preconditions = array_filter(
127            $preconditions,
128            function ($p) {
129                return isset($this->failed[$p->getHash()]);
130            }
131        );
132
133        // We only have preconditions left that we know to have failed.
134        if (count($preconditions) !== 0
135        && count($preconditions) === count($failed_preconditions)) {
136            throw new UnachievableException(
137                "Objective only has failed preconditions."
138            );
139        }
140
141        // No preconditions open, we can proceed with the objective.
142        if (count($preconditions) === 0) {
143            $this->returned[$hash] = true;
144            $this->current = $cur;
145            return;
146        }
147
148        $this->stack[] = $cur;
149        $this->detectDependencyCycles($hash, $hash);
150        foreach (array_reverse($preconditions) as $p) {
151            $this->stack[] = $p;
152            $this->setReverseDependency($p->getHash(), $hash);
153        }
154        $this->next();
155    }
156
157    public function valid()
158    {
159        return $this->current !== null;
160    }
161
162    protected function detectDependencyCycles(string $cur, string $next)
163    {
164        if (!isset($this->reverse_dependencies[$next])) {
165            return;
166        }
167        if (in_array($cur, $this->reverse_dependencies[$next])) {
168            throw new UnachievableException(
169                "The objectives contain a dependency cycle and won't all be achievable."
170            );
171        }
172        foreach ($this->reverse_dependencies[$next] as $d) {
173            $this->detectDependencyCycles($cur, $d);
174        }
175    }
176
177    protected function setReverseDependency(string $other, string $cur)
178    {
179        if (!isset($this->reverse_dependencies[$other])) {
180            $this->reverse_dependencies[$other] = [];
181        }
182        $this->reverse_dependencies[$other][] = $cur;
183    }
184}
185