bool-tag-expr 0.1.0-beta.2

//!
//! Syntactic parsing of boolean expressions
//!

use crate::{BoolTagExprLexicalParse, ParseError, Tag, Tags, Token};
use serde::{Deserialize, Deserializer, Serialize, Serializer};
use thiserror::Error;

/// A boolean expression tree.
///
/// This is a simple wrapper around a [`Node`].
#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct BoolTagExpr(Node);

/// Error that arises when attempting to use an invalid SQL identifier
#[derive(Debug, Clone, PartialEq, Eq, Hash, Error)]
pub enum SqlTableInfoError {
    /// There is an invalid SQL identifier
    #[error("Invalid identifiers: '{0}'")]
    InvalidIdentifier(String),
}

// TODO: write a macro for compile time checking?
/// Holds information about the table against which the SQL will be run - this
/// is used to produce the SQL.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct DbTableInfo {
    /// The name of the table that holds the tag name & value columns as well as
    /// a column for identifying the target
    table_name: String,

    /// The name of the column holding data used to ID some entity being
    /// selected
    id_column: String,

    /// The name of the column holding the tag name
    tag_name_column: String,

    /// The name of the column holding the tag value
    tag_value_column: String,
}

impl DbTableInfo {
    /// Create a `DbTableInfo`, ensuring that the values are valid SQL
    /// identifiers to protect against SQL injection attacks
    pub fn from(
        table_name: &str,
        id_column: &str,
        tag_name_column: &str,
        tag_value_column: &str,
    ) -> Result<Self, SqlTableInfoError> {
        for identifier in [table_name, id_column, tag_name_column, tag_value_column] {
            if !is_valid_sql_identifier(identifier) {
                Err(SqlTableInfoError::InvalidIdentifier(identifier.to_string()))?;
            }
        }

        Ok(Self {
            table_name: table_name.to_string(),
            id_column: id_column.to_string(),
            tag_name_column: tag_name_column.to_string(),
            tag_value_column: tag_value_column.to_string(),
        })
    }
}

/// Check that the string is a valid SQL identifier
///
/// This bluntly protects against SQL injection by limiting allowed chars
fn is_valid_sql_identifier(s: &str) -> bool {
    let mut chars = s.chars();
    match chars.next() {
        // Check the first char (can't be numeric)
        Some(c) if c.is_ascii_alphabetic() || c == '_' => {
            // Check the rest of the chars (can be numeric_)
            chars.all(|ch| ch.is_ascii_alphanumeric() || ch == '_')
        }
        _ => false,
    }
}

// TODO: Needs testing
impl Serialize for BoolTagExpr {
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        let bool_expr = self.clone().to_boolean_expression();
        serializer.serialize_str(&bool_expr)
    }
}

// TODO: needs testing
impl<'de> Deserialize<'de> for BoolTagExpr {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: Deserializer<'de>,
    {
        let raw_expr = String::deserialize(deserializer)?;
        let tree = Self::from(raw_expr);
        match tree {
            Ok(tree) => Ok(tree),
            Err(error) => {
                // TODO: use the error (impl into?)
                let err_msg = format!("Boolean expressions is invalid: {error}");
                Err(serde::de::Error::custom(err_msg))
            }
        }
    }
}

/// Possible elements of a boolean expression (a boolean expression tree is made
/// up of these)
#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum Node {
    And(Box<Node>, Box<Node>),
    Or(Box<Node>, Box<Node>),
    Not(Box<Node>),
    Tag(Tag),
    Bool(bool),
}

/// Possible syntax errors
#[derive(Debug, PartialEq, Clone, Error, Hash, Eq)]
pub enum SyntaxParseError {
    /// The boolean tag expression contains no tags (there must be at least 1)
    #[error("No tags in expression")]
    NoTags,

    // TODO: store token for error msg?
    /// The first lexical token of the boolean tag expression is invalid
    #[error("Invalid opening token")]
    InvalidOpeningToken,

    // TODO: store token for error msg?
    /// The last lexical token of the boolean tag expression is invalid
    #[error("Invalid closing token")]
    InvalidClosingToken,

    // TODO: store token for error msg?
    /// There are more closing brakets than opening brackets in the boolean tag
    /// expression
    #[error("Unopended brackets")]
    UnopenedBrackets,

    // TODO: store token for error msg?
    /// There are more opening brakets than closing brackets in the boolean tag
    /// expression
    #[error("Unclosed brackets")]
    UnclosedBrackets,

    /// There is an invalid token order/sequence in the boolean tag expression
    #[error("Invalid sequence of tokens: {0} -> {1}")]
    InvalidSequence(Token, Token),
}

