首先声明，我不是标题党，我真的是用5000行左右的JS实现了一个轻量级的关系型数据库JSDB，核心是一个SQL编译器，支持增删改查。
源代码放到github上了：https://github.com/lavezhang/jsdb
如果你需要修改程序引入新的特性，请严格遵守GPL协议。
如果转发此文，请注明来源。
前言
工作太忙，好久没写这种长文章了，难得今年国庆超长，又不便外出，这才有时间“不务正业”。
为什么要用一周的时间写这么个玩意儿？看起来也没什么用处，毕竟，没有哪个系统需要在浏览器中跑一个关系型数据库。
如果要搞一个"年度最无用项目"的颁奖，估计JSDB榜上有名。
我一直有一个梦想，要研发一款咱们中国人自己的列式存储分布式数据库！（此处应有掌声^_^）
古人讲，不积跬步无以至千里，JSDB就算探索数据库自研的一个开端吧。
为什么用TypeScript？因为coding效率非常高，跟Python差不多，而且有浏览器就能运行，非常方便，很适合做技术预研，正式开发时再改为C或Rust。
如文章开头所言，JSDB的核心是一个SQL编译器，准确地说，是解释器。学习过《编译原理》的同学，对这个不会陌生。
解释器也是属于编译器的范畴，所以，后面仍然会沿用“SQL编译器”的说法。
概述
按照执行顺序，JSDB的代码由四个部分构成：
1、词法分析，得到 token 列表。参见GitHub源代码，SqlLexer.ts 文件，基于状态机实现，详见 lex_state_flow.xlsx 文件。
2、语法语义分析，得到抽象语法数。参见 SqlParser.ts 文件，自上而下解析，这是行数最多的一个文件。
3、对抽象语法树的执行。参见SqlDatabase.ts文件，以及ast目录下的几十个语法节点的compute(ctx)方法。
4、单元测试和应用范例。test目录和test.html文件里运行着所有的单元测试，index.html文件就是文章开头的体验页面，语法高亮功能基于第三方组件codemirror实现，在 static/codemirror 目录里。
JSDB确实是一个关系型数据库，参照SQL92标准实现，但它并不完整，只实现了最核心的一小部分功能，可以满足日常基本需求。主要特性有：
01、create table 语句
02、insert 语句
03、update 语句
04、delete 语句
05、select 语句，含：distinct / from / join / left join / where / group by / having / order by / limit
06、算数运算符：+、-、*、/、%
07、关系运算符：>、>=、<、<=、=、<>
08、条件运算符：and、or、not
09、其它操作符：like、not like、is null、is not null、between
10、动态占位符：?
11、标准函数，目前只实现了：ifnull、len、substr、substring、instr、concat。
如果需要增加新的标准函数，可以在SqlContext类的构造函数中实现，所有的标准函数都注册到SqlContext.standardFunctions字段中。
尚未实现的重要特性有：
1、with / sub query / exists / alter / truncate 等
2、数据存储。一直在内存中运行，大家可以修改程序，写入浏览器localStorage中。
3、事务。这个需要事务日志来实现，以后再搞，不过在内存中模拟一个，问题也不大。
4、并发锁。JS是单线程，没有真正的并发，有了一个不用实现它的好理由。
5、其它功能。详见大学时的《数据库原理》。
如果大家多多点赞，我就把它实现得更加完整。^_^
本文针对编译器和数据库的入门读者，写了很多小白的内容，高手请飘过。
第一章 词法分析
关于词法分析，程序本身并不难。无论何种编程语言，它的词法分析模块一般都不超过300行，有些甚至只有几十行。
很多人喜欢用 lex/yacc/antr 之类的工具来自动生成，我不喜欢，我就是喜欢手撸的感觉。
词法分析就是要识别源代码中的一个个token，一般包括：关键字、标识符、字符串、数值、布尔值、空值、运算符、操作符、分隔符。
例如，一条SQL语句：
select name, (total_score / 4) as avg_score from student where id = ‘010123‘
涉及如下token：
关键字：select、as、from、where
标识符：name、total_score、avg_score、student、id
字符串：‘010123‘
数值：4
运算符：/、=
分隔符：, ( )
如何识别这些token呢？两种办法：硬实现、状态机。
硬实现，就是用一大坨的 if/else 识别每一个字符。
举例来说，如果当前字符是一个单引号，程序就认为是一个字符串的开始，于是用一个while循环来判断，直到遇到另一个单引号，表示字符串的结束。
硬实现的最大问题在于，条件分支太多，很容易遗漏或判断错误。
比如，字符串中是要处理转义符的，遇到换行符则要记录错误。
再比如，‘>=‘ 和 ‘> =‘ 是不一样的，前者表示大于等于号，后者表示两个运算符：大于号和等于号，因为中间有个空格，而硬写的程序往往会忽略掉这些空白符，什么时候空白符该忽略，什么时候不该忽略，必须把规则一条条列出来，针对处理。
类似的情况还非常多，所以，硬写出来的词法分析程序，无一例外，都是非常复杂的。
给大家看一段用 java 硬实现的字符串识别程序：
if (c == ‘\‘‘) {
while (pos < len) {
c = source.charAt(pos++);
if (c == ‘\\‘) {
c = source.charAt(pos++);
if (c == ‘n‘) {
buf.append(‘\n‘);
} else if (c == ‘r‘) {
buf.append(‘\r‘);
} else if (c == ‘t‘) {
buf.append(‘\t‘);
} else {
buf.append(c);
}
} else if (c == ‘\‘‘) {
return addToken(buf.toString(), SqlConstants.STRING, line);
} else {
buf.append(c);
}
}
}
上述java程序是我很久之前写的，整个词法程序漏洞百出。
即使是硬实现，也要提前梳理各种转换关系，既然这样，为什么不用状态机呢？
状态机是老一辈计算机科学家发明的理论，基于状态机和BNF产生式，词法分析程序完全可以被形式化了。
一个字符串识别的状态机范例如下：
一个字符串就涉及4个状态，完整的SQL词法涉及几十个状态，如果都用状态流转图画出来，实在太复杂，所以，一般都改用等价的表格来表示。
我在github上放了一个叫 lex_state_flow.xlsx 的Excel文件，截图如下：
需要特别解释两点：
1、状态2到状态6的名字用紫色标记，因为这几个状态是中间状态，最终不能独立存在。
2、状态转换的单元格有三种颜色：灰色、白色、红色。
灰色表示回到初始状态；
白色表示正数状态，转换状态时，前面的缓存内容作为一个token，当前新字符进入新的状态；比如，当前状态是 TK_IDENTITY，这时输入一个字符 ‘>‘，则缓冲区的内容得到一个标识符token，新输入的 ‘>‘ 字符进入 TK_GT 状态。
红色表示负数状态，转换状态时，前面的内容加上当前字符一起进入新的状态。比如，当前状态是 TK_GT，这时输入一个字符 ‘=’，则缓冲区的内容 ‘>‘ 加上新输入的 ‘=‘，得到 ‘>=‘ ，进入新的状态 TK_GE，表示大于等于。
词法分析的核心，正是这个状态表格。要完成这样一张表格，看着容易，实际并不容易，我也是花了一天时间。因为一旦遗漏了某个状态或输入字符，整个表格都要改一遍，撸得手都起茧子了。
完成状态表格后，基于此实现的词法扫描程序，就可以非常简单了。文件名为 SqlLexer.ts，代码如下：
const TK_START = 0; //起始
const TK_ERROR = 1; //错误
const TK_IDENTITY = 7; //标识符（下划线当作字母处理）
const TK_INT = 8; //整数（不支持科学计数法）
const TK_FLOAT = 9; //浮点数（不支持科学计数法）
const TK_GT = 10; //操作符：大于 >
const TK_LT = 11; //操作符：小于 <
const TK_GE = 12; //操作符：大于等于 >=
const TK_LE = 13; //操作符：小于等于 <=
const TK_EQ = 14; //操作符：等于 =
const TK_NE = 15; //操作符：不等于 <>
const TK_ADD = 16; //操作符：加 +
const TK_SUB = 17; //操作符：减 -
const TK_MUL = 18; //操作符：乘 *
const TK_DIV = 19; //操作符：除 /
const TK_MOD = 20; //操作符：模（取余） %
const TK_MOVE_LEFT = 21; //操作符：左移 <<
const TK_MOVE_RIGHT = 22; //操作符：右移 >>
const TK_DOT = 23; //分隔符：点 .
const TK_OPEN_PAREN = 24; //分隔符：左圆括号 (
const TK_CLOSE_PAREN = 25; //分隔符：右圆括号 )
const TK_COMMA = 26; //分隔符：逗号 ,
const TK_HOLD = 27; //占位符 ?
const TK_COMMENT = 28; //注释 /**/
const TK_STRING = 29; //字符串 ‘abc‘
const TK_SELECT = 50; //关键字：select
const TK_FROM = 51; //关键字：from
const TK_WHERE = 52; //关键字：where
const TK_AS = 53; //关键字：as
const TK_DISTINCT = 54; //关键字：distinct
const TK_LEFT = 55; //关键字：left
const TK_JOIN = 56; //关键字：join
const TK_ON = 57; //关键字：on
const TK_CASE = 58; //关键字：case
const TK_WHEN = 59; //关键字：when
const TK_THEN = 60; //关键字：then
const TK_ELSE = 61; //关键字：else
const TK_END = 62; //关键字：end
const TK_IS = 63; //关键字：is
const TK_NOT = 64; //关键字：not
const TK_NULL = 65; //关键字：null
const TK_TRUE = 66; //关键字：true
const TK_FALSE = 67; //关键字：false
const TK_AND = 68; //关键字：and
const TK_OR = 69; //关键字：or
const TK_BETWEEN = 70; //关键字：between
const TK_IN = 71; //关键字：in
const TK_LIKE = 72; //关键字：like
const TK_GROUP = 73; //关键字：group
const TK_BY = 74; //关键字：by
const TK_HAVING = 75; //关键字：having
const TK_ORDER = 76; //关键字：order
const TK_ASC = 77; //关键字：asc
const TK_DESC = 78; //关键字：desc
const TK_LIMIT = 79; //关键字：limit
const TK_INSERT = 80; //关键字：insert
const TK_INTO = 81;//关键字：into
const TK_VALUES = 82;//关键字：values
const TK_UPDATE = 83;//关键字：update
const TK_SET = 84;//关键字：set
const TK_DELETE = 85;//关键字：delete
const TK_CREATE = 86;//关键字：create
const TK_TABLE = 87;//关键字：table
/**
* 词法状态流转图。
* 详见：lex_state_flow.xlsx 文件。
*/
const STATE_FLOW_TABLE = [
[0, 0, 8, 7, 1, 4, 1, 16, 17, 18, 19, 20, 10, 11, 14, 24, 25, 26, 27, 1],
[0, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
[-2, -2, -2, -2, -2, -2, -2, -2, -2, -3, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2],
[-2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -28, -2, -2, -2, -2, -2, -2, -2, -2, -2],
[-5, -1, -5, -5, -5, -29, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5],
[-5, -1, -5, -5, -5, -29, -6, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5],
[-5, -1, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5],
[0, 0, -7, -7, 23, -1, -1, 16, 17, 18, 19, 20, 10, 11, 14, 24, 25, 26, 27, -1],
[0, 0, -8, -1, -9, -1, -1, 16, 17, 18, 19, 20, 10, 11, 14, 24, 25, 26, 27, -1],
[0, 0, -9, -1, -1, -1, -1, 16, 17, 18, 19, 20, 10, 11, 14, 24, 25, 26, 27, -1],
[0, 0, 8, 7, -1, 4, -1, 16, 17, -1, 19, -1, -22, -1, -12, 24, -1, -1, 27, -1],
[0, 0, 8, 7, -1, 4, -1, 16, 17, -1, 19, -1, -15, -21, -13, 24, -1, -1, 27, -1],
[0, 0, 8, 7, -1, 4, -1, 16, 17, -1, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
[0, 0, 8, 7, -1, 4, -1, 16, 17, -1, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
[0, 0, 8, 7, -1, 4, -1, 16, 17, -1, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
[0, 0, 8, 7, -1, 4, -1, 16, 17, -1, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
[0, 0, 8, 7, -1, 4, -1, 16, 17, -1, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
[0, 0, 8, 7, -1, -1, -1, 16, 17, -1, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
[0, 0, 8, 7, -1, -1, -1, 16, 17, -1, -1, -1, -1, -1, -1, 24, 25, 26, 27, -1],
[0, 0, 8, 7, -1, -1, -1, 16, 17, -2, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
[0, 0, 8, 7, -1, -1, -1, 16, 17, -1, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
[0, 0, 8, 7, -1, -1, -1, 16, 17, -1, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
[0, 0, 8, 7, -1, -1, -1, 16, 17, -1, 19, -1, -1, -1, -1, 24, -1, -1, 27, -1],
[0, 0, 1, 7, -1, -1, -1, -1, -1, 18, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1],
[0, 0, 8, 7, -1, 4, -1, 16, 17, 18, -1, -1, -1, -1, -1, 24, 25, -1, 27, -1],
[0, 0, 1, 7, -1, -1, -1, 16, 17, 18, 19, 20, 10, 11, 14, 24, 25, 26, -1, -1],
[0, 0, 8, 7, -1, 4, -1, 16, 17, -1, -1, -1, -1, -1, -1, 24, -1, -1, 27, -1],
[0, 0, 1, -1, -1, -1, -1, 16, 17, 18, 19, 20, 10, 11, 14, -1, 25, 26, -1, -1],
[0, 0, 8, 7, -1, 4, -1, 16, 17, 18, 19, 20, 10, 11, 14, 24, 25, 26, 27, -1],
[0, 0, 1, 7, -1, -1, -1, 16, -1, -1, 19, -1, 10, 11, 14, -1, 25, 26, -1, -1]
];
/**
* SQL词法分析类。
*/
class SqlLexer {
/**
* 扫描指定的SQL语句，返回所有单词。
* 用一个元组来表示单词的三个字段：类型（状态）、内容、行号（从1开始）。
* @param sql 要扫描的SQL语句。
*/
public scan(sql: string): Array<[number, string, number]> {
let tokens = new Array<[number, string, number]>();
let pos = 0;
let len = sql.length;
let buf = ‘‘;
let c = ‘‘;
let j = 0;
let state = TK_START;
let beginLine = 1;
let totalLine = 1;
while (pos < len) {
c = sql[pos++];
if (c == ‘ ‘ || c == ‘\t‘ || c == ‘\r‘) {
j = 0;
} else if (c == ‘\n‘) {
j = 1;
} else if (c >= ‘0‘ && c <= ‘9‘) {
j = 2;
} else if ((c >= ‘a‘ && c <= ‘z‘) || (c >= ‘A‘ && c <= ‘Z‘) || c == ‘_‘) {
j = 3;
} else if (c == ‘.‘) {
j = 4;
} else if (c == ‘\‘‘) {
j = 5;
} else if (c == ‘\\‘) {
j = 6;
} else if (c == ‘+‘) {
j = 7;
} else if (c == ‘-‘) {
j = 8;
} else if (c == ‘*‘) {
j = 9;
} else if (c == ‘/‘) {
j = 10;
} else if (c == ‘%‘) {
j = 11;
} else if (c == ‘>‘) {
j = 12;
} else if (c == ‘<‘) {
j = 13;
} else if (c == ‘=‘) {
j = 14;
} else if (c == ‘(‘) {
j = 15;
} else if (c == ‘)‘) {
j = 16;
} else if (c == ‘,‘) {
j = 17;
} else if (c == ‘?‘) {
j = 18;
} else {
j = 19;
}
//如果新状态的值小于0，表示带着当前缓存区的内容，直接转换到新的状态；
//如果新状态的值大于等于0，则用当前缓冲区的内容构造一个旧状态的单词，然后从当前字符开始进入新的状态。
let nextState = STATE_FLOW_TABLE[state][j];
if (nextState < 0) {
buf += c;
} else {
let token = this.newToken(state, buf, beginLine);
if (token) {
tokens.push(token);
beginLine = totalLine;
}
buf = j > 1 ? c : ‘‘;
if (c == ‘\n‘) {
beginLine++;
}
}
state = Math.abs(nextState);
//处理最后一个单词
if (pos >= len) {
let token = this.newToken(state, buf, beginLine);
if (token) {
tokens.push(token);
beginLine = totalLine;
}
} else if (c == ‘\n‘) {
totalLine++;
}
}
return tokens;
}
private newToken(state: number, value: string, line: number): [number, string, number] {
if (value.length <= 0) {
return null;
}
if (state == TK_IDENTITY) {
value = value.toLowerCase();
switch (value) {
case ‘select‘:
state = TK_SELECT;
break;
case ‘from‘:
state = TK_FROM;
break;
case ‘where‘:
state = TK_WHERE;
break;
case ‘as‘:
state = TK_AS;
break;
case ‘distinct‘:
state = TK_DISTINCT;
break;
case ‘left‘:
state = TK_LEFT;
break;
case ‘join‘:
state = TK_JOIN;
break;
case ‘on‘:
state = TK_ON;
break;
case ‘case‘:
state = TK_CASE;
break;
case ‘when‘:
state = TK_WHEN;
break;
case ‘then‘:
state = TK_THEN;
break;
case ‘else‘:
state = TK_ELSE;
break;
case ‘end‘:
state = TK_END;
break;
case ‘is‘:
state = TK_IS;
break;
case ‘not‘:
state = TK_NOT;
break;
case ‘null‘:
state = TK_NULL;
break;
case ‘true‘:
state = TK_TRUE;
break;
case ‘false‘:
state = TK_FALSE;
break;
case ‘and‘:
state = TK_AND;
break;
case ‘or‘:
state = TK_OR;
break;
case ‘between‘:
state = TK_BETWEEN;
break;
case ‘in‘:
state = TK_IN;
break;
case ‘like‘:
state = TK_LIKE;
break;
case ‘group‘:
state = TK_GROUP;
break;
case ‘by‘:
state = TK_BY;
break;
case ‘having‘:
state = TK_HAVING;
break;
case ‘order‘:
state = TK_ORDER;
break;
case ‘asc‘:
state = TK_ASC;
break;
case ‘desc‘:
state = TK_DESC;
break;
case ‘limit‘:
state = TK_LIMIT;
break;
case ‘insert‘:
state = TK_INSERT;
break;
case ‘into‘:
state = TK_INTO;
break;
case ‘values‘:
state = TK_VALUES;
break;
case ‘update‘:
state = TK_UPDATE;
break;
case ‘set‘:
state = TK_SET;
break;
case ‘delete‘:
state = TK_DELETE;
break;
case ‘create‘:
state = TK_CREATE;
break;
case ‘table‘:
state = TK_TABLE;
break;
default:
break;
}
} else if (state > TK_ERROR && state < TK_IDENTITY) {//无效字符
state = TK_ERROR;
}
return [state, value, line];
}
}
细心的同学可能会发现，代码里的关键字状态，并没有出现在状态表格中。
原则上来讲，每个关键字都是一个单独的状态。但是，如果都列入状态表格，这个表格就超级复杂了。比如，为了识别一个关键字select，要依次检查连续字符 ‘s’ ‘e‘ ‘l‘ ‘e‘ ‘c‘ ‘t‘ ，即使到了最后一个字符 ‘t‘ ，也不意味着结束，后面跟上一个数字 ‘1‘，立马就不是关键字了，而是一个普通的标识符 select1。而JSDEB一共支持38个关键字，都要并入表格，简直难以想象。所以，通常的做法是，先统一作为标识符来识别，完成一个token时，再进一步判断是否为某个关键字，而在状态表格中就不画了。
一个token用一个三元组来表达，在TypeScript中是Tuple类型，实际就是JavaScript中的数组。这里有三个值，分别是number、string、number类型。
第0个值，number类型，表示token的类型，对应于状态表格中的状态id；
第1个值，string类型，表示token的内容，对于字符串 ‘abc‘ 来说，存的不是 abc，而是 ‘abc‘，也就是说，原原本本保存，后面在执行的时候才会翻译为 abc；
第2个值，number类型，表示token所在的行号，提示词法错误的时候，可以明确告知在哪一行。
有的同学可能会问，为什么不用一个class来表示。其实也可以用class表示，但是，扫描一段源代码，得到的token非常多，如果用class表示，会浪费更多的资源，不如用数组，返璞归真，简单实用。
用一组单元测试来验证程序是否正确。
代码中的Assert类是一个简单的断言类，用于单元测试中的条件检查。
/test/SqlLexerTest.ts 文件包含了所有词法扫描的测试用例。截取一段代码如下：
Assert.runCase(‘scan identity‘, function () {
let lexer = new SqlLexer();
let tokens = lexer.scan(‘id _name‘);
Assert.isEqual(tokens.length, 2);
Assert.isEqual(tokens[0], [TK_IDENTITY, ‘id‘, 1]);
Assert.isEqual(tokens[1], [TK_IDENTITY, ‘_name‘, 1]);
});
到这里词法分析就结束了，得到一个token列表，接下来，会对这个token列表进行扫描，也就是语法解析。
第二章 语法解析
语法解析也叫语法分析，读入token列表，输出抽象语法树。
在编译器设计中，以抽象语法树的形式构造一条SQL语句。例如SQL：
SELECT id, t.stf_name AS name FROM student t WHERE id = 123
会被解析成如下树结构：
自上而下，递归解析，识别出每一个节点。
每种语法节点都是一个单独的class，比如，SqlSelectNode、SqlFromNode、SqlWhereNode、SqlIdentityNode、StringNumberNode，等等。
数量有点多，一共39个。这39个类都是继承自语法节点基类SqlNode。
/**
* SQL语法节点基类。
*/
class SqlNode {
/**
* 构造函数。
* @param parent 父节点。
* @param value 节点值
* @param line 所在行号（从1开始）。
*/
protected constructor(parent: SqlNode, value: string, line: number) {
this.parent = parent;
if (parent) {
parent.nodes.push(this);
}
this.value = value;
this.line = line;
this.nodes = [];
}
public value: string;
public line: number;
public parent: SqlNode;
public nodes: Array<SqlNode>;
/**
* 类型推导。
* @param ctx 上下文。
*/
public typeDeriva(ctx: SqlContext): SqlColumnType {
return SqlColumnType.varchar;
}
/**
* 计算节点的值。
* @param ctx 上下文。
*/
public compute(ctx: SqlContext): any {
return null;
}
}
详细介绍一下：
value字段，用于保存节点的值。SqlStringNode存的是类似 ‘abc‘这样的值，SqlNumber存的是类似 123 这样的值，SqlSelectNode存的是 select。
line字段，用于保存节点所在的行号。这个行号是从前一阶段的词法分析中得到的，就是token三元组的最后一个值。
nodes字段，用于保存子节点。例如，SqlExpAddNode的value是 + 或 - ，它的nodes是两个表达式节点，表示这个表达式的结果相加或相减。
compute方法，用于计算表达式的值。例如，id = 3，如果运行时id的值为3，则运行时返回True，否则返回False。再例如，a * 3，如果运行时a的值为10，则运行时返回30。
typeDeriva方法，用于类型推导。如果数据库列id是number类型，那么 id + 100 的结果也应该是numer类型；如果 id列是varchar类型，那么 id + 100也是varchar类型。这就是类型推导。
类型推导非常重要，主要用于类型安全检查。比如，count(*)的结果一定是numer类型，如果写出 substr(count(*),1) 这样的表达式，就应该给出语法错误。此外，类型推导还可以用于提前确定查询结果集中每一列的类型，构造好结果集，以容纳接下来返回的数据。比如，对于C#或Java，查询数据库后得到DataTable或RecordSet，可以获取到每一列的类型信息，这些类型信息在正式查询数据库之前通过语法分析就已经得到了。
推导出的类型，理论上来说，应该跟compute方法返回的值，保持一致。
实现各个语法节点子类的时候，重点是重写compute和typeDeriva这两个方法。
接下来讲如何构造这些语法节点。
有的节点具有明确的特征，比如 select节点，以关键字SELECT开头，只要扫描这个关键字，就可以认为是一条SELECT语句，然后按照SELECT语句的规则继续往下扫描。
有的节点则不那么容易判断，具有二义性。
比如 减号 -，如果是 a - b，则表示相减；如果是a = -b，则表示负号。
再比如关键字 AND，如果是 a AND b，则表示条件与；如果是 a BETWEEN b AND c，则表示一个数值范围或字符串范围。
这种情况下，需要通过上下文分析、优先级判断、消除文法左递归的办法，来消除二义性。
JSDB实现的只是SQL92的子集，SELECT语法如下：
select -> ‘select‘ [‘distinct‘] fields [from] [where] [groupby] [having] [orderby] [limit] fields -> field [‘,‘ field]* insert -> ‘insert‘ ‘into‘ identity ‘values‘ ‘(‘ identity [‘,‘ identity] * ‘)‘ ‘values‘ params update -> ‘update‘ identity ‘set‘ identity ‘=‘ exp_or [‘,‘ identity ‘=‘ exp_or]* [ where ] delete -> ‘delete‘ ‘from‘ identity [ where ] create_table -> ‘create‘ ‘table‘ identity ‘(‘ field_declare [‘,‘ field_declare] ‘)‘ field_declare-> identity (‘varchar‘ | ‘number‘) from -> ‘from‘ table field -> exp_or [[‘as‘] identity] table -> identity [‘as‘ identity] join -> [‘left‘] ‘join‘ table ‘on‘ exp_or where -> ‘where‘ exp_or groupby -> ‘group‘ ‘by‘ exp_or [‘,‘ exp_or]* having -> ‘having ‘ [exp_or] orderby -> ‘order‘ ‘by‘ order [‘,‘ order]* order -> exp_or [‘asc‘ | ‘desc‘] limit -> ‘limit‘ exp_or [‘,‘ exp_or] params -> ‘(‘ exp_or [‘,‘ exp_or]+ ‘)‘ exp_or -> exp_or ‘or‘ exp_and | exp_and exp_and -> exp_and ‘and‘ exp_eq | exp_eq exp_eq -> exp_eq (‘=‘ | ‘<>‘ | ‘in‘ | ‘not‘ ‘in‘ | ‘is‘ | ‘is‘ ‘not‘ | ‘between‘ | ‘like‘ | ‘not‘ ‘like‘) exp_rel | exp_rel exp_rel -> exp_add (‘<‘ | ‘<=‘ | ‘>‘ | ‘>=‘) exp_add | exp_add exp_add -> exp_add (‘+‘ | ‘-‘) exp_mult | exp_mult exp_mul -> exp_mul (‘*‘ | ‘/‘ | ‘%‘) exp_unary | exp_unary exp_unary -> (‘+‘ | ‘-‘ | ‘not‘) exp_unary | factor exp_ref -> identity ‘.‘ (identity | ‘*‘) exp_func -> identity ‘(‘ exp_or [‘,‘ exp_or]* | empty) ‘)‘ exp_case -> ‘case‘ [exp_or] [‘when‘ exp_or ‘then‘ exp_or]+ [‘else‘ exp_or] ‘end‘ exp_hold -> ‘?‘ factor -> identity | string | number | bool | star | exp_hold | exp_ref | exp_func | exp_case | ‘(‘ exp_or ‘)‘ identity -> (‘_‘ | a-z | A-Z)[‘_‘ | a-z | A-Z | 0-9]* star -> ‘*‘ string -> ‘‘‘ (*)* ‘‘‘ number -> [0-9]+ [‘.‘ [0-9]+] bool -> ‘true‘ | ‘false‘ null -> ‘null‘
由于简化了SELECT语法，所以相对来说还算简单。唯一有难度的地方，在于表达式的解析，采用的方法是抄自“龙书”《编译原理》。
自上而下，根据优先级，依次解析 exp_or、exp_and、exp_eq、exp_rel、exp_add、exp_mult、exp_unary、factor。
先看一个简单点的方法，parseExpRefNode，用于解析类似 t.id 这样的字段引用表达式。
先尝试解析第一个标识符，然后是一个分隔符点，最后是结尾的标识符。如果解析失败，则添加一个SqlError。
public parseExpRefNode(parent: SqlNode): SqlExpRefNode {
let beginToken = this.peekAndCheck();
if (!beginToken) {
return null;
}
let beginIndex = this.pos;
let node1 = this.parseIdentityNode(null);
if (!node1) {
this.moveTo(beginIndex);
return null;
}
let dotToken = this.peek();
if (!dotToken || dotToken[0] != TK_DOT) {
this.moveTo(beginIndex);
return null;
}
let endToken = this.moveNext();
if (!endToken) {
this.errors.push(new SqlError(‘语法错误：‘ + beginToken[1] + ‘后缺少引用项的名称。‘, beginToken[2]));
return null;
}
if (endToken[0] == TK_MUL || endToken[0] == TK_IDENTITY) {
this.moveNext();
return new SqlExpRefNode(parent, beginToken[1] + dotToken[1] + endToken[1], beginToken[2]);
}
this.errors.push(new SqlError(‘语法错误：‘ + beginToken[1] + ‘后的引用项无效。‘, beginToken[2]));
return null;
}
接下来看parseExpOrNode、parseExpAndNode两个方法，分别用于解析条件OR和AND的节点。由于函数是一层层调用进去的，所以，实际上的构造节点顺序是反过来的，从factor开始，然后才依次是 unary、mult、add、rel、req、and、or 。
先是从左到右挨个解析，放到一个列表中，然后把列表中的元素转换为一棵二叉树，函数返回的是这棵二叉树的根节点。
parseExpOrNode类：
public parseExpOrNode(parent: SqlNode): SqlExpOrNode {
let beginToken = this.peekAndCheck();
if (!beginToken) {
return null;
}
let node1 = this.parseExpAndNode(parent);
if (this.errors.length > 0) {
return null;
}
if (node1 == null) {
if (this.errors.length == 0) {
this.errors.push(new SqlError(‘词法错误：解析逻辑或表达式失败。‘, beginToken[2]));
}
return null;
}
let nodeList = [node1];
let opToken = this.peek();
while (opToken && opToken[0] == TK_OR) {
let node = new SqlExpOrNode(parent, opToken[1], opToken[2]);
nodeList.push(node);
let node2Token = this.moveNext();
if (!node2Token) {
this.errors.push(new SqlError(‘词法错误：符号‘ + opToken[1] + "后面缺少表达式。", opToken[2]));
return null;
}
let node2 = this.parseExpAndNode(parent);
if (this.errors.length > 0) {
return null;
}
if (!node2) {
if (this.errors.length == 0) {
this.errors.push(new SqlError(‘词法错误：解析符号‘ + opToken[1] + "右侧表达式失败。", opToken[2]));
}
return null;
}
nodeList.push(node2);
opToken = this.peek();
}
if (nodeList.length % 2 == 0) {
this.errors.push(new SqlError(‘词法错误：逻辑或表达式数量错误。‘, opToken[2]));
return null;
}
//把列表转换为二叉树
let rootNode = null;
for (let i in nodeList) {
let node = nodeList[i];
if (!rootNode) {
rootNode = node;
} else if (node instanceof SqlExpOrNode) {
this.setNodeParent(rootNode, node);
rootNode = node;
} else {
this.setNodeParent(node, rootNode);
}
}
if (parent && rootNode) {
this.setNodeParent(rootNode, parent);
}
return rootNode;
}
parseExpAndNode类：
public parseExpAndNode = function (parent): SqlExpAndNode {
let beginToken = this.peekAndCheck();
if (!beginToken) {
return null;
}
let node1 = this.parseExpEqNode(parent);
if (this.errors.length > 0) {
return null;
}
if (!node1) {
this.errors.push(new SqlError(‘词法错误：解析逻辑与表达式失败。‘, beginToken[2]));
return null;
}
let nodeList = [node1];
let opToken = this.peek();
while (opToken && opToken[0] == TK_AND) {
let node = new SqlExpAndNode(parent, opToken[1], opToken[2]);
nodeList.push(node);
let node2Token = this.moveNext();
if (!node2Token) {
this.errors.push(new SqlError(‘词法错误：符号‘ + opToken[1] + "后面缺少表达式。", opToken[2]));
return null;
}
let node2 = this.parseExpEqNode(parent);
if (this.errors.length > 0) {
return null;
}
if (!node2) {
this.errors.push(new SqlError(‘词法错误：解析符号‘ + opToken[1] + "右侧表达式失败。", opToken[2]));
return null;
}
nodeList.push(node2);
opToken = this.peek();
}
if (nodeList.length % 2 == 0) {
this.errors.push(new SqlError(‘词法错误：逻辑与表达式数量错误。‘ + opToken[1] + "右侧表达式失败。", opToken[2]));
return null;
}
//把列表转换为二叉树
let rootNode = null;
for (let i in nodeList) {
let node = nodeList[i];
if (!rootNode) {
rootNode = node;
} else if (node instanceof SqlExpAndNode) {
this.setNodeParent(rootNode, node);
rootNode = node;
} else {
this.setNodeParent(node, rootNode);
}
}
if (parent && rootNode) {
this.setNodeParent(rootNode, parent);
}
return rootNode;
}
看着有点晕？没关系，我画一张图，演示一下表达式 a OR b AND c OR d OR e 是如何转换为二叉树的。
测试代码：
Assert.runCase(‘parse exp‘, function () {
let parser = new SqlParser("a OR b AND c OR d OR e");
let node = parser.parseExpOrNode(null);
console.log(node.toString());
});
输出如下二叉树结构：
|--SqlExpOrNode@1：or
|--SqlExpOrNode@1：or
|--SqlExpOrNode@1：or
|--SqlIdentityNode@1：a
|--SqlExpAndNode@1：and
|--SqlIdentityNode@1：b
|--SqlIdentityNode@1：c
|--SqlIdentityNode@1：d
|--SqlIdentityNode@1：e
构造该二叉树的步骤如下图所示：
构造完抽象语法树后，不用生成机器码，直接在语法树上计算。
第三章 计算语法树
前面提到过，语法树节点基类SqlNode里有一个compute方法，用于计算节点的值，子类会重写该方法，实现具体的计算逻辑。
语法节点太多了，咱们只讲几个关键节点的计算逻辑：
SqlNumberNode类，根据value字段的值是否有小数点，相应返回parseInt(this.value)或parseFloat(this,value)。
public compute(ctx: SqlContext): any {
return this.value.indexOf(‘.‘) >= 0 ? parseFloat(this.value) : parseInt(this.value);
}
SqlStringNode类，根据value字段的值返回字符串，去掉首尾的单引号，如果有转义符，要进行转义。
public compute(ctx: SqlContext): any {
if (!this.value) {
return ‘‘;
}
//处理字符串转义
let s = ‘‘;
for (let i = 1; i < this.value.length - 1; i++) {
let c = this.value[i];
if (c == ‘\\‘) {//escape
c = this.value[++i];
if (c == ‘r‘) {
c = ‘\r‘;
} else if (c == ‘n‘) {
c = ‘\n‘;
} else if (c == ‘t‘) {
c = ‘\t‘;
}
s += c;
} else {
s += c;
}
}
return s;
}
SqlExpRelNode类，计算左右两个子节点的值，比较其大小，返回True或False。
public compute(ctx: SqlContext): any {
let left = this.nodes[0].compute(ctx);
if (left instanceof SqlError) {
return left;
}
let right = this.nodes[1].compute(ctx);
if (right instanceof SqlError) {
return right;
}
if (this.value == ‘>‘) {
return left > right;
} else if (this.value == ‘>=‘) {
return left >= right;
} else if (this.value == ‘<‘) {
return left < right;
} else if (this.value == ‘<=‘) {
return left <= right;
}
return false;
}
SqlExpAddNode类，计算左右两个子节点的值，根据value字段的值是 ‘+‘ 还是 ‘-‘，相应执行相加或相减。
public compute(ctx: SqlContext): any {
let left = this.nodes[0].compute(ctx);
if (left instanceof SqlError) {
return left;
}
let right = this.nodes[1].compute(ctx);
if (right instanceof SqlError) {
return right;
}
if (typeof left == ‘number‘ && typeof right == ‘number‘) {
if (this.value == ‘+‘) {
return left + right;
} else if (this.value == ‘-‘) {
return left - right;
}
}
return null;
}
SqlExpMulNode类，计算左右两个子节点的值，根据value字段的值是 ‘*‘ 、‘/‘ 还是 ‘%‘，相应执行相乘、相除、取余。
SqlExpAndNode类，计算左右两个子节点的值，如果都为True，才返回True，否则返回False。
SqlExpOrNode类，计算左右两个子节点的值，如果都为False，才返回False，否则返回True。
SqlExpUnaryNode类，一元操作符，只有一个节点，计算其值。根据操作符的值是‘+‘、‘-‘、‘not‘，执行相应的取正、取负、取反逻辑。
SqlExpFuncNode类，执行函数。首先从SqlContext.standardFunctions字段取一下，如果取到了，说明是标准函数，直接执行，否则再看是不是聚合函数。聚合函数的执行比较复杂，咱们单独讲。
SqlInsertNode类，执行插入逻辑，返回受影响行数。
SqlUpdateNode类，执行更新逻辑，返回受影响行数。
SqlDeleteNode类，执行删除逻辑，返回受影响行数。
SqlSelectNode类，执行查询逻辑，返回一个二维表SqlDataTable实例。这个最复杂，咱们接下来重点讲。
其它语法节点的执行逻辑，请参见源代码。
接下来，重点讲一下SqlSelectNode类和SqlExpFuncNode类的实现逻辑，也就是SELECT语句到底是怎么实现数据查询的，这货老复杂了，烧了不少脑细胞，大伙一定要给个赞。
第四章 SELECT语句
一条SELECT语句的执行，可以分为如下几个步骤：
1、根据 from 节点，以及可能存在的 join 节点，合并出一张宽表（fullTable）。这里我没有做任何优化，直接生成一个笛卡尔积，所以，测试的数据量千万不要太大，否则，运行的速度够你酸爽的~~~
//主表
let fromTableName = this.getFromTableNode().nodes[0].value;
let fromTableAlias = this.getFromTableNode().value;
if (fromTableAlias) {
ctx.tableAliasMap[fromTableAlias] = fromTableName;
ctx.tableAliasMap[fromTableName] = fromTableAlias;
}
let fromTable: SqlDataTable = ctx.database.tables[fromTableName];
if (!fromTable) {
return new SqlError(‘不存在指定的主表：‘ + fromTableName, this.getFromTableNode().line);
}
let tableList = new Array<SqlDataTable>();
tableList.push(fromTable);
//构造宽表的结构
let fullTable = new SqlDataTable(‘__full__‘);
for (let j = 0; j < fromTable.columnNames.length; j++) {
let col = fromTable.getColumnByIndex(j);
fullTable.addColumn((fromTableAlias ? fromTableAlias : fromTableName) + ‘.‘ + col.name, col.type);
}
let joinNodes = this.getJoinNodes();
for (let k = 0; k < joinNodes.length; k++) {
let joinNode = joinNodes[k];
let joinTableNode = joinNode.nodes[0];
let joinTableName = joinTableNode.nodes[0].value;
let joinTableAlias = joinTableNode.value;
if (joinTableAlias && joinTableAlias == fromTableName) {
return new SqlError(‘联结表别名与主表名冲突。‘, joinTableNode.line);
}
if (joinTableAlias && joinTableAlias == fromTableAlias) {
return new SqlError(‘联结表别名与主表别名冲突。‘, joinTableNode.line);
}
if (!joinTableAlias && joinTableName == fromTableName) {
return new SqlError(‘联结表名与主表名冲突，必须指定别名。‘, joinTableNode.line);
}
if (!joinTableAlias && joinTableName == fromTableAlias) {
return new SqlError(‘联结表名与主表别名冲突，必须指定别名。‘, joinTableNode.line);
}
if (joinTableAlias) {
ctx.tableAliasMap[joinTableAlias] = joinTableName;
ctx.tableAliasMap[joinTableName] = joinTableAlias;
}
let joinTable: SqlDataTable = ctx.database.tables[joinTableName];
if (!joinTable) {
return new SqlError(‘不存在指定的联结表：‘ + joinTableName, joinTableNode.line);
}
for (let j = 0; j < joinTable.columnNames.length; j++) {
let col = joinTable.getColumnByIndex(j);
fullTable.addColumn((joinTableAlias ? joinTableAlias : joinTableName) + ‘.‘ + col.name, col.type);
}
tableList.push(joinTable);
}
//构造宽表的数据
let fullTableRowCount = tableList[0].rows.length;
for (let i = 1; i < tableList.length; i++) {
fullTableRowCount *= tableList[i].rows.length;
}
for (let i = 0; i < fullTableRowCount; i++) {
fullTable.addDataRow(fullTable.newRow());
}
if (fullTableRowCount > 0) {
let joinTableRowCount = fullTableRowCount;
let colStart = 0;
for (let i = 0; i < tableList.length; i++) {
let table = tableList[i];
joinTableRowCount /= table.rows.length;
let rowIndex = 0;
while (rowIndex < fullTableRowCount) {
for (let j = 0; j < table.rows.length; j++) {
for (let k = 0; k < joinTableRowCount; k++) {
for (let m = 0; m < table.columnNames.length; m++) {
fullTable.setValueByIndex(rowIndex, colStart + m, table.rows[j].values[m]);
}
if (i == 0) {//from table
fullTable.rows[rowIndex].id = table.rows[j].id;
}
rowIndex++;
}
}
}
colStart += table.columnNames.length;
}
}
ctx.dataTable = fullTable;
2、如果有 join节点，执行联结规则。JSDB只支持 join 和 left join 这两种最常用的联结方式，其它联结方式暂不支持。执行on条件节点，如果返回False，表示没有join上，这时再判断是join还是left join，如果是join，就直接删除；如果是left join，就填上null值。
不太好理解的是repeatJoinRows这个字段，这是为了处理重复join的问题。比如，from表有一条记录，外键ID对应一个 join表中的两条记录，也就是说，join表存在id重复的情况。针对这种情况，需要把重复join的数据也保留下来。
//join筛选
if (joinNodes.length > 0) {
let filteredRowIndexSet = [];
for (let i = fullTable.rows.length - 1; i >= 0; i--) {
ctx.rowIndex = i;
let joinFaildCount = 0;
for (let k = 0; k < joinNodes.length; k++) {
let joinNode = joinNodes[k];
let joinTableNode = joinNode.nodes[0];
let joinOnNode = joinNode.nodes[1];
let v = joinOnNode.compute(ctx);
if (v instanceof SqlError) {
return v;
}
if (v != true) {
if (joinNode.value == ‘join‘) {
joinFaildCount = joinNodes.length + 1;//must be deleted
} else {//left join
joinFaildCount++;
}
//没join上的字段设置为null值
for (let j = 0; j < fullTable.columnNames.length; j++) {
let colTableName = fullTable.columnNames[j].split(‘.‘)[0];
if (colTableName == joinTableNode.value || colTableName == joinTableNode.nodes[0].value) {
fullTable.setValueByIndex(i, j, null);
}
}
}
}
let rid = fullTable.rows[i].id;
if (typeof filteredRowIndexSet[rid] == ‘undefined‘) {
filteredRowIndexSet[rid] = {rowIndex: i, failures: joinFaildCount, repeatJoinRows: []};
} else if (joinFaildCount < filteredRowIndexSet[rid].failures) {
filteredRowIndexSet[rid].rowIndex = i;
filteredRowIndexSet[rid].failures = joinFaildCount;
} else if (joinFaildCount == 0) {
if (filteredRowIndexSet[rid].failures == 0) {
filteredRowIndexSet[rid].repeatJoinRows.push(fullTable.rows[i]);
} else {
filteredRowIndexSet[rid].rowIndex = i;
filteredRowIndexSet[rid].failures = joinFaildCount;
}
}
}
//删除未join上的行
for (let i = fullTable.rows.length - 1; i >= 0; i--) {
let r = filteredRowIndexSet[fullTable.rows[i].id];
if (r.failures > joinNodes.length) {
fullTable.deleteRow(i);
continue;
}
if (r.rowIndex == i) {
continue;
}
let needDelete = true;
for (let k = 0; k < r.repeatJoinRows.length; k++) {
if (r.repeatJoinRows[k] == fullTable.rows[i]) {
needDelete = false;
break;
}
}
if (needDelete) {
fullTable.deleteRow(i);
}
}
}
3、如果有 where 节点，执行筛选规则。就是执行SqlWhereNode节点，不符合条件的记录，直接删除。
//where筛选
let whereExpNode = this.getWhereExpNode();
if (whereExpNode) {
for (let i = fullTable.rows.length - 1; i >= 0; i--) {
ctx.rowIndex = i;
if (whereExpNode) {
let v = whereExpNode.compute(ctx);
if (v instanceof SqlError) {
return v;
}
if (v != true) {
fullTable.deleteRow(i);
}
}
}
}
4、如果有 group by 节点，则执行分组规则。这个最复杂，分为以下几个步骤：
4.1 首先要提取出 fields、having、orderby 这三个节点中的聚合表达式。
4.2 根据 group by的节点，以及上一步得到的聚合表达式列表，构造一张分组计算中间表，写入上下文中，后面聚合函数计算时会用到。
4.3 遍历宽表fullTable，计算分组中间表的值，得到分组中间表groupByMidTable。这段代码不好理解，实际逻辑是在SqlExpFuncNode类中。为了遍历一次就能算出所有聚合表达式的值，我封装了一个SqlGroupByValue类，该类用于记录一个聚合表达式的当前最新的count行数、sum汇总、distinctValues去重值列表，以及当前最新值，这个当前最新值可以是行数、汇总，也可以是最大值、最小值、平均值，取决于具体的聚合函数。所以，一定要注意，普通SqlDataTable的单元值是string或number，但是分组中间表的单元值是SqlGroupByValue。
4.4 基于分组中间表groupByMidTable，根据fields节点进行计算，得到结果表resultTable。为什么要再算一遍？因为，对于 count(*) * 10 这样的表达式，在4.3小节中实际只计算了count(*)，乘以10的步骤是在这里计算的。另外，并不是所有聚合表达式都是要返回的，有些聚合表达式是在having或order节点中出现的，并不在fields节点中，所以，必须在这一步中集中处理一下。
//分组
let groupByNode = this.getGroupByNode();
let havingNode = this.getHavingNode();
let orderByNode = this.getOrderByNode();
//找出用到的所有聚合表达式
let funcNodeList: SqlExpFuncNode[] = [];
for (let j = 0; j < fieldNodes.length; j++) {
this.loadAggregateFunctions(fieldNodes[j], funcNodeList);
}
if (havingNode) {
this.loadAggregateFunctions(havingNode, funcNodeList);
}
if (orderByNode) {
this.loadAggregateFunctions(orderByNode, funcNodeList);
}
let funcNodeCount = 0;
for (let m in funcNodeList) {
funcNodeCount++;
}
if (groupByNode || funcNodeCount > 0) {
//构造分组中间表
let t = new SqlDataTable(‘__group__‘);
if (groupByNode) {
for (let k = 0; k < groupByNode.nodes.length; k++) {
let gNode = groupByNode.nodes[k];
let col = t.addColumn(gNode.toSql(), gNode.typeDeriva(ctx));
if (col) {
col.node = gNode;
}
}
}
for (let i in funcNodeList) {
let fNode = funcNodeList[i];
let col = t.addColumn(fNode.toSql(), fNode.typeDeriva(ctx));
if (col) {
col.node = fNode;
}
}
ctx.groupByMidTable = t;
//计算分组中间表的数据
for (let i = 0; i < fullTable.rows.length; i++) {
ctx.rowIndex = i;
for (let j = 0; j < t.columnNames.length; j++) {
let col = t.getColumnByIndex(j);
let expNode = col.node;
let v = expNode.compute(ctx);
if (v instanceof SqlError) {
return v;
}
}
}
ctx.isGroupByMidTableFinished = true;
ctx.dataTable = ctx.groupByMidTable;
//计算结果表的数据
for (let i = 0; i < ctx.dataTable.rows.length; i++) {
ctx.rowIndex = i;
if (havingNode) {
let hv = havingNode.compute(ctx);
if (hv instanceof SqlError) {
return hv;
}
if (hv != true) {
continue;
}
}
let rowValues = [];
for (let j = 0; j < fieldExpNodes.length; j++) {
let fNode = fieldExpNodes[j];
let fCol = ctx.dataTable.getColumnByName(fNode.toSql());
if (fCol) {
let fVal = ctx.dataTable.rows[i].values[fCol.index];
if (fVal instanceof SqlGroupByValue) {
fVal = fVal.value;
}
rowValues.push(fVal);
} else {
let v = fNode.compute(ctx);
if (v instanceof SqlError) {
return v;
}
rowValues.push(v);
}
}
resultTable.addRow(rowValues);
}
}
涉及的函数表达式，尤其是聚合函数表达式，计算代码如下：
public compute(ctx: SqlContext): any {
let fnName = this.value;
let isDistinct = this.nodes.length > 1 && this.nodes[0] instanceof SqlModifiersNode && this.nodes[0].nodes[0].value == ‘distinct‘;
let paramNodes = isDistinct ? this.nodes[1].nodes : (this.nodes.length > 0 ? this.nodes[0].nodes : []);
//
// 执行非聚合函数
//
if (!this.isAggregate()) {
let fn = ctx.standardFunctions[‘_‘ + fnName];
if (!fn) {
return new SqlError(‘不存在指定的函数：‘ + fnName, this.line);
}
//计算实参的值
let fnArgs = [];
for (let i = 0; i < paramNodes.length; i++) {
let v = paramNodes[i].compute(ctx);
if (v instanceof SqlError) {
return v;
}
fnArgs.push(v);
}
return fn(fnArgs);
}
//
// 执行聚合函数
//
//检查分组中间表
let t: SqlDataTable = ctx.groupByMidTable;
if (!t) {
return new SqlError(‘分组中间表未初始化。‘, this.line);
}
let k = this.toSql();
let col = t.getColumnByName(k);
if (!col) {
return new SqlError(‘分组中间表中不存在指定的聚合列：‘ + k, this.line);
}
//检查分组中间表是否已完成，如果已完成，则可以直接取值
if (ctx.isGroupByMidTableFinished) {
let gv: SqlGroupByValue = t.getValueByIndex(ctx.rowIndex, col.index);
return gv ? gv.value : null;
}
//分组中间表还没有完成，需要继续计算
let fnArgs = [];
for (let i = 0; i < paramNodes.length; i++) {
let pNode = paramNodes[i];
let v = null;
if (pNode instanceof SqlStarNode) {
v = 1;// TODO: 这里应该改为判断该行所有列是否都不为null
} else {
v = pNode.compute(ctx);
}
if (v instanceof SqlError) {
return v;
}
fnArgs.push(v);
}
if (fnArgs.length != 1) {
return new SqlError(‘函数‘ + fnName + ‘的参数个数错误。‘, this.line);
}
let v = fnArgs[0];
if (v == null) {
return null;
}
//分组的中间数据行
let groupByNode = ctx.selectNode.getGroupByNode();
let groupByExpNodes = groupByNode ? groupByNode.nodes : [];
let groupByValues = [];
for (let i = 0; i < groupByExpNodes.length; i++) {
let bv = groupByExpNodes[i].compute(ctx);
if (bv instanceof SqlError) {
return bv;
}
groupByValues.push(bv);
}
let r = t.addDataRow(new SqlDataRow(groupByValues, false));
//分组计算
let gv: SqlGroupByValue = r.values[col.index];
if (!gv) {
gv = new SqlGroupByValue();
r.values[col.index] = gv;
}
if (fnName == ‘count‘) {
if (isDistinct) {
v = v + ‘‘;
if (!gv.distinctValues[v]) {
gv.distinctValues[v] = 1;
gv.value = gv.value == null ? 1 : gv.value + 1;
}
} else {
gv.value = gv.value == null ? 1 : gv.value + 1;
}
} else if (fnName == ‘sum‘) {
gv.value = gv.value == null ? v : v + gv.value;
} else if (fnName == ‘max‘) {
if (gv.value == null || v > gv.value) {
gv.value = v;
}
} else if (fnName == ‘min‘) {
if (gv.value == null || v < gv.value) {
gv.value = v;
}
} else if (fnName == ‘avg‘) {
gv.sum += v;
gv.count++;
gv.value = gv.sum / gv.count;
}
return null;
}
5、如果没有 group by 节点，直接在where筛选后的fullTable上根据fields节点进行计算，得到结果表resultTable。这个就简单很多了。
//计算结果表的数据
for (let i = 0; i < ctx.dataTable.rows.length; i++) {
ctx.rowIndex = i;
let rowValues = [];
for (let j = 0; j < fieldExpNodes.length; j++) {
let v = fieldExpNodes[j].compute(ctx);
if (v instanceof SqlError) {
return v;
}
rowValues.push(v);
}
resultTable.addRow(rowValues);
}
6、如果有 order by 节点，则对结果表resultTable进行排序。由于排序规则可能包含多个条件，这里要分为三个步骤来计算：
6.1 遍历resultTable表，每一行数据都得到一个orderByValues数组，包含了排序要用的值。如果是多个排序条件，数组就包含多个值。
6.2 计算每个排序条件的方向，默认是asc。
6.3 根据排序表达式的值，以及排序方向，对数据行进行排序。这里调用的是Array类的sort方法，传入一个function，实现自定义排序。
//排序
if (orderByNode && orderByNode.nodes.length > 0) {
//计算每一行的排序值
let rows = resultTable.rows;
for (let i = 0; i < rows.length; i++) {
ctx.rowIndex = i;
let row = rows[i];
for (let m = 0; m < orderByNode.nodes.length; m++) {
let oVal = orderByNode.nodes[m].nodes[0].compute(ctx);
if (oVal instanceof SqlError) {
return oVal;
}
row.orderByValues.push(oVal);
}
}
//计算每个排序项的方向
let directions: boolean[] = [];
for (let k = 0; k < orderByNode.nodes.length; k++) {
directions.push(orderByNode.nodes[k].value == ‘desc‘);
}
//对数据行进行排序
rows.sort(function (a: SqlDataRow, b: SqlDataRow) {
let m = 0;
while (m < directions.length) {
if (a.orderByValues[m] == b.orderByValues[m]) {
m++;
} else {
if (directions[m]) {//desc
return a.orderByValues[m] < b.orderByValues[m] ? 1 : -1;
} else {
return a.orderByValues[m] > b.orderByValues[m] ? 1 : -1;
}
}
}
return 0;
});
}
7、如果有 limit 节点，则返回指定范围的数据，也就是分页时要用的东西。如果是limit n，则返回前面n行数据；如果是limit m, n，则从第m行开始，返回n行数据的。
let limitNode = this.getLimitNode();
if (limitNode) {
let limitNums = [];
for (let i = 0; i < limitNode.nodes.length; i++) {
let v = limitNode.nodes[i].compute(ctx);
if (v instanceof SqlError) {
return v;
}
if (typeof v != ‘number‘) {
return new SqlError(‘无效的limit值：‘ + v, limitNode.line);
}
limitNums.push(v);
}
if (limitNums.length == 1) {
let end = limitNums[0];
if (resultTable.rows.length > end) {
resultTable.rows.splice(end, resultTable.rows.length - end);
}
} else if (limitNums.length == 2) {
let begin = limitNums[0];
let end = limitNums[0] + limitNums[1] - 1;
resultTable.rows.splice(end + 1, resultTable.rows.length - end - 1);
resultTable.rows.splice(0, begin);
}
}
到这里就得到最终的结果表了。
相对于SELECT语句，其它语句就简单多了。
第五章 其它语句
DELETE语句的执行分为两步：执行where筛选，然后根据row.id进行删除。
public compute(ctx: SqlContext): any {
let tableName = this.nodes[0].nodes[0].value;
let table: SqlDataTable = ctx.database.tables[tableName];
if (!table) {
return new SqlError(‘不存在指定的表：‘ + tableName, this.line);
}
ctx.dataTable = table;
let deletedCount = 0;
if (this.nodes.length >= 2) {
for (let i = table.rows.length - 1; i >= 0; i--) {
ctx.rowIndex = i;
ctx.holdIndex = -1;
let v = this.nodes[1].compute(ctx);
if (v instanceof SqlError) {
return v;
}
if (v) {
table.deleteRow(i);
deletedCount++;
}
}
} else {
deletedCount = table.rows.length;
table.rows = [];
}
return deletedCount;
}
UPDATE语句也分为两步：执行where筛选，然后set规则更新指定列的数据。
public compute(ctx: SqlContext): any {
let tableName = this.nodes[0].nodes[0].value;
let table: SqlDataTable = ctx.database.tables[tableName];
if (!table) {
return new SqlError(‘不存在指定的表：‘ + tableName, this.line);
}
ctx.dataTable = table;
let updateCols = [];
let updateValueNodes = [];
for (let j in this.nodes[1].nodes) {
let setNode = this.nodes[1].nodes[j];
let colName = setNode.nodes[0].value;
let col = table.getColumnByName(colName);
if (!col) {
return new SqlError(‘不存在指定的列：‘ + colName, setNode.nodes[0].line);
}
updateCols.push(col);
updateValueNodes.push(setNode.nodes[1]);
}
let updateRowIndexList = [];
if (this.nodes.length == 2) {
for (let i = 0; i < table.rows.length; i++) {
updateRowIndexList.push(i);
}
} else if (this.nodes.length == 3) {
for (let i = 0; i < table.rows.length; i++) {
ctx.rowIndex = i;
ctx.holdIndex = -1;
let whereValue = this.nodes[2].compute(ctx);
if (whereValue instanceof SqlError) {
return whereValue;
}
if (whereValue) {
updateRowIndexList.push(i);
}
}
}
for (let i in updateRowIndexList) {
ctx.rowIndex = updateRowIndexList[i];
ctx.holdIndex = -1;
for (let j in updateCols) {
let col = updateCols[j];
let v = updateValueNodes[j].compute(ctx);
if (v instanceof SqlError) {
return v;
}
table.setValueByIndex(ctx.rowIndex, col.index, v);
}
}
return updateRowIndexList.length;
}
INSERT语句也分为两步：根据表构造创建一个空行，然后更新指定列的数据。
public compute(ctx: SqlContext): any {
let tableName = this.nodes[0].value;
let table = ctx.database.tables[tableName];
if (!table) {
return new SqlError(‘不存在指定的表：‘ + tableName, this.line);
}
let fieldsNodes = this.nodes[1].nodes;
let valuesNodes = this.nodes[2].nodes;
let row = table.newRow();
ctx.holdIndex = -1;
for (let j = 0; j < fieldsNodes.length; j++) {
let colName = fieldsNodes[j].value;
let colIndex = table.getColumnByName(colName).index;
let valueNode = valuesNodes[j];
let v = valueNode.compute(ctx);
if (v instanceof SqlError) {
return v;
}
row.values[colIndex] = v;
}
table.addDataRow(row);
return 1;
}
CREATE TABLE语句，在 SqlDatabase 中创建一个新的 SqlDataTable 实例。
public compute(ctx: SqlContext): any {
let table = new SqlDataTable(this.nodes[0].value);
let paramsNode = this.nodes[1];
let columnNames = [];
for (let i = 0; i < paramsNode.nodes.length; i++) {
let fieldDeclareNode = paramsNode.nodes[i];
let colName = fieldDeclareNode.value;
let colType = fieldDeclareNode.nodes[0].value;
if (columnNames.indexOf(colName) >= 0) {
return new SqlError(‘列名重复：‘ + colName, fieldDeclareNode.line);
}
table.addColumn(colName, colType);
columnNames.push(fieldDeclareNode);
}
return ctx.database.addTable(table);
}
至此，几个主要的语句都介绍了。
最后，我们写几个测试范例，展示一下运行结果，这几个测试范例，在文章开头的“体验页面”上都有展示。
第六章 程序展示
通过JS创建三张表：t_gender（性别字典表）、t_dept（部门字典表）、t_staff（员工表）。
var database = new SqlDatabase();
database.execute("create table t_gender(id number, name varchar(100))");
database.execute("create table t_dept(dept_id number, dept_name varchar)");
database.execute("create table t_staff(id varchar, name varchar, gender number, dept_id number)");
database.execute("insert into t_gender(id, name)values(1, ‘Male‘)");
database.execute("insert into t_gender(id, name)values(2, ‘Female‘)");
database.execute("insert into t_dept(dept_id, dept_name)values(101, ‘Tech‘)");
database.execute("insert into t_dept(dept_id, dept_name)values(102, ‘Finance‘)");
database.execute("insert into t_staff(id, name, gender, dept_id)values(‘016001‘, ‘Jack‘, 1, 102)");
database.execute("insert into t_staff(id, name, gender, dept_id)values(‘016002‘, ‘Bruce‘, 1, null)");
database.execute("insert into t_staff(id, name, gender, dept_id)values(‘016003‘, ‘Alan‘, null, 101)");
database.execute("insert into t_staff(id, name, gender, dept_id)values(‘016004‘, ‘Hellen‘, 2, 103)");
database.execute("insert into t_staff(id, name, gender, dept_id)values(‘016005‘, ‘Linda‘, 2, 101)");
database.execute("insert into t_staff(id, name, gender, dept_id)values(‘016006‘, ‘Royal‘, 3, 104)");
然后准备几条范例sql，方便大家执行查询，也可以自己写一个新的sql。
SELECT
s.id,
s.name,
ifnull(s.gender, ‘--‘) AS gender_id, /*处理空值*/
(CASE g.name WHEN ‘Male‘ THEN ‘男‘ WHEN ‘Female‘ THEN ‘女‘ ELSE ‘未知‘ END) AS gender_name,
s.dept_id,
d.dept_name
FROM t_staff s
LEFT JOIN t_gender g ON g.id=s.gender
LEFT JOIN t_dept d ON d.dept_id=s.dept_id
WHERE d.dept_name IS NOT NULL
LIMIT 3
执行结果：
文章到这里就结束了，欢迎大家指正，多给Star，多给赞 ^_^