ucifer/

document.rs

/* Copyright © 2025 CZ.NIC z.s.p.o. (http://www.nic.cz/)
 *
 * This file is part of the ucifer library
 *
 * Ucifer is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free
 * Software Foundation, either version 3 of the License, or (at your option)
 * any later version.
 *
 * Ucifer is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * For more information, see /LICENSE.txt
 */

//! Represents model of the configuration in a structured manner.
//!
//! This model can be then used to perform lookup in.

pub mod export;
pub mod import;
pub mod option;

pub use option::ConfigOption;

use {
	crate::{document::export::DocumentExport, syntax::DirectiveIter},
	alloc::{
		boxed::Box,
		collections::{
			BTreeMap,
			btree_map::{Range, RangeMut},
		},
		string::String,
	},
	core::{
		any::type_name,
		fmt::{Debug, Display},
		hash::{BuildHasher, Hash},
		ops::Bound,
		str::FromStr,
	},
	derive_more::{Display, Error, From},
	hashbrown::{HashMap, HashTable, hash_map::EntryRef},
	import::Importer,
	lasso::{Rodeo, Spur},
};

/// A configuration file
///
/// This contains sections indexed by type and ordinal and map for the keys.
#[derive(Debug, Default)]
pub struct Document {
	/// Map of all sections
	sections: BTreeMap<SectionKey, SectionRecord>,
	/// Map of name to section key
	names: HashTable<(u64, SectionKey)>,
	/// Hash state for names
	hash_state: hashbrown::DefaultHashBuilder,
	/// Interned type names
	types: Rodeo,
}

impl PartialEq for Document {
	fn eq(&self, other: &Self) -> bool {
		// We compare only sections as other stuff is implementation detail
		self.sections == other.sections
	}
}

impl Document {
	/// Delete all entries in [`Document`], but keeping the allocations
	pub fn clear(&mut self) {
		self.sections.clear();
		self.names.clear();
		self.types.clear();
	}

	/// Insert a section, replacing the previous one if one with matching name
	/// existed
	///
	/// If no name is provided, new section is always allocated.
	///
	/// **TIP:** If you need to pass [`None`] as `name`, try `None::<&str>`.
	///
	/// ```
	/// # use ucifer::document::*;
	/// let mut doc = Document::default();
	/// doc.insert("foo", Some("bar"), Section::default());
	/// ```
	pub fn insert(
		&mut self,
		type_: &str,
		name: Option<impl AsRef<str> + Into<Box<str>>>,
		value: Section,
	) -> (SectionKey, Option<Section>) {
		let type_key = TypeSymbol(self.types.get_or_intern(type_));

		let maybe_conflicting_key = name
			.as_ref()
			.and_then(|name| self.section_key_of_name(name.as_ref()))
			.copied();

		let key = maybe_conflicting_key.unwrap_or_else(|| SectionKey {
			type_key,
			index: self.free_index(type_key),
		});

		let previous_section = match self.sections.entry(key) {
			alloc::collections::btree_map::Entry::Vacant(e) => {
				if let Some(name) = &name {
					let hash = self.hash_state.hash_one(name.as_ref());
					self.names.insert_unique(hash, (hash, key), |(h, _)| *h);
				}

				e.insert(SectionRecord {
					name: name.map(Into::into),
					section: value,
				});
				None
			}
			alloc::collections::btree_map::Entry::Occupied(e) => {
				Some(core::mem::replace(&mut e.into_mut().section, value))
			}
		};

		(key, previous_section)
	}

	/// Insert a section in the file of specific type, merging two sections of
	/// same type, if found.
	///
	/// # Errors
	/// When same-named section exists but type differs
	pub fn merge_or_insert(
		&mut self,
		type_: &str,
		name: Option<impl AsRef<str> + Into<Box<str>>>,
		value: Section,
	) -> Result<SectionKey, MergeTypeMismatch> {
		let maybe_key = name
			.as_ref()
			.and_then(|name| self.section_key_of_name(name.as_ref()));

		// First, let's check if there is already a section so we can merge them
		let Some(&key) = maybe_key else {
			let (key, _) = self.insert(type_, name, value);
			return Ok(key);
		};

		let type_key = TypeSymbol(self.types.get_or_intern(type_));
		if type_key != key.type_key {
			return Err(MergeTypeMismatch {
				stored: key.type_key,
				inserting: type_key,
			});
		}

		let stored = self.get_mut(&key).unwrap_or_else(|| {
			unreachable!(
				"state consistency violation: we got name to a section which doesn't exist"
			)
		});

		stored.merge(value);

		Ok(key)
	}

