keytree/

lib.rs

//! # KeyTree
//! 
//! `KeyTree` is an elegant markup language designed to convert human readable information into Rust
//! data-structures. It is designed to be fast, to reduce cognitive load and to be easy to
//! implement for one's own types. It has no dependencies on other crates and so is fast to
//! compile. The format looks like
//! 
//! ```text
//! hobbit:
//!     name:           Frodo Baggins
//!     age:            60
//!     friends:
//!         hobbit:
//!             name:   Bilbo Baggins
//!             age:    111
//!         hobbit:
//!             name:   Samwise Gamgee
//!             age:    38
//! ```
//!
//! so data can be recursive. Also, it is easy to refer to a set of data using a path such as
//! `hobbit::friends::hobbit` refers to a collection of two hobbits.
//!
//! This library does not follow the standard Rust error handling pattern. If there is a parsing
//! error it will crash or if there is an error in converting a value into a Rust type it will
//! crash (with a nice error message). If you don't want this to happen, you will need to run this
//! in its own thread/process.
//! 
//! ## Data Format Rules
//! 
//! - Indentation has meaning and is 4 spaces, relative to the top key. Since indenting is
//!    relative to the top key, then you can neatly align strings embedded in code.
//! 
//! - Each line can be empty, have whitespace only, be a comment, be a key, or be a key/value
//!    pair.
//! 
//! - There are keys and values. Key/Value pairs look like
//! 
//! ```text
//! name: Frodo
//! ```
//! are used for `struct` fields and `enum` variants.
//! 
//! Keys refer to child keys or child key/value pairs indented on lines under it, for example
//! 
//! ```text
//! hobbit:
//!     name: Frodo
//! ```
//! hobbit refers to the name of the struct or enum. In this way, the data maps simply to Rust
//! data-structures.
//! 
//! - If a key has many children with the same key, it forms a collection, for example
//! 
//! ```test
//! hobbit:
//!     name: Frodo
//!     name: Bilbo
//! ```
//! is a collection of hobbits.
//! 
//! - Keys must not include but must be followed by a colon `:`.
//! 
//! - Values are all characters between the combination of ':' and whitespace and the end of the
//!    line. The value is trimmed of whitespace at both ends.
//! 
//! - Comments require `//` at the start of the line. For example
//! 
//! ```text
//! // comment
//! hobbit:
//!     name: Frodo
//! ```
//! 
//! ## Example
//! 
//! `Into` from `KeyTree` into Rust types is automatically implemented for `Vec<T>`, `Option<T>`
//! and basic Rust types. `KeyTree` text can be automatically converted to these data types, making
//! use of type inference. The `at()` function returns an iterator over `KeyTree` types that can be
//! used to implement `Into` for your own types. The following example should cover 90 percent of
//! use cases,
//! 
//! ```rust
//! use keytree::KeyTree;
//! use keytree::parser::KeyTreeBuilder;
//! 
//! #[derive(Debug)]
//! struct Hobbit {
//!     name:    String,
//!     age:     u32,
//!     friends: Vec<Hobbit>,
//!     nick:    Option<String>,
//! }
//! 
//! impl<'a> Into<Hobbit> for KeyTree<'a> {
//!     fn into(self) -> Hobbit {
//!         Hobbit {
//!             name:       self.at("hobbit::name"),
//!             age:        self.at("hobbit::age"),
//!             friends:    self.at("hobbit::friends::hobbit"),
//!             nick:       self.op("hobbit::nick"),
//!         }
//!     }
//! }
//! 
//! fn main() {
//!     let s = r#"
//!          hobbit:
//!              name:         Frodo Baggins
//!              age:          98
//!              friends:
//!                  hobbit:
//!                      name: Bilbo Baggins
//!                      age:  176
//!                  hobbit:
//!                      name: Samwise Gamgee
//!                      age:  66
//!                      nick: Sam"#;
//! 
//!     
//!     let core = KeyTreeBuilder::parse(s);
//!     let hobbit: Hobbit = KeyTree::from_core(&core).into();
//!     dbg!(&hobbit);
//! }
//! ```
//!
//! ## Details
//! 
//! We'll have a look in detail at what is happening in the example on the line
//! 
//! ```
//! friends:    self.at("hobbit::friends::hobbit"),
//! ```
//! 
//! In the `Into` trait impl, we want Bilbo Baggins and Samwise Gamgee to be Frodo's
//! friends. We specify their location in the `KeyTree` string using a path
//! `"hobbit::friends::hobbit"` which refers to two branches in the tree (two
//! hobbits). The `at()` function, unlike the the `op()` function, requires that the
//! branches exist. Rust infers that they need to be converted into the type `Vec<Hobbit>` as
//! specified in the `Hobbit` struct. The `Vec<T>` impl of `Into` is supplied by `KeyTree`. In fact
//! the `at()` function supplies an iterator over the Hobbits, which the `Vec<T>` impl uses.

