徒手撸一个表达式引擎
MLSQL在最近版本中添加了if/else分支语句支持。一个典型的代码样例如下：
set a = "wow,jack";
!if ''' split(:a,",")[0] == "jack" ''';
select 1 as a as b;
!else;
select 2 as a as b;
!fi;
select * from b as output;
比较复杂的条件表达式：
set a="jack,2";
!if '''
select split(:a,",")[0] as :name, split(:a,",")[1] as :num;
:name == "jack" and :num == 3;
''';
MLSQL的条件判断语句具有以下特色：
- 语法设计遵循SQL的一些原则。比如采用 and/or 替代 &&,||.使用select语句做变量赋值
- 兼容大部分SQL函数
- 支持多个语句，最后一条语句作为最后的条件
- 支持用户自定义函数
对If/Else的完整使用说明可以参考这篇：MLSQL 支持条件分支语句。
实际上，我们在实现MLSQL条件表达式时，选择了完全手写了Lexer/Parser/Codegen三个部分，最终，Codegen会把条件表达式翻译成可以运行在SQL引擎上的代码。
完整实现代码在这里：mlsql-lang
实现代码比较少，总共7个文件：
语法设计
MLSQL条件表达式支持赋值以及比较。
赋值语法如下：
select 值表单式 as 变量名称,值表单式 as 变量名称....
值表单式表达式支持三类基础变量：
- 字符串
- 数字
- 布尔值
以及任意SQL函数组合和一些特殊用法，典型如：
- [数字] 取数组元数
- cast (变量 as 类型)
比较语句语法如下：
值表达式 比较运算符 值表达式
多个比较语法可以通过 and/or连接。
为什么不采用通用语言设计
比如赋值，为啥不采用如下方式：
:variable1 = "jack"
这样看起来似乎更简洁。实际上，我们面向的受众是仅仅懂一些SQL语法的人而不是专业的编程人员。我们希望表达式设计更像SQL一点，让大家很快能找到参考，易于学习。这样包括连接符我们采用了 and 或者 or 而不是通用语言的 && 或者 ||,因为他们更符合SQL中的且或使用。
另外，用户可能会疑问，为什么使用如下语法：
!if ''' split(:a,",")[0] == "jack" ''';
而不是
if split(:a,",")[0] == "jack"
确实，下面的语法更加简洁。之所以采用上面的语法比如if关键字前面加了个! 是因为我们在增加条件表达式的时候，是完全兼容标准MLSQL语法的。 严格来说 !if 并不是关键字，他只是一个命令，MLSQL引擎会自动将将上面的语法转化为如下的代码：
run command as IfCommand.`` where parameters='''['split(:a,",")[0] == "jack"' ]'''
也就是说，其实if/else也是利用MLSQL已经提供的扩展能力来实现的。在MLSQL语言层面，依然没有if/else语法结构，他们都只是一条一条命令而已。
Lexer/Tokenizer实现
上面说了一些设计思想，这里我们开始一些干货了。对于一个条件表达式，第一步是要实现一个词法分析器，其次是形成Ast树，最后根据场景需求，可能还有优化器，中间码，最后才是生成汇编代码，然后使用汇编器得到可执行二进制文件。 当然，在我们的场景里，仅仅会到中间码这一层，产生后会直接丢给我们的MLSQL Engine中的SQL引擎执行。
首先我们需要定义一个Scanner,这个Scanner会一个字符一个字符的扫描源码，然后将其解析成一个一个token. 在MLSQL条件表达式里，Token包含两个核心属性，一个是对应文本，一个是文本的所属类型。比如扫描如下语句
split(:a,",")[0] == "jack"
其中有一个Token，字面量（文本）会是:a,同时他还会有一个类型属性，他是一个变量。下面是Scanner中我们定义的一些类型：
val EOF_INT = (-2).toChar
val EOF = Value("EOF")
val Ident = Value("Ident")//关键字
val Variable = Value("Variable")//变量
val Int = Value("Int") //整数类型
val Float = Value("Float") //浮点数类型
val Char = Value("Char")
val String = Value("String") //字符串
val RawString = Value("RawString") //多行文本
val Comment = Value("Comment") // 注释
当然，类型可以比这个广泛，比如每个关键字就是一个类型，在MLSQL 条件表达式里， select目前是唯一的一个关键字。其次比如 左括号，右括号等等，都是单独的类型，我们需要一一罗列出来。
下面是目前实现中所有的枚举值，我去掉了大部分代码，只留下一部分，大家可以有个感觉。
object Scanner extends Enumeration {
type TokenType = Value
val EOF_INT = (-2).toChar
val EOF = Value("EOF")
....
val Lparen = Value("(") // (
val Lbrack = Value("[") // [
....
// keywords
val _SELECT = Value("select")
val _WHERE = Value("where")
// internal use only
val skipComment = Value("skipComment")
// operator
val AndAnd = Value("&&") // &&
val OrOr = Value("||") // ||
val Not = Value("!") // !
val Eql = Value("==") // ==
....
val _Or = Value("or")
val _Not = Value("not")
val _And = Value("and")
val _As = Value("as")
val OPERATOR_MAP = Map(
"&&" -> Scanner.AndAnd,
"||" -> Scanner.OrOr,
.....
)
val OPERATOR_SET = OPERATOR_MAP.values.toSet
val KEYWORD_MAP = Map(
"select" -> Scanner._SELECT,
"where" -> Scanner._WHERE
)
val KEYWORD_SET = KEYWORD_MAP.values.toSet
}
有了这些定义后，就可以定义一个Token了：
case class Token(t: Scanner.TokenType,
srcPos: Int, srcEnd: Int,
line: Int, column: Int,
scanner: Scanner) {
def text = {
(srcPos to srcEnd).map(scanner.srcChars(_)).mkString("")
}
}
我们并不记录Token的text值，而是通过位置得到的。Scanner的目标就是扫描字符串，然后将其转化为一个一个Token,Token包含了类型以及位置。整个过程是一个字符串不断匹配的过程。 因为我们对语法实现了严格的控制，可以做到只需要look ahead(多看几个字符)，而不需要回溯(查看以前的字符)，所以可以效率很高。
下面是一段典型的代码,大家有个感觉即可。
def scan: Scanner.TokenType = {
var ch = peek
while (whiteSpace(peek)) {
ch = next
}
ch = peek
lastTokenPos = srcPos
tok = Scanner.EOF
ch match {
case s if isVariable(ch, 1) =>
val tempSrcPos = srcPos
ch = scanVariable
tok = Scanner.Variable
if (srcPos - tempSrcPos == 1) {
error(": should be variable")
return Scanner.EOF
}
case s if isIdent(s, 1) =>
ch = scanIdent
tok = Scanner.Ident
val possibleKeyword = Scanner.KEYWORD_MAP.get(tokenString().toLowerCase())
if (possibleKeyword.isDefined) {
tok = possibleKeyword.get
} else {
val possibaleOperator = Scanner.OPERATOR_MAP.get(tokenString().toLowerCase)
if (possibaleOperator.isDefined) {
tok = possibaleOperator.get
}
}
最后整个用法可以通过一个测试用例来看：
test("tokenizer2") {
val items = Tokenizer.tokenize("""select split(:a,",") as :jack;""")
want(items, 0, Scanner._SELECT, "select")
want(items, 1, Scanner.Ident, "split")
want(items, 2, Scanner.Lparen, "(")
want(items, 3, Scanner.Variable, ":a")
want(items, 4, Scanner.Comma, ",")
want(items, 5, Scanner.String, "\",\"")
want(items, 6, Scanner.Rparen, ")")
want(items, 7, Scanner._As, "as")
want(items, 8, Scanner.Variable, ":jack")
//want(items,9,Scanner.Semi,";")
}
Parser
一旦我们得到了Token集合，此时他们是一个线性结构，无法体现实际的语义。比如 split(:a,",") 就被分成了split,（,:a,',','","',')'等六个Token,这六个Token等价于对split函数操作。所以为了方便形成语义以及进行后续的操作，我们需要将其转化为树形结构。这个过程我们称为Parser阶段。
Parser是以语句为粒度的。语句的分割符是分号，对应的实现是StatementParser,我们看下入口和签名：
class StatementParser(tokenizer: Tokenizer) extends Parser(tokenizer) {
def parseStatement(): TreeNode[_] = {
if (_match(Scanner.Semi))
return parseStatement()
if (_match(Scanner._SELECT))
return parseSelect()
parseExpression()
}
以Tokenizer为数据源，首先匹配分隔符，匹配上了意味着可以开始匹配一个完整语句了，其次匹配select语句，如果不是，那肯定就是比较表达式了。
在解析过程中，select 语句比较简单，多次匹配赋值语句即可：
比较困难的是中缀操作符，比如 a * (b + c) ,这意味着在解析过程中，我们可能需要一个中间存储，同时我们还需要知道操作符的优先级，并且我们只有遇到特定操作符的时候才能知道下一步该怎么办，比如遇到*,那么我们应该继续往后处理，而且后面可能又会是一个完整的表达式。大部分情况我们可能会使用函数栈来保留这个结构，然后再反向弹出，先得到(b+c),再得到*,再得到a。 对于这个，有一个标准的操作范式叫Pratt Parsers,用来解决这种表达式。我参考了这篇文章做的实现：Pratt Parsers: Expression Parsing Made Easy。具体就是一个for循环，不断的通过操作符不同得到对应的parser去解析，直到遇到终止条件。
在MLSQL条件表达式里，我们还支持and/or语法，所以这个是需要单独处理的地方。这些Parser处理后得到的都是表达式，他们会统一继承自Expression:
我们实现了Variable，Literal，Leq，As等各种表达式，parser的最后产物就是这些表达式形成的一个树状结构。值得注意的是，每个表达式都具备给自己生成SQL代码的能力，比如数组下表的实现如下：
红框部分会产生一个合法的SQL代码片段。我们最终会通过CodeGen将这些代码片段以一定的方式拼接起来丢给SQL引擎执行实际的运行动作。
代码生成部分
代码生成部分，我们的抽象很简单：
case class VariableTable(
name:String,
variables:mutable.HashMap[String,Any],
types:mutable.HashMap[String,Any])
trait CodegenContext {
def execute(
exprs: List[Expression],
variableTable: VariableTable): Any
}
给我一个表达式集合（保证合法顺序），我们会利用变量表（每个表达式执行完成后都会更新该变量表，并且传递给后一个表达式用于计算）。我们实现SQL版本的运行时，只需要惊人的83行代码,参看这里 SQLGenContext.scala。
其基本思想是，所有的变量都会转成表，所有的表达式都会被转化为SQL算子，这样就将对变量的处理转化成了SQL算子对表的处理。
我们举一个非常简单的例子。对于下面的语句：
split(:a,",")[0] == "jack" and :b == 10
我们知道有个:a,:b变量，这两个变量来自set语法，set语法本质上是一个Map[String,String],SQLGenContext会将这个Map转换成一个实际的SQL视图表。
示例中的语句被解析后，实际上顶层是一个AndAnd表达式，left 和 right部分我们会分别计算，left 语句最后被转成了如下语句执行：
select split(a,",")[0] == "jack" from 变量表;
同理right部分，最后根据两者求且关系。对于比较复杂的有嵌套and/or,因为我们使用自底向上的策略，所以可以递归处理。整个核心代码如下：
总结
MLSQL分支语句中的条件表达式，尽管我们采用了hand-craft模式带来了一定的复杂度，但是这可以让我们实现更好的性能以及更好的掌控。我们成功的让表达式语句支持SQL引擎，从而能够复用各种函数的实现，降低了用户的学习成本。