kconfig_parser/lex/

macro_lexer.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 macro lexer, which behaves like a regular lexer,
//! but captures all macro statements and evaluates them.

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

use super::{
    structs::{Lexicon, Token},
    LexerBase,
};

#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Symbol {
    name: String,
    line: usize,
    column: usize,
    value: String,
}

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

impl Symbol {
    pub fn name(&self) -> String {
        self.name.to_string()
    }

    pub fn value(&self) -> String {
        self.value.to_string()
    }
}

/// The macro lexer interprets and evaluates assignment statements and
/// expressions.
pub struct MacroLexer<LB, U>
where
    LB: LexerBase,
    U: Clone,
{
    /// This table composes the found symbols and their assignments.
    symbol_table: HashSet<Symbol>,

    /// This is the foundation lexer on which the macro lexer applies
    /// macro interpretation
    base_lexer: LB,

    /// A queue is used to contain specified tokens for look-ahead
    /// purposes, this queue contains already expanded tokens.
    expanded_q: VecDeque<Token>,

    /// A queue is used to contain specified tokens for look-ahead
    /// purposes, this queue contains not expanded tokens.
    raw_q: VecDeque<Token>,

    /// A map of functions which can be executed. The first parameter
    /// contains the arguments to the macro, the second parameter the
    /// file/stream name, where applicable, the third and fourth
    /// parameters the row and column of the cursor and finally the
    /// user object as created while constructing the Macro lexer
    functions:
        HashMap<String, fn(Vec<String>, &str, usize, usize, &U) -> Result<Vec<Lexicon>, String>>,

    /// A user struct, object or value which can be used by the
    /// functions to utilize behavior defined on it.
    user_object: U,
}

impl<LB, U> MacroLexer<LB, U>
where
    LB: LexerBase,
    U: Clone,
{
    /// Creates a new macro lexer, given an original base lexer. This
    /// will interpret all tokens necessary for macro interpretation
    /// and expansion, and result into tokens specific for the user
    /// of this lexer.
    pub fn new(base_lexer: LB, user_object: &U) -> Self {
        Self {
            symbol_table: HashSet::new(),
            base_lexer,
            expanded_q: VecDeque::new(),
            raw_q: VecDeque::new(),
            functions: HashMap::new(),
            user_object: user_object.clone(),
        }
    }

    /// Retrieves the symbol table to be used apart from the Macro Lexer
    pub fn symbol_table(&self) -> HashSet<Symbol> {
        self.symbol_table.clone()
    }

    /// Adds a macro function to be able to be called by the interpreter
    pub fn add_fn(
        &mut self,
        name: &str,
        func: fn(Vec<String>, &str, usize, usize, &U) -> Result<Vec<Lexicon>, String>,
    ) {
        self.functions.insert(name.to_string(), func);
    }

    /// Interprets a macro call, typically only existing out of either
    /// identifiers or commas.
    fn interpret(&mut self, mut tokens: VecDeque<Token>) -> Vec<Token> {
        // If the first identifier starts with "call", contains a space
        // and further characters, it is a call macro, and needs to
        // be separated from the rest of the macro call.
        let mut is_call = false;

        let token = match tokens.front() {
            Some(t) => {
                let (c, t) = is_call_token(t);
                is_call = c;
                if is_call {
                    tokens.pop_front();
                    tokens.push_front(t.clone());
                };
                t
            }
            _ => Token::create_eot(0, 0),
        };

        let mut identifiers = match macro_simplify(&tokens) {
            Ok(i) => i,
            Err(s) => return vec![create_error(&tokens, s)],
        };

        if identifiers.len() == 1 && !is_call {
            let identifier = identifiers.front().unwrap();
            for symbol in &self.symbol_table {
                if symbol.name.eq(identifier) {
                    let value = &symbol.value;
                    let (column, line) = get_tokens_column_line(&tokens);
                    return vec![Token::create(
                        Lexicon::Identifier(value.to_string()),
                        column,
                        line,
                        value,
                    )];
                };
            }
        };

        if identifiers.len() > 0 {
            let name = identifiers.pop_front().unwrap();
            let result = match self.functions.get(&name) {
                Some(f) => {
                    let arguments = Vec::from_iter(identifiers);
                    let line = token.line();
                    let column = token.column();
                    let stream = self.base_lexer.current_stream();
                    match f(
                        arguments,
                        &stream.unwrap_or_default(),
                        line,
                        column,
                        &self.user_object,
                    ) {
                        Ok(s) => s,
                        Err(s) => {
                            return vec![create_error(
                                &tokens,
                                &format!("Expansion {} failed: {}", name, s),
                            )]
                        }
                    }
                }
                None => {
                    return vec![create_error(
                        &tokens,
                        &format!("Expansion with name {} not found", name),
                    )]
                }
            };

            let (column, line) = get_tokens_column_line(&tokens);

            return result
                .iter()
                .map(|l| Token::create(l.clone(), column, line, &l.to_string()))
                .collect();
        }

        vec![create_error(&tokens, "Macro expansion failed")]
    }

    fn expand(&mut self) -> Vec<Token> {
        let mut input_tokens: VecDeque<Token> = VecDeque::new();

        let mut open_state = 0;
        let mut next = self.queued_next_token();
        while next.term() != Lexicon::Close || open_state != 0 {
            match next.term() {
                Lexicon::Open => {
                    open_state += 1;
                    input_tokens.push_back(next.clone());
                }
                Lexicon::Close => {
                    open_state -= 1;
                    input_tokens.push_back(next.clone());
                }
                Lexicon::MacroOpen => input_tokens.extend(self.expand()),
                _ => input_tokens.push_back(next.clone()),
            };
            next = self.queued_next_token();
        }

        self.interpret(input_tokens)
    }

    /// Extracts the next token from the lexer, but does not evaluate it yet.
    /// Pushes the token onto the queue, to be handled by macro_next_token().
    fn queue_raw_token(&mut self) -> Token {
        let result = self.queued_next_token();
        self.raw_q.push_back(result.clone());
        result
    }

    /// Extracts the next token from the queue, if the queue is depleted,
    /// fills the queue from the base lexer, then extracts it.
    fn queued_next_token(&mut self) -> Token {
        match self.raw_q.pop_front() {
            Some(t) => t,
            None => self.base_lexer.next_token(),
        }
    }

    fn macro_next_token(&mut self) -> Token {
        let token = self.queued_next_token();
        match token.term() {
            Lexicon::MacroOpen => {
                for token in self.expand() {
                    self.raw_q.push_back(token);
                }
                self.macro_next_token()
            }
            _ => token,
        }
    }
}

