| // Copyright 2021 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| use std::collections::{HashSet, VecDeque}; |
| |
| use crate::{core::Object, Component}; |
| |
| #[derive(Debug, Default)] |
| pub struct DependencySorter { |
| perm: HashSet<Object<Component>>, |
| temp: HashSet<Object<Component>>, |
| } |
| |
| impl DependencySorter { |
| pub fn sort(&mut self, root: Object<Component>, order: &mut VecDeque<Object<Component>>) { |
| order.clear(); |
| self.visit(root, order); |
| } |
| |
| fn visit(&mut self, component: Object<Component>, order: &mut VecDeque<Object<Component>>) { |
| if self.perm.contains(&component) { |
| return; |
| } |
| |
| if self.temp.contains(&component) { |
| panic!("dependency cycle"); |
| } |
| |
| self.temp.insert(component.clone()); |
| |
| for dependent in component.as_ref().depdenents() { |
| self.visit(dependent, order); |
| } |
| |
| self.perm.insert(component.clone()); |
| order.push_front(component); |
| } |
| } |