whydrogen 0.1.0

// SPDX-FileContributor: Slatian
//
// SPDX-License-Identifier: LGPL-3.0-only

//! Whydrogen is a slightly opinioated parser for search queries from humans.
//!
//! Its main purpose is converting strings of text from a search entry into a
//! more easy to process list of tokens/lexemes
//! (depending on what you are doing with them).
//!
//! The search syntax in a nutshell:
//! * Unless something else applies everythinng seperated by a space is a word.
//! * Character classification happens through the means of Unicode category groups.
//! * Any sequence of whitespace (Unicode whitespace category plus newline and tab)
//!   or the start or end of a query can be a token seperator.
//! * Phrases are quoted sequences of text.
//! 	* Supported pairs of quotes are: `"…"`, `»…«` and `«…»`,
//! 	  this will be expanded in the future.
//! 	* The Phrase can only start after a token seperator.
//! 	* The closing quote must be followed by a token seperator
//! 	  (if not it is taken as part of the phrase).
//! 	* Any token seperator inside a quote is taken as its literal character
//! 	  (as in most quoting syntaxes).
//! 	* Inside a phrase a backslash `\` can be used to escape the closing
//! 	  quote character (independent of any token seperators)
//! 	* A double backslash `\\` can be used to unambigiously represent a
//! 	  backslash inside the quotes.
//! 	* A backslash followed by anything else is taken as is.
//! 	* A minus `-` before the first quote marks the phrase as inverted.
//! 	* An unclosed phrase is ignored, the part with the opening quote
//! 	  is treated as a word, parsing continues as usual after that.
//! * Key-Value pairs are a keyword and an <i>optionally quoted</i> value
//!   seperated by a colon `:`.
//!     * A keyword may contain any alphanumeric (unicode letter or number) character
//!       and `-`, `_` and `.`. It may only start with an alphanumreic.
//! 	* Valid keywords are
//! 	  [implementation defined][KeywordConverter::try_convert_keyword].
//! 	* A minus `-` before the keyword marks the Key-Value pair as inverted.
//! * Prefixed values are <i>optionally quoted</i> values prefixed
//!   with a single non-alphanumeric character.
//! 	* Valid prefixes are
//! 	  [implementation defined][KeywordConverter::try_convert_prefix].
//! 	* Prefixed values are parsed to the same data structure as Key-Value pairs.
//! 	* A minus `-` before the prefix marks the prefixed value as inverted.
//! * <i>optionally quoted</i> means:
//! 	* A text literal that ends at the next token seperator like a word.
//! 	* Quoted text according to the same quoting rules as Phrases
//! 	  (but starting immedeately instetad of after a token seperator),
//! 	  an additional quote pair of semicolons `;…;` is supported.
//!
//! Design goals of the syntax were:
//! * Familiar to anyone who has used such sntax in other search engines.
//! * Fault tolerant without synax errors in case of clumsy use.
//! * Pasting things like error messages into the serch field should not trigger
//!   any search syntax.
//! * Quotting must be able to reliably encode any sequence of characters without
//!   getting into the way of more casual use.
//!
//! The name is made up of the word for asking the most important kind of questtion
//! and the most abundand chemical element in the universe, which also happens to be
//! a very important component in answer seeking beings :D.
 
use std::marker::PhantomData;

mod parser_iterator;
mod chartest;
pub mod keyword_converter;

use crate::parser_iterator::ParserIterator;
use crate::chartest::*;
pub use crate::keyword_converter::KeywordConverter;

/// Parser output token (lexeme).
///
/// Each syntax element gets converted to such a token.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Token<K> {
	/// Unquoted, plain token, contains th raw text from the query.
	/// Generated for each piece of non-space text that isn't one of the other tokens.
	///
	/// One could make a more coplex syntax based on this token.
	/// (i.e. for making queries like `thingy NOT othertingy`
	/// as an alternative for `thingy -"otherthingy"` work.)
	Word(String),
	
	/// Standalone quoted text
	Phrase{
		/// Parsed text from inside the quotes without the sourrounding quotes.
		text: String,
		/// Whether the phrase was negated using a prefixed minus or other mechanism.
		invert: bool,
	},
	
	/// KeyValue or Prefix construct
	KeyValue{
		/// The key obtained from the [KeywordConverter].
		key: K,
		/// The vvalue as a parsed String with quoting and escaping already resolved.
		value: String,
		/// Whether the construct was negated using a prefixed minus or other mechanism.
		invert: bool,
	}
}