/// Implementing types can be (lexically and) syntactically parsed to a boolean
/// expression tree
pub trait BoolTagExprSyntaxParse<T: BoolTagExprLexicalParse> {
    /// Lexically and then syntactically parse the value into a boolean
    /// expression tree
    fn syntax_parse(self) -> Result<BoolTagExpr, ParseError>;
}

// TODO: For anything that can be a string (eg str too)
/// Blanket implementation of syntax parsing for any type that implements
/// `BoolTagExprLexicalParse`
impl<T: BoolTagExprLexicalParse> BoolTagExprSyntaxParse<T> for T {
    fn syntax_parse(self) -> Result<BoolTagExpr, ParseError> {
        let lexical_tokens = self.lexical_parse()?;
        validate_token_stream(lexical_tokens.tokens().to_owned())?;
        Ok(BoolTagExpr(syntax_parse_token_stream(
            &mut lexical_tokens.tokens().to_owned(),
        )))
    }
}

impl BoolTagExpr {
    /// Produce a [`BoolTagExpr`] from a type that implements both
    /// `LexicalParse` and `SyntaxParse<T>`
    pub fn from<T>(boolean_expr: T) -> Result<Self, ParseError>
    where
        T: BoolTagExprLexicalParse + BoolTagExprSyntaxParse<T>,
    {
        boolean_expr.syntax_parse()
    }

    /// Produce a logical boolean expression string from a [`BoolTagExpr`]
    #[must_use]
    pub fn to_boolean_expression(self) -> String {
        boolean_expr_tree_to_logical_expr_string(self.0)
    }

    /// Produce an SQL boolean statement from a [`BoolTagExpr`] for pulling
    /// entities out of a database
    ///
    /// If the SQL string returned by this function is denoted by `X`, then, as
    /// an example, we can use it in the following way:
    ///
    /// ```sql
    /// SELECT id, name
    /// FROM entities
    /// WHERE X
    /// ORDER BY name
    /// ```
    #[must_use]
    pub fn to_sql(self, table_info: &DbTableInfo) -> String {
        boolean_expr_tree_to_sql(self.0, table_info)
    }

    /// Get the boolean expr tree
    #[must_use]
    pub fn into_node(self) -> Node {
        self.0
    }

    /// Evaluate the expression against a list of `Tags`
    #[must_use]
    pub fn matches(&self, tags: &Tags) -> bool {
        recusively_evaluate_expr_against_tags(&self.0, tags)
    }
}

/// Evaluate a `BooleanTagExpr` tree against a list of `Tags`
fn recusively_evaluate_expr_against_tags(expr: &Node, tags: &Tags) -> bool {
    match expr {
        Node::And(l, r) => {
            recusively_evaluate_expr_against_tags(l, tags)
                && recusively_evaluate_expr_against_tags(r, tags)
        }
        Node::Or(l, r) => {
            recusively_evaluate_expr_against_tags(l, tags)
                || recusively_evaluate_expr_against_tags(r, tags)
        }
        Node::Not(e) => !recusively_evaluate_expr_against_tags(e, tags),
        Node::Tag(tag) => tags.contains(&tag),
        Node::Bool(_) => panic!(),
    }
}

// TODO: check the examples)
/// Recursively produce an SQL statement from a tree of [`Node`]s
///
/// Examples of the SQL output:
///
/// - `(tag_value=XYZ AND tag_value=ABC)`
/// - `((tag_name=QWE AND tag_value=XYZ) OR tag_value=ABC)`
fn boolean_expr_tree_to_sql(expr: Node, table_info: &DbTableInfo) -> String {
    match expr {
        Node::And(l, r) => {
            let mut sql_fragment = format!(
                "SELECT {} FROM {} WHERE {} IN (",
                table_info.id_column, table_info.table_name, table_info.id_column
            );
            sql_fragment.push_str(&boolean_expr_tree_to_sql(*l, table_info));
            sql_fragment.push_str(&format!(") AND {} IN (", table_info.id_column));
            sql_fragment.push_str(&boolean_expr_tree_to_sql(*r, table_info));
            sql_fragment.push_str(&format!(") GROUP BY {}", table_info.id_column));
            sql_fragment
        }
        Node::Or(l, r) => {
            let mut sql_fragment = format!("SELECT {} FROM (", table_info.id_column);
            sql_fragment.push_str(&boolean_expr_tree_to_sql(*l, table_info));
            sql_fragment.push_str(" UNION ");
            sql_fragment.push_str(&boolean_expr_tree_to_sql(*r, table_info));
            sql_fragment.push(')');
            sql_fragment
        }
        Node::Not(e) => {
            let mut sql_fragment = format!(
                "SELECT {} FROM {} WHERE {} NOT IN (",
                table_info.id_column, table_info.table_name, table_info.id_column
            );
            sql_fragment.push_str(&boolean_expr_tree_to_sql(*e, table_info));
            sql_fragment.push(')');
            sql_fragment
        }
        Node::Tag(tag) => match tag.name {
            None => format!(
                "SELECT {} FROM {} WHERE {}='{}'",
                table_info.id_column, table_info.table_name, table_info.tag_value_column, tag.value
            ),
            Some(tag_name) => format!(
                "SELECT {} FROM {} WHERE {}='{}' AND {}='{}'",
                table_info.id_column,
                table_info.table_name,
                table_info.tag_name_column,
                tag_name,
                table_info.tag_value_column,
                tag.value
            ),
        },
        Node::Bool(_) => panic!(),
    }
}

