libreda_db/hierarchy/
util.rs

1// Copyright (c) 2020-2021 Thomas Kramer.
2// SPDX-FileCopyrightText: 2022 Thomas Kramer
3//
4// SPDX-License-Identifier: AGPL-3.0-or-later
5
6//! Utility functions for dealing with the hierarchy of netlists or layouts.
7
8use super::traits::{HierarchyBase, HierarchyEdit};
9use fnv::FnvHashSet;
10
11/// Non-modifying utility functions for the cell hierarchy..
12/// Import the this trait to use the utility functions all types that implement the `HierarchyBase` trait.
13pub trait HierarchyUtil: HierarchyBase {
14    /// Check if the cell is a top level cell.
15    /// This is done by checking that no other cells have an instance of this cell.
16    fn is_top_level_cell(&self, cell: &Self::CellId) -> bool {
17        self.num_dependent_cells(cell) == 0
18    }
19
20    /// Check if the cell is a leaf cell.
21    /// This is done by checking that this cell contains no other cell instances.
22    fn is_leaf_cell(&self, cell: &Self::CellId) -> bool {
23        self.num_cell_dependencies(cell) == 0
24    }
25
26    /// Iterate over all top level cells.
27    fn each_top_level_cell(&self) -> Box<dyn Iterator<Item = Self::CellId> + '_> {
28        Box::new(self.each_cell().filter(move |c| self.is_top_level_cell(c)))
29    }
30
31    /// Iterate over all leaf cells, i.e. cells which contain no other cells.
32    fn each_leaf_cell(&self) -> Box<dyn Iterator<Item = Self::CellId> + '_> {
33        Box::new(self.each_cell().filter(move |c| self.is_leaf_cell(c)))
34    }
35
36    /// Iterate over topologically sorted cells (from leaf-cells to top-cells).
37    fn each_cell_bottom_to_top(&self) -> Box<dyn Iterator<Item = Self::CellId> + '_> {
38        let mut unsorted_cells: Vec<_> = self.each_cell_vec();
39        let mut visited_cells: FnvHashSet<_> = Default::default();
40        let mut sorted_cells = vec![];
41
42        unsorted_cells.retain(|cell| {
43            let all_dependencies_resolved = self
44                .each_cell_dependency(cell)
45                .all(|dependency| visited_cells.contains(&dependency));
46            if all_dependencies_resolved {
47                sorted_cells.push(cell.clone());
48                visited_cells.insert(cell.clone());
49                false
50            } else {
51                true
52            }
53        });
54
55        debug_assert!({
56            let mut is_topo_sorted = true;
57            for (i, cell) in sorted_cells.iter().enumerate() {
58                is_topo_sorted &= self
59                    .each_cell_dependency(cell)
60                    .all(|dependency| sorted_cells[0..i].contains(&dependency))
61            }
62            is_topo_sorted
63        });
64
65        Box::new(sorted_cells.into_iter())
66    }
67}
68
69impl<N: HierarchyBase> HierarchyUtil for N {}
70
71/// Modifying utility functions for the cell hierarchy..
72/// Import the this trait to use the utility functions all types that implement the `HierarchyEdit` trait.
73pub trait HierarchyEditUtil: HierarchyEdit {
74    /// Remove all child instances inside the `cell`.
75    fn clear_cell_instances(&mut self, cell: &Self::CellId) {
76        let child_instances = self.each_cell_instance_vec(cell);
77        for child in &child_instances {
78            self.remove_cell_instance(child);
79        }
80    }
81
82    /// Remove the cell instance and all cells which are then not used anymore.
83    fn prune_cell_instance(&mut self, inst: &Self::CellInstId) {
84        let template = self.template_cell(inst);
85        self.remove_cell_instance(inst);
86        if self.num_cell_references(&template) == 0 {
87            // The cell is now not used anymore.
88            self.remove_cell(&template)
89        }
90    }
91
92    /// Remove the cell and all other cells which are then not used anymore.
93    fn prune_cell(&mut self, cell: &Self::CellId) {
94        let child_instances = self.each_cell_instance_vec(cell);
95        for child in &child_instances {
96            self.prune_cell_instance(child);
97        }
98        self.remove_cell(cell)
99    }
100}
101
102impl<N: HierarchyEdit> HierarchyEditUtil for N {}
libreda_db/hierarchy/util.rs

libreda_db/hierarchy/
util.rs
