Optimizing calls*() for generating call graph in C#

[chanely99]

Hi there, I'm trying to generate the call graph of the given function. That is, for the following code:

public class Test
    {
        public void a() {
            b(); 
        }
        public void b()
        {
            c(); 
        }
        public void c()
        {
            d(); 
        }
        public void d()
        {
        }
    }
    

I want something like a -> b -> c -> d. Using the suggestion here, I wrote up my first pass, which generates the expected result for my test code. However, the query is extremely inefficient, taking over half an hour running on the demo projects on lgtm.com, and over an hour on the db I want to actually use it on.

class PathCallable extends Callable{
	string getPath(Callable sink){
		(
			this.calls(sink) and
			result = this.getName() + "-->" + sink.getName()
		) or

		exists(
			PathCallable next | 
			this.calls*(sink) and
			this.calls(next) and
			result = this.getName() + " -->" +  next.getPath(sink)
		) 
	}
}

from PathCallable a, Callable d

where 
	d.hasName("d") and
	a.hasName("a") and

	a.calls*(d) 
select a, d, a.getPath(d)

Any suggestions/ideas on how to cut down on the runtime? I suspect that calls* is the culprit, but not sure if there's any better alternatives or ways to use it more efficiently. Thanks for your help

[intrigus-lgtm]

What exactly are you trying to do?
Do you want to actually view a graph/path?
Or do you only really care that there exists a path, without knowing the actual path?

Full graph: If you want a full graph, have a look at this discussion, but note that graphs are not really officially supported and you'd pretty much be on your own:
#7437

Call graph path: If you just want a single call graph path, you can use a path-problem query as described next.
(Note that you'd probably have to adapt some parts as I originally wrote this for Java I think)

Neither: If you want neither, then I unfortunately can't help you, and you'd have to wait for a CodeQL C# developer.

(Copying my reply from #7531 (comment))
Have a look at this discussion: #5353 (comment)
Also look at the additional comments from @Marcono1234.

I think this is what you want :)

(Quote from the above discussion also copied and pasted below)

Yes, this is possible!

The site you linked to mentions it here and here although it's easy too miss or easy to underestimate its potential.

When you use taint or data-flow the edges predicate is defined by the PathGraph module. But you can also define your own edges query-predicate.

A self-defined query-predicate is used in @agustingianni's blog post. It's relatively easy to port the code to "Java CodeQL".

Here's my code that only creates a path for methods itself and not for the (control flow) basic-blocks. Link to query

/**
 * @kind path-problem
 */

import java

class StartMethod extends Method {
  StartMethod() { getName() = "validateExpression" }
}

class TargetMethod extends Method {
  TargetMethod() { getName() = "findValue" }
}

query predicate edges(Method a, Method b) { a.calls(b) }

from TargetMethod end, StartMethod entryPoint
where edges+(entryPoint, end)
select end, entryPoint, end, "Found a path from start to target."

[chanely99]

The edges predicate is exactly what I'm looking for!! Thanks for your response, appreciate the help