	/// Lookup all sections matching a type
	///
	/// If no sections of such type are found, returns empty iterator.
	///
	/// ```
	/// # use ucifer::document::*;
	/// let mut doc = Document::default();
	/// doc.insert("type", None::<&str>, Section::default());
	/// doc.insert("type", Some("named"), Section::default());
	///
	/// for (key, section) in doc.lookup_by_type("type") {
	///     // ...
	/// }
	/// ```
	pub fn lookup_by_type<'this>(&'this self, type_: &str) -> LookupRange<'this> {
		let Some(type_key) = self.type_key(type_) else {
			return LookupRange::default();
		};

		LookupRange {
			range: self.sections.range(lookup_range_by_type(type_key)),
		}
	}

	/// Lookup all sections matching a type and get mutable references to them
	///
	/// If no sections of such type are found, returns empty iterator.
	///
	/// Refer to [`Self::lookup_by_type`]
	///
	/// ```
	/// # use assert2::{assert, let_assert};
	/// # use ucifer::document::*;
	/// let mut doc = Document::default();
	/// doc.insert("type", None::<&str>, Section::default());
	/// doc.insert("type", Some("ほげら"), Section::default());
	///
	/// for (_key, section) in doc.lookup_by_type_mut("type") {
	///     section.insert("křeček", ConfigOption::from("karel"));
	/// }
	///
	/// # let_assert!(Some(section) = doc.lookup_by_type_name("type", "ほげら"));
	/// # assert!(section.get("křeček") == Some(&ConfigOption::from("karel")));
	/// ```
	pub fn lookup_by_type_mut<'this>(&'this mut self, type_: &str) -> LookupRangeMut<'this> {
		let Some(type_key) = self.type_key(type_) else {
			return LookupRangeMut::default();
		};

		LookupRangeMut {
			range: self.sections.range_mut(lookup_range_by_type(type_key)),
		}
	}

	/// Lookup a section by it's name
	///
	/// ```
	/// # use ucifer::document::*;
	/// let mut doc = Document::default();
	/// doc.insert("type", Some("name"), Section::default());
	///
	/// let lookup = doc.lookup_by_name("name");
	/// # assert2::assert!(lookup.is_some())
	/// ```
	#[must_use]
	pub fn lookup_by_name(&self, name: &str) -> Option<&Section> {
		self.get(self.section_key_of_name(name)?)
	}

	/// Lookup a section by it's name and get a mutable refernece to
	/// it
	///
	/// Refer to [`Self::lookup_by_name`]
	///
	/// ```
	/// # use ucifer::document::*;
	/// let mut doc = Document::default();
	/// let mut section = Section::default();
	/// section.insert("křeček", ConfigOption::from("karel"));
	/// doc.insert("type", Some("name"), section);
	///
	/// if let Some(section) = doc.lookup_by_name_mut("name") {
	///     # let removed =
	///     section.remove("křeček");
	///     # assert2::assert!(removed.is_some());
	/// }
	/// # else {
	/// #     panic!("expected section");
	/// # }
	/// ```
	pub fn lookup_by_name_mut(&mut self, name: &str) -> Option<&mut Section> {
		let &key = self.section_key_of_name(name)?;
		self.get_mut(&key)
	}

	/// Lookup a section by it's type *and* name
	///
	/// ```
	/// # use assert2::assert;
	/// # use ucifer::document::*;
	/// let mut doc = Document::default();
	/// doc.insert("kitty", Some("maria"), Section::default());
	/// doc.insert("box", Some("dynAny"), Section::default());
	///
	/// let lookup = doc.lookup_by_type_name("box", "maria");
	/// assert!(lookup.is_none());
	///
	/// let lookup = doc.lookup_by_type_name("kitty", "maria");
	/// assert!(lookup.is_some());
	/// ```
	#[must_use]
	pub fn lookup_by_type_name(&self, ty: &str, name: &str) -> Option<&Section> {
		let key = self.section_key_of_name(name)?;
		let type_key = self.type_key(ty)?;
		(key.type_key == type_key).then(|| self.get(key)).flatten()
	}

	/// Lookup a section by it's type *and* name and get mutable reference to it
	///
	/// Refer to [`Self::lookup_by_type_name`]
	/// ```
	/// # use ucifer::document::*;
	/// let mut doc = Document::default();
	/// let mut section = Section::default();
	/// section.insert("křeček", ConfigOption::from("karel"));
	/// doc.insert("type", Some("name"), section);
	///
	/// if let Some(section) = doc.lookup_by_type_name_mut("type", "name") {
	///     # let removed =
	///     section.remove("křeček");
	///     # assert2::assert!(removed.is_some());
	/// }
	/// # else {
	/// #     panic!("expected section");
	/// # }
	/// ```
	#[must_use]
	pub fn lookup_by_type_name_mut(&mut self, ty: &str, name: &str) -> Option<&mut Section> {
		let key = *self.section_key_of_name(name)?;
		let type_key = self.type_key(ty)?;
		(key.type_key == type_key)
			.then(|| self.get_mut(&key))
			.flatten()
	}

	/// Get reference to section by specified key
	///
	/// ```
	/// # use ucifer::document::*;
	/// # let mut document = Document::default();
	/// # document.insert("mlem", None::<&str>, Section::default());
	/// let lookup = document.lookup_by_type("mlem");
	/// for (key, section) in lookup {
	///     let got = document.get(key);
	///     assert_eq!(got, Some(section));
	/// }
	/// ```
	#[must_use]
	pub fn get(&self, key: &SectionKey) -> Option<&Section> {
		self.sections.get(key).map(|r| &r.section)
	}

	/// Get mutable reference to section by specified key
	///
	/// ```
	/// # use ucifer::document::*;
	/// # let mut document = Document::default();
	/// # document.insert("mlem", None::<&str>, Section::default());
	/// let mut lookup = document.lookup_by_type_mut("mlem");
	/// let (&key, _) = lookup.next().unwrap();
	/// document.get_mut(&key);
	/// ```
	#[must_use]
	pub fn get_mut(&mut self, key: &SectionKey) -> Option<&mut Section> {
		self.sections.get_mut(key).map(|r| &mut r.section)
	}

	/// Remove section by specified key, returning it
	///
	/// If it wasn't present, returns [`None`]
	///
	/// ```
	/// # use assert2::assert;
	/// # use ucifer::document::*;
	/// let mut document = Document::default();
	/// document.insert("mlem", Some("section"), Section::default());
	///
	/// let mut lookup = document.lookup_by_type("section");
	/// if let Some((&key, _)) = lookup.next() {
	///     document.remove(key);
	///     assert!(document.lookup_by_type("section").next().is_none());
	/// }
	///
	/// assert!(document.lookup_by_name("mlem").is_none());
	/// ```
	pub fn remove(&mut self, key: SectionKey) -> Option<Section> {
		let record = self.sections.remove(&key)?;

		if let Some(name) = record.name {
			let hash = self.hash_state.hash_one(&name[..]);
			let maybe_entry = self.names.find_entry(hash, |(got_hash, got_key)| {
				got_hash == &hash && got_key == &key
			});

			if let Ok(entry) = maybe_entry {
				entry.remove();
			}
		}

		Some(record.section)
	}

	/// Get name of a section by it's specified key
	#[must_use]
	pub fn section_name(&self, key: SectionKey) -> Option<&str> {
		self.sections.get(&key)?.name.as_deref()
	}

	/// Get section type key from the interner. Returns [`None`] if not found.
	#[must_use]
	pub fn type_key(&self, name: &str) -> Option<TypeSymbol> {
		self.types.get(name).map(TypeSymbol)
	}

	/// Get section type name by it's key
	#[must_use]
	pub fn type_name(&self, key: TypeSymbol) -> Option<&str> {
		self.types.try_resolve(&key.0)
	}

	/// Export entire document as iterator of directives
	pub fn export(&self) -> DocumentExport<'_> {
		DocumentExport::from_document(self)
	}

	/// Create importer to import directives to
	pub const fn importer(&mut self) -> Importer<'_> {
		Importer::new(self)
	}

	/// Last free index of type hash
	fn free_index(&self, type_key: TypeSymbol) -> usize {
		self.sections
			.range(lookup_range_by_type(type_key))
			.last()
			.map_or(0, |(key, _)| key.index + 1)
	}

	/// Find section key of name
	fn section_key_of_name(&self, name: &str) -> Option<&SectionKey> {
		let (hash, eq) = section_name_lookup(&self.hash_state, name, &self.sections);
		let (_, key) = self.names.find(hash, eq)?;

		Some(key)
	}
}

