1<?php
2
3/**
4 * Hoa
5 *
6 *
7 * @license
8 *
9 * New BSD License
10 *
11 * Copyright © 2007-2017, Hoa community. All rights reserved.
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions are met:
15 *     * Redistributions of source code must retain the above copyright
16 *       notice, this list of conditions and the following disclaimer.
17 *     * Redistributions in binary form must reproduce the above copyright
18 *       notice, this list of conditions and the following disclaimer in the
19 *       documentation and/or other materials provided with the distribution.
20 *     * Neither the name of the Hoa nor the names of its contributors may be
21 *       used to endorse or promote products derived from this software without
22 *       specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
25 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS AND CONTRIBUTORS BE
28 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
29 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
30 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
31 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
32 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
33 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34 * POSSIBILITY OF SUCH DAMAGE.
35 */
36
37namespace Hoa\Compiler\Llk\Sampler;
38
39use Hoa\Compiler;
40use Hoa\Iterator;
41use Hoa\Visitor;
42
43/**
44 * Class \Hoa\Compiler\Llk\Sampler\BoundedExhaustive.
45 *
46 * This generator aims at producing all possible data (exhaustive) up to a given
47 * size n (bounded).
48 * This algorithm is based on multiset (set with repetition).
49 * Repetition unfolding: upper bound of + and * is set to n.
50 *
51 * @copyright  Copyright © 2007-2017 Hoa community
52 * @license    New BSD License
53 */
54class BoundedExhaustive extends Sampler implements Iterator
55{
56    /**
57     * Stack of rules to explore.
58     *
59     * @var array
60     */
61    protected $_todo    = null;
62
63    /**
64     * Stack of rules that have already been covered.
65     *
66     * @var array
67     */
68    protected $_trace   = null;
69
70    /**
71     * Current iterator key.
72     *
73     * @var int
74     */
75    protected $_key     = -1;
76
77    /**
78     * Current iterator value.
79     *
80     * @var string
81     */
82    protected $_current = null;
83
84    /**
85     * Bound.
86     *
87     * @var int
88     */
89    protected $_length  = 5;
90
91
92
93    /**
94     * Construct a generator.
95     *
96     * @param   \Hoa\Compiler\Llk\Parser  $compiler        Compiler/parser.
97     * @param   \Hoa\Visitor\Visit        $tokenSampler    Token sampler.
98     * @param   int                       $length          Max data length.
99     */
100    public function __construct(
101        Compiler\Llk\Parser $compiler,
102        Visitor\Visit       $tokenSampler,
103        $length = 5
104    ) {
105        parent::__construct($compiler, $tokenSampler);
106        $this->setLength($length);
107
108        return;
109    }
110
111    /**
112     * Get the current iterator value.
113     *
114     * @return  string
115     */
116    public function current()
117    {
118        return $this->_current;
119    }
120
121    /**
122     * Get the current iterator key.
123     *
124     * @return  int
125     */
126    public function key()
127    {
128        return $this->_key;
129    }
130
131    /**
132     * Useless here.
133     *
134     * @return  void
135     */
136    public function next()
137    {
138        return;
139    }
140
141    /**
142     * Rewind the internal iterator pointer.
143     *
144     * @return  void
145     */
146    public function rewind()
147    {
148        $ruleName       = $this->_rootRuleName;
149        $this->_current = null;
150        $this->_key     = -1;
151        $this->_trace   = [];
152        $handle         = new Compiler\Llk\Rule\Ekzit($ruleName, 0);
153        $this->_todo    = [
154            $handle,
155            new Compiler\Llk\Rule\Entry($ruleName, 0, [$handle])
156        ];
157
158        return;
159    }
160
161    /**
162     * Compute the current iterator value, i.e. generate a new solution.
163     *
164     * @return  bool
165     */
166    public function valid()
167    {
168        if (false === $this->unfold()) {
169            return false;
170        }
171
172        $handle = null;
173
174        foreach ($this->_trace as $trace) {
175            if ($trace instanceof Compiler\Llk\Rule\Token) {
176                $handle .= $this->generateToken($trace);
177            }
178        }
179
180        ++$this->_key;
181        $this->_current = $handle;
182
183        return $this->backtrack();
184    }
185
186    /**
187     * Unfold rules from the todo stack.
188     *
189     * @return  bool
190     */
191    protected function unfold()
192    {
193        while (0 < count($this->_todo)) {
194            $pop = array_pop($this->_todo);
195
196            if ($pop instanceof Compiler\Llk\Rule\Ekzit) {
197                $this->_trace[] = $pop;
198            } else {
199                $ruleName = $pop->getRule();
200                $next     = $pop->getData();
201                $rule     = $this->_rules[$ruleName];
202                $out      = $this->boundedExhaustive($rule, $next);
203
204                if (true !== $out && true !== $this->backtrack()) {
205                    return false;
206                }
207            }
208        }
209
210        return true;
211    }
212
213    /**
214     * The bounded-exhaustive algorithm.
215     *
216     * @param   \Hoa\Compiler\Llk\Rule  $rule    Rule to cover.
217     * @param   int                     $next    Next rule.
218     * @return  bool
219     */
220    protected function boundedExhaustive(Compiler\Llk\Rule $rule, $next)
221    {
222        $children = $rule->getChildren();
223
224        if ($rule instanceof Compiler\Llk\Rule\Repetition) {
225            if (0 === $next) {
226                $this->_trace[] = new Compiler\Llk\Rule\Entry(
227                    $rule->getName(),
228                    $rule->getMin()
229                );
230
231                array_pop($this->_todo);
232                $this->_todo[]  = new Compiler\Llk\Rule\Ekzit(
233                    $rule->getName(),
234                    $rule->getMin(),
235                    $this->_todo
236                );
237
238                for ($i = 0, $min = $rule->getMin(); $i < $min; ++$i) {
239                    $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
240                        $children,
241                        0
242                    );
243                    $this->_todo[] = new Compiler\Llk\Rule\Entry(
244                        $children,
245                        0
246                    );
247                }
248            } else {
249                $nbToken = 0;
250
251                foreach ($this->_trace as $trace) {
252                    if ($trace instanceof Compiler\Llk\Rule\Token) {
253                        ++$nbToken;
254                    }
255                }
256
257                $max = $rule->getMax();
258
259                if (-1 != $max && $next > $max) {
260                    return false;
261                }
262
263                $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
264                    $rule->getName(),
265                    $next,
266                    $this->_todo
267                );
268                $this->_todo[] = new Compiler\Llk\Rule\Ekzit($children, 0);
269                $this->_todo[] = new Compiler\Llk\Rule\Entry($children, 0);
270            }
271
272            return true;
273        } elseif ($rule instanceof Compiler\Llk\Rule\Choice) {
274            if (count($children) <= $next) {
275                return false;
276            }
277
278            $this->_trace[] = new Compiler\Llk\Rule\Entry(
279                $rule->getName(),
280                $next,
281                $this->_todo
282            );
283            $nextRule      = $children[$next];
284            $this->_todo[] = new Compiler\Llk\Rule\Ekzit($nextRule, 0);
285            $this->_todo[] = new Compiler\Llk\Rule\Entry($nextRule, 0);
286
287            return true;
288        } elseif ($rule instanceof Compiler\Llk\Rule\Concatenation) {
289            $this->_trace[] = new Compiler\Llk\Rule\Entry(
290                $rule->getName(),
291                $next
292            );
293
294            for ($i = count($children) - 1; $i >= 0; --$i) {
295                $nextRule      = $children[$i];
296                $this->_todo[] = new Compiler\Llk\Rule\Ekzit($nextRule, 0);
297                $this->_todo[] = new Compiler\Llk\Rule\Entry($nextRule, 0);
298            }
299
300            return true;
301        } elseif ($rule instanceof Compiler\Llk\Rule\Token) {
302            $nbToken = 0;
303
304            foreach ($this->_trace as $trace) {
305                if ($trace instanceof Compiler\Llk\Rule\Token) {
306                    ++$nbToken;
307                }
308            }
309
310            if ($nbToken >= $this->getLength()) {
311                return false;
312            }
313
314            $this->_trace[] = $rule;
315            array_pop($this->_todo);
316
317            return true;
318        }
319
320        return false;
321    }
322
323    /**
324     * Backtrack to the previous choice-point.
325     *
326     * @return  bool
327     */
328    protected function backtrack()
329    {
330        $found = false;
331
332        do {
333            $last = array_pop($this->_trace);
334
335            if ($last instanceof Compiler\Llk\Rule\Entry) {
336                $rule  = $this->_rules[$last->getRule()];
337                $found = $rule instanceof Compiler\Llk\Rule\Choice;
338            } elseif ($last instanceof Compiler\Llk\Rule\Ekzit) {
339                $rule  = $this->_rules[$last->getRule()];
340                $found = $rule instanceof Compiler\Llk\Rule\Repetition;
341            }
342        } while (0 < count($this->_trace) && false === $found);
343
344        if (false === $found) {
345            return false;
346        }
347
348        $rule          = $last->getRule();
349        $next          = $last->getData() + 1;
350        $this->_todo   = $last->getTodo();
351        $this->_todo[] = new Compiler\Llk\Rule\Entry(
352            $rule,
353            $next,
354            $this->_todo
355        );
356
357        return true;
358    }
359
360    /**
361     * Set upper-bound, the maximum data length.
362     *
363     * @param   int  $length    Length.
364     * @return  int
365     * @throws  \Hoa\Compiler\Exception
366     */
367    public function setLength($length)
368    {
369        if (0 >= $length) {
370            throw new Exception(
371                'Length must be greater than 0, given %d.',
372                0,
373                $length
374            );
375        }
376
377        $old           = $this->_length;
378        $this->_length = $length;
379
380        return $old;
381    }
382
383    /**
384     * Get upper-bound.
385     *
386     * @return  int
387     */
388    public function getLength()
389    {
390        return $this->_length;
391    }
392}
393