8


for automated grading of assignments I'm trying to develop a test that checks whether a c++ function is implemented recursively.

My current ideas are:
1) parse the function code and check for the keywords {for, while, goto}
2) somehow monitor the call stack. Maybe from a different thread, or by scripting GDB.

I'm curious about other ideas or maybe somebody has already implemented one of the above.

paulst
  • 81
  • 2
  • 3
    Welcome to stackoverflow.com. Please take some time to read [the help pages](http://stackoverflow.com/help), especially the sections named ["What topics can I ask about here?"](http://stackoverflow.com/help/on-topic) and ["What types of questions should I avoid asking?"](http://stackoverflow.com/help/dont-ask). Also please [take the tour](http://stackoverflow.com/tour) and [read about how to ask good questions](http://stackoverflow.com/help/how-to-ask). Lastly please read [this question checklist](https://codeblog.jonskeet.uk/2012/11/24/stack-overflow-question-checklist/). – Some programmer dude Dec 16 '19 at 12:41
  • 4
    Monitoring the call stack will only serve your purpose if you do it for unoptimized binaries. An optimizing compiler might transform a recursion into a loop. Walking the AST with clang might work, but could still easily be fooled (`if (false) recurse();`). – Max Langhof Dec 16 '19 at 12:41
  • I think parsing for keywords (not in the function but in the whole program, or someone might `#define gotcha while` outside) would be the best option. – Max Langhof Dec 16 '19 at 12:45
  • Can you introduce policies like "all function calls must use an external wrapper provided by me"? It would require to know in advance the prototype of all student-written functions. But it could open the way of using call-counters. It would however be not too hard to work around this, if students intetionally try to or fail/forget/misunderstand wrapper-calling. – Yunnosch Dec 16 '19 at 12:46
  • Alernative policy "all functions have to call `enter(id)` at start and `leave(id)` at end. This would get around the need to know all prototypes in advance, reducing it to providing unique IDs for each function. – Yunnosch Dec 16 '19 at 12:50
  • @Yunnosch `#define repeat(x) x x x` and then `repeat(enter(id);) repeat(leave(id);)`. It's more security by obfuscation... – Max Langhof Dec 16 '19 at 12:51
  • @MaxLanghof I do not believe in security by obfuscation. But please elaborate your contribution. I did not yet get the point. – Yunnosch Dec 16 '19 at 12:52
  • 1
    @MaxLanghof So it was an indirect way of agreeing with my "not too hard to work around"? – Yunnosch Dec 16 '19 at 12:55
  • @Yunnosch Yeah. Didn't know how to word it better, sorry. – Max Langhof Dec 16 '19 at 12:55
  • How about setting up the problem in such a way that it guarantees a stack overflow if solved with recursion? – Matzi Dec 16 '19 at 12:57
  • let's say you scan the code of a function "foo" for a supposedly call to itself. How would you check if it's actually calling itself or an overloaded version of "foo" – Yamahari Dec 16 '19 at 13:09
  • @Matzi How would you check the correctness of a program that overflows the stack? – byxor Dec 16 '19 at 13:34
  • @byxor You can test the correctness with a smaller input, and test if it uses recursion with a larger input. It is an automated test system, I assume it is able to run the same code multiple times. – Matzi Dec 17 '19 at 11:47

1 Answers1

4

You can use Clang's LibTooling to parse the C++ code. Then walk through the AST and build a call graph (i.e. graph with functions as nodes and edges as calls from one function to another). Search that graph for cycles, using Tarjan's algorithm. If a cycle exists, you have a potentially recursive implementation.

If the code uses dynamic dispatch (i.e. virtual functions), this paper may help you. If the code uses function pointers, this paper might but in general, the problem is undecidable.

If you're only looking for direct recursion, scanning the function's body AST for calls to itself is enough, but theoretically you'd still need to check dynamic dispatch and function pointers.

Edit: See this question for generating a callgraph.

flyx
  • 35,506
  • 7
  • 89
  • 126