github-vet / bots

Bots for running analysis on GitHub's public Go repositories and crowdsourcing their classification.
MIT License
1 stars 1 forks source link

callgraph improvements using pointer argument pattern #101

Open kalexmills opened 3 years ago

kalexmills commented 3 years ago

Once #28 lands, there will be one more thing we can use in the call-graph to disambiguate nodes without using any type information.

Whether we want to do this depends entirely on how many false-positives we see. (EDIT: maybe not; I kind of just want to do it...)

We can use name, arity, and the pattern of pointer arguments to uniquely identify a function in the callgraph.

For instance, a function

func foo(x int, y *int, z int) {
  // ...
}

would have signature {foo, 3, [false, true, false]}.

We can easily construct this graph for function signatures. However, using the graph at the call-site without type information is a little bit trickier. We can use the position where the pointer argument(s) are being passed to lookup the set of all the nodes in the call-graph whose signatures match and run our BFS starting from those nodes.

That lookup is only a tiny bit tricky. I think it's easiest trading off space for time by using an index.

Functions which do not take any pointer arguments are also totally useless for our purposes. I think we can just ignore them in every case (see #102). Any edges which we may miss couldn't have a pointer crossing them in any case.

kalexmills commented 3 years ago

That last paragraph is actually much simpler to implement; and not wholly irrelevant. We only care about the portion of the callgraph which makes use of pointer arguments.

So let's open a new issue for that and do it first.