databend中nom的应用

databend中sql解析器是基于nom来完成的，接下来结合一个样例：explain语句

let explain = map_res( // 需要完成sql输入解析的Parser以及将解析完成后的输出提供给闭包函数
        rule! {
            EXPLAIN ~ ( AST | SYNTAX | PIPELINE | JOIN | GRAPH | FRAGMENTS | RAW | OPTIMIZED | MEMO )? ~ #statement
        }, // 解析器
        |(_, opt_kind, statement)| { // 用于使用nom的parser解Input后的结果当成输入参数，提供给当前的闭包函数
            Ok(Statement::Explain {
                kind: match opt_kind.map(|token| token.kind) {
                    Some(TokenKind::AST) => {
                        let formatted_stmt = format_statement(statement.stmt.clone())
                            .map_err(|_| ErrorKind::Other("invalid statement"))?;
                        ExplainKind::Ast(formatted_stmt)
                    }
                    Some(TokenKind::SYNTAX) => {
                        let pretty_stmt = pretty_statement(statement.stmt.clone(), 10)
                            .map_err(|_| ErrorKind::Other("invalid statement"))?;
                        ExplainKind::Syntax(pretty_stmt)
                    }
                    Some(TokenKind::PIPELINE) => ExplainKind::Pipeline,
                    Some(TokenKind::JOIN) => ExplainKind::JOIN,
                    Some(TokenKind::GRAPH) => ExplainKind::Graph,
                    Some(TokenKind::FRAGMENTS) => ExplainKind::Fragments,
                    Some(TokenKind::RAW) => ExplainKind::Raw,
                    Some(TokenKind::OPTIMIZED) => ExplainKind::Optimized,
                    Some(TokenKind::MEMO) => ExplainKind::Memo("".to_string()),
                    None => ExplainKind::Plan,
                    _ => unreachable!(),
                },
                query: Box::new(statement.stmt),
            })
        },
    );

这里先介绍下nom实现解析文本的

关于nom实现解析文本: 一种是基于macro来完成的，另一种是function来完成的(目前最新的nom版本比较支持的)

直接引入官方的一个demo

use nom::character::complete::digit1;
use nom::combinator::map_res;

// 这里的组合器包括digit1用来判断内容是否为数字，当满足是数字字符串时，则继续执行后续的闭包进行类型转换
let mut parse = map_res(digit1, |s: &str| s.parse::<u8>());

// the parser will convert the result of digit1 to a number
assert_eq!(parse("123"), Ok(("", 123)));

// this will fail if digit1 fails
assert_eq!(parse("abc"), Err(Err::Error(("abc", ErrorKind::Digit))));

// this will fail if the mapped function fails (a `u8` is too small to hold `123456`)
assert_eq!(parse("123456"), Err(Err::Error(("123456", ErrorKind::MapRes))));

关于nom中map_res的定义

pub fn map_res<I: Clone, O1, O2, E: FromExternalError<I, E2>, E2, F, G>(
    parser: F,   // 解析器
    f: G         // 针对解析处理后的内容进行后续处理
) -> impl FnMut(I) -> IResult<I, O2, E>
where
    F: Parser<I, O1, E>,
    G: FnMut(O1) -> Result<O2, E2>,

不过在databend中map_res被改写了：去掉了FromExternalError，其中被改写的还有：separated_list1、separated_list0(将原有的函数声明中的error定义剔除)
比如在databend中map_res的定义

