TMI: Bug hunting

[tim]

I'm back from vacation, which means Daily TMI is back! In my confused post-vacation state, I decided I'd better set aside destructors (the last thing I worked on), as they're a new feature, and focus on fixing bugs in the compiler for a little while. There's a general consensus we need to do a sprint of fixing-bugs-not-adding-features, as the bugs seem to be piling up.

I started off looking at Issue 2383, in which a program using the deque library (part of the Rust standard library) failed to compile with a mysterious internal error message. Between getting a backtrace and looking at the source code and its imports, I figured out that the create function in deque, which has an internal impl (like an instance declaration for a type class, but nested inside a function in this case), was causing the problem -- the impl wasn't having its information serialized, so code in a different crate couldn't use it. Actually, the problem was that code in a different crate couldn't use create at all, because create has type parameters and thus gets inlined anywhere it's used (in order to do monomorphization) -- but once an inlined instance got created, it would have a reference to the nested impl, which was undefined. By adding debug statements to the metadata encoder, and looking at the trace of debug statements while encoding the standard library, I figured out that the reachability analysis (which determines which items need to be put in the external metadata, in order to save space by omitting definitions that can never be referred to externally) was simply skipping over nested items. The code even had a comment to that effect. I wasn't able to ask the original author of the comment what was meant, but I decided to go ahead and make the analysis look at nested items. Once I fixed that, I ran into a few other bugs, but those were easier to fix. And then I got to check in a fix that closed a bug, mere hours after returning from vacation! Yay!

Next I looked at Issue 2311, trying to find bugs milestoned with 0.3 or 0.4 that cause the compiler to crash. The bug title was "bounds in iface types do not appear to be resolved" and in this case, the purported cause was indeed the cause of the bug. The code in resolve that visits types was just skipping over bounds in type parameters, partly because there was a bug in the code that implements our AST visitor (generic traversal) that didn't visit methods' type parameters at all, but also because some visitor functions in resolve were calling visit::visit_ty_params instead of v.visit_ty_params -- the first is the generic function that maps a visitor onto ty params, so it ignores the first level of structure entirely and just applies the visitors' behavior to the subcomponents; the second calls the specific visitor behavior on this particular set of ty params. (Got that?) It probably took me less time to fix that bug than to write this description...

Next I looked at Issue 2380, which happily turned out to be a duplicate of the one I'd just fixed -- 2383. I checked in the test case and closed the issue -- it's nice when it's that easy.

Finally, I took on Issue 2374, which had been sitting for a while. I had some trepidations about diving back into typestate, but the fix turned out to be easy. The bug had to do with Rust's loop { ... } construct -- an infinite loop that may contain breaks or continues -- in this case, a nested loop. The inner loop was the tail expression for the outer loop, and the inner loop could break (which would return to the top of the outer loop), so its poststate had to be considered as a prestate for the outer loop's body. It turned out that the bug has to do with a rather dodgy part of typestate. In typestate, a predicate at a particular program point can have the value 0 -- "false"; 1 -- "true"; or ? -- "don't know". For example, in

let x = 1;
if foo { y <- x; } else { }

the predicate "x is initialized" evaluates to 1 just before execution of the if; 0 in the true branch of the if, just after evaluation of its statement (y <- x means "assign x's value to y, then deinitialize x"); and ? just after execution of the if, since we can't know which branch was taken.

In any case, there are multiple sensible definitions of the intersection operator on typestates (really strings of these three-valued bits, or "trits"), and each one gives you a different analysis. I was a bit hand-wavy and ad hoc about which definitions I was using where, and that informality came back to bite me in the butt here. We need a semantics! For now, the fix was to say that the poststate of a loop that may break is a state in which every predicate is 0 (known to be false), not ? (unknown), which it was before.

I looked at Issue 2445 as well, but it didn't look possible to make much headway without fixing Issue 2364. And then it was time to finish packing my apartment to move tomorrow.

Comments

[lindseykuper]

Now that I'm back in the thick of things with Rust, I'm enjoying reading these. Please keep it up.

[tim]

Well, thanks, that encourages me to continue! Though since most of the past two days got eaten by moving, there probably won't be another post till the end of tomorrow.