use std::collections::{BTreeMap, HashMap, HashSet};
use std::ops::Bound;
use crate::summary::{DeclFact, MacroFact};
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub(crate) struct Posting {
pub file: u32,
pub reading: u32,
slot: u32,
}
impl Posting {
fn new(file: u32, reading: u32, index: usize) -> Self {
debug_assert!(
index < u32::MAX as usize,
"a file with four billion declarations"
);
Posting {
file,
reading,
slot: index as u32,
}
}
pub fn index(self) -> usize {
self.slot as usize
}
}
#[derive(Debug, Default)]
pub(super) struct NameIndex {
by_name: HashMap<Box<str>, Vec<Posting>>,
by_scope: HashMap<Box<str>, Vec<Posting>>,
definers: HashMap<Box<str>, Vec<u32>>,
sorted: BTreeMap<Box<str>, Vec<Box<str>>>,
}
impl NameIndex {
pub fn add_declarations(&mut self, file: u32, reading: u32, facts: &[DeclFact]) {
for (index, fact) in facts.iter().enumerate() {
let posting = Posting::new(file, reading, index);
if !fact.local {
self.add_name(&fact.name, posting);
}
if let Some(scope) = &fact.scope {
insert_sorted(&mut self.by_scope, scope, posting);
}
}
}
fn add_name(&mut self, name: &str, posting: Posting) {
let is_new = !self.by_name.contains_key(name);
insert_sorted(&mut self.by_name, name, posting);
if is_new {
self.sorted
.entry(lowercase(name).into_boxed_str())
.or_default()
.push(Box::from(name));
}
}
fn drop_name(&mut self, name: &str, file: u32, reading: u32) {
if !remove_range(&mut self.by_name, name, file, reading) {
return;
}
let lowered = lowercase(name);
if let Some(spellings) = self.sorted.get_mut(lowered.as_str()) {
spellings.retain(|spelling| &**spelling != name);
if spellings.is_empty() {
self.sorted.remove(lowered.as_str());
}
}
}
pub fn remove_declarations(&mut self, file: u32, reading: u32, facts: &[DeclFact]) {
let mut names: HashSet<&str> = HashSet::new();
let mut scopes: HashSet<&str> = HashSet::new();
for fact in facts {
if !fact.local {
names.insert(fact.name.as_str());
}
if let Some(scope) = &fact.scope {
scopes.insert(scope.as_str());
}
}
for name in names {
self.drop_name(name, file, reading);
}
for scope in scopes {
let _ = remove_range(&mut self.by_scope, scope, file, reading);
}
}
pub fn add_macros(&mut self, file: u32, macros: &[MacroFact]) {
for fact in macros.iter().filter(|fact| fact.kind.is_definition()) {
let files = match self.definers.get_mut(fact.name.as_str()) {
Some(files) => files,
None => self
.definers
.entry(Box::from(fact.name.as_str()))
.or_default(),
};
match files.binary_search(&file) {
Ok(_) => {}
Err(at) => files.insert(at, file),
}
}
}
pub fn remove_macros(&mut self, file: u32, macros: &[MacroFact]) {
for name in macros
.iter()
.filter(|fact| fact.kind.is_definition())
.map(|fact| fact.name.as_str())
.collect::<HashSet<_>>()
{
let Some(files) = self.definers.get_mut(name) else {
continue;
};
if let Ok(at) = files.binary_search(&file) {
files.remove(at);
}
if files.is_empty() {
self.definers.remove(name);
}
}
}
pub fn named(&self, name: &str) -> &[Posting] {
self.by_name.get(name).map(Vec::as_slice).unwrap_or(&[])
}
pub fn scoped(&self, scope: &str) -> &[Posting] {
self.by_scope.get(scope).map(Vec::as_slice).unwrap_or(&[])
}
pub fn definers_of(&self, name: &str) -> &[u32] {
self.definers.get(name).map(Vec::as_slice).unwrap_or(&[])
}
pub fn spellings_of(&self, lowered: &str) -> Option<&[Box<str>]> {
self.sorted.get(lowered).map(Vec::as_slice)
}
pub fn lowered_from<'a>(
&'a self,
lowered: &str,
) -> impl Iterator<Item = (&'a str, &'a [Box<str>])> + 'a {
self.sorted
.range::<str, _>((Bound::Included(lowered), Bound::Unbounded))
.map(|(key, spellings)| (&**key, spellings.as_slice()))
}
pub fn distinct_names(&self) -> usize {
self.by_name.len()
}
pub fn accounting(&self) -> NameIndexCost {
let postings = |map: &HashMap<Box<str>, Vec<Posting>>| {
let slots: usize = map.values().map(Vec::capacity).sum();
let keys: usize = map.keys().map(|key| key.len()).sum();
let entries = map.len();
let bytes = slots * std::mem::size_of::<Posting>()
+ keys
+ entries * std::mem::size_of::<Vec<Posting>>();
(entries, slots, bytes)
};
let (name_entries, name_postings, name_bytes) = postings(&self.by_name);
let (scope_entries, scope_postings, scope_bytes) = postings(&self.by_scope);
let definers: usize = self.definers.values().map(Vec::capacity).sum();
let definer_keys: usize = self.definers.keys().map(|key| key.len()).sum();
let definer_bytes = definers * std::mem::size_of::<u32>()
+ definer_keys
+ self.definers.len() * std::mem::size_of::<Vec<u32>>();
let spellings: Vec<&Box<str>> = self.sorted.values().flatten().collect();
let sorted_bytes = self.sorted.keys().map(|key| key.len()).sum::<usize>()
+ spellings
.iter()
.map(|spelling| spelling.len())
.sum::<usize>()
+ self.sorted.len() * std::mem::size_of::<Vec<Box<str>>>()
+ spellings.len() * std::mem::size_of::<Box<str>>();
NameIndexCost {
name_entries,
name_postings,
scope_entries,
scope_postings,
definer_entries: self.definers.len(),
definers,
spelling_entries: spellings.len(),
bytes: name_bytes + scope_bytes + definer_bytes + sorted_bytes,
}
}
}
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
pub struct NameIndexCost {
pub name_entries: usize,
pub name_postings: usize,
pub scope_entries: usize,
pub scope_postings: usize,
pub definer_entries: usize,
pub definers: usize,
pub spelling_entries: usize,
pub bytes: usize,
}
fn insert_sorted(map: &mut HashMap<Box<str>, Vec<Posting>>, key: &str, posting: Posting) {
let list = match map.get_mut(key) {
Some(list) => list,
None => map.entry(Box::from(key)).or_default(),
};
match list.last() {
Some(last) if *last >= posting => {
let at = list.partition_point(|held| *held < posting);
list.insert(at, posting);
}
_ => list.push(posting),
}
}
fn remove_range(
map: &mut HashMap<Box<str>, Vec<Posting>>,
key: &str,
file: u32,
reading: u32,
) -> bool {
let Some(list) = map.get_mut(key) else {
return false;
};
let start = list.partition_point(|held| held.file < file);
let end = start + list[start..].partition_point(|held| held.file == file);
let begin = start + list[start..end].partition_point(|held| held.reading < reading);
let finish = begin + list[begin..end].partition_point(|held| held.reading == reading);
list.drain(begin..finish);
if list.is_empty() {
map.remove(key);
return true;
}
false
}
pub(super) fn lowercase(text: &str) -> String {
if text.is_ascii() {
text.to_ascii_lowercase()
} else {
text.to_lowercase()
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::cache::SummaryKey;
use crate::index::summarize;
use std::path::Path;
fn facts_of(source: &str) -> Vec<DeclFact> {
summarize(Path::new("/p/a.h"), source, SummaryKey::new(0, 0)).declarations
}
fn held(index: &NameIndex, name: &str) -> Vec<(u32, u32)> {
index
.named(name)
.iter()
.map(|posting| (posting.file, posting.reading))
.collect()
}
#[test]
fn a_list_stays_in_file_order_whatever_order_files_arrive_in() {
let facts = facts_of("int x;\n");
let mut index = NameIndex::default();
index.add_declarations(3, 0, &facts);
index.add_declarations(1, 0, &facts);
index.add_declarations(2, 1, &facts);
index.add_declarations(2, 0, &facts);
assert_eq!(held(&index, "x"), vec![(1, 0), (2, 0), (2, 1), (3, 0)]);
}
#[test]
fn removing_one_reading_of_a_file_leaves_the_other() {
let facts = facts_of("namespace ns { int x; int y; }\n");
let mut index = NameIndex::default();
index.add_declarations(1, 0, &facts);
index.add_declarations(1, 1, &facts);
index.add_declarations(2, 0, &facts);
let scoped = index.scoped("ns").len();
assert_eq!(scoped, 6, "two facts in the scope, three readings");
index.remove_declarations(1, 1, &facts);
assert_eq!(held(&index, "x"), vec![(1, 0), (2, 0)]);
assert_eq!(index.scoped("ns").len(), 4);
index.remove_declarations(1, 0, &facts);
index.remove_declarations(2, 0, &facts);
assert!(index.named("x").is_empty());
assert!(index.scoped("ns").is_empty());
assert_eq!(
index.distinct_names(),
0,
"an emptied list is dropped, not kept as an empty entry"
);
}
#[test]
fn a_local_has_no_name_entry() {
let facts = facts_of("void f() { int inner; }\n");
assert!(
facts.iter().any(|fact| fact.name == "inner" && fact.local),
"the fixture has a local"
);
let mut index = NameIndex::default();
index.add_declarations(1, 0, &facts);
assert!(index.named("inner").is_empty());
assert_eq!(index.named("f").len(), 1);
}
#[test]
fn a_posting_points_at_the_slot_it_was_made_for() {
let facts = facts_of("int a;\nint b;\n");
let cooked = facts_of("int b;\n");
let mut index = NameIndex::default();
index.add_declarations(7, 0, &facts);
index.add_declarations(7, 1, &cooked);
let b = index.named("b");
assert_eq!((b[0].index(), b[0].reading), (1, 0));
assert_eq!((b[1].index(), b[1].reading), (0, 1));
}
#[test]
fn the_sorted_names_are_in_step_with_the_lists() {
let upper = facts_of("int Size;\n");
let lower = facts_of("int size;\n");
let mut index = NameIndex::default();
index.add_declarations(1, 0, &upper);
index.add_declarations(2, 0, &lower);
index.add_declarations(3, 0, &lower);
let spellings = |index: &NameIndex| -> Vec<String> {
index
.spellings_of("size")
.map(|held| held.iter().map(|spelling| spelling.to_string()).collect())
.unwrap_or_default()
};
assert_eq!(
spellings(&index).len(),
2,
"two spellings, one lowercase key: {:?}",
spellings(&index)
);
index.remove_declarations(2, 0, &lower);
assert_eq!(spellings(&index).len(), 2, "file 3 still declares `size`");
index.remove_declarations(3, 0, &lower);
assert_eq!(spellings(&index), vec!["Size".to_string()]);
index.remove_declarations(1, 0, &upper);
assert!(index.spellings_of("size").is_none());
assert_eq!(index.lowered_from("").count(), 0);
}
#[test]
fn a_walk_from_a_key_is_in_lowercase_order() {
let mut index = NameIndex::default();
for (file, source) in [
"int banana;\n",
"int Apple;\n",
"int cherry;\n",
"int apple2;\n",
]
.iter()
.enumerate()
{
index.add_declarations(file as u32, 0, &facts_of(source));
}
let keys: Vec<&str> = index.lowered_from("apple").map(|(key, _)| key).collect();
assert_eq!(keys, vec!["apple", "apple2", "banana", "cherry"]);
}
#[test]
fn the_definers_of_a_macro_are_the_files_that_define_it() {
let define = summarize(
Path::new("/p/a.h"),
"#define M 1\n#define M 2\n",
SummaryKey::new(0, 0),
);
let use_only = summarize(
Path::new("/p/b.h"),
"#ifdef M\n#endif\n",
SummaryKey::new(0, 0),
);
let mut index = NameIndex::default();
index.add_macros(5, &define.macros);
index.add_macros(2, &define.macros);
index.add_macros(9, &use_only.macros);
assert_eq!(
index.definers_of("M"),
&[2, 5],
"sorted, once per file, and a use is not a definition"
);
index.remove_macros(5, &define.macros);
assert_eq!(index.definers_of("M"), &[2]);
index.remove_macros(2, &define.macros);
assert!(index.definers_of("M").is_empty());
}
}