/// Recursively produce a logical boolean expressions from a tree of
/// [`BooleanTagExpr`]s
fn boolean_expr_tree_to_logical_expr_string(expr: Node) -> String {
    match expr {
        Node::And(l, r) => {
            let mut sql_fragment = String::from("(");
            sql_fragment.push_str(&boolean_expr_tree_to_logical_expr_string(*l));
            sql_fragment.push_str(" & ");
            sql_fragment.push_str(&boolean_expr_tree_to_logical_expr_string(*r));
            sql_fragment.push(')');
            sql_fragment
        }
        Node::Or(l, r) => {
            let mut sql_fragment = String::from("(");
            sql_fragment.push_str(&boolean_expr_tree_to_logical_expr_string(*l));
            sql_fragment.push_str(" | ");
            sql_fragment.push_str(&boolean_expr_tree_to_logical_expr_string(*r));
            sql_fragment.push(')');
            sql_fragment
        }
        Node::Not(e) => {
            let mut sql_fragment = String::from("!");
            sql_fragment.push_str(&boolean_expr_tree_to_logical_expr_string(*e));
            sql_fragment
        }
        Node::Tag(tag) => match tag.name {
            None => format!("{}", tag.value),
            Some(tag_name) => format!("({}={})", tag_name, tag.value),
        },
        Node::Bool(_) => panic!(),
    }
}

