use hashbrown::HashTable;
use rayon::prelude::*;
use super::{
NameRef, SHARDS, Symbol, SymbolId, SymbolKind, SymbolTable, merge_symbol,
name_hash, shard_of,
};
use crate::{
elf::constants::STV_DEFAULT,
error::{Error, Result},
input::InputSymbol,
};
type Pos = u64;
const fn pos(file: usize, index: u32) -> Pos {
((file as u64) << 32) | index as u64
}
#[allow(clippy::cast_possible_truncation)]
const fn index_of(at: Pos) -> u32 {
at as u32
}
struct Shard<'a> {
index: HashTable<SymbolId>,
names: Vec<&'a [u8]>,
syms: Vec<Symbol>,
first: Vec<Pos>,
file_start: Vec<u32>,
slots: Vec<Vec<u32>>,
global: Vec<SymbolId>,
merge_error: Option<(Pos, Error)>,
}
type Bins = [Vec<(u32, u32)>];
pub(super) fn intern_all<'data>(
table: &mut SymbolTable<'data>,
files: &[Vec<InputSymbol<'data>>],
bins: &Bins,
) -> Result<Vec<Vec<Option<SymbolId>>>> {
debug_assert!(table.is_empty(), "bulk fold starts from an empty table");
let mut shards = build_shards(files, bins)?;
if let Some(err) = earliest_merge_error(&mut shards) {
return Err(err);
}
let order = assign_ids(&mut shards, files.len());
fill_table(table, &mut shards, &order);
Ok(fill_rows(files, bins, &shards))
}
pub(super) fn partition_file(
syms: &mut Vec<InputSymbol<'_>>,
) -> Vec<(u32, u32)> {
let mut counts = vec![0usize; SHARDS];
for sym in syms.iter() {
if let Some(c) = counts.get_mut(shard_of(sym.name_hash)) {
*c = c.saturating_add(1);
}
}
let mut buckets: Vec<Vec<InputSymbol<'_>>> =
counts.iter().map(|&n| Vec::with_capacity(n)).collect();
for sym in syms.iter() {
if let Some(bucket) = buckets.get_mut(shard_of(sym.name_hash)) {
bucket.push(*sym);
}
}
let mut bounds = Vec::with_capacity(SHARDS);
syms.clear();
for bucket in buckets {
let start = u32::try_from(syms.len()).unwrap_or(u32::MAX);
syms.extend(bucket);
let end = u32::try_from(syms.len()).unwrap_or(u32::MAX);
bounds.push((start, end));
}
bounds
}
fn run<'a, 'd>(
bins: &Bins,
syms: &'a [InputSymbol<'d>],
file: usize,
shard: usize,
) -> &'a [InputSymbol<'d>] {
let Some(&(lo, hi)) = bins.get(file).and_then(|b| b.get(shard)) else {
return &[];
};
syms.get(lo as usize..hi as usize).unwrap_or_default()
}
fn build_shards<'data>(
files: &[Vec<InputSymbol<'data>>],
bins: &Bins,
) -> Result<Vec<Shard<'data>>> {
(0..SHARDS)
.into_par_iter()
.map(|s| {
let expect: usize = bins
.iter()
.filter_map(|b| b.get(s))
.map(|&(lo, hi)| (hi.saturating_sub(lo)) as usize)
.sum();
let mut shard = Shard {
index: HashTable::with_capacity(expect),
names: Vec::with_capacity(expect),
syms: Vec::with_capacity(expect),
first: Vec::with_capacity(expect),
file_start: Vec::with_capacity(files.len().saturating_add(1)),
slots: vec![Vec::new(); files.len()],
global: Vec::new(),
merge_error: None,
};
for (file, syms) in files.iter().enumerate() {
shard
.file_start
.push(u32::try_from(shard.first.len()).unwrap_or(u32::MAX));
let run = run(bins, syms, file, s);
let mut slots = Vec::with_capacity(run.len());
for inc in run {
slots.push(shard.absorb(inc, file)?);
}
if let Some(row) = shard.slots.get_mut(file) {
*row = slots;
}
}
shard
.file_start
.push(u32::try_from(shard.first.len()).unwrap_or(u32::MAX));
Ok(shard)
})
.collect()
}
impl<'a> Shard<'a> {
fn absorb(&mut self, inc: &InputSymbol<'a>, file: usize) -> Result<u32> {
let index = inc.sym_idx;
let hash = inc.name_hash;
let names = &self.names;
if let Some(&slot) = self
.index
.find(hash, |&s| names.get(s.0).copied() == Some(inc.name))
{
let sym = self
.syms
.get_mut(slot.0)
.ok_or(Error::OutOfRange("symbol shard slot"))?;
if let Err(err) = merge_symbol(sym, inc, file) {
self.record_merge_error(pos(file, index), err);
}
return u32::try_from(slot.0)
.map_err(|_| Error::OutOfRange("symbol shard slot"));
}
let slot = self.names.len();
self.names.push(inc.name);
self.syms.push(Symbol::from_input(inc, file));
self.first.push(pos(file, index));
let names = &self.names;
self.index.insert_unique(hash, SymbolId(slot), |&s| {
names.get(s.0).copied().map_or(0, name_hash)
});
u32::try_from(slot).map_err(|_| Error::OutOfRange("symbol shard slot"))
}
fn record_merge_error(&mut self, at: Pos, err: Error) {
if self.merge_error.as_ref().is_none_or(|(prev, _)| at < *prev) {
self.merge_error = Some((at, err));
}
}
}
fn earliest_merge_error(shards: &mut [Shard<'_>]) -> Option<Error> {
shards
.iter_mut()
.filter_map(|s| s.merge_error.take())
.min_by_key(|(at, _)| *at)
.map(|(_, err)| err)
}
fn assign_ids(shards: &mut [Shard<'_>], file_count: usize) -> Vec<(u32, u32)> {
let per_file: Vec<Vec<(u32, u32, u32)>> = (0..file_count)
.into_par_iter()
.map(|file| {
let mut names = Vec::new();
for (s, shard) in shards.iter().enumerate() {
let s = u32::try_from(s).unwrap_or(u32::MAX);
let lo = shard.file_start.get(file).copied().unwrap_or(0);
let hi = shard
.file_start
.get(file.saturating_add(1))
.copied()
.unwrap_or(lo);
for slot in lo..hi {
let at =
shard.first.get(slot as usize).copied().unwrap_or(0);
names.push((index_of(at), s, slot));
}
}
names.sort_unstable_by_key(|&(idx, _, _)| idx);
names
})
.collect();
let total: usize = per_file.iter().map(Vec::len).sum();
let mut order = Vec::with_capacity(total);
for shard in shards.iter_mut() {
shard.global = vec![SymbolId(0); shard.names.len()];
}
for names in &per_file {
for &(_, s, slot) in names {
let id = SymbolId(order.len());
if let Some(shard) = shards.get_mut(s as usize)
&& let Some(cell) = shard.global.get_mut(slot as usize)
{
*cell = id;
}
order.push((s, slot));
}
}
for shard in shards.iter_mut() {
let global = &shard.global;
for value in &mut shard.index {
if let Some(&id) = global.get(value.0) {
*value = id;
}
}
}
order
}
fn fill_table<'a>(
table: &mut SymbolTable<'a>,
shards: &mut [Shard<'a>],
order: &[(u32, u32)],
) {
table.names = order
.par_iter()
.map(|&(s, slot)| {
NameRef::Slice(
shards
.get(s as usize)
.and_then(|sh| sh.names.get(slot as usize))
.copied()
.unwrap_or_default(),
)
})
.collect();
table.symbols = order
.par_iter()
.map(|&(s, slot)| {
shards
.get(s as usize)
.and_then(|sh| sh.syms.get(slot as usize))
.cloned()
.unwrap_or(Symbol {
kind: SymbolKind::Undefined { weak: true },
visibility: STV_DEFAULT,
})
})
.collect();
for (dst, shard) in table.index.iter_mut().zip(shards.iter_mut()) {
*dst = std::mem::take(&mut shard.index);
}
}
fn fill_rows(
files: &[Vec<InputSymbol<'_>>],
bins: &Bins,
shards: &[Shard<'_>],
) -> Vec<Vec<Option<SymbolId>>> {
files
.par_iter()
.enumerate()
.map(|(file, syms)| {
let len = syms
.iter()
.map(|s| s.sym_idx as usize)
.max()
.map_or(0, |m| m.saturating_add(1));
let mut row = vec![None; len];
for (s, shard) in shards.iter().enumerate() {
let slots =
shard.slots.get(file).map_or(&[][..], Vec::as_slice);
for (sym, &slot) in run(bins, syms, file, s).iter().zip(slots) {
let Some(&id) = shard.global.get(slot as usize) else {
continue;
};
if let Some(cell) = row.get_mut(sym.sym_idx as usize) {
*cell = Some(id);
}
}
}
row
})
.collect()
}