pub mod error;
pub mod into;
pub mod parser;
pub mod path;

use error::KeyTreeErr;
use path::{UniquePath, NonUniquePath};
use std::collections::{BTreeMap, HashMap};
use std::collections::btree_map::Range;
use core::fmt;
use core::fmt::{Debug, Display};
use core::iter::Peekable;
use core::ops::Index;
use core::ops::Bound::Included;

#[derive(Clone, Copy, Debug)]
enum Token {
    Key(Key),
    Value(Value),
}

impl Token {
    // Returns the index of the start character of the key in the data string.
    fn start_key(&self) -> usize {
        match self {
            Token::Key(k)    => k.start_key,
            Token::Value(kv) => kv.start_key,
        }
    }
}

impl Display for Token {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Self::Key(k) => {
                write!(f, "({}, {})", k.start_key, k.end_key)
            },
            Self::Value(v) => {
                write!(f, "({}, {}):({}, {})", v.start_key, v.end_key, v.start_val, v.end_val)
            },
        }
    }
}

/// Line 1 is a Key Token. It refers to indented lines under it. Contains pointers into the data
/// string.
///
/// 1. hobbit:
/// 2.     name: Frodo Baggins
/// 3.     age:  98
///
#[derive(Clone, Copy, Debug)]
struct Key {
    start_key:  usize,
    end_key:    usize,
}

impl Key {
    fn new(sk: usize, ek: usize) -> Self {
        Key {
            start_key:  sk,
            end_key:    ek,
        }
    }
}


/// Line 2 and 3 are Value tokens. They each have a value. Contains pointers into the data string.
///
/// 1. hobbit:
/// 2.     name: Frodo Baggins
/// 3.     age:  98
///
#[derive(Clone, Copy, Debug)]
struct Value {
    start_key:  usize,
    end_key:    usize,
    start_val:  usize,
    end_val:    usize,
}

impl Value {
    fn new(sk: usize, ek: usize, sv: usize, ev: usize) -> Self {
        Value {
            start_key:  sk,
            end_key:    ek,
            start_val:  sv,
            end_val:    ev,
        }
    }
}

struct Tokens(Vec<Token>);

impl Tokens {
    fn new() -> Self {
        Tokens(Vec::new())
    }

    fn push(&mut self, token: Token) {
        self.0.push(token)
    }

    fn len(&self) -> usize {
        self.0.len()
    }
}

impl Index<usize> for Tokens {
    type Output = Token;

    fn index(&self, i: usize) -> &Self::Output {
        &(self.0)[i]
    }
}

impl fmt::Debug for Tokens {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut s = String::from("Tokens: ");
        for tok in &self.0 {
            s.push_str(&tok.to_string());
            s.push_str(", ");
        };
        s.pop();
        s.pop();
        write!(f, "{:?}", s)
    }
}

// TokenIndex holds indexes into a start and end position in a list of tokens.
//
#[derive(Clone, Copy)]
struct TokenIndex((usize, Option<usize>));

impl TokenIndex {

    // Create a token builder. The end index will be set later.
    fn new(start: usize) -> Self {
        TokenIndex((start, None))
    }

    fn start(&self) -> usize {
        (self.0).0
    }

    // Will fail if Option is None.
    fn end(&self) -> usize {
        (self.0).1.unwrap()
    }