// TODO: check token stream length?
/// Check a stream of lexical tokens is a valid sequence (part of syntax
/// parsing)
fn validate_token_stream(mut tokens: Vec<Token>) -> Result<(), SyntaxParseError> {
    let mut at_least_1_tag = false;
    for token in tokens.clone() {
        if let Token::Tag(_) = token {
            at_least_1_tag = true;
            break;
        }
    }
    if !at_least_1_tag {
        return Err(SyntaxParseError::NoTags);
    }

    let mut opening_bracket_count = 0;
    let mut closing_bracket_count = 0;

    let mut previous_token = tokens.remove(0);

    // Check first token
    match &previous_token {
        Token::Not | Token::OpenBracket | Token::Tag(_) => Ok(()),
        _ => return Err(SyntaxParseError::InvalidOpeningToken),
    }?;

    for token in tokens {
        match previous_token {
            Token::OpenBracket => {
                opening_bracket_count += 1;
                match token.clone() {
                    // Valid
                    Token::OpenBracket | Token::Not | Token::Tag(_) => Ok(()),

                    // Invalid
                    Token::CloseBracket => {
                        return Err(SyntaxParseError::InvalidSequence(
                            Token::OpenBracket,
                            Token::CloseBracket,
                        ))
                    }
                    Token::And => {
                        return Err(SyntaxParseError::InvalidSequence(
                            Token::OpenBracket,
                            Token::And,
                        ))
                    }
                    Token::Or => {
                        return Err(SyntaxParseError::InvalidSequence(
                            Token::OpenBracket,
                            Token::Or,
                        ))
                    }
                }
            }
            Token::CloseBracket => {
                closing_bracket_count += 1;
                match token.clone() {
                    // Valid
                    Token::CloseBracket | Token::And | Token::Or => Ok(()),

                    // Invalid
                    Token::OpenBracket => {
                        return Err(SyntaxParseError::InvalidSequence(
                            Token::CloseBracket,
                            Token::OpenBracket,
                        ))
                    }
                    Token::Not => {
                        return Err(SyntaxParseError::InvalidSequence(
                            Token::CloseBracket,
                            Token::Not,
                        ))
                    }
                    Token::Tag(tag) => {
                        return Err(SyntaxParseError::InvalidSequence(
                            Token::CloseBracket,
                            Token::Tag(tag),
                        ))
                    }
                }
            }
            Token::Not => match token.clone() {
                // Valid
                Token::Tag(_) | Token::OpenBracket => Ok(()),

                // Invalid
                Token::CloseBracket => {
                    return Err(SyntaxParseError::InvalidSequence(
                        Token::Not,
                        Token::CloseBracket,
                    ))
                }
                Token::Not => {
                    return Err(SyntaxParseError::InvalidSequence(Token::Not, Token::Not))
                }
                Token::And => {
                    return Err(SyntaxParseError::InvalidSequence(Token::Not, Token::And))
                }
                Token::Or => return Err(SyntaxParseError::InvalidSequence(Token::Not, Token::Or)),
            },
            Token::And => match token.clone() {
                // Valid
                Token::Not | Token::OpenBracket | Token::Tag(_) => Ok(()),

                // Invalid
                Token::CloseBracket => {
                    return Err(SyntaxParseError::InvalidSequence(
                        Token::And,
                        Token::CloseBracket,
                    ))
                }
                Token::And => {
                    return Err(SyntaxParseError::InvalidSequence(Token::And, Token::And))
                }
                Token::Or => return Err(SyntaxParseError::InvalidSequence(Token::And, Token::Or)),
            },
            Token::Or => match token.clone() {
                // Valid
                Token::Not | Token::OpenBracket | Token::Tag(_) => Ok(()),

                // Invalid
                Token::CloseBracket => {
                    return Err(SyntaxParseError::InvalidSequence(
                        Token::Or,
                        Token::CloseBracket,
                    ))
                }
                Token::And => return Err(SyntaxParseError::InvalidSequence(Token::Or, Token::And)),
                Token::Or => return Err(SyntaxParseError::InvalidSequence(Token::Or, Token::Or)),
            },
            Token::Tag(previous_tag) => match token.clone() {
                // Valid
                Token::CloseBracket | Token::And | Token::Or => Ok(()),

                // Invalid
                Token::OpenBracket => {
                    return Err(SyntaxParseError::InvalidSequence(
                        Token::Tag(previous_tag),
                        Token::OpenBracket,
                    ))
                }
                Token::Not => {
                    return Err(SyntaxParseError::InvalidSequence(
                        Token::Tag(previous_tag),
                        Token::Not,
                    ))
                }
                Token::Tag(this_tag) => {
                    println!("{previous_tag} then {this_tag}, is not allowed");
                    return Err(SyntaxParseError::InvalidSequence(
                        Token::Tag(previous_tag),
                        Token::Tag(this_tag),
                    ));
                }
            },
        }?;

        previous_token = token;
    }

    // Check last token
    match &previous_token {
        Token::CloseBracket => {
            closing_bracket_count += 1;
            Ok(())
        }
        Token::Tag(_) => Ok(()),
        _ => return Err(SyntaxParseError::InvalidClosingToken),
    }?;

    if closing_bracket_count > opening_bracket_count {
        return Err(SyntaxParseError::UnopenedBrackets);
    }

    if closing_bracket_count < opening_bracket_count {
        return Err(SyntaxParseError::UnclosedBrackets);
    }

    Ok(())
}

/// Parse a sequence (of valid tokens) into a boolean expression tree (wrapper
/// around calling `recursive_syntax_parse()`)
fn syntax_parse_token_stream(tokens: &mut Vec<Token>) -> Node {
    let mut expr: Node = recursive_syntax_parse(tokens, None);
    loop {
        if tokens.is_empty() {
            break;
        }
        expr = recursive_syntax_parse(tokens, Some(expr));
    }
    expr
}

/// Recursively parse a sequence (of valid tokens) into a boolean expression
/// tree (called by the wrapper function `syntax_parse_token_stream()`))
fn recursive_syntax_parse(tokens: &mut Vec<Token>, expr: Option<Node>) -> Node {
    if tokens.is_empty() {
        return expr.unwrap();
    }
    let token = tokens.remove(0);
    match token {
        Token::OpenBracket => {
            // TODO: Need to pass in?
            recursive_syntax_parse(tokens, expr)
        }
        Token::CloseBracket => expr.unwrap(),
        Token::And => {
            let result = recursive_syntax_parse(tokens, None);
            Node::And(Box::new(expr.unwrap()), Box::new(result))
        }
        Token::Or => {
            let result = recursive_syntax_parse(tokens, None);
            Node::Or(Box::new(expr.unwrap()), Box::new(result))
        }
        Token::Tag(tag) => recursive_syntax_parse(tokens, Some(Node::Tag(tag))),
        Token::Not => {
            let result = recursive_syntax_parse(tokens, None);
            Node::Not(Box::new(result))
        }
    }
}

