kconfig-parser 0.1.1

/*
 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 for expressions in a Kconfig file.
//! It is used eventually by the dependency parser and on certain
//! other places.

use super::parser::Error;
use super::structs::*;
use crate::{
    lex::{structs::*, LexerBase},
    parse_string,
};
use std::collections::BTreeSet;

#[derive(Eq, PartialEq, Copy, Clone, Debug)]
enum Operator {
    Eq,
    Ne,
    Lt,
    Gt,
    Lte,
    Gte,
    And,
    Or,
}

impl Operator {
    fn get_precedence_number(&self) -> u8 {
        match self {
            Self::Lt | Self::Gt | Self::Lte | Self::Gte => 255,
            Self::Eq | Self::Ne => 127,
            Self::And => 63,
            Self::Or => 0,
        }
    }
}

fn parse_single<LB>(lexer: &mut LB, first_pass: bool) -> Result<(Option<Expr>, Token), Error>
where
    LB: LexerBase,
{
    let token = lexer.next_token();
    match token.term() {
        // If the token starts with an exclamation mark, then it is a negation
        // of the next token.
        Lexicon::Not => {
            let neg_token = lexer.next_token();
            // If the new token is an negation, start interior parsing
            // otherwise, it must be an identifier.
            match neg_token.term() {
                Lexicon::String(s) => match parse_string(&s) {
                    Ok(s) => Ok((Some(Expr::Not(Box::new(Expr::Sym(s)))), lexer.next_token())),
                    Err(e) => Err(Error::from(Error::new(token, &e))),
                },
                Lexicon::Identifier(s) => {
                    Ok((Some(Expr::Not(Box::new(Expr::Sym(s)))), lexer.next_token()))
                }
                Lexicon::Open => {
                    let (expr, token) = parse_interior(None, BTreeSet::new(), false, lexer)?;
                    match token.term() {
                        Lexicon::Close => Ok((
                            Some(Expr::Not(Box::new(Expr::Sub(Box::new(expr.unwrap()))))),
                            lexer.next_token(),
                        )),
                        _ => Err(Error::new(token.clone(), "Expected ')'")),
                    }
                }
                _ => Err(Error::new(token.clone(), "Expected identifier or '('")),
            }
        }

        // If the token starts with an open parentheses, then it is a subexpression
        Lexicon::Open => {
            let (expr, token) = parse_interior(None, BTreeSet::new(), false, lexer)?;
            match token.term() {
                Lexicon::Close => {
                    Ok((Some(Expr::Sub(Box::new(expr.unwrap()))), lexer.next_token()))
                }
                _ => Err(Error::new(token.clone(), "Expected ')'")),
            }
        }

        // If a token is a string, it will be converted to a symbol
        Lexicon::String(s) => match parse_string(&s) {
            Ok(s) => Ok((Some(Expr::Sym(s)), lexer.next_token())),
            Err(e) => Err(Error::from(Error::new(token, &e))),
        },

        // If a token is an identifier, it will be a symbol
        Lexicon::Identifier(s) => Ok((Some(Expr::Sym(s)), lexer.next_token())),

        _ => {
            if !first_pass {
                Err(Error::new(
                    token.clone(),
                    "Expected identifier, '$(', '(', '!'",
                ))
            } else {
                Ok((None, token))
            }
        }
    }
}

pub(super) fn parse<LB>(lexer: &mut LB) -> Result<(Option<Expr>, Token), Error>
where
    LB: LexerBase,
{
    parse_interior(None, BTreeSet::new(), true, lexer)
}

// Wraps an operator and set into a single expression type
fn wrap_operator_and_set(o: Operator, set: BTreeSet<Expr>) -> Expr {
    match o {
        Operator::And => Expr::And(set),
        Operator::Or => Expr::Or(set),
        Operator::Lt => Expr::Lt(set),
        Operator::Lte => Expr::Lte(set),
        Operator::Gt => Expr::Gt(set),
        Operator::Gte => Expr::Gte(set),
        Operator::Eq => Expr::Eq(set),
        Operator::Ne => Expr::Ne(set),
    }
}

// Converts an equality operator to an internal operator representatio
fn equality_operator_to_operator(eqo: EqualityOperator) -> Operator {
    match eqo {
        EqualityOperator::Gt => Operator::Gt,
        EqualityOperator::Gte => Operator::Gte,
        EqualityOperator::Lt => Operator::Lt,
        EqualityOperator::Lte => Operator::Lte,
        EqualityOperator::Eq => Operator::Eq,
        EqualityOperator::Ne => Operator::Ne,
    }
}

// Converts a token to an operator, if it is an operator
fn token_to_operator(token: &Token) -> Option<Operator> {
    let term = token.term();
    match term {
        Lexicon::EqualityOperator(eqo) => Some(equality_operator_to_operator(eqo)),
        Lexicon::And => Some(Operator::And),
        Lexicon::Or => Some(Operator::Or),
        _ => None,
    }
}

fn parse_interior<LB>(
    mut initial_operator: Option<Operator>,
    mut set: BTreeSet<Expr>,
    mut first_pass: bool,
    lexer: &mut LB,
) -> Result<(Option<Expr>, Token), Error>
where
    LB: LexerBase,
{
    loop {
        let (expr, maybe_operator_token) = parse_single(lexer, first_pass)?;
        match expr {
            None => break Ok((None, maybe_operator_token)),
            Some(expr) => {
                first_pass = false;
                let maybe_operator = token_to_operator(&maybe_operator_token);
                match maybe_operator {
                    Some(current_operator) => {
                        // If the last operator is None, then it is easy, it will become
                        // the current operator, if it is the same, it is also easy, nothing
                        // will happen. If it is however different, then the precedence rules
                        // need to be properly calculated.
                        match initial_operator {
                            None => {
                                initial_operator = Some(current_operator);
                                set.insert(expr);
                            }
                            Some(last) => {
                                if last != current_operator {
                                    let precedes = last.get_precedence_number()
                                        < current_operator.get_precedence_number();
                                    // Here it becomes difficult. We need to know whether the
                                    // current operator precedes the last operator;
                                    // or when the last operator either precedes the current
                                    // operator or is similar to the current operator.
                                    if precedes {
                                        // This is the simple variant,
                                        // the next part is to be parsed independently, with the
                                        // last token from the set moved to the new parser
                                        let mut sub_set = BTreeSet::new();
                                        sub_set.insert(expr);
                                        let (sub_expr, sub_token) = parse_interior(
                                            Some(current_operator),
                                            sub_set,
                                            false,
                                            lexer,
                                        )?;
                                        set.insert(sub_expr.unwrap());
                                        let final_expr = wrap_operator_and_set(last, set);
                                        // We should be ending here, as the interior parser will have parsed
                                        // until the end.
                                        break Ok((Some(final_expr), sub_token));
                                    } else {
                                        // The current set is to be placed into a single expression subset,
                                        // and a new subset with the current operator is to be created
                                        set.insert(expr);
                                        let sub_expr = wrap_operator_and_set(last, set.clone());
                                        set.clear();
                                        set.insert(sub_expr);
                                        initial_operator = Some(current_operator);
                                    }
                                } else {
                                    set.insert(expr);
                                }
                            }
                        }
                    }
                    None => {
                        break Ok((
                            Some({
                                // If reached, and the set is not filled, it is a symbol,
                                // otherwise this symbol needs to be added to the list, and
                                // the list needs to be returned as the apporiate Expr for
                                // the given operator.
                                match initial_operator {
                                    None => {
                                        if set.len() > 0 {
                                            return Err(Error::new(
                                                maybe_operator_token.clone(),
                                                "Operator expected if set length > 0",
                                            ));
                                        } else {
                                            expr
                                        }
                                    }
                                    Some(o) => {
                                        set.insert(expr);
                                        wrap_operator_and_set(o, set)
                                    }
                                }
                            }),
                            maybe_operator_token,
                        ));
                    }
                }
            }
        }
    }
}

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

    #[test]
    fn test_simple_symbol() -> Result<(), Error> {
        let input = &mut "FOO".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_sym(), true);
        assert_eq!(expr.get_sym().unwrap(), "FOO".to_string());
        assert_eq!(expr, Expr::Sym("FOO".to_string()));
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_simple_string_symbol() -> Result<(), Error> {
        let input = &mut "\"FOO\"".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_sym(), true);
        assert_eq!(expr.get_sym().unwrap(), "FOO".to_string());
        assert_eq!(expr, Expr::Sym("FOO".to_string()));
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_simple_numeric_symbol() -> Result<(), Error> {
        let input = &mut "123".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_sym(), true);
        assert_eq!(expr.get_sym().unwrap(), "123".to_string());
        assert_eq!(expr, Expr::Sym("123".to_string()));
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_simple_negative_numeric_symbol() -> Result<(), Error> {
        let input = &mut "-123".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_sym(), true);
        assert_eq!(expr.get_sym().unwrap(), "-123".to_string());
        assert_eq!(expr, Expr::Sym("-123".to_string()));
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_simple_hexadecimal_symbol() -> Result<(), Error> {
        let input = &mut "0x123".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_sym(), true);
        assert_eq!(expr.get_sym().unwrap(), "0x123".to_string());
        assert_eq!(expr, Expr::Sym("0x123".to_string()));
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_simple_negative_hexadecimal_symbol() -> Result<(), Error> {
        let input = &mut "-0x123".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_sym(), true);
        assert_eq!(expr.get_sym().unwrap(), "-0x123".to_string());
        assert_eq!(expr, Expr::Sym("-0x123".to_string()));
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_simple_negation() -> Result<(), Error> {
        let input = &mut "!FOO".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_not(), true);
        assert_eq!(expr.get_not_expr().unwrap(), Expr::Sym("FOO".to_string()));
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_simple_sub() -> Result<(), Error> {
        let input = &mut "(FOO)".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_sub(), true);
        assert_eq!(expr.get_sub_expr().unwrap(), Expr::Sym("FOO".to_string()));
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_not_with_sub() -> Result<(), Error> {
        let input = &mut "!(FOO)".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_not(), true);
        let expr = expr.get_not_expr().unwrap();
        assert_eq!(expr.is_sub(), true);
        assert_eq!(expr.get_sub_expr().unwrap(), Expr::Sym("FOO".to_string()));
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_sub_with_not() -> Result<(), Error> {
        let input = &mut "(!FOO)".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_sub(), true);
        let expr = expr.get_sub_expr().unwrap();
        assert_eq!(expr.is_not(), true);
        assert_eq!(expr.get_not_expr().unwrap(), Expr::Sym("FOO".to_string()));
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_simple_eq() -> Result<(), Error> {
        let input = &mut "FOO == BAR".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_comparison(), true);
        assert_eq!(expr.is_eq(), true);
        assert_eq!(expr.len(), 2);
        let mut counter: usize = 0;
        for sub_expr in expr.clone() {
            assert_eq!(sub_expr.is_sym(), true);
            counter = counter + 1;
        }
        assert_eq!(counter, expr.len());
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_simple_ne() -> Result<(), Error> {
        let input = &mut "FOO != BAR".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_comparison(), true);
        assert_eq!(expr.is_ne(), true);
        assert_eq!(expr.len(), 2);
        let mut counter: usize = 0;
        for sub_expr in expr.clone() {
            assert_eq!(sub_expr.is_sym(), true);
            counter = counter + 1;
        }
        assert_eq!(counter, expr.len());
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_simple_lt() -> Result<(), Error> {
        let input = &mut "FOO < BAR".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_comparison(), true);
        assert_eq!(expr.is_lt(), true);
        assert_eq!(expr.len(), 2);
        let mut counter: usize = 0;
        for sub_expr in expr.clone() {
            assert_eq!(sub_expr.is_sym(), true);
            counter = counter + 1;
        }
        assert_eq!(counter, expr.len());
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_simple_gt() -> Result<(), Error> {
        let input = &mut "FOO > BAR".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_comparison(), true);
        assert_eq!(expr.is_gt(), true);
        assert_eq!(expr.len(), 2);
        let mut counter: usize = 0;
        for sub_expr in expr.clone() {
            assert_eq!(sub_expr.is_sym(), true);
            counter = counter + 1;
        }
        assert_eq!(counter, expr.len());
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_simple_lte() -> Result<(), Error> {
        let input = &mut "FOO <= BAR".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_comparison(), true);
        assert_eq!(expr.is_lte(), true);
        assert_eq!(expr.len(), 2);
        let mut counter: usize = 0;
        for sub_expr in expr.clone() {
            assert_eq!(sub_expr.is_sym(), true);
            counter = counter + 1;
        }
        assert_eq!(counter, expr.len());
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_simple_gte() -> Result<(), Error> {
        let input = &mut "FOO >= BAR".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_comparison(), true);
        assert_eq!(expr.is_gte(), true);
        assert_eq!(expr.len(), 2);
        let mut counter: usize = 0;
        for sub_expr in expr.clone() {
            assert_eq!(sub_expr.is_sym(), true);
            counter = counter + 1;
        }
        assert_eq!(counter, expr.len());
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_simple_and() -> Result<(), Error> {
        let input = &mut "FOO && BAR".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_comparison(), true);
        assert_eq!(expr.is_and(), true);
        assert_eq!(expr.len(), 2);
        let mut counter: usize = 0;
        for sub_expr in expr.clone() {
            assert_eq!(sub_expr.is_sym(), true);
            counter = counter + 1;
        }
        assert_eq!(counter, expr.len());
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_simple_or() -> Result<(), Error> {
        let input = &mut "FOO || BAR".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_comparison(), true);
        assert_eq!(expr.is_or(), true);
        assert_eq!(expr.len(), 2);
        let mut counter: usize = 0;
        for sub_expr in expr.clone() {
            assert_eq!(sub_expr.is_sym(), true);
            counter = counter + 1;
        }
        assert_eq!(counter, expr.len());
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_and_then_or() -> Result<(), Error> {
        // HAM && SPAM Should be evaluated prior to SPAM || EGGS,
        // Therefore, HAM && SPAM are a subexpression
        let input = &mut "HAM && SPAM || EGGS".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_comparison(), true);
        assert_eq!(expr.is_or(), true);
        assert_eq!(expr.len(), 2);
        let mut count_is_and = 0;
        let mut count_is_not_and = 0;
        for sub_expr in expr.clone() {
            if sub_expr.is_and() {
                count_is_and = count_is_and + 1;
            } else {
                count_is_not_and = count_is_not_and + 1;
            }
        }
        assert_eq!(count_is_and, 1);
        assert_eq!(count_is_not_and, 1);
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_or_then_and() -> Result<(), Error> {
        // HAM || SPAM Should be evaluated prior to SPAM && EGGS,
        // Therefore, SPAM && EGGS are a subexpression
        let input = &mut "HAM || SPAM && EGGS".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_comparison(), true);
        assert_eq!(expr.is_or(), true);
        assert_eq!(expr.len(), 2);
        let mut count_is_and = 0;
        let mut count_is_not_and = 0;
        for sub_expr in expr.clone() {
            if sub_expr.is_and() {
                count_is_and = count_is_and + 1;
            } else {
                count_is_not_and = count_is_not_and + 1;
            }
        }
        assert_eq!(count_is_and, 1);
        assert_eq!(count_is_not_and, 1);
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_or_then_lt_then_and() -> Result<(), Error> {
        // Expected evaluation is:
        // HAM || ((SPAM < EGGS) && BACON)
        let input = &mut "HAM || SPAM < EGGS && BACON".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_comparison(), true);
        assert_eq!(expr.is_or(), true);
        assert_eq!(expr.len(), 2);
        let mut count_is_and = 0;
        let mut count_is_lt = 0;
        let mut count_is_not_and = 0;
        for sub_expr in expr.clone() {
            if sub_expr.is_and() {
                count_is_and += 1;
                for subsub_expr in sub_expr.clone() {
                    if subsub_expr.is_lt() {
                        count_is_lt += 1;
                    }
                }
            } else {
                count_is_not_and += 1;
            }
        }
        assert_eq!(count_is_lt, 1);
        assert_eq!(count_is_and, 1);
        assert_eq!(count_is_not_and, 1);
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }

    #[test]
    fn test_or_then_lt_then_paren_and() -> Result<(), Error> {
        // Expected evaluation is:
        // HAM || (SPAM < (EGGS && BACON))
        let input = &mut "HAM || SPAM < (EGGS && BACON)".as_bytes();
        let mut lexer = Lexer::create(input);
        let (expr, token) = parse(&mut lexer)?;
        let expr = expr.unwrap();
        assert_eq!(expr.is_comparison(), true);
        assert_eq!(expr.is_or(), true);
        assert_eq!(expr.len(), 2);
        let mut count_is_sub = 0;
        let mut count_is_lt = 0;
        let mut count_is_normal = 0;
        for sub_expr in expr.clone() {
            if sub_expr.is_lt() {
                count_is_lt += 1;
                for subsub_expr in sub_expr.clone() {
                    if subsub_expr.is_sub() {
                        count_is_sub += 1;
                    }
                }
            } else {
                count_is_normal += 1;
            }
        }
        assert_eq!(count_is_lt, 1);
        assert_eq!(count_is_sub, 1);
        assert_eq!(count_is_normal, 1);
        assert_eq!(token.term(), Lexicon::EOT);
        Ok(())
    }
}