use std::ops::Range;
use indexmap::IndexSet;
#[derive(Debug)]
pub struct ScopeIndex {
names: IndexSet<String>,
ranges: Vec<(u32, u32)>,
}
impl ScopeIndex {
#[tracing::instrument(level = "trace", name = "ScopeIndex::new", skip_all)]
pub fn new(mut scopes: Vec<(Range<u32>, Option<String>)>) -> Result<Self, ScopeIndexError> {
let mut names = IndexSet::new();
let mut ranges = vec![];
scopes.sort_by_key(|s| s.0.start);
let needs_zero = scopes.first().map(|s| s.0.start != 0).unwrap_or(false);
if needs_zero {
ranges.push((0, GLOBAL_SCOPE_SENTINEL));
}
let mut stack: Vec<(Range<u32>, u32)> = vec![];
for (range, name) in scopes {
unwind_scope_stack(&mut ranges, &mut stack, range.clone())?;
let name_idx = match name {
Some(name) => names
.insert_full(name)
.0
.try_into()
.map_err(|_| ScopeIndexError(()))?,
None => ANONYMOUS_SCOPE_SENTINEL,
};
ranges.push((range.start, name_idx));
if let Some(last) = stack.last() {
if last.0.end == range.end {
stack.pop();
}
}
stack.push((range, name_idx));
}
while let Some(last) = stack.pop() {
let name_idx = stack
.last()
.map(|prev| prev.1)
.unwrap_or(GLOBAL_SCOPE_SENTINEL);
ranges.push((last.0.end, name_idx));
}
Ok(Self { names, ranges })
}
pub fn lookup(&self, offset: u32) -> ScopeLookupResult {
let range_idx = match self.ranges.binary_search_by_key(&offset, |r| r.0) {
Ok(idx) => idx,
Err(0) => 0, Err(idx) => idx - 1,
};
let name_idx = match self.ranges.get(range_idx) {
Some(r) => r.1,
None => return ScopeLookupResult::Unknown,
};
self.resolve_name(name_idx)
}
fn resolve_name(&self, name_idx: u32) -> ScopeLookupResult {
if name_idx == GLOBAL_SCOPE_SENTINEL {
ScopeLookupResult::Unknown
} else if name_idx == ANONYMOUS_SCOPE_SENTINEL {
ScopeLookupResult::AnonymousScope
} else {
match self.names.get_index(name_idx as usize) {
Some(name) => ScopeLookupResult::NamedScope(name.as_str()),
None => ScopeLookupResult::Unknown,
}
}
}
pub fn iter(&self) -> impl Iterator<Item = (u32, ScopeLookupResult)> {
self.ranges.iter().map(|r| (r.0, self.resolve_name(r.1)))
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum ScopeLookupResult<'data> {
NamedScope(&'data str),
AnonymousScope,
Unknown,
}
fn unwind_scope_stack(
ranges: &mut Vec<(u32, u32)>,
stack: &mut Vec<(Range<u32>, u32)>,
range: Range<u32>,
) -> Result<(), ScopeIndexError> {
while let Some(last) = stack.pop() {
if last.0.end <= range.start {
let name_idx = stack
.last()
.map(|prev| prev.1)
.unwrap_or(GLOBAL_SCOPE_SENTINEL);
ranges.push((last.0.end, name_idx));
} else if last.0.end < range.end {
return Err(ScopeIndexError(()));
} else {
stack.push(last);
return Ok(());
}
}
Ok(())
}
pub(crate) const GLOBAL_SCOPE_SENTINEL: u32 = u32::MAX;
pub(crate) const ANONYMOUS_SCOPE_SENTINEL: u32 = u32::MAX - 1;
#[derive(Debug)]
pub struct ScopeIndexError(());
impl std::error::Error for ScopeIndexError {}
impl std::fmt::Display for ScopeIndexError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str("source could not be converted to source context")
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn invalid_nesting() {
let scopes = vec![(0..10, None), (5..15, None)];
assert!(ScopeIndex::new(scopes).is_err());
}
#[test]
fn scope_index() {
let scopes = vec![
(5..25, Some(String::from("parent"))),
(10..15, Some(String::from("child"))),
(20..25, Some(String::from("child2"))),
(30..50, None),
];
let idx = ScopeIndex::new(scopes).unwrap();
assert_eq!(idx.lookup(3), ScopeLookupResult::Unknown);
assert_eq!(idx.lookup(7), ScopeLookupResult::NamedScope("parent"));
assert_eq!(idx.lookup(12), ScopeLookupResult::NamedScope("child"));
assert_eq!(idx.lookup(17), ScopeLookupResult::NamedScope("parent"));
assert_eq!(idx.lookup(22), ScopeLookupResult::NamedScope("child2"));
assert_eq!(idx.lookup(25), ScopeLookupResult::Unknown);
assert_eq!(idx.lookup(30), ScopeLookupResult::AnonymousScope);
assert_eq!(idx.lookup(50), ScopeLookupResult::Unknown);
}
}