Would it be possible to have a compiler that would predict every possible 'situation specific' runtime error?

Question

By 'situation specific' I mean it uses some data that it would have access to such as your current database setup, version of some OS, etc.

Imagine if the compiler would check the database you were currently using in your app and call you out a warning saying 'just so you know, the current data in your database will never trigger the statement you just wrote' or things like 'you know, if this becomes a null value you are really going to be screwed'... It could probably take a while, but if it had something to go by (such as a current database) it could have something to check against rather than just 'every possibility'.

Do you think this is feasible/valuable? Does this exist anywhere?

It would be cool to have a quantum compiler that would figure out every possibility and automatically come up with exception handling, etc.

Answer 1

It's theoretically possible, but not likely. In essence what you're doing is asking a static analysis to use some auxiliary data to verify some claim. This is generally possible, but static analyses in general suffer from a degree of imprecision. For example if I have the code block:

If(getResultFromDB() == someResult) {
do this;
} else {
do that;
}

You essentially would like the analysis to complain at you if you write code in the first block of the if, because the database can never return someResult. This is possible in the theoretical sense, I mean it just needs to examine all possible return values for the function getResultFromDB() for a given database then conclude on an answer.

The problem is this number can be absolutely massive. And this is a problem in general with static analyses, to get precise results, we need to consider ALL possible execution paths, inputs, contexts, etc. In practice that is simply not doable, so a static analysis will usually make concessions where it reduces the size of it's current set of possibilities.

Edit: If you're interested in advanced static analysis in general, here's a fun analysis I read about done the other day. It tries to find possible XSS attacks in PHP source code. To find XSS attacks involving databases it actually simulates the effects of database queries in a sort of abstract database. http://www.cs.washington.edu/homes/mernst/pubs/create-attacks-tr054.pdf

Answer 2

I can't guarantee it, but this seems isomorphic to the Halting problem, which is known to be impossible.

Answer 3

As James suspects, this is isomorphic to the Halting problem and thus provably impossible.

In fact, this problem can trivially be reduced to compiling Perl (because Perl requires situation-dependent knowledge). There exists a simple, elegant proof that Perl cannot in fact be compiled.

Thus, we have at least one counter-example (Perl) where a static compiler is unable to check a program’s correctness, thus contradicting the hypothesis. Q.E.D.

Answer 4

This doesn't exist anywhere that I know of (yet). However I really like the idea of humanized error messages:

You know, if this becomes a null value you are really going to be screwed.

As to whether or not this is feasible: I would say that in time anything could happen, so who really knows (and who am I to predict the future).

Is it valuable: YEAH! It would be a huge time saver and if it did what you said, by coming up with exception handling, it would be one of the most useful tools ever. EVER!!!

Answer 5

It sounds like you're talking about a sophisticated form of data-flow analysis. This technique is used by existing compilers and extensively by static analysis tools. There probably isn't currently a tool out there as advanced as what you propose, but that doesn't mean it can't be created, given enough time and research.

Answer 6

While this problem may not be possible to be solved fully, there are some attempts to make static analysis as smart as possible, one of them - NStatic from Wesner Moise - has the expectations set quite high (this may also be the reason that the tool did not ship and seems to not be shipping any time soon :))

http://wesnerm.blogs.com/net_undocumented/nstatic/