use std::collections::HashMap;
use std::sync::Arc;
use crate::limits::{Charge, Meter, MeteredVec, hash_table_cost};
use crate::typetree::{NodeId, Tree};
use crate::value::{Map, Parsed, Value};
use crate::walk::dict::steps;
use crate::walk::{OpenWork, STEP_WORK, WriteError};
fn name_work(name: &[u8]) -> u64 {
STEP_WORK.saturating_add(u64::try_from(name.len()).unwrap_or(u64::MAX))
}
pub(super) struct Lookup<'a> {
map: &'a Map,
native: bool,
keyed: bool,
found: MeteredVec<u32>,
cursor: usize,
by_name: Option<NameTable<'a>>,
}
const UNSET: u32 = u32::MAX;
impl<'a> Lookup<'a> {
pub(super) fn new(parsed: &'a Parsed, tree: &Tree, node: NodeId, map: &'a Map) -> Self {
let kids = tree.list().children(node);
let native = usize::try_from(map.list())
.ok()
.and_then(|i| parsed.lists().get(i))
.is_some_and(|l| triomphe::Arc::ptr_eq(l, tree.list()))
&& map
.entries()
.first()
.is_none_or(|(k, _)| kids.binary_search_by_key(&k.0, |c| c.0).is_ok());
let keyed = native && tree.info(node).is_some_and(|i| i.dup_names);
Self {
map,
native,
keyed,
found: MeteredVec::new(parsed.charge().meter()),
cursor: 0,
by_name: None,
}
}
pub(super) fn get(
&mut self,
parsed: &'a Parsed,
tree: &Tree,
child: NodeId,
kept: Option<&mut KeptTables<'a>>,
work: &mut OpenWork<'_>,
) -> Result<Option<&'a Value>, WriteError> {
let entries = self.map.entries();
let name = tree.list().name(child);
steps(1);
if !self.native {
work.add(name_work(name)).map_err(WriteError::Limit)?;
}
let at_cursor = entries.get(self.cursor).is_some_and(|(k, _)| {
if self.native {
Some(*k) == tree.info(child).map(|i| i.key)
} else {
parsed.key_name(self.map, *k) == name
}
});
let slot = tree
.info(child)
.filter(|_| self.native)
.map(|i| i.slot as usize);
let known = slot
.and_then(|s| self.found.as_slice().get(s).copied())
.filter(|p| *p != UNSET)
.map(|p| p as usize);
let pos = match (known, at_cursor) {
(Some(p), _) => Some(p),
(None, true) => Some(self.cursor),
(None, false) => {
if let Some(k) = kept {
k.position(parsed, self.map, name, work)?
} else {
if self.by_name.is_none() {
self.by_name = Some(NameTable::build(parsed, self.map, work)?);
}
work.add(name_work(name)).map_err(WriteError::Limit)?;
self.by_name.as_ref().and_then(|t| t.position(name))
}
}
};
if let (Some(p), Some(s), true) = (pos, slot, self.keyed) {
let more = (s + 1).saturating_sub(self.found.len());
if more > 0 {
work.steps(more).map_err(WriteError::Limit)?;
steps(more);
self.found.reserve(more).map_err(WriteError::Charge)?;
for _ in 0..more {
self.found.push(UNSET).map_err(WriteError::Charge)?;
}
}
if let Some(f) = self.found.as_mut_slice().get_mut(s) {
*f = u32::try_from(p).unwrap_or(UNSET);
}
}
if let Some(p) = pos
&& p >= self.cursor
{
self.cursor = p + 1;
}
Ok(pos.and_then(|p| entries.get(p)).map(|(_, v)| v))
}
}
pub(super) struct NameTable<'a> {
first: HashMap<&'a [u8], u32>,
_charge: Charge,
}
impl<'a> NameTable<'a> {
pub(super) fn build(
parsed: &'a Parsed,
map: &'a Map,
work: &mut OpenWork<'_>,
) -> Result<Self, WriteError> {
let n = map.entries().len();
let charge = parsed
.charge()
.meter()
.charge(hash_table_cost(n, size_of::<(&[u8], u32)>()))
.map_err(WriteError::Charge)?;
let mut first = HashMap::with_capacity(n);
for (i, (name, _)) in parsed.entries(map).enumerate() {
steps(1);
work.add(name_work(name)).map_err(WriteError::Limit)?;
first
.entry(name)
.or_insert(u32::try_from(i).unwrap_or(UNSET));
}
Ok(Self {
first,
_charge: charge,
})
}
pub(super) fn position(&self, name: &[u8]) -> Option<usize> {
self.first
.get(name)
.filter(|p| **p != UNSET)
.map(|p| *p as usize)
}
}
pub(super) struct KeptTables<'a> {
tables: HashMap<usize, NameTable<'a>>,
charge: Charge,
}
impl<'a> KeptTables<'a> {
pub(super) fn new(meter: &Arc<Meter>) -> Self {
Self {
tables: HashMap::new(),
charge: Charge::zero(meter),
}
}
fn cost(n: usize) -> u64 {
if n == 0 {
return 0;
}
hash_table_cost(n, size_of::<(usize, NameTable<'_>)>())
}
pub(super) fn position(
&mut self,
parsed: &'a Parsed,
map: &'a Map,
name: &[u8],
work: &mut OpenWork<'_>,
) -> Result<Option<usize>, WriteError> {
work.add(name_work(name)).map_err(WriteError::Limit)?;
let key = std::ptr::from_ref(map).addr();
if let Some(t) = self.tables.get(&key) {
return Ok(t.position(name));
}
let n = self.tables.len();
let more = Self::cost(n + 1).saturating_sub(Self::cost(n));
self.charge.grow(more).map_err(WriteError::Charge)?;
let table = NameTable::build(parsed, map, work)?;
let pos = table.position(name);
self.tables.insert(key, table);
Ok(pos)
}
}