    fn set_end(&mut self, i: usize) {
        (self.0).1 = Some(i);
    }
}

impl fmt::Display for TokenIndex {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match (self.0).1 {
            Some(_) => write!(f, "({}, {})", self.start(), self.end()),
            None    => write!(f, "({}, _)", self.start()),
        }
    }
}

impl fmt::Debug for TokenIndex{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.to_string())
    }
}

// While parsing, tracks the last ocurring path for each indent level. This is used for getting the
// index of the latest path, and for inserting end indices in TokenIndex when the contents of a
// key have been fully read.
//
#[derive(Debug)]
struct EachIndent(Vec<UniquePath>);

impl EachIndent {

    fn push(&mut self, path: &UniquePath) {
        self.0.push(path.clone())
    }

    fn new() -> Self {
        EachIndent(Vec::new())
    }

    // Used by parser to calculate the index of a newly parsed NonUniquePath.
    //
    fn new_index(&self, path: &UniquePath, indent: usize) -> usize {
        let max_indent = self.0.len() - 1;
        if indent <= max_indent && path.eq_base(&self.0[indent]) {
            self.0[indent].last_index() + 1
        } else {
            0
        }
    }

    fn insert(&mut self, path: &UniquePath, indent: usize) {
        if self.0.is_empty() {
            self.0.push(path.clone())
        } else if indent <= self.0.len() - 1 {
            self.0[indent] = path.clone();
        } else {
            self.0.push(path.clone())
        }
    }

    fn len(&self) -> usize {
        self.0.len()
    }
}

impl Index<usize> for EachIndent {
    type Output = UniquePath;

    fn index(&self, index: usize) -> &Self::Output {
        &self.0[index]
    }
}

struct KeyMap(BTreeMap<UniquePath, TokenIndex>);

impl KeyMap {
    fn new() -> Self {
        let bt: BTreeMap<UniquePath, TokenIndex> = BTreeMap::new();
        KeyMap(bt)
    }

    // That path is a borrow simply reflects stdlib <HashMap>.get().
    //
    fn get(&self, path: &UniquePath) -> Option<TokenIndex> {
        self.0.get(path).map(|tok_ix| *tok_ix)
    }

    fn set_end(&mut self, path: &UniquePath, end: usize) {
        let token_index = self.0.get_mut(path).unwrap();
        token_index.set_end(end);
    }

    // Check if the path already exists and return an error if it does, otherwise insert the path.
    //
    fn insert(&mut self, path: &UniquePath, start: usize) {
        self.0.insert(path.clone(), TokenIndex::new(start));
    }

    pub fn len(&self) -> usize {
        self.0.len()
    }
}

impl Debug for KeyMap {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut s = String::with_capacity(self.len() * 40);
        s.push_str("KeyMap:\n");
        for (key, value) in self.0.iter() {
            s.push_str(&format!("{:?}:{}\n", key, value));
        };
        s.pop();
        write!(f, "{}", s)
    }
}

// This is an iterator over something that can be used to construct KeyTrees.
//
#[derive(Clone, Debug)]
enum Context<'a> {
    // Unique and Iter are the same internally. Unique marks an iterator with one element. Iter
    // marks an iterator with zero of more than one elements.
    Unique(Peekable<Range<'a, UniquePath, TokenIndex>>),
    Iter(Peekable<Range<'a, UniquePath, TokenIndex>>),

    // We need to be able to handle paths that point to nothing. These will fail if we apply into()
    // on these unless the target type is Option<T> or if the target type is Vec<T> which creates
    // an empty Vec. It is not possible to have an empty BTreeMap Range, so we use EmptyIter
    // instead.
    EmptyIter(NonUniquePath),
}

// You can think of converting a KeyTree into a data-type as an algorithm that creates a whole set of
// KeyTrees (which are small efficient structures all pointing into an immutable KeyTreeCore) at each
// node in the tree, and then consumes each of these KeyTrees into the target data-type. The at()
// function creates a new KeyTree which applies a local_path to Self's context to construct a new
// KeyTree and then convert it using into(). next() also creates a new KeyTree by iterating over Self's
// context. The iter() function creates a new Context as a component of constructing a KeyTree.
//
/// `KeyTree` is a mutable reference into the immutable `KeyTreeCore`. You can move the `KeyTree`
/// reference around by applying the `at()` function to it.
///
#[derive(Clone, Debug)]
pub struct KeyTree<'a> {
    keytree_core:   &'a KeyTreeCore<'a>,
    context:        Context<'a>,
}

