rive_rs/
dependency_sorter.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 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;
use crate::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);
    }
}