/// Parser internal enum for the state machine.
#[derive(Debug, Clone, PartialEq, Eq)]
enum ParserState {
	Space,
	Word,
	Phrase,
	KeyValue,
	Prefixed,
}

/// Thingy that does the actual parsing.
pub struct Parser<CK,K>
where
	CK: KeywordConverter<K>,
{
	pub keyword_converter: CK,

	phantom_keyword: PhantomData<K>,
}

impl<CK, K> Parser<CK, K>
where
	CK: KeywordConverter<K>,
{
	/// Creates a new parser that uses the given [KeywordConverter].
	pub fn new(keyword_converter: CK) -> Self {
		Self{
			keyword_converter: keyword_converter,

			phantom_keyword: PhantomData,
		}
	}

	/// Parses the given text to a list of tokens.
	pub fn parse(&self, text: &str) -> Vec<Token<K>> {
		let mut match_start: usize = 0;
		let mut key_start: usize = 0;
		let mut state: ParserState = ParserState::Space;
		let mut iter = ParserIterator::new(text);
		let mut result: Vec<Token<K>> = Vec::new();
		let mut ok: bool;
		let mut invert_flag: bool = false;
		let mut prefix_key: Option<K> = None;
		
		loop {
			ok = false;
			match state {
				ParserState::Space => {
					if iter.consume_chars(is_space_char) > 0 {
						invert_flag = false;
					}
					match_start = iter.index();
					match iter.peek() {
						Some('-') => {
							invert_flag = true;
							iter.next();
							if let Some(c) = iter.peek() {
								if is_keyword_safe_first_char(c) {
									state = ParserState::KeyValue;
								} else if let Some(key) = self.keyword_converter.try_convert_prefix(c) {
									state = ParserState::Prefixed;
									iter.next();
									prefix_key = Some(key);
								} else {
									state = ParserState::Phrase;
								}
							} else {
								state = ParserState::Word;
							}
						},
						Some(c) => {
							if is_keyword_safe_first_char(c) {
								state = ParserState::KeyValue;
							} else if let Some(key) = self.keyword_converter.try_convert_prefix(c) {
								state = ParserState::Prefixed;
								iter.next();
								prefix_key = Some(key);
							} else {
								state = ParserState::Phrase;
							}
						},
						None => {
							break;
						}
					}
					if state != ParserState::Space {
						key_start = iter.index();
					}
					ok = true;
				},
				ParserState::Word => {
					// Consume any (remaining) non-spaces
					iter.consume_chars(is_non_space_char);
					result.push(Token::Word(text[match_start..iter.index()].to_string()));
					state = ParserState::Space;
					ok = true;
				},
				ParserState::Phrase => {
					if let Some(value) = consume_quoted_literal(&mut iter) {
						result.push(Token::Phrase{
							text: value,
							invert: invert_flag,
						});
						state = ParserState::Space;
						ok = true;
					}
				},
				ParserState::KeyValue => {
					if iter.consume_chars(is_keyword_safe_char) > 0 {
						let key_end = iter.index();
						if iter.try_consume_char(':') {
							if !is_token_end(iter.peek()) {
								if let Some(key) = self.keyword_converter.try_convert_keyword(&text[key_start..key_end]) {
									let value = consume_quick_quotable_chars(&mut iter, text);
									result.push(Token::KeyValue{
										key: key,
										value: value,
										invert: invert_flag,
									});
									ok = true;
									state = ParserState::Space;
								}
							}
						}
					}
				},
				ParserState::Prefixed => {
					let value = consume_quick_quotable_chars(&mut iter, text);
					if value.len() > 0 {
						if let Some(key) = prefix_key {
							result.push(Token::KeyValue{
								key: key,
								value: value,
								invert: invert_flag,
							});
							state = ParserState::Space;
							ok = true;
						}
						prefix_key = None;
					}
				},
			}
			if !ok {
				state = ParserState::Word;
			}
		}

		return result;
	}
}

