git_bug/query/parse/parser/

relaxed.rs

// git-bug-rs - A rust library for interfacing with git-bug repositories
//
// Copyright (C) 2025 Benedikt Peetz <benedikt.peetz@b-peetz.de>
// SPDX-License-Identifier: GPL-3.0-or-later
//
// This file is part of git-bug-rs/git-gub.
//
// You should have received a copy of the License along with this program.
// If not, see <https://www.gnu.org/licenses/agpl.txt>.

//! The relaxed query parser

use crate::query::{
    Matcher,
    parse::{
        parser::{format_unexpected_token, format_unknown_key},
        tokenizer::{Token, TokenKind, TokenSpan},
    },
    queryable::{QueryKeyValue, Queryable},
};

#[derive(Debug, thiserror::Error)]
#[allow(missing_docs)]
pub enum Error<E: Queryable>
where
    <E::KeyValue as QueryKeyValue>::Err: std::fmt::Debug + std::fmt::Display,
{
    #[error(fmt = format_unexpected_token)]
    UnexpectedToken { expected: TokenKind, found: Token },

    /// An unexpected token was found, and multiple possible token kinds were
    /// possible.
    #[error("The input stream contained {found} but expected one of: {expected:?}")]
    UnexpectedTokens {
        /// The token kinds that could have occurred.
        expected: Vec<TokenKind>,

        /// The token we actually found.
        found: Token,
    },

    /// A key in a `MatchKey` expression was unknown.
    #[error(fmt = format_unknown_key::<E>)]
    UnknownKey {
        /// The returned error
        err: <E::KeyValue as QueryKeyValue>::Err,

        /// The key we found.
        key: String,

        /// The span this key takes up.
        at: TokenSpan,
    },

    /// A value for the default key in a `MatchKey` expression was unknown.
    #[error("The input stream countained a unknown value '{value}' for the default key: {err}")]
    UnknownDefaultKey {
        /// The value that was unknown for the default key.
        value: String,

        /// The returned error from the [`QueryKeyValue::from_value`] method.
        err: <<E as Queryable>::KeyValue as QueryKeyValue>::Err,

        /// The span in the query this value takes up.
        at: TokenSpan,
    },

    /// An expression that needs both a left hand side (LHS) and right hand side
    /// (RHS) was specified without a LHS.
    #[error("Expected a LHS for {at}, but got nothing.")]
    MissingLhs {
        /// Which expression requested the LHS.
        at: Token,
    },
}

impl<E: Queryable> From<super::parsing::Error<E>> for Error<E>
where
    <E::KeyValue as QueryKeyValue>::Err: std::fmt::Debug + std::fmt::Display,
{
    fn from(value: super::parsing::Error<E>) -> Self {
        match value {
            super::parsing::Error::UnexpectedToken { expected, found } => {
                Self::UnexpectedToken { expected, found }
            }
            super::parsing::Error::UnknownKey { err, key, at } => Self::UnknownKey { err, key, at },
        }
    }
}

pub(super) struct Parser<'a, E: Queryable> {
    parent: &'a mut super::Parser<'a, E>,
}

