Recursive monotonic aggregates

[Ninja3047]

Hi,

I'm trying to follow the depth query specified on this page.
https://codeql.github.com/docs/ql-language-reference/expressions/#:~:text=Recursive%20monotonic%20aggregates

import tutorial

int depth(Person p) {
  if not exists(p.getAParent())
  then result = 0
  else result = 1 + max(Person g | g = p.getAParent() | depth(g))
}

from Person p
select p, depth(p)

When I try to implement a similar "depth" function for the tutorial, I get the "Non-monotonic recursion: ..." error.

Is there something I'm not understanding about the Node depth example? Why is that valid but my nearly identical implementation of that using the Person class in the tutorial not valid?

Thanks

[smowton]

You need to add the language[monotonicAggregates] modifier to the int depth(...) predicate.

Why? As set out in https://codeql.github.com/docs/ql-language-reference/expressions/#recursive-monotonic-aggregates, without the monotonic-aggregate semantics, on the second iteration of the algorithm the node a would be assigned a depth of 1, because its child b is known to have depth 0 and its child c hasn't been assigned a depth yet. Then on the third iteration it would be necessary to revise the depth of node a to 2 (and presumably to revise any parents of a that would get transient wrong answers). This isn't compatible with CodeQL's approach to recursion, which requires that the result set grows with each iteration, with results from previous iterations never being removed.

With the language[monotonicAggregates] modifier, instead the node a isn't assigned a depth at all until all of its children have depths, and so the first answer is the final answer. This fits with the CodeQL approach to recursion.

[Ninja3047]

Thanks for the explanation!

Final query is

import tutorial

language[monotonicAggregates]
int depth(Person p) {
  if not exists(p.getAParent())
  then result = 0
  else result = 1 + max(Person g | g = p.getAParent() | depth(g))
}

from Person p
select p, depth(p)