This follows up my previous RFC, and now contains pretty much all the changes
I think are critical before this is ready to go:
This replaces the old dependency cycle reporting in puppet with a new, fancier
version. It automatically finds all the cycles, always delivers the minimum
set of dependencies in them, processes them, and reports them in a useful and
independent fashion.
We report up to ten dependency paths through each cycle, always generating the
shortest paths. This should allow easy targeting of the cycle without
overwhelming y'all with information, and without too much performance cost.
Performance mostly approximates O(1), even though this shouldn't be
performance critical, and it is limited to chains smaller than available heap
memory; practically, this is effectively unlimited depth cycles.
All the promises (minimum vertex set, shortest path, performance, etc) are
guaranteed algorithmically rather than probabilistically, so we should always
see good results from this.
The overall change adds a bunch of code to the graph object, and a bunch of
testing to ensure that we deliver what we promised:
lib/puppet/simple_graph.rb | 163 +++++++++++++++++++++++++++++++++-------
spec/unit/simple_graph_spec.rb | 101 +++++++++++++++++++++++++
2 files changed, 236 insertions(+), 28 deletions(-)
This is mostly ready to merge, but I need more feedback. An actual code
review, and someone double-checking that I delivered the O(1) performance
would be good. Any takers?
Regards,
Daniel
--
You received this message because you are subscribed to the Google Groups
"Puppet Developers" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/puppet-dev?hl=en.