/// Convenience implementation for serializing document to it's string
/// representation
impl Display for Document {
	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
		self.export()
			.try_for_each(|directive| Display::fmt(&directive, f))
	}
}

/// Convenience implementation for reading entire document from string
impl FromStr for Document {
	type Err = FromStrError;

	fn from_str(s: &str) -> Result<Self, Self::Err> {
		let mut document = Self::default();
		let mut importer = document.importer();

		for result in DirectiveIter::new(s) {
			importer.import(result?)?;
		}

		Ok(document)
	}
}

/// Error returned by [`Document`] as [`FromStr`]
#[derive(Clone, Debug, Display, Error, From, PartialEq, Eq)]
pub enum FromStrError {
	/// Syntax Error
	///
	/// Document couldn't be parsed into directives
	Syntax(crate::syntax::ParseError),
	/// Import Error
	///
	/// Document is syntactically correct but directives are arranged in invalid
	/// way
	Import(import::ImportError),
}

/// There was a type mismatch when attempting to merge two sections
#[derive(Clone, Copy, Display, Debug, PartialEq, Eq, Error)]
#[display("merge type mismatch, stored: {stored:?} but we are inserting {inserting:?}")]
pub struct MergeTypeMismatch {
	/// Type of section present in the document
	pub stored: TypeSymbol,
	/// Type of section attempted to be inserted
	pub inserting: TypeSymbol,
}

