use std::collections::{BTreeSet, HashMap, HashSet};
use crate::relaxng::grammar::{NameClass, Pattern};
use crate::relaxng::simplify::{CompiledSchema, name_class_matches};
const COMPATIBILITY_LIBRARY: &str = "http://relaxng.org/ns/compatibility/datatypes/1.0";
const XSD_LIBRARY: &str = "http://www.w3.org/2001/XMLSchema-datatypes";
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum IdType {
Id,
Idref,
Idrefs,
}
#[derive(Clone, Debug, Default)]
pub struct IdTypes {
attribute_names: HashSet<String>,
types: HashMap<(String, String, String, String), IdType>,
index: Nested<Nested<Nested<HashMap<String, IdType>>>>,
}
type Nested<T> = HashMap<String, T>;
impl IdTypes {
pub fn is_empty(&self) -> bool {
self.types.is_empty()
}
pub fn get(&self, element: (&str, &str), attribute: (&str, &str)) -> Option<IdType> {
self.index
.get(attribute.1)?
.get(attribute.0)?
.get(element.1)?
.get(element.0)
.copied()
}
pub(crate) fn analyze(schema: &CompiledSchema) -> Result<Self, String> {
let mut elements = Vec::new();
let mut visited = HashSet::new();
find_elements(&schema.start, schema, &mut visited, &mut elements)?;
for (name, pattern) in &schema.definitions {
if visited.insert(name.as_str()) {
find_elements(pattern, schema, &mut visited, &mut elements)?;
}
}
let mut analysed = Vec::new();
let mut cache = HashMap::new();
for (element_name, body) in elements {
let mut attributes = Vec::new();
for pattern in body {
collect_attributes(pattern, schema, &mut cache, &mut attributes)?;
}
let mut seen = HashSet::new();
attributes.retain(|attribute| seen.insert(std::ptr::from_ref(attribute.0)));
analysed.push((element_name, attributes));
}
let mut table = IdTypes::default();
for (element_name, attributes) in &analysed {
for &(attribute_name, id_type) in attributes {
let Some(id_type) = id_type else { continue };
let (Some(elements), Some(attribute_names)) =
(simple_names(element_name), simple_names(attribute_name))
else {
return Err(if simple_names(element_name).is_none() {
r#"an "element" pattern containing an "attribute" pattern with a non-null ID-type must have a name class that contains only "choice" and "name" elements"#.into()
} else {
r#"an "attribute" pattern with a non-null ID-type must have a name class that contains only "choice" and "name" elements"#.into()
});
};
for (element_ns, element_local) in &elements {
for (attribute_ns, attribute_local) in &attribute_names {
let key = (
element_ns.clone(),
element_local.clone(),
attribute_ns.clone(),
attribute_local.clone(),
);
match table.types.insert(key, id_type) {
Some(previous) if previous != id_type => {
return Err(conflict(attribute_local, element_local));
}
_ => {}
}
table.attribute_names.insert(attribute_local.clone());
}
}
}
}
let mut typed: ByAttribute<'_> = HashMap::new();
for (element_ns, element_local, attribute_ns, attribute_local) in table.types.keys() {
typed
.entry((Some(attribute_ns.clone()), attribute_local.clone()))
.or_default()
.push((Some(element_ns.clone()), element_local.as_str()));
}
for (element_name, attributes) in &analysed {
for &(attribute_name, id_type) in attributes {
if id_type.is_some() {
continue;
}
if let NameClass::Name { lexical, .. } = attribute_name
&& !table.attribute_names.contains(lexical)
{
continue;
}
let candidates: Vec<_> = match simple_names(attribute_name) {
Some(names) => names
.into_iter()
.filter_map(|(ns, local)| typed.get_key_value(&(Some(ns), local)))
.collect(),
None => typed
.iter()
.filter(|((ns, local), _)| name_class_matches(attribute_name, ns, local))
.collect(),
};
for ((_, attribute_local), elements) in candidates {
if let Some((_, element_local)) = elements
.iter()
.find(|(ns, local)| name_class_matches(element_name, ns, local))
{
return Err(conflict(attribute_local, element_local));
}
}
}
}
for ((element_ns, element_local, attribute_ns, attribute_local), &id_type) in &table.types {
table
.index
.entry(attribute_local.clone())
.or_default()
.entry(attribute_ns.clone())
.or_default()
.entry(element_local.clone())
.or_default()
.insert(element_ns.clone(), id_type);
}
Ok(table)
}
}
fn conflict(attribute: &str, element: &str) -> String {
format!(r#"conflicting ID-types for attribute "{attribute}" of element "{element}""#)
}
fn data_id_type(pattern: &Pattern) -> Option<IdType> {
let (datatype, library) = match pattern {
Pattern::Data {
datatype,
datatype_library,
..
} => (datatype.as_str(), datatype_library.as_deref()),
Pattern::Value {
datatype: Some(datatype),
datatype_library,
..
} => (datatype.as_str(), datatype_library.as_deref()),
_ => return None,
};
if !matches!(library, Some(COMPATIBILITY_LIBRARY | XSD_LIBRARY)) {
return None;
}
match datatype {
"ID" => Some(IdType::Id),
"IDREF" => Some(IdType::Idref),
"IDREFS" => Some(IdType::Idrefs),
_ => None,
}
}
fn find_elements<'s>(
pattern: &'s Pattern,
schema: &'s CompiledSchema,
visited: &mut HashSet<&'s str>,
out: &mut Vec<(&'s NameClass, &'s [Pattern])>,
) -> Result<(), String> {
match pattern {
Pattern::Element { name, body, .. } => {
out.push((name, body));
for child in body {
find_elements(child, schema, visited, out)?;
}
}
Pattern::Attribute { body, .. } => {
for child in body {
find_elements(child, schema, visited, out)?;
}
}
Pattern::Group(children)
| Pattern::Interleave(children)
| Pattern::Choice(children)
| Pattern::Optional(children)
| Pattern::ZeroOrMore(children)
| Pattern::OneOrMore(children)
| Pattern::List(children)
| Pattern::Mixed(children) => {
for child in children {
find_elements(child, schema, visited, out)?;
}
}
Pattern::Data { except, .. } => {
for child in except {
find_elements(child, schema, visited, out)?;
}
}
Pattern::Ref(name) | Pattern::ParentRef(name) => {
if let Some((name, target)) = schema.definitions.get_key_value(name)
&& visited.insert(name.as_str())
{
find_elements(target, schema, visited, out)?;
}
}
_ => {}
}
Ok(())
}
type ByAttribute<'s> = HashMap<(Option<String>, String), Vec<(Option<String>, &'s str)>>;
type Attribute<'s> = (&'s NameClass, Option<IdType>);
fn collect_attributes<'s>(
pattern: &'s Pattern,
schema: &'s CompiledSchema,
cache: &mut HashMap<&'s str, std::rc::Rc<Vec<Attribute<'s>>>>,
out: &mut Vec<Attribute<'s>>,
) -> Result<(), String> {
match pattern {
Pattern::Element { .. } => {}
Pattern::Attribute { name, body, .. } => {
let value = match body.as_slice() {
[only] => resolve(only, schema),
_ => None,
};
let id_type = value.and_then(data_id_type);
if id_type.is_none() {
for child in body {
reject_id_data(child, schema, &mut BTreeSet::new())?;
}
}
out.push((name, id_type));
}
Pattern::Group(children)
| Pattern::Interleave(children)
| Pattern::Choice(children)
| Pattern::Optional(children)
| Pattern::ZeroOrMore(children)
| Pattern::OneOrMore(children)
| Pattern::Mixed(children) => {
for child in children {
collect_attributes(child, schema, cache, out)?;
}
}
Pattern::List(_) | Pattern::Data { .. } | Pattern::Value { .. } => {
reject_id_data(pattern, schema, &mut BTreeSet::new())?;
}
Pattern::Ref(name) | Pattern::ParentRef(name) => {
if let Some((name, target)) = schema.definitions.get_key_value(name) {
if let Some(attributes) = cache.get(name.as_str()) {
out.extend(attributes.iter().copied());
} else {
let mut attributes = Vec::new();
collect_attributes(target, schema, cache, &mut attributes)?;
let mut seen = HashSet::new();
attributes.retain(|attribute| seen.insert(std::ptr::from_ref(attribute.0)));
out.extend(attributes.iter().copied());
cache.insert(name.as_str(), std::rc::Rc::new(attributes));
}
}
}
_ => {}
}
Ok(())
}
fn resolve<'s>(pattern: &'s Pattern, schema: &'s CompiledSchema) -> Option<&'s Pattern> {
let mut pattern = pattern;
for _ in 0..64 {
match pattern {
Pattern::Ref(name) | Pattern::ParentRef(name) => {
pattern = schema.definitions.get(name)?
}
Pattern::Group(children)
| Pattern::Interleave(children)
| Pattern::Choice(children)
if children.len() == 1 =>
{
pattern = &children[0];
}
_ => return Some(pattern),
}
}
None
}
fn reject_id_data(
pattern: &Pattern,
schema: &CompiledSchema,
seen: &mut BTreeSet<String>,
) -> Result<(), String> {
if data_id_type(pattern).is_some() {
return Err(r#"a "data" or "value" pattern with non-null ID-type must occur as the child of an "attribute" pattern"#.into());
}
match pattern {
Pattern::Group(children)
| Pattern::Interleave(children)
| Pattern::Choice(children)
| Pattern::Optional(children)
| Pattern::ZeroOrMore(children)
| Pattern::OneOrMore(children)
| Pattern::List(children)
| Pattern::Mixed(children) => {
for child in children {
reject_id_data(child, schema, seen)?;
}
}
Pattern::Data { except, .. } => {
for child in except {
reject_id_data(child, schema, seen)?;
}
}
Pattern::Ref(name) | Pattern::ParentRef(name) => {
if seen.insert(name.clone())
&& let Some(target) = schema.definitions.get(name)
&& !matches!(target, Pattern::Element { .. })
{
reject_id_data(target, schema, seen)?;
}
}
_ => {}
}
Ok(())
}
fn simple_names(class: &NameClass) -> Option<Vec<(String, String)>> {
match class {
NameClass::Name {
lexical, namespace, ..
} => Some(vec![(
namespace.clone().unwrap_or_default(),
lexical.clone(),
)]),
NameClass::Choice(options) => {
let mut names = Vec::new();
for option in options {
names.extend(simple_names(option)?);
}
Some(names)
}
_ => None,
}
}