impl<'a, E: Queryable> Parser<'a, E>
where
    <E::KeyValue as QueryKeyValue>::Err: std::fmt::Debug + std::fmt::Display,
{
    pub(super) fn parse(parent: &'a mut super::Parser<'a, E>) -> Result<Matcher<E>, Error<E>> {
        let mut me = Parser { parent };
        me.actual_parse(None)
    }

    fn actual_parse(&mut self, matcher: Option<Matcher<E>>) -> Result<Matcher<E>, Error<E>> {
        fn unwrap_matcher<E: Queryable>(
            matcher: Option<Matcher<E>>,
            token: Token,
        ) -> Result<Matcher<E>, Error<E>>
        where
            <E::KeyValue as QueryKeyValue>::Err: std::fmt::Debug + std::fmt::Display,
        {
            if let Some(matcher) = matcher {
                Ok(matcher)
            } else {
                Err(Error::MissingLhs { at: token })
            }
        }

        self.clean();

        let peek_next = self.parent.tokenizer.peek();
        match peek_next.kind {
            TokenKind::And => {
                let token = self.parent.expect(TokenKind::And)?;
                self.parent.expect(TokenKind::Break)?;

                let next = Matcher::And {
                    lhs: Box::new(unwrap_matcher(matcher, token)?),
                    rhs: Box::new(self.parse_matcher()?),
                };
                self.actual_parse(Some(next))
            }
            TokenKind::Or => {
                let token = self.parent.expect(TokenKind::Or)?;
                self.parent.expect(TokenKind::Break)?;

                let next = Matcher::Or {
                    lhs: Box::new(unwrap_matcher(matcher, token)?),
                    rhs: Box::new(self.parse_matcher()?),
                };
                self.actual_parse(Some(next))
            }

            TokenKind::ParenOpen | TokenKind::Char(_) => {
                let next = merge_matcher(matcher, self.parse_matcher()?);

                self.actual_parse(Some(next))
            }

            TokenKind::Colon => Err(Error::UnexpectedTokens {
                expected: vec![
                    TokenKind::And,
                    TokenKind::Or,
                    TokenKind::ParenOpen,
                    TokenKind::Char('*'),
                ],
                found: peek_next,
            }),
            TokenKind::Eof => Ok(matcher.expect("This should be some at this point")),
            TokenKind::Break | TokenKind::ParenClose => unreachable!("Sorted out above."),
        }
    }

    fn clean(&mut self) {
        // Allow for leading white space and trailing closing parentheses
        while let kind @ (TokenKind::ParenClose | TokenKind::Break) =
            self.parent.tokenizer.peek().kind()
        {
            let next = self.parent.tokenizer.next_token();
            assert_eq!(next.kind, kind);
        }
    }

    fn parse_matcher(&mut self) -> Result<Matcher<E>, Error<E>> {
        let peek_next = self.parent.tokenizer.peek();

        match peek_next.kind {
            TokenKind::ParenOpen => self.parse_and_or_or(),
            TokenKind::Char(_) => self.parse_match_key(),
            TokenKind::Colon
            | TokenKind::Eof
            | TokenKind::ParenClose
            | TokenKind::And
            | TokenKind::Or => Err(Error::UnexpectedTokens {
                expected: vec![TokenKind::ParenOpen, TokenKind::Char('*')],
                found: peek_next,
            }),
            TokenKind::Break => {
                self.parent.expect(TokenKind::Break)?;
                self.parse_matcher()
            }
        }
    }

    fn parse_match_key(&mut self) -> Result<Matcher<E>, Error<E>> {
        // A normal MatchKey is `<key>:<value>`.
        // But we also support only passing `<value>`, and defaulting to the `search`
        // key.

        let key_tokens = self
            .parent
            .take_while(|t| matches!(t, TokenKind::Char(_)))?;
        let key = if TokenKind::Colon == self.parent.tokenizer.peek().kind {
            // We have a normalized MatchKey.
            self.parent.expect(TokenKind::Colon)?;
            let (value, value_span_end) = {
                let value_tokens = self
                    .parent
                    .take_while(|t| matches!(t, TokenKind::Char(_)))?;
                (
                    super::Parser::<'a, E>::parse_value_from(&value_tokens),
                    value_tokens.last().map_or(0, |last| last.span.stop),
                )
            };

            self.parent
                .parse_key_from(&key_tokens, value, value_span_end)?
        } else {
            // We don't have a colon after the key values. Thus assume, that the
            // “key_tokens” are actually already the “value_tokens”.

            let value = super::Parser::<'a, E>::parse_value_from(&key_tokens);
            E::KeyValue::from_value(self.parent.user_state, value.clone()).map_err(|err| {
                Error::UnknownDefaultKey {
                    value,
                    err,
                    at: TokenSpan {
                        start: key_tokens.first().expect("Exists").span.start,
                        stop: key_tokens.last().expect("Exists").span.stop,
                    },
                }
            })?
        };

        Ok(Matcher::Match { key_value: key })
    }

    fn parse_and_or_or(&mut self) -> Result<Matcher<E>, Error<E>> {
        self.parent.expect(TokenKind::ParenOpen)?;
        let lhs = Box::new(self.parse_matcher()?);
        self.parent.expect(TokenKind::Break)?;

        // TODO(@bpeetz): I have no idea at all why this is needed here, but somehow
        // ParenClose and Break end up here. <2025-05-11>
        self.clean();

        let mode = {
            let next = self.parent.tokenizer.next_token();
            match next.kind {
                TokenKind::And => TokenKind::And,
                TokenKind::Or => TokenKind::Or,
                _ => {
                    return Err(Error::UnexpectedTokens {
                        expected: vec![TokenKind::And, TokenKind::Or],
                        found: next,
                    });
                }
            }
        };

        self.parent.expect(TokenKind::Break)?;
        let rhs = Box::new(self.parse_matcher()?);

        // Do not enforce balanced parentheses.
        // This is needed to support things like “(x AND y AND z)” (notice the missing
        // parentheses between them).
        if self.parent.tokenizer.peek().kind() == TokenKind::ParenClose {
            self.parent.expect(TokenKind::ParenClose)?;
        }

        if mode == TokenKind::And {
            Ok(Matcher::And { lhs, rhs })
        } else if mode == TokenKind::Or {
            Ok(Matcher::Or { lhs, rhs })
        } else {
            unreachable!("This should have been filtered out in the match above");
        }
    }
}

