Log in

No account? Create an account
A Most Vexatious Merge - Beware of the Train [entries|archive|friends|userinfo]

[ website | My Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

[Links:| My moblog Hypothetical, the place to be My (fairly feeble) website ]

A Most Vexatious Merge [Mar. 30th, 2011|10:57 pm]
[Tags|, , , , , , ]

In The Art of Unix Programming, Eric Raymond lists among his basics of the Unix philosophy the "Rule of Generation":
14. Rule of Generation: Avoid hand-hacking; write programs to write programs when you can.
He goes into this idea in more detail in chapter 9 of the same book.

I used to believe this was a good idea, and in many situations (here's a great example) it is. But my current work project, which makes heavy use of code generators and custom minilanguages, has been a crash course (sometimes literally) in the downsides. Here's the latest example.

I've recently been merging in some code a colleague wrote about a year ago, just before I started. As you'd expect, with a year's drift this was a non-trivial exercise, but I eventually got all the diffs applied in (I thought) the right places. Protip: if forced to interact with a Subversion repository, use git as your client. It makes your life so much less unpleasant. Anyway, I finished the textual part of the merge, and compiled the code.

Screens-full of error messages. Oh well, that's not so unexpected.

I'm a big fan of Tilton's Law: "solve the first problem". The chances are good that the subsequent problems are just cascading damage from the first problem; no sense in worrying about them until you've fixed that one. Accordingly, I looked only at the first message: "The variable 'state' has not been declared at line 273".

Hang on...

Git checkout colleagues-branch. Make. No errors.

Git checkout merge-branch. Make. Screens-full of errors.

Git checkout colleagues-branch. Grep for a declaration of "state". None visible.

Clearly, there was some piece of voodoo that I'd failed to merge correctly.

I spent days looking through diffs for something, anything, that I'd failed to merge properly that might be relevant to this problem. I failed.

I then spent some serious quality time with the code-generation framework's thousand-page manual, looking for some implicit-declaration mechanism that might explain why "state" was visible in my colleague's branch, but not in mine. I failed.

Finally, I did what I probably should have done in the first place, and took a closer look at the generated code. The error messages that I was seeing referred to the DSL source code rather than the generated C code, because the code-generator emitted #line directives to reset the C compiler's idea of the current file and line; I could therefore find the relevant section of generated code by grepping for the name of the buggy source file in the gen/ directory.

The framework uses code generators for all sorts of things (my favourite generator being the shell script that interprets a DSL to build a Makefile which is used to build another Makefile), but this particular one was used to implement a form of polymorphism: the C snippet you provide is pasted into a honking great switch statement, which switches on some kind of type tag.

I found the relevant bit of generated code, and searched back to the beginning of the function. Yep, "state" was indeed undeclared in that function. And the code generator had left a helpful comment to tell me which hook I needed to use to declare variables or do other setup at the beginning of the function. So that was the thing I'd failed to merge properly!

Git checkout colleagues-branch. Grep for the hook. No results.

And then it hit me.

Like all nontrivial compilers, ours works by making several transformation passes over the code. The first pass parses your textual source-code and spits out a machine-independent tree-structured intermediate representation (IR). There then follow various optimization and analysis passes, which take in IR and return IR. Then the IR is expanded into a machine-specific low-level IR, and finally the low-level IR is emitted as assembly language.

The code that was refusing to compile was part of the expansion stage. But at the time that code was written, the expansion stage didn't exist: we went straight from the high-level IR to assembly. Adding an expansion stage had been my first task on being hired. Had we been using a language that supported polymorphism natively, that wouldn't have been a problem: the code would have been compiled anyway, and the errors would have been spotted; a smart enough compiler would have pointed out that the function was never called. But because we were using a two-stage generate-and-compile build process, we were in trouble. Because there was no expansion stage in my colleague's branch, the broken code was never pasted into a C file, and hence never compiled. My colleague's code was, in fact, full of compile-time errors, but appeared not to be, because the C compiler never got a look at it.

And then I took a closer look at the screensfull of error messages, and saw that I could have worked that out right at the beginning: subsequent error messages referred to OUTFILE, and the output file isn't even open at the expansion stage. Clearly, the code had originally been written to run in the emit phase (when both state and OUTFILE were live), and he'd got half-way through converting it to run at expansion-time before having to abandon it.

Lessons learned:
  1. In a generated-code scenario, do not assume that any particular snippet has been compiled successfully just because the whole codebase builds without errors.
  2. Prefer languages with decent native abstraction mechanisms to code generators.
  3. At least skim the subsequent error messages before dismissing them and working on the first bug: they may provide useful context.
  4. Communication: if I'd enquired more carefully about the condition of the code to be merged I could have saved myself a lot of time.
  5. Bear in mind the possibility that you might not be the guilty one.
  6. Treat ESR's pronouncements with even greater caution in future. Same goes for Kenny Tilton, or any other Great Prognosticator.
Any more?

Edit: two more:
  1. If, despite (2), you find yourself writing a snippet-pasting code generator, give serious thought to providing "this snippet is unused" warnings.
  2. Learn to spot when you're engaged in fruitless activity and need to step back and form a better plan. In my case, the time crawling through diffs was wasted, and I probably could have solved the problem much quicker if I'd rolled up my sleeves and tried to understand the actual code.
Thanks to gareth_rees and jerf.

[User Picture]From: necaris
2011-03-31 02:58 am (UTC)
Writing programs to write programs seems awfully Lispy to me -- or am I misunderstanding?
(Reply) (Thread)
[User Picture]From: pozorvlak
2011-03-31 09:10 am (UTC)
Yes, metaprogramming's a big part of Lisp culture. Lisp macros have a big advantage over textual macro-expansion, though, in that they operate on ASTs rather than textual tokens. I don't know how they handle the dead-code and tool-support issues: possibly this could be handled in a general way by advanced Lisp IDEs?

Judging by SICP, there's also a culture of writing custom interpreters and compilers for external DSLs (like the kind of thing discussed above) in the Scheme world. Again, it would be interesting to know how they solve this sort of problem.
(Reply) (Parent) (Thread)
[User Picture]From: danl2620
2011-04-01 01:29 am (UTC)
We're using PLT Scheme in an environment with many layers of DSLs. The syntax transformers (fancy name for macros) are the heart of it all.

Dead code isn't a problem since we have subtle control over generation and evaluation so we never generate anything we don't mean to.

Tool interaction can certainly be a problem. It is extremely easy and natural to define new DSLs in each context, so at this point we have hundreds of them. There's no real standard way to interact with code that diverse. We will occasionally create simplistic new DSLs just so that external tools can generate or read our scripted code.
(Reply) (Parent) (Thread)
[User Picture]From: andrewducker
2011-03-31 07:23 am (UTC)
We use code generators to transform XML schemas into classes. Oh, and for UI stuff. Other than that I think it's all handcrafted. Our build stuff is all in Ant and Nant, which seems to be flexible enough by itself (at leas, so far).
(Reply) (Thread)
[User Picture]From: pozorvlak
2011-03-31 12:20 pm (UTC)
We do something like that; one problem that I've found is that now your getters and setters are declared (a) implicitly, (b) in another language, so ctags doesn't work. Do you find this a problem, or do you have a cunning solution?

Ant/Nant: I've heard many complaints about them, but "not flexible enough" is not one of them :-) Note, incidentally, that Makefiles have exactly this "snippets of copy-and-pasted code" problem.
(Reply) (Parent) (Thread)
[User Picture]From: andrewducker
2011-03-31 12:27 pm (UTC)
Our code is C# and Java. We generate Java jars and C# DLLs using Liquid.

In both cases it produces fairly standard code - our build process checks to see if any schemas have changed that day, and if so builds the associated DLL before the compile stage. This means that our continuous integration build fails if a schema has been checked in, but the code hasn't yet been brought up to date (basically treating the schema as a contract).

Can't talk about ctags, as that looks like a C thing, which we don't use :->

Ant/Nant definitely have problems - they're complex to read, it's very hard to tell if you've got it working without running it, and there's no way of debugging them short of console output. You can make them do almost anything though :->
(Reply) (Parent) (Thread)
[User Picture]From: pozorvlak
2011-03-31 01:16 pm (UTC)
Ctags is a cross-language "jump to where this symbol is defined" tool, whose output is interpreted by vi/Emacs/etc; it was originally designed for C, but offers configuration hooks for other languages. Last time I tried to extend it I ran into a world of pain and gave up, but maybe I should try again.
(Reply) (Parent) (Thread)
[User Picture]From: andrewducker
2011-03-31 02:04 pm (UTC)
Aaah - because we're generating code in the same language (and even if we weren't, reflection is cross-language in .Net) we don't have to worry about generating that kind of thing, it's built in.
(Reply) (Parent) (Thread)
[User Picture]From: pozorvlak
2011-03-31 04:23 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]From: gareth_rees
2011-03-31 05:10 pm (UTC)
Nice war story!

Your lessons look good (especially #6—though nothing will cure any sense that ESR is a Great Prognosticator quite as fast as Sex Tips for Geeks).

But I think you're missing the main one. You wrote:

days looking through diffs

I'm not sure if "days" is an exaggeration, but if it isn't then it's worth learning to spot when you're engaged in fruitless activity like that, and stepping back to try to make a better plan. Looking through diffs is basically hoping for a quick fix—something that will let you fix the problem without having to understand it. Which is great if it works (and often it does) but if it doesn't then you're going to have to understand the problem, and that means rolling your sleeves up and getting stuck in.
(Reply) (Thread)
[User Picture]From: pozorvlak
2011-04-01 11:03 am (UTC)
You're right! And in this case rolling up my sleeves and getting stuck in wouldn't have been too difficult - certainly easier than what I ended up doing. And no, "days" wasn't an exaggeration :-(
(Reply) (Parent) (Thread)