pub fn map_res<'a, O1, O2, F, G>(
    mut parser: F,  // 使用的parser，一般是nom中的parser
    mut f: G,       // 闭包函数
) -> impl FnMut(Input<'a>) -> IResult<'a, O2>
where
    F: nom::Parser<Input<'a>, O1, Error<'a>>,
    G: FnMut(O1) -> Result<O2, ErrorKind>,

在databend中如何进行sql解析

map_res( // 需要完成sql输入解析的Parser以及将解析完成后的输出提供给闭包函数
    rule! {
            EXPLAIN ~ ( AST | SYNTAX | PIPELINE | JOIN | GRAPH | FRAGMENTS | RAW | OPTIMIZED | MEMO )? ~ #statement
    }, // 解析器
   | (_, opt_kind, statement)| {
      // 省略代码
   },
)

map_res来完成sql解析，主要有两部分：

• rule!(解析器集) 通过解析使用 BNF 来定义 SQL 的语法规则，
• |(_, opt_kind, statement)|{} 闭包 用于对解析器处理后的内容进行处理，获取当前statement的kind

sql解析

通过将用户输入的sql字符串提供给词法解析器生成token序列，接着将token序列提供给语法解析器，并结合指定的sql方言/语义最终生成statement；
在语法解析过程会进行sql语法检查，若是整个sql没有问题就会输出抽象语法树AST.

// 样例sql
select a + 1 from t

// 通过语法解析器输出抽象语法树(AST)
SelectStatement {
    projection: Expr::BinaryOp {
        op: Op::Plus,
        args: [
            Expr::ColumnRef("a"),
            Expr::Constant(Scalar::Int(1))
        ]
    }
    from: "t",
}

sql解析分成两个阶段：Tokenize(分词) 和 Parsing(解析)阶段

• Tokenize分词token化
  主要是将用户输入的sql字符串切分成具有独立语义的单元，称为token； 一般是通过正则表达式从字符串中识别相邻有意义的部分，比如关键字、变量名
  、常量、操作符
  类似如下定义

Ident = [_a-zA-Z][_$a-zA-Z0-9]*
Number = [0-9]+
Plus = +
SELECT = SELECT
FROM = FROM

按照从上到下顺序尝试匹配正则表达式，并一直重复这个步骤最终得到token序列
比如 select a+1 from t，token化序列如下

[
    Keyword(SELECT),
    Ident(a),
    BinOp(+),
    Number(1),
    Keyword(FROM),
    Ident(t),
]

接下来就是parsing阶段，首先先来了解下BNF来定义sql语法规则

关于BNF定义sql语法规则

主要来描述了有意义的Token如何进行组合

<select_statement> ::= SELECT <expr> FROM <ident>
<expr> ::= <number>
         | <ident>
         | <expr> <op> <expr>
<op> ::= + | - | * | /

• Parsing解析statement
  在databend中使用BNF来定义sql语法规则，将上面生成的token序列输入到解析器，进而生成AST

SelectStatement {
    projection: Expr::BinaryOp {
        op: Op::Plus,
        args: [
            Expr::ColumnRef("a"),
            Expr::Constant(Scalar::Int(1))
        ]
    }
    from: "t",
}

自此sql statement就形成了。

databend的sql token和parsing阶段的实现

在databend中使用logos和nom来分别完成token化和解析：
1、使用logos库来完成sql字符串token化, 详情见databend sql字符串token化
在databend中定义了TokenKind的enum枚举类型，每个TokenKind对应一个特定的Token: 例如关键字、变量名、常量和操作符。并且每个TokenKind都会有
一个单独的正则表达式进行匹配，以确保准确地从输入字符串中提取token，将TokenKind和Logos库整合，最终编译一个高效的状态机和跳表来达到超过手写Tokenizer
的极快的分词性能

#[allow(non_camel_case_types)]
#[derive(Logos)]
pub enum TokenKind {
    #[regex(r"[ \t\r\n\f]+", logos::skip)]
    Whitespace,

    #[regex(r#"[_a-zA-Z][_$a-zA-Z0-9]*"#)]
    Ident,
    #[regex(r"[0-9]+")]
    Number,

    #[token("+")]
    Plus,

    #[token("SELECT", ignore(ascii_case))]
    SELECT,
    #[token("FROM", ignore(ascii_case))]
    FROM,
}

将“select a+1 from t”进行token化,如下

[
    Token { kind: TokenKind::Select, text: "SELECT", span: 0..6 },
    Token { kind: TokenKind::Ident, text: "a", span: 7..8 },
    Token { kind: TokenKind::Plus, text: "+", span: 9..10 },
    Token { kind: TokenKind::Number, text: "1", span: 11..12 },
    Token { kind: TokenKind::From, text: "from", span: 13..17 },
    Token { kind: TokenKind::Ident, text: "t", span: 18..19 },
]

除了 TokenKind 的定义，Token 本身还包括了一个重要的属性——span。span 记录了 Token 在原始字符串中的起始和结束位置。

2、使用nom实现递归下降sql解析器，同时nom自身语法规则构建过程相对繁琐，所以定义了rule!()过程宏，并使用BNF来定义语法规则， 自动生成nom解析器

// databend中rule过程宏
rule! {
    EXPLAIN ~ ( AST | SYNTAX | PIPELINE | JOIN | GRAPH | FRAGMENTS | RAW | OPTIMIZED | MEMO )? ~ #statement
}

// 底层使用nom中的nom_rule::rule!来完成的
#[macro_export]
macro_rules! rule {
    ($($tt:tt)*) => { nom_rule::rule!(
        $crate::match_text,
        $crate::match_token,
        $($tt)*)
    }
}

在databend中使用nom来实现递归下降sql解析器，其中有两个比较主要的parser组成
1、Terminal Parser：是最基本的解析器，用于匹配特定的TokenKind的Token。在databend中定义了match_token()和match_text()这两个Terminal Parser

fn match_text(text: &str) -> impl FnMut(&[Token]) -> IResult<&[Token], Token> {
    satisfy(|token: &Token| token.text == text)(i)
}

fn match_token(kind: TokenKind) -> impl FnMut(&[Token]) -> IResult<&[Token], Token> {
    satisfy(|token: &Token| token.kind == kind)(i)
}

2、 Combinator parser：允许将多个小的解析器组合成较大的解析器。也是构建复杂逻辑的基础。以下是一些常见的组合器：

 -* tuple(a, b, c)：会让多个 parser 按顺序排列（例如先是 a，然后是 b，接着是 c）。它们需要按照预期的顺序逐个成功才算作最后的成功。
 -* alt(a, b, c)：尝试多个 parser 分支（例如 a，b 或 c），直到满足第一个成功条件。如果全部失败，解析器将报告错误。
 -* many0(a)：贪婪地循环调用相同的 parser。如果无法继续，这个解析器将成功返回已匹配的 Token 序列。可能为空。
 -* many1(a)：贪婪地循环调用相同的 parser，但至少需要匹配成功一次。如果至少匹配成功一次，解析器会返回 Token 序列。
 -* opt(a)：允许 parser 失败。当 parser 失败时，将返回 `None`。成功时将返回成功匹配的结果。

举个例子：

 <select_statement> ::= SELECT <expr>+ FROM <ident>

接下来使用nom来组装语法树: 使用match_token识别关键字；使用many1来实现循环多个 <expr>+。

tuple((
    match_token(SELECT),
    many1(expr),
    match_token(FROM),
    match_token(Ident),
))

将‘select a+1 from t’进行token化和解析，结果如下：

Query {
    span: Some(0..17,),
    with: None,
    body: Select(
            SelectStmt {
                span: Some(0..17,),
                hints: None,
                distinct: false,
                select_list: [
                    AliasedExpr {
                        expr: BinaryOp {
                                span: Some(8..9,),
                                op: Plus,
                                left: ColumnRef {
                                    span: Some(7..8,),
                                    database: None,
                                    table: None,
                                    column: Name(
                                        Identifier {
                                            name: \"a\",
                                            quote: None,
                                            span: Some(7..8,),
                                        },
                                    ),
                                },
                                right: Literal {
                                      span: Some(9..10,),
                                      lit: UInt64(1,),
                                },
                        },
                        alias: None,
                    },
                ],
                from: [
                    Table {
                        span: Some(16..17,),
                        catalog: None,
                        database: None,
                        table: Identifier {
                            name: \"t\",
                            quote: None,
                            span: Some(16..17, ),
                        },
                        alias: None,
                        travel_point: None,
                        pivot: None,
                        unpivot: None,
                    },
                ],
                selection: None,
                group_by: None,
                having: None,
                window_list: None,
            },
    ),
    order_by: [],
    limit: [],
    offset: None,
    ignore_result: false,
}