impl<'a> KeyTree<'a> {

    /// Construct a mutable KeyTree from an immutable KeyTreeCore. See main example at the start of
    /// the documentation or in README.md
    ///
    pub fn from_core(keytree_core: &'a KeyTreeCore) -> Self {
        KeyTree {
            keytree_core:   keytree_core,
            context:        keytree_core.iter(keytree_core.root.clone().non_unique()),
        }
    }

    /// Finds the value in `path` and converts into `T`. Will crash if it cannot be found. For
    /// context, see main example at the start of the documentation or in README.md
    ///
    // Creates a new KeyTree at a new position in the tree. Then calls into() to convert itself into
    // a type T.
    //
    pub fn at<T>(&self, path: &str) -> T
    where
        KeyTree<'a>: Into<T>
        // T has to be something such that <KeyTree>.into() returns a T.
    {
        let local_path = match NonUniquePath::from(path) {
            Ok(path) => path,
            Err(_)   => { KeyTreeErr::parse_keytree(); unreachable!() },
        };
        
        // Clone this value and append
        // local_path to create a new Context. Call iter() to create a context and then use this to
        // construct KeyTree.
        //
        let global_path = match &self.context {
            Context::Unique(iter) | Context::Iter(iter) => {
                iter.clone()
                    .peek()
                    .unwrap()
                    .0
                    .clone()
                    .append_non_unique(&local_path.tail())
            },
            Context::EmptyIter(_) => {
                KeyTreeErr::not_unique_but_empty();
                unreachable!();
            },
        };
        KeyTree {
            keytree_core: &self.keytree_core,
            context:    self.keytree_core.iter(global_path),
        }.into()
    }

    /// Finds the value in `path` and converts into `Some<T>` if it can be found otherwise returns
    /// `None`. For context, see main example at the start of the documentation or in README.md
    ///
    pub fn op<T>(&self, path: &str) -> Option<T>
    where
        KeyTree<'a>: Into<T>
    {
        let local_path = match NonUniquePath::from(path) {
            Ok(path) => path,
            Err(_)   => { KeyTreeErr::parse_keytree(); unreachable!() },
        };
        
        // Clone this value and append
        // local_path to create a new Context. Call iter() to create a context and then use this to
        // construct KeyTree.
        //
        let global_path = match &self.context {
            Context::Unique(iter) | Context::Iter(iter) => {
                iter.clone()
                    .peek()
                    .unwrap()
                    .0
                    .clone()
                    .append_non_unique(&local_path.tail())
            },
            Context::EmptyIter(_) => {
                KeyTreeErr::not_unique_but_empty();
                unreachable!();
            },
        };

        let context = self.keytree_core.iter(global_path);

        match context {
            Context::EmptyIter(_) => None,
            _ => {
                Some(
                    KeyTree {
                        keytree_core: &self.keytree_core,
                        context:    context,
                    }.into()
                )
            }
        }
    }

    /// Returns the value of at the root of the `KeyTree`. Requires that it is unique, otherwise
    /// crashes with an error. 
    ///
    pub fn value(&mut self) -> Option<&str> {
        match &self.context {
            Context::Unique(iter) => {
                let tok_ix = iter.clone()
                    .peek()
                    .unwrap()
                    .1
                    .end();

                let token = self
                    .keytree_core
                    .tokens[tok_ix];

                match token {
                    Token::Value(tok) => Some(&self.keytree_core.s[tok.start_val..=tok.end_val]),
                    Token::Key(_)     => { panic!("Should not be reachable.") },
                }
            },
            Context::Iter(_)        => { KeyTreeErr::not_unique(); unreachable!() },
            Context::EmptyIter(_)   => None,
        }
    }
}

