Hoa central
Coverage.php
Go to the documentation of this file.
1 <?php
2 
37 namespace Hoa\Compiler\Llk\Sampler;
38 
39 use Hoa\Compiler;
40 use Hoa\Iterator;
41 
62 class Coverage
63  extends Sampler
64  implements Iterator
65 {
71  protected $_todo = null;
72 
78  protected $_trace = null;
79 
85  protected $_tests = null;
86 
93  protected $_coveredRules = null;
94 
100  protected $_key = -1;
101 
107  protected $_current = null;
108 
109 
110 
116  public function current()
117  {
118  return $this->_current;
119  }
120 
126  public function key()
127  {
128  return $this->_key;
129  }
130 
136  public function next()
137  {
138  return;
139  }
140 
146  public function rewind()
147  {
148  $this->_key = -1;
149  $this->_current = null;
150  $this->_tests = [];
151  $this->_coveredRules = [];
152 
153  foreach ($this->_rules as $name => $rule) {
154  $this->_coveredRules[$name] = [];
155 
156  if ($rule instanceof Compiler\Llk\Rule\Repetition) {
157  $min = $rule->getMin();
158  $min1 = $min + 1;
159  $max = -1 == $rule->getMax() ? 2 : $rule->getMax();
160  $max1 = $max - 1;
161 
162  if ($min == $max) {
163  $this->_coveredRules[$name][$min] = 0;
164  } else {
165  $this->_coveredRules[$name][$min] = 0;
166  $this->_coveredRules[$name][$min1] = 0;
167  $this->_coveredRules[$name][$max1] = 0;
168  $this->_coveredRules[$name][$max] = 0;
169  }
170  } elseif ($rule instanceof Compiler\Llk\Rule\Choice) {
171  for ($i = 0, $max = count($rule->getContent()); $i < $max; ++$i) {
172  $this->_coveredRules[$name][$i] = 0;
173  }
174  } else {
175  $this->_coveredRules[$name][0] = 0;
176  }
177  }
178 
179  return;
180  }
181 
187  public function valid()
188  {
189  $ruleName = $this->_rootRuleName;
190 
191  if (true !== in_array(0, $this->_coveredRules[$ruleName]) &&
192  true !== in_array(.5, $this->_coveredRules[$ruleName])) {
193  return false;
194  }
195 
196  $this->_trace = [];
197  $this->_todo = [new Compiler\Llk\Rule\Entry(
198  $ruleName,
199  $this->_coveredRules
200  )];
201 
202  $result = $this->unfold();
203 
204  if (true !== $result) {
205  return false;
206  }
207 
208  $handle = null;
209 
210  foreach ($this->_trace as $trace) {
211  if ($trace instanceof Compiler\Llk\Rule\Token) {
212  $handle .= $this->generateToken($trace);
213  }
214  }
215 
216  ++$this->_key;
217  $this->_current = $handle;
218  $this->_tests[] = $this->_trace;
219 
220  foreach ($this->_coveredRules as $key => $value) {
221  foreach ($value as $k => $v) {
222  if (-1 == $v) {
223  $this->_coveredRules[$key][$k] = 0;
224  }
225  }
226  }
227 
228  return true;
229  }
230 
236  protected function unfold()
237  {
238  while (0 < count($this->_todo)) {
239  $pop = array_pop($this->_todo);
240 
241  if ($pop instanceof Compiler\Llk\Rule\Ekzit) {
242  $this->_trace[] = $pop;
243  $this->updateCoverage($pop);
244  } else {
245  $out = $this->coverage($this->_rules[$pop->getRule()]);
246 
247  if (true !== $out && true !== $this->backtrack()) {
248  return false;
249  }
250  }
251  }
252 
253  return true;
254  }
255 
262  protected function coverage(Compiler\Llk\Rule $rule)
263  {
264  $content = $rule->getContent();
265 
266  if ($rule instanceof Compiler\Llk\Rule\Repetition) {
267  $uncovered = [];
268  $inprogress = [];
269  $already = [];
270 
271  foreach ($this->_coveredRules[$rule->getName()] as $child => $value) {
272  if (0 == $value || .5 == $value) {
273  $uncovered[] = $child;
274  } elseif (-1 == $value) {
275  $inprogress[] = $child;
276  } else {
277  $already[] = $child;
278  }
279  }
280 
281  if (empty($uncovered)) {
282  if (empty($already)) {
283  $rand = $inprogress[rand(
284  0,
285  count($inprogress) - 1
286  )];
287  } else {
288  $rand = $already[rand(
289  0,
290  count($already) - 1
291  )];
292  }
293 
294  $this->_trace[] = new Compiler\Llk\Rule\Entry(
295  $rule->getName(),
298  );
299  $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
300  $rule->getName(),
301  $rand
302  );
303 
304  if ($this->_rules[$content] instanceof Compiler\Llk\Rule\Token) {
305  for ($i = 0; $i < $rand; ++$i) {
306  $this->_todo[] = new Compiler\Llk\Rule\Entry(
307  $content,
308  $this->_coveredRules,
309  $this->_todo
310  );
311  }
312  } else {
313  $sequence = $this->extract([$content]);
314 
315  if (null === $sequence) {
316  return null;
317  }
318 
319  for ($i = 0; $i < $rand; ++$i) {
320  foreach ($sequence as $seq) {
321  $this->_trace[] = $seq;
322 
323  if ($seq instanceof Compiler\Llk\Rule\Ekzit) {
324  $this->updateCoverage($seq);
325  }
326  }
327  }
328  }
329  } else {
330  $rand = $uncovered[rand(0, count($uncovered) - 1)];
331  $this->_coveredRules[$rule->getName()][$rand] = -1;
332  $this->_trace[] = new Compiler\Llk\Rule\Entry(
333  $rule->getName(),
336  );
337  $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
338  $rule->getName(),
339  $rand
340  );
341 
342  for ($i= 0 ; $i < $rand; ++$i) {
343  $this->_todo[] = new Compiler\Llk\Rule\Entry(
344  $content,
345  $this->_coveredRules,
346  $this->_todo
347  );
348  }
349  }
350 
351  return true;
352  } elseif ($rule instanceof Compiler\Llk\Rule\Choice) {
353  $uncovered = [];
354  $inprogress = [];
355  $already = [];
356 
357  foreach ($this->_coveredRules[$rule->getName()] as $child => $value) {
358  if (0 == $value || .5 == $value) {
359  $uncovered[] = $child;
360  } elseif (-1 == $value) {
361  $inprogress[] = $child;
362  } else {
363  $already[] = $child;
364  }
365  }
366 
367  if (empty($uncovered)) {
368  $this->_trace[] = new Compiler\Llk\Rule\Entry(
369  $rule->getName(),
372  );
373  $sequence = $this->extract($content);
374 
375  if (null === $sequence) {
376  return null;
377  }
378 
379  foreach ($sequence as $seq) {
380  $this->_trace[] = $seq;
381 
382  if ($seq instanceof Compiler\Llk\Rule\Ekzit) {
383  $this->updateCoverage($seq);
384  }
385  }
386 
387  if (empty($already)) {
388  $rand = $inprogress[rand(
389  0,
390  count($inprogress) - 1
391  )];
392  } else {
393  $rand = $already[rand(
394  0,
395  count($already) - 1
396  )];
397  }
398 
399  $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
400  $rule->getName(),
401  $rand
402  );
403  } else {
404  $rand = $uncovered[rand(0, count($uncovered) - 1)];
405  $this->_trace[] = new Compiler\Llk\Rule\Entry(
406  $rule->getName(),
409  );
410  $this->_coveredRules[$rule->getName()][$rand] = -1;
411  $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
412  $rule->getName(),
413  $rand
414  );
415  $this->_todo[] = new Compiler\Llk\Rule\Entry(
416  $content[$rand],
417  $this->_coveredRules,
418  $this->_todo
419  );
420  }
421 
422  return true;
423  } elseif ($rule instanceof Compiler\Llk\Rule\Concatenation) {
424  $this->_coveredRules[$rule->getName()][0] = -1;
425  $this->_trace[] = new Compiler\Llk\Rule\Entry(
426  $rule->getName(),
427  false
428  );
429  $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
430  $rule->getName(),
431  false
432  );
433 
434  for ($i = count($content) - 1; $i >= 0; --$i) {
435  $this->_todo[] = new Compiler\Llk\Rule\Entry(
436  $content[$i],
437  false,
438  $this->_todo
439  );
440  }
441 
442  return true;
443  } elseif ($rule instanceof Compiler\Llk\Rule\Token) {
444  $this->_trace[] = new Compiler\Llk\Rule\Entry(
445  $rule->getName(),
446  false
447  );
448  $this->_trace[] = $rule;
449  $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
450  $rule->getName(),
451  false
452  );
453 
454  return true;
455  }
456 
457  return false;
458  }
459 
466  protected function extract(Array $rules)
467  {
468  $out = [];
469 
470  foreach ($rules as $rule) {
471  foreach ($this->_tests as $test) {
472  $opened = 0;
473 
474  foreach ($test as $t) {
475  if ($t instanceof Compiler\Llk\Rule\Entry &&
476  $t->getRule() == $rule) {
477  ++$opened;
478  }
479 
480  if (0 < $opened) {
481  $out[] = $t;
482 
483  if ($t instanceof Compiler\Llk\Rule\Ekzit &&
484  $t->getRule() == $rule) {
485  --$opened;
486 
487  if (0 === $opened) {
488  return $out;
489  }
490  }
491  }
492  }
493  }
494  }
495 
496  foreach ($rules as $rule) {
497  $out = [];
498  $closed = 0;
499 
500  foreach ($this->_trace as $t) {
501  if ($t instanceof Compiler\Llk\Rule\Ekzit &&
502  $t->getRule() == $rule) {
503  ++$closed;
504  }
505 
506  if (0 < $closed) {
507  $out[] = $t;
508 
509  if ($t instanceof Compiler\Llk\Rule\Ekzit &&
510  $t->getRule() == $rule) {
511  --$closed;
512 
513  if (0 === $closed) {
514  return array_reverse($out);
515  }
516  }
517  }
518  }
519  }
520 
521  return null;
522  }
523 
529  protected function backtrack()
530  {
531  $found = false;
532 
533  do {
534  $pop = array_pop($this->_trace);
535 
536  if ($pop instanceof Compiler\Llk\Rule\Entry) {
537  $rule = $this->_rules[$pop->getRule()];
538  $found = $rule instanceof Compiler\Llk\Rule\Choice ||
539  $rule instanceof Compiler\Llk\Rule\Repetition;
540  }
541  } while (0 < count($this->_trace) && false === $found);
542 
543  if (false === $found) {
544  return false;
545  }
546 
547  $ruleName = $pop->getRule();
548  $this->_covered = $pop->getData();
549  $this->_todo = $pop->getTodo();
550  $this->_todo[] = new Compiler\Llk\Rule\Entry(
551  $ruleName,
552  $this->_covered,
553  $this->_todo
554  );
555 
556  return true;
557  }
558 
565  protected function updateCoverage(Compiler\Llk\Rule\Ekzit $Rule)
566  {
567  $ruleName = $Rule->getRule();
568  $child = $Rule->getData();
569  $rule = $this->_rules[$ruleName];
570  $content = $rule->getContent();
571 
572  if ($rule instanceof Compiler\Llk\Rule\Repetition) {
573  if (0 === $child) {
574  $this->_coveredRules[$ruleName][$child] = 1;
575  } else {
576  if (true === $this->allCovered($content) ||
577  true === $this->checkRuleRoot($content)) {
578  $this->_coveredRules[$ruleName][$child] = 1;
579 
580  foreach ($this->_coveredRules[$ruleName] as $child => $value) {
581  if (.5 == $value) {
582  $this->_coveredRules[$ruleName][$child] = 1;
583  }
584  }
585  } else {
586  $this->_coveredRules[$ruleName][$child] = .5;
587  }
588  }
589  } elseif ($rule instanceof Compiler\Llk\Rule\Choice) {
590  if (true === $this->allCovered($content[$child]) ||
591  true === $this->checkRuleRoot($content[$child])) {
592  $this->_coveredRules[$ruleName][$child] = 1;
593  } else {
594  $this->_coveredRules[$ruleName][$child] = .5;
595  }
596  } elseif ($rule instanceof Compiler\Llk\Rule\Concatenation) {
597  $isCovered = true;
598 
599  for ($i = count($content) - 1; $i >= 0 && true === $isCovered; --$i) {
600  if (false === $this->allCovered($content[$i]) &&
601  false === $this->checkRuleRoot($content[$i])) {
602  $isCovered = false;
603  }
604  }
605 
606  $this->_coveredRules[$ruleName][0] = true === $isCovered ? 1 : .5;
607  } elseif ($rule instanceof Compiler\Llk\Rule\Token) {
608  $this->_coveredRules[$ruleName][0] = 1;
609  }
610 
611  return;
612  }
613 
620  protected function allCovered($ruleName)
621  {
622  foreach ($this->_coveredRules[$ruleName] as $value) {
623  if (1 !== $value) {
624  return false;
625  }
626  }
627 
628  return true;
629  }
630 
637  protected function checkRuleRoot($ruleName)
638  {
639  if (true === $this->_rules[$ruleName]->isTransitional()) {
640  return false;
641  }
642 
643  $i = count($this->_trace) - 1;
644  $nb = 0;
645 
646  while ($i >= 0) {
647  $lastRule = $this->_trace[$i];
648 
649  if ($lastRule instanceof Compiler\Llk\Rule\Entry) {
650  if ($lastRule->getRule() == $ruleName) {
651  ++$nb;
652  }
653  } elseif ($lastRule instanceof Compiler\Llk\Rule\Ekzit) {
654  if ($lastRule->getRule() == $ruleName) {
655  --$nb;
656  }
657  }
658 
659  --$i;
660  }
661 
662  return 0 < $nb;
663  }
664 }
coverage(Compiler\Llk\Rule $rule)
Definition: Coverage.php:262
generateToken(Compiler\Llk\Rule\Token $token)
Definition: Sampler.php:188
updateCoverage(Compiler\Llk\Rule\Ekzit $Rule)
Definition: Coverage.php:565
$content
Definition: Hoa.php:119