use core::convert::TryInto;
use core::hash::BuildHasher;
use core::iter::{FromIterator, FusedIterator, Zip};
use core::marker::PhantomData;
use core::mem::ManuallyDrop;
use core::ops::Range;
use core::slice;
use std::borrow::Cow;
use std::collections::hash_map::{HashMap, RandomState};
use std::ffi::OsStr;
use crate::internal::Interned;
use crate::{Symbol, SymbolOverflowError, DEFAULT_SYMBOL_TABLE_CAPACITY};
#[derive(Debug, Clone, Hash, PartialEq, Eq)]
#[cfg_attr(docsrs, doc(cfg(feature = "osstr")))]
pub struct AllSymbols<'a> {
range: Range<usize>,
phantom: PhantomData<&'a SymbolTable>,
}
impl<'a> Iterator for AllSymbols<'a> {
type Item = Symbol;
fn next(&mut self) -> Option<Self::Item> {
let next = self.range.next()?;
debug_assert!(u32::try_from(next).is_ok());
Some((next as u32).into())
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.range.size_hint()
}
fn count(self) -> usize {
self.range.count()
}
fn last(self) -> Option<Self::Item> {
let last = self.range.last()?;
debug_assert!(u32::try_from(last).is_ok());
Some((last as u32).into())
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
let nth = self.range.nth(n)?;
debug_assert!(u32::try_from(nth).is_ok());
Some((nth as u32).into())
}
fn collect<B: FromIterator<Self::Item>>(self) -> B {
self.range.map(|sym| Symbol::from(sym as u32)).collect()
}
}
impl<'a> DoubleEndedIterator for AllSymbols<'a> {
fn next_back(&mut self) -> Option<Self::Item> {
let next = self.range.next_back()?;
debug_assert!(u32::try_from(next).is_ok());
Some((next as u32).into())
}
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
let nth = self.range.nth_back(n)?;
debug_assert!(u32::try_from(nth).is_ok());
Some((nth as u32).into())
}
}
impl<'a> FusedIterator for AllSymbols<'a> {}
#[derive(Debug, Clone)]
#[cfg_attr(docsrs, doc(cfg(feature = "osstr")))]
pub struct OsStrings<'a>(slice::Iter<'a, Interned<OsStr>>);
impl<'a> Iterator for OsStrings<'a> {
type Item = &'a OsStr;
fn next(&mut self) -> Option<Self::Item> {
self.0.next().map(Interned::as_slice)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
fn count(self) -> usize {
self.0.count()
}
fn last(self) -> Option<Self::Item> {
self.0.last().map(Interned::as_slice)
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
self.0.nth(n).map(Interned::as_slice)
}
fn collect<B: FromIterator<Self::Item>>(self) -> B {
self.0.map(Interned::as_slice).collect()
}
}
impl<'a> DoubleEndedIterator for OsStrings<'a> {
fn next_back(&mut self) -> Option<Self::Item> {
self.0.next_back().map(Interned::as_slice)
}
fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
self.0.nth_back(n).map(Interned::as_slice)
}
fn rfold<B, F>(self, accum: B, f: F) -> B
where
F: FnMut(B, Self::Item) -> B,
{
self.0.map(Interned::as_slice).rfold(accum, f)
}
}
impl<'a> ExactSizeIterator for OsStrings<'a> {
fn len(&self) -> usize {
self.0.len()
}
}
impl<'a> FusedIterator for OsStrings<'a> {}
#[derive(Debug, Clone)]
#[cfg_attr(docsrs, doc(cfg(feature = "osstr")))]
pub struct Iter<'a>(Zip<AllSymbols<'a>, OsStrings<'a>>);
impl<'a> Iterator for Iter<'a> {
type Item = (Symbol, &'a OsStr);
fn next(&mut self) -> Option<Self::Item> {
self.0.next()
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
fn count(self) -> usize {
self.0.count()
}
fn last(self) -> Option<Self::Item> {
self.0.last()
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
self.0.nth(n)
}
fn collect<B: FromIterator<Self::Item>>(self) -> B {
self.0.collect()
}
}
impl<'a> FusedIterator for Iter<'a> {}
impl<'a> IntoIterator for &'a SymbolTable {
type Item = (Symbol, &'a OsStr);
type IntoIter = Iter<'a>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
#[derive(Default, Debug)]
#[cfg_attr(docsrs, doc(cfg(feature = "osstr")))]
pub struct SymbolTable<S = RandomState> {
map: ManuallyDrop<HashMap<&'static OsStr, Symbol, S>>,
vec: ManuallyDrop<Vec<Interned<OsStr>>>,
}
impl<S> Drop for SymbolTable<S> {
fn drop(&mut self) {
unsafe {
ManuallyDrop::drop(&mut self.map);
ManuallyDrop::drop(&mut self.vec);
}
}
}
impl SymbolTable<RandomState> {
#[must_use]
pub fn new() -> Self {
Self::with_capacity(DEFAULT_SYMBOL_TABLE_CAPACITY)
}
#[must_use]
pub fn with_capacity(capacity: usize) -> Self {
let capacity = capacity.next_power_of_two();
Self {
map: ManuallyDrop::new(HashMap::with_capacity(capacity)),
vec: ManuallyDrop::new(Vec::with_capacity(capacity)),
}
}
}
impl<S> SymbolTable<S> {
pub fn with_hasher(hash_builder: S) -> Self {
Self::with_capacity_and_hasher(DEFAULT_SYMBOL_TABLE_CAPACITY, hash_builder)
}
pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
Self {
map: ManuallyDrop::new(HashMap::with_capacity_and_hasher(capacity, hash_builder)),
vec: ManuallyDrop::new(Vec::with_capacity(capacity)),
}
}
pub fn capacity(&self) -> usize {
usize::min(self.vec.capacity(), self.map.capacity())
}
pub fn len(&self) -> usize {
self.vec.len()
}
pub fn is_empty(&self) -> bool {
self.vec.is_empty()
}
#[must_use]
pub fn contains(&self, id: Symbol) -> bool {
self.get(id).is_some()
}
#[must_use]
pub fn get(&self, id: Symbol) -> Option<&OsStr> {
let os_str = self.vec.get(usize::from(id))?;
Some(os_str.as_slice())
}
pub fn iter(&self) -> Iter<'_> {
Iter(self.all_symbols().zip(self.os_strings()))
}
pub fn all_symbols(&self) -> AllSymbols<'_> {
AllSymbols {
range: 0..self.len(),
phantom: PhantomData,
}
}
pub fn os_strings(&self) -> OsStrings<'_> {
OsStrings(self.vec.iter())
}
}
impl<S> SymbolTable<S>
where
S: BuildHasher,
{
pub fn intern<T>(&mut self, contents: T) -> Result<Symbol, SymbolOverflowError>
where
T: Into<Cow<'static, OsStr>>,
{
let contents = contents.into();
if let Some(&id) = self.map.get(&*contents) {
return Ok(id);
}
let name = Interned::from(contents);
let id = self.map.len().try_into()?;
let slice = unsafe { name.as_static_slice() };
self.map.insert(slice, id);
self.vec.push(name);
debug_assert_eq!(self.get(id), Some(slice));
debug_assert_eq!(self.intern(slice), Ok(id));
Ok(id)
}
#[must_use]
pub fn check_interned(&self, contents: &OsStr) -> Option<Symbol> {
self.map.get(contents).copied()
}
#[must_use]
pub fn is_interned(&self, contents: &OsStr) -> bool {
self.map.contains_key(contents)
}
pub fn reserve(&mut self, additional: usize) {
self.map.reserve(additional);
self.vec.reserve(additional);
}
pub fn shrink_to_fit(&mut self) {
self.map.shrink_to_fit();
self.vec.shrink_to_fit();
}
pub fn shrink_to(&mut self, min_capacity: usize) {
self.map.shrink_to(min_capacity);
self.vec.shrink_to(min_capacity);
}
}
#[cfg(test)]
#[allow(clippy::needless_pass_by_value)]
mod tests {
use std::ffi::{OsStr, OsString};
use quickcheck_macros::quickcheck;
use super::SymbolTable;
#[test]
fn alloc_drop_new() {
let table = SymbolTable::new();
drop(table);
}
#[test]
fn alloc_drop_with_capacity() {
let table = SymbolTable::with_capacity(1 << 14);
drop(table);
}
#[test]
fn drop_with_true_static_data() {
let mut table = SymbolTable::new();
table.intern(OsStr::new("1")).unwrap();
table.intern(OsStr::new("2")).unwrap();
table.intern(OsStr::new("3")).unwrap();
table.intern(OsStr::new("4")).unwrap();
table.intern(OsStr::new("5")).unwrap();
drop(table);
}
#[test]
fn drop_with_owned_data() {
let mut table = SymbolTable::new();
table.intern(OsString::from("1")).unwrap();
table.intern(OsString::from("2")).unwrap();
table.intern(OsString::from("3")).unwrap();
table.intern(OsString::from("4")).unwrap();
table.intern(OsString::from("5")).unwrap();
drop(table);
}
#[test]
fn set_owned_value_and_get_with_owned_and_borrowed() {
let mut table = SymbolTable::new();
let sym = table.intern(OsString::from("abc")).unwrap();
assert_eq!(OsStr::new("abc"), table.get(sym).unwrap());
assert_eq!(sym, table.intern(OsString::from("abc")).unwrap());
assert_eq!(sym, table.intern(OsStr::new("abc")).unwrap());
}
#[test]
fn set_borrowed_value_and_get_with_owned_and_borrowed() {
let mut table = SymbolTable::new();
let sym = table.intern(OsStr::new("abc")).unwrap();
assert_eq!(OsStr::new("abc"), table.get(sym).unwrap());
assert_eq!(sym, table.intern(OsString::from("abc")).unwrap());
assert_eq!(sym, table.intern(OsStr::new("abc")).unwrap());
}
#[quickcheck]
fn intern_twice_symbol_equality(os_string: OsString) -> bool {
let mut table = SymbolTable::new();
let sym = table.intern(os_string.clone()).unwrap();
let sym_again = table.intern(os_string).unwrap();
sym == sym_again
}
#[quickcheck]
fn intern_get_roundtrip(os_string: OsString) -> bool {
let mut table = SymbolTable::new();
let sym = table.intern(os_string.clone()).unwrap();
let retrieved_os_string = table.get(sym).unwrap();
&*os_string == retrieved_os_string
}
#[quickcheck]
fn table_contains_sym(os_string: OsString) -> bool {
let mut table = SymbolTable::new();
let sym = table.intern(os_string).unwrap();
table.contains(sym)
}
#[quickcheck]
fn table_does_not_contain_missing_symbol_ids(sym: u32) -> bool {
let table = SymbolTable::new();
!table.contains(sym.into())
}
#[quickcheck]
fn empty_table_does_not_report_any_interned_os_strings(os_string: OsString) -> bool {
let table = SymbolTable::new();
!table.is_interned(os_string.as_os_str())
}
#[quickcheck]
fn table_reports_interned_os_strs_as_interned(os_string: OsString) -> bool {
let mut table = SymbolTable::new();
table.intern(os_string.clone()).unwrap();
table.is_interned(os_string.as_os_str())
}
}