impl<'a> Iterator for KeyTree<'a> {
    type Item = KeyTree<'a>;

    // Creates a new KeyTree, that has as its context its present Iterator state.
    //
    fn next(&mut self) -> Option<Self::Item> {
        match self.context {
            Context::Iter(ref mut context) | Context::Unique(ref mut context) => {
                match context.next() {
                    Some((path, _)) => {
                        let iter = self
                            .keytree_core.keymap.0
                            .range((Included(path), Included(path)))
                            .peekable();
                        Some(
                            KeyTree {
                                keytree_core: &self.keytree_core,
                                context:    Context::Unique(iter),
                            }
                        )
                    },
                    None => None,
                }
            },
            Context::EmptyIter(_) => {
                // Should not call next() on an KeyTree with an EmptyIter, it should be handled
                // separately in Into implementation.
                panic!("Should not call next() on KeyTree with Context::EmptyIter(_)");
            },
        }
    }
}

// KeyTreeCore is the data-structure generated from parsing an KeyTree string. It can be thought of as
// a tree, with Paths refering to locations in the tree. It is represented as a HashMap (keylen) of
// paths[..] => max. Keymap is a BTree which maps path[0]...path[max] => TokenIndex, which has
// pointers to the start and end of a list of Tokens (tokens). Each token then points into the
// original &str s.
//
// All possible searches are recorded. It is possible to dig into this data structure using
// path[index], but it is simpler for the user to dig using path[..] which returns an iterator over
// the multiple paths. This iterator is then converted to a Rust data structure by taking the
// iterator and apply into() from the Into Trait, which in turn can dig further into its
// (sub)-KeyTree, recording its position in the tree, and then doing another lookup in the global
// KeyTreeCore.
//
/// `KeyTreeCore` is the immutable result of parsing a string.
///
pub struct KeyTreeCore<'a> {
    s:          &'a str,
                // `s` is a reference to the original str passed into new(),

    keymap: KeyMap,
                // Maps unique Path to a TokenIndex

    keylen:     KeyLen,
                // Maps non-unique Path to a usize. The usize is the max index of this Path in KeyMap.
                        
    tokens:     Tokens,     
                // Lists all the tokens. Tokens point into `s`.

    root:   UniquePath,  
                // Sets the immutable root of the parsed string.
}

impl<'a> KeyTreeCore<'a> {
    // Constructs a Context given a global_path. This is used in at().
    fn iter(&self, global_path: NonUniquePath) -> Context {
        match self.keylen.0.get(&global_path) {
            Some(max) => {
                // Set the bounds on the BTree
                let start_path  = global_path.clone().unique(0);
                let end_path    = global_path.clone().unique(*max);

                let iter = self
                    .keymap.0
                    .range((Included(start_path), Included(end_path)))
                    .peekable();

                if *max == 0 {
                    Context::Unique(iter)
                } else {
                    Context::Iter(iter)
                }
            },
            None => {
                Context::EmptyIter(global_path)
            },
        }
    }
}

impl<'a> fmt::Debug for KeyTreeCore<'a> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}\n{:?}\n{:?}\n{:?}", self.s, self.tokens, self.keymap, self.keylen)
    }
}

// KeyLen is a part of KeyTreeCore (the immutable representation of a KeyTree string). It records the
// number of elements in a path.
//
struct KeyLen(HashMap<NonUniquePath, usize>);

impl KeyLen {

    fn new() -> Self {
        KeyLen(HashMap::new())
    }

    fn get(&self, path: &NonUniquePath) -> Option<usize> {
        match self.0.get(path) {
            Some(path)  => Some(*path),
            None        => None,
        }
    }

    // This is used only while parsing.
    //
    fn insert(&mut self, path: &UniquePath) {
        self.0.insert(path.clone().non_unique(), path.last_index());
    }
}

impl<'a> fmt::Debug for KeyLen {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut s = String::from("Keylen: \n");
        for (key, value) in self.0.iter() {
            s.push_str(&format!("{:?}: {:?}\n", key, value));
        };
        write!(f, "{}", s)
    }
}