/// Consume a literal that may be quoted or not after a keyword.
/// Allows for a quick quoting style using semicolons that might
/// be easier to type aftr a colon.
fn consume_quick_quotable_chars(
	iter: &mut ParserIterator,
	text: &str
) -> String {

	if let Some(value) = consume_quoted_literal(iter) {
		return value;
	}
	if let Some(value) = consume_quoted(iter, ';',';') {
		return value;
	}
	
	// Assume unquoted string that ends at next regular token end.
	let start = iter.index();
	iter.consume_chars(is_non_space_char);
	return text[start..iter.index()].to_string();
}

/// Try to consume an explicitly quoted literal token,
/// either after a keyword or standalone.
fn consume_quoted_literal(iter: &mut ParserIterator) -> Option<String> {
	let mut value: Option<String>;
	value = consume_quoted(iter, '"','"');
	if value.is_some() { return value; }
	value = consume_quoted(iter, '»','«');
	if value.is_some() { return value; }
	value = consume_quoted(iter, '«','»');
	if value.is_some() { return value; }
	return None;
}

/// Try to consume a quoted string with the given start and end-quote.
fn consume_quoted(iter: &mut ParserIterator, start_quote: char, end_quote: char) -> Option<String> {
	if iter.peek() != Some(start_quote) {
		return None;
	}
	iter.checkpoint();
	iter.next(); //eat the initial quotemark
	let mut out: String = "".to_string();
	loop {
		match iter.next() {
			Some('\\') => {
				let peek = iter.peek();
				if peek == Some(end_quote) {
					iter.next();
					out.push(end_quote);
				} else if peek == Some('\\') {
					iter.next();
					out += "\\";
				} else {
					out += "\\"
				}
			},
			Some(c) => {
				if c == end_quote && is_token_end(iter.peek()) {
					iter.drop_checkpoint();
					return Some(out);
				} else {
					out.push(c);
				}
			},
			None => {
				//Reched the ond of text without closing quote
				break;
			}
		}
	}
	iter.restore();
	return None;
}


#[cfg(test)]
mod tests {
	use crate::keyword_converter::NullKeywordConverter;
	use crate::keyword_converter::StringKeywordConverter;
	use super::*;

	#[test]
	fn all_features() {
		let mut converter = StringKeywordConverter::new();
		converter.add_key("quick");
		converter.add_key("foo");
		converter.add_prefix('#');
		converter.add_prefix('!');
		let parser_config = Parser::new(converter);
	    assert_eq!(
		    parser_config.parse(" -#Hello -»world« -foo:\"bar \\\\\\\"bat\" quick:;quote text; !map foo:bar ~tilde bar:baz \t"),
		    vec![
			    Token::KeyValue{key: "#".to_string(), value:"Hello".to_string(), invert: true},
			    Token::Phrase{text: "world".to_string(), invert: true},
			    Token::KeyValue{key: "foo".to_string(), value:"bar \\\"bat".to_string(), invert: true},
			    Token::KeyValue{key: "quick".to_string(), value:"quote text".to_string(), invert: false},
			    Token::KeyValue{key: "!".to_string(), value:"map".to_string(), invert: false},
			    Token::KeyValue{key: "foo".to_string(), value:"bar".to_string(), invert: false},
			    Token::Word("~tilde".to_string()),
			    Token::Word("bar:baz".to_string()),
			]
	    );
	}

	#[test]
	fn empty() {
		let converter = NullKeywordConverter::<()>::new();
		let parser_config = Parser::new(converter);
		assert_eq!(
			parser_config.parse(""),
			vec![]
		);
	}

	#[test]
	fn space_only() {
		let converter = NullKeywordConverter::<()>::new();
		let parser_config = Parser::new(converter);
		assert_eq!(
			parser_config.parse(" \t \n"),
			vec![]
		);
	}

	#[test]
	fn null_keyword_converter() {
		let converter = NullKeywordConverter::<()>::new();
		let parser_config = Parser::new(converter);
		assert_eq!(
			parser_config.parse("word \"phrase\" not_key:value -«not phrase» #tag"),
			vec![
			    Token::Word("word".to_string()),
			    Token::Phrase{text: "phrase".to_string(), invert: false},
			    Token::Word("not_key:value".to_string()),
			    Token::Phrase{text: "not phrase".to_string(), invert: true},
			    Token::Word("#tag".to_string()),
			]
		);
	}
}