wellen/
hierarchy.rs

1// Copyright 2023-2024 The Regents of the University of California
2// Copyright 2024-2025 Cornell University
3// released under BSD 3-Clause License
4// author: Kevin Laeufer <laeufer@cornell.edu>
5
6use crate::FileFormat;
7use indexmap::IndexSet;
8use rustc_hash::{FxBuildHasher, FxHashMap};
9use std::num::{NonZeroI32, NonZeroU16, NonZeroU32};
10use std::ops::Index;
11
12#[derive(Debug, Clone, Copy, PartialEq)]
13#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
14pub struct Timescale {
15    pub factor: u32,
16    pub unit: TimescaleUnit,
17}
18
19impl Timescale {
20    pub fn new(factor: u32, unit: TimescaleUnit) -> Self {
21        Timescale { factor, unit }
22    }
23}
24
25#[derive(Debug, Clone, Copy, PartialEq)]
26#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
27pub enum TimescaleUnit {
28    ZeptoSeconds,
29    AttoSeconds,
30    FemtoSeconds,
31    PicoSeconds,
32    NanoSeconds,
33    MicroSeconds,
34    MilliSeconds,
35    Seconds,
36    Unknown,
37}
38
39impl TimescaleUnit {
40    pub fn to_exponent(&self) -> Option<i8> {
41        match &self {
42            TimescaleUnit::ZeptoSeconds => Some(-21),
43            TimescaleUnit::AttoSeconds => Some(-18),
44            TimescaleUnit::FemtoSeconds => Some(-15),
45            TimescaleUnit::PicoSeconds => Some(-12),
46            TimescaleUnit::NanoSeconds => Some(-9),
47            TimescaleUnit::MicroSeconds => Some(-6),
48            TimescaleUnit::MilliSeconds => Some(-3),
49            TimescaleUnit::Seconds => Some(0),
50            TimescaleUnit::Unknown => None,
51        }
52    }
53}
54
55/// Uniquely identifies a variable in the hierarchy.
56/// Replaces the old `SignalRef`.
57#[derive(Debug, Clone, Copy, PartialEq, Eq)]
58#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
59pub struct VarRef(NonZeroU32);
60
61impl VarRef {
62    #[inline]
63    pub fn from_index(index: usize) -> Option<Self> {
64        NonZeroU32::new(index as u32 + 1).map(VarRef)
65    }
66
67    #[inline]
68    pub fn index(&self) -> usize {
69        (self.0.get() - 1) as usize
70    }
71}
72
73impl Default for VarRef {
74    fn default() -> Self {
75        Self::from_index(0).unwrap()
76    }
77}
78
79/// Uniquely identifies a scope in the hierarchy.
80/// Replaces the old `ModuleRef`.
81#[derive(Debug, Clone, Copy, Eq, PartialEq, Hash)]
82#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
83pub struct ScopeRef(NonZeroU32);
84
85impl ScopeRef {
86    #[inline]
87    pub const fn from_index(index: usize) -> Option<Self> {
88        match NonZeroU32::new(index as u32 + 1) {
89            None => None,
90            Some(v) => Some(Self(v)),
91        }
92    }
93
94    #[inline]
95    pub fn index(&self) -> usize {
96        (self.0.get() - 1) as usize
97    }
98}
99
100impl Default for ScopeRef {
101    fn default() -> Self {
102        Self::from_index(0).unwrap()
103    }
104}
105
106#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
107#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
108pub struct HierarchyStringId(NonZeroU32);
109
110impl HierarchyStringId {
111    #[inline]
112    fn from_index(index: usize) -> Self {
113        let value = (index + 1) as u32;
114        HierarchyStringId(NonZeroU32::new(value).unwrap())
115    }
116
117    #[inline]
118    fn index(&self) -> usize {
119        (self.0.get() - 1) as usize
120    }
121}
122
123#[derive(Debug, Clone, Copy, Eq, PartialEq)]
124#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
125#[non_exhaustive]
126pub enum ScopeType {
127    // VCD Scope Types
128    Module,
129    Task,
130    Function,
131    Begin,
132    Fork,
133    Generate,
134    Struct,
135    Union,
136    Class,
137    Interface,
138    Package,
139    Program,
140    // VHDL
141    VhdlArchitecture,
142    VhdlProcedure,
143    VhdlFunction,
144    VhdlRecord,
145    VhdlProcess,
146    VhdlBlock,
147    VhdlForGenerate,
148    VhdlIfGenerate,
149    VhdlGenerate,
150    VhdlPackage,
151    // from GHW
152    GhwGeneric,
153    VhdlArray,
154    // for questa sim
155    Unknown,
156}
157
158#[derive(Debug, Clone, Copy, PartialEq, Eq)]
159#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
160pub enum VarType {
161    // VCD
162    Event,
163    Integer,
164    Parameter,
165    Real,
166    Reg,
167    Supply0,
168    Supply1,
169    Time,
170    Tri,
171    TriAnd,
172    TriOr,
173    TriReg,
174    Tri0,
175    Tri1,
176    WAnd,
177    Wire,
178    WOr,
179    String,
180    Port,
181    SparseArray,
182    RealTime,
183    // System Verilog
184    Bit,
185    Logic,
186    Int,
187    ShortInt,
188    LongInt,
189    Byte,
190    Enum,
191    ShortReal,
192    // VHDL (these are the types emitted by GHDL)
193    Boolean,
194    BitVector,
195    StdLogic,
196    StdLogicVector,
197    StdULogic,
198    StdULogicVector,
199}
200
201/// Signal directions of a variable. Currently these have the exact same meaning as in the FST format.
202///
203/// For VCD inputs, all variables will be marked as `VarDirection::Unknown` since no direction information is included.
204#[derive(Debug, Clone, Copy, Eq, PartialEq)]
205#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
206pub enum VarDirection {
207    Unknown,
208    Implicit,
209    Input,
210    Output,
211    InOut,
212    Buffer,
213    Linkage,
214}
215
216impl VarDirection {
217    pub fn vcd_default() -> Self {
218        VarDirection::Unknown
219    }
220}
221
222#[derive(Debug, Clone, Copy, Eq, PartialEq)]
223#[repr(Rust, packed(4))]
224#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
225pub struct VarIndex {
226    lsb: i64,
227    width: NonZeroI32,
228}
229
230const DEFAULT_ZERO_REPLACEMENT: NonZeroI32 = NonZeroI32::new(i32::MIN).unwrap();
231
232impl VarIndex {
233    pub fn new(msb: i64, lsb: i64) -> Self {
234        let width = NonZeroI32::new((msb - lsb) as i32).unwrap_or(DEFAULT_ZERO_REPLACEMENT);
235        Self { lsb, width }
236    }
237
238    #[inline]
239    pub fn msb(&self) -> i64 {
240        if self.width == DEFAULT_ZERO_REPLACEMENT {
241            self.lsb()
242        } else {
243            self.width.get() as i64 + self.lsb()
244        }
245    }
246
247    #[inline]
248    pub fn lsb(&self) -> i64 {
249        self.lsb
250    }
251
252    #[inline]
253    pub fn length(&self) -> u32 {
254        if self.width == DEFAULT_ZERO_REPLACEMENT {
255            1
256        } else {
257            self.width.get().unsigned_abs() + 1
258        }
259    }
260}
261
262/// Signal identifier in the waveform (VCD, FST, etc.) file.
263#[derive(Debug, Clone, Copy, Eq, Hash, PartialEq, PartialOrd, Ord)]
264#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
265pub struct SignalRef(NonZeroU32);
266
267impl SignalRef {
268    #[inline]
269    pub fn from_index(index: usize) -> Option<Self> {
270        NonZeroU32::new(index as u32 + 1).map(Self)
271    }
272
273    #[inline]
274    pub fn index(&self) -> usize {
275        (self.0.get() - 1) as usize
276    }
277}
278
279/// Specifies how the underlying signal of a variable is encoded.
280/// This is different from the `VarType` which tries to correspond to the variable type in the
281/// source HDL code.
282#[derive(Debug, Clone, Copy, Eq, PartialEq)]
283#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
284pub enum SignalEncoding {
285    /// encoded as variable length strings
286    String,
287    /// encoded as 64-bit floating point values
288    Real,
289    /// encoded as a fixed width bit-vector
290    BitVector(NonZeroU32),
291}
292
293impl SignalEncoding {
294    pub fn bit_vec_of_len(len: u32) -> Self {
295        match NonZeroU32::new(len) {
296            // a zero length signal should be represented as a 1-bit signal
297            None => SignalEncoding::BitVector(NonZeroU32::new(1).unwrap()),
298            Some(value) => SignalEncoding::BitVector(value),
299        }
300    }
301}
302
303#[derive(Debug, Clone)]
304#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
305pub struct Var {
306    name: HierarchyStringId,
307    var_tpe: VarType,
308    direction: VarDirection,
309    signal_encoding: SignalEncoding,
310    index: Option<VarIndex>,
311    signal_idx: SignalRef,
312    enum_type: Option<EnumTypeId>,
313    vhdl_type_name: Option<HierarchyStringId>,
314    parent: Option<ScopeRef>,
315    next: Option<ScopeOrVarRef>,
316}
317
318/// Represents a slice of another signal identified by its `SignalRef`.
319/// This is helpful for formats like GHW where some signals are directly defined as
320/// slices of other signals, and thus we only save the data of the larger signal.
321#[derive(Debug, Copy, Clone)]
322#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
323pub struct SignalSlice {
324    pub msb: u32,
325    pub lsb: u32,
326    pub sliced_signal: SignalRef,
327}
328
329const SCOPE_SEPARATOR: char = '.';
330
331impl Var {
332    /// Local name of the variable.
333    #[inline]
334    pub fn name<'a>(&self, hierarchy: &'a Hierarchy) -> &'a str {
335        &hierarchy[self.name]
336    }
337
338    /// Full hierarchical name of the variable.
339    pub fn full_name(&self, hierarchy: &Hierarchy) -> String {
340        match self.parent {
341            None => self.name(hierarchy).to_string(),
342            Some(parent) => {
343                let mut out = hierarchy[parent].full_name(hierarchy);
344                out.push(SCOPE_SEPARATOR);
345                out.push_str(self.name(hierarchy));
346                out
347            }
348        }
349    }
350
351    pub fn var_type(&self) -> VarType {
352        self.var_tpe
353    }
354    pub fn enum_type<'a>(
355        &self,
356        hierarchy: &'a Hierarchy,
357    ) -> Option<(&'a str, Vec<(&'a str, &'a str)>)> {
358        self.enum_type.map(|id| hierarchy.get_enum_type(id))
359    }
360
361    #[inline]
362    pub fn vhdl_type_name<'a>(&self, hierarchy: &'a Hierarchy) -> Option<&'a str> {
363        self.vhdl_type_name.map(|i| &hierarchy[i])
364    }
365
366    pub fn direction(&self) -> VarDirection {
367        self.direction
368    }
369    pub fn index(&self) -> Option<VarIndex> {
370        self.index
371    }
372    pub fn signal_ref(&self) -> SignalRef {
373        self.signal_idx
374    }
375    pub fn length(&self) -> Option<u32> {
376        match &self.signal_encoding {
377            SignalEncoding::String => None,
378            SignalEncoding::Real => None,
379            SignalEncoding::BitVector(len) => Some(len.get()),
380        }
381    }
382    pub fn is_real(&self) -> bool {
383        matches!(self.signal_encoding, SignalEncoding::Real)
384    }
385    pub fn is_string(&self) -> bool {
386        matches!(self.signal_encoding, SignalEncoding::String)
387    }
388    pub fn is_bit_vector(&self) -> bool {
389        matches!(self.signal_encoding, SignalEncoding::BitVector(_))
390    }
391    pub fn is_1bit(&self) -> bool {
392        match self.length() {
393            Some(l) => l == 1,
394            _ => false,
395        }
396    }
397    pub fn signal_encoding(&self) -> SignalEncoding {
398        self.signal_encoding
399    }
400}
401
402#[derive(Debug, Clone, Copy)]
403#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
404pub enum ScopeOrVarRef {
405    Scope(ScopeRef),
406    Var(VarRef),
407}
408
409impl ScopeOrVarRef {
410    pub fn deref<'a>(&self, h: &'a Hierarchy) -> ScopeOrVar<'a> {
411        h.get_item(*self)
412    }
413}
414
415impl From<ScopeRef> for ScopeOrVarRef {
416    fn from(value: ScopeRef) -> Self {
417        Self::Scope(value)
418    }
419}
420
421impl From<VarRef> for ScopeOrVarRef {
422    fn from(value: VarRef) -> Self {
423        Self::Var(value)
424    }
425}
426
427#[derive(Debug, Clone, Copy)]
428pub enum ScopeOrVar<'a> {
429    Scope(&'a Scope),
430    Var(&'a Var),
431}
432
433#[derive(Debug, Clone)]
434#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
435pub struct Scope {
436    name: HierarchyStringId,
437    /// Some wave formats supply the name of the component, e.g., of the module that was instantiated.
438    component: Option<HierarchyStringId>,
439    tpe: ScopeType,
440    declaration_source: Option<SourceLocId>,
441    instance_source: Option<SourceLocId>,
442    child: Option<ScopeOrVarRef>,
443    parent: Option<ScopeRef>,
444    next: Option<ScopeOrVarRef>,
445}
446
447impl Scope {
448    /// Local name of the scope.
449    pub fn name<'a>(&self, hierarchy: &'a Hierarchy) -> &'a str {
450        &hierarchy[self.name]
451    }
452
453    /// Local name of the component, e.g., the name of the module that was instantiated.
454    pub fn component<'a>(&self, hierarchy: &'a Hierarchy) -> Option<&'a str> {
455        self.component.map(|n| &hierarchy[n])
456    }
457
458    /// Full hierarchical name of the scope.
459    pub fn full_name(&self, hierarchy: &Hierarchy) -> String {
460        let mut parents = Vec::new();
461        let mut parent = self.parent;
462        while let Some(id) = parent {
463            parents.push(id);
464            parent = hierarchy[id].parent;
465        }
466        let mut out: String = String::with_capacity((parents.len() + 1) * 5);
467        for parent_id in parents.iter().rev() {
468            out.push_str(hierarchy[*parent_id].name(hierarchy));
469            out.push(SCOPE_SEPARATOR)
470        }
471        out.push_str(self.name(hierarchy));
472        out
473    }
474
475    pub fn scope_type(&self) -> ScopeType {
476        self.tpe
477    }
478
479    pub fn source_loc<'a>(&self, hierarchy: &'a Hierarchy) -> Option<(&'a str, u64)> {
480        self.declaration_source
481            .map(|id| hierarchy.get_source_loc(id))
482    }
483
484    pub fn instantiation_source_loc<'a>(&self, hierarchy: &'a Hierarchy) -> Option<(&'a str, u64)> {
485        self.instance_source.map(|id| hierarchy.get_source_loc(id))
486    }
487
488    pub fn items<'a>(
489        &'a self,
490        hierarchy: &'a Hierarchy,
491    ) -> impl Iterator<Item = ScopeOrVarRef> + 'a {
492        HierarchyItemIdIterator::new(hierarchy, self.child)
493    }
494
495    pub fn vars<'a>(&'a self, hierarchy: &'a Hierarchy) -> impl Iterator<Item = VarRef> + 'a {
496        to_var_ref_iterator(HierarchyItemIdIterator::new(hierarchy, self.child))
497    }
498
499    pub fn scopes<'a>(&'a self, hierarchy: &'a Hierarchy) -> impl Iterator<Item = ScopeRef> + 'a {
500        to_scope_ref_iterator(HierarchyItemIdIterator::new(hierarchy, self.child))
501    }
502}
503
504struct HierarchyItemIdIterator<'a> {
505    hierarchy: &'a Hierarchy,
506    item: Option<ScopeOrVarRef>,
507    is_first: bool,
508}
509
510impl<'a> HierarchyItemIdIterator<'a> {
511    fn new(hierarchy: &'a Hierarchy, item: Option<ScopeOrVarRef>) -> Self {
512        Self {
513            hierarchy,
514            item,
515            is_first: true,
516        }
517    }
518
519    fn get_next(&self, item: ScopeOrVarRef) -> Option<ScopeOrVarRef> {
520        match self.hierarchy.get_item(item) {
521            ScopeOrVar::Scope(scope) => scope.next,
522            ScopeOrVar::Var(var) => var.next,
523        }
524    }
525}
526
527impl Iterator for HierarchyItemIdIterator<'_> {
528    type Item = ScopeOrVarRef;
529
530    fn next(&mut self) -> Option<Self::Item> {
531        match self.item {
532            None => None, // this iterator is done!
533            Some(item) => {
534                if self.is_first {
535                    self.is_first = false;
536                    Some(item)
537                } else {
538                    self.item = self.get_next(item);
539                    self.item
540                }
541            }
542        }
543    }
544}
545
546fn to_var_ref_iterator(iter: impl Iterator<Item = ScopeOrVarRef>) -> impl Iterator<Item = VarRef> {
547    iter.flat_map(|i| match i {
548        ScopeOrVarRef::Scope(_) => None,
549        ScopeOrVarRef::Var(v) => Some(v),
550    })
551}
552
553fn to_scope_ref_iterator(
554    iter: impl Iterator<Item = ScopeOrVarRef>,
555) -> impl Iterator<Item = ScopeRef> {
556    iter.flat_map(|i| match i {
557        ScopeOrVarRef::Scope(s) => Some(s),
558        ScopeOrVarRef::Var(_) => None,
559    })
560}
561
562#[derive(Debug, PartialEq, Copy, Clone)]
563#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
564pub struct SourceLocId(NonZeroU32);
565
566impl SourceLocId {
567    #[inline]
568    fn from_index(index: usize) -> Self {
569        let value = (index + 1) as u32;
570        SourceLocId(NonZeroU32::new(value).unwrap())
571    }
572
573    #[inline]
574    fn index(&self) -> usize {
575        (self.0.get() - 1) as usize
576    }
577}
578
579#[derive(Debug, PartialEq, Copy, Clone)]
580#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
581struct SourceLoc {
582    path: HierarchyStringId,
583    line: u64,
584    is_instantiation: bool,
585}
586
587#[derive(Debug, PartialEq, Copy, Clone)]
588#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
589pub struct EnumTypeId(NonZeroU16);
590
591impl EnumTypeId {
592    #[inline]
593    fn from_index(index: usize) -> Self {
594        let value = (index + 1) as u16;
595        EnumTypeId(NonZeroU16::new(value).unwrap())
596    }
597
598    #[inline]
599    fn index(&self) -> usize {
600        (self.0.get() - 1) as usize
601    }
602}
603
604#[derive(Debug, PartialEq, Clone)]
605#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
606struct EnumType {
607    name: HierarchyStringId,
608    mapping: Vec<(HierarchyStringId, HierarchyStringId)>,
609}
610
611#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
612pub struct Hierarchy {
613    vars: Vec<Var>,
614    scopes: Vec<Scope>,
615    strings: Vec<String>,
616    source_locs: Vec<SourceLoc>,
617    enums: Vec<EnumType>,
618    signal_idx_to_var: Vec<Option<VarRef>>,
619    meta: HierarchyMetaData,
620    slices: FxHashMap<SignalRef, SignalSlice>,
621}
622
623#[cfg_attr(feature = "serde1", derive(serde::Serialize, serde::Deserialize))]
624struct HierarchyMetaData {
625    timescale: Option<Timescale>,
626    date: String,
627    version: String,
628    comments: Vec<String>,
629    file_format: FileFormat,
630}
631
632impl HierarchyMetaData {
633    fn new(file_format: FileFormat) -> Self {
634        HierarchyMetaData {
635            timescale: None,
636            date: "".to_string(),
637            version: "".to_string(),
638            comments: Vec::default(),
639            file_format,
640        }
641    }
642}
643
644// public implementation
645impl Hierarchy {
646    /// Returns an iterator over all variables (at all levels).
647    pub fn iter_vars(&self) -> std::slice::Iter<'_, Var> {
648        self.vars.iter()
649    }
650
651    /// Returns an iterator over all scopes (at all levels).
652    pub fn iter_scopes(&self) -> std::slice::Iter<'_, Scope> {
653        self.scopes.iter()
654    }
655
656    /// Retrieves the first item inside the implicit fake top scope
657    fn first_item(&self) -> Option<ScopeOrVarRef> {
658        debug_assert!(self.scopes[FAKE_TOP_SCOPE.index()].next.is_none());
659        self.scopes[FAKE_TOP_SCOPE.index()].child
660    }
661
662    /// Returns an iterator over references to all top-level scopes and variables.
663    pub fn items(&self) -> impl Iterator<Item = ScopeOrVarRef> + '_ {
664        HierarchyItemIdIterator::new(self, self.first_item())
665    }
666
667    /// Returns an iterator over references to all top-level scopes.
668    pub fn scopes(&self) -> impl Iterator<Item = ScopeRef> + '_ {
669        to_scope_ref_iterator(HierarchyItemIdIterator::new(self, self.first_item()))
670    }
671
672    /// Returns an iterator over references to all top-level variables.
673    pub fn vars(&self) -> impl Iterator<Item = VarRef> + '_ {
674        to_var_ref_iterator(HierarchyItemIdIterator::new(self, self.first_item()))
675    }
676
677    /// Returns the first scope that was declared in the underlying file.
678    pub fn first_scope(&self) -> Option<&Scope> {
679        // we need to skip the fake top scope
680        self.scopes.get(1)
681    }
682
683    /// Returns one variable per unique signal in the order of signal handles.
684    /// The value will be None if there is no var pointing to the given handle.
685    pub fn get_unique_signals_vars(&self) -> Vec<Option<Var>> {
686        let mut out = Vec::with_capacity(self.signal_idx_to_var.len());
687        for maybe_var_id in self.signal_idx_to_var.iter() {
688            if let Some(var_id) = maybe_var_id {
689                out.push(Some((self[*var_id]).clone()));
690            } else {
691                out.push(None)
692            }
693        }
694        out
695    }
696
697    /// Size of the Hierarchy in bytes.
698    pub fn size_in_memory(&self) -> usize {
699        let var_size = self.vars.capacity() * std::mem::size_of::<Var>();
700        let scope_size = self.scopes.capacity() * std::mem::size_of::<Scope>();
701        let string_size = self.strings.capacity() * std::mem::size_of::<String>()
702            + self.strings.iter().map(|s| s.len()).sum::<usize>();
703        let handle_lookup_size = self.signal_idx_to_var.capacity() * std::mem::size_of::<VarRef>();
704        var_size + scope_size + string_size + handle_lookup_size + std::mem::size_of::<Hierarchy>()
705    }
706
707    pub fn date(&self) -> &str {
708        &self.meta.date
709    }
710    pub fn version(&self) -> &str {
711        &self.meta.version
712    }
713    pub fn timescale(&self) -> Option<Timescale> {
714        self.meta.timescale
715    }
716    pub fn file_format(&self) -> FileFormat {
717        self.meta.file_format
718    }
719
720    pub fn lookup_scope<N: AsRef<str>>(&self, names: &[N]) -> Option<ScopeRef> {
721        let prefix = names.first()?.as_ref();
722        let mut scope = self.scopes().find(|s| self[*s].name(self) == prefix)?;
723        for name in names.iter().skip(1) {
724            scope = self[scope]
725                .scopes(self)
726                .find(|s| self[*s].name(self) == name.as_ref())?;
727        }
728        Some(scope)
729    }
730
731    pub fn lookup_var<N: AsRef<str>>(&self, path: &[N], name: &N) -> Option<VarRef> {
732        self.lookup_var_with_index(path, name, &None)
733    }
734
735    pub fn lookup_var_with_index<N: AsRef<str>>(
736        &self,
737        path: &[N],
738        name: &N,
739        index: &Option<VarIndex>,
740    ) -> Option<VarRef> {
741        match path {
742            [] => self.vars().find(|v| {
743                let v = &self[*v];
744                v.name(self) == name.as_ref() && (index.is_none() || (v.index == *index))
745            }),
746            scopes => {
747                let scope = &self[self.lookup_scope(scopes)?];
748                scope.vars(self).find(|v| {
749                    let v = &self[*v];
750                    v.name(self) == name.as_ref() && (index.is_none() || (v.index == *index))
751                })
752            }
753        }
754    }
755}
756
757impl Hierarchy {
758    pub fn num_unique_signals(&self) -> usize {
759        self.signal_idx_to_var.len()
760    }
761
762    /// Retrieves the length of a signal identified by its id by looking up a
763    /// variable that refers to the signal.
764    pub fn get_signal_tpe(&self, signal_idx: SignalRef) -> Option<SignalEncoding> {
765        let var_id = (*self.signal_idx_to_var.get(signal_idx.index())?)?;
766        Some(self[var_id].signal_encoding)
767    }
768
769    pub fn get_slice_info(&self, signal_idx: SignalRef) -> Option<SignalSlice> {
770        self.slices.get(&signal_idx).copied()
771    }
772}
773
774// private implementation
775impl Hierarchy {
776    fn get_source_loc(&self, id: SourceLocId) -> (&str, u64) {
777        let loc = &self.source_locs[id.index()];
778        (&self[loc.path], loc.line)
779    }
780
781    fn get_enum_type(&self, id: EnumTypeId) -> (&str, Vec<(&str, &str)>) {
782        let enum_tpe = &self.enums[id.index()];
783        let name = &self[enum_tpe.name];
784        let mapping = enum_tpe
785            .mapping
786            .iter()
787            .map(|(a, b)| (&self[*a], &self[*b]))
788            .collect::<Vec<_>>();
789        (name, mapping)
790    }
791
792    fn get_item(&self, id: ScopeOrVarRef) -> ScopeOrVar<'_> {
793        match id {
794            ScopeOrVarRef::Scope(id) => ScopeOrVar::Scope(&self[id]),
795            ScopeOrVarRef::Var(id) => ScopeOrVar::Var(&self[id]),
796        }
797    }
798}
799
800impl Index<VarRef> for Hierarchy {
801    type Output = Var;
802
803    fn index(&self, index: VarRef) -> &Self::Output {
804        &self.vars[index.index()]
805    }
806}
807
808impl Index<ScopeRef> for Hierarchy {
809    type Output = Scope;
810
811    fn index(&self, index: ScopeRef) -> &Self::Output {
812        &self.scopes[index.index()]
813    }
814}
815
816impl Index<HierarchyStringId> for Hierarchy {
817    type Output = str;
818
819    fn index(&self, index: HierarchyStringId) -> &Self::Output {
820        &self.strings[index.index()]
821    }
822}
823
824struct ScopeStackEntry {
825    scope_id: usize,
826    last_child: Option<ScopeOrVarRef>,
827    /// indicates that this scope is being flattened and all operations should be done on the parent instead
828    flattened: bool,
829}
830
831pub struct HierarchyBuilder {
832    vars: Vec<Var>,
833    scopes: Vec<Scope>,
834    scope_stack: Vec<ScopeStackEntry>,
835    source_locs: Vec<SourceLoc>,
836    enums: Vec<EnumType>,
837    handle_to_node: Vec<Option<VarRef>>,
838    meta: HierarchyMetaData,
839    slices: FxHashMap<SignalRef, SignalSlice>,
840    /// used to deduplicate strings
841    strings: IndexSet<String, FxBuildHasher>,
842    /// keeps track of the number of children to decide when to switch to a hash table based
843    /// deduplication strategy
844    scope_child_count: Vec<u8>,
845    scope_dedup_tables: FxHashMap<ScopeRef, FxHashMap<HierarchyStringId, ScopeRef>>,
846}
847
848const EMPTY_STRING: HierarchyStringId = HierarchyStringId(NonZeroU32::new(1).unwrap());
849const FAKE_TOP_SCOPE: ScopeRef = ScopeRef::from_index(0).unwrap();
850/// Scopes that have a larger number of children will get a HashTable to
851/// speed up searching for duplicates. Otherwise, we run into a O(n**2) problem.
852const DUPLICATE_SCOPE_HASH_TABLE_THRESHOLD: u8 = 128;
853
854impl HierarchyBuilder {
855    pub fn new(file_type: FileFormat) -> Self {
856        // we start with a fake entry in the scope stack to keep track of multiple items in the top scope
857        let scope_stack = vec![ScopeStackEntry {
858            scope_id: FAKE_TOP_SCOPE.index(),
859            last_child: None,
860            flattened: false,
861        }];
862        let fake_top_scope = Scope {
863            name: EMPTY_STRING,
864            component: None,
865            tpe: ScopeType::Module,
866            declaration_source: None,
867            instance_source: None,
868            child: None,
869            parent: None,
870            next: None,
871        };
872        let mut strings: IndexSet<String, FxBuildHasher> = Default::default();
873        let (zero_id, _) = strings.insert_full("".to_string());
874        // empty string should always map to zero
875        debug_assert_eq!(zero_id, 0);
876        HierarchyBuilder {
877            vars: Vec::default(),
878            scopes: vec![fake_top_scope],
879            scope_stack,
880            strings,
881            source_locs: Vec::default(),
882            enums: Vec::default(),
883            handle_to_node: Vec::default(),
884            meta: HierarchyMetaData::new(file_type),
885            slices: FxHashMap::default(),
886            scope_child_count: vec![0],
887            scope_dedup_tables: Default::default(),
888        }
889    }
890}
891
892impl HierarchyBuilder {
893    pub fn finish(mut self) -> Hierarchy {
894        self.vars.shrink_to_fit();
895        self.scopes.shrink_to_fit();
896        self.strings.shrink_to_fit();
897        self.source_locs.shrink_to_fit();
898        self.enums.shrink_to_fit();
899        self.handle_to_node.shrink_to_fit();
900        self.slices.shrink_to_fit();
901        Hierarchy {
902            vars: self.vars,
903            scopes: self.scopes,
904            strings: self.strings.into_iter().collect::<Vec<_>>(),
905            source_locs: self.source_locs,
906            enums: self.enums,
907            signal_idx_to_var: self.handle_to_node,
908            meta: self.meta,
909            slices: self.slices,
910        }
911    }
912
913    pub fn add_string(&mut self, value: std::borrow::Cow<str>) -> HierarchyStringId {
914        if value.is_empty() {
915            return EMPTY_STRING;
916        }
917        if let Some(index) = self.strings.get_index_of(value.as_ref()) {
918            HierarchyStringId::from_index(index)
919        } else {
920            let (index, _) = self.strings.insert_full(value.into_owned());
921            HierarchyStringId::from_index(index)
922        }
923    }
924
925    pub fn get_str(&self, id: HierarchyStringId) -> &str {
926        &self.strings[id.index()]
927    }
928
929    pub fn add_source_loc(
930        &mut self,
931        path: HierarchyStringId,
932        line: u64,
933        is_instantiation: bool,
934    ) -> SourceLocId {
935        let sym = SourceLocId::from_index(self.source_locs.len());
936        self.source_locs.push(SourceLoc {
937            path,
938            line,
939            is_instantiation,
940        });
941        sym
942    }
943
944    pub fn add_enum_type(
945        &mut self,
946        name: HierarchyStringId,
947        mapping: Vec<(HierarchyStringId, HierarchyStringId)>,
948    ) -> EnumTypeId {
949        let sym = EnumTypeId::from_index(self.enums.len());
950        self.enums.push(EnumType { name, mapping });
951        sym
952    }
953
954    /// adds a variable or scope to the hierarchy tree
955    fn add_to_hierarchy_tree(&mut self, node_id: ScopeOrVarRef) -> Option<ScopeRef> {
956        let entry_pos = find_parent_scope(&self.scope_stack);
957        let entry = &mut self.scope_stack[entry_pos];
958        let parent = entry.scope_id;
959        match entry.last_child {
960            Some(ScopeOrVarRef::Var(child)) => {
961                // add pointer to new node from last child
962                assert!(self.vars[child.index()].next.is_none());
963                self.vars[child.index()].next = Some(node_id);
964            }
965            Some(ScopeOrVarRef::Scope(child)) => {
966                // add pointer to new node from last child
967                assert!(self.scopes[child.index()].next.is_none());
968                self.scopes[child.index()].next = Some(node_id);
969            }
970            None => {
971                // otherwise we need to add a pointer from the parent
972                assert!(self.scopes[parent].child.is_none());
973                self.scopes[parent].child = Some(node_id);
974            }
975        }
976        // the new node is now the last child
977        entry.last_child = Some(node_id);
978        // return the parent id, unless it is the fake top scope
979        let parent_ref = ScopeRef::from_index(parent).unwrap();
980        if parent_ref == FAKE_TOP_SCOPE {
981            None
982        } else {
983            Some(parent_ref)
984        }
985    }
986
987    /// Checks to see if a scope of the same name already exists.
988    fn find_duplicate_scope(&self, name_id: HierarchyStringId) -> Option<ScopeRef> {
989        let parent = &self.scope_stack[find_parent_scope(&self.scope_stack)];
990
991        if self.scope_child_count[parent.scope_id] > DUPLICATE_SCOPE_HASH_TABLE_THRESHOLD {
992            let parent_ref = ScopeRef::from_index(parent.scope_id).unwrap();
993            debug_assert!(self.scope_dedup_tables.contains_key(&parent_ref));
994            self.scope_dedup_tables[&parent_ref].get(&name_id).cloned()
995        } else {
996            // linear search
997            let mut maybe_item = self.scopes[parent.scope_id].child;
998
999            while let Some(item) = maybe_item {
1000                if let ScopeOrVarRef::Scope(other) = item {
1001                    // it is enough to compare the string id
1002                    // since strings get the same id iff they have the same value
1003                    if self.scopes[other.index()].name == name_id {
1004                        // duplicate found!
1005                        return Some(other);
1006                    }
1007                }
1008                maybe_item = self.get_next(item);
1009            }
1010            // no duplicate found
1011            None
1012        }
1013    }
1014
1015    fn get_next(&self, item: ScopeOrVarRef) -> Option<ScopeOrVarRef> {
1016        match item {
1017            ScopeOrVarRef::Scope(scope_ref) => self.scopes[scope_ref.index()].next,
1018            ScopeOrVarRef::Var(var_ref) => self.vars[var_ref.index()].next,
1019        }
1020    }
1021
1022    fn find_last_child(&self, scope: ScopeRef) -> Option<ScopeOrVarRef> {
1023        if let Some(mut child) = self.scopes[scope.index()].child {
1024            while let Some(next) = self.get_next(child) {
1025                child = next;
1026            }
1027            Some(child)
1028        } else {
1029            None
1030        }
1031    }
1032
1033    pub fn add_scope(
1034        &mut self,
1035        name: HierarchyStringId,
1036        component: Option<HierarchyStringId>,
1037        tpe: ScopeType,
1038        declaration_source: Option<SourceLocId>,
1039        instance_source: Option<SourceLocId>,
1040        flatten: bool,
1041    ) {
1042        // check to see if there is a scope of the same name already
1043        // if so we just activate that scope instead of adding a new one
1044        if let Some(duplicate) = self.find_duplicate_scope(name) {
1045            let last_child = self.find_last_child(duplicate);
1046            self.scope_stack.push(ScopeStackEntry {
1047                scope_id: duplicate.index(),
1048                last_child,
1049                flattened: false,
1050            })
1051        } else if flatten {
1052            self.scope_stack.push(ScopeStackEntry {
1053                scope_id: usize::MAX,
1054                last_child: None,
1055                flattened: true,
1056            });
1057        } else {
1058            let node_id = self.scopes.len();
1059            let scope_ref = ScopeRef::from_index(node_id).unwrap();
1060            let parent = self.add_to_hierarchy_tree(scope_ref.into());
1061
1062            // new active scope
1063            self.scope_stack.push(ScopeStackEntry {
1064                scope_id: node_id,
1065                last_child: None,
1066                flattened: false,
1067            });
1068
1069            // empty component name is treated the same as none
1070            let component = component.filter(|&name| name != EMPTY_STRING);
1071
1072            // now we can build the node data structure and store it
1073            let node = Scope {
1074                parent,
1075                child: None,
1076                next: None,
1077                name,
1078                component,
1079                tpe,
1080                declaration_source,
1081                instance_source,
1082            };
1083            self.scopes.push(node);
1084            self.scope_child_count.push(0);
1085
1086            // increment the child count of the parent
1087            self.increment_child_count(parent, name, scope_ref.into());
1088        }
1089    }
1090
1091    /// increments the child count and generates a hash table if we cross the threshold
1092    /// must be called after the child is inserted into the list and into the scope Vec
1093    fn increment_child_count(
1094        &mut self,
1095        parent: Option<ScopeRef>,
1096        child_name: HierarchyStringId,
1097        child_ref: ScopeOrVarRef,
1098    ) {
1099        let p = if let Some(p) = parent {
1100            p
1101        } else {
1102            FAKE_TOP_SCOPE
1103        };
1104
1105        let child_count = self.scope_child_count[p.index()];
1106
1107        if child_count < DUPLICATE_SCOPE_HASH_TABLE_THRESHOLD {
1108            self.scope_child_count[p.index()] += 1;
1109        } else if child_count == DUPLICATE_SCOPE_HASH_TABLE_THRESHOLD {
1110            // we are at the threshold
1111            self.scope_child_count[p.index()] += 1;
1112            debug_assert!(!self.scope_dedup_tables.contains_key(&p));
1113            let lookup = self.build_child_scope_map(p);
1114            self.scope_dedup_tables.insert(p, lookup);
1115        } else {
1116            debug_assert_eq!(child_count, DUPLICATE_SCOPE_HASH_TABLE_THRESHOLD + 1);
1117            debug_assert!(self.scope_dedup_tables.contains_key(&p));
1118            // insert new name
1119            if let ScopeOrVarRef::Scope(child_scope_ref) = child_ref {
1120                self.scope_dedup_tables
1121                    .get_mut(&p)
1122                    .unwrap()
1123                    .insert(child_name, child_scope_ref);
1124            }
1125        }
1126    }
1127
1128    /// Creates a mapping of child scope names to scope references
1129    fn build_child_scope_map(&self, parent: ScopeRef) -> FxHashMap<HierarchyStringId, ScopeRef> {
1130        let mut maybe_item = self.scopes[parent.index()].child;
1131        let mut out = FxHashMap::default();
1132        while let Some(item) = maybe_item {
1133            if let ScopeOrVarRef::Scope(child_scope) = item {
1134                let scope = &self.scopes[child_scope.index()];
1135                out.insert(scope.name, child_scope);
1136            }
1137            maybe_item = self.get_next(item);
1138        }
1139        out
1140    }
1141
1142    /// Helper function for adding scopes that were generated from a nested array name in VCD or FST.
1143    #[inline]
1144    pub fn add_array_scopes(&mut self, names: Vec<std::borrow::Cow<str>>) {
1145        for name in names {
1146            let name_id = self.add_string(name);
1147            self.add_scope(name_id, None, ScopeType::VhdlArray, None, None, false);
1148        }
1149    }
1150
1151    #[allow(clippy::too_many_arguments)]
1152    pub fn add_var(
1153        &mut self,
1154        name: HierarchyStringId,
1155        tpe: VarType,
1156        signal_tpe: SignalEncoding,
1157        direction: VarDirection,
1158        index: Option<VarIndex>,
1159        signal_idx: SignalRef,
1160        enum_type: Option<EnumTypeId>,
1161        vhdl_type_name: Option<HierarchyStringId>,
1162    ) {
1163        let node_id = self.vars.len();
1164        let var_id = VarRef::from_index(node_id).unwrap();
1165        let parent = self.add_to_hierarchy_tree(var_id.into());
1166
1167        // add lookup
1168        let handle_idx = signal_idx.index();
1169        if self.handle_to_node.len() <= handle_idx {
1170            self.handle_to_node.resize(handle_idx + 1, None);
1171        }
1172        self.handle_to_node[handle_idx] = Some(var_id);
1173
1174        // now we can build the node data structure and store it
1175        let node = Var {
1176            parent,
1177            name,
1178            var_tpe: tpe,
1179            index,
1180            direction,
1181            signal_encoding: signal_tpe,
1182            signal_idx,
1183            enum_type,
1184            next: None,
1185            vhdl_type_name,
1186        };
1187        self.vars.push(node);
1188        // increment the child count of the parent
1189        self.increment_child_count(parent, name, var_id.into());
1190    }
1191
1192    #[inline]
1193    pub fn pop_scopes(&mut self, num: usize) {
1194        for _ in 0..num {
1195            self.pop_scope();
1196        }
1197    }
1198
1199    pub fn pop_scope(&mut self) {
1200        self.scope_stack.pop().unwrap();
1201    }
1202
1203    pub fn set_date(&mut self, value: String) {
1204        assert!(
1205            self.meta.date.is_empty(),
1206            "Duplicate dates: {} vs {}",
1207            self.meta.date,
1208            value
1209        );
1210        self.meta.date = value;
1211    }
1212
1213    pub fn set_version(&mut self, value: String) {
1214        assert!(
1215            self.meta.version.is_empty(),
1216            "Duplicate versions: {} vs {}",
1217            self.meta.version,
1218            value
1219        );
1220        self.meta.version = value;
1221    }
1222
1223    pub fn set_timescale(&mut self, value: Timescale) {
1224        assert!(
1225            self.meta.timescale.is_none(),
1226            "Duplicate timescales: {:?} vs {:?}",
1227            self.meta.timescale.unwrap(),
1228            value
1229        );
1230        self.meta.timescale = Some(value);
1231    }
1232
1233    pub fn add_comment(&mut self, comment: String) {
1234        self.meta.comments.push(comment);
1235    }
1236
1237    pub fn add_slice(
1238        &mut self,
1239        signal_ref: SignalRef,
1240        msb: u32,
1241        lsb: u32,
1242        sliced_signal: SignalRef,
1243    ) {
1244        debug_assert!(msb >= lsb);
1245        debug_assert!(!self.slices.contains_key(&signal_ref));
1246        self.slices.insert(
1247            signal_ref,
1248            SignalSlice {
1249                msb,
1250                lsb,
1251                sliced_signal,
1252            },
1253        );
1254    }
1255}
1256
1257/// finds the first not flattened parent scope
1258fn find_parent_scope(scope_stack: &[ScopeStackEntry]) -> usize {
1259    let mut index = scope_stack.len() - 1;
1260    loop {
1261        if scope_stack[index].flattened {
1262            index -= 1;
1263        } else {
1264            return index;
1265        }
1266    }
1267}
1268
1269#[cfg(test)]
1270mod tests {
1271    use super::*;
1272
1273    #[test]
1274    fn test_sizes() {
1275        // unfortunately this one is pretty big
1276        assert_eq!(std::mem::size_of::<ScopeOrVarRef>(), 8);
1277
1278        // 4 byte length + tag + padding
1279        assert_eq!(std::mem::size_of::<SignalEncoding>(), 8);
1280
1281        // var index is packed in order to take up 12 bytes and contains a NonZero field to allow
1282        // for zero cost optioning
1283        assert_eq!(
1284            std::mem::size_of::<VarIndex>(),
1285            std::mem::size_of::<Option<VarIndex>>()
1286        );
1287        assert_eq!(std::mem::size_of::<VarIndex>(), 12);
1288
1289        // Var
1290        assert_eq!(
1291            std::mem::size_of::<Var>(),
1292            std::mem::size_of::<HierarchyStringId>()        // name
1293                + std::mem::size_of::<VarType>()            // var_tpe
1294                + std::mem::size_of::<VarDirection>()       // direction
1295                + std::mem::size_of::<SignalEncoding>()     // signal_encoding
1296                + std::mem::size_of::<Option<VarIndex>>()   // index
1297                + std::mem::size_of::<SignalRef>()          // signal_idx
1298                + std::mem::size_of::<Option<EnumTypeId>>() // enum type
1299                + std::mem::size_of::<HierarchyStringId>()  // VHDL type name
1300                + std::mem::size_of::<Option<ScopeRef>>()   // parent
1301                + std::mem::size_of::<ScopeOrVarRef>() // next
1302        );
1303        // currently this all comes out to 48 bytes (~= 6x 64-bit pointers)
1304        assert_eq!(std::mem::size_of::<Var>(), 48);
1305
1306        // Scope
1307        assert_eq!(
1308            std::mem::size_of::<Scope>(),
1309            std::mem::size_of::<HierarchyStringId>() // name
1310                + std::mem::size_of::<HierarchyStringId>() // component name
1311                + 1 // tpe
1312                + 4 // source info
1313                + 4 // source info
1314                + std::mem::size_of::<ScopeOrVarRef>() // child
1315                + std::mem::size_of::<ScopeRef>() // parent
1316                + std::mem::size_of::<ScopeOrVarRef>() // next
1317                + 3 // padding
1318        );
1319        // currently this all comes out to 40 bytes (= 5x 64-bit pointers)
1320        assert_eq!(std::mem::size_of::<Scope>(), 40);
1321
1322        // for comparison: one string is 24 bytes for the struct alone (ignoring heap allocation)
1323        assert_eq!(std::mem::size_of::<String>(), 24);
1324    }
1325
1326    #[test]
1327    fn test_var_index() {
1328        let msb = 15;
1329        let lsb = -1;
1330        let index = VarIndex::new(msb, lsb);
1331        assert_eq!(index.lsb(), lsb);
1332        assert_eq!(index.msb(), msb);
1333    }
1334}
wellen/hierarchy.rs

wellen/
hierarchy.rs
