keytree/

parser.rs

//! Parses string into `KeyTreeCore` type.

use crate::path::UniquePath;
use crate::error::KeyTreeErr;

use crate::{
    EachIndent,
    Key,
    KeyLen,
    Value,
    Token,
    Tokens,
    KeyMap,
    KeyTreeCore,
};

const INDENT_STEP: usize = 4;

// The parser has a set of states that change as it reads through the characters. The states are:
//
// ```text
//         this_is_a_key:      "v\"alue"
// ^  ^    ^             ^     ^         ^
// |  |    |             |     |         |
// FC BK   IK            RAK   IV        AV
// ```
//
// or 
//
// ```test
//           CM
//           |
//           v
//          // this is a comment
// ^   ^    ^
// |   |    |
// FC  BK   COK
// ```
//
// or
//
// ```test
//           IK
//           |
//           v
//          /this_is_a_key:
// ^   ^    ^
// |   |    |
// FC  BC   COK
// ```

#[derive(Clone, Debug, PartialEq)]
enum PS {
    FC,       // First char.
    BK,       // Before key.
    COK,      // Comment or key

    IK,       // In key.
    RAK,      // The character right after the key.
    AK,       // After key.

    IV,       // In value.

    CM,       // In comment
}
 
pub struct KeyTreeBuilder;

// Because there are many variables that need to be passed from parse() to new_token(), the
// BuildVars struct is used to collect them together.

#[derive(Debug)]
pub struct BuildVars<'a> {

    // Grow while looping

    keymap:         KeyMap,

    keylen:         KeyLen,

    tokens:         Tokens,

    each_indent:    EachIndent,
                        // While parsing, this Vec keeps track of the set of all paths which do not
                        // have 'end' set. The first element in the Vec has indent equal to its
                        // index. It also keeps track of indent numbers.

    path:           UniquePath,
                        // The last path inserted into KeyMap.

    first_key:      bool,
                        // Starts off as true and flips to false after the         
                        // first key is read. This is used to check that the first
                        // non-blank, non-comment token is a key only.

    ch_root_indent: Option<usize>,
                    // This is the indentation of the top key. Indentation of
                    // other keys in the data string should be aligned to this
                    // value.
    
    root_path:      Option<UniquePath>,
                        // The root path.

    pos:            usize,
                        // Char position. This is required after while loop.

    // Reset with each new line 

    ch_indent:      Option<usize>,
    
    start_line:     Option<usize>,
                        // The index of the start of a new line.
    
    start_key:      Option<usize>,

    end_key:        Option<usize>,
                        // The index of the end of a key.

    start_val:      Option<usize>,
                        // The index of the start of a key. It is also set at the
                        // start of a comment.
    
    end_val:        Option<usize>,
                        // The index of the end of a value.

    pub s:              &'a str,
}

impl<'a> BuildVars<'a> {

    fn new(s: &'a str) -> Self {
        Self {
            keymap:             KeyMap::new(),
            keylen:             KeyLen::new(),
            tokens:             Tokens::new(),
            each_indent:        EachIndent::new(),
            path:               UniquePath::new(),
            first_key:          true,
            ch_root_indent:     None,
            root_path:          None,
            pos:                0,
            ch_indent:          None,
            start_line:         None,
            start_key:          None,
            end_key:            None,
            start_val:          None,
            end_val:            None,
            s:                  s,
        }
    }

    // Resets values that are not valid for the next loop. 
    fn new_line(&mut self, pos: usize) {
        self.start_line = Some(pos);
        self.start_key  = None;
        self.end_key    = None;
        self.start_val  = None;
        self.end_val    = None;
    }

    // pub fn err_output(&self, pos: usize) {
    //     let line: &str;
    //     let num: usize;
    //     let mut spos: usize = 0;
    //     let mut iter = self.s.lines().enumerate();
    //     while spos < pos {
    //         if let Some((num, line)) = iter.next() {
    //             spos += line.chars().count();
    //         }
    //     };
    //     println!("{:3} {}", num + 1, line)
    // }

