kconfig_parser/ast/

parser.rs

/*
 Cargo KConfig - KConfig parser
 Copyright (C) 2022  Sjoerd van Leent

--------------------------------------------------------------------------------

Copyright Notice: Apache

Licensed under the Apache License, Version 2.0 (the "License"); you may not use
this file except in compliance with the License. You may obtain a copy of the
License at

   https://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed
under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
CONDITIONS OF ANY KIND, either express or implied. See the License for the
specific language governing permissions and limitations under the License.

--------------------------------------------------------------------------------

Copyright Notice: GPLv2

This program 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 2 of the License, or
(at your option) any later version.

This program 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.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <https://www.gnu.org/licenses/>.

--------------------------------------------------------------------------------

Copyright Notice: MIT

Permission is hereby granted, free of charge, to any person obtaining a copy of
this software and associated documentation files (the “Software”), to deal in
the Software without restriction, including without limitation the rights to
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
the Software, and to permit persons to whom the Software is furnished to do so,
subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

//! This file contains the parser of the Kconfig file, and creates the
//! Abstract Syntax Tree for it.

use std::{
    collections::{HashMap, HashSet, VecDeque},
    fmt::Display,
    hash::Hash,
};

use super::dependency_parser::parse as parse_dependency;
use super::expr_parser::parse as parse_expr;
use super::structs::*;
use crate::lex::{
    structs::{Keyword, Lexicon, Token},
    LexerBase,
};
use crate::parse_string;

#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Error {
    token: Token,
    msg: String,
}

impl Display for Error {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(
            f,
            "{} at {}:{}, found: {}",
            self.msg,
            self.token.line(),
            self.token.column(),
            self.token,
        )
    }
}

impl Error {
    pub(super) fn new(token: Token, msg: &str) -> Self {
        Self {
            token,
            msg: msg.to_string(),
        }
    }
}

/// Determines which config element type to use, this can either be
/// Config or Menuconfig.
/// Contains the Ast for the entire stream of tokens, including sourced
/// elements.
#[derive(Clone, Debug, Eq, PartialEq, Default)]
pub struct Ast {
    main_menu: Option<String>,
    elements: Vec<(String, Element)>,
    comment: String,
    conditions: Vec<Condition>,
}

/// Describes a configuration element, typically starting with the
/// "config" keyword
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct ConfigElement {
    config: Config,
}

/// Describes a menu-configuration element, typically starting with the
/// "menuconfig" keyword
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct MenuConfigElement {
    config: Config,
}

/// Describes a menu element, typically starting with the "menu" keyword
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Menu {
    config: Config,
    visible_if: HashSet<Dependency>,
    elements: Vec<(String, Element)>,
    comment: String,
    conditions: Vec<Condition>,
}

/// Describes a condition, typically a statement part of another expression,
/// which is introduced by appending "if" to the statement. This would apply
/// a particular statement in a certain condition.
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Condition {
    dependency: Dependency,
    elements: Vec<(String, Element)>,
    conditions: Vec<Condition>,
}

impl Condition {
    pub fn new(dependency: &Dependency) -> Self {
        Self {
            dependency: dependency.clone(),
            elements: Vec::new(),
            conditions: Vec::new(),
        }
    }

    pub fn dependency(&self) -> Dependency {
        self.dependency.clone()
    }

    pub fn elements(&self) -> Vec<(String, Element)> {
        self.elements.clone()
    }
}

pub trait WithComment {
    fn comment(&self) -> String;
}

impl WithComment for Ast {
    fn comment(&self) -> String {
        self.comment.clone()
    }
}

impl WithComment for Menu {
    fn comment(&self) -> String {
        self.comment.clone()
    }
}

trait Commentable {
    fn set_comment(&mut self, s: &str);
}

impl Commentable for Ast {
    fn set_comment(&mut self, s: &str) {
        self.comment = s.to_string()
    }
}

impl Commentable for Menu {
    fn set_comment(&mut self, s: &str) {
        self.comment = s.to_string()
    }
}

pub trait ConditionContainer {
    fn len_conditional_blocks(&self) -> usize;
    fn conditional_blocks(&self) -> Vec<Condition>;
}

impl ConditionContainer for Ast {
    fn len_conditional_blocks(&self) -> usize {
        self.conditions.len()
    }
    fn conditional_blocks(&self) -> Vec<Condition> {
        self.conditions.clone()
    }
}

impl ConditionContainer for Menu {
    fn len_conditional_blocks(&self) -> usize {
        self.conditions.len()
    }

    fn conditional_blocks(&self) -> Vec<Condition> {
        self.conditions.clone()
    }
}

impl ConditionContainer for Condition {
    fn len_conditional_blocks(&self) -> usize {
        self.conditions.len()
    }

    fn conditional_blocks(&self) -> Vec<Condition> {
        self.conditions.clone()
    }
}

pub trait Container {
    fn element_names(&self) -> Box<dyn Iterator<Item = String>>;
}

trait MutableContainer: Container {
    fn insert_child(&mut self, name: &str, e: Element);
    fn insert_condition(&mut self, e: Condition);
    fn len(&self) -> usize;
}

impl Container for Ast {
    fn element_names(&self) -> Box<dyn Iterator<Item = String>> {
        Box::new(
            self.elements
                .clone()
                .into_iter()
                .map(|(name, _)| name.clone()),
        )
    }
}

impl Container for Menu {
    fn element_names(&self) -> Box<dyn Iterator<Item = String>> {
        Box::new(
            self.elements
                .clone()
                .into_iter()
                .map(|(name, _)| name.clone()),
        )
    }
}

impl Container for Condition {
    fn element_names(&self) -> Box<dyn Iterator<Item = String>> {
        Box::new(
            self.elements
                .clone()
                .into_iter()
                .map(|(name, _)| name.clone()),
        )
    }
}

impl MutableContainer for Ast {
    fn insert_child(&mut self, name: &str, e: Element) {
        self.elements.push((name.to_string(), e));
    }

    fn insert_condition(&mut self, e: Condition) {
        self.conditions.push(e);
    }

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

impl MutableContainer for Menu {
    fn insert_child(&mut self, name: &str, e: Element) {
        self.elements.push((name.to_string(), e));
    }

    fn insert_condition(&mut self, e: Condition) {
        self.conditions.push(e);
    }

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

impl MutableContainer for Condition {
    fn insert_child(&mut self, name: &str, e: Element) {
        self.elements.push((name.to_string(), e));
    }

    fn insert_condition(&mut self, e: Condition) {
        self.conditions.push(e);
    }

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

trait BaseConfigElement {
    fn create(name: &str) -> Self;
    fn config(&mut self) -> &mut Config;
    fn insert_into_hierarchy<I>(&mut self, hierarchy: &mut I)
    where
        I: MutableContainer;
}

impl BaseConfigElement for ConfigElement {
    fn create(name: &str) -> Self {
        let config = Config::create(name);
        Self { config }
    }

    fn config(&mut self) -> &mut Config {
        &mut self.config
    }

    fn insert_into_hierarchy<I>(&mut self, hierarchy: &mut I)
    where
        I: MutableContainer,
    {
        hierarchy.insert_child(&self.config().name.clone(), Element::Config(self.clone()));
    }
}

impl BaseConfigElement for MenuConfigElement {
    fn create(name: &str) -> Self {
        let config = Config::create(name);
        Self { config }
    }

    fn config(&mut self) -> &mut Config {
        &mut self.config
    }

    fn insert_into_hierarchy<I>(&mut self, hierarchy: &mut I)
    where
        I: MutableContainer,
    {
        hierarchy.insert_child(
            &self.config().name.clone(),
            Element::MenuConfig(self.clone()),
        );
    }
}

impl BaseConfigElement for Menu {
    fn create(name: &str) -> Self {
        let config = Config::create(name);
        Self {
            config,
            visible_if: HashSet::new(),
            elements: Vec::new(),
            comment: String::new(),
            conditions: Vec::new(),
        }
    }

    fn config(&mut self) -> &mut Config {
        &mut self.config
    }

    fn insert_into_hierarchy<I>(&mut self, hierarchy: &mut I)
    where
        I: MutableContainer,
    {
        hierarchy.insert_child(&self.config().name.clone(), Element::Menu(self.clone()));
    }
}

impl Hash for ConfigElement {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.config.name.hash(state);
    }
}

impl Hash for MenuConfigElement {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.config.name.hash(state);
    }
}

impl Hash for Menu {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.config.name.hash(state);
    }
}

impl Hash for Condition {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.dependency.hash(state);
    }
}

#[derive(Hash, Clone, Debug, Eq, PartialEq)]
pub enum ElementType {
    Config,
    MenuConfig,
    Menu,
}

/// An Ast contains a list of elements, which might themselves contain
/// other parts of the Ast, etc.
#[derive(Hash, Clone, Debug, Eq, PartialEq)]
pub enum Element {
    Config(ConfigElement),
    MenuConfig(MenuConfigElement),
    Menu(Menu),
}

impl Element {
    pub fn len_conditional_blocks(&self) -> usize {
        match self {
            Element::Menu(elt) => elt.len_conditional_blocks(),
            _ => 0,
        }
    }

    pub fn conditional_blocks(&self) -> Vec<Condition> {
        match self {
            Element::Menu(elt) => elt.conditional_blocks(),
            _ => Vec::new(),
        }
    }

    pub fn dependencies(&self) -> HashSet<Dependency> {
        match self {
            Element::Config(elt) => elt.config.dependencies.clone(),
            Element::MenuConfig(elt) => elt.config.dependencies.clone(),
            Element::Menu(elt) => elt.config.dependencies.clone(),
        }
    }

    pub fn name(&self) -> String {
        match self {
            Element::Config(elt) => elt.config.name.clone(),
            Element::MenuConfig(elt) => elt.config.name.clone(),
            Element::Menu(elt) => elt.config.name.clone(),
        }
    }

    pub fn prompt(&self) -> Option<String> {
        match self {
            Element::Config(elt) => elt.config.prompt.as_ref().map(|s| s.to_string()),
            Element::MenuConfig(elt) => elt.config.prompt.as_ref().map(|s| s.to_string()),
            _ => None,
        }
    }

    pub fn elt_type(&self) -> ElementType {
        match self {
            Element::Config(_) => ElementType::Config,
            Element::MenuConfig(_) => ElementType::MenuConfig,
            Element::Menu(_) => ElementType::Menu,
        }
    }

    pub fn types(&self) -> Option<&HashMap<ConfigType, Option<Dependency>>> {
        match self {
            Element::Config(elt) => Some(&elt.config.types),
            Element::MenuConfig(elt) => Some(&elt.config.types),
            _ => None,
        }
    }

    pub fn defaults(&self) -> Option<&HashMap<Expr, Option<Dependency>>> {
        match self {
            Element::Config(elt) => Some(&elt.config.defaults),
            Element::MenuConfig(elt) => Some(&elt.config.defaults),
            _ => None,
        }
    }

    pub fn reverse_dependencies(&self) -> Option<&HashMap<String, Option<Dependency>>> {
        match self {
            Element::Config(elt) => Some(&elt.config.reverse_dependencies),
            Element::MenuConfig(elt) => Some(&elt.config.reverse_dependencies),
            Element::Menu(elt) => Some(&elt.config.reverse_dependencies),
        }
    }

    pub fn weak_dependencies(&self) -> Option<&HashMap<String, Option<Dependency>>> {
        match self {
            Element::Config(elt) => Some(&elt.config.weak_dependencies),
            Element::MenuConfig(elt) => Some(&elt.config.weak_dependencies),
            Element::Menu(elt) => Some(&elt.config.weak_dependencies),
        }
    }

    pub fn range(&self) -> Option<Range> {
        match self {
            Element::Config(elt) => elt.config.range.clone(),
            Element::MenuConfig(elt) => elt.config.range.clone(),
            _ => None,
        }
    }

    pub fn help(&self) -> VecDeque<String> {
        match self {
            Element::Config(elt) => elt.config.help.clone(),
            Element::MenuConfig(elt) => elt.config.help.clone(),
            Element::Menu(elt) => elt.config.help.clone(),
        }
    }

    pub fn visible_if(&self) -> HashSet<Dependency> {
        match self {
            Element::Menu(elt) => elt.visible_if.clone(),
            _ => HashSet::new(),
        }
    }

    pub fn sub_element(&self, s: &str) -> Option<&Element> {
        match self {
            // TODO, evaluate if this is a condition, and then continue
            // to a subelement, and so forth.
            Element::Menu(elt) => {
                for (subname, subelt) in &elt.elements {
                    if subname == s {
                        return Some(subelt);
                    };
                }
                None
            }
            _ => None,
        }
    }

    pub fn sub_elements(&self) -> Vec<(String, Element)> {
        match self {
            // TODO, evaluate if this is a condition, and then continue
            // to a subelement, and so forth.
            Element::Menu(elt) => elt.elements.clone(),
            _ => Vec::new(),
        }
    }

    pub fn len(&self) -> usize {
        match self {
            // TODO, evaluate if this is a condition, and then continue
            // to a subelement, and so forth.
            Element::Menu(elt) => elt.len(),
            _ => 0,
        }
    }
}

/// Checks if the given token has an error indication, if so, the
/// result will be filled with the error, Otherwise an empty Ok
/// will result
fn has_error(t: &Token) -> Result<(), Error> {
    if let Lexicon::Error(e) = t.term() {
        let msg = format!("Erroneous element: {}", e);
        Err(Error::new(t.clone(), &msg))
    } else {
        Ok(())
    }
}

/// Will result into an Err element with the expected type_name
/// in the message.
fn result_unexpected(t: &Token, type_name: &str) -> Error {
    let msg = format!("Expected {}", type_name);
    Error::new(t.clone(), &msg)
}

/// Verify if the current token is a String, if not so, returns an error,
/// otherwise returns the contents of the string.
fn should_be_string(t: &Token) -> Result<String, Error> {
    has_error(t)?;
    match t.term() {
        Lexicon::String(s) => Ok(s),
        _ => Err(result_unexpected(t, "Prompt")),
    }
}

/// Parses a prompt from the lexer after the Prompt keyword
fn parse_prompt<LB, F>(lexer: &mut LB, mut closure: F) -> Result<Token, Error>
where
    LB: LexerBase,
    F: FnMut(&str),
{
    let next_token = lexer.next_token();
    match next_token.term() {
        Lexicon::String(s) => match parse_string(&s) {
            Ok(v) => closure(&v),
            Err(e) => return Err(Error::new(next_token.clone(), &e)),
        },
        _ => return Err(Error::new(next_token.clone(), "Expected string")),
    };
    Ok(lexer.next_token())
}

/// Parses a bool type from the lexer after the Bool keyword
fn parse_type<LB, Fp, Fd>(
    lexer: &mut LB,
    token: Token,
    mut prompt_closure: Fp,
    mut dependency_closure: Fd,
) -> Result<Token, Error>
where
    LB: LexerBase,
    Fp: FnMut(&str),
    Fd: FnMut(&Dependency),
{
    let mut next_token = lexer.next_token();
    let mut line = token.line();
    if let Lexicon::String(s) = next_token.term() {
        match parse_string(&s) {
            Ok(v) => prompt_closure(&v),
            Err(e) => return Err(Error::new(next_token.clone(), &e)),
        }
        line = next_token.line();
        next_token = lexer.next_token();
    };
    if let Lexicon::Keyword(Keyword::If) = next_token.term() {
        // The line of the if statement must be on the same line as the line
        // of the prompt or the type indication
        if line == next_token.line() {
            let (dependency, result_token) = parse_dependency(lexer)?;
            next_token = result_token;
            dependency_closure(&dependency);
        }
    };
    Ok(next_token)
}

/// Parses a default value, which requires an expression and optionally a dependency expression can be
/// given through the if statement.
fn parse_default<LB, F>(lexer: &mut LB, token: Token, mut closure: F) -> Result<Token, Error>
where
    LB: LexerBase,
    F: FnMut(&Expr, Option<Dependency>),
{
    let line = token.line();
    let (maybe_expr, mut next_token) = parse_expr(lexer)?;
    let expr = match maybe_expr {
        None => return Err(Error::new(token.clone(), "Expected expression")),
        Some(expr) => expr,
    };
    let mut dep_result: Option<Dependency> = None;
    if let Lexicon::Keyword(k) = next_token.term() {
        if let Keyword::If = k {
            if line == token.line() {
                let (dep, new_token) = parse_dependency(lexer)?;

                dep_result = Some(dep);
                next_token = new_token;
            }
        }
    }
    closure(&expr, dep_result);
    Ok(next_token)
}

/// Parses an auto default type, typically in the form of def_bool and def_tristate. The
/// default value is given (as expression) and optionally a dependency expression can be
/// given through the if statement.
fn parse_def_type<LB, F>(lexer: &mut LB, token: Token, mut closure: F) -> Result<Token, Error>
where
    LB: LexerBase,
    F: FnMut(&Expr, Option<Dependency>),
{
    let line = token.line();
    let (maybe_expr, mut next_token) = parse_expr(lexer)?;
    let expr = match maybe_expr {
        None => return Err(Error::new(token.clone(), "Expected expression")),
        Some(expr) => expr,
    };
    let mut dep_result: Option<Dependency> = None;
    if let Lexicon::Keyword(k) = next_token.term() {
        if let Keyword::If = k {
            if line == token.line() {
                let (dep, new_token) = parse_dependency(lexer)?;

                dep_result = Some(dep);
                next_token = new_token;
            }
        }
    }
    closure(&expr, dep_result);
    Ok(next_token)
}

/// Parses a select statement which causes a reverse dependency. This is used by both
/// reverse dependencies (select) and weak reverse dependencies (imply). A reverse
/// dependencies forces a configuration, even though the regular dependencies should
/// not allow it. A weak reverse dependency only sets the option if available and
/// possible.
fn parse_select<LB, F>(lexer: &mut LB, token: Token, mut closure: F) -> Result<Token, Error>
where
    LB: LexerBase,
    F: FnMut(&str, Option<Dependency>),
{
    let line = token.line();
    let mut next_token = lexer.next_token();
    let sym = match next_token.term() {
        Lexicon::Identifier(s) => {
            next_token = lexer.next_token();
            s
        }
        _ => return Err(Error::new(next_token.clone(), "Expected identifier")),
    };

    let mut dep_result: Option<Dependency> = None;
    if let Lexicon::Keyword(k) = next_token.term() {
        if let Keyword::If = k {
            if line == token.line() {
                let (dep, new_token) = parse_dependency(lexer)?;

                dep_result = Some(dep);
                next_token = new_token;
            }
        }
    }
    closure(&sym, dep_result);
    Ok(next_token)
}

/// This function parses out a range (specifically for integer and hexadecimal usage). It
/// requires two arguments to be set (lower limit and upper limit), optionally with a
/// dependency expression
fn parse_range<LB, F>(lexer: &mut LB, token: Token, mut closure: F) -> Result<Token, Error>
where
    LB: LexerBase,
    F: FnMut(i64, i64, Option<Dependency>),
{
    let line = token.line();
    let mut next_token = lexer.next_token();
    let sym1 = match next_token.term() {
        Lexicon::Identifier(s) => {
            next_token = lexer.next_token();
            s
        }
        _ => return Err(Error::new(next_token.clone(), "Expected symbol")),
    };
    let i164 = match sym1.parse::<i64>() {
        Ok(s) => s,
        Err(_) => return Err(Error::new(next_token.clone(), "Expected integer symbol")),
    };
    let sym2 = match next_token.term() {
        Lexicon::Identifier(s) => {
            next_token = lexer.next_token();
            s
        }
        _ => return Err(Error::new(next_token.clone(), "Expected symbol")),
    };
    let i264 = match sym2.parse::<i64>() {
        Ok(s) => s,
        Err(_) => return Err(Error::new(next_token.clone(), "Expected integer symbol")),
    };

    let mut dep_result: Option<Dependency> = None;
    if let Lexicon::Keyword(k) = next_token.term() {
        if let Keyword::If = k {
            if line == token.line() {
                let (dep, new_token) = parse_dependency(lexer)?;

                dep_result = Some(dep);
                next_token = new_token;
            }
        }
    }
    closure(i164, i264, dep_result);
    Ok(next_token)
}

/// Converts a given token, if it contains a keyword specifying a configuration
/// type, to that configuration type.
fn token_to_config_type(t: &Token) -> Result<ConfigType, Error> {
    match t.term() {
        Lexicon::Keyword(k) => match k {
            Keyword::Bool => Ok(ConfigType::Bool),
            Keyword::Tristate => Ok(ConfigType::Tristate),
            Keyword::String => Ok(ConfigType::String),
            Keyword::Hex => Ok(ConfigType::Hex),
            Keyword::Int => Ok(ConfigType::Int),
            _ => Err(Error::new(
                t.clone(),
                "Expected type keyword bool, tristate, string, int or hex",
            )),
        },
        _ => Err(Error::new(t.clone(), "Expected keyword")),
    }
}

/// Parses the section of a configuration element. The first item read is the name of
/// the configuration, then the possible settings of the configuration element.
fn parse_config<I, LB, CE>(hierarchy: &mut I, lexer: &mut LB) -> Result<Token, Error>
where
    I: MutableContainer,
    LB: LexerBase,
    CE: BaseConfigElement,
{
    // Reads a generic configuration item. A generic configuration items needs to start with
    // a name defining it.
    let name_token = lexer.next_token();

    // If the next token is not an identifier, something is really off
    let mut config_element = match name_token.term() {
        Lexicon::Identifier(n) => CE::create(&n),
        _ => return Err(Error::new(name_token.clone(), "Expected identifier")),
    };

    let mut has_more = true;
    let mut next_token = lexer.next_token();
    // Loops over all the configuration options, until a non-conforming token is found, then
    // this token is handed back to parse_element
    while has_more {
        let start_token = next_token.clone();
        match start_token.term() {
            Lexicon::Help(s) => {
                config_element.config().help.push_back(s);
                next_token = lexer.next_token();
            }
            Lexicon::Keyword(k) => match k {
                Keyword::Depends => {
                    // If the Keyword contains depends, then the next keyword always needs
                    // to be 'On', if this is not the case, it is an error
                    next_token = lexer.next_token();
                    match next_token.term() {
                        Lexicon::Keyword(k) => match k {
                            Keyword::On => {
                                let (d, new_token) = parse_dependency(lexer)?;
                                config_element.config().dependencies.insert(d);
                                next_token = new_token;
                            }
                            _ => {
                                return Err(Error::new(name_token.clone(), "Expected keyword 'on'"))
                            }
                        },
                        _ => return Err(Error::new(name_token.clone(), "Expected keyword 'on'")),
                    }
                }
                Keyword::Select => {
                    next_token = parse_select(lexer, next_token, |s, d| {
                        config_element
                            .config()
                            .reverse_dependencies
                            .insert(s.to_string(), d.clone());
                        ()
                    })?;
                }
                Keyword::Imply => {
                    next_token = parse_select(lexer, next_token, |s, d| {
                        config_element
                            .config()
                            .weak_dependencies
                            .insert(s.to_string(), d.clone());
                        ()
                    })?;
                }
                Keyword::Prompt => {
                    next_token = parse_prompt(lexer, |s| {
                        config_element.config().prompt = Some(s.to_string());
                    })?
                }
                Keyword::Bool
                | Keyword::Tristate
                | Keyword::String
                | Keyword::Hex
                | Keyword::Int => {
                    let mut dependency: Option<Dependency> = None;
                    next_token = parse_type(
                        lexer,
                        next_token,
                        |s| config_element.config().prompt = Some(s.to_string()),
                        |d| dependency = Some(d.clone()),
                    )?;
                    config_element
                        .config()
                        .types
                        .insert(token_to_config_type(&start_token)?, dependency);
                }
                Keyword::Default => {
                    next_token = parse_default(lexer, next_token, |e, d| {
                        config_element
                            .config()
                            .defaults
                            .insert(e.clone(), d.map(|x| x.to_owned()));
                    })?
                }
                Keyword::DefBool | Keyword::DefTristate => {
                    next_token = parse_def_type(lexer, next_token, |e, d| {
                        match k {
                            Keyword::DefBool => config_element
                                .config()
                                .types
                                .insert(ConfigType::Bool, d.clone()),
                            _ => config_element
                                .config()
                                .types
                                .insert(ConfigType::Tristate, d.clone()),
                        };
                        config_element
                            .config()
                            .defaults
                            .insert(e.clone(), d.map(|x| x.to_owned()));
                    })?
                }
                Keyword::Range => {
                    next_token = parse_range(lexer, next_token, |lhs, rhs, dependency| {
                        config_element.config().range = Some(Range {
                            lhs,
                            rhs,
                            dependency,
                        })
                    })?
                }
                _ => {
                    has_more = false;
                }
            },
            _ => {
                has_more = false;
            }
        }
    }

    config_element.insert_into_hierarchy(hierarchy);

    Ok(next_token)
}

/// Parses a comment for a menu or for the Ast
fn parse_comment<C, LB>(commentable: &mut C, lexer: &mut LB) -> Result<Token, Error>
where
    C: Commentable,
    LB: LexerBase,
{
    let next_token = lexer.next_token();
    match next_token.term() {
        Lexicon::String(s) => {
            match parse_string(&s) {
                Ok(v) => commentable.set_comment(&v),
                Err(e) => return Err(Error::new(next_token.clone(), &e)),
            };
            Ok(lexer.next_token())
        }
        _ => Err(Error::new(next_token.clone(), "Expected string")),
    }
}

fn parse_if<I, LB>(hierarchy: &mut I, lexer: &mut LB) -> Result<Token, Error>
where
    I: MutableContainer,
    LB: LexerBase,
{
    // The If block statement requires to contain a dependency, so first
    // parsing the dependency.
    let (dependency, mut next_token) = parse_dependency(lexer)?;
    let mut condition = Condition::new(&dependency);
    let mut has_more = true;
    // Loops over all the configuration options, until a non-conforming token is found, then
    // this token is handed back to parse_element
    while has_more {
        let start_token = next_token.clone();
        match start_token.term() {
            Lexicon::Keyword(k) => match k {
                Keyword::Config => {
                    next_token =
                        parse_config::<Condition, LB, ConfigElement>(&mut condition, lexer)?
                }
                Keyword::Menuconfig => {
                    next_token =
                        parse_config::<Condition, LB, MenuConfigElement>(&mut condition, lexer)?
                }
                Keyword::Menu => {
                    // If this keyword is read, it will be a menu block. A menu block has a few items
                    // which a config or menu config does not have. Also, a menu bock ends with the
                    // endmenu.
                    // A menu block can have config and menu config items inside

                    next_token = parse_menu::<Condition, LB>(&mut condition, lexer)?;
                    // The next token must contain "endmenu"
                    match next_token.term() {
                        Lexicon::Keyword(k) => match k {
                            Keyword::Endmenu => next_token = lexer.next_token(),
                            _ => {
                                return Err(Error::new(
                                    next_token.clone(),
                                    "Keyword not expected, expected 'endmenu'",
                                ))
                            }
                        },
                        _ => return Err(Error::new(next_token.clone(), "Expected keyword")),
                    }
                }
                Keyword::If => {
                    // If this keyword is read, it will be a if block. A if block has a few items
                    // which a config or if config does not have. Also, a if bock ends with the
                    // endif.
                    // A if block can have config and if config items inside

                    next_token = parse_if::<Condition, LB>(&mut condition, lexer)?;
                    // The next token must contain "endif"
                    match next_token.term() {
                        Lexicon::Keyword(k) => match k {
                            Keyword::Endif => next_token = lexer.next_token(),
                            _ => {
                                return Err(Error::new(
                                    next_token.clone(),
                                    "Keyword not expected, expected 'endif'",
                                ))
                            }
                        },
                        _ => return Err(Error::new(next_token.clone(), "Expected keyword")),
                    }
                }
                _ => {
                    has_more = false;
                }
            },
            _ => {
                has_more = false;
            }
        }
    }

    hierarchy.insert_condition(condition);
    Ok(next_token)
}

fn parse_menu<I, LB>(hierarchy: &mut I, lexer: &mut LB) -> Result<Token, Error>
where
    I: MutableContainer,
    LB: LexerBase,
{
    // The next token needs to be the name of the menu
    let name_token = lexer.next_token();
    let mut menu = match name_token.term() {
        Lexicon::String(s) => match parse_string(&s) {
            Ok(v) => Menu::create(&v),
            Err(e) => return Err(Error::new(name_token.clone(), &e)),
        },
        _ => {
            return Err(Error::new(
                name_token.clone(),
                "Expected character string identifying the menu's name",
            ))
        }
    };

    let mut has_more = true;
    let mut next_token = lexer.next_token();
    // Loops over all the configuration options, until a non-conforming token is found, then
    // this token is handed back to parse_element
    while has_more {
        let start_token = next_token.clone();
        match start_token.term() {
            Lexicon::Help(s) => {
                menu.config().help.push_back(s);
                next_token = lexer.next_token();
            }
            Lexicon::Keyword(k) => match k {
                Keyword::Depends => {
                    // If the Keyword contains 'Depends', then the next keyword always needs
                    // to be 'On', if this is not the case, it is an error
                    next_token = lexer.next_token();
                    match next_token.term() {
                        Lexicon::Keyword(k) => match k {
                            Keyword::On => {
                                let (d, new_token) = parse_dependency(lexer)?;
                                menu.config().dependencies.insert(d);
                                next_token = new_token;
                            }
                            _ => {
                                return Err(Error::new(name_token.clone(), "Expected keyword 'on'"))
                            }
                        },
                        _ => return Err(Error::new(name_token.clone(), "Expected keyword 'on'")),
                    }
                }
                Keyword::Visible => {
                    // If the Keyword contains 'Visible', then the next keyword always needs
                    // to be 'If', if this is not the case, it is an error
                    next_token = lexer.next_token();
                    match next_token.term() {
                        Lexicon::Keyword(k) => match k {
                            Keyword::If => {
                                let (d, new_token) = parse_dependency(lexer)?;
                                menu.visible_if.insert(d);
                                next_token = new_token;
                            }
                            _ => {
                                return Err(Error::new(name_token.clone(), "Expected keyword 'if'"))
                            }
                        },
                        _ => return Err(Error::new(name_token.clone(), "Expected keyword 'if'")),
                    }
                }
                Keyword::Comment => next_token = parse_comment::<Menu, LB>(&mut menu, lexer)?,
                Keyword::Config => {
                    next_token = parse_config::<Menu, LB, ConfigElement>(&mut menu, lexer)?
                }
                Keyword::Menuconfig => {
                    next_token = parse_config::<Menu, LB, MenuConfigElement>(&mut menu, lexer)?
                }
                Keyword::Menu => {
                    // If this keyword is read, it will be a menu block. A menu block has a few items
                    // which a config or menu config does not have. Also, a menu bock ends with the
                    // endmenu.
                    // A menu block can have config and menu config items inside

                    next_token = parse_menu::<Menu, LB>(&mut menu, lexer)?;
                    // The next token must contain "endmenu"
                    match next_token.term() {
                        Lexicon::Keyword(k) => match k {
                            Keyword::Endmenu => next_token = lexer.next_token(),
                            _ => {
                                return Err(Error::new(
                                    next_token.clone(),
                                    "Keyword not expected, expected 'endmenu'",
                                ))
                            }
                        },
                        _ => return Err(Error::new(next_token.clone(), "Expected keyword")),
                    }
                }
                Keyword::If => {
                    // If this keyword is read, it will be a if block. A if block has a few items
                    // which a config or if config does not have. Also, a if bock ends with the
                    // endif.
                    // A if block can have config and if config items inside

                    next_token = parse_if::<Menu, LB>(&mut menu, lexer)?;
                    // The next token must contain "endif"
                    match next_token.term() {
                        Lexicon::Keyword(k) => match k {
                            Keyword::Endif => next_token = lexer.next_token(),
                            _ => {
                                return Err(Error::new(
                                    next_token.clone(),
                                    "Keyword not expected, expected 'endif'",
                                ))
                            }
                        },
                        _ => return Err(Error::new(next_token.clone(), "Expected keyword")),
                    }
                }
                _ => {
                    has_more = false;
                }
            },
            _ => {
                has_more = false;
            }
        }
    }

    menu.insert_into_hierarchy(hierarchy);
    Ok(next_token)
}

impl Ast {
    fn read_main_menu<LB>(&mut self, lexer: &mut LB) -> Result<Token, Error>
    where
        LB: LexerBase,
    {
        let t = lexer.next_token();
        match t.term() {
            Lexicon::Keyword(k) => match k {
                Keyword::Mainmenu => {
                    self.main_menu = match parse_string(&should_be_string(&lexer.next_token())?) {
                        Ok(v) => Some(v),
                        Err(e) => return Err(Error::new(t.clone(), &e)),
                    };
                    Ok(lexer.next_token())
                }
                _ => Ok(t),
            },
            _ => Ok(t),
        }
    }

    pub fn element(&self, name: &str) -> Option<&Element> {
        for (elt_name, elt) in &self.elements {
            if elt_name == name {
                return Some(&elt);
            }
        }
        None
    }

    pub fn contains_element(&self, name: &str) -> bool {
        match self.element(name) {
            Some(_) => true,
            None => false,
        }
    }

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

    fn parse_element<LB>(&mut self, token: Token, lexer: &mut LB) -> Result<Token, Error>
    where
        LB: LexerBase,
    {
        match token.term() {
            // The first token needs to be a keyword, precicely, it needs to be any of the following:
            // - config - Defines a newly defined configuration item within the current menu hierarchy
            // - menuconfig - Defines a newly defined configuration item, with possible suboptions
            // - choice - Defines a choice item, which only allows choice options (boolean or tristate)
            // - comment - Defines a comment item
            // - menu - Defines a new menu, which allows for a menu structure, it is not a configuration item
            // - if - Evaluates an expression, and if evaluated to true, replaces itself with its body
            // - source - Inserts the given source file (even when found within an if statement)
            Lexicon::Keyword(k) => match k {
                Keyword::Config => parse_config::<Ast, LB, ConfigElement>(self, lexer),
                Keyword::Menuconfig => parse_config::<Ast, LB, MenuConfigElement>(self, lexer),
                Keyword::Menu => {
                    // If this keyword is read, it will be a menu block. A menu block has a few items
                    // which a config or menu config does not have. Also, a menu bock ends with the
                    // endmenu.
                    // A menu block can have config and menu config items inside

                    let next_token = parse_menu::<Ast, LB>(self, lexer)?;
                    // The next token must contain "endmenu"
                    match next_token.term() {
                        Lexicon::Keyword(k) => match k {
                            Keyword::Endmenu => Ok(lexer.next_token()),
                            _ => Err(Error::new(next_token.clone(), "Keyword not expected, expected 'endmenu'"))
                        },
                        _ => Err(Error::new(next_token.clone(), "Expected keyword"))
                    }
                }
                Keyword::If => {
                    // If this keyword is read, it will be a if block. A if block has a few items
                    // which a config or if config does not have. Also, a if bock ends with the
                    // endif.
                    // A if block can have config and if config items inside

                    let next_token = parse_if::<Ast, LB>(self, lexer)?;
                    // The next token must contain "endif"
                    match next_token.term() {
                        Lexicon::Keyword(k) => match k {
                            Keyword::Endif => Ok(lexer.next_token()),
                            _ => Err(Error::new(next_token.clone(), "Keyword not expected, expected 'endif'"))
                        },
                        _ => Err(Error::new(next_token.clone(), "Expected keyword"))
                    }
                }
                Keyword::Comment => parse_comment(self, lexer),
                _ => Err(Error::new(token.clone(), "Keyword not expected, expected 'config', 'menuconfig', 'choice', 'comment', 'menu', 'if', 'source'"))
            },
            Lexicon::Error(e) => Err(Error::new(token.clone(), &format!("Erroneous element: {}", e))),
            _ => Err(Error::new(token.clone(), "Expected keyword"))
        }
    }

    fn read_actual<LB>(&mut self, lexer: &mut LB) -> Result<(), Error>
    where
        LB: LexerBase,
    {
        // The first token being read should either be the "mainmenu" token
        // followed by a string, or it should be a normal token.

        let mut next_token = self.read_main_menu(lexer)?;

        while !next_token.eot() {
            next_token = self.parse_element(next_token, lexer)?;
        }

        Ok(())
    }

    /// Creates an empty, non-usable Ast
    fn new() -> Self {
        Self {
            main_menu: None,
            elements: Vec::new(),
            comment: String::new(),
            conditions: Vec::new(),
        }
    }

    /// Parses the Ast from a stream which implements the Read trait.
    pub fn parse<LB>(input: &mut LB) -> Result<Self, Error>
    where
        LB: LexerBase,
    {
        let mut ast = Ast::new();
        ast.read_actual(input)?;
        Ok(ast)
    }

    pub fn main_menu(&self) -> Option<&String> {
        return self.main_menu.as_ref();
    }
}

#[cfg(test)]
mod tests {
    use super::super::super::lex::lexer::Lexer;
    use super::*;

    fn ast_from(s: &str) -> Result<Ast, Error> {
        let mut lexer = Lexer::create(s.as_bytes());
        Ok(Ast::parse(&mut lexer)?)
    }

    fn elements_vec_to_hashmap(v: Vec<(String, Element)>) -> HashMap<String, Element> {
        v.iter().map(|tuple| tuple.clone()).collect()
    }

    #[test]
    fn test_mainmenu() -> Result<(), Error> {
        let ast = ast_from(&"mainmenu \"Hello World\"")?;
        assert_eq!(ast.main_menu(), Some(&"Hello World".to_string()));
        Ok(())
    }

    #[test]
    fn test_parse_config() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_eq!(elt.elt_type(), ElementType::Config);
        Ok(())
    }

    #[test]
    fn test_parse_menuconfig() -> Result<(), Error> {
        let ast = ast_from(&"menuconfig MODVERSIONS")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_eq!(elt.elt_type(), ElementType::MenuConfig);
        Ok(())
    }

    #[test]
    fn test_parse_config_dependencies() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS depends on MODULES")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        let deps = elt.dependencies();
        assert_eq!(deps.len(), 1);
        let expected_dep = Dependency::new(&Expr::Sym("MODULES".to_string()));
        assert_eq!(deps.contains(&expected_dep), true);
        Ok(())
    }

    #[test]
    fn test_parse_config_multiple_dependencies() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS depends on FOO && BAR")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        let deps = elt.dependencies();
        assert_eq!(deps.len(), 1);
        let foo_subexpr = Expr::Sym("FOO".to_string());
        let bar_subexpr = Expr::Sym("BAR".to_string());
        for dep in deps {
            assert_eq!(dep.expr().is_and(), true);
            assert_eq!(dep.len(), 2);
            assert_eq!(dep.contains(&foo_subexpr), true);
            assert_eq!(dep.contains(&bar_subexpr), true);
        }
        Ok(())
    }

    #[test]
    fn test_parse_config_prompt() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS prompt \"Hello World\"")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_ne!(elt.prompt(), None);
        let prompt = elt.prompt().unwrap();
        assert_eq!(prompt, "Hello World".to_string());
        Ok(())
    }

    #[test]
    fn test_parse_bool() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \n prompt \"Hello World\" \nbool")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_ne!(elt.prompt(), None);
        let prompt = elt.prompt().unwrap();
        assert_eq!(prompt, "Hello World".to_string());
        assert_eq!(elt.types().unwrap().get(&ConfigType::Bool).unwrap(), &None);
        Ok(())
    }

    #[test]
    fn test_parse_bool_with_prompt() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \nbool \"Hello World\"")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_ne!(elt.prompt(), None);
        let prompt = elt.prompt().unwrap();
        assert_eq!(prompt, "Hello World".to_string());
        assert_eq!(elt.types().unwrap().get(&ConfigType::Bool).unwrap(), &None);
        Ok(())
    }

    #[test]
    fn test_parse_bool_with_if_dependency() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \nbool if FOO")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_eq!(elt.prompt(), None);
        let expected_dep = Dependency::new(&Expr::Sym("FOO".to_string()));
        assert_eq!(
            elt.types().unwrap().get(&ConfigType::Bool).unwrap(),
            &Some(expected_dep)
        );
        Ok(())
    }

    #[test]
    fn test_parse_bool_with_prompt_and_if_dependency() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \ntristate \"Hello World\" if FOO")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_ne!(elt.prompt(), None);
        let prompt = elt.prompt().unwrap();
        assert_eq!(prompt, "Hello World".to_string());
        let expected_dep = Dependency::new(&Expr::Sym("FOO".to_string()));
        assert_eq!(
            elt.types().unwrap().get(&ConfigType::Tristate).unwrap(),
            &Some(expected_dep)
        );
        Ok(())
    }

    #[test]
    fn test_parse_tristate() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \n prompt \"Hello World\" \ntristate")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_ne!(elt.prompt(), None);
        let prompt = elt.prompt().unwrap();
        assert_eq!(prompt, "Hello World".to_string());
        assert_eq!(
            elt.types().unwrap().get(&ConfigType::Tristate).unwrap(),
            &None
        );
        Ok(())
    }

    #[test]
    fn test_parse_tristate_with_prompt() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \ntristate \"Hello World\"")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_ne!(elt.prompt(), None);
        let prompt = elt.prompt().unwrap();
        assert_eq!(prompt, "Hello World".to_string());
        assert_eq!(
            elt.types().unwrap().get(&ConfigType::Tristate).unwrap(),
            &None
        );
        Ok(())
    }

    #[test]
    fn test_parse_tristate_with_if_dependency() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \ntristate if FOO")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_eq!(elt.prompt(), None);
        let expected_dep = Dependency::new(&Expr::Sym("FOO".to_string()));
        assert_eq!(
            elt.types().unwrap().get(&ConfigType::Tristate).unwrap(),
            &Some(expected_dep)
        );
        Ok(())
    }

    #[test]
    fn test_parse_tristate_with_prompt_and_if_dependency() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \ntristate \"Hello World\" if FOO")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_ne!(elt.prompt(), None);
        let prompt = elt.prompt().unwrap();
        assert_eq!(prompt, "Hello World".to_string());
        let expected_dep = Dependency::new(&Expr::Sym("FOO".to_string()));
        assert_eq!(
            elt.types().unwrap().get(&ConfigType::Tristate).unwrap(),
            &Some(expected_dep)
        );
        Ok(())
    }

    #[test]
    fn test_parse_string() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \n prompt \"Hello World\" \nstring")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_ne!(elt.prompt(), None);
        let prompt = elt.prompt().unwrap();
        assert_eq!(prompt, "Hello World".to_string());
        assert_eq!(
            elt.types().unwrap().get(&ConfigType::String).unwrap(),
            &None
        );
        Ok(())
    }

    #[test]
    fn test_parse_string_with_prompt() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \nstring \"Hello World\"")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_ne!(elt.prompt(), None);
        let prompt = elt.prompt().unwrap();
        assert_eq!(prompt, "Hello World".to_string());
        assert_eq!(
            elt.types().unwrap().get(&ConfigType::String).unwrap(),
            &None
        );
        Ok(())
    }

    #[test]
    fn test_parse_string_with_if_dependency() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \nstring if FOO")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_eq!(elt.prompt(), None);
        let expected_dep = Dependency::new(&Expr::Sym("FOO".to_string()));
        assert_eq!(
            elt.types().unwrap().get(&ConfigType::String).unwrap(),
            &Some(expected_dep)
        );
        Ok(())
    }

    #[test]
    fn test_parse_string_with_prompt_and_if_dependency() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \nstring \"Hello World\" if FOO")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_ne!(elt.prompt(), None);
        let prompt = elt.prompt().unwrap();
        assert_eq!(prompt, "Hello World".to_string());
        let expected_dep = Dependency::new(&Expr::Sym("FOO".to_string()));
        assert_eq!(
            elt.types().unwrap().get(&ConfigType::String).unwrap(),
            &Some(expected_dep)
        );
        Ok(())
    }

    #[test]
    fn test_parse_int() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \n prompt \"Hello World\" \nint")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_ne!(elt.prompt(), None);
        let prompt = elt.prompt().unwrap();
        assert_eq!(prompt, "Hello World".to_string());
        assert_eq!(elt.types().unwrap().get(&ConfigType::Int).unwrap(), &None);
        Ok(())
    }

    #[test]
    fn test_parse_int_with_prompt() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \nint \"Hello World\"")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_ne!(elt.prompt(), None);
        let prompt = elt.prompt().unwrap();
        assert_eq!(prompt, "Hello World".to_string());
        assert_eq!(elt.types().unwrap().get(&ConfigType::Int).unwrap(), &None);
        Ok(())
    }

    #[test]
    fn test_parse_int_with_if_dependency() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \nint if FOO")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_eq!(elt.prompt(), None);
        let expected_dep = Dependency::new(&Expr::Sym("FOO".to_string()));
        assert_eq!(
            elt.types().unwrap().get(&ConfigType::Int).unwrap(),
            &Some(expected_dep)
        );
        Ok(())
    }

    #[test]
    fn test_parse_int_with_prompt_and_if_dependency() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \nint \"Hello World\" if FOO")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_ne!(elt.prompt(), None);
        let prompt = elt.prompt().unwrap();
        assert_eq!(prompt, "Hello World".to_string());
        let expected_dep = Dependency::new(&Expr::Sym("FOO".to_string()));
        assert_eq!(
            elt.types().unwrap().get(&ConfigType::Int).unwrap(),
            &Some(expected_dep)
        );
        Ok(())
    }

    #[test]
    fn test_parse_hex() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \n prompt \"Hello World\" \nhex")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_ne!(elt.prompt(), None);
        let prompt = elt.prompt().unwrap();
        assert_eq!(prompt, "Hello World".to_string());
        assert_eq!(elt.types().unwrap().get(&ConfigType::Hex).unwrap(), &None);
        Ok(())
    }

    #[test]
    fn test_parse_hex_with_prompt() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \nhex \"Hello World\"")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_ne!(elt.prompt(), None);
        let prompt = elt.prompt().unwrap();
        assert_eq!(prompt, "Hello World".to_string());
        assert_eq!(elt.types().unwrap().get(&ConfigType::Hex).unwrap(), &None);
        Ok(())
    }

    #[test]
    fn test_parse_hex_with_if_dependency() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \nhex if FOO")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_eq!(elt.prompt(), None);
        let expected_dep = Dependency::new(&Expr::Sym("FOO".to_string()));
        assert_eq!(
            elt.types().unwrap().get(&ConfigType::Hex).unwrap(),
            &Some(expected_dep)
        );
        Ok(())
    }

    #[test]
    fn test_parse_hex_with_prompt_and_if_dependency() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \nhex \"Hello World\" if FOO")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_ne!(elt.prompt(), None);
        let prompt = elt.prompt().unwrap();
        assert_eq!(prompt, "Hello World".to_string());
        let expected_dep = Dependency::new(&Expr::Sym("FOO".to_string()));
        assert_eq!(
            elt.types().unwrap().get(&ConfigType::Hex).unwrap(),
            &Some(expected_dep)
        );
        Ok(())
    }

    #[test]
    fn test_parse_default() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \n default y")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_eq!(
            elt.defaults()
                .unwrap()
                .get(&Expr::Sym("y".to_string()))
                .unwrap(),
            &None
        );
        Ok(())
    }

    #[test]
    fn test_parse_default_string() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \n default \"y\"")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_eq!(
            elt.defaults()
                .unwrap()
                .get(&Expr::Sym("y".to_string()))
                .unwrap(),
            &None
        );
        Ok(())
    }

    #[test]
    fn test_parse_default_with_if_dependency() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \nbool default y if FOO")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        let key = Expr::Sym("y".to_string());
        let expected_dep = Dependency::new(&Expr::Sym("FOO".to_string()));
        assert_eq!(
            elt.defaults().unwrap().get(&key).unwrap(),
            &Some(expected_dep)
        );
        Ok(())
    }

    #[test]
    fn test_parse_def_bool() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \n def_bool y")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_eq!(elt.types().unwrap().get(&ConfigType::Bool).unwrap(), &None);
        assert_eq!(
            elt.defaults()
                .unwrap()
                .get(&Expr::Sym("y".to_string()))
                .unwrap(),
            &None
        );
        Ok(())
    }

    #[test]
    fn test_parse_def_bool_with_dependency() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \ndef_bool y if FOO")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        let expected_dep = Dependency::new(&Expr::Sym("FOO".to_string()));
        assert_eq!(
            elt.types().unwrap().get(&ConfigType::Bool).unwrap(),
            &Some(expected_dep.clone())
        );
        let key = Expr::Sym("y".to_string());
        assert_eq!(
            elt.defaults().unwrap().get(&key).unwrap(),
            &Some(expected_dep)
        );
        Ok(())
    }

    #[test]
    fn test_parse_def_tristate() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \n def_tristate y")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_eq!(
            elt.types().unwrap().get(&ConfigType::Tristate).unwrap(),
            &None
        );
        assert_eq!(
            elt.defaults()
                .unwrap()
                .get(&Expr::Sym("y".to_string()))
                .unwrap(),
            &None
        );
        Ok(())
    }

    #[test]
    fn test_parse_def_tristate_with_dependency() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \ndef_tristate y if FOO")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        let expected_dep = Dependency::new(&Expr::Sym("FOO".to_string()));
        assert_eq!(
            elt.types().unwrap().get(&ConfigType::Tristate).unwrap(),
            &Some(expected_dep.clone())
        );
        let key = Expr::Sym("y".to_string());
        assert_eq!(
            elt.defaults().unwrap().get(&key).unwrap(),
            &Some(expected_dep)
        );
        Ok(())
    }

    #[test]
    fn test_parse_select() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \n select y")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_eq!(
            elt.reverse_dependencies()
                .unwrap()
                .get(&"y".to_string())
                .unwrap(),
            &None
        );
        Ok(())
    }

    #[test]
    fn test_parse_select_with_dependency() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \nselect y if FOO")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        let expected_dep = Dependency::new(&Expr::Sym("FOO".to_string()));
        assert_eq!(
            elt.reverse_dependencies()
                .unwrap()
                .get(&"y".to_string())
                .unwrap(),
            &Some(expected_dep)
        );
        Ok(())
    }

    #[test]
    fn test_parse_imply() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \n imply y")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_eq!(
            elt.weak_dependencies()
                .unwrap()
                .get(&"y".to_string())
                .unwrap(),
            &None
        );
        Ok(())
    }

    #[test]
    fn test_parse_imply_with_dependency() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \nimply y if FOO")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        let expected_dep = Dependency::new(&Expr::Sym("FOO".to_string()));
        assert_eq!(
            elt.weak_dependencies()
                .unwrap()
                .get(&"y".to_string())
                .unwrap(),
            &Some(expected_dep)
        );
        Ok(())
    }

    #[test]
    fn test_parse_range() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \n range 1 2")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_eq!(elt.range().unwrap().lhs(), 1);
        assert_eq!(elt.range().unwrap().rhs(), 2);
        assert_eq!(elt.range().unwrap().dependency(), &None);
        Ok(())
    }

    #[test]
    fn test_negative_to_positive_range() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \n range -1 1")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_eq!(elt.range().unwrap().lhs(), -1);
        assert_eq!(elt.range().unwrap().rhs(), 1);
        assert_eq!(elt.range().unwrap().dependency(), &None);
        Ok(())
    }

    #[test]
    fn test_negative_range() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \n range -2 -1")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_eq!(elt.range().unwrap().lhs(), -2);
        assert_eq!(elt.range().unwrap().rhs(), -1);
        assert_eq!(elt.range().unwrap().dependency(), &None);
        Ok(())
    }

    #[test]
    fn test_parse_range_with_dependency() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \nrange 1 2 if FOO")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        let expected_dep = Dependency::new(&Expr::Sym("FOO".to_string()));
        assert_eq!(elt.range().unwrap().lhs(), 1);
        assert_eq!(elt.range().unwrap().rhs(), 2);
        assert_eq!(elt.range().unwrap().dependency(), &Some(expected_dep));
        Ok(())
    }

    #[test]
    fn test_parse_help() -> Result<(), Error> {
        let ast = ast_from(&"config MODVERSIONS \nhelp\n    foo\n    bar\n")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("MODVERSIONS"), true);
        let elt = ast.element("MODVERSIONS").unwrap();
        assert_eq!(
            elt.help().into_iter().next().unwrap(),
            "foo\nbar".to_string()
        );
        Ok(())
    }

    #[test]
    fn test_parse_comment() -> Result<(), Error> {
        let ast = ast_from(&"comment \"Foo\"")?;

        assert_eq!(ast.comment(), "Foo".to_string());
        Ok(())
    }

    #[test]
    fn test_parse_simple_if() -> Result<(), Error> {
        let ast = ast_from(&"if FOO endif")?;

        assert_eq!(ast.len_conditional_blocks(), 1);
        let expected_dep = Dependency::new(&Expr::Sym("FOO".to_string()));
        let mut passes = 0;
        for block in ast.conditional_blocks() {
            assert_eq!(block.dependency(), expected_dep);
            passes += 1;
        }
        assert_eq!(passes, 1);
        Ok(())
    }

    #[test]
    fn test_simple_menu() -> Result<(), Error> {
        let ast = ast_from(&"menu \"Menu\"\nendmenu")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("Menu"), true);
        let elt = ast.element("Menu").unwrap();
        assert_eq!(elt.elt_type(), ElementType::Menu);
        Ok(())
    }

    #[test]
    fn test_menu_depends_on() -> Result<(), Error> {
        let ast = ast_from(&"menu \"Menu\" depends on MODULES \nendmenu")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("Menu"), true);
        let elt = ast.element("Menu").unwrap();
        let deps = elt.dependencies();
        assert_eq!(deps.len(), 1);
        let expected_dep = Dependency::new(&Expr::Sym("MODULES".to_string()));
        assert_eq!(deps.contains(&expected_dep), true);
        Ok(())
    }

    #[test]
    fn test_menu_visible_if() -> Result<(), Error> {
        let ast = ast_from(&"menu \"Menu\" visible if MODULES \nendmenu")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("Menu"), true);
        let elt = ast.element("Menu").unwrap();
        let visible_deps = elt.visible_if();
        assert_eq!(visible_deps.len(), 1);
        let expected_dep = Dependency::new(&Expr::Sym("MODULES".to_string()));
        assert_eq!(visible_deps.contains(&expected_dep), true);
        Ok(())
    }

    #[test]
    fn test_menu_with_config() -> Result<(), Error> {
        let ast = ast_from(&"menu \"Menu\" config FOO \nendmenu")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("Menu"), true);
        let elt = ast.element("Menu").unwrap();
        let sub_elements = elements_vec_to_hashmap(elt.sub_elements());
        assert_eq!(sub_elements.len(), 1);
        assert_eq!(sub_elements.contains_key("FOO"), true);
        let sub_elt = sub_elements.get("FOO").unwrap();
        assert_eq!(sub_elt.elt_type(), ElementType::Config);
        assert_eq!(sub_elt.name(), "FOO".to_string());
        Ok(())
    }

    #[test]
    fn test_menu_with_menuconfig() -> Result<(), Error> {
        let ast = ast_from(&"menu \"Menu\" menuconfig FOO \nendmenu")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("Menu"), true);
        let elt = ast.element("Menu").unwrap();
        let sub_elements = elements_vec_to_hashmap(elt.sub_elements());
        assert_eq!(sub_elements.len(), 1);
        assert_eq!(sub_elements.contains_key("FOO"), true);
        let sub_elt = sub_elements.get("FOO").unwrap();
        assert_eq!(sub_elt.elt_type(), ElementType::MenuConfig);
        assert_eq!(sub_elt.name(), "FOO".to_string());
        Ok(())
    }

    #[test]
    fn test_menu_with_submenu() -> Result<(), Error> {
        let ast = ast_from(&"menu \"Menu\"\nmenu \"Submenu\" endmenu \nendmenu")?;

        assert_eq!(ast.len(), 1);
        assert_eq!(ast.contains_element("Menu"), true);
        let elt = ast.element("Menu").unwrap();
        let sub_elements = elements_vec_to_hashmap(elt.sub_elements());
        assert_eq!(sub_elements.len(), 1);
        assert_eq!(sub_elements.contains_key("Submenu"), true);
        let sub_elt = sub_elements.get("Submenu").unwrap();
        assert_eq!(sub_elt.elt_type(), ElementType::Menu);
        assert_eq!(sub_elt.name(), "Submenu".to_string());
        Ok(())
    }

    #[test]
    fn test_menu_comment() -> Result<(), Error> {
        let ast = ast_from(&"menu \"Menu\" comment \"Foo\" endmenu")?;

        let elt = ast.element("Menu").unwrap();
        assert_eq!(elt.elt_type(), ElementType::Menu);
        if let Element::Menu(menu) = elt {
            assert_eq!(menu.comment(), "Foo".to_string());
        }
        Ok(())
    }

    #[test]
    fn test_menu_simple_if() -> Result<(), Error> {
        let ast = ast_from(&"menu \"Menu\" if FOO endif endmenu")?;

        assert_eq!(ast.contains_element("Menu"), true);
        let elt = ast.element("Menu").unwrap();
        assert_eq!(elt.len_conditional_blocks(), 1);
        let expected_dep = Dependency::new(&Expr::Sym("FOO".to_string()));
        let mut passes = 0;
        for block in elt.conditional_blocks() {
            assert_eq!(block.dependency(), expected_dep);
            passes += 1;
        }
        assert_eq!(passes, 1);
        Ok(())
    }

    #[test]
    fn test_if_with_config() -> Result<(), Error> {
        let ast = ast_from(&"if CONDITION \n config FOO \n endif")?;

        assert_eq!(ast.len_conditional_blocks(), 1);
        let expected_dep = Dependency::new(&Expr::Sym("CONDITION".to_string()));
        let mut passes = 0;
        for block in ast.conditional_blocks() {
            assert_eq!(block.dependency(), expected_dep);
            let sub_elements = elements_vec_to_hashmap(block.elements());
            assert_eq!(sub_elements.len(), 1);
            assert_eq!(sub_elements.contains_key("FOO"), true);
            let sub_elt = sub_elements.get("FOO").unwrap();
            assert_eq!(sub_elt.elt_type(), ElementType::Config);
            assert_eq!(sub_elt.name(), "FOO".to_string());
            passes += 1;
        }
        assert_eq!(passes, 1);
        Ok(())
    }

    #[test]
    fn test_if_with_menuconfig() -> Result<(), Error> {
        let ast = ast_from(&"if CONDITION\n menuconfig FOO \n endif")?;

        assert_eq!(ast.len_conditional_blocks(), 1);
        let expected_dep = Dependency::new(&Expr::Sym("CONDITION".to_string()));
        let mut passes = 0;
        for block in ast.conditional_blocks() {
            assert_eq!(block.dependency(), expected_dep);
            let sub_elements = elements_vec_to_hashmap(block.elements());
            assert_eq!(sub_elements.len(), 1);
            assert_eq!(sub_elements.contains_key("FOO"), true);
            let sub_elt = sub_elements.get("FOO").unwrap();
            assert_eq!(sub_elt.elt_type(), ElementType::MenuConfig);
            assert_eq!(sub_elt.name(), "FOO".to_string());
            passes += 1;
        }
        assert_eq!(passes, 1);
        Ok(())
    }

    #[test]
    fn test_if_with_subif() -> Result<(), Error> {
        let ast = ast_from(&"if CONDITION if CONDITION2 endif endif")?;

        assert_eq!(ast.len_conditional_blocks(), 1);
        let mut passes = 0;
        for block in ast.conditional_blocks() {
            assert_eq!(block.len_conditional_blocks(), 1);
            passes += 1;
        }
        assert_eq!(passes, 1);
        Ok(())
    }

    #[test]
    fn test_nameless_mainmenu() -> Result<(), Error> {
        let ast = ast_from(&"")?;
        assert_eq!(ast.main_menu(), None);
        Ok(())
    }
}