CodeQL递归语法详解<\/h1>

1. 递归基础概念<\/h2>

1.1 递归的基本形式<\/h3>
在CodeQL中，递归是通过谓词(Predicate)实现的，其基本形式为：<\/p>
Person ancestorOf(Person p) {
    result = parentOf(p) or 
    result = parentOf(ancestorOf(p))
}
<\/code><\/pre>
这个谓词定义了如何查找一个人的祖先：<\/p>

直接父母(parentOf(p)<\/code>)<\/li>
已经确定是祖先的直接父母(parentOf(ancestorOf(p))<\/code>)<\/li>
<\/ol>
1.2 递归的执行逻辑<\/h3>
CodeQL处理递归时与传统编程语言不同：<\/p>

不是"从上到下执行"的模式<\/li>
会根据查询逻辑查找所有满足条件的可能结果<\/li>
会首先满足基础条件，然后递归查找其他可能结果<\/li>
<\/ul>
示例：<\/p>
int getANumber() {
    result = 0 or
    result <= 100 and
    result = getANumber() + 1
}
select getANumber() as number
<\/code><\/pre>
执行过程：<\/p>

首先满足result = 0<\/code>（基础条件）<\/li>
然后尝试满足result = getANumber() + 1<\/code>，即：

result = 1<\/code>（通过result = 0 + 1<\/code>）<\/li>
result = 2<\/code>（通过result = 1 + 1<\/code>）<\/li>
以此类推，直到100<\/li>
<\/ul>
<\/li>
<\/ol>
2. 闭包概念<\/h2>
2.1 传递闭包(+)<\/h3>
传递闭包是对递归的简化表示，表示对某个谓词重复执行一次或多次(≥1)。<\/p>
语法：<\/p>
p.getAParent+()
<\/code><\/pre>
等价于：<\/p>
Person getAncestor() {
    result = this.getAParent() or
    result = this.getAParent().getAnAncestor()
}
<\/code><\/pre>
示例：<\/p>
from Person p
where p = "Cornelius"
select p.getAParent+() as name
<\/code><\/pre>
2.2 自反传递闭包(*)<\/h3>
自反传递闭包与传递闭包类似，但包含自身，表示对某个谓词重复执行零次或多次(≥0)。<\/p>
语法：<\/p>
p.getAParent*()
<\/code><\/pre>
2.3 闭包应用示例<\/h3>
查找亲戚关系：<\/p>
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
<\/code><\/pre>
这个查询：<\/p>

使用parentOf*()<\/code>查找所有祖先（包括自己）<\/li>
通过比较祖先集合找到有共同祖先的人（亲戚）<\/li>
排除自己<\/li>
过滤掉已故的人<\/li>
<\/ol>
3. 递归谓词设计要点<\/h2>

基础条件<\/strong>：必须有一个明确的终止条件（如result = 0<\/code>或result = parentOf(p)<\/code>）<\/li>
递归条件<\/strong>：定义如何从已知结果推导出新的结果<\/li>
结果变量<\/strong>：使用result<\/code>表示返回值，可以在谓词中任何位置使用<\/li>
反向关系<\/strong>：可以通过result<\/code>反向表示关系（如p = parentOf(result)<\/code>表示result<\/code>是p<\/code>的孩子）<\/li>
<\/ol>
4. 实际应用示例<\/h2>
4.1 查找活着的兄弟姐妹<\/h3>
from Person p
where parentOf(p) = parentOf("King Basil") and
      not p = "King Basil" and
      not p.isDeceased()
select p
<\/code><\/pre>
4.2 定义孩子关系<\/h3>
Person childOf(Person p) {
    p = parentOf(result)
}
<\/code><\/pre>
4.3 复杂亲戚关系查询<\/h3>
通过递归可以查询：<\/p>

堂兄弟<\/li>
堂兄弟的孩子<\/li>
二表兄弟等复杂关系<\/li>
<\/ul>
5. 注意事项<\/h2>

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

通过谓词实现，使用result<\/code>表示返回值<\/li>
包含基础条件和递归条件<\/li>
闭包操作符(+<\/code>和*<\/code>)可以简化递归表达<\/li>
特别适合处理树状或图状数据结构（如家谱、调用图等）<\/li>
需要适应其"反向"逻辑思维方式<\/li>
<\/ul>
掌握递归是使用CodeQL进行复杂查询的关键技能，特别是在处理程序分析中的调用链、数据流等问题时尤为重要。<\/p>