/// Configuration section
///
/// Delimited by `config` in the doc.
#[derive(Debug, Default, PartialEq, Eq)]
pub struct Section {
	/// Configuration options
	options: HashMap<String, ConfigOption>,
}

impl Section {
	/// Get option / list reference in section by key
	#[inline]
	#[must_use]
	pub fn get(&self, key: &str) -> Option<&ConfigOption> {
		self.options.get(key)
	}

	/// Get option / list mutable reference in section by key
	#[inline]
	#[must_use]
	pub fn get_mut(&mut self, key: &str) -> Option<&mut ConfigOption> {
		self.options.get_mut(key)
	}

	/// Insert option / list into the section
	///
	/// If there was an option in the section with this key already present,
	/// inserts it in the option as list.
	pub fn insert(&mut self, key: &str, option: ConfigOption) {
		match self.options.entry_ref(key) {
			EntryRef::Occupied(entry) => {
				entry.replace_entry_with(|_, current| {
					Some(match (current, option) {
						(_, new @ ConfigOption::Scalar(_)) => new,
						(ConfigOption::Scalar(current), ConfigOption::List(mut items)) => {
							items.insert(0, current);
							ConfigOption::List(items)
						}
						(ConfigOption::List(mut current), ConfigOption::List(new)) => {
							current.extend_from_slice(&new);
							ConfigOption::List(current)
						}
					})
				});
			}
			EntryRef::Vacant(entry) => {
				entry.insert(option);
			}
		}
	}

	/// Merge from another section
	///
	/// Performs [`Self::insert`] on every entry
	pub fn merge(&mut self, other: Self) {
		for (key, value) in other.options {
			self.insert(&key, value);
		}
	}

	/// Remove entry from section
	///
	/// If it wasn't present, returns [`None`]
	pub fn remove(&mut self, key: &str) -> Option<ConfigOption> {
		self.options.remove(key)
	}

	/// Create borrowing iterator from section
	#[inline]
	#[must_use]
	pub fn iter(&self) -> <&Self as IntoIterator>::IntoIter {
		<&Self as IntoIterator>::into_iter(self)
	}
}

impl IntoIterator for Section {
	type Item = (String, ConfigOption);
	type IntoIter = hashbrown::hash_map::IntoIter<String, ConfigOption>;

	fn into_iter(self) -> Self::IntoIter {
		self.options.into_iter()
	}
}

impl<'a> IntoIterator for &'a Section {
	type Item = (&'a String, &'a ConfigOption);
	type IntoIter = hashbrown::hash_map::Iter<'a, String, ConfigOption>;

	fn into_iter(self) -> Self::IntoIter {
		self.options.iter()
	}
}

impl<K: AsRef<str>> Extend<(K, ConfigOption)> for Section {
	fn extend<T: IntoIterator<Item = (K, ConfigOption)>>(&mut self, iter: T) {
		for (key, value) in iter {
			self.insert(key.as_ref(), value);
		}
	}
}

/// Key to a section. As sections are stored in [`BTreeMap`] this contains a
/// hash of section type name and its index.
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct SectionKey {
	/// Section type key
	type_key: TypeSymbol,
	/// Section index unique for the type
	index: usize,
}

impl Debug for SectionKey {
	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
		f.debug_struct(type_name::<Self>())
			.field("type_key", &format_args!("{:#x?}", self.type_key))
			.field("index", &self.index)
			.finish()
	}
}

