zf-fr/rbac — pull request #5 by danizord (2014-01-06 17:18:08+00:00)
Title: Traversal strategies

Finally! Sorry for the delay :D

# Traversal strategies
The [Graph traversal](http://en.wikipedia.org/wiki/Graph_traversal) is a very complex problem, there are several ways to do this, but none of them is the best way for all cases. There are many cases that need a specific algorithm. For instance, If you have a very dense role graph, you'll probably want to avoid redundancy when traversing the graph (checking the same role more than once). But if you have a flatter role graph, then you will not care about the redundancy, because the logic to avoid redundancy would be more costly than the redundancy itself.

So, if we make this algorithm pluggable, the RBAC component will become much more flexible, allowing the developers to easily implement their own strategies for specific cases.

I have many ideas for other strategies to implement (e.g a non-redundant generator strategy), but for now I'll suggest two:
### Built-in traversal strategies:
* **RecursiveRoleIteratorStrategy** - The default strategy, it recursively traverses the roles using a SPL `RecursiveIteratorIterator` that iterate over instances of `Rbac\Traversal\RecursiveRoleIterator`.

* **GeneratorStrategy** - This strategy requires PHP >= 5.5, the fastest and lightweight strategy! It takes advantage of the new PHP 5.5 generators to recursively traverse the role graph.

### Benchmarks
I did some performance tests of the built-in strategies to know which one is faster. You can run the benchmarks yourself, just follow the instructions in the [danizord/rbac-benchmarks](https://github.com/danizord/rbac-benchmarks) repository. See the results on my PC:
```
daniel@Danibook:~/projects/rbac-benchmarks$ php vendor/bin/athletic -p src/ -b vendor/autoload.php

Danizord\RbacBenchmarks\Traversal\GeneratorStrategyEvent
Method Name Iterations Average Time Ops/second
--------------------------- ------------ -------------- -------------
flatFirstMatch : [1,000 ] [0.0000078084469] [128,066.44072]
flatLastMatch : [1,000 ] [0.0000445151329] [22,464.27079]
hierarchicalFirstDepthMatch: [1,000 ] [0.0000128533840] [77,800.52308]
hierarchicalLastDepthMatch : [1,000 ] [0.0000390281677] [25,622.51979]

Danizord\RbacBenchmarks\Traversal\RecursiveIteratorStrategyEvent
Method Name Iterations Average Time Ops/second
--------------------------- ------------ -------------- -------------
flatFirstMatch : [1,000 ] [0.0000188462734] [53,060.88783]
flatLastMatch : [1,000 ] [0.0000955798626] [10,462.45488]
hierarchicalFirstDepthMatch: [1,000 ] [0.0000269591808] [37,093.11519]
hierarchicalLastDepthMatch : [1,000 ] [0.0000535430908] [18,676.54602]
```

## Additional changes
* `HierarchicalRoleInterface` no longer extends `RecursiveIterator`, this means that the roles are not aware of traversal nor recursion anymore.
* The recursive iteration that was previously in `HierarchicalRole`, now is done in the new `RecursiveRoleIterator`.
* `Rbac::isGranted()` now now accepts a collection/array of `RoleInterface`s, but still accepting a single `RoleInterface` instance. If one of the given roles has the required permission, then it returns `true`.
* Some tests was updated, the code coverage of this component is now 100%. :smiley:

## Known issues/limitations
* Since `RecursiveRoleIterator` extends `ArrayIterator`, it works only with arrays. This means that `RecursiveRoleIteratorStrategy` will not work with Doctrine collections. So, a custom implementation of `TraversalStrategyInterface` will be necessary to work on top of Doctrine collections. (ZfcRbac should provide it).

## Questions
* Should `HierarchicalRoleInterface` specify a `hasChildren()` method (to avoid [this](https://github.com/danizord/rbac/blob/5989bd78408b9026392eb3c9081aeb12692d4a93/src/Rbac/Traversal/RecursiveRoleIterator.php#L38-40) check)?
* Btw, do you think the [above check](https://github.com/danizord/rbac/blob/5989bd78408b9026392eb3c9081aeb12692d4a93/src/Rbac/Traversal/RecursiveRoleIterator.php#L38-40) is really necessary?
* When `Rbac::isGranted()` receives a single instance of `RoleInterface` as first argument, should it check the given role alone without trigger traversal? See an example [here](https://gist.github.com/danizord/61f941b4f15376a5efc8).
* The way I'm injecting the traversal strategy in `Rbac` seems good? Or should I inject it via setter and lazy-load the default strategy via getter?