chore(flags): Add method to build up evaluation levels from a flags DAG #33699
Conversation
There was a problem hiding this comment.
PR Summary
Implements parallel evaluation of feature flags using a dependency-based staging system, moving from sequential topological sorting to a more efficient approach.
- Added
build_from_nodesmethod to construct multi-root DAGs from feature flag collections with strict cycle validation - Implemented
evaluation_stagesto organize flags into parallel evaluation stages (e.g.,[1, 4, 5, 6, 8]->[3, 7]->[2]) - Reuses existing dependency graph infrastructure from cohort system for feature flags
- Comprehensive test coverage for various dependency scenarios including linear chains and complex DAGs
2 files reviewed, no comments
Edit PR Review Bot Settings | Greptile
There was a problem hiding this comment.
Pull Request Overview
This PR adds graph construction and staged evaluation features to support dependent feature flags without changing the parallel evaluation model.
- Introduces
build_from_nodesto create a multi-root DAG from any set of flag nodes. - Adds
evaluation_stagesto batch nodes into dependency-respecting stages for parallel evaluation. - Refactors
newto collect reachable nodes and delegate tobuild_from_nodes.
Reviewed Changes
Copilot reviewed 2 out of 2 changed files in this pull request and generated 2 comments.
| File | Description |
|---|---|
| graph_utils.rs | Implemented build_from_nodes and evaluation_stages, refactored new. |
| test_graph_utils.rs | Added unit tests for build_from_nodes and evaluation_stages. |
Comments suppressed due to low confidence (1)
rust/feature-flags/src/utils/graph_utils.rs:75
- The doc comment above
newstill refers toinitial_itemanditems. Please update it to mentionrootandpool, and note that it delegates tobuild_from_nodesfor consistency.
pub fn new(root: T, pool: &[T]) -> Result<Self, T::Error> {
| if let Some(target_idx) = id_map.get(&dep_id) { | ||
| graph.add_edge(source_idx, *target_idx, ()); |
There was a problem hiding this comment.
build_from_nodes silently drops dependencies that aren’t in the provided node list. It s
10000
hould return an error when dep_id is not found rather than ignoring it, to avoid hidden missing-dependency bugs.
| if let Some(target_idx) = id_map.get(&dep_id) { | |
| graph.add_edge(source_idx, *target_idx, ()); | |
| match id_map.get(&dep_id) { | |
| Some(target_idx) => { | |
| graph.add_edge(source_idx, *target_idx, ()); | |
| } | |
| None => { | |
| return Err(FlagError::MissingDependency( | |
| T::dependency_type(), | |
| dep_id.into(), | |
| ) | |
| .into()); | |
| } |
Copilot uses AI. Check for mistakes.
| Ok(node) | ||
| if current_stage.is_empty() { | ||
| // This should never happen if the graph is acyclic (already validated during build) | ||
| return Err(FlagError::DependencyCycle(T::dependency_type(), 0).into()); |
There was a problem hiding this comment.
Using the literal 0 as the cycle-start ID is a magic number and may not correspond to a real node. Consider propagating the actual node ID or using a more descriptive error variant.
| return Err(FlagError::DependencyCycle(T::dependency_type(), 0).into()); | |
| if let Some((&node_idx, _)) = out_degree.iter().next() { | |
| let node_id = self.get_node_id(node_idx); | |
| return Err(FlagError::DependencyCycle(T::dependency_type(), node_id).into()); | |
| } | |
| // Fallback in case no node is found (should not occur) | |
| return Err(FlagError::DependencyCycle(T::dependency_type(), -1).into()); |
Copilot uses AI. Check for mistakes.
| pub fn new(initial_item: T, items: &[T]) -> Result<Self, T::Error> { | ||
| let mut graph = DiGraph::new(); | ||
| let mut node_map = NodeMap::<T>::new(); | ||
| pub fn new(root: T, pool: &[T]) -> Result<Self, T::Error> { |
There was a problem hiding this comment.
Because we have build_from_nodes we can make this method simpler by building on that.
Perhaps we should rename this method though?
1eb0013 to
778649a
Compare
Note that this PR targets the PR #33643.
Problem
In preparation for the upcoming feature where feature flags can depend on other feature flags, we need to consider feature flag dependencies. Typically, this would require that we sort flags topologically, reverse them, and then evaluate them sequentially.
However, our current code evaluates flags in parallel, and we'd like to keep doing that. So what we need to do is build up a multi-root DAG (Directed Acyclic Graph) and evaluate flag dependencies in stages. This PR implements the ability to build those stages (it doesn't do the evaluation in stages yet).
Related to #29016
Changes
This adds a two new methods:
build_from_nodeswhich takes in a collection of nodes and builds up a multi-root graph with all the nodes.The second new method is
evaluation_stages. This returns flags in stages where each stage must be evaluated before the next stage can be evaluated. Here's an example:Suppose we have these flags (represented by IDs) and their dependencies (represented by arrows):
In other words:
1, 5, 6 - are independent flags (no dependencies, nobody depends on them)
2 depends on 3
3 depends on 4
When we evaluate these flags, we have to do them in the following stages:
[1, 4, 5, 6, 8](leaf nodes and indpendent flags)[3, 7](flags with one dependency)[2](flags with two dependencies)This allows us to evaluate the flags in each stage in parallel while making sure we always evaluate dependencies before parents.
Did you write or update any docs for this change?
How did you test this code?
Unit tests