rive_rs/
dependency_sorter.rs

1// Copyright 2021 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use std::collections::{HashSet, VecDeque};
6
7use crate::core::Object;
8use crate::Component;
9
10#[derive(Debug, Default)]
11pub struct DependencySorter {
12    perm: HashSet<Object<Component>>,
13    temp: HashSet<Object<Component>>,
14}
15
16impl DependencySorter {
17    pub fn sort(&mut self, root: Object<Component>, order: &mut VecDeque<Object<Component>>) {
18        order.clear();
19        self.visit(root, order);
20    }
21
22    fn visit(&mut self, component: Object<Component>, order: &mut VecDeque<Object<Component>>) {
23        if self.perm.contains(&component) {
24            return;
25        }
26
27        if self.temp.contains(&component) {
28            panic!("dependency cycle");
29        }
30
31        self.temp.insert(component.clone());
32
33        for dependent in component.as_ref().depdenents() {
34            self.visit(dependent, order);
35        }
36
37        self.perm.insert(component.clone());
38        order.push_front(component);
39    }
40}