    // pub fn line_of_pos(&self, pos: usize) {

    //     println!("{}", pos)
    // }
}

impl<'a> KeyTreeBuilder {

    /// Parse a `KeyTree` string into an immutable `KeyTreeCore`. For context, see main example at
    /// the start of the documentation or in README.md
    ///
    pub fn parse(s: &'a str) -> KeyTreeCore<'a> {

        if s == "" { KeyTreeErr::empty_string(); unreachable!() };

        let mut vars = BuildVars::new(s);

        let mut parse_state: PS = PS::FC;

                // Declared here so that it can be used after iterating over chars.

        let mut iter = s.char_indices();

        while let Some((pos, ch)) = iter.next() {

            vars.pos = pos;

            // 'continue's are required at the end of each section because parse_state may have
            // changed and so the parser may enter into a new section without iterating to the next
            // character.
            //
            // `fn ParseErr::name()` functions are errors that exit and so never return.

            match (&parse_state, ch, ch.is_whitespace()) {

                // If the first char is '\n' then must be blank line.
                (PS::FC, '\n', true) => {
                    parse_state = PS::FC;
                },

                // First character in line. Whitespace.
                (PS::FC, _, true) => {
                    Self::set_start_line(&mut vars, pos);
                    parse_state = PS::BK;
                },

                // First character in line. Could be either first '/' of comment or first char of
                // key.
                (PS::FC, '/', false) => {
                    Self::set_start_line(&mut vars, pos);
                    Self::set_start_key(&mut vars, pos);
                    parse_state = PS::COK;
                },

                // First character in line. Key cannot start with colon.
                (PS::FC, ':', false) => {
                    KeyTreeErr::colon_before_key(pos);
                    unreachable!();
                },

                // At first character and receive a non-whitespace other than '/'. This must be a
                // key or key_value.
                (PS::FC, _, false) => {
                    Self::set_start_line(&mut vars, pos);
                    Self::set_start_key(&mut vars, pos);
                    vars.start_key = Some(pos);
                    parse_state = PS::IK;
                },

                // If we are given a '\n' before a key it must be a blank line.
                (PS::BK, '\n', true) => {
                    parse_state = PS::FC;
                },
                
                // Before key and receive a whitespace. Continue.
                (PS::BK, _, true) => { },

                // Before key and receive a `/`. This Could be either first '/' of comment or first
                // char of key.
                (PS::BK, '/', false) => {
                    Self::set_start_key(&mut vars, pos);
                    parse_state = PS::COK;
                },

                // Before key and recieve ':'. Key cannot start with colon.
                (PS::BK, ':', false) => {
                    KeyTreeErr::colon_before_key(pos);
                    unreachable!();
                },

                // Before key are receive non-whitespace other than ':'. Must be first token in a
                // key.
                (PS::BK, _, false) => {
                    Self::set_start_key(&mut vars, pos);
                    parse_state = PS::IK;
                },

                // Have received one '/' and receive a newline. Line is incomplete.
                (PS::COK, '\n', true) => {
                    KeyTreeErr::line_incomplete(pos);
                    unreachable!();
                },
                
                // Have received one '/' and receive a whitespace. This is an error.
                (PS::COK, _, true) => {
                    KeyTreeErr::no_colon(pos);
                    unreachable!();
                },

                // Have received one '/' and receive another '/'. This must be a comment.
                (PS::COK, '/', false) => {
                    parse_state = PS::CM;
                },

                // Have received one '/' and get a non-whitespace. This must be a key.
                (PS::COK, _, false) => {
                    parse_state = PS::IK;
                },

                // In comment and recieve '\n'. End of line.
                (PS::CM, '\n', true) => {
                    parse_state = PS::FC;
                },

                // In comment and receive something other than '\n'. Continue.
                (PS::CM, _, _) => { },

                // In key and receive a '\n'. The line is incomplete.
                (PS::IK, '\n', true) => {
                    KeyTreeErr::line_incomplete(pos);
                    unreachable!();
                },

                // In key and receive a whitespace. The key in incomplete.
                (PS::IK, _, true) => {
                    KeyTreeErr::no_colon(pos);
                    unreachable!();
                },

                // In key and receive a ':'. This must be end of key.
                (PS::IK, ':', false) => {
                    Self::set_end_key(&mut vars, pos - 1);
                    parse_state = PS::RAK;
                },
                
                // In key and receive a non-whitespace. Continue.
                (PS::IK, _, false) => { }

                // Right after key and receive a non-whitespace. This is an error.
                (PS::RAK, _, false) => {
                    KeyTreeErr::no_space_after_key(pos);
                    unreachable!();
                },

                // Right after key and receive a '\n\'. This must be a key token.
                (PS::RAK, '\n', true) => {
                    Self::new_token(Self::key_token(&vars), &mut vars);
                    parse_state = PS::FC;
                },

                // Right after key and receive a whitespace other than '\n'. Continue.
                (PS::RAK, _, true) => {
                    parse_state = PS::AK;
                },

                // After key and receive a non-whitespace which must be the start of value.
                (PS::AK, _, false) => {
                    // First key must be key only.
                    if vars.first_key {
                        KeyTreeErr::first_token_is_val(vars.start_key.unwrap(), &vars);
                        unreachable!();
                    };
                    Self::set_start_val(&mut vars, pos);
                    parse_state = PS::IV;
                },

                // After key. No value.
                (PS::AK, '\n', true) => {
                    Self::new_token(Self::key_token(&vars), &mut vars);
                    parse_state = PS::FC;
                },

                // After key. Whitespace is a no-op.
                (PS::AK, _, true) => { },

                // In value and receive a '\n'. This must be a key_value.
                (PS::IV, '\n', true) => {
                    Self::set_end_val(&mut vars, pos - 1);
                    Self::new_token(Self::value_token(&vars), &mut vars);
                    parse_state = PS::FC;
                },

                // In value. Whitespace is a no-op.
                (PS::IV, _, true) => { },

                // In value. Non-whitespace, update end_val.
                (PS::IV, _, false) => {
                    vars.end_val = Some(pos);
                },
            };  // end match
        };
 
        // Need to handle end of text with no newline. Expect parse start to be
        //
        //  FC (first char)          do nothing  
        //  RAK (right after key)    insert new key
        //  AK (after key)           insert new key
        //  AV                       insert new key_value
        //  CM                       do nothing
        //  _                        error: incomplete_parse()
        
        match parse_state {

            // In comment. Non-whitespace.
            PS::CM => { }, 

            // After key. No value.
            PS::RAK | PS::AK => {
                vars.end_key = Some(vars.pos);
                Self::new_token(Self::key_token(&vars), &mut vars);
            },

            // After value.
            PS::IV => {
                // First key must be key only.
                if vars.first_key {
                    KeyTreeErr::first_token_is_val(vars.start_key.unwrap(), &vars);
                    unreachable!();
                };
                vars.end_val = Some(vars.pos);
                Self::new_token(Self::value_token(&vars), &mut vars);
            },

            _ => {
                KeyTreeErr::line_incomplete(s.len() - 1);
            },
        };

        // This sets ends in vars.keymap
        Self::insert_end_indices(&mut vars, 0);

        KeyTreeCore {
            s:      s,
            keymap: vars.keymap,
            keylen: vars.keylen,
            tokens: vars.tokens,
            root:   vars.root_path.unwrap(),
        }
    }

    // New token takes a new Token and inserts it into a KeyMap and Tokens list. We are passing a
    // whole lot of variables that we need to change in the calling function `parse()`.
    //
    fn new_token(token: Token, mut vars: &mut BuildVars) {

        // Check that we can use the token to create a path segment.
        
        let key = &vars.s[vars.start_key.unwrap()..=vars.end_key.unwrap()];

        // let indent = Self::indent(vars);

        if vars.first_key {     // Root token

            vars.ch_root_indent = Some(vars.start_key.unwrap());
            vars.first_key      = false;

            vars.path           = UniquePath::from(key).unwrap();
            vars.root_path      = Some(vars.path.clone());

            vars.tokens.push(token);
            vars.keymap.insert(&vars.path, vars.tokens.len() - 1);
            vars.keylen.insert(&vars.path);

            // Update vars.each_indent
            vars.each_indent.push(&vars.path);

        } else {                // All other tokens

            // Order is important in this section because the dependencies are intricate. First we
            // set independent variables
            //
            //  old_indent
            //  new_indent
            //
            //  To set vars.path, we need to create it from `key` and then set its index by looking
            //  up each_indent. Each_indent is determined by the previous loop, and therefore
            //  should be set at the end of this function.
            //
            //  vars.path
            //
            //  Inserting end indices should be done before

            // Set independent variables
            
            let old_indent = vars.path.len() - 1;
            let new_indent = Self::indent(&vars); // Indent from new token.


            // Set vars.path

            vars.path = vars.path
                .clone()
                .truncate(new_indent)
                .append_unique(
                    &mut UniquePath::from(key).unwrap()
                );                            // Parsing should eliminate
                                              // badly formed strings.
                                              
            let index = vars.each_indent.new_index(
                    &vars.path,
                    new_indent
                );

            vars.path.set_last_index(index);

            // Update end indices

            if new_indent <= old_indent {
                Self::insert_end_indices(&mut vars, new_indent);
            };

            // Insert the data

            vars.keylen.insert(&vars.path);

            vars.tokens.push(token);

            vars.keymap.insert(&vars.path, vars.tokens.len() - 1);

            // Insert var.each_indent should be at the end of this function as its state should be
            // set by the previous parser loop.
            
            vars.each_indent.insert(&vars.path, new_indent);

        };
    }
 
    // Return indentation given position from start of line and root_indent (as an integer 0, 1, 2,
    // ...).
    //
    fn indent(vars: &BuildVars) -> usize {

        let ch_indent = (vars.start_key.unwrap() - vars.start_line.unwrap()) - vars.ch_root_indent.unwrap() + 1;

        if ch_indent % INDENT_STEP != 0 {
            KeyTreeErr::indent(ch_indent, vars);
            unreachable!();
        } else {
            ch_indent / INDENT_STEP
        }
    }

    // Construct a Value Token

    fn value_token(vars: &BuildVars) -> Token {
        Token::Value(
            Value::new(
                vars.start_key.unwrap(),
                vars.end_key.unwrap(),
                vars.start_val.unwrap(),
                vars.end_val.unwrap(),
            )
        )
    }

    fn key_token(vars: &BuildVars) -> Token {
        Token::Key(
            Key::new(
                vars.start_key.unwrap(),
                vars.end_key.unwrap(),
            )
        )
    }

    fn set_start_line(vars: &mut BuildVars, pos: usize) {
        vars.start_line = Some(pos);
    }

    fn set_start_key(vars: &mut BuildVars, pos: usize) {
        vars.start_key = Some(pos);
    }

    fn set_end_key(vars: &mut BuildVars, pos: usize) {
        vars.end_key = Some(pos);
    }

    fn set_start_val(vars: &mut BuildVars, pos: usize) {
        vars.start_val = Some(pos);
    }

    fn set_end_val(vars: &mut BuildVars, pos: usize) {
        vars.end_val = Some(pos);
    }

    // When new tokens are inserted into KeyMap, the end index is not known. This function inserts
    // the end index when it is known.
    //
    fn insert_end_indices(vars: &mut BuildVars, indent: usize) {
        for i in indent..vars.each_indent.len() {
            vars.keymap
                .set_end(&vars.each_indent[i], vars.tokens.len() - 1);
        };
        vars.each_indent.0.truncate(indent);
    }
}