关于Databend源码-token解析

一、 databend自定义token实现

举个例子： 在databend中将sql进行token化生成最终的AST

// 使用logos进行lexer
let tokens = tokenize_sql(case).unwrap();
let backtrace = Backtrace::new();
// 生成sql的AST
let stmts = parse_sql(&tokens, &backtrace).unwrap();
// 
for stmt in stmts {
      writeln!(file, "---------- Output ---------").unwrap();
      writeln!(file, "{}", stmt).unwrap();
      writeln!(file, "---------- AST ------------").unwrap();
      writeln!(file, "{:#?}", stmt).unwrap();
      writeln!(file, "\n").unwrap();
}

在databend中将一个sql进行token化少不了的struct Tokenizer，主要是结合databend中定义token类型：enum TokenKind，底层使用logos来完成最终的词法解析。

pub struct Tokenizer<'a> {
    // 要被token化的原始sql
    source: &'a str,  
    // 用于token化的lexer：使用logos来进行词法解析              
    lexer: Lexer<'a, TokenKind>,
   // 
    eoi: bool,
}

看一下databend自身结合logos定义的一些token类型：TokenKind详情；
主要是通过#[derive(Logos)] 使用logos；

#[derive(Logos, Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum TokenKind {
    // 省略代码
    // 主要涉及：空白类、标识符、块类型、转义类、符号类、关键字类等
}

而logos进行词法解析的入口TokenKind::lexer(sql), logos是使用过程宏(proc_macro_derive)的方式,来为不同的自定义token化提供了lexer操作;进而得到每个token：kind(类型)/source(原始内容)/span(在原始内容串的范围)，具体代码如下:

impl<'a> Iterator for Tokenizer<'a> {
    // 得到databend里面定义Token
    type Item = Result<Token<'a>>;

    fn next(&mut self) -> Option<Self::Item> {
        match self.lexer.next() { // 在logos中Lexer实现了Iterator
            Some(kind) if kind == TokenKind::Error => { // 遍历token类型
                let rest_span = Token { // 不满意定义token规则的错误：看TokenKind中Error
                    source: self.source,
                    kind: TokenKind::Error,
                    span: self.lexer.span().start..self.source.len(),
                };
                Some(Err(ErrorCode::SyntaxException(rest_span.display_error( // 语法解析错误
                    "unable to recognize the rest tokens".to_string(),
                ))))
            }
            Some(kind) => Some(Ok(Token { // token解析正常
                source: self.source,
                kind,
                span: self.lexer.span(),
            })),
            None if !self.eoi => { // ??? 解析结束标识
                self.eoi = true;
                Some(Ok(Token {
                    source: self.source,
                    kind: TokenKind::EOI,
                    span: (self.lexer.span().end)..(self.lexer.span().end),
                }))
            }
            None => None,  // 没有可遍历的内容
        }
    }
}

再看看databend中定义的Token:

#[derive(Clone, PartialEq)]
pub struct Token<'a> {
    pub source: &'a str,      // token在被解析字符串的原始内容
    pub kind: TokenKind,   // token类型
    pub span: Span,          // token在解析字符串中的范围
}

完成token化: 主要是完成databend中自定义的token化

 // Tokenizer本身也实现Iterator trait，可以使用collect完成转为Result<Vec<Token>>
 Tokenizer::new(sql).collect::<Result<Vec<_>>>()

接下来就是将已经token化的Token生成Statement：使用nom文本解析器来完成该部分的；

