diff options
author | Ivan Enderlin <ivan.enderlin@hoa-project.net> | 2014-03-31 22:57:29 +0200 |
---|---|---|
committer | Ivan Enderlin <ivan.enderlin@hoa-project.net> | 2014-04-01 14:31:12 +0200 |
commit | 78d81ac4a1077cfc455ccacff1c5e9b9aa345459 (patch) | |
tree | 6877d305f69f746b9f0d8c81498fd5cb680681b0 | |
parent | 080f7b8777d237aeadae68b8e716c7b8ccd7bc0a (diff) | |
download | Praspel-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).
-rw-r--r-- | Iterator/Coverage/Structural.php | 334 |
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; |