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;
41
42/**
43 * Class \Hoa\Compiler\Llk\Sampler\Coverage.
44 *
45 * This generator aims at producing data that activate all the branches of the
46 * grammar rules.
47 * A rule is said to be covered if and only if its sub-rules have all been
48 * covered. A token is said to be covered if it has been successfully used in a
49 * data generation.
50 * To ensure diversity, a random choice is made amongst the remaining sub-rules
51 * of a choice-point to cover.
52 * Finally, we use boundary test generation heuristics to avoid combinatorial
53 * explosion and guarantee the termination, i.e. we bound repetition operators
54 * as follow:
55 *      • * is bounded to 0, 1 or 2;
56 *      • + is unfolded 1 or 2 times;
57 *      • {x,y} is unfolded x, x + 1, y - 1 and y times.
58 *
59 * @copyright  Copyright © 2007-2017 Hoa community
60 * @license    New BSD License
61 */
62class Coverage extends Sampler implements Iterator
63{
64    /**
65     * Stack of rules to explore.
66     *
67     * @var array
68     */
69    protected $_todo         = null;
70
71    /**
72     * Stack of rules that have already been covered.
73     *
74     * @var array
75     */
76    protected $_trace        = null;
77
78    /**
79     * Produced test cases.
80     *
81     * @var array
82     */
83    protected $_tests        = null;
84
85    /**
86     * Covered rules: ruleName to structure that contains the choice point and
87     * 0 for uncovered, 1 for covered, -1 for failed and .5 for in progress.
88     *
89     * @var array
90     */
91    protected $_coveredRules = null;
92
93    /**
94     * Current iterator key.
95     *
96     * @var int
97     */
98    protected $_key          = -1;
99
100    /**
101     * Current iterator value.
102     *
103     * @var string
104     */
105    protected $_current      = null;
106
107
108
109    /**
110     * Get the current iterator value.
111     *
112     * @return  string
113     */
114    public function current()
115    {
116        return $this->_current;
117    }
118
119    /**
120     * Get the current iterator key.
121     *
122     * @return  int
123     */
124    public function key()
125    {
126        return $this->_key;
127    }
128
129    /**
130     * Useless here.
131     *
132     * @return  void
133     */
134    public function next()
135    {
136        return;
137    }
138
139    /**
140     * Rewind the internal iterator pointer.
141     *
142     * @return  void
143     */
144    public function rewind()
145    {
146        $this->_key          = -1;
147        $this->_current      = null;
148        $this->_tests        = [];
149        $this->_coveredRules = [];
150
151        foreach ($this->_rules as $name => $rule) {
152            $this->_coveredRules[$name] = [];
153
154            if ($rule instanceof Compiler\Llk\Rule\Repetition) {
155                $min  = $rule->getMin();
156                $min1 = $min + 1;
157                $max  = -1 == $rule->getMax() ? 2 : $rule->getMax();
158                $max1 = $max - 1;
159
160                if ($min == $max) {
161                    $this->_coveredRules[$name][$min]  = 0;
162                } else {
163                    $this->_coveredRules[$name][$min]  = 0;
164                    $this->_coveredRules[$name][$min1] = 0;
165                    $this->_coveredRules[$name][$max1] = 0;
166                    $this->_coveredRules[$name][$max]  = 0;
167                }
168            } elseif ($rule instanceof Compiler\Llk\Rule\Choice) {
169                for ($i = 0, $max = count($rule->getChildren()); $i < $max; ++$i) {
170                    $this->_coveredRules[$name][$i] = 0;
171                }
172            } else {
173                $this->_coveredRules[$name][0] = 0;
174            }
175        }
176
177        return;
178    }
179
180    /**
181     * Compute the current iterator value, i.e. generate a new solution.
182     *
183     * @return  bool
184     */
185    public function valid()
186    {
187        $ruleName = $this->_rootRuleName;
188
189        if (true !== in_array(0,  $this->_coveredRules[$ruleName]) &&
190            true !== in_array(.5, $this->_coveredRules[$ruleName])) {
191            return false;
192        }
193
194        $this->_trace = [];
195        $this->_todo  = [new Compiler\Llk\Rule\Entry(
196            $ruleName,
197            $this->_coveredRules
198        )];
199
200        $result = $this->unfold();
201
202        if (true !== $result) {
203            return false;
204        }
205
206        $handle = null;
207
208        foreach ($this->_trace as $trace) {
209            if ($trace instanceof Compiler\Llk\Rule\Token) {
210                $handle .= $this->generateToken($trace);
211            }
212        }
213
214        ++$this->_key;
215        $this->_current = $handle;
216        $this->_tests[] = $this->_trace;
217
218        foreach ($this->_coveredRules as $key => $value) {
219            foreach ($value as $k => $v) {
220                if (-1 == $v) {
221                    $this->_coveredRules[$key][$k] = 0;
222                }
223            }
224        }
225
226        return true;
227    }
228
229    /**
230     * Unfold rules from the todo stack.
231     *
232     * @return  bool
233     */
234    protected function unfold()
235    {
236        while (0 < count($this->_todo)) {
237            $pop = array_pop($this->_todo);
238
239            if ($pop instanceof Compiler\Llk\Rule\Ekzit) {
240                $this->_trace[] = $pop;
241                $this->updateCoverage($pop);
242            } else {
243                $out = $this->coverage($this->_rules[$pop->getRule()]);
244
245                if (true !== $out && true !== $this->backtrack()) {
246                    return false;
247                }
248            }
249        }
250
251        return true;
252    }
253
254    /**
255     * The coverage algorithm.
256     *
257     * @param   \Hoa\Compiler\Llk\Rule  $rule    Rule to cover.
258     * @return  bool
259     */
260    protected function coverage(Compiler\Llk\Rule $rule)
261    {
262        $children = $rule->getChildren();
263
264        if ($rule instanceof Compiler\Llk\Rule\Repetition) {
265            $uncovered  = [];
266            $inprogress = [];
267            $already    = [];
268
269            foreach ($this->_coveredRules[$rule->getName()] as $child => $value) {
270                if (0 == $value || .5 == $value) {
271                    $uncovered[]  = $child;
272                } elseif (-1 == $value) {
273                    $inprogress[] = $child;
274                } else {
275                    $already[]    = $child;
276                }
277            }
278
279            if (empty($uncovered)) {
280                if (empty($already)) {
281                    $rand = $inprogress[rand(
282                        0,
283                        count($inprogress) - 1
284                    )];
285                } else {
286                    $rand = $already[rand(
287                        0,
288                        count($already) - 1
289                    )];
290                }
291
292                $this->_trace[] = new Compiler\Llk\Rule\Entry(
293                    $rule->getName(),
294                    $this->_coveredRules,
295                    $this->_todo
296                );
297                $this->_todo[]  = new Compiler\Llk\Rule\Ekzit(
298                    $rule->getName(),
299                    $rand
300                );
301
302                if ($this->_rules[$children] instanceof Compiler\Llk\Rule\Token) {
303                    for ($i = 0; $i < $rand; ++$i) {
304                        $this->_todo[] = new Compiler\Llk\Rule\Entry(
305                            $children,
306                            $this->_coveredRules,
307                            $this->_todo
308                        );
309                    }
310                } else {
311                    $sequence = $this->extract([$children]);
312
313                    if (null === $sequence) {
314                        return null;
315                    }
316
317                    for ($i = 0; $i < $rand; ++$i) {
318                        foreach ($sequence as $seq) {
319                            $this->_trace[] = $seq;
320
321                            if ($seq instanceof Compiler\Llk\Rule\Ekzit) {
322                                $this->updateCoverage($seq);
323                            }
324                        }
325                    }
326                }
327            } else {
328                $rand                                         = $uncovered[rand(0, count($uncovered) - 1)];
329                $this->_coveredRules[$rule->getName()][$rand] = -1;
330                $this->_trace[]                               = new Compiler\Llk\Rule\Entry(
331                    $rule->getName(),
332                    $this->_coveredRules,
333                    $this->_todo
334                );
335                $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
336                    $rule->getName(),
337                    $rand
338                );
339
340                for ($i= 0 ; $i < $rand; ++$i) {
341                    $this->_todo[] = new Compiler\Llk\Rule\Entry(
342                        $children,
343                        $this->_coveredRules,
344                        $this->_todo
345                    );
346                }
347            }
348
349            return true;
350        } elseif ($rule instanceof Compiler\Llk\Rule\Choice) {
351            $uncovered  = [];
352            $inprogress = [];
353            $already    = [];
354
355            foreach ($this->_coveredRules[$rule->getName()] as $child => $value) {
356                if (0 == $value || .5 == $value) {
357                    $uncovered[]  = $child;
358                } elseif (-1 == $value) {
359                    $inprogress[] = $child;
360                } else {
361                    $already[]    = $child;
362                }
363            }
364
365            if (empty($uncovered)) {
366                $this->_trace[] = new Compiler\Llk\Rule\Entry(
367                    $rule->getName(),
368                    $this->_coveredRules,
369                    $this->_todo
370                );
371                $sequence = $this->extract($children);
372
373                if (null === $sequence) {
374                    return null;
375                }
376
377                foreach ($sequence as $seq) {
378                    $this->_trace[] = $seq;
379
380                    if ($seq instanceof Compiler\Llk\Rule\Ekzit) {
381                        $this->updateCoverage($seq);
382                    }
383                }
384
385                if (empty($already)) {
386                    $rand = $inprogress[rand(
387                        0,
388                        count($inprogress) - 1
389                    )];
390                } else {
391                    $rand = $already[rand(
392                        0,
393                        count($already) - 1
394                    )];
395                }
396
397                $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
398                    $rule->getName(),
399                    $rand
400                );
401            } else {
402                $rand           = $uncovered[rand(0, count($uncovered) - 1)];
403                $this->_trace[] = new Compiler\Llk\Rule\Entry(
404                    $rule->getName(),
405                    $this->_coveredRules,
406                    $this->_todo
407                );
408                $this->_coveredRules[$rule->getName()][$rand] = -1;
409                $this->_todo[]                                = new Compiler\Llk\Rule\Ekzit(
410                    $rule->getName(),
411                    $rand
412                );
413                $this->_todo[]  = new Compiler\Llk\Rule\Entry(
414                    $children[$rand],
415                    $this->_coveredRules,
416                    $this->_todo
417                );
418            }
419
420            return true;
421        } elseif ($rule instanceof Compiler\Llk\Rule\Concatenation) {
422            $this->_coveredRules[$rule->getName()][0] = -1;
423            $this->_trace[]                           = new Compiler\Llk\Rule\Entry(
424                $rule->getName(),
425                false
426            );
427            $this->_todo[]  = new Compiler\Llk\Rule\Ekzit(
428                $rule->getName(),
429                false
430            );
431
432            for ($i = count($children) - 1; $i >= 0; --$i) {
433                $this->_todo[] = new Compiler\Llk\Rule\Entry(
434                    $children[$i],
435                    false,
436                    $this->_todo
437                );
438            }
439
440            return true;
441        } elseif ($rule instanceof Compiler\Llk\Rule\Token) {
442            $this->_trace[] = new Compiler\Llk\Rule\Entry(
443                $rule->getName(),
444                false
445            );
446            $this->_trace[] = $rule;
447            $this->_todo[]  = new Compiler\Llk\Rule\Ekzit(
448                $rule->getName(),
449                false
450            );
451
452            return true;
453        }
454
455        return false;
456    }
457
458    /**
459     * Extract a given sequence from existing traces.
460     *
461     * @param   array  $rules    Rules to consider.
462     * @return  array
463     */
464    protected function extract(array $rules)
465    {
466        $out = [];
467
468        foreach ($rules as $rule) {
469            foreach ($this->_tests as $test) {
470                $opened = 0;
471
472                foreach ($test as $t) {
473                    if ($t instanceof Compiler\Llk\Rule\Entry &&
474                        $t->getRule() == $rule) {
475                        ++$opened;
476                    }
477
478                    if (0 < $opened) {
479                        $out[] = $t;
480
481                        if ($t instanceof Compiler\Llk\Rule\Ekzit &&
482                            $t->getRule() == $rule) {
483                            --$opened;
484
485                            if (0 === $opened) {
486                                return $out;
487                            }
488                        }
489                    }
490                }
491            }
492        }
493
494        foreach ($rules as $rule) {
495            $out    = [];
496            $closed = 0;
497
498            foreach ($this->_trace as $t) {
499                if ($t instanceof Compiler\Llk\Rule\Ekzit &&
500                    $t->getRule() == $rule) {
501                    ++$closed;
502                }
503
504                if (0 < $closed) {
505                    $out[] = $t;
506
507                    if ($t instanceof Compiler\Llk\Rule\Ekzit &&
508                        $t->getRule() == $rule) {
509                        --$closed;
510
511                        if (0 === $closed) {
512                            return array_reverse($out);
513                        }
514                    }
515                }
516            }
517        }
518
519        return null;
520    }
521
522    /**
523     * Backtrack to the previous choice-point.
524     *
525     * @return  bool
526     */
527    protected function backtrack()
528    {
529        $found = false;
530
531        do {
532            $pop = array_pop($this->_trace);
533
534            if ($pop instanceof Compiler\Llk\Rule\Entry) {
535                $rule  = $this->_rules[$pop->getRule()];
536                $found = $rule instanceof Compiler\Llk\Rule\Choice ||
537                         $rule instanceof Compiler\Llk\Rule\Repetition;
538            }
539        } while (0 < count($this->_trace) && false === $found);
540
541        if (false === $found) {
542            return false;
543        }
544
545        $ruleName       = $pop->getRule();
546        $this->_covered = $pop->getData();
547        $this->_todo    = $pop->getTodo();
548        $this->_todo[]  = new Compiler\Llk\Rule\Entry(
549            $ruleName,
550            $this->_covered,
551            $this->_todo
552        );
553
554        return true;
555    }
556
557    /**
558     * Update coverage of a rule.
559     *
560     * @param   \Hoa\Compiler\Llk\Rule\Ekzit  $rule    Rule to consider.
561     * @return  void
562     */
563    protected function updateCoverage(Compiler\Llk\Rule\Ekzit $Rule)
564    {
565        $ruleName = $Rule->getRule();
566        $child    = $Rule->getData();
567        $rule     = $this->_rules[$ruleName];
568        $children = $rule->getChildren();
569
570        if ($rule instanceof Compiler\Llk\Rule\Repetition) {
571            if (0 === $child) {
572                $this->_coveredRules[$ruleName][$child] = 1;
573            } else {
574                if (true === $this->allCovered($children) ||
575                    true === $this->checkRuleRoot($children)) {
576                    $this->_coveredRules[$ruleName][$child] = 1;
577
578                    foreach ($this->_coveredRules[$ruleName] as $child => $value) {
579                        if (.5 == $value) {
580                            $this->_coveredRules[$ruleName][$child] = 1;
581                        }
582                    }
583                } else {
584                    $this->_coveredRules[$ruleName][$child] = .5;
585                }
586            }
587        } elseif ($rule instanceof Compiler\Llk\Rule\Choice) {
588            if (true === $this->allCovered($children[$child]) ||
589                true === $this->checkRuleRoot($children[$child])) {
590                $this->_coveredRules[$ruleName][$child] = 1;
591            } else {
592                $this->_coveredRules[$ruleName][$child] = .5;
593            }
594        } elseif ($rule instanceof Compiler\Llk\Rule\Concatenation) {
595            $isCovered = true;
596
597            for ($i = count($children) - 1; $i >= 0 && true === $isCovered; --$i) {
598                if (false === $this->allCovered($children[$i]) &&
599                    false === $this->checkRuleRoot($children[$i])) {
600                    $isCovered = false;
601                }
602            }
603
604            $this->_coveredRules[$ruleName][0] = true === $isCovered ? 1 : .5;
605        } elseif ($rule instanceof Compiler\Llk\Rule\Token) {
606            $this->_coveredRules[$ruleName][0] = 1;
607        }
608
609        return;
610    }
611
612    /**
613     * Check if all rules have been entirely covered.
614     *
615     * @param   string  $ruleName    Rule name.
616     * @return  bool
617     */
618    protected function allCovered($ruleName)
619    {
620        foreach ($this->_coveredRules[$ruleName] as $value) {
621            if (1 !== $value) {
622                return false;
623            }
624        }
625
626        return true;
627    }
628
629    /**
630     * Check if a rule is a root rule that is currently being processed.
631     *
632     * @param   string  $ruleName    Rule name.
633     * @return  bool
634     */
635    protected function checkRuleRoot($ruleName)
636    {
637        if (true === $this->_rules[$ruleName]->isTransitional()) {
638            return false;
639        }
640
641        $i  = count($this->_trace) - 1;
642        $nb = 0;
643
644        while ($i >= 0) {
645            $lastRule = $this->_trace[$i];
646
647            if ($lastRule instanceof Compiler\Llk\Rule\Entry) {
648                if ($lastRule->getRule() == $ruleName) {
649                    ++$nb;
650                }
651            } elseif ($lastRule instanceof Compiler\Llk\Rule\Ekzit) {
652                if ($lastRule->getRule() == $ruleName) {
653                    --$nb;
654                }
655            }
656
657            --$i;
658        }
659
660        return 0 < $nb;
661    }
662}
663