impl<LB, U> LexerBase for MacroLexer<LB, U>
where
    LB: LexerBase,
    U: Clone,
{
    fn next_token(&mut self) -> Token {
        // The macro lexer requires a lot of read ahead to perform
        // expression interpretation and expansion. Therefore, a look
        // ahead buffer is used.

        // If there still is a token in the queue, and it is not an
        // identifier or if the token is not the only one in the queuu,
        // then it can be popped and returned.

        if self.expanded_q.len() > 1 {
            return self.expanded_q.pop_front().unwrap();
        }

        match self.expanded_q.front() {
            Some(token) => match token.term() {
                Lexicon::Identifier(_) => (),
                _ => return self.expanded_q.pop_front().unwrap(),
            },
            None => (),
        }

        // If the queue is empty, the next element should be pushed on it,
        // if it is an identifier, otherwise is should be passed on.

        if self.expanded_q.len() < 1 {
            let next_token = self.macro_next_token();
            self.expanded_q.push_back(next_token);
        };

        // If the next token is an assignment, assignment evaluation should
        // take place, otherwise the token should be pushed onto the queue
        // the the queued token should be released.
        let token = self.macro_next_token();
        match token.term() {
            Lexicon::AppendAssignment | Lexicon::ImmediateAssignment => {
                let lhs = self.expanded_q.pop_front().unwrap();
                match lhs.term() {
                    Lexicon::Identifier(symbol_name) => {
                        let mut value = String::new();
                        let mut continue_scan = true;

                        while continue_scan {
                            let rhs = self.macro_next_token();
                            match rhs.term() {
                                Lexicon::EOT => continue_scan = false,
                                Lexicon::Error(_) => return rhs,
                                _ => {
                                    value += &rhs.raw();
                                }
                            }

                            if continue_scan {
                                let test = self.queue_raw_token();
                                if rhs.line() != test.line() {
                                    continue_scan = false;
                                }
                            }
                        }

                        value = value.replace("\n", "").replace("\r", "");

                        // Create the new symbol
                        let mut sym = Symbol {
                            name: symbol_name.to_string(),
                            line: lhs.line(),
                            column: lhs.column(),
                            value: value.to_string(),
                        };

                        // If the current assignment is an append assignment, find whether the
                        // symbol has already been used, acquire the value and prefix that value
                        // in front of the new symbol's value
                        if let Lexicon::AppendAssignment = token.term() {
                            for origin in self.symbol_table.iter() {
                                if origin.name.eq(&symbol_name) {
                                    sym.value = format!("{}{}", origin.value, sym.value)
                                }
                            }
                        }
                        self.symbol_table.insert(sym);
                        self.next_token()
                    }
                    _ => Token::create_error(
                        lhs.column(),
                        lhs.line(),
                        "Left-hand side value should be an identifier",
                    ),
                }
            }
            _ => {
                self.expanded_q.push_back(token);
                return self.expanded_q.pop_front().unwrap();
            }
        }
    }
}