/// Parse a SQL string into `Statement`s.
pub fn parse_sql<'a>(
    sql_tokens: &'a [Token<'a>],
    backtrace: &'a Backtrace<'a>,
) -> Result<Vec<Statement<'a>>> {
    match statements(Input(sql_tokens, backtrace)) {
        Ok((rest, stmts)) if rest[0].kind == TokenKind::EOI => Ok(stmts), // 结束标识
        Ok((rest, _)) => Err(ErrorCode::SyntaxException( // 语法解析异常
            rest[0].display_error("unable to parse rest of the sql".to_string()),
        )),
        Err(nom::Err::Error(err) | nom::Err::Failure(err)) => { // 解析异常
            Err(ErrorCode::SyntaxException(err.display_error(())))
        }
        Err(nom::Err::Incomplete(_)) => unreachable!(),
    }
}

最终输出databend本身的sql ast:

---------- Input ----------
show tables
---------- Output ---------
SHOW TABLES
---------- AST ------------
ShowTables {
    database: None,
    full: false,
    limit: None,
}

二、关于logos部分

• 准备: cargo.toml中引入logos

[dependencies]
logos = "0.12.0"

• 使用：自定义Token

#[derive(Logos, Debug, PartialEq)]
enum Token {
    #[token("fast")]
    Fast,

    #[token(".")]
    Period,

    #[regex("[a-zA-Z]+")]
    Text,

    #[error]
    #[regex(r"[ \t\n\f]+", logos::skip)]
    Error,

    #[regex("[0-9]+", |lex| lex.slice().parse())]
    #[regex("[0-9]+k", kilo)]
    #[regex("[0-9]+m", mega)]
    Number(u64),
}

• 测试

// 解析简单的文本
#[test]
fn test_lexer_token_demo () {
    let mut tokens = Token::lexer("Create ridiculously fast Lexers.");
    assert_eq!(tokens.next(), Some(Token::Text));
    assert_eq!(tokens.span(), 0..6);
    assert_eq!(tokens.slice(), "Create");

    assert_eq!(tokens.next(), Some(Token::Text));
    assert_eq!(tokens.span(), 7..19);
    assert_eq!(tokens.slice(), "ridiculously");

    assert_eq!(tokens.next(), Some(Token::Fast));
    assert_eq!(tokens.span(), 20..24);
    assert_eq!(tokens.slice(), "fast");

    assert_eq!(tokens.next(), Some(Token::Text));
    assert_eq!(tokens.span(), 25..31);
    assert_eq!(tokens.slice(), "Lexers");

    assert_eq!(tokens.next(), Some(Token::Period));
    assert_eq!(tokens.span(), 31..32);
    assert_eq!(tokens.slice(), ".");

    assert_eq!(tokens.next(), None);
}

在自定义token中，定义回调函数:

// 使用自定义回调函数
#[regex("[0-9]+", |lex| lex.slice().parse())]
#[regex("[0-9]+k", kilo)]   
#[regex("[0-9]+m", mega)]
Number(u64),

回调函数如下：

fn kilo(lex: &mut Lexer<Token>) -> Option<u64> {
    eprintln!("==execute kilo==");
    let slice = lex.slice();
    let n: u64 = slice[..slice.len() - 1].parse().ok()?;
    Some(n * 1_000)
}

fn mega(lex: &mut Lexer<Token>) -> Option<u64> {
    eprintln!("==execute mega==");
    let slice = lex.slice();
    let n: u64 = slice[..slice.len() - 1].parse().ok()?;
    Some(n * 1_000_000)
}

用例：

#[test]
fn test_callback_lexer_demo() {
    let mut lexer = Token::lexer("5 42k 75m");
    assert_eq!(lexer.next(), Some(Token::Number(5)));
    assert_eq!(lexer.span(), 0..1);
    assert_eq!(lexer.slice(), "5");

    assert_eq!(lexer.next(), Some(Token::Number(42_000)));
    assert_eq!(lexer.span(), 2..5);
    assert_eq!(lexer.slice(), "42k");

    assert_eq!(lexer.next(), Some(Token::Number(75_000_000)));
    assert_eq!(lexer.span(), 6..9);
    assert_eq!(lexer.slice(), "75m");

    assert_eq!(lexer.next(), None);
}

三、引用

logos
nom