aboutsummaryrefslogtreecommitdiffstats
path: root/Iterator
diff options
context:
space:
mode:
authorIvan Enderlin <ivan.enderlin@hoa-project.net>2014-03-31 22:57:29 +0200
committerIvan Enderlin <ivan.enderlin@hoa-project.net>2014-04-01 14:31:12 +0200
commit78d81ac4a1077cfc455ccacff1c5e9b9aa345459 (patch)
tree6877d305f69f746b9f0d8c81498fd5cb680681b0 /Iterator
parent080f7b8777d237aeadae68b8e716c7b8ccd7bc0a (diff)
downloadPraspel-78d81ac4a1077cfc455ccacff1c5e9b9aa345459.zip
Praspel-78d81ac4a1077cfc455ccacff1c5e9b9aa345459.tar.gz
Praspel-78d81ac4a1077cfc455ccacff1c5e9b9aa345459.tar.bz2
Totally new structural coverage algorithm.
Much faster, much simpler to maintain and consider recents changes in Praspel (cf research papers).
Diffstat (limited to 'Iterator')
-rw-r--r--Iterator/Coverage/Structural.php334
1 files changed, 174 insertions, 160 deletions
diff --git a/Iterator/Coverage/Structural.php b/Iterator/Coverage/Structural.php
index d59b208..77c496b 100644
--- a/Iterator/Coverage/Structural.php
+++ b/Iterator/Coverage/Structural.php
@@ -39,6 +39,11 @@ namespace {
from('Hoa')
/**
+ * \Hoa\Praspel\Exception\Generic
+ */
+-> import('Praspel.Exception.Generic')
+
+/**
* \Hoa\Praspel\Iterator\WeakStack
*/
-> import('Praspel.Iterator.WeakStack')
@@ -85,6 +90,34 @@ namespace Hoa\Praspel\Iterator\Coverage {
class Structural implements \Hoa\Iterator\Recursive {
/**
+ * State of the iterator: will compute a @requires clause.
+ *
+ * @const int
+ */
+ const STATE_REQUIRES = 0;
+
+ /**
+ * State of the iterator: will compute a @behavior clause.
+ *
+ * @const int
+ */
+ const STATE_BEHAVIOR = 1;
+
+ /**
+ * State of the iterator: will compute an @ensures clause.
+ *
+ * @const int
+ */
+ const STATE_ENSURES = 2;
+
+ /**
+ * State of the iterator: will compute a @throwable clause.
+ *
+ * @const int
+ */
+ const STATE_THROWABLE = 3;
+
+ /**
* Specification to cover.
*
* @var \Hoa\Praspel\Model\Specification object
@@ -100,6 +133,13 @@ class Structural implements \Hoa\Iterator\Recursive {
// | Coverage::CRITERIA_EXCEPTIONAL
/**
+ * Path.
+ *
+ * @var \SplQueue object
+ */
+ protected $_path = null;
+
+ /**
* Stack (to manage backtracks, yields, etc.)
*
* @var \SplStack object
@@ -107,11 +147,18 @@ class Structural implements \Hoa\Iterator\Recursive {
protected $_stack = null;
/**
+ * Pop queue (when we should pop an element from the path).
+ *
+ * @var \SplQueue
+ */
+ protected $_pop = null;
+
+ /**
* Key.
*
* @var \Hoa\Praspel\Iterator\Coverage\Structural int
*/
- protected $_key = 0;
+ protected $_key = -1;
/**
* Current (with two indexes: pre and post, with SplStack
@@ -121,20 +168,6 @@ class Structural implements \Hoa\Iterator\Recursive {
*/
protected $_current = null;
- /**
- * Whether the algorithm is backtracking or not.
- *
- * @var \Hoa\Praspel\Iterator\Coverage\Structural bool
- */
- protected $_up = false;
-
- /**
- * Post-condition clause: ensure or throwable.
- *
- * @var \Hoa\Praspel\Iterator\Coverage\Structural string
- */
- protected $_post = 'ensures';
-
/**
@@ -162,7 +195,15 @@ class Structural implements \Hoa\Iterator\Recursive {
*/
public function current ( ) {
- return $this->_current;
+ $out = array('pre' => array(), 'post' => array());
+
+ foreach($this->_path as $element)
+ if($element instanceof \Hoa\Praspel\Model\Requires)
+ $out['pre'][] = $element;
+ else
+ $out['post'][] = $element;
+
+ return $out;
}
/**
@@ -180,119 +221,127 @@ class Structural implements \Hoa\Iterator\Recursive {
* Advance the internal collection pointer, and return the current value.
*
* @access public
- * @return array
+ * @return void
*/
public function next ( ) {
- $collection = $this->_stack->top();
-
- if($collection instanceof \Hoa\Praspel\Model\Specification) {
-
- if(true === $this->_up) {
-
- if( 'ensures' === $this->_post
- && 0 !== (Coverage::CRITERIA_EXCEPTIONAL & $this->getCriteria())) {
-
- $this->_up = false;
- $this->_post = 'throwable';
- ++$this->_key;
- $this->_rewindCurrent();
-
- return $this->current();
- }
-
- unset($this->_current);
- $this->_current = null;
-
- return $this->current();
- }
-
- if(true === $collection->clauseExists('behavior'))
- return $this->_next($collection);
-
- $this->_up = true;
-
- return $this->next();
- }
- elseif($collection instanceof \Hoa\Praspel\Model\DefaultBehavior) {
-
- if(false === $this->_up) {
-
- $this->pushCurrent($collection);
- $this->_up = true;
- ++$this->_key;
+ $this->_current = null;
- return $this->current();
- }
+ if(0 === count($this->_stack))
+ return;
- $this->_current['pre']->pop();
- $this->_current['post']->pop();
+ while(0 === $this->_pop->top()) {
- $this->_stack->pop();
-
- return $this->next();
+ $this->_pop->pop();
+ $this->_path->pop();
+ $this->_pop->push($this->_pop->pop() - 1);
}
- $handle = current($collection);
-
- if( false === $this->_up
- && true === $handle->clauseExists('behavior'))
- return $this->_next($handle);
-
- $this->_current['pre']->pop();
- $this->_current['post']->pop();
+ list($behavior, $state) = array_values($this->_stack->pop());
- next($collection);
- $nextHandle = current($collection);
+ switch($state) {
- if(false === $nextHandle) {
+ case static::STATE_REQUIRES:
+ ++$this->_key;
+ $this->_current = $behavior->getClause('requires');
+ $this->_path->push($this->_current);
+
+ if(true === $behavior->clauseExists('behavior')) {
+
+ $behaviors = $behavior->getClause('behavior')->getIterator();
+ $this->_stack->push(array(
+ 'behavior' => $behavior,
+ 'state' => static::STATE_BEHAVIOR
+ ));
+ $this->_stack->push(array(
+ 'behavior' => $behaviors,
+ 'state' => static::STATE_BEHAVIOR
+ ));
+
+ $this->_pop->push(
+ count($behaviors)
+ + (2 * $behavior->clauseExists('default'))
+ );
+ }
+ else {
+
+ $this->_stack->push(array(
+ 'behavior' => $behavior,
+ 'state' => static::STATE_ENSURES
+ ));
+ $this->_pop->push(2);
+ $this->next();
+ }
+ break;
+
+ case static::STATE_BEHAVIOR:
+ if(true === $behavior->valid()) {
+
+ $this->_stack->push(array(
+ 'behavior' => $behavior,
+ 'state' => static::STATE_BEHAVIOR
+ ));
+ $this->_stack->push(array(
+ 'behavior' => $behavior->current(),
+ 'state' => static::STATE_REQUIRES
+ ));
+ $behavior->next();
+ $this->next();
+
+ break;
+ }
- $this->_stack->pop();
+ list($parentBehavior, ) = array_values($this->_stack->pop());
- if(true === $handle->getParent()->clauseExists('default')) {
+ if(true === $parentBehavior->clauseExists('default'))
+ $this->_stack->push(array(
+ 'behavior' => $parentBehavior->getClause('default'),
+ 'state' => static::STATE_ENSURES
+ ));
- $this->_up = false;
- $this->_stack->push($handle->getParent()->getClause('default'));
+ $this->next();
+ break;
- return $this->next();
- }
+ case static::STATE_ENSURES:
+ $this->_stack->push(array(
+ 'behavior' => $behavior,
+ 'state' => static::STATE_THROWABLE
+ ));
- $this->_up = true;
+ if( false === $behavior->clauseExists('ensures')
+ || 0 === (Coverage::CRITERIA_NORMAL & $this->getCriteria())) {
- return $this->next();
- }
+ $this->_pop->push($this->_pop->pop() - 1);
+ $this->next();
- $this->_up = false;
- $this->pushCurrent($nextHandle);
- ++$this->_key;
+ break;
+ }
- return $this->current();
- }
+ ++$this->_key;
+ $this->_current = $behavior->getClause('ensures');
+ $this->_path->push($this->_current);
+ $this->_pop->push(0);
+ break;
- /**
- * Common (and inline) parts of the $this->next() method.
- *
- * @access private
- * @param \Hoa\Praspel\Model\Behavior $handle Handle.
- * @return array
- */
- private function _next ( \Hoa\Praspel\Model\Behavior $handle ) {
+ case static::STATE_THROWABLE:
+ if( false === $behavior->clauseExists('throwable')
+ || 0 === (Coverage::CRITERIA_EXCEPTIONAL & $this->getCriteria())) {
- $iterator = $handle->getClause('behavior')->getIterator();
- $this->_stack->push($iterator);
- $current = current($iterator);
+ $this->_pop->push($this->_pop->pop() - 1);
+ $this->next();
- if(false === $current) {
+ break;
+ }
- $this->_up = true;
+ ++$this->_key;
+ $this->_current = $behavior->getClause('throwable');
- return $this->next();
+ $this->_path->push($this->_current);
+ $this->_pop->push(0);
+ break;
}
- $this->pushCurrent($current);
- ++$this->_key;
-
- return $this->current();
+ return;
}
/**
@@ -303,70 +352,28 @@ class Structural implements \Hoa\Iterator\Recursive {
*/
public function rewind ( ) {
- $this->_up = false;
- $this->_key = 0;
+ $this->_key = -1;
+
+ unset($this->_path);
+ $this->_path = new \SplQueue();
unset($this->_stack);
$this->_stack = new \SplStack();
- $this->_stack->push($this->_specification);
+ $this->_stack->push(array(
+ 'behavior' => $this->_specification,
+ 'state' => static::STATE_REQUIRES
+ ));
- $this->_post = 0 !== (Coverage::CRITERIA_NORMAL & $this->getCriteria())
- ? 'ensures'
- : 'throwable';
+ unset($this->_pop);
+ $this->_pop = new \SplQueue();
+ $this->_pop->push(-1);
- $this->_rewindCurrent();
+ $this->next();
return $this->current();
}
/**
- * Rewind $this->_current.
- *
- * @access protected
- * @return void
- */
- protected function _rewindCurrent ( ) {
-
- $stack = new \Hoa\Praspel\Iterator\WeakStack();
- $stack->setIteratorMode(
- \SplDoublyLinkedList::IT_MODE_LIFO
- | \SplDoublyLinkedList::IT_MODE_KEEP
- );
- unset($this->_current);
- $this->_current = array(
- 'pre' => $stack,
- 'post' => clone $stack
- );
- $this->pushCurrent($this->_stack->top());
-
- return;
- }
-
- /**
- * Push pre and post clauses in $this->_current.
- *
- * @access protected
- * @param \Hoa\Praspel\Model\Behavior $current Current.
- * @return void
- */
- protected function pushCurrent ( \Hoa\Praspel\Model\Behavior $current ) {
-
- $pre = null;
- $post = null;
-
- if(true === $current->clauseExists('requires'))
- $pre = $current->getClause('requires');
-
- if(true === $current->clauseExists($this->_post))
- $post = $current->getClause($this->_post);
-
- $this->_current['pre']->push($pre);
- $this->_current['post']->push($post);
-
- return;
- }
-
- /**
* Check if there is a current element after calls to the rewind() or the
* next() methods.
*
@@ -388,6 +395,12 @@ class Structural implements \Hoa\Iterator\Recursive {
*/
public function setCriteria ( $criteria ) {
+ if( 0 !== (Coverage::CRITERIA_DOMAIN & $criteria)
+ && 0 !== (Coverage::CRITERIA_EXCEPTIONAL & $criteria))
+ throw new \Hoa\Praspel\Exception\Generic(
+ 'Mixing CRITERIA_EXCEPTIONAL and CRITERIA_DOMAIN is not ' .
+ 'supported yet. Sorry.', 0);
+
$old = $this->_criteria;
$this->_criteria = $criteria;
@@ -426,12 +439,13 @@ class Structural implements \Hoa\Iterator\Recursive {
public function getChildren ( ) {
$variables = array();
+ $current = $this->current();
- foreach($this->_current['pre'] as $clause)
+ foreach($current['pre'] as $clause)
foreach($clause->getLocalVariables() as $variable)
$variables[] = $variable;
- foreach($this->_current['post'] as $clause)
+ foreach($current['post'] as $clause)
foreach($clause->getLocalVariables() as $variable)
$variables[] = $variable;