CodeQL学习笔记(2)-QL语法（递归）

最近在学习CodeQL，对于CodeQL就不介绍了，目前网上一搜一大把。本系列是学习CodeQL的个人学习笔记，根据个人知识库笔记修改整理而来的，分享出来共同学习。个人觉得QL的语法比较反人类，至少与目前主流的这些OOP语言相比，还是有一定难度的。与现在网上的大多数所谓CodeQL教程不同，本系列基于官方文档和情景实例，包含大量的个人理解、思考和延伸，直入主题，只切要害，几乎没有废话，并且坚持用从每一个实例中学习总结归纳，再到实例中验证。希望能给各位一点不一样的见解和思路。当然，也正是如此必定会包含一定的错误，希望各位大佬能在评论区留言指正。

CodeQL学习笔记(1)

递归

我们逐渐来理解递归。先设定一个目标–查询国王是否有活着的兄弟姐妹

// 表示p和“King Basil”的父母是相同的，则p是其兄弟姐妹
from Person p 
where 
    parentOf(p) = parentOf("King Basil") and    // parentOf(Person p)返回p的父母
    not p = "King Basil"
    and not p.isDeceased()    // isDeceased()谓词，判断是否死亡
select p
// 没有结果

然后尝试查找这些兄弟姐妹们是否有孩子

根据paretOf定义一个childOf谓词（反逻辑）

Person childOf(Person p){    // 这里的返回值是一个Person类型
    p = paretOf(result)
}
select childOf(p)
// 依旧没有结果

在QL谓词中，约定result为返回值。

理解代码：这里有两个身份，p和result，要搞清楚它们间的关系。定义的childOf谓词在这里表示–childOf(p) = result，p的孩子是result。那么在谓词实现中，要把这个逻辑反过来，类似于数学中的反函数的概念，p = parentOf(result)，当且仅当 p 是某人的父亲时，某人是 p 的孩子

在谓词中不一定要在谓词定义中直接写明result = ，也可以把result放到后面来作为一个“已知”变量来表达关系。（引用官方文档：相反，您还可以通过用 result 来“反向”表示 p 和 result 之间的关系。）

再尝试找是否有活着的堂兄弟、堂兄弟的孩子、二表兄弟等……这里面会涉及到非常复杂的关系，最好是能够定义一个谓词列出所有的亲戚relativeOf(Person p)：如果两个人拥有同一个祖先，那么他们就是亲戚

如果我们定义一个谓词ancestorOf(Person p)，列出某个人所有的祖先，这其中包含它的parent，parent的parent……无穷尽，这里就存在了一个递归的思想。我们可以把祖先的定义进行拆分，分为直接父母和已经确定是祖先的直接父母

对于祖先定义的拆分的理解，如果某人已经被确定是祖先了，那么它的直接父母肯定也是祖先

Person ancestorOf(Person p){
    result = parentOf(p) or
    result = parentOf(ancestorOf(p))
}

下面看一个递归的具体例子

// 列出0-100
int getANumber(){
    result = 0
    or
    result <= 100 and result = getANumber() + 1
}
select getANumber() as number    // 列名为“number”，列名不用加引号

这里需要与传统函数式编程严格区分开，不是按传统编程语言的“从上到下执行”模式。ql中在处理递归时，会根据查询逻辑查找所有满足条件的可能结果。因此，select getANumber() 其实是在寻找所有可能满足 getANumber() 定义条件的 result 值，而不是只运行一次 getANumber() 函数。

QL 会首先满足 result = 0，这是递归的基础条件。所以getANumber()在没有其他限制的情况下，可以返回 0。

然后CodeQL 会继续尝试满足其他条件，以找到所有可能的 result 值。
• 递归条件result = getANumber() + 1意味着 QL 还会去找比 0 大的所有整数结果，直到达到 result = 100 的上限。
• 例如，在 result = 0 确定之后，递归条件允许 result = 1（通过 result = getANumber() + 1 得到），接着再允许 result = 2，以此类推，直到 100。（可以看成是result <= 100 and result = 1, result <= 100 and result = 2……）

闭包

我们把上面的递归ancestorOf(Person p)改写一下

Person getAncestor(){
  result = this.getAParent()
  or
  result = this.getAParent().getAnAncestor()
}

其实它的本质就是不断的在找parent，parent的parent……，在QL里有个概念叫做闭包，简单理解就是对某个类的谓词重复执行的简化，不需要我们再去写复杂的递归谓词。

传递闭包（+）

直接对getParent这个谓词使用传递闭包p.getAParent+(),这里得到的是p的parent、p的parent的parent……，是不包含p自身的，即递归一次或多次（>=1，和正则表达式中+、*的用法一致）。

1
2
3

from Person p 
where p = "Cornelius"
select p.getAParent+() as name    // 找到Cornelius的所有ancestor，getAnAncestor()等价于getAParent+()

自反传递闭包（*）

与传递闭包唯一的差别是包含p本身，递归0次或多次（>=0）

1	select p.getAParent*() as name

其他详细的递归深入用法等到后期专题再展开。当前学习的目的仅是快速入门。

完善代码

在学习完闭包之后，就可以实现前面我们的需求–找出国王的所有亲戚relativeOf(Person p)

Person relativeOf(Person p){
    parentOf*(p) = parentOf*(result)
    and
    not result = p     // 由于这个具体例子中的国王已经死了，在where中也已经过滤了，所以可以不加。正常来说自反传递闭包需要排除自身
}

from Person p 
where
    not p.isDeceased() and
    p = relativeOf("King Basil")
select p