代码分析平台CodeQL学习手记（七）
导语：在本文中，我们将以寻找合法王位继承人为例深入讲解递归的概念与应用。
在前面的文章中，我们通过一个抓纵火犯的例子来复习了谓词的相关知识，并进一步学习类的定义和用法，以及如何覆盖父类的成员谓词。在本文中，我们将以寻找合法王位继承人为例深入讲解递归的概念与应用。
简介
就在我们连续破获了发生在村庄中的两起案件后，村庄又恢复了往日的平静。然而，就在我们离开村子前的最后一个夜晚，城堡中年老的国王——伟大的Basil国王——在睡梦中与世长辞，村庄再次陷入混乱之中！
为什么会再次陷入混乱呢？因为老国王既没结过婚，也没有自己的孩子，所以，没有人知道应该由谁来继承国王的城堡和财产。这时，许多村民都声称自己是国王家族的后裔，是合法的继承人。为此，人们争论不休，鸡犬不宁。
最终，受村民之托，我们决定留在村子里平息这场争论——找到真正的王位继承人。
寻找国王的兄弟姐妹
既然许多村民都声称自己是王室家族的后裔，我们就需要弄清楚他们跟国王到底有没有亲缘关系。当然，这是一项非常艰巨的任务，不过，好在我们手头上已经掌握了村民们许多的数据，同时，我们还获得了一份名单，上面记录了村里所有的父母及其子女之间的关系。
为了深入了解国王及其家世，我们开始进入城堡查找相应的线索，最终找到了一些古老的家谱。掌握这条重要的线索后，我们立刻查询现有的数据库中，看看国王家族中是否还有人健在。
为此，我们可以借助于一个谓词：parentOf(Person p)。它的作用是，输入一个表示村民的变量p，该谓词就会返回该村民的父母。例如，通过它，我们可以将所有村民p与其父母一起列出：
from Person p select parentOf(p) + " is a parent of " + p
运行结果如下所示：
如您所见，这里返回的信息太多了，如果通过人工方式进行搜索的话，那就太费时费力了。所以，我们打算编写了一个QL查询来查找国王的继承人。
尽管国王膝下并没有子女，但是，也许他还有兄弟姐妹健在。为此，我们可以编写一个查询，来查找国王的兄弟姐妹。很明显，这里要查找的人，就是除了国王本人之外，跟国王同父同母的村民，具体代码如下所示：
from Person p
where parentOf(p) = parentOf("King Basil") and
not p = "King Basil"
select p上面的代码的运行结果如下所示：
如您所见，确实是有兄弟姐妹的！不过，既然国王年事已高，他的同胞们肯定也不小了，所以，我们需要考察他们是否还健在。为了完成这项任务，我们可以编写一个词，即isDeceased()，让它来判断某人是否已经离世。
下面，我们就借助谓词isDeceased()来考察国王的兄弟姐妹是否还健在，具体的代码如下所示：
from Person p
where parentOf(p) = parentOf("King Basil") and
not p = "King Basil"
and not p.isDeceased()
select p
下面是上述代码的运行结果：
不幸的是，Basil国王的兄弟姐妹都已经不在人世了——上面没有返回任何结果。既然老国王同辈的亲属已经不在了，我们就需要进一步调查还有没有晚辈的亲属。为此，我们可以定义一个谓词childOf()，用来返回某人的子女。我们知道，当且仅当村民p是某人的父母时，某人才是村民p的子女。所以，在定义谓词childOf()时，我们可以借助于前面介绍过的谓词parentOf()，具体如下所示：
Person childOf(Person p) {
p = parentOf(result)
}对于上面的定义，我们可以这样理解：遍历所有村民，把符合p = parentOf(result)条件的村民作为返回值。当然，我们也可用result =
好了，下面我们利用谓词childOf()来编写一个查询，看看国王的兄弟姐妹是否有后代：
from Person p
where parentOf(p) = parentOf("King Basil") and
not p = "King Basil"
select childOf(p)上面的代码的运行结果如下所示：
如您所见，这里的查询没有返回任何结果，这表明国王的兄弟姐妹们并没有后代。既然国王的近亲没有后代，那么接下来，我们要做的事情就是调查老国王远亲是否还健在，或者是否有后代。
寻找国王的远亲
到目前为止，事情好像变得越来越复杂了。为了找到国王的所有亲戚，我们想要定义一个谓词relativeOf(Person p)，以便帮忙找出某人的所有亲属。
不过，在编写这个谓词之前，需要对亲属关系下一个精确地定义：如果两个人有共同的祖先，他们就是亲属关系。
为此，我们又引入一个共同祖先的关系。这时，我们可以定义一个谓词ancestorOf(Person p)，用来找出某人p的所有祖先。当然，某人p的祖先可以是p的父辈，或者p的父辈的父辈，或者p的父辈的父辈的父辈，依此类推。不过，如果这样做的话，我们就会得到一个无穷无尽的父辈名单。很明显，我们必须寻找一个更可行的方法。
思考良久，我们终于想到，如果把问题重新表述一下，就能帮我们找到答案。也就是说，这里所说的祖先，要么是某人的父母，要么是已知为某人祖先的人的父母。好了，下面我们将上面的话翻译成QL语言，具体如下所示：
Person ancestorOf(Person p) {
result = parentOf(p) or
result = parentOf(ancestorOf(p))
}正如您所看到的，我们在谓词ancestorOf()的定义中调用了它自己。这实际上是一个递归的例子。对于这种递归来说，其中的同一个操作（在本例中为谓词ancestorOf()）被应用了多次，这在QL语言中是非常常见的，被称为操作的传递闭包。在处理传递闭包时，有两个特殊的符号极其有用，即+和*，具体如下所示：
· parentOf+(p) ，这表示对变量p应用一次或多次谓词parentOf()，它等价于ancestorOf(p)。
· parentOf*(p) ，这表示对变量p应用零次或多次谓词parentOf()，因此，它要么返回变量p的祖先，要么返回变量p本身。
接下来，让我们来定义谓词relativeOf(Person p)，帮忙找出某人的所有亲属。具体代码如下所示：
Person relativeOf(Person p) {
parentOf*(result) = parentOf*(p)
}当然，如果想要列出国王的所有在世亲属，我们还可以借助于谓词isDeceased()，完整的代码如下所示：
import tutorial
Person relativeOf(Person p) {
parentOf*(result) = parentOf*(p)
}
from Person p
where not p.isDeceased() and
p = relativeOf("King Basil")
select p好了，我们看看上面代码的运行结果：
合法的王位继承人
经过一番努力，我们终于找到了国王的两个在世的亲戚。可是，到底该由谁来继承王位呢？为了做出抉择，村民们又拿出了“村庄宪法”：
“王位继承人必须是国王的在世亲属。任何有案底的人都不予以考虑。如果存在多个候选人选，那么，选择年龄最大的人作为王位继承人。”
现在，我们需要考察这两位候选者是否有过犯罪记录，为此，我们可以编写一个谓词criminalRecord(p)，检查村民p是否有案底。根据前面的文章可知，村里至少有三个人是有案底的，他们分别是Hester、Hugh和Charlie。假设其他村民都是遵纪守法的，那么，谓词criminalRecord(p)的定义则为：
predicate criminalRecord(Person p) {
p = "Hester" or
p = "Hugh" or
p = "Charlie"
}至此，我们就可以查询真正的王位继承人了，完整的代码如下所示：
import tutorial
Person relativeOf(Person p) {
parentOf*(result) = parentOf*(p)
}
predicate criminalRecord(Person p) {
p = "Hester" or
p = "Hugh" or
p = "Charlie"
}
from Person p
where not p.isDeceased() and
p = relativeOf("King Basil") and
not criminalRecord(p)
select p
import tutorial
Person relativeOf(Person p) {
parentOf*(result) = parentOf*(p)
}
predicate criminalRecord(Person p) {
p = "Hester" or
p = "Hugh" or
p = "Charlie"
}
from Person p
where not p.isDeceased() and
p = relativeOf("King Basil") and
not criminalRecord(p)
select p运行结果如下所示：
太棒了！王位继承人终于找到了，村庄又可以恢复往日的安宁了。我们不难发现，递归在寻找王位继承人的过程中发挥了非常重要的作用，下面，我们就来进一步了解一下这个概念。
深入了解递归
QL语言为递归提供了强大的支持。在QL语言中，如果谓词如果直接或间接地调用了自身，则称其为递归型谓词。
为了求解递归型谓词的返回值的集合，QL编译器需要找到递归的最小不动点。具体来说，QL编译器会从一个空集开始求解，通过重复应用谓词以寻找新的、符合要求的值，直到返回值的集合不再变化为止，此时的集合就是递归的最小不动点，也就是递归的结果。类似地，QL查询的结果是查询中引用的谓词的最小不动点。
下面，我们开始举例说明。
求0到100之间的整数的递归型谓词
下面的查询代码，将通过谓词getANumber()给出从0到100(包括100在内)之间的所有整数：
int getANumber() {
result = 0
or
result <= 100 and result = getANumber() + 1
}
select getANumber()谓词getANumber()的计算结果是这样一个集合，该集合包含0以及比集合中已有的数字大1的所有整数。这个求解过程将重复进行多次，直到得到元素100为止，并且100也是这个集合的元素。下面是上述代码的运算结果的最前面的部分和最后面的部分：
相互递归
实际上，上面的谓词是在自己调用自己；除此之外，谓词之间也可以相互递归调用，也就是说，你调用我，我调用你，形成一个循环。例如，下面的QL查询就是通过两个谓词的互相调用来求0到100之间的所有偶数的：
int getAnEven() {
result = 0
or
result <= 100 and result = getAnOdd() + 1
}
int getAnOdd() {
result = getAnEven() + 1
}
select getAnEven()上述代码的运行结果如下所示：
如果我们可以将上面代码中的select getAnEven()语句替换为select getAnOdd()，将会得到从1到101之间的奇数（包括101），结果如下所示：
传递闭包
谓词的传递闭包就是一种递归型谓词，其结果是通过重复应用原始谓词而得到的。具体而言，原始谓词必须带有两个参数（可包括this或result值），并且这些参数必须具有兼容的类型。
由于传递闭包是递归的一种常见形式，所以QL提供了两个非常有用的运算符号：
传递闭包运算符+
若要将某个谓词应用一次或多次，可以在谓词名称后面加上符号“+”。例如，假设我们定义了一个带有成员谓词getAParent()的类Person，那么p.getAparent()只会返回p的父辈。而传递闭包p.getAparent+()则会返回p的父辈、p的父辈的父辈，等等。
不难看出，使用符号+通常比显式定义递归谓词更加简洁。如果不使用该符号，相应的代码会长不少：
Person getAnAncestor() {
result = this.getAParent()
or
result = this.getAParent().getAnAncestor()
}自反传递闭包运算符*
该运算符的作用类似于上面的传递闭包运算符，不同之处在于，我们可以使用自反传递闭包运算符*将一个谓词应用于自身零次或多次。
例如，p.getAparent*()的返回结果可能是p的祖先（应用多次，如上），或者p本身（应用零次），其显式定义如下所示：
Person getAnAncestor2() {
result = this
or
result = this.getAParent().getAnAncestor2()
}常见错误
虽然QL语言为查询递归数据提供了强大的支持，但在定义递归的时候，却非常容易出错，其后果是，要么无法得到想要的结果，要么出现编译器错误。下面，我们给出一些常见的错误。
空递归
首先，一个有效的递归定义必须提供一个起点，或者终止条件。如果递归谓词的计算结果为空集，通常就是这些地方出错了。
例如，如果我们将getAnAncestor()定义为：
Person getAnAncestor() {
result = this.getAParent().getAnAncestor()
}那么，QL编译器将会报错，指出这是一个空递归。这是因为getAnAncestor()最初被假定为一个空集，导致无法继续添加新值。要想解决这个问题，我们可以给谓词提供一个递归的起点，例如：
Person getAnAncestor() {
result = this.getAParent()
or
result = this.getAParent().getAnAncestor()
}非单调递归
除了上面介绍的常见错误之外，还要注意一点，那就是有效的递归谓词必须是单调的。这意味着，进行(相互)递归调用时，只允许进行偶数次否定。
表面上看，这是为了防止出现“说谎者悖论”的情况，因为在这种情况下，是没有办法通过递归进行求解的。例如:
predicate isParadox() {
not isParadox()
}根据这个定义，谓词isParadox()成立的条件就是其自身不成立。这是不可能的，所以递归没有不动点解。
如果递归出现在偶数次的否定之下，那么这就不是问题。例如，考虑类Person的以下成员谓词：
predicate isExtinct() {
this.isDead() and
not exists(Person descendant | descendant.getAParent+() = this |
not descendant.isExtinct()
)
}即使p和p的所有后代都已去世，p.isExtinct()仍然成立。
由于对isExtinct()的递归调用是嵌套在偶数次的否定之中的，因此，这是一个有效的定义。事实上，您可以将定义的第二部分改写成下面的样子：
forall(Person descendant | descendant.getAParent+() = this | descendant.isExtinct() )
小结
在本文中，我们以寻找合法王位继承人为例深入讲解了递归的概念与应用。在下一篇文章中，我们将为读者演示如何综合利用类、谓词和递归等知识来编写一个QL查询，从而解决经典的过河问题。
备注：本系列文章乃本人在学习CodeQL平台过程中所做的笔记，希望能够对大家有点滴帮助——若果真如此的话，本人将备感荣幸。
参考资料：https://help.semmle.com/
发表评论
提供云计算服务