Check if adding a dependency from target to source would create a cycle. Uses DFS with visited set for efficient cycle detection. Args: features: List of all feature dicts source_id: The feature that would gain the dependency target_id: The feature that would become
(
features: list[dict], source_id: int, target_id: int
)
| 143 | |
| 144 | |
| 145 | def would_create_circular_dependency( |
| 146 | features: list[dict], source_id: int, target_id: int |
| 147 | ) -> bool: |
| 148 | """Check if adding a dependency from target to source would create a cycle. |
| 149 | |
| 150 | Uses DFS with visited set for efficient cycle detection. |
| 151 | |
| 152 | Args: |
| 153 | features: List of all feature dicts |
| 154 | source_id: The feature that would gain the dependency |
| 155 | target_id: The feature that would become a dependency |
| 156 | |
| 157 | Returns: |
| 158 | True if adding the dependency would create a cycle |
| 159 | """ |
| 160 | if source_id == target_id: |
| 161 | return True # Self-reference is a cycle |
| 162 | |
| 163 | feature_map = {f["id"]: f for f in features} |
| 164 | source = feature_map.get(source_id) |
| 165 | if not source: |
| 166 | return False |
| 167 | |
| 168 | # Check if target already depends on source (direct or indirect) |
| 169 | target = feature_map.get(target_id) |
| 170 | if not target: |
| 171 | return False |
| 172 | |
| 173 | # DFS from target to see if we can reach source |
| 174 | visited: set[int] = set() |
| 175 | |
| 176 | def can_reach(current_id: int, depth: int = 0) -> bool: |
| 177 | # Security: Prevent stack overflow with depth limit |
| 178 | if depth > MAX_DEPENDENCY_DEPTH: |
| 179 | return True # Assume cycle if too deep (fail-safe) |
| 180 | if current_id == source_id: |
| 181 | return True |
| 182 | if current_id in visited: |
| 183 | return False |
| 184 | visited.add(current_id) |
| 185 | |
| 186 | current = feature_map.get(current_id) |
| 187 | if not current: |
| 188 | return False |
| 189 | |
| 190 | deps = current.get("dependencies") or [] |
| 191 | for dep_id in deps: |
| 192 | if can_reach(dep_id, depth + 1): |
| 193 | return True |
| 194 | return False |
| 195 | |
| 196 | return can_reach(target_id) |
| 197 | |
| 198 | |
| 199 | def validate_dependencies( |