CodeQL递归语法详解

1. 递归基础概念

1.1 递归的基本形式

在CodeQL中，递归是通过谓词(Predicate)实现的，其基本形式为：

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

这个谓词定义了如何查找一个人的祖先：

1. 直接父母(parentOf(p))
2. 已经确定是祖先的直接父母(parentOf(ancestorOf(p)))

1.2 递归的执行逻辑

CodeQL处理递归时与传统编程语言不同：

• 不是"从上到下执行"的模式
• 会根据查询逻辑查找所有满足条件的可能结果
• 会首先满足基础条件，然后递归查找其他可能结果

示例：

int getANumber() {
    result = 0 or
    result <= 100 and
    result = getANumber() + 1
}
select getANumber() as number

执行过程：

1. 首先满足result = 0（基础条件）
2. 然后尝试满足result = getANumber() + 1，即：
   • result = 1（通过result = 0 + 1）
   • result = 2（通过result = 1 + 1）
   • 以此类推，直到100

2. 闭包概念

2.1 传递闭包(+)

传递闭包是对递归的简化表示，表示对某个谓词重复执行一次或多次(≥1)。

语法：

p.getAParent+()

等价于：

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

示例：

from Person p
where p = "Cornelius"
select p.getAParent+() as name

2.2 自反传递闭包(*)

自反传递闭包与传递闭包类似，但包含自身，表示对某个谓词重复执行零次或多次(≥0)。

语法：

p.getAParent*()

2.3 闭包应用示例

查找亲戚关系：

Person relativeOf(Person p) {
    parentOf*(p) = parentOf*(result) and
    not result = p
}

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

这个查询：

1. 使用parentOf*()查找所有祖先（包括自己）
2. 通过比较祖先集合找到有共同祖先的人（亲戚）
3. 排除自己
4. 过滤掉已故的人

3. 递归谓词设计要点

1. 基础条件：必须有一个明确的终止条件（如result = 0或result = parentOf(p)）
2. 递归条件：定义如何从已知结果推导出新的结果
3. 结果变量：使用result表示返回值，可以在谓词中任何位置使用
4. 反向关系：可以通过result反向表示关系（如p = parentOf(result)表示result是p的孩子）

4. 实际应用示例

4.1 查找活着的兄弟姐妹

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

4.2 定义孩子关系

Person childOf(Person p) {
    p = parentOf(result)
}

4.3 复杂亲戚关系查询

通过递归可以查询：

• 堂兄弟
• 堂兄弟的孩子
• 二表兄弟等复杂关系

5. 注意事项

1. 递归可能导致性能问题，特别是在大数据集上
2. 确保递归有明确的终止条件，避免无限循环
3. 优先考虑使用闭包操作符(+和*)，它们通常比手动编写递归谓词更高效
4. 理解QL的"反向"逻辑，与传统编程语言不同

6. 总结

CodeQL中的递归：

• 通过谓词实现，使用result表示返回值
• 包含基础条件和递归条件
• 闭包操作符(+和*)可以简化递归表达
• 特别适合处理树状或图状数据结构（如家谱、调用图等）
• 需要适应其"反向"逻辑思维方式

掌握递归是使用CodeQL进行复杂查询的关键技能，特别是在处理程序分析中的调用链、数据流等问题时尤为重要。