#[cfg(test)]
mod tests;
mod path;
use std::{
fmt,
str::FromStr,
sync::{
Arc, OnceLock,
atomic::{AtomicU64, Ordering},
},
};
use crate::{LookupError, PathError, PathFormatError, Result, SliceError};
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct HierarchyPath {
components: Vec<String>,
}
impl HierarchyPath {
pub fn parse(text: &str) -> std::result::Result<Self, PathError> {
path::parse(text).map(|components| Self { components })
}
pub fn from_components<I, S>(components: I) -> Self
where
I: IntoIterator<Item = S>,
S: Into<String>,
{
Self {
components: components.into_iter().map(Into::into).collect(),
}
}
pub fn components(&self) -> impl ExactSizeIterator<Item = &str> + '_ {
self.components.iter().map(String::as_str)
}
pub fn len(&self) -> usize {
self.components.len()
}
pub fn is_empty(&self) -> bool {
self.components.is_empty()
}
pub fn name(&self) -> Option<&str> {
self.components.last().map(String::as_str)
}
pub fn parent(&self) -> Option<Self> {
self.components.split_last().map(|(_, parent)| Self {
components: parent.to_vec(),
})
}
pub fn join(&self, component: impl Into<String>) -> Self {
let mut path = self.clone();
path.components.push(component.into());
path
}
pub fn to_verilog(&self) -> std::result::Result<String, PathFormatError> {
let mut output = String::new();
for component in &self.components {
if component.is_empty() || !component.bytes().all(|b| (33..=126).contains(&b)) {
return Err(PathFormatError::NotRepresentable {
component: component.clone(),
});
}
if !output.is_empty() {
output.push('.');
}
output.push('\\');
output.push_str(component);
output.push(' ');
}
Ok(output)
}
}
impl FromStr for HierarchyPath {
type Err = PathError;
fn from_str(text: &str) -> std::result::Result<Self, Self::Err> {
Self::parse(text)
}
}
impl fmt::Display for HierarchyPath {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
for (index, component) in self.components.iter().enumerate() {
if index != 0 {
formatter.write_str(".")?;
}
if component.is_empty()
|| component.chars().any(|c| {
c.is_whitespace() || c.is_control() || matches!(c, '.' | '[' | ']' | '"' | '\\')
})
{
formatter.write_str(&serde_json::to_string(component).map_err(|_| fmt::Error)?)?;
} else {
formatter.write_str(component)?;
}
}
Ok(())
}
}
#[derive(Clone)]
pub struct Hierarchy {
source: u64,
data: Arc<HierarchyData>,
}
pub(crate) struct ScopeData {
pub(crate) name: String,
pub(crate) name_was_escaped: bool,
pub(crate) parent: Option<usize>,
pub(crate) kind: String,
pub(crate) definition_name: Option<String>,
pub(crate) packing: Option<Packing>,
pub(crate) is_hidden: bool,
}
pub(crate) struct VariableData {
pub(crate) name: String,
pub(crate) reader_name: Option<String>,
pub(crate) name_was_escaped: bool,
pub(crate) parent: Option<usize>,
pub(crate) kind: String,
pub(crate) direction: Direction,
pub(crate) range: Option<BitRange>,
pub(crate) is_constant: bool,
pub(crate) type_name: Option<String>,
pub(crate) signedness: Option<Signedness>,
pub(crate) logic_domain: Option<LogicDomain>,
pub(crate) enumeration: Option<EnumerationData>,
pub(crate) signal: Option<usize>,
}
pub(crate) struct EnumerationData {
pub(crate) name: Option<String>,
variants: Vec<(String, String)>,
}
impl EnumerationData {
pub(crate) fn for_encoding(
name: Option<String>,
mut variants: Vec<(String, String)>,
encoding: Encoding,
) -> Option<Self> {
let Encoding::Bits { width } = encoding else {
return None;
};
if variants.is_empty()
|| !variants.iter().all(|(key, _)| {
crate::BitsRef::from_ascii(key.as_bytes()).is_some_and(|bits| bits.width() == width)
})
{
return None;
}
for (key, _) in &mut variants {
key.make_ascii_lowercase();
}
Some(Self { name, variants })
}
}
struct HierarchyData {
scopes: Vec<ScopeData>,
variables: Vec<VariableData>,
encodings: Vec<Encoding>,
children: OnceLock<ChildLinks>,
declarations_by_name: OnceLock<NameIndex>,
}
struct NameIndex {
offsets: Vec<usize>,
declarations: Vec<usize>,
}
struct ChildLinks {
first: Vec<usize>,
next: Vec<usize>,
}
impl ChildLinks {
fn new(scopes: &[ScopeData], variables: &[VariableData]) -> Self {
let mut first = vec![usize::MAX; scopes.len()];
let mut next = vec![usize::MAX; scopes.len() + variables.len()];
for (index, variable) in variables.iter().enumerate().rev() {
if let Some(parent) = variable.parent {
let child = scopes.len() + index;
next[child] = std::mem::replace(&mut first[parent], child);
}
}
for (index, scope) in scopes.iter().enumerate().rev() {
if let Some(parent) = scope.parent {
next[index] = std::mem::replace(&mut first[parent], index);
}
}
Self { first, next }
}
}
fn vec_bytes<T>(capacity: usize) -> usize {
capacity.saturating_mul(std::mem::size_of::<T>())
}
static NEXT_SOURCE: AtomicU64 = AtomicU64::new(1);
fn next_source() -> u64 {
NEXT_SOURCE
.fetch_update(Ordering::Relaxed, Ordering::Relaxed, |id| id.checked_add(1))
.expect("hierarchy source IDs exhausted")
}
pub enum Item<'h> {
Scope(Scope<'h>),
Variable(Variable<'h>),
}
pub struct Scope<'h> {
hierarchy: &'h Hierarchy,
index: usize,
}
pub struct Variable<'h> {
hierarchy: &'h Hierarchy,
index: usize,
}
impl PartialEq<Scope<'_>> for Scope<'_> {
fn eq(&self, other: &Scope<'_>) -> bool {
self.hierarchy.source == other.hierarchy.source && self.index == other.index
}
}
impl Eq for Scope<'_> {}
impl PartialEq<Variable<'_>> for Variable<'_> {
fn eq(&self, other: &Variable<'_>) -> bool {
self.hierarchy.source == other.hierarchy.source && self.index == other.index
}
}
impl Eq for Variable<'_> {}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct Signal {
source: u64,
index: usize,
computed: bool,
base_encoding: Encoding,
encoding: Encoding,
lsb: u32,
}
impl Hierarchy {
pub(crate) fn new(
scopes: Vec<ScopeData>,
variables: Vec<VariableData>,
encodings: Vec<Encoding>,
) -> Self {
Self {
source: next_source(),
data: Arc::new(HierarchyData {
scopes,
variables,
encodings,
children: OnceLock::new(),
declarations_by_name: OnceLock::new(),
}),
}
}
pub(crate) fn validated_bytes(&self) -> usize {
let data = &self.data;
let scopes = data.scopes.len();
let variables = data.variables.len();
let mut bytes = std::mem::size_of::<HierarchyData>();
bytes = bytes.saturating_add(vec_bytes::<ScopeData>(data.scopes.capacity()));
for scope in &data.scopes {
bytes = bytes.saturating_add(scope.name.capacity());
bytes = bytes.saturating_add(scope.kind.capacity());
bytes = bytes.saturating_add(
scope
.definition_name
.as_ref()
.map_or(0, |name| name.capacity()),
);
}
bytes = bytes.saturating_add(vec_bytes::<VariableData>(data.variables.capacity()));
for variable in &data.variables {
bytes = bytes.saturating_add(variable.name.capacity());
bytes = bytes.saturating_add(variable.kind.capacity());
bytes = bytes.saturating_add(
variable
.reader_name
.as_ref()
.map_or(0, |name| name.capacity()),
);
bytes = bytes.saturating_add(
variable
.type_name
.as_ref()
.map_or(0, |name| name.capacity()),
);
if let Some(enumeration) = &variable.enumeration {
bytes = bytes.saturating_add(std::mem::size_of::<EnumerationData>());
bytes = bytes
.saturating_add(enumeration.name.as_ref().map_or(0, |name| name.capacity()));
bytes = bytes.saturating_add(vec_bytes::<(String, String)>(
enumeration.variants.capacity(),
));
for (key, label) in &enumeration.variants {
bytes = bytes.saturating_add(key.capacity());
bytes = bytes.saturating_add(label.capacity());
}
}
}
bytes = bytes.saturating_add(vec_bytes::<Encoding>(data.encodings.capacity()));
let child_entries = scopes.saturating_mul(2).saturating_add(variables);
let name_entries = scopes
.saturating_mul(2)
.saturating_add(variables)
.saturating_add(2);
let words = std::mem::size_of::<usize>();
bytes = bytes.saturating_add(child_entries.saturating_mul(words));
bytes = bytes.saturating_add(name_entries.saturating_mul(words));
bytes
}
pub(crate) fn reopened(&self) -> Self {
Self {
source: next_source(),
data: Arc::clone(&self.data),
}
}
pub(crate) fn signal_at(&self, index: usize) -> Signal {
let encoding = self.data.encodings[index];
Signal {
source: self.source,
index,
computed: false,
base_encoding: encoding,
encoding,
lsb: 0,
}
}
pub(crate) fn validate(&self, signal: Signal) -> Result<usize> {
let encoding = (!signal.computed)
.then(|| self.data.encodings.get(signal.index).copied())
.flatten();
self.validate_encoding(signal, encoding)
}
pub(crate) fn computed_signal(&self, index: usize, width: u32) -> Signal {
let encoding = Encoding::Bits { width };
Signal {
source: self.source,
index,
computed: true,
base_encoding: encoding,
encoding,
lsb: 0,
}
}
pub(crate) fn validate_encoding(
&self,
signal: Signal,
encoding: Option<Encoding>,
) -> Result<usize> {
let valid = signal.source == self.source
&& encoding == Some(signal.base_encoding)
&& match (signal.base_encoding, signal.encoding) {
(Encoding::Bits { width: base }, Encoding::Bits { width }) => {
(width > 0 || signal == signal.base())
&& signal.lsb.checked_add(width).is_some_and(|end| end <= base)
}
(base, current) => base == current && signal.lsb == 0,
};
if valid {
Ok(signal.index)
} else {
Err(crate::Error::InvalidSignal { signal })
}
}
fn children_of(&self, parent: usize) -> impl Iterator<Item = Item<'_>> + '_ {
let links = self
.data
.children
.get_or_init(|| ChildLinks::new(&self.data.scopes, &self.data.variables));
let scopes = self.data.scopes.len();
let mut next = links.first[parent];
std::iter::from_fn(move || {
let index = next;
if index == usize::MAX {
return None;
}
next = links.next[index];
Some(if index < scopes {
Item::Scope(Scope {
hierarchy: self,
index,
})
} else {
Item::Variable(Variable {
hierarchy: self,
index: index - scopes,
})
})
})
}
fn scope_path_at(&self, mut index: Option<usize>) -> HierarchyPath {
let mut components = Vec::new();
while let Some(current) = index {
let scope = &self.data.scopes[current];
components.push(scope.name.clone());
index = scope.parent;
}
components.reverse();
HierarchyPath { components }
}
pub fn roots(&self) -> impl Iterator<Item = Item<'_>> + '_ {
self.scopes()
.filter(|scope| scope.data().parent.is_none())
.map(Item::Scope)
.chain(
self.variables()
.filter(|variable| variable.data().parent.is_none())
.map(Item::Variable),
)
}
pub fn scopes(&self) -> impl Iterator<Item = Scope<'_>> + '_ {
(0..self.data.scopes.len()).map(|index| Scope {
hierarchy: self,
index,
})
}
pub fn variables(&self) -> impl Iterator<Item = Variable<'_>> + '_ {
(0..self.data.variables.len()).map(|index| Variable {
hierarchy: self,
index,
})
}
pub fn signals(&self) -> impl Iterator<Item = Signal> + '_ {
(0..self.data.encodings.len()).map(|index| self.signal_at(index))
}
pub fn scope(&self, text: &str) -> std::result::Result<Scope<'_>, LookupError> {
self.scope_path(&HierarchyPath::parse(text)?)
}
pub fn variable(&self, text: &str) -> std::result::Result<Variable<'_>, LookupError> {
self.variable_path(&HierarchyPath::parse(text)?)
}
pub fn signal(&self, selector: &str) -> std::result::Result<Signal, LookupError> {
let exact = HierarchyPath::parse(selector)
.map_err(LookupError::from)
.and_then(|path| self.signal_path(&path));
if !matches!(
&exact,
Err(LookupError::NotFound { .. } | LookupError::InvalidPath(_))
) {
return exact;
}
if let Some((path, msb, lsb)) = path::selector(selector)? {
return Ok(self.signal_path(&path)?.slice(msb, lsb)?);
}
exact
}
pub fn scope_path(&self, path: &HierarchyPath) -> std::result::Result<Scope<'_>, LookupError> {
let mut matches = self
.scopes()
.filter(|scope| Some(scope.name()) == path.name() && scope.path() == *path);
let first = matches.next();
match (first, matches.count()) {
(None, _) => Err(LookupError::NotFound { path: path.clone() }),
(Some(scope), 0) => Ok(scope),
(_, remaining) => Err(LookupError::Ambiguous {
path: path.clone(),
matches: remaining + 1,
}),
}
}
pub fn variable_path(
&self,
path: &HierarchyPath,
) -> std::result::Result<Variable<'_>, LookupError> {
let Some((name, scopes)) = path.components.split_last() else {
return Err(LookupError::NotFound { path: path.clone() });
};
let mut parent = None;
for name in scopes {
let mut candidates = self
.declarations_named(parent, name)
.iter()
.copied()
.filter(|index| *index < self.data.scopes.len());
let Some(first) = candidates.next() else {
return Err(LookupError::NotFound { path: path.clone() });
};
if candidates.next().is_some() {
return self.variable_path_frontier(path);
}
parent = Some(first);
}
let mut matches = self
.declarations_named(parent, name)
.iter()
.copied()
.filter_map(|index| index.checked_sub(self.data.scopes.len()))
.map(|index| Variable {
hierarchy: self,
index,
});
let first = matches.next();
match (first, matches.count()) {
(None, _) => Err(LookupError::NotFound { path: path.clone() }),
(Some(variable), 0) => Ok(variable),
(_, remaining) => Err(LookupError::Ambiguous {
path: path.clone(),
matches: remaining + 1,
}),
}
}
fn variable_path_frontier(
&self,
path: &HierarchyPath,
) -> std::result::Result<Variable<'_>, LookupError> {
let Some((name, scopes)) = path.components.split_last() else {
return Err(LookupError::NotFound { path: path.clone() });
};
let mut parents = vec![None];
for name in scopes {
parents = parents
.into_iter()
.flat_map(|parent| self.declarations_named(parent, name))
.copied()
.filter(|index| *index < self.data.scopes.len())
.map(Some)
.collect();
if parents.is_empty() {
return Err(LookupError::NotFound { path: path.clone() });
}
}
let mut matches = parents
.into_iter()
.flat_map(|parent| self.declarations_named(parent, name))
.filter_map(|index| index.checked_sub(self.data.scopes.len()))
.map(|index| Variable {
hierarchy: self,
index,
});
let first = matches.next();
match (first, matches.count()) {
(None, _) => Err(LookupError::NotFound { path: path.clone() }),
(Some(variable), 0) => Ok(variable),
(_, remaining) => Err(LookupError::Ambiguous {
path: path.clone(),
matches: remaining + 1,
}),
}
}
fn declaration_key(&self, index: usize) -> (Option<usize>, &str) {
if index < self.data.scopes.len() {
let scope = &self.data.scopes[index];
(scope.parent, &scope.name)
} else {
let variable = &self.data.variables[index - self.data.scopes.len()];
(variable.parent, &variable.name)
}
}
fn declarations_named(&self, parent: Option<usize>, name: &str) -> &[usize] {
let index = self.data.declarations_by_name.get_or_init(|| {
let root = self.data.scopes.len();
let count = root + self.data.variables.len();
let mut offsets = vec![0; root + 2];
for item in 0..count {
let parent = self.declaration_key(item).0.unwrap_or(root);
offsets[parent + 1] += 1;
}
for parent in 1..offsets.len() {
offsets[parent] += offsets[parent - 1];
}
let mut next = offsets[..offsets.len() - 1].to_vec();
let mut declarations = vec![0; count];
for item in 0..count {
let parent = self.declaration_key(item).0.unwrap_or(root);
declarations[next[parent]] = item;
next[parent] += 1;
}
for range in offsets.windows(2) {
declarations[range[0]..range[1]].sort_unstable_by(|a, b| {
self.declaration_key(*a).1.cmp(self.declaration_key(*b).1)
});
}
NameIndex {
offsets,
declarations,
}
});
let parent = parent.unwrap_or(self.data.scopes.len());
let index = &index.declarations[index.offsets[parent]..index.offsets[parent + 1]];
let start = index.partition_point(|item| self.declaration_key(*item).1 < name);
let count = index[start..].partition_point(|item| self.declaration_key(*item).1 == name);
&index[start..start + count]
}
pub fn signal_path(&self, path: &HierarchyPath) -> std::result::Result<Signal, LookupError> {
self.variable_path(path)?
.signal()
.ok_or_else(|| LookupError::NoSignal { path: path.clone() })
}
pub fn aliases(&self, signal: Signal) -> Result<impl Iterator<Item = Variable<'_>> + '_> {
if signal.computed {
self.validate_encoding(signal, Some(signal.base_encoding))?;
}
let index = if signal.computed {
None
} else {
Some(self.validate(signal)?)
};
Ok(self
.variables()
.filter(move |variable| index.is_some() && variable.data().signal == index))
}
}
impl<'h> Scope<'h> {
fn data(&self) -> &'h ScopeData {
&self.hierarchy.data.scopes[self.index]
}
pub fn name(&self) -> &'h str {
&self.data().name
}
pub fn path(&self) -> HierarchyPath {
self.hierarchy.scope_path_at(Some(self.index))
}
pub fn parent(&self) -> Option<Scope<'h>> {
self.data().parent.map(|index| Scope {
hierarchy: self.hierarchy,
index,
})
}
pub fn children(&self) -> impl Iterator<Item = Item<'h>> + '_ {
self.hierarchy.children_of(self.index)
}
pub fn kind(&self) -> &'h str {
&self.data().kind
}
pub fn name_was_escaped(&self) -> bool {
self.data().name_was_escaped
}
pub fn is_hidden(&self) -> bool {
self.data().is_hidden
}
pub fn definition_name(&self) -> Option<&'h str> {
self.data().definition_name.as_deref()
}
pub fn packing(&self) -> Option<Packing> {
self.data().packing
}
}
pub(crate) fn normalize_name(mut name: String) -> (String, bool) {
let escaped = name.starts_with('\\');
if escaped {
name.remove(0);
}
(name, escaped)
}
impl<'h> Variable<'h> {
fn data(&self) -> &'h VariableData {
&self.hierarchy.data.variables[self.index]
}
pub fn name(&self) -> &'h str {
&self.data().name
}
pub fn reader_name(&self) -> Option<&'h str> {
self.data().reader_name.as_deref()
}
pub fn name_was_escaped(&self) -> bool {
self.data().name_was_escaped
}
pub fn path(&self) -> HierarchyPath {
self.hierarchy
.scope_path_at(self.data().parent)
.join(self.name())
}
pub fn parent(&self) -> Option<Scope<'h>> {
self.data().parent.map(|index| Scope {
hierarchy: self.hierarchy,
index,
})
}
pub fn signal(&self) -> Option<Signal> {
self.data()
.signal
.map(|index| self.hierarchy.signal_at(index))
}
pub fn kind(&self) -> &'h str {
&self.data().kind
}
pub fn direction(&self) -> Direction {
self.data().direction
}
pub fn range(&self) -> Option<BitRange> {
self.data().range
}
pub fn is_constant(&self) -> bool {
self.data().is_constant
}
pub fn type_name(&self) -> Option<&'h str> {
self.data().type_name.as_deref()
}
pub fn signedness(&self) -> Option<Signedness> {
self.data().signedness
}
pub fn logic_domain(&self) -> Option<LogicDomain> {
self.data().logic_domain
}
pub fn enumeration(&self) -> Option<Enumeration<'h>> {
self.data()
.enumeration
.as_ref()
.map(|data| Enumeration { data })
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum Signedness {
Signed,
Unsigned,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum LogicDomain {
TwoState,
FourState,
NineState,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum Direction {
Unknown,
Implicit,
Input,
Output,
InOut,
Buffer,
Linkage,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum Packing {
Packed,
Unpacked,
Sparse,
TaggedPacked,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct BitRange {
msb: i64,
lsb: i64,
}
impl BitRange {
pub const fn new(msb: i64, lsb: i64) -> Self {
Self { msb, lsb }
}
pub const fn msb(self) -> i64 {
self.msb
}
pub const fn lsb(self) -> i64 {
self.lsb
}
pub const fn width(self) -> u64 {
match self.msb.abs_diff(self.lsb).checked_add(1) {
Some(width) => width,
None => panic!("range width exceeds u64"),
}
}
pub fn slice(
self,
signal: Signal,
msb: i64,
lsb: i64,
) -> std::result::Result<Signal, SliceError> {
let width = signal.width().ok_or(SliceError::NotBits)?;
if i128::from(self.msb).abs_diff(i128::from(self.lsb)) + 1 != u128::from(width) {
return Err(SliceError::HdlRangeWidthMismatch { range: self, width });
}
let low = self.msb.min(self.lsb);
let high = self.msb.max(self.lsb);
if !(low..=high).contains(&msb) || !(low..=high).contains(&lsb) {
return Err(SliceError::HdlOutOfBounds {
range: self,
msb,
lsb,
});
}
let position = |index: i64| index.abs_diff(self.lsb) as u32;
let (left, right) = (position(msb), position(lsb));
if left < right {
return Err(SliceError::HdlDirectionMismatch {
range: self,
msb,
lsb,
});
}
signal.slice(left, right)
}
}
pub struct Enumeration<'h> {
data: &'h EnumerationData,
}
impl<'h> Enumeration<'h> {
pub fn name(&self) -> Option<&'h str> {
self.data.name.as_deref()
}
pub fn variants(&self) -> impl Iterator<Item = EnumerationVariant<'h>> + '_ {
self.data
.variants
.iter()
.map(|(encoded, label)| EnumerationVariant {
encoded: crate::BitsRef::from_validated_ascii(encoded.as_bytes()),
label,
})
}
}
pub struct EnumerationVariant<'h> {
pub encoded: crate::BitsRef<'h>,
pub label: &'h str,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub enum Encoding {
Bits {
width: u32,
},
Real,
String,
Event,
Unsupported,
}
impl Signal {
pub(crate) fn is_computed(self) -> bool {
self.computed
}
pub(crate) fn index(self) -> usize {
self.index
}
pub(crate) fn lsb(self) -> u32 {
self.lsb
}
pub fn encoding(self) -> Encoding {
self.encoding
}
pub fn width(self) -> Option<u32> {
match self.encoding {
Encoding::Bits { width } => Some(width),
_ => None,
}
}
pub fn slice(self, msb: u32, lsb: u32) -> std::result::Result<Self, SliceError> {
let width = self.width().ok_or(SliceError::NotBits)?;
if msb < lsb {
return Err(SliceError::InvalidRange { msb, lsb });
}
if msb >= width {
return Err(SliceError::OutOfBounds { width, msb, lsb });
}
Ok(Self {
encoding: Encoding::Bits {
width: msb - lsb + 1,
},
lsb: self.lsb + lsb,
..self
})
}
pub fn base(self) -> Self {
Self {
encoding: self.base_encoding,
lsb: 0,
..self
}
}
pub fn is_slice(self) -> bool {
self != self.base()
}
}