/// Section record in the map
///
/// As this may contain a name and we can get mutable references to sections
/// from the document, meddling with seciton's name will cause consistency
/// violation, so private type is made instead of putting name into [`Section`].
#[derive(Debug, Default, PartialEq, Eq)]
struct SectionRecord {
	/// Maybe name of the section
	name: Option<Box<str>>,
	/// Section itself
	section: Section,
}

/// Symbolized type
///
/// Can be resolved into name using [`Document::type_name`]
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[repr(transparent)]
pub struct TypeSymbol(Spur);

/// Iterator over document sub-range
#[derive(Debug, Default)]
#[must_use]
pub struct LookupRange<'doc> {
	/// Underlying range we map over
	range: Range<'doc, SectionKey, SectionRecord>,
}

impl<'doc> Iterator for LookupRange<'doc> {
	type Item = (&'doc SectionKey, &'doc Section);

	fn next(&mut self) -> Option<Self::Item> {
		let (key, value) = self.range.next()?;
		Some((key, &value.section))
	}
}

impl DoubleEndedIterator for LookupRange<'_> {
	fn next_back(&mut self) -> Option<Self::Item> {
		let (key, value) = self.range.next_back()?;
		Some((key, &value.section))
	}
}

/// Mutable iterator over document sub-range
#[derive(Debug, Default)]
#[must_use]
pub struct LookupRangeMut<'doc> {
	/// Underlying range we map over
	range: RangeMut<'doc, SectionKey, SectionRecord>,
}

impl<'doc> Iterator for LookupRangeMut<'doc> {
	type Item = (&'doc SectionKey, &'doc mut Section);

	fn next(&mut self) -> Option<Self::Item> {
		let (key, value) = self.range.next()?;
		Some((key, &mut value.section))
	}
}

impl DoubleEndedIterator for LookupRangeMut<'_> {
	fn next_back(&mut self) -> Option<Self::Item> {
		let (key, value) = self.range.next_back()?;
		Some((key, &mut value.section))
	}
}

/// Create a range for lookup of all entires of type
const fn lookup_range_by_type(type_key: TypeSymbol) -> (Bound<SectionKey>, Bound<SectionKey>) {
	let from = SectionKey { type_key, index: 0 };
	let to = SectionKey {
		type_key,
		index: usize::MAX,
	};

	(Bound::Included(from), Bound::Included(to))
}

/// Get all stuff necessary to look up things in name table
///
/// Returns hash and equivalence predicate
fn section_name_lookup(
	hash_state: &impl BuildHasher,
	name: &str,
	sections: &BTreeMap<SectionKey, SectionRecord>,
) -> (u64, impl Fn(&(u64, SectionKey)) -> bool) {
	let hash = hash_state.hash_one(name);
	let pred = move |(got_hash, key): &_| {
		let name_matches =
			|| sections.get(key).and_then(|record| record.name.as_deref()) == Some(name);

		*got_hash == hash && name_matches()
	};

	(hash, pred)
}

#[cfg(test)]
mod tests {
	use {
		super::*,
		crate::syntax::Directive,
		alloc::string::ToString,
		assert2::{assert, let_assert},
	};

	#[test]
	fn import_export() {
		let source = [
			Directive::Section {
				type_: "kitty".into(),
				name: Some("emily".into()),
			},
			Directive::Option {
				key: "foo".into(),
				value: Some("bar".into()),
			},
			Directive::Section {
				type_: "kitty".into(),
				name: None,
			},
			Directive::List {
				key: "list".into(),
				value: ":".into(),
			},
			Directive::List {
				key: "list".into(),
				value: "3".into(),
			},
		];

		let mut doc = Document::default();
		let mut importer = doc.importer();
		source
			.iter()
			.cloned()
			.try_for_each(|dir| importer.import(dir))
			.unwrap();

		let exported: alloc::vec::Vec<_> = doc.export().collect();
		assert!(exported == source);
	}

	#[test]
	fn document_reuse() {
		let mut doc = Document::default();
		let mut section = Section::default();
		section.insert("A", ConfigOption::from("value"));
		doc.insert("section", Some(":3"), section);

		let_assert!(Some(key) = doc.lookup_by_type_name("section", ":3"));
		assert!(key.get("A").is_some());

		doc.clear();
		assert!(doc.lookup_by_type_name("section", ":3").is_none());
	}

	#[test]
	fn parse_fmt() {
		let source = r#"
			config "A" "B"
				option "c" "d"
				list   "e" "f"
		"#;

		let document = Document::from_str(source).unwrap();
		let from_fmt = Document::from_str(&document.to_string()).unwrap();

		assert!(document == from_fmt);
	}
}