Re: [Edoc-main] Skip throw() function pointers?

[Niko R. <nr...@mb...>]

On Tue, 2007-11-27 at 08:25 +1100, Brendon Costa wrote:=20
> The warnings/errors I thought MIGHT be affected specifically relate to
> situations where the currently caught exception is re-thrown from a
> called function. This should emit a warning anyway for exception type
> "..." being thrown from a no-throw function. An example follows:

Obviously this is something I never thought about. To be honest, I
didn't know it was even possible. If this is important enough, perhaps
functions that re-throw outside a catch block could be detected and
always expanded, throw() or not.

Would you care to explain briefly how EDoc++ currently handles these
situations? I don't see how it can sensibly process a function with a
naked "throw;" without knowing the context it's called in (especially
since there may be multiple potential callers), or does it somehow
descend to such functions from each caller unlike its normal behaviour
of only processing each function without circular dependencies once?

> While processing a function we look at all functions it calls and add
> their exceptions to the current functions list (A little bit more
> complex than that but that is the gist).
[...]=20
> The issue discussed before arises only with circular callgraph
> dependencies. In this case the called function is not guaranteed to have
> already been processed before and so EDoc++ will descend into that
> functions implementation temporarily to determine what it might throw.

I was thinking about this, even though I'm not currently interested in
trying to implement anything myself. This seems like a somewhat
complicated instance of a common problem encountered for example in data
flow analysis in compilers, and infinitely more information can be found
elsewhere. By taking a sort of reverse approach, an accurate result
should be attainable with efficiency. The algorithm would be "pushing"
exceptions to calling functions, instead of "pulling" them from called
functions.

My explanation may be too detailed, I hope it's still understandable.

The algorithm could begin by propagating exceptions in the functions not
involved in circular paths in the regular, more efficient way. After
that, each function in the remaining call graph has a known set of
exceptions it may either throw directly or propagate from the already
processed functions it may call. This set will be expanded while the
algorithm runs, and is all that we care about.

To start with, a working set W is constructed of those functions that
may call functions with non-empty sets of known exceptions. The rest is
repeated while W is non-empty: Remove a function f from W. Propagate
(known) exceptions through f. This could be optimized to only account
for previously unknown exceptions. If new exceptions are added to f's
set of known exceptions, add to W (if not in it already) all functions
that contain potential calls to f.

We would like to only add a caller if one or more of its "call-points"
haven't yet "seen" some of f's (new) exceptions. What I'm calling
call-points match function calls in source code, so that there can be
multiple in a single function, but potential calls to any number of
functions may originate at one call-point. A static call to f has never
"seen" the new exceptions, but dynamic calls (including calls through
function pointers) require more tracking if we want to be optimal. With
a large number of potential called functions, this can be very
significant.

For a call-graph with N call-points and E exceptions possible on each
call-point, and the worst case altogether, this needs (only) EN
additions to W, if already seen exceptions per call-point are kept track
of. The amount of processing per function removed from W is basically
same as in the non-circular case, I'm guessing something like O(EN)
ignoring the function size, so, O(E=B2N=B2) total. Fully optimized maybe
only O(CEN) with C being the number of call-points to possibly call a
single function. Optimizations in choosing the order of processing are
also possible, potentially allowing more exceptions to be propagated at
once, further approaching the non-circular case.

I'm not sure about the current algorithm, but given your results in
another message, it seems to be exponential on C. Even a naive
implementation that doesn't keep track of exceptions "seen" at
call-points should easily beat it, at least with a large circular part
of the call-graph.

I'm sure there's quite a bit of code required to implement, let alone
optimize, this algorithm in EDoc++. Maybe too much considering the
problem that it solves. Or maybe there's something fundamental stopping
this from being viable at all. At least the above discussed case of
functions with naked "throw;"s may require special treatment.

Hope you got something out of this even if you aren't going to try to
implement the algorithm. The explanation sure turned out longer than I
thought...

--=20
Niko Ritari