spice/parser/
shorts.rs

1//! Short propagation analysis.
2
3use crate::parser::conv::{SubcktName, map_subckts};
4use crate::parser::{Ast, Component, Node, Subckt};
5use std::collections::{HashMap, HashSet};
6
7#[derive(Copy, Clone, Debug, Default, Eq, PartialEq, Hash, Ord, PartialOrd)]
8struct NodeKey(u32);
9
10type NodeUf = ena::unify::InPlaceUnificationTable<NodeKey>;
11
12#[derive(Copy, Clone, Debug, Default, Eq, PartialEq, Hash, Ord, PartialOrd)]
13enum NodePriority {
14    Io = 2,
15    #[default]
16    Default = 1,
17}
18
19/// The value associated to a node in a schematic builder's union find data structure.
20#[derive(Clone, Debug, Eq, PartialEq, Hash, Ord, PartialOrd)]
21#[doc(hidden)]
22struct NodeUfValue {
23    /// The overall priority of a set of merged nodes.
24    ///
25    /// Taken to be the highest among priorities of all nodes
26    /// in the merged set.
27    priority: NodePriority,
28
29    /// The node that provides `priority`.
30    ///
31    /// For example, if priority is NodePriority::Io, `node`
32    /// should be the node identifier representing the IO node.
33    pub(crate) source: Node,
34}
35
36impl ena::unify::UnifyKey for NodeKey {
37    type Value = NodeUfValue;
38    fn index(&self) -> u32 {
39        self.0
40    }
41
42    fn from_index(u: u32) -> Self {
43        Self(u)
44    }
45
46    fn tag() -> &'static str {
47        "NodeKey"
48    }
49}
50
51impl ena::unify::UnifyValue for NodeUfValue {
52    type Error = ena::unify::NoError;
53
54    fn unify_values(value1: &Self, value2: &Self) -> std::result::Result<Self, Self::Error> {
55        Ok(std::cmp::max(value1.clone(), value2.clone()))
56    }
57}
58
59/// Analyzes shorts in a SPICE netlist.
60#[derive(Clone)]
61pub struct ShortPropagator {
62    cells: HashMap<SubcktName, CellShortManager>,
63}
64
65/// Stores information about shorts within a cell.
66#[derive(Clone)]
67pub struct CellShortManager {
68    node_to_key: HashMap<Node, NodeKey>,
69    uf: NodeUf,
70}
71
72impl ShortPropagator {
73    /// Construct a [`ShortPropagator`] from the given SPICE AST.
74    pub fn analyze(ast: &Ast, blackbox: &HashSet<SubcktName>) -> Self {
75        let mut val = Self::new();
76        let subckts = map_subckts(ast);
77        let order = dfs_postorder(&subckts, blackbox);
78
79        for name in order.iter() {
80            let subckt = subckts[name];
81            let mut manager = CellShortManager::new();
82            for p in subckt.ports.iter() {
83                manager.register_node(p.clone(), NodePriority::Io);
84            }
85
86            for c in subckt.components.iter() {
87                match c {
88                    Component::Mos(m) => {
89                        for node in [&m.d, &m.g, &m.s, &m.b] {
90                            manager.register_node(node.clone(), NodePriority::Default);
91                        }
92                    }
93                    Component::Res(r) => {
94                        for node in [&r.pos, &r.neg] {
95                            manager.register_node(node.clone(), NodePriority::Default);
96                        }
97                    }
98                    Component::Diode(d) => {
99                        for node in [&d.pos, &d.neg] {
100                            manager.register_node(node.clone(), NodePriority::Default);
101                        }
102                    }
103                    Component::Bjt(bjt) => {
104                        for node in [&bjt.collector, &bjt.base, &bjt.emitter] {
105                            manager.register_node(node.clone(), NodePriority::Default);
106                        }
107                        if let Some(node) = &bjt.substrate {
108                            manager.register_node(node.clone(), NodePriority::Default);
109                        }
110                    }
111                    Component::Cap(c) => {
112                        for node in [&c.pos, &c.neg] {
113                            manager.register_node(node.clone(), NodePriority::Default);
114                        }
115                    }
116                    Component::Instance(inst) => {
117                        for node in inst.ports.iter() {
118                            manager.register_node(node.clone(), NodePriority::Default);
119                        }
120                        // We do not support propagation of shorts in blackbox/missing subcircuits.
121                        if !blackbox.contains(&inst.child) {
122                            let child_subckt = match subckts.get(&inst.child) {
123                                None => continue,
124                                Some(&s) => s,
125                            };
126                            let mut port_to_connected_node = HashMap::new();
127                            assert_eq!(inst.ports.len(), child_subckt.ports.len());
128                            for (node, cport) in inst.ports.iter().zip(child_subckt.ports.iter()) {
129                                port_to_connected_node.insert(cport, node);
130                            }
131                            let child_shorts = val.get_or_add_cell(inst.child.clone());
132                            for (node, cport) in inst.ports.iter().zip(child_subckt.ports.iter()) {
133                                let croot = child_shorts.root(cport);
134                                manager.connect(node, port_to_connected_node[&croot]);
135                            }
136                        }
137                    }
138                }
139            }
140
141            for (n1, n2) in subckt.connects.iter() {
142                manager.connect(n1, n2);
143            }
144
145            val.set_cell(name.clone(), manager);
146        }
147
148        val
149    }
150
151    fn new() -> Self {
152        Self {
153            cells: Default::default(),
154        }
155    }
156
157    fn get_or_add_cell(&mut self, name: SubcktName) -> &mut CellShortManager {
158        self.cells.entry(name).or_insert(CellShortManager::new())
159    }
160
161    /// Get the set of shorts within a cell.
162    pub fn get_cell(&mut self, name: &SubcktName) -> &mut CellShortManager {
163        self.cells.get_mut(name).unwrap()
164    }
165
166    fn set_cell(&mut self, name: SubcktName, manager: CellShortManager) {
167        self.cells.insert(name, manager);
168    }
169}
170
171impl CellShortManager {
172    fn new() -> Self {
173        Self {
174            node_to_key: HashMap::new(),
175            uf: NodeUf::new(),
176        }
177    }
178
179    /// Adds a node with the given priority.
180    /// Does nothing if the node has already been registered.
181    ///
182    /// Consequently, IO nodes must be registered first.
183    fn register_node(&mut self, node: Node, priority: NodePriority) {
184        if self.node_to_key.contains_key(&node) {
185            return;
186        }
187        let key = self.uf.new_key(NodeUfValue {
188            priority,
189            source: node.clone(),
190        });
191        self.node_to_key.insert(node, key);
192    }
193
194    fn connect(&mut self, node1: &Node, node2: &Node) {
195        let Some(k1) = self.node_to_key.get(node1) else {
196            return;
197        };
198        let Some(k2) = self.node_to_key.get(node2) else {
199            return;
200        };
201        self.uf.union(*k1, *k2);
202    }
203
204    /// The node to which the given node is shorted.
205    pub fn root(&mut self, node: &Node) -> Node {
206        let k = self.node_to_key[node];
207        let v = self.uf.probe_value(k);
208        v.source
209    }
210}
211
212fn dfs_postorder(
213    subckts: &HashMap<SubcktName, &Subckt>,
214    blackbox: &HashSet<SubcktName>,
215) -> Vec<SubcktName> {
216    let mut visited = HashSet::new();
217    let mut order = Vec::new();
218
219    for name in subckts.keys() {
220        dfs_postorder_inner(name, subckts, blackbox, &mut visited, &mut order);
221    }
222
223    order
224}
225
226fn dfs_postorder_inner(
227    name: &SubcktName,
228    subckts: &HashMap<SubcktName, &Subckt>,
229    blackbox: &HashSet<SubcktName>,
230    visited: &mut HashSet<SubcktName>,
231    out: &mut Vec<SubcktName>,
232) {
233    if visited.contains(name) || blackbox.contains(name) {
234        return;
235    }
236
237    let subckt = match subckts.get(name) {
238        None => {
239            return;
240        }
241        Some(&s) => s,
242    };
243    for c in subckt.components.iter() {
244        if let Component::Instance(inst) = c {
245            dfs_postorder_inner(&inst.child, subckts, blackbox, visited, out);
246        }
247    }
248
249    out.push(name.clone());
250    visited.insert(name.clone());
251}
spice/parser/shorts.rs

spice/parser/
shorts.rs
