Dependency Resolution
ROC's dependency resolution system builds a comprehensive dependency graph from discovered packages and determines the optimal build order. This chapter explains the algorithms and strategies used for dependency management.
Dependency Graph Construction
Graph Representation
The dependency system uses a directed graph where:
- Nodes: Represent packages in the workspace
- Edges: Represent dependencies (A → B means A depends on B)
- Direction: Dependencies point from dependent to dependency
#![allow(unused)] fn main() { pub fn topological_sort(packages: &[PackageMeta]) -> Result<Vec<usize>, Box<dyn std::error::Error>> { let mut name_to_index: HashMap<String, usize> = HashMap::new(); let mut graph: Vec<Vec<usize>> = vec![Vec::new(); packages.len()]; let mut in_degree: Vec<usize> = vec![0; packages.len()]; // Build name to index mapping for (idx, package) in packages.iter().enumerate() { name_to_index.insert(package.name.clone(), idx); } // Build dependency graph for (pkg_idx, package) in packages.iter().enumerate() { for dep_name in &package.build_deps { if let Some(&dep_idx) = name_to_index.get(dep_name) { graph[dep_idx].push(pkg_idx); in_degree[pkg_idx] += 1; } // External dependencies are ignored (assumed available) } } } }
Dependency Types
The system considers multiple types of dependencies when building the graph:
Build Dependencies (build_depend
)
- Required for compilation/building
- Must be built before dependent package
- Include headers, libraries, and build tools
Build Tool Dependencies (buildtool_depend
)
- Build system tools (cmake, ament_cmake, etc.)
- Usually external to workspace
- Considered for ordering if present in workspace
Runtime Dependencies (exec_depend
)
- Required at runtime
- Not directly used for build ordering
- Important for environment setup
External Dependencies
Dependencies not found in the workspace are treated as external:
- Assumed to be available in the environment
- Not included in build ordering
- May trigger warnings if expected but missing
Topological Sorting Algorithm
Kahn's Algorithm Implementation
ROC uses Kahn's algorithm for topological sorting, which is efficient and provides clear cycle detection:
#![allow(unused)] fn main() { // Kahn's algorithm for topological sorting let mut queue: VecDeque<usize> = VecDeque::new(); let mut result: Vec<usize> = Vec::new(); // Add all nodes with no incoming edges for (idx, °ree) in in_degree.iter().enumerate() { if degree == 0 { queue.push_back(idx); } } while let Some(current) = queue.pop_front() { result.push(current); // Remove this node and update in-degrees for &neighbor in &graph[current] { in_degree[neighbor] -= 1; if in_degree[neighbor] == 0 { queue.push_back(neighbor); } } } }
Algorithm Benefits
Kahn's algorithm provides several advantages:
- Cycle Detection: Incomplete result indicates circular dependencies
- Efficiency: O(V + E) time complexity
- Stability: Consistent ordering for the same input
- Parallelization: Can identify independent packages for parallel builds
Cycle Detection and Resolution
Circular Dependency Detection
Circular dependencies are detected when the topological sort fails to include all packages:
#![allow(unused)] fn main() { // Check for cycles if result.len() != packages.len() { // Find the cycle let remaining: Vec<String> = packages .iter() .enumerate() .filter(|(idx, _)| !result.contains(idx)) .map(|(_, pkg)| pkg.name.clone()) .collect(); return Err(format!("Circular dependency detected among packages: {:?}", remaining).into()); } }
Common Cycle Scenarios
Typical circular dependency patterns:
- Direct Cycles: A depends on B, B depends on A
- Indirect Cycles: A → B → C → A
- Build Tool Cycles: Package depends on build tool that depends on package
Resolution Strategies
When cycles are detected, users can:
- Review Dependencies: Examine package.xml files for unnecessary dependencies
- Split Packages: Break large packages into smaller, independent pieces
- Use Interface Packages: Create interface-only packages to break cycles
- Dependency Inversion: Restructure dependencies using abstract interfaces
Package Filtering
Build Selection Filters
The dependency resolver supports various package selection strategies:
Selective Building (--packages-select
)
Build only specified packages plus their dependencies:
#![allow(unused)] fn main() { if let Some(ref selected) = self.config.packages_select { self.packages.retain(|pkg| selected.contains(&pkg.name)); } }
Package Exclusion (--packages-ignore
)
Exclude specific packages from builds:
#![allow(unused)] fn main() { if let Some(ref ignored) = self.config.packages_ignore { self.packages.retain(|pkg| !ignored.contains(&pkg.name)); } }
Build Up To (--packages-up-to
)
Build dependencies up to specified packages:
#![allow(unused)] fn main() { if let Some(ref up_to) = self.config.packages_up_to { let mut packages_to_build = std::collections::HashSet::new(); // Add target packages for target in up_to { if let Some(pkg) = self.packages.iter().find(|p| &p.name == target) { packages_to_build.insert(pkg.name.clone()); // Add all dependencies recursively self.add_dependencies_recursive(&pkg.name, &mut packages_to_build); } } self.packages.retain(|pkg| packages_to_build.contains(&pkg.name)); } }
Recursive Dependency Collection
For --packages-up-to
, dependencies are collected recursively:
#![allow(unused)] fn main() { fn add_dependencies_recursive(&self, pkg_name: &str, packages_to_build: &mut std::collections::HashSet<String>) { if let Some(pkg) = self.packages.iter().find(|p| &p.name == pkg_name) { for dep in &pkg.build_deps { if !packages_to_build.contains(dep) { if self.packages.iter().any(|p| &p.name == dep) { packages_to_build.insert(dep.clone()); self.add_dependencies_recursive(dep, packages_to_build); } } } } } }
Parallel Build Optimization
Independent Package Identification
The topological sort naturally identifies packages that can be built in parallel:
- Packages with no dependencies can start immediately
- Packages with the same dependency level can build concurrently
- Only direct dependencies need to complete before a package starts
Dependency Satisfaction Checking
During parallel builds, each worker verifies dependencies before starting:
#![allow(unused)] fn main() { let all_deps_ready = deps.iter().all(|dep| { states.get(dep).map(|s| *s == PackageState::Completed).unwrap_or(true) }); if all_deps_ready { states.insert(pkg_name.clone(), PackageState::Building); ready_package = Some(pkg_name); break; } }
Load Balancing
The work-stealing approach ensures optimal resource utilization:
- Dynamic Work Assignment: Workers pick up available packages as dependencies complete
- No Static Partitioning: Avoids idle workers when some builds take longer
- Dependency-Aware: Respects build order constraints while maximizing parallelism
Advanced Dependency Scenarios
Cross-Package Dependencies
Handling complex dependency relationships:
Message/Service Dependencies
<build_depend>my_interfaces</build_depend>
<exec_depend>my_interfaces</exec_depend>
Metapackage Dependencies
<buildtool_depend>ament_cmake</buildtool_depend>
<exec_depend>package1</exec_depend>
<exec_depend>package2</exec_depend>
Conditional Dependencies (Format 3)
<depend condition="$ROS_VERSION == 2">ros2_specific_pkg</depend>
Build Tool Resolution
Special handling for build tools:
- External Build Tools: ament_cmake, cmake, python3-setuptools
- Workspace Build Tools: Custom ament extensions built from source
- Version Constraints: Ensuring compatible tool versions
Error Handling and Diagnostics
Dependency Validation
The system performs comprehensive validation:
#![allow(unused)] fn main() { // Check for missing dependencies for package in &packages { for dep in &package.build_deps { if !name_to_index.contains_key(dep) && !is_external_dependency(dep) { warnings.push(format!("Package {} depends on missing package {}", package.name, dep)); } } } }
Diagnostic Output
Detailed information for troubleshooting:
- Build Order Visualization: Show the determined build sequence
- Dependency Tree: Display complete dependency relationships
- Cycle Analysis: Identify specific packages involved in cycles
- Missing Dependencies: List external dependencies that may be missing
Recovery Strategies
When dependency issues are encountered:
- Graceful Degradation: Continue with buildable packages
- Partial Builds: Build independent subgraphs
- Dependency Suggestions: Recommend missing packages to install
- Alternative Orderings: Provide multiple valid build orders when possible
The dependency resolution system provides a robust foundation for workspace builds, ensuring correct build order while maximizing parallel execution opportunities and providing clear diagnostics for troubleshooting dependency issues.