fn affected_closure()

in tools/determinator/src/determinator.rs [621:719]
72 lines of code
6 McCabe index (conditional complexity)

    fn affected_closure(
        &self,
        package_graph: &'g PackageGraph,
        path_changed: &HashSet<&'g PackageId>,
        summary_changed: &HashSet<&'g PackageId>,
    ) -> PackageSet<'g> {
        // This is a *really* interesting DFS, in that there's one restriction: you can't follow
        // two CargoBuild edges consecutively. Also, in the initial set, path_changed allows
        // CargoBuild to be followed once while summary_changed doesn't allow it to be followed.

        #[derive(Copy, Clone, Debug, Eq, PartialEq)]
        enum FollowCargoBuild {
            Allowed,
            NotAllowed,
        }

        use FollowCargoBuild::*;

        // The order of what goes in the stack doesn't matter for correctness, but putting Allowed
        // at the end (and therefore popping it first) lowers the chance of an upgrade re-traversal.
        let mut stack: Vec<_> = summary_changed
            .iter()
            .map(|id| (*id, NotAllowed))
            .chain(path_changed.iter().map(|id| (*id, Allowed)))
            .collect();

        // Do a DFS with two maps, in case there are cycles (can happen with dev deps).
        let mut discovered = HashMap::new();
        let mut finished = HashSet::new();

        while let Some(&(id, follow)) = stack.last() {
            let push_neighbors = match discovered.entry(id) {
                Entry::Vacant(entry) => {
                    // First time visiting this node. Push neighbors, don't pop the stack.
                    entry.insert(follow);
                    true
                }
                Entry::Occupied(mut entry) => {
                    // This node was seen before.
                    match (entry.get(), follow) {
                        (NotAllowed, Allowed) => {
                            // Upgrade this node to Allowed and push neighbors.
                            entry.insert(follow);
                            true
                        }
                        _ => {
                            // Already been fully discovered or just NotAllowed -> NotAllowed, no
                            // point revisiting it.
                            false
                        }
                    }
                }
            };

            if push_neighbors {
                for (_, neighbor, &edge) in self.reverse_index.edges(Some(id)) {
                    if edge == ReverseIndexEdge::CargoBuild && follow == NotAllowed {
                        // Can't follow two consecutive CargoBuild edges.
                        continue;
                    }
                    match neighbor {
                        Some(neighbor) => {
                            let neighbor_follow = match edge {
                                ReverseIndexEdge::CargoBuild => NotAllowed,
                                ReverseIndexEdge::PackageRule => Allowed,
                            };

                            match (discovered.get(&neighbor), neighbor_follow) {
                                (None, _) => {
                                    // Node has not been discovered yet. Add it to the stack to
                                    // be visited.
                                    stack.push((neighbor, neighbor_follow))
                                }
                                (Some(NotAllowed), Allowed) => {
                                    // Node was previously discovered with NotAllowed but is
                                    // now discovered with Allowed. This is an upgrade. Add it to
                                    // the stack to be visited.
                                    stack.push((neighbor, neighbor_follow))
                                }
                                _ => {}
                            }
                        }
                        None => {
                            // Build everything, can just exit here.
                            return package_graph.resolve_workspace();
                        }
                    }
                }
            } else {
                stack.pop();
                finished.insert(id);
            }
        }

        // At the end of this process, finished contains all nodes discovered.
        package_graph
            .resolve_ids(finished.iter().copied())
            .expect("all IDs are valid")
    }