#[cfg(test)]
mod test {
    use super::*;
    use crate::{TagName, TagValue};

    #[test]
    fn syntax_parse_empty() -> anyhow::Result<()> {
        // Must have at least 1 tag
        let a = "";
        assert!(a.syntax_parse().err().unwrap() == ParseError::Syntax(SyntaxParseError::NoTags));

        let a = "(&)";
        assert!(a.syntax_parse().err().unwrap() == ParseError::Syntax(SyntaxParseError::NoTags));

        let a = "(& & &) | (& & &)";
        assert!(a.syntax_parse().err().unwrap() == ParseError::Syntax(SyntaxParseError::NoTags));

        Ok(())
    }

    #[test]
    fn syntax_parse() -> anyhow::Result<()> {
        // Should fail because of `&&` and `||`
        let a = "((nationality=american && scientist) || (=british & scientist))  & !man && person";
        assert!(a.syntax_parse().is_err());

        // Should fail because of `&&`
        let a = "((nationality=american & scientist) | (=british & scientist))  && !man & person";
        assert!(a.syntax_parse().is_err());

        // Should fail because of `||`
        let a = "((nationality=american & scientist) || (=british & scientist))  & !man && person";
        assert!(a.syntax_parse().is_err());

        // Should pass
        let a = "((nationality=american & scientist) | (=british & scientist))  & !man & person";
        assert!(a.syntax_parse().is_ok());

        // Should fail because of unmatched brackets
        let a = "(a & b";
        assert!(a.syntax_parse().is_err());

        // Should pass
        let a = "(a & b & c)";
        assert!(a.syntax_parse().is_ok());

        Ok(())
    }

    // TODO: improve this test (best approach, I think, will be to create an
    // in-memory DB and execute against it)
    //
    // TODO: How to test
    // This functionality should be tested by created an in-memory SQListe
    // database with a single table with 3 columns: ID, tag name, tag value.
    // The functionality should be tested by extracting matching IDs.
    #[test]
    fn to_sql() -> anyhow::Result<()> {
        let table_info = DbTableInfo::from(
            &"table_name",
            &"id_column",
            &"tag_name_column",
            &"tag_value_column",
        )?;

        // Should pass
        let a = "((x=a & b) | (c & b)) & !d";
        assert!(a.syntax_parse()?.to_sql(&table_info).is_ascii());

        Ok(())
    }

    // TODO: should the output string be "((x=a & b) | (c & b)) & !d" for readability?
    #[test]
    fn to_boolean_expression() -> anyhow::Result<()> {
        // Should pass
        let a = "((x=a & b) | (c & b)) & !d";
        let parsed = a.syntax_parse()?.to_boolean_expression();
        let parsed_again = parsed.clone().syntax_parse()?.to_boolean_expression();
        assert_eq!(parsed, parsed_again);

        Ok(())
    }

    #[test]
    fn matches() -> anyhow::Result<()> {
        // Shouldn't match
        let expr = BoolTagExpr::from("!d")?;
        let tags = Tags::from([Tag::from(None, TagValue::from("d")?)]);
        assert!(!expr.matches(&tags));

        // Should match
        let expr = BoolTagExpr::from("d")?;
        let tags = Tags::from([Tag::from(None, TagValue::from("d")?)]);
        assert!(expr.matches(&tags));

        // Complex
        let expr_str = "((x=a & b) | (c & b)) & !d";
        let expr = BoolTagExpr::from(expr_str)?;
        {
            // Should match
            let tags = Tags::from([
                Tag::from(None, TagValue::from("c")?),
                Tag::from(None, TagValue::from("b")?),
            ]);
            assert!(expr.matches(&tags));
        }
        {
            // Shouldn't match
            let tags = Tags::from([
                Tag::from(None, TagValue::from("c")?),
                Tag::from(None, TagValue::from("b")?),
                Tag::from(None, TagValue::from("d")?),
            ]);
            assert!(!expr.matches(&tags));
        }
        {
            // Should match
            let tags = Tags::from([
                Tag::from(Some(TagName::from("x")?), TagValue::from("a")?),
                Tag::from(None, TagValue::from("b")?),
            ]);
            assert!(expr.matches(&tags));
        }
        {
            // Shouldn't match
            let tags = Tags::from([
                Tag::from(Some(TagName::from("x")?), TagValue::from("a")?),
                Tag::from(None, TagValue::from("b")?),
                Tag::from(None, TagValue::from("d")?),
            ]);
            assert!(!expr.matches(&tags));
        }

        Ok(())
    }
}