mate1214 added a comment.
Hi @Szelethus !
Thanks for all your detailed and helpful input, I will make sure to go over all
the comments and answer them, but it will take some time.
A bit more background information on this checker and how it came to be might
help you and others to understand some of the choices I made, and also address
some of your general questions and worries.
I was hesitant about putting too much in the summary but it seems I should have
added more.
This was a university assignment and I was encouraged to put it up here. This
code has seen quite a few iterations and criticism.
It was my introduction to the clang tool-chain, and the clang-tidy checker was
actually the first one to exist. Explaining it briefly will help with the
"bigger picture".
It focused on single function bodies and could tell you how much the maximal
stack space that body can occupy is.
It was able to calculate with:
- variable lifetimes (even taking into account lifetimes extended by `const`
references etc.)
- recycled space (if the lifetime of a variable ends you can place the new ones
can take up its place)
- execution rules (for example: if there is an `if` statement then you take the
maximal space from its branches and not add them together etc.).
- variable length arrays (it took note when it saw one and if the resulting
number was close enough to the limit but not over it you still got a warning)
The final result was the all-time maximum so if you had a ` ... {... char
c[1000]; ...} ...` somewhere in the middle that was, by lifetime rules, gone by
the end and nothing surpassed it, you still got the correct numbers.
To produce the result, 2-3 massive recursive functions with tons of `else if`-s
were used to traverse the AST of the function body with an in-order traverse
strategy.
Now for ordinary functions it was an easy "traverse it all then get the final
number" task. But enter the templates. There seemed to be no way to tell right
away that we entered a function that had dependent types.
The easiest answer to templates was going until you see something that has
dependent types involved then quit right away and say "it is a template we have
nothing to do here".
The implementation was crude but it got the job done. It had (and still has)
tests for most of the cases (statement types, expressions, VLA, templates etc.)
and those tests felt natural there because they were concerned
with the contents of a particular function body.
Now single functions are fun, but entire call chains are what usually matter.
You can pack a few `char[10000]`-s in one body but having them in each function
of a call stack may not be so good idea.
So the static analyzer checker basically uses the same logic for single
functions as mentioned before but as the analyzer follows the execution paths
it adds up everything.
Now you could say that simply taking the whole bodies into account is enough
but consider the following example:
void f(...){
... some minor stack space is used
if(...) {
start_a_deep_and_costly_calculation();
} else {
char x[5000];
....
}
}
Here taking the whole body of `f` may yield 5000+"someting" bytes, instead of
the actual small space, that gets used in the call stack when the condition is
true and the other function gets called.
So it is reasonable to say that partial summaries should be possible up to
certain point in the body.
Having said these and the fact that the original code was even harder to read,
the `StackUsageMeasuringVisitor` came into existence to replace those massive
recursive functions.
It is based on the `RecursiveASTVisitor` and uses post-order traverse strategy
to accomplish its goals. This is where the readability over performance aspect
comes in.
Without going too deep into details my visitor assigns `Usage` values to the
AST nodes and then their parents can calculate with that, depending on what
they actually are. The aforementioned requirement to stop on templates is quite
easy,
because you do not need a real answer at the end so you can stop. The
requirement to leave out the parts after a certain point is trickier, because
it has to assign a value to all the nodes up to the top for proper calculations.
With the specifics of the visitor base class (I've seen no in-order traverse
possibility), the solution was to assign zero to everything we do not care
about and basically after a certain point it is a dry run on the rest of the
function body and some calculation in the parent nodes.
I saw a question about that `ContinueTraversing` and `ExitFlag` in the visitor.
They are both needed, because you can use the same logic for "I don't care
about anything following this statement" and "I don't care about anything if I
see a template type"
with some predicates, but in the first case you still need to do stuff with the
post-order strategy and can not stop the visitor right away.
Also I saw a comment about `Usage::Empty` and `Usage::EmptyFlagged`, the first
one says something uses no space at all in general, the second one says that it
may, but it is considered zero by decision and nothing should change that
(i.e.: visiting the same node again but as a subclass of the statement or
expression type).
The rest of this SA checker is basically "use the visitor on every function
body you enter and add the numbers to the global picture".
I'm contradicting my previous example here a bit, but if you take the SA
approach, probably what you are *really* interested in the grand picture is the
fact that the checker can follow the execution path and not make too big
mistakes during calculations.
That is what the currently included tests try to aim for. The real "nit picky"
ones like const references or ones about casts and such are left in the tidy
checker. There you are really interested in them because you want to really
focus on one function at a time and get the best possible result.
I realize this breakdown might not be the best, and anyone is welcome to
suggest a proper test layout. The other concern I had about tests is the fact
that these warnings contain numbers that the checker has to match exactly with
the ones in the test, and sometimes it feels a bit forced to require exactly
238 bytes in the message instead of "somewhere between 230-250" if we are
talking about some `f --> g --> h` call graph. I'm fine with doing the "exact"
math for a single function f but it gets redundant and cumbersome.
Also if someone says for example that something that has been assumed to take
up some space on the stack should just be zero because clang always optimizes
it out no matter what (just a thought, but may happen with the various types of
casts that the AST can include), then you may have to recalculate more tests
than it should be necessary. Again if I have slipped over some fact about the
capabilities of the testing system please correct me.
About your suggestion with the folder, it seems reasonable, but I'm not sure
about the name.
I hope this helps some of the general questions, I will post other answers as I
get to them. Thanks again for your comments!
Repository:
rC Clang
https://reviews.llvm.org/D52390
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