/// If the token is an identifier, and starts with the call semantics,
/// it is "special" as it identifies a call.
fn is_call_token(token: &Token) -> (bool, Token) {
    match token.term() {
        Lexicon::Identifier(s) => {
            if s.starts_with("call ")
                || s.starts_with("call\t")
                || s.starts_with("call\r")
                || s.starts_with("call\n")
            {
                let result = Token::create(
                    Lexicon::Identifier(s[4..].trim().to_string()),
                    token.column(),
                    token.line(),
                    &"$(call ",
                );
                (true, result.clone())
            } else {
                (false, token.clone())
            }
        }
        _ => (false, token.clone()),
    }
}

/// Because macros can contain adjecent identifiers because of earlier
/// macro expansions, the identifiers are to be interpreted as a single
/// identifier, for example:
///
/// FOO := foo
/// BAR := bar
/// $($(FOO)$(BAR))
///
/// $(FOO) would be replaced with "foo" and $(BAR) would be replaced
/// with "bar". But "foobar" should be the identifier resulting from
/// that statement.
fn macro_simplify(tokens: &VecDeque<Token>) -> Result<VecDeque<String>, &str> {
    let mut simplified: VecDeque<String> = VecDeque::new();
    let mut compiled_string: String = "".to_string();
    for token in tokens {
        match token.term() {
            Lexicon::Identifier(s) => {
                compiled_string = format!("{}{}", compiled_string, s);
            }
            Lexicon::Comma => {
                simplified.push_back(compiled_string.to_string());
                compiled_string = "".to_string();
            }
            _ => return Err(&"Expected macro identifier or comma"),
        }
    }
    simplified.push_back(compiled_string.to_string());
    Ok(simplified)
}

fn get_tokens_column_line(tokens: &VecDeque<Token>) -> (usize, usize) {
    match tokens.front() {
        Some(t) => (t.column(), t.line()),
        _ => (0, 0),
    }
}

fn create_error(tokens: &VecDeque<Token>, err_msg: &str) -> Token {
    let (column, line) = get_tokens_column_line(tokens);
    Token::create_error(column, line, err_msg)
}

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

    fn create_lexer(s: &str) -> MacroLexer<Lexer<&[u8]>, ()> {
        MacroLexer::new(Lexer::create(s.as_bytes()), &())
    }

    #[test]
    fn test_basic_expansion() {
        let mut l = create_lexer(&"FOO := foo\n$(FOO)");
        assert_eq!(
            Lexicon::Identifier("foo".to_string()),
            l.next_token().term()
        );
        assert_eq!(Lexicon::EOT, l.next_token().term());
    }

    #[test]
    fn test_dual_expansion() {
        let mut l = create_lexer(&"FOO := foo\nBAR := bar\n$(FOO) $(BAR)");
        assert_eq!(
            Lexicon::Identifier("foo".to_string()),
            l.next_token().term()
        );
        assert_eq!(
            Lexicon::Identifier("bar".to_string()),
            l.next_token().term()
        );
        assert_eq!(Lexicon::EOT, l.next_token().term());
    }

    fn foo_func(
        params: Vec<String>,
        _: &str,
        _: usize,
        _: usize,
        _: &(),
    ) -> Result<Vec<Lexicon>, String> {
        match params.len() {
            1 => Ok(vec![Lexicon::Identifier(
                params.first().unwrap().to_string(),
            )]),
            _ => Err("Expected exactly one parameter".to_string()),
        }
    }

    #[test]
    fn test_simple_macro_expansion() {
        let mut l = create_lexer(&"$(call func,foo)");
        l.add_fn("func", foo_func);
        assert_eq!(
            Lexicon::Identifier("foo".to_string()),
            l.next_token().term()
        );
        assert_eq!(Lexicon::EOT, l.next_token().term());
    }

    #[test]
    fn test_abbrev_macro_expansion() {
        let mut l = create_lexer(&"$(func,foo)");
        l.add_fn("func", foo_func);
        assert_eq!(
            Lexicon::Identifier("foo".to_string()),
            l.next_token().term()
        );
        assert_eq!(Lexicon::EOT, l.next_token().term());
    }

    #[test]
    fn test_recursive_macro_expansion() {
        let mut l = create_lexer(&"FOO := foo\nBAR := $(call func,$(FOO))\n$(BAR)");
        l.add_fn("func", foo_func);
        assert_eq!(
            Lexicon::Identifier("foo".to_string()),
            l.next_token().term()
        );
        assert_eq!(Lexicon::EOT, l.next_token().term());
    }
}