substrate/types/
schematic.rs

1//! Traits and types for schematic IOs.
2
3use crate::block::Block;
4use crate::diagnostics::SourceInfo;
5use crate::schematic::{CellId, HasNestedView, InstanceId, InstancePath, NestedView};
6use crate::types::{FlatLen, Flatten};
7use arcstr::ArcStr;
8use scir::Direction;
9use serde::{Deserialize, Serialize};
10use std::collections::{BTreeMap, HashMap};
11use std::ops::Deref;
12
13use super::{Array, ArrayBundle, BundleKind, HasBundleKind, Io, Signal, Unflatten};
14
15/// A type that has a bundle of nodes.
16pub trait HasNodeBundle: HasBundleKind + Sized + Send + Sync {
17    /// The associated node bundle.
18    type NodeBundle: HasNestedView<NestedView: HasBundleKind<BundleKind = <Self as HasBundleKind>::BundleKind>>
19        + HasBundleKind<BundleKind = <Self as HasBundleKind>::BundleKind>
20        + Unflatten<<Self as HasBundleKind>::BundleKind, Node>
21        + Flatten<Node>;
22}
23
24/// A type that has a bundle of terminals.
25pub trait HasTerminalBundle: HasBundleKind + Sized + Send + Sync {
26    /// The associated terminal bundle.
27    type TerminalBundle: HasNestedView<NestedView: HasBundleKind<BundleKind = <Self as HasBundleKind>::BundleKind>>
28        + HasBundleKind<BundleKind = <Self as HasBundleKind>::BundleKind>
29        + Unflatten<<Self as HasBundleKind>::BundleKind, Terminal>
30        + Flatten<Terminal>
31        + Flatten<Node>;
32}
33
34/// A schematic bundle kind.
35pub trait SchematicBundleKind: BundleKind + HasNodeBundle + HasTerminalBundle {
36    /// Creates a terminal view of the object given a parent node, the cell IO, and the instance IO.
37    fn terminal_view(
38        cell: CellId,
39        cell_io: &NodeBundle<Self>,
40        instance: InstanceId,
41        instance_io: &NodeBundle<Self>,
42    ) -> TerminalBundle<Self>;
43}
44
45/// A schematic bundle kind that can be viewed as another bundle kind `T`.
46pub trait DataView<T: SchematicBundleKind>: SchematicBundleKind {
47    /// Views a node bundle as a node bundle of a different kind.
48    fn view_nodes_as(nodes: &NodeBundle<Self>) -> NodeBundle<T>;
49
50    /// Views a terminal bundle as a terminal bundle of a different kind.
51    fn view_terminals_as(terminals: &TerminalBundle<Self>) -> TerminalBundle<T> {
52        // TODO: Do some sanity checking/error handling.
53        let kind = terminals.kind();
54        let flat_terminals = Flatten::<Terminal>::flatten_vec(terminals);
55        let terminal_map = flat_terminals
56            .iter()
57            .map(|terminal| (terminal.instance_node, terminal))
58            .collect::<HashMap<_, _>>();
59        let mut flat_nodes = flat_terminals.iter().map(|terminal| terminal.instance_node);
60        let nodes = NodeBundle::<Self>::unflatten(&kind, &mut flat_nodes).unwrap();
61        let nodes_view = Self::view_nodes_as(&nodes);
62        let nodes_view_kind = nodes_view.kind();
63        let flat_nodes_view = Flatten::<Node>::flatten_vec(&nodes_view);
64        let mut flat_terminals_view = flat_nodes_view.iter().map(|node| *terminal_map[node]);
65        TerminalBundle::<T>::unflatten(&nodes_view_kind, &mut flat_terminals_view).unwrap()
66    }
67}
68
69impl<T: SchematicBundleKind> DataView<Array<Signal>> for T {
70    fn view_nodes_as(nodes: &NodeBundle<Self>) -> NodeBundle<Array<Signal>> {
71        ArrayBundle::new(
72            Signal,
73            <NodeBundle<Self> as Flatten<Node>>::flatten_vec(nodes),
74        )
75    }
76}
77
78/// The type of a bundle associated with an IO.
79pub type IoNodeBundle<T> = NodeBundle<<T as Block>::Io>;
80/// The type of a terminal bundle associated with an IO.
81pub type IoTerminalBundle<T> = TerminalBundle<<T as Block>::Io>;
82/// The type of a node bundle associated with [`SchematicBundleKind`] `T`.
83pub type NodeBundle<T> = <<T as HasBundleKind>::BundleKind as HasNodeBundle>::NodeBundle;
84/// The type of a terminal bundle associated with [`SchematicBundleKind`] `T`.
85pub type TerminalBundle<T> =
86    <<T as HasBundleKind>::BundleKind as HasTerminalBundle>::TerminalBundle;
87
88/// The priority a node has in determining the name of a merged node.
89#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, Ord, PartialOrd, Serialize, Deserialize)]
90pub(crate) enum NodePriority {
91    /// An IO / externally-visible signal name.
92    ///
93    /// Has the highest priority in determining node names.
94    Io = 3,
95    /// An explicitly named signal.
96    Named = 2,
97    /// A signal with an automatically-generated name.
98    ///
99    /// Has the lowest priority in determining node names.
100    Auto = 1,
101}
102
103/// A node unification table for connectivity management.
104pub type NodeUf = ena::unify::InPlaceUnificationTable<Node>;
105
106#[derive(Clone, Debug)]
107pub(crate) struct NodeConnectDirectionError {
108    #[allow(dead_code)]
109    data: Vec<[(Direction, NodeDriverData); 2]>,
110}
111
112/// A single node in a circuit.
113#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, Serialize, Deserialize)]
114pub struct Node(u32);
115
116impl FlatLen for Node {
117    fn len(&self) -> usize {
118        1
119    }
120}
121
122impl Flatten<Node> for Node {
123    fn flatten<E>(&self, output: &mut E)
124    where
125        E: Extend<Node>,
126    {
127        output.extend(std::iter::once(*self));
128    }
129}
130
131impl Unflatten<Signal, Node> for Node {
132    fn unflatten<I>(_data: &Signal, source: &mut I) -> Option<Self>
133    where
134        I: Iterator<Item = Node>,
135    {
136        source.next()
137    }
138}
139
140impl HasBundleKind for Node {
141    type BundleKind = Signal;
142
143    fn kind(&self) -> Self::BundleKind {
144        Signal
145    }
146}
147
148impl HasNestedView for Node {
149    type NestedView = NestedNode;
150    fn nested_view(&self, parent: &InstancePath) -> NestedView<Self> {
151        NestedNode {
152            node: *self,
153            instances: parent.clone(),
154        }
155    }
156}
157
158/// A nested node within a cell.
159///
160/// Created when accessing nodes from instances propagated through data.
161#[derive(Clone, Debug)]
162pub struct NestedNode {
163    pub(crate) instances: InstancePath,
164    pub(crate) node: Node,
165}
166
167/// A raw nested node within a cell that is opaque to substrate.
168///
169/// May reference Substrate nodes or nodes within SCIR primitives.
170#[derive(Clone, Debug)]
171pub struct RawNestedNode {
172    pub(crate) instances: InstancePath,
173    pub(crate) tail: ArcStr,
174}
175
176impl RawNestedNode {
177    /// Creates a new [`RawNestedNode`].
178    pub fn new(instances: InstancePath, tail: impl Into<ArcStr>) -> Self {
179        Self {
180            instances,
181            tail: tail.into(),
182        }
183    }
184
185    /// The instances along the path to this nested node.
186    ///
187    /// Does not include instances from the raw tail.
188    pub fn instances(&self) -> &InstancePath {
189        &self.instances
190    }
191
192    /// Returns the raw tail.
193    pub fn tail(&self) -> &ArcStr {
194        &self.tail
195    }
196}
197
198impl HasNestedView for RawNestedNode {
199    type NestedView = RawNestedNode;
200    fn nested_view(&self, parent: &InstancePath) -> NestedView<Self> {
201        RawNestedNode {
202            tail: self.tail.clone(),
203            instances: self.instances.prepend(parent),
204        }
205    }
206}
207
208/// A path from a top level cell to a nested node.
209#[derive(Debug, Clone, Hash, PartialEq, Eq, Serialize, Deserialize)]
210pub struct NodePath {
211    pub(crate) top: CellId,
212    pub(crate) instances: Vec<InstanceId>,
213    pub(crate) node: Node,
214}
215
216impl NestedNode {
217    /// Returns the path to this node.
218    pub fn path(&self) -> NodePath {
219        NodePath {
220            top: self.instances.top,
221            instances: self.instances.path.iter().copied().collect(),
222            node: self.node,
223        }
224    }
225}
226
227impl FlatLen for NestedNode {
228    fn len(&self) -> usize {
229        1
230    }
231}
232
233impl Flatten<NestedNode> for NestedNode {
234    fn flatten<E>(&self, output: &mut E)
235    where
236        E: Extend<NestedNode>,
237    {
238        output.extend(std::iter::once(self.clone()));
239    }
240}
241
242impl HasBundleKind for NestedNode {
243    type BundleKind = Signal;
244
245    fn kind(&self) -> Self::BundleKind {
246        Signal
247    }
248}
249
250impl HasNestedView for NestedNode {
251    type NestedView = NestedNode;
252    fn nested_view(&self, parent: &InstancePath) -> NestedView<Self> {
253        NestedNode {
254            node: self.node,
255            instances: self.instances.prepend(parent),
256        }
257    }
258}
259
260impl FlatLen for Vec<Node> {
261    fn len(&self) -> usize {
262        self.len()
263    }
264}
265
266impl Flatten<Node> for Vec<Node> {
267    fn flatten<E>(&self, output: &mut E)
268    where
269        E: Extend<Node>,
270    {
271        output.extend(self.iter().copied());
272    }
273}
274
275impl From<NestedNode> for NodePath {
276    fn from(value: NestedNode) -> Self {
277        value.path()
278    }
279}
280
281impl From<&NestedNode> for NodePath {
282    fn from(value: &NestedNode) -> Self {
283        value.path()
284    }
285}
286
287/// A terminal of an instance.
288#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, Serialize, Deserialize)]
289pub struct Terminal {
290    pub(crate) cell_id: CellId,
291    pub(crate) cell_node: Node,
292    pub(crate) instance_id: InstanceId,
293    pub(crate) instance_node: Node,
294}
295
296impl Deref for Terminal {
297    type Target = Node;
298
299    fn deref(&self) -> &Self::Target {
300        &self.instance_node
301    }
302}
303
304impl AsRef<Node> for Terminal {
305    fn as_ref(&self) -> &Node {
306        self
307    }
308}
309
310impl FlatLen for Terminal {
311    fn len(&self) -> usize {
312        1
313    }
314}
315
316impl Flatten<Node> for Terminal {
317    fn flatten<E>(&self, output: &mut E)
318    where
319        E: Extend<Node>,
320    {
321        output.extend(std::iter::once(self.instance_node));
322    }
323}
324
325impl Flatten<Terminal> for Terminal {
326    fn flatten<E>(&self, output: &mut E)
327    where
328        E: Extend<Terminal>,
329    {
330        output.extend(std::iter::once(*self));
331    }
332}
333
334impl Unflatten<Signal, Terminal> for Terminal {
335    fn unflatten<I>(_data: &Signal, source: &mut I) -> Option<Self>
336    where
337        I: Iterator<Item = Terminal>,
338    {
339        source.next()
340    }
341}
342
343impl HasBundleKind for Terminal {
344    type BundleKind = Signal;
345
346    fn kind(&self) -> Self::BundleKind {
347        Signal
348    }
349}
350
351impl HasNestedView for Terminal {
352    type NestedView = NestedTerminal;
353    fn nested_view(&self, parent: &InstancePath) -> NestedView<Self> {
354        NestedTerminal(NestedNode {
355            instances: parent.append_segment(self.instance_id, self.cell_id),
356            node: self.cell_node,
357        })
358    }
359}
360
361/// A nested instance terminal.
362#[derive(Clone, Debug)]
363pub struct NestedTerminal(NestedNode);
364
365impl Deref for NestedTerminal {
366    type Target = NestedNode;
367
368    fn deref(&self) -> &Self::Target {
369        &self.0
370    }
371}
372
373impl AsRef<NestedNode> for NestedTerminal {
374    fn as_ref(&self) -> &NestedNode {
375        self
376    }
377}
378
379impl NestedTerminal {
380    /// Returns the path to this [`NestedTerminal`].
381    pub fn path(&self) -> TerminalPath {
382        TerminalPath(self.0.path())
383    }
384}
385
386impl FlatLen for NestedTerminal {
387    fn len(&self) -> usize {
388        1
389    }
390}
391
392impl Flatten<NestedTerminal> for NestedTerminal {
393    fn flatten<E>(&self, output: &mut E)
394    where
395        E: Extend<NestedTerminal>,
396    {
397        output.extend(std::iter::once(self.clone()));
398    }
399}
400
401impl HasBundleKind for NestedTerminal {
402    type BundleKind = Signal;
403
404    fn kind(&self) -> Self::BundleKind {
405        Signal
406    }
407}
408
409impl HasNestedView for NestedTerminal {
410    type NestedView = NestedTerminal;
411    fn nested_view(&self, parent: &InstancePath) -> NestedView<Self> {
412        NestedTerminal(<NestedNode as HasNestedView>::nested_view(&self.0, parent))
413    }
414}
415
416/// A path to an instance's terminal.
417#[derive(Debug, Clone, Hash, PartialEq, Eq, Serialize, Deserialize)]
418pub struct TerminalPath(NodePath);
419
420impl Deref for TerminalPath {
421    type Target = NodePath;
422
423    fn deref(&self) -> &Self::Target {
424        &self.0
425    }
426}
427
428impl AsRef<NodePath> for TerminalPath {
429    fn as_ref(&self) -> &NodePath {
430        self
431    }
432}
433
434impl From<NestedTerminal> for TerminalPath {
435    fn from(value: NestedTerminal) -> Self {
436        value.path()
437    }
438}
439
440impl From<&NestedTerminal> for TerminalPath {
441    fn from(value: &NestedTerminal) -> Self {
442        value.path()
443    }
444}
445
446/// The value associated to a node in a schematic builder's union find data structure.
447#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, Serialize, Deserialize)]
448#[doc(hidden)]
449pub struct NodeUfValue {
450    /// The overall priority of a set of merged nodes.
451    ///
452    /// Taken to be the highest among priorities of all nodes
453    /// in the merged set.
454    priority: NodePriority,
455
456    /// The node that provides `priority`.
457    ///
458    /// For example, if priority is NodePriority::Io, `node`
459    /// should be the node identifier representing the IO node.
460    pub(crate) source: Node,
461}
462
463impl ena::unify::UnifyValue for NodeUfValue {
464    type Error = ena::unify::NoError;
465
466    fn unify_values(value1: &Self, value2: &Self) -> std::result::Result<Self, Self::Error> {
467        if value1.priority == NodePriority::Io
468            && value2.priority == NodePriority::Io
469            && value1.source != value2.source
470        {
471            panic!("shorted IOs are not supported")
472        }
473        Ok(if value1.priority >= value2.priority {
474            *value1
475        } else {
476            *value2
477        })
478    }
479}
480
481impl ena::unify::UnifyKey for Node {
482    type Value = Option<NodeUfValue>;
483    fn index(&self) -> u32 {
484        self.0
485    }
486
487    fn from_index(u: u32) -> Self {
488        Self(u)
489    }
490
491    fn tag() -> &'static str {
492        "Node"
493    }
494}
495
496#[derive(Clone)]
497pub(crate) struct NodeContext {
498    uf: NodeUf,
499    connections_data: Vec<Option<NodeConnectionsData>>,
500}
501
502#[derive(Clone, Debug)]
503struct NodeConnectionsData {
504    /// Info about all attached nodes on the net, grouped by direction
505    drivers: BTreeMap<Direction, NodeDriverData>,
506}
507
508impl NodeConnectionsData {
509    fn merge_from(&mut self, other: Self) {
510        for (direction, data) in other.drivers {
511            use std::collections::btree_map::Entry;
512            match self.drivers.entry(direction) {
513                Entry::Vacant(entry) => {
514                    entry.insert(data);
515                }
516                Entry::Occupied(mut entry) => {
517                    entry.get_mut().merge_from(data);
518                }
519            }
520        }
521    }
522
523    fn from_single(direction: Direction, source_info: SourceInfo) -> Self {
524        Self {
525            drivers: [(direction, NodeDriverData::from_single(source_info))].into(),
526        }
527    }
528
529    fn empty() -> Self {
530        Self { drivers: [].into() }
531    }
532}
533
534impl Default for NodeConnectionsData {
535    fn default() -> Self {
536        Self::empty()
537    }
538}
539
540/// Information about all nodes on a net of a particular [`Direction`]
541#[derive(Clone, Debug)]
542struct NodeDriverData {
543    // FIXME: come up with some mechanism for representing root cell IO
544    // locations (there's no call-site source info that would make sense)
545    /// Locations at which nodes on this net were instantiated
546    sources: Vec<SourceInfo>,
547}
548
549impl NodeDriverData {
550    fn merge_from(&mut self, other: Self) {
551        self.sources.extend(other.sources);
552    }
553
554    fn from_single(source_info: SourceInfo) -> Self {
555        Self {
556            sources: vec![source_info],
557        }
558    }
559}
560
561impl NodeContext {
562    #[inline]
563    pub(crate) fn new() -> Self {
564        Self {
565            uf: Default::default(),
566            connections_data: vec![],
567        }
568    }
569
570    fn connections_data(&self, node: Node) -> &Option<NodeConnectionsData> {
571        &self.connections_data[usize::try_from(ena::unify::UnifyKey::index(&node)).unwrap()]
572    }
573
574    fn connections_data_mut(&mut self, node: Node) -> &mut Option<NodeConnectionsData> {
575        &mut self.connections_data[usize::try_from(ena::unify::UnifyKey::index(&node)).unwrap()]
576    }
577
578    pub(crate) fn node(
579        &mut self,
580        direction: Option<Direction>,
581        priority: NodePriority,
582        source_info: SourceInfo,
583    ) -> Node {
584        let id = self.uf.new_key(Default::default());
585
586        assert_eq!(
587            usize::try_from(ena::unify::UnifyKey::index(&id)).unwrap(),
588            self.connections_data.len()
589        );
590        self.connections_data.push(Some(
591            direction
592                .map(|direction| NodeConnectionsData::from_single(direction, source_info))
593                .unwrap_or_default(),
594        ));
595        // scuffed self-consistency check - false negatives possible
596        debug_assert!(self.connections_data_mut(id).is_some());
597
598        self.uf.union_value(
599            id,
600            Some(NodeUfValue {
601                priority,
602                source: id,
603            }),
604        );
605
606        id
607    }
608
609    #[inline]
610    pub fn into_uf(self) -> NodeUf {
611        self.uf
612    }
613
614    fn nodes_directed(
615        &mut self,
616        directions: &[Direction],
617        priority: NodePriority,
618        source_info: SourceInfo,
619    ) -> Vec<Node> {
620        directions
621            .iter()
622            .map(|dir| self.node(Some(*dir), priority, source_info.clone()))
623            .collect()
624    }
625
626    fn nodes_undirected(
627        &mut self,
628        n: usize,
629        priority: NodePriority,
630        source_info: SourceInfo,
631    ) -> Vec<Node> {
632        (0..n)
633            .map(|_| self.node(None, priority, source_info.clone()))
634            .collect()
635    }
636
637    pub fn instantiate_directed<IO: Io + HasBundleKind<BundleKind: SchematicBundleKind>>(
638        &mut self,
639        io: &IO,
640        priority: NodePriority,
641        source_info: SourceInfo,
642    ) -> (Vec<Node>, NodeBundle<IO>) {
643        let nodes = self.nodes_directed(&io.flatten_vec(), priority, source_info);
644        let data = NodeBundle::<IO>::unflatten(&io.kind(), &mut nodes.iter().copied()).unwrap();
645        (nodes, data)
646    }
647
648    pub fn instantiate_undirected<K: HasBundleKind<BundleKind: SchematicBundleKind>>(
649        &mut self,
650        kind: &K,
651        priority: NodePriority,
652        source_info: SourceInfo,
653    ) -> (Vec<Node>, NodeBundle<K>) {
654        let kind = kind.kind();
655        let nodes = self.nodes_undirected(kind.len(), priority, source_info);
656        let data = NodeBundle::<K>::unflatten(&kind, &mut nodes.iter().copied()).unwrap();
657        (nodes, data)
658    }
659
660    pub(crate) fn connect(&mut self, n1: Node, n2: Node, source_info: SourceInfo) {
661        fn get_root(this: &mut NodeContext, n: Node) -> Node {
662            this.uf
663                .probe_value(n)
664                .expect("node should be populated")
665                .source
666        }
667
668        let n1_root = get_root(self, n1);
669        let n2_root = get_root(self, n2);
670
671        if n1_root == n2_root {
672            tracing::info!(?source_info, "connecting nodes that are already connected");
673            return;
674        }
675
676        let n1_connections_data = self
677            .connections_data(n1_root)
678            .as_ref()
679            .expect("n1 should be populated");
680        let n2_connections_data = self
681            .connections_data(n2_root)
682            .as_ref()
683            .expect("n1 should be populated");
684
685        // TODO: potentially use an algorithm better than n^2?
686        let incompatible_drivers: Vec<_> = n1_connections_data
687            .drivers
688            .iter()
689            .flat_map(|e1| n2_connections_data.drivers.iter().map(move |e2| [e1, e2]))
690            .filter(|[(k1, _), (k2, _)]| !k1.is_compatible_with(**k2))
691            .collect();
692        if !incompatible_drivers.is_empty() {
693            // If drivers are not compatible, return an error but connect them
694            // anyways, because (1) we would like to detect further errors
695            // that may be caused by the connection being made and (2) the
696            // error might be spurious and waived by the user.
697            let err = NodeConnectDirectionError {
698                data: incompatible_drivers
699                    .iter()
700                    .map(|&[(&k1, v1), (&k2, v2)]| [(k1, v1.clone()), (k2, v2.clone())])
701                    .collect(),
702            };
703            tracing::warn!(?err, "incompatible drivers");
704        }
705
706        self.uf.union(n1, n2);
707
708        let new_root = get_root(self, n1);
709        let old_root = match new_root {
710            x if x == n1_root => n2_root,
711            x if x == n2_root => n1_root,
712            _ => panic!(
713                "connect: new root isn't any of the old roots? (got {:?}, had {:?} {:?})",
714                new_root, n1_root, n2_root
715            ),
716        };
717
718        let old_connections_data = self
719            .connections_data_mut(old_root)
720            .take()
721            .expect("old root should be populated");
722        self.connections_data_mut(new_root)
723            .as_mut()
724            .expect("new root should be populated")
725            .merge_from(old_connections_data);
726    }
727}
728
729/// A signal exposed by a cell.
730#[allow(dead_code)]
731#[derive(Debug, Clone, Serialize, Deserialize)]
732pub struct Port {
733    direction: Direction,
734    node: Node,
735}
736
737impl Port {
738    #[inline]
739    pub(crate) fn new(node: Node, direction: Direction) -> Self {
740        Self { node, direction }
741    }
742
743    #[inline]
744    #[allow(dead_code)]
745    pub(crate) fn direction(&self) -> Direction {
746        self.direction
747    }
748
749    #[inline]
750    pub(crate) fn node(&self) -> Node {
751        self.node
752    }
753}
substrate/types/schematic.rs

substrate/types/
schematic.rs
