4 ms·
The java compiler might not know if a variable is safe to pass as null, but it is not unknowable. I think on every thread similar to this that I am on, I have
by taeric 9y ago
The java compiler might not know if a variable is safe to pass as null, but it is not unknowable. I think on every thread similar to this that I am on, I have plugged Coverity as a tool that can and will flag spots like this. That is, it won't just say "it is possible this will be a null pointer exception," instead it will say "setting this value to null will lead to this dereference of a null." It can look magical sometimes, because they will trace pretty deeply into your code.
Which is just my way of saying over and over again that tooling can improve that does not require a complete rewrite of your software.
- drfuchs 9y agoIt sounds like you’re claiming that Coverity has a solution to the Halting Problem? That would indeed be magical.
- phpnode 9y agoIt doesn't sound like the OP is claiming that at all, Coverity and tools like it use a technique called Symbolic Execution [0] [0]. https://en.wikipedia.org/wiki/Symbolic_execution https://en.wikipedia.org/wiki/Symbolic_execution
- taeric 9y agoUh, no? Null pointers are far from the halting problem, though. And to be clear, there are still limitations. It can't say if any value you pass into a function that is not part of the current compilation is safe. For somewhat obvious reasons. But for a large large class of bugs, using advanced tooling can go a long way. As evidenced by the power of the advanced tooling new languages bring into the compilers. :)
- drfuchs 9y agoThe claim seems to be that the tool will always tell you absolutely whether a null-dereference will happen, and never say “maybe.” The Halting Problem is trivially reducible to this (just put an intentional null-deref in front of each halt).
- taeric 9y agoNot necessarily the same point being made. At least, they are subtly different, to my understanding. It can tell you that, "if this line is reached, and it was called from this path (with evidence on how this could happen), it will dereference a null." It is not saying that "running this program will guarantee give you a null dereference." The halting problem is more in line with "this program will terminate on any possible inputs", which is more expansive. It is trivial to say that you can prove some programs won't terminate on a particular input. Question is if you can do it for all inputs, no?
- zenhack 9y agoRice's theorem is a bit more direct here: C is Turing complete, some C programs derefernce null pointers, and some don't. Therefore, the question of whether a an arbitrary C program derefernces a null pointer is in general undecidable. But I don't think the Op was claiming it was possible to do this perfectly, just possible to write very useful tools. You will always have either flase positives or false negatives (or I suppose inputs where you just hang). Turing completeness is the bane of static analysis, but that doesn't make it a fruitless endeavor.
- UncleMeat 9y agoI wouldn't say that Rice's thm is the bane of static analysis. It is what makes the field interesting. If the problems were not undecidable then we wouldn't have do so many interesting and challenging things to make working tools.
- Gibbon1 9y agoReminds me c compilers will bitch if a variable is unused. That's basically the same problem. And sometimes the compiler will flag something that won't happen because the code path is a phantom[1]. [1] Recent headline 'Phantom Code Paths Found Harmful'
- bitL 9y agoOnly the experimental Coverity Hypercomputing branch ;-)
- slezakattack 9y agoI think you may be conflating the Halting Problem. The problem simply states whether it can be determined that a program, given a set of inputs, will eventually halt. Attempting to use a null pointer can be deterministic at compile time but it's not telling you that your program would halt or not.
- drfuchs 9y agoA tool that can reliably tell whether a given program will hit a null deference or not can also trivially be repurposed to solve the Halting Problem. Thus, no such perfect deref tool can exist. The best you can claim is that there’s a tool with few false positives and false negatives. But the original post seems to claim that there’s a perfect one.
- orf 9y agoSure, for an arbitrary program that is. One that is annotated to specify if a function returns/accepts null is a subset of this that is solveable.
- inlined 9y agoThe halting problem is used as a means to stick one's head in the sand. The halting problem imo is fundamentally uninteresting. A question that's almost as useful and is answerable is whether a program might not halt. Using your mapping to nullability, this tries to answer whether a pointer might be null. That's all the tools are trying to do and the halting problem doesn't get in the way.
- brabel 9y agoNo, it can't. You are just playing around with a problem you don't understand (null checks have 0 to do with the halting problem, it's always possible to know that a value will never be null in Java at compile time as long as you have all the source code - no dynamic libraries loaded at runtime)... unless you can actually show the proof of that, that would be really interesting to see.
- librexpr 9y agoWhile the halting problem can be pretty important in some cases, it's not very relevant in most day to day code. If you're not sure if your code will ever terminate, that usually means that you're doing something wrong. So sure, sometimes Coverity will fail because of the halting problem, and in those cases it can give an appropriate error message. Most of the time, though, it'll work just fine and be a very useful tool.
- RandomBK 9y agoThe issue on the Java side is more one of compatibility than technical feasibility. IDEA and Eclipse have been able to infer potential null issues for a while now, but it's difficult to retrofit those features into a compiler that must also accept code written 15 years ago.
- hacker_9 9y agoOne major difference is that Kotlin can tell you about nullability problems from simply analysing the method body, without going any further down the execution tree. this is a lot more reliable, and fast enough for real time IDE error reporting, than doing symbolic execution and diving into every method call to figure out all the possible paths. Same with Rust: it can determine multi threading issues from the surface layer, whereas in other languages in order to detect data races and contention you need some serious tracing analysis as well as doing a lot of runtime profiling.
- taeric 9y agoAh, please don't take my point as dismissing the new tools, either. Indeed, I would hope that a synergy between all tools lead to better tools for us all. I just have a pet peeve for the attitude of jumping rather quickly to "rewrite it all in new language" and not realizing you can bring a lot of this into existing codebases.