use std::collections::HashMap;
use std::hash::{BuildHasherDefault, Hash, Hasher};
use std::rc::Rc;
use crate::relaxng::grammar::Pattern;
pub(crate) type Definitions = std::collections::BTreeMap<String, Pattern>;
pub(crate) type FastMap<K, V> = HashMap<K, V, BuildHasherDefault<FastHasher>>;
#[derive(Clone, Copy, Default)]
pub(crate) struct FastHasher {
hash: u64,
}
impl FastHasher {
fn add(&mut self, word: u64) {
self.hash = (self.hash.rotate_left(5) ^ word).wrapping_mul(0x51_7c_c1_b7_27_22_0a_95);
}
}
impl Hasher for FastHasher {
fn write(&mut self, bytes: &[u8]) {
let mut chunks = bytes.chunks_exact(8);
for chunk in &mut chunks {
self.add(u64::from_le_bytes(chunk.try_into().expect("8 bytes")));
}
for &byte in chunks.remainder() {
self.add(u64::from(byte));
}
}
fn write_u8(&mut self, value: u8) {
self.add(u64::from(value));
}
fn write_u32(&mut self, value: u32) {
self.add(u64::from(value));
}
fn write_u64(&mut self, value: u64) {
self.add(value);
}
fn write_usize(&mut self, value: usize) {
self.add(value as u64);
}
fn finish(&self) -> u64 {
self.hash
}
}
#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub(crate) struct Id(u32);
impl Id {
pub(crate) fn index(self) -> usize {
self.0 as usize
}
}
pub(crate) const EMPTY: Id = Id(0);
pub(crate) const NOT_ALLOWED: Id = Id(1);
pub(crate) const TEXT: Id = Id(2);
#[derive(Clone, Copy, Debug)]
pub(crate) struct Leaf<'s>(pub(crate) &'s Pattern);
impl PartialEq for Leaf<'_> {
fn eq(&self, other: &Self) -> bool {
std::ptr::eq(self.0, other.0)
}
}
impl Eq for Leaf<'_> {}
impl Hash for Leaf<'_> {
fn hash<H: Hasher>(&self, state: &mut H) {
std::ptr::hash(self.0, state);
}
}
#[derive(Clone, Debug, Eq, Hash, PartialEq)]
pub(crate) enum Node<'s> {
Empty,
NotAllowed,
Text,
Element(Leaf<'s>),
Attribute(Leaf<'s>, Id),
Data(Leaf<'s>, Rc<[Id]>),
Value(Leaf<'s>),
List(Id),
Group(Rc<[Id]>),
Interleave(Rc<[Id]>),
Choice(Rc<[Id]>),
OneOrMore(Id),
}
pub(crate) struct PatternStore<'s> {
nodes: Vec<Node<'s>>,
ids: FastMap<Node<'s>, Id>,
interned: FastMap<*const Pattern, Id>,
element_contents: FastMap<Id, Id>,
definitions: &'s Definitions,
}
impl<'s> PatternStore<'s> {
pub(crate) fn new(definitions: &'s Definitions) -> Self {
let mut store = Self {
nodes: Vec::new(),
ids: FastMap::default(),
interned: FastMap::default(),
element_contents: FastMap::default(),
definitions,
};
for (node, id) in [
(Node::Empty, EMPTY),
(Node::NotAllowed, NOT_ALLOWED),
(Node::Text, TEXT),
] {
assert_eq!(store.make(node), id);
}
store
}
pub(crate) fn node(&self, id: Id) -> &Node<'s> {
&self.nodes[id.index()]
}
fn make(&mut self, node: Node<'s>) -> Id {
if let Some(&id) = self.ids.get(&node) {
return id;
}
let id = Id(u32::try_from(self.nodes.len()).expect("fewer than 2^32 patterns"));
self.nodes.push(node.clone());
self.ids.insert(node, id);
id
}
pub(crate) fn intern(&mut self, pattern: &'s Pattern) -> Id {
let key = pattern as *const Pattern;
if let Some(&id) = self.interned.get(&key) {
return id;
}
let node = match pattern {
Pattern::Empty => Node::Empty,
Pattern::NotAllowed => Node::NotAllowed,
Pattern::Text => Node::Text,
Pattern::Element { .. } => Node::Element(Leaf(pattern)),
Pattern::Attribute { body, .. } => {
Node::Attribute(Leaf(pattern), self.intern(&body[0]))
}
Pattern::Data { except, .. } => Node::Data(Leaf(pattern), self.intern_all(except)),
Pattern::Value { .. } => Node::Value(Leaf(pattern)),
Pattern::List(values) => Node::List(self.intern(&values[0])),
Pattern::Group(values) => Node::Group(self.intern_all(values)),
Pattern::Interleave(values) => Node::Interleave(self.intern_all(values)),
Pattern::Choice(values) => Node::Choice(self.intern_all(values)),
Pattern::OneOrMore(values) => Node::OneOrMore(self.intern(&values[0])),
Pattern::Ref(name) => {
let definitions = self.definitions;
let target = definitions
.get(name)
.expect("RELAX NG §4.18 guarantees every ref target exists");
let id = self.intern(target);
self.interned.insert(key, id);
return id;
}
Pattern::Optional(_)
| Pattern::ZeroOrMore(_)
| Pattern::Mixed(_)
| Pattern::ExternalRef { .. }
| Pattern::ParentRef(_)
| Pattern::Grammar(_) => {
unreachable!("resolved into other patterns by simplify_pattern")
}
};
let id = self.make(node);
self.interned.insert(key, id);
id
}
fn intern_all(&mut self, patterns: &'s [Pattern]) -> Rc<[Id]> {
patterns
.iter()
.map(|pattern| self.intern(pattern))
.collect()
}
pub(crate) fn element_content(&mut self, id: Id) -> Id {
if let Some(&content) = self.element_contents.get(&id) {
return content;
}
let Node::Element(Leaf(Pattern::Element { body, .. })) = self.node(id) else {
unreachable!("element_content called on an element node")
};
let content = self.intern(&body[0]);
self.element_contents.insert(id, content);
content
}
pub(crate) fn group(&mut self, values: Vec<Id>) -> Id {
self.sequence(values, Node::Group)
}
pub(crate) fn interleave(&mut self, values: Vec<Id>) -> Id {
self.sequence(values, Node::Interleave)
}
pub(crate) fn sequence(&mut self, mut values: Vec<Id>, wrap: fn(Rc<[Id]>) -> Node<'s>) -> Id {
if values.contains(&NOT_ALLOWED) {
return NOT_ALLOWED;
}
if values.len() > 1 {
values.retain(|&value| value != EMPTY);
}
match values.len() {
0 => EMPTY,
1 => values[0],
_ => self.make(wrap(values.into())),
}
}
pub(crate) fn choice(&mut self, values: Vec<Id>) -> Id {
let mut flat = Vec::with_capacity(values.len());
for value in values {
match self.node(value) {
Node::Choice(nested) => flat.extend(nested.iter().copied()),
_ => flat.push(value),
}
}
flat.retain(|&value| value != NOT_ALLOWED);
flat.sort_unstable();
flat.dedup();
match flat.len() {
0 => NOT_ALLOWED,
1 => flat[0],
_ => self.make(Node::Choice(flat.into())),
}
}
#[cfg(test)]
pub(crate) fn to_pattern(&self, id: Id) -> Pattern {
let all = |values: &[Id]| values.iter().map(|&value| self.to_pattern(value)).collect();
match self.node(id) {
Node::Empty => Pattern::Empty,
Node::NotAllowed => Pattern::NotAllowed,
Node::Text => Pattern::Text,
Node::Element(leaf)
| Node::Attribute(leaf, _)
| Node::Data(leaf, _)
| Node::Value(leaf) => leaf.0.clone(),
Node::List(inner) => Pattern::List(vec![self.to_pattern(*inner)]),
Node::Group(values) => Pattern::Group(all(values)),
Node::Interleave(values) => Pattern::Interleave(all(values)),
Node::Choice(values) => Pattern::Choice(all(values)),
Node::OneOrMore(inner) => Pattern::OneOrMore(vec![self.to_pattern(*inner)]),
}
}
}