Hi all,
After doing duplicate handlers for exceptions in C++, there is still a FIXME in Sema::ActOnCXXTryBlock which I am thinking of fixing:
// FIXME: We should detect handlers that cannot catch anything because an
// earlier handler catches a superclass. Need to find a method that is not
// quadratic for this.
I pondered a bit on this, and I cannot think of a non-quadratic algorithm. So, does anybody have ideas for this?
I am currently thinking of implementing a quadratic algorithm for it, and keep a TODO mentioning that the algorithm should be improved. That way, there at least is a check, albeit maybe not the most efficient one.
-- Erik.
Erik Verbruggen wrote:
Hi all,
After doing duplicate handlers for exceptions in C++, there is still a FIXME in Sema::ActOnCXXTryBlock which I am thinking of fixing:
// FIXME: We should detect handlers that cannot catch anything because an
// earlier handler catches a superclass. Need to find a method that is not
// quadratic for this.
I pondered a bit on this, and I cannot think of a non-quadratic algorithm. So, does anybody have ideas for this?
You could keep a set of caught types and just walk the caught class's inheritance hierarchy whenever you reach a new clause. That's O(cb), where /c/ is the number of catch clauses and /b/ is total number of base classes a class has. I think there are a lot of other things that implicitly scale with /b/.
But I don't think the quadratic/linear difference is particularly important here, where /c/ is very unlikely to get large.
John.
Yes. When Sema and CodeGen do all the conversions and checking nicely, there well may be primitives that can get you an answer faster. Hide the bad algorithms behind a nice api, the idea being, all the clients can use the nice api now, and eventually someone will fix it up.
[Oops, forgot the CC the list again with my reply]
From: cfe-dev-bounces@cs.uiuc.edu [mailto:cfe-dev-bounces@cs.uiuc.edu]
On Behalf Of Erik Verbruggen
Sent: 30 July 2009 11:35
To: clang-dev Developers
Subject: [cfe-dev] RFC: unreachable catch-clauses due to superclass
cathes
Hi all,
After doing duplicate handlers for exceptions in C++, there is still a
FIXME in Sema::ActOnCXXTryBlock which I am thinking of fixing:
// FIXME: We should detect handlers that cannot catch anything
because an
// earlier handler catches a superclass. Need to find a method that
is not
// quadratic for this.
I pondered a bit on this, and I cannot think of a non-quadratic
algorithm. So, does anybody have ideas for this?
I am currently thinking of implementing a quadratic algorithm for it,
and keep a TODO mentioning that the algorithm should be improved. That
way, there at least is a check, albeit maybe not the most efficient
one.
Actually, that FIXME sounds wrong. An earlier catch handler for a superclass may not trigger due to ambiguity when using multiple inheritance. Example:
struct base {};
struct a1 : base {};
struct a2 : base {};
struct derived : a1, a2 {};
int main() {
try {
throw derived();
}
catch( base const &) {} // ambiguous, not selected
catch( a1 const &) {
// a1 unambiguously derived from base
// yet this is the selected catch clause
}
}
This might be worth checking in as a perverse test case, but I'm not sure what the protocol for run-time checks in C++ is - all the current tests are syntax-check only as we are not yet generating code for C++.
AlisdairM
AlisdairM(public) wrote:
From: cfe-dev-bounces@cs.uiuc.edu [mailto:cfe-dev-bounces@cs.uiuc.edu]
On Behalf Of Erik Verbruggen
// FIXME: We should detect handlers that cannot catch anything
because an
// earlier handler catches a superclass. Need to find a method that
is not
// quadratic for this.
Actually, that FIXME sounds wrong.
It's not wrong, it just doesn't tell the whole story.
An earlier catch handler for a superclass may not trigger due to ambiguity when using multiple inheritance.
Or because the superclass is inaccessible.
Sebastian
Erik Verbruggen wrote:
Hi all,
After doing duplicate handlers for exceptions in C++, there is still a FIXME in Sema::ActOnCXXTryBlock which I am thinking of fixing:
// FIXME: We should detect handlers that cannot catch anything because an
// earlier handler catches a superclass. Need to find a method that is not
// quadratic for this.
I pondered a bit on this, and I cannot think of a non-quadratic algorithm. So, does anybody have ideas for this?
I am currently thinking of implementing a quadratic algorithm for it, and keep a TODO mentioning that the algorithm should be improved. That way, there at least is a check, albeit maybe not the most efficient one.
Hi,
that sounds like lowest common ancestor problem to me. That's O(n+q) for
trees where n is the total count of classes in the module and q is the
number of queries. Perhaps the problem could be generalized to DAGs.
Regards,
Martin Doucha
Rolling all feedback together would give an algorithm like:
- start with an empty list of okayed-types
- for each handler in the AST:
--- get the canonical type A
--- if A is ambiguous, give a warning and continue [2]
--- if the okayed-types list is empty, just put A in, and continue
--- for each handler in the okayed-types list:
------- get the canonical type B
------- "deep check" if B is a base-class for A [1]
------- if it is, give a warning
------- if not, put A into the okayed-types list
[1]: do this in a separate method, which "skips" ambiguous base-classes[2], but otherwise just recursively/iteratively walks the base-classes. This method can be changed with an improved Sema/CodeGen.
[2]: Remaining question is if there is a utility method to check if a class is the base-class of a diamond-construct (as mentioned in AlisdairM's mail)....?
-- Erik.