fn merge_matcher<E: Queryable>(old: Option<Matcher<E>>, new: Matcher<E>) -> Matcher<E> {
    if let Some(old) = old {
        Matcher::And {
            lhs: Box::new(old),
            rhs: Box::new(new),
        }
    } else {
        new
    }
}

#[cfg(test)]
mod test {
    use pretty_assertions::assert_eq;

    use crate::query::{
        Matcher::{And, Match, Or},
        ParseMode, Query,
        parse::parser::test::{
            QueryTestKey1::{Value1, Value2},
            QueryTestKeyValue::{Key1, Key2, Key3},
            QueryTestObj, query,
        },
    };

    #[test]
    fn test_default_key() {
        let input = "(value1 AND 'state p2 󰵘')";
        let query = Query::<QueryTestObj>::from_continuous_str(&(), input, ParseMode::Relaxed)
            .map_err(|err| panic!("{err}"))
            .unwrap();

        assert_eq!(
            query,
            query! {
                And {
                    lhs: {Match (Key2, "value1")},
                    rhs: {Match (Key2, "state p2 \u{f0d58}")}
                }
            }
        );
    }

    #[test]
    fn test_and_defaults() {
        let input = "key1:value1 key2:other key3:20";
        let query = Query::<QueryTestObj>::from_continuous_str(&(), input, ParseMode::Relaxed)
            .map_err(|err| panic!("{err}"))
            .unwrap();

        assert_eq!(
            query,
            query! {
                And {
                    lhs: {And {
                        lhs: {Match(Key1, Value1)},
                        rhs: {Match(Key2, "other")},
                    }},
                    rhs: {Match(Key3, 20)}
                }
            },
        );
    }

    #[test]
    fn test_full_defaults() {
        let input = "value1 other 20";
        let query = Query::<QueryTestObj>::from_continuous_str(&(), input, ParseMode::Relaxed)
            .map_err(|err| panic!("{err}"))
            .unwrap();

        assert_eq!(
            query,
            query! {
               And {
                    lhs: {
                        And {
                            lhs: {Match(Key2, "value1")},
                            rhs: {Match(Key2, "other")},
                        },
                    },
                    rhs: {Match(Key2,"20")}
                }
            },
        );
    }

    #[test]
    fn test_and_chain() {
        let input = "key1:value1 AND key1:value2 AND key2:value3 OR key3:21";
        let query = Query::<QueryTestObj>::from_continuous_str(&(), input, ParseMode::Relaxed)
            .map_err(|err| panic!("{err}"))
            .unwrap();

        assert_eq!(
            query,
            query! {
                Or {
                    lhs: {And {
                            lhs: {And {
                                    lhs: {Match(Key1, Value1)},
                                    rhs: {Match(Key1, Value2)}
                            }},
                            rhs: {Match(Key2, "value3")},
                    }},
                    rhs: {Match(Key3, 21)},
                }
            }
        );
    }

    #[test]
    #[ignore = "The order of the AND and OR conjunctions is wrong."]
    fn test_full_query() {
        let input = "(
                        (
                            key1:value1
                            AND 'key2:bitter sweet 🫠'
                            AND key3:20199
                        ) OR (
                            key2:abc
                            AND key1:value2
                            AND key1:value1
                        )
                     ) OR (
                        (
                            c
                            AND key3:20
                        ) OR (
                            orwell
                            AND key3:1902
                        )
                     )"
        .replace('\n', "");
        let query = Query::<QueryTestObj>::from_continuous_str(&(), &input, ParseMode::Relaxed)
            .map_err(|err| panic!("{err}"))
            .unwrap();

        assert_eq!(
            query,
            query! {
                Or {
                    lhs: {Or {
                            lhs: {And {
                                    lhs: {And {
                                            lhs: {Match(Key1, Value1)},
                                            rhs: {Match(Key2, "bitter sweet 🫠")},
                                        }
                                    },
                                    rhs: {Match(Key3, 20199)},
                                } },
                            rhs: {And {
                                    lhs: {And {
                                        lhs: {Match(Key2, "abc")},
                                        rhs: {Match(Key1, Value2)},
                                    }},
                                    rhs: {Match(Key1, Value1)},
                                } }
                    }   },
                    rhs: {Or {
                            lhs: {And {
                                lhs: {Match(Key2, "c")},
                                rhs: {Match(Key3, 20)},
                            }},
                            rhs: {And {
                                lhs: {Match(Key2, "orwell")},
                                rhs: {Match(Key3, 1902)},
                            }}
                        }
                    },
                }
            }
        );
    }
}