Quetzalcoatal

How bugs get fixed

2012-01-10T10:19:00.000-05:00

Recently, I have had the ~~misfortune~~opportunity to fix bug 695309. This bug is perhaps a good exemplar of why "obvious" bugs take weeks or months to fix; it is also a good example of why just reporting that a bug occurs for the filer is insufficient to fix. In the hope that others might find this useful, I will explain in a fake liveblogging format how I fixed the bug (fake because I'm writing most of these entries well after they happened).

October 20

There's a bug that "Thunderbird sometimes marks entire newsgroups as unread" in my email. Time to open up the bug report… reported in version 8… I'm pretty sure I've seen this once or twice before, so I don't think it's just a "the news server borked itself" issue. Time to file it away until when I have more time.

November 12

Another comment reminded me that I have this tab open. I've definitely seen it a few times, but I need to remember to keep Thunderbird open with logging enabled to figure out what's going on. It's reported as being a regression from version 8, when I checked in a slew of the NNTP URI parsing patches, so that seems like a probable target to look at. The question is why URI parsing would be causing an intermittent problem instead of a constant issue?

December 3

Some NNTP logs. Nothing is obviously amiss (not terribly unexpected, since logging either tends to drown you in useless information or omit the things you really want to know). Note after the fact: the NNTP logs in fact contain the smoking gun; it's just that the poster trimmed it out.

December 6

Bienvenu comments that no developer has seen the problem; this isn't true, as I have seen it (but just taken to avoiding it as much as possible). At some point in time, I figured out that the issue could be avoided by shutting down Thunderbird before putting my laptop to sleep. After being prodded over IRC, I finally sat down and attempted to debug it. The working thesis is that the problem is that newsrc files are getting corrupted, so I faithfully save several copies of the newsrc for confirmation. The msf files are also generally good candidates, but since other flags are untouched, it's highly unlikely in this bug.

I successfully trigger the bug once. The reports are mixed: the newsrc didn't get trashed as expected at first, but later it did. However, there is a brief window of time after the bug happens which allows you to fix it, if you shut down Thunderbird. Knowing what I now know, this is because the newsrc file is written out on a timer, so the newly-all-unread messages wouldn't have been saved to disk to show the bug. Since I always think of what to log after the fact, I try to trigger it a few more times.

None of the later tests are quite so successful as the first one. It does start to dawn on me that the bug probably has two parts. There is a first step that puts the group into a pre-bug situation; a second step actually produces the symptoms of the bug. Omniscient addendum: the first step is where the bug happens; the second step is just the delay in getting the bug to occur. I report my findings, and subsequent comments all but confirm my hypothesis for a necessary component.

December 12

This bug seems to be happening for me only when I don't want it to happen. I thought of more things to test earlier, and had them ready to copy-paste into my error console to try to find a smoking gun. This test confirms that the fault originates with the newsrcLine (so something reset that); more investigation leads to only one truly likely scenario to cause this to happen. At this point, I am all but convinced that the bug happens in two parts. All of the debugging needs to focus on when the first part happens; the symptoms (everything being marked read) are a result of Thunderbird attempting to repair the damage that had already been done. Since most people are going to try to report based on when they see the problems, I'm probably not going to get anything useful.

December 13

Hey, I found it again. Tests confirm that the high water number was first set to 0. This means either we have memory corruption or we are setting the value incorrectly initially. Looking at the code, this is set from a call to sscanf. A simple test indicates that I can set the input value to 0 if I don't have it scan a number. Now all I need to do is figure out network traffic that can cause this. Time to try to trigger it with xpcshell tests. And then get frustrated because I still can't do it reliably.

December 18

With Wireshark (logging on Windows is rather annoying), I finally can track down the network traffic of interest. It turns out that we are off-by-one in terms of responses. This really should be enough to get xpcshell to report the error. However, it also means I probably should finally give up and go for the NNTP logs again to catch the error: it is painfully obvious that the problem is that the internal state is futzed up. This also means that other various newly-reported issues (more frequent auth failures, various alerts like "Not in a newsgroup", etc.) are pretty much confirmed to be the same bug.

January 9

I finally buckled down and turned my very old hackish code for NSPR log management into an extension. This means that I don't have to futz with environment variables on Windows, and it also gives me an easy way to trim down my log size (since unlike environment variables, I can stop logging). I test and finally get the NNTP log of interest.

Now that I have a log, I can try to work backwards and figure out how this bug happens. The failure is easily ascribable to somehow thinking we've already opened the socket when we open a socket; this much I have known for almost a month (the Wireshark told me). What the NNTP log gives me is a more fine-grained ability to try to trace the code after-the-fact to figure out where the bug is.

Working backwards from the log

NNTP logs helpfully record the address of the the NNTP protocol object when emitting output, so the best place to start is from the first line of that object. Since the numbers are hard to read, so I replace the addresses with a more obvious string like "evil." The next state was set to SEND_FIRST_NNTP_COMMAND—that clearly should be NNTP_LOGIN_RESPONSE, so let's see why it might be skipped. The latter is set if m_socketIsOpen is false, so perhaps someone could open a socket if it isn't set.

This variable is set only by nsMsgProtocol, specifically the LoadUrl method. So who might call that? Still nothing out of the ordinary is popping out at me, so it's time to return to the logs (A particularly astute developer might be able to find out the bug without returning to the log here, but I doubt most people would come up with the final flash of insight yet).

To figure out the problem, it's important (to me, at least) to set out the time frames. The natural sequence of events for a connection is to be created, connected to the server, and then go through several iterations of running URLs. Is this bad connection a new connection or an old one (since I started the log after TB started up, I can't guarantee that this is truly a new connection)? Thunderbird stupidly (but helpfully, in this case) tells me when the connection is created, since we get a log message of "creating" in the constructor. Since this message doesn't appear, it's being reused.

Wait—that message is there, tucked just underneath the lines that tell me LoadUrl is run. As I am often wont to do, I announce my revelation to IRC: "< jcranmer> bienvenu: please slap me". The code for the constructor is pretty simple, but there is one little function call that ends up causing the problem. If I tell you the exact revision that caused the regression (specifically, the first hunk of that the patch), can you find the regression? Click me if you can't

Reproducing the bug

Now that I know the exact sequence of events to cause the bug, I can write a test to reliably reproduce the bug. I can also explain why the symptoms occur. First, a connection's socket dies, but it doesn't fail the timeout check in mailnews code, so it remains in the cache. Next, the server schedules a URL on the connection, which promptly dies. If there are many more URLs to be run (when we're doing, say, a timed update), then we have several elements in the queue waiting to be processed. Now, we attempt to run a new URL; with no connections available in the cache, we now create a new connection and run the new URL on that. Since the queue is not empty, the SetIsBusy(false) call ends up pulling a queued URL and setting up the state (including opening up the connection) and running that. Then the constructor finishes, and the new URL for which the connection was constructed is used to initialize it. Since the connection is by now open, the code moves straight to the run-my-URL part of the state machine, which misinterprets the login response as the answer to the command it just sent. This ends up leading to all of the various badness subsequently observed.

The description of these events is pretty complicated. A condensed version is added to the test I constructed to get this to happen, which is called, fittingly enough, test_bug695309.js. I am not going to try to come up with a better name, as I think most people might agree that this is where naming tests after bug numbers is most desirable. Naturally, the code to actually trigger this is complicated: I started with code to trigger just the unread effect, and then switched to monitoring the highwater mark instead (one less download of messages). I need to fill up the connection cache and then figure out how to kill the connections (restarting the server seems to do an adequate job). After that, I need to run enough URLs to cause the connections to queue, and then trigger a load of the folder in question at precisely the right moment. All of these requires paying careful attention to what happens synchronously and what does not, and it all relies on knowing the precise steps of what will happen as a result of each action. Any of a small number of changes I could make in the future is probably going to "break" the test, in that it will cease to test anything meaningful.

Postmortem on fixing it

I'm sure some people might look at this bug and ask several questions. Let me try to anticipate some of them and answer them.

Why did the reviewers fail to notice this change?: This bug is a result of the confluence of several changes. In the beginning, SetIsBusy was mostly a no-op, so calling it from the constructor was safe. Then the URL queue was added, and SetIsBusy was used to indicate that the connection was ready to receive a new URL from the queue. This turned it into a time bomb, since the code was correct only because the server was null in the constructor and the queue should have been empty during connection construction anyways. The final change was moving initialization of the server, which triggered the time bomb. But even then, it triggered the bomb only in a rather abnormal circumstance. At no time would the code have failed any automated tests or any of the "does your patch work" tests that a reviewer normally goes through: robustness during connection interruption is both sufficiently difficult to test and rare enough that it generally doesn't get tested.
Why did this bug take so long to track down?: The time since December 1 is truly a result of lack of time: I have had maybe 1 good week to work on anything due to outside factors. There are two, maybe three, people in active participation with Mozilla who know this code well, and out of those, only one was able to somewhat reliably reproduce it (specifically, the one with the least amount of time on his hands). I could have relied on others to gather the information I needed, but my previous efforts in QA have taught me that getting people to give you necessary information is often very difficult, especially when the information collectable at the obvious point in time is completely useless. I realize in retrospect that there were some more technically inclined people in the bug (at which point in time I was already devoting as much attention as I felt I could spare on the bug anyways). The bug is also particularly pernicious in that the most valuable information is that which is gathered before any visible symptoms occur; it was after I figured out how to discover that the bug was going to occur that I could track it down further.
Will the fix be backported to more stable branches?: At this stage, I am looking at two fixes: the small one-liner that fixes the specific bug, and the larger patch which fixes the larger issue of "the NNTP URL connection queue is a ticking time bomb". The former I would definitely like to see backported to aurora and beta (and possibly release if there are plans for another one before the next uplift), and I can't see any reason a small patch on the most-highly-voted TB bug filed since 01-01-2011 would get rejected (it is the newest bug to have more than 5 votes, and the next largest has 1/3 less and is almost twice as old).
Why is this bug so hard to reproduce?: If you think to the cause of the bug, it is that it is passing a check in a function that is always called. It therefore seems like this bug should be triggered a majority of the time, and not an undependable minority. As I alluded to earlier, the problem is that this also has to interact with a buggy pending URL queue management system. In short, most of the time, this queue will be empty during the initial, buggy call; with a poor timing of events (less likely to happen on most developers' computers, in short), the queue will cease to be empty and cause the problem. Indeed, when crafting my test for reproduction, I discovered that letting the event loop spin in one particular location (after killing connections) would fail to trigger the bug. In the real world, that is one of the places where the event loop is most liable to spinning for the longest.

2011 LLVM Developers' Meeting

2011-12-14T23:34:00.003-05:00

This feels a bit late to be talking about the 2011 LLVM Developers' Meeting (seeing as how it happened almost exactly a month ago), but since the slides have been put up over the past week and the talks were only put up on Youtube this week, I suppose I can finally back notes up with links and not talk so abstractly.

Of the talks I went to, I think by far the most interesting one was Doug Gregor's talk on Extending Clang. It covered various extension points in Clang and some of their capabilities with simple examples. It also ended in what might be impolitely titled "Where Extending Clang Sucks" and what was politely titled "Help Wanted." This boils down to "plugins are hard to use" and "one-off rewriters are hard to write". Indeed, I think the refrain of problematic architecture for further tools was repeated in more than a few presentations: Clang has the information you want and need, but squeezing the information out is inordinately difficult.

What was probably the most popular talk was Chandler Carruth's talk on Clang MapReduce—Automatic C++ Refactoring at Google Scale (his slides appear to not yet be posted). From what I recall, the more interesting parts of the talk are closer to the end. He had a discussion on developing a language for semantic queries to identify code that needs to be replaced (the example query was essentially "find all calls to Foo::get()"); the previous things people have tried are regexes (C++ is not syntactically regular, it's recursively enumerable), XPath (unfortunately, ASTs, despite their name, aren't exactly tree structures), and pattern matching ASTs (not always sufficient textual clues). The team's idea was to use a matcher library on "AST" values as predicates. He also spoke a bit about some of the efforts they did on using Clang with Chromium.

There is a point brought up in Chandler's talk that I want to reiterate. One of the problems with writing refactoring tools (or static analysis tools in general) is in getting people to trust that they work. For any sufficiently large codebase—millions of lines of code or more—it is fairly certain that the project will run up against the nasty edge cases in parsing tools. If a tool is intended to run mostly automated analysis on such code, it is impossible for anyone to be able to look at the output and ensure complete correctness. However, most sufficiently large codebases come with massive testsuites to help people believe their code is correct; if the same parser is capable of producing code that passes the entire testsuite, then one only needs to trust that the analysis is done correctly, a much smaller task. Without such a capability, no one would be willing to trust the analysis; in other words, any parser which is not capable of then generating code is never going to be trusted as a basis for further work, at least, not if you are looking at million-line projects.

Speaking of Chromium and Clang, there was talk on this too. As I am sure most of my audience is well aware, Chromium uses Clang for several of its buildbots (and all of its recent Mac development); I wish Mozilla could get Clang to be a tier 2 or tier 1 platform for Mac and Linux. As for why they prefer it, the brief rundown is this: better diagnostics, faster, smaller object sizes, they can write a style checker, and they can build better tools off of it (like AddressSanitizer, which, unsurprisingly, itself had a talk). Again, there were the complaints: building the rewriter proved to be difficult a task (notice a trend here?). Incidentally, I also attended the AddressSanitizer talk, but I'm getting tired of copying down notes of talks, so I'll let those slides and the video speak for themselves.

Finally, I did give a talk on DXR. It seemed to be well-received; I had a few people coming up to me later in the day thanking me for the talk and asking more questions about DXR. Something I did discover when giving it, though, is just how difficult giving a talk really is. I had specific notes on the slides written in my notebook, only to discover that I wasn't able to gracefully retreat to the podium and read the notes long enough to figure out what to say next. If you're wondering what I forgot to mention in the talk, it's mostly a more coherent explanation during the undead demo.

How I got involved with Mozilla

2011-10-15T14:46:00.002-04:00

My journey to become a contributor to Mozilla started during the summer of 2007, which was when I started very heavily using Thunderbird. The initial impetus is probably best traced to this thread in a newsgroup: a long, semi-flame war. I wanted to excise the flame war portions from the rest of the thread, so I filed bug 392404 (the first bug I ever filed!). That bug was marked as a duplicate of bug 11054.

At that time, I had a fair amount of free time (this was around the time my summer internship ended but before school started). I downloaded the source code to Thunderbird and then built it, only to discover that every time I built it, it crashed in a linker. After bugging people about it on IRC, I learned that I needed a swap file, and I finally managed to get a successful build. Then, having had programming experience, I decided just to fix the bug myself. I honestly can't remember for certain, but I believe I built the original patch without much aide from people on IRC--it was only the inability to build that I had needed to ask for help.

I do remember that I needed guidance on how to get a patch committed. This being mailnews code around the time that Mozilla Messaging was being set up, the pool of potential reviewers and superreviewers was rather slim. I had been advised that David Bienvenu and Scott McGregor were my best candidates for review. Unfortunately, around this time, Scott had cut off all work with Mozilla; after two months of not getting any response from him whatsoever, I switched to another reviewer.

While I was waiting for the patch to be reviewed, I recall Dan Mosedale talking about bug 132340 indirectly; later, when I asked if there was a fix that people would be interested in, that bug was what I was pointed towards. This patch took about two months and four review cycles to be accepted, but it eventually satisfied my reviewer and superreviewer and became my first contribution to Mozilla. That first patch I worked on? It turned out to be significantly more complicated than I first appreciated and finally was closed 9 months after I started work on it. After bug 132340, I started getting more and more involved with Mozilla development and have been a contributor since then.

Public Service Announcement #2

2011-09-19T22:17:00.002-04:00

A brief note to all application and operating system developers:

Failure to respond to a prompt does not indicate accession to perform the actions that would otherwise occur. Especially if those actions have a high risk of losing my data. So I would like to thank you (whichever product is responsible for my most recent undesired restart) for completely obliterating my class notes. At the very least, you did not destroy all of my research too, just a day's worth.

Not-so-random mozilla-central factoids

2011-08-03T23:49:00.003-04:00

Back when I was looking at reducing disk usage of running DXR, I used the sizes of the generated CSV files to make a rough estimate of how many times the average line of mozilla-central needs to be parsed and compiled (the answer is around 20). Now, having just respun a build of mozilla-central with the newest version of DXR, I have a larger database with some fairly accurate statistics of its size. This all started when I wondered what our most common function name was, so I decided to make a list of factoids (it's also a chance to refresh my SQL memory). All of the statistics come from a build of Firefox today on Linux x86-64 with debug and tests disabled.

Notes on accuracy

DXR tries as hard as possible to correlate data back to the original source code, and it is very likely that it can get itself confused in some weird circumstances. I don't yet have a good idea of where all of the buggy cases are, but I am aware of some broad strokes. Pretty much all information that deals with references is likely missing large swathes of the codebase. Information about callers only counts explicit calls (i.e, call expressions). The most accurate data I have is the macro information and the least accurate is information involving a templated class in almost any fashion. I also suspect that scope information is malformed in a non-empty set of cases, and I'm pretty sure that the number of global objects in any count is overcounted.

Type statistics

I count in mozilla-central just 33,555 distinct types. Of these, we have 13,648 typedefs, 6,523 structs, 6,470 classes, 5,147 enums, 1,410 interfaces, and 357 unions. Of all of these, 13,740 types are nested in another in some fashion, and another 4,524 types are templated. I'm not counting separate template instantiations as new types, but I am counting specializations individually.

Then there's the inheritance. I found 7,715 direct inheritance relations, all but a handful of which (around 200) are public. These relations account for 2,317 distinct base classes and 6,157 distinct subclasses. Naturally, some types are inherited much more than others. The winner, by a factor of 6, is nsISupports, having a whopping 3,156 implementations. Pickle and IPC::Message tie for second place with 501 implementations each; nsIRunnable takes 4th place at 282 implementations. The 5th place goes to nsXPCOMCycleParticipant (242). Rounding out the top 10 are nsIDOMElement (226), nsRunnable (224), nsScriptObjectTracer (209), nsSupportsWeakReference (154), and nsIObserver with 144. Subclass relationships involving templates are not counted, which may bump a few classes up into this list.

Macros

There are 42,457 distinct definitions of macros to produce 38,045 distinct names. Of these, 30,475 look like variables and 7,647 look like functions, which implies that 77 macros take on both depending on how they got defined.

How about calling them? I count just 482,142 macro invocations, so each macro is being invoked about 12 times on average. But... 20,628 of our macros are never used (or almost 48.6% of them), so the average is closer to 25 times. Of course, some macros really get used. Here are the top 5:

Count	Macro name
23,109	nsnull
22,941	PR_FALSE
20,139	NS_OK
13,154	NS_IMETHOD
13,138	NS_IMETHODIMP

Functions

There are 137,903 functions in mozilla-central. Of these, there are 68,867 having a distinct name. Of these, I found 33,693 in the global scope, and 8,943 that were a member of a class. Directly templated functions comprise about 2,291 functions. Just for fun, I found that there are 774 functions named exactly "Init" and a further 1,681 that begin with "Init" (case-insensitively in the last case).

In terms of calling these functions, I found 291,598 distinct edges in the callgraph (this is definitely an underestimate, since I am missing a large number of cases). For my usage, a callgraph is not a traditional directed graph but rather a hypergraph, where each edge goes from a single head to a set of nodes in the tail. These comprise 85,144 distinct callers and 67,098 distinct targets. Of the targets, I found 51,590 distinct functions being called statically, 13,274 distinct virtual functions invoked, and 2,234 distinct function pointers or pointers-to-member-functions being called. If I break it up by calls, 246,086 of the calls are static function calls, 41,770 virtual function calls, and 3,742 function pointer calls. I want to emphasize here that information pertaining to templates, in particular nsCOMPtr is completely missing, so a lot of calls to nsISupport's methods are missing, which is going to horribly skew the statistics.

Counting the function pointers, we have 65 pointers-to-member-functions and around 1700-1800 function pointers (those numbers do not add up to what I should get above, but I'm not sure who's in error here). I count about 19,721 virtual functions that I generated target information for (a subset of all virtual functions), and 65,761 implementations of those virtual functions, so the average virtual function has about 3.4 implementations. In addition, I found about 981 of these virtual functions were also called statically.

Now I'm sure, having mentioned it earlier, that you too are now wondering what the most common function name in mozilla-central is. The answer should be pretty obvious when you consider the most heavily-implemented class. And the winners are...

Count	Function name
1,687	Release
1,680	AddRef
1,600	GetIID
1,587	QueryInterface
774	Init
659	operator=
549	Log
517	Read
506	Write
396	GetType

The top 4 methods are related to XPCOM; the famed Init method is a mere 5th place. Of interesting note is that there are 659 assignment operators; I'm guessing some of these may be default copy constructors implemented for non-POD classes.

Variables

There's not much to say here. We have some 623,237 variables of some kind. Most of these, naturally, are local variables or parameters: 516,627, to be precise. We additionally have 82,008 members of some compound type, and 24,602 global variables. Some interesting statistics would be to compute the number of variables whose names defy our naming convention or the number of static constructors that need to be run before startup, but that data is harder to compute.

Warnings

I count 5,283 reported warnings for mozilla-central. Of these, 1,608 are warning about the use of non-virtual destructors with virtual functions. Another 940 warn about our use of mismatched enumeration types. There are 1,348 warnings of unused things. Finally, there are 1,551 warnings about use of extensions, leaving 466 "miscellaneous warnings".

Build statistics

The final set of statistics I have is mere size statistics for the build information. There are about 8,581,746 non-empty lines of text comprising some 320MiB of data. These are organized into about 51,469 files, including 1,469 files of generated files in the build directory. My output SQLite file was 464MiB, easily comprising around 3.5 million rows of data. We also have about 38MiB of binary files (like PNGs) in the source tree. Almost 15MiB of the generated included files were produced, comprising around 354,893 non-empty lines of text.

I think the best way to summarize this data is "mozilla-central is a massive codebase." It also goes to show you why just looking at source code without compiling is a bad idea: around 3-5% of our source code actually isn't in the source tree to begin with but is instead automatically created at compile time.

Fixing sqlite compatibility issues

2011-08-02T20:23:00.003-04:00

While testing the separation of database generation and the actual webpage, I had discovered that there was a weird bug in that SQLite cheerily opened the database but then complained that the database was invalid. I thought this was quite weird, and double-checked that the file had copied correctly: same size, correct permissions, file gives the same information (SQLite database, version 3). After a bit of thought, I found the problem:

[mozbuild@dm-dxr01 ~]$ sqlite3 -version
3.3.6
...
jcranmer@xochiquetazal ~ $ sqlite3 -version
3.7.7 2011-06-23 19:49:22 4374b7e83ea0a3fbc3691f9c0c936272862f32f2

The databases were incompatible. So I did some investigation and I found an easy way to fix this:

jcranmer@xochiquetzal ~ $ sqlite3 -line '.dump' spidermonkey.sqlite > /tmp/statements.sql
[mozbuild@dm-dxr01 ~]$ sqlite3 -init /tmp/statements.sql spidermonkey.sqlite

That worked wonderfully. So if you ever need to fix a problem with SQLite-incompatible versions, that is how you dump a database to sqlite and import it again. While I'm on the topic, this is worth paying attention to:

-rw-r--r-- 1 jcranmer   jcranmer   27394048 Aug  2 17:13 spidermonkey.sqlite
-rw-r--r-- 1 jcranmer   jcranmer   27419572 Aug  2 17:17 statements.sql

The list of SQL statements is only 0.1% larger than the SQLite file. If I look at the older database, it's actually smaller than the database. Food for thought.

Callgraph

2011-07-26T13:29:00.003-04:00

There remains, as of this blog post, one major regression from the original dehydra-based DXR, and that is the lack of support for callgraph. The main problem I have here is trying to pin down the scope of the feature. To give an idea of why this hard, I pose the following challenge: how many different ways are there in C++ of invoking a function, as would be viewed from the generated assembly code? Here is my list:

Global function
Invocation of non-virtual member
Nonvirtual invocation of virtual member
Constructor, copy constructor invocations
Implicit destructor invocation
Functors (objects that implement operator())
C++0x lambdas (which appears to be a functor): Count all of these as "one," if you like, since they're all still more or less boil down to a call addr instruction, so it really boils down to how pedantic you get about the differences. Most of these look fairly distinct in source code level as well too. But, on the plus side, being a statically-known function call, all of these are easy to handle.
Virtual member function invoked virtually: This is clearly different at an assembly level, since it requires a vtable lookup with the added possibility of thunking. From a handling perspective, though, this is more or less statically known, since we know the possible targets of a virtual method call are limited to subclasses of the method, if we assume that people aren't sneaky.
Function pointers: Easy to dip into, impossible to think about off the top of your head (how many tries does it take you to write the type of a function pointer that returns a function pointer without using typedefs?), and it requires data-flow analysis to solve. The main question is if it's even worth trying to at least plan to support function pointers, or if they should just be left out entirely.
Pointer-to-member function pointers: Theoretically easier than function pointers (because we again have a more limited state space), but they still suffer from the same need to data flow analysis. Not to mention that they are much harder to use, and that their implementations are much different from function pointers.
Template dependent name resolution: Templates, as far as C++ is concerned, is essentially a macro system that is more powerful and more inane than the C preprocessor. So if the expression that is to be called is dependent on the type parameter, then the function call can be any (or all) of the above depending on what was passed in.
throw: The entire exception handling semantics in C++ essentially gets handled by the ABI as a combination of magic function calls and magic data sections; undoubtedly a throw itself is a function call which gets to do stack unwinding. Most of this stuff isn't exposed in the code, it just leaks out in semantics.

One goal I've had in mind is to make sure I can do some reasonable support for dynamic languages as well as static languages. To that end, I've looked up other callgraph implementations to see what they do in the realm of indirect function calls. The answer is a mixture of either "do runtime instrumentation to build the callgraph" or "ignore them altogether." The closest I've seen is one implementation that indicated when the address of a function was taken.

Viewsource up and running

2011-07-22T15:27:00.002-04:00

This morning, I have made available a public version of the viewsource code. Viewsource was originally a web tool to output a pretty-printed version of the Dehydra objects for simple snippets of source code. Since I found it a useful idea for debugging, I also added dumps for the now-defunct Pork rewriting toolset, JSHydra, and now, finally Clang.

The odd tool out here is clang, as it has neither a debug-useful XML output nor a simple JS representation that can report the output, which requires me to make the tool a two-stage process: the first stage is a compiler plugin that figures out from clang::RecursiveASTVisitor which functions and classes it needs to worry about dumping out, and then writes out the code for the second stage, another compiler plugin that actually dumps the generated AST information to the console. In other words, I have a plugin to write a plugin that is used to dump information to write plugins.

Eventually, I hope to be more complete in the information I can dump out (particularly type locations and type information), but this is complete enough to be at least somewhat useful for finding interesting things, such as understanding what the location information actually refers to. As I work on this tool more and more, this should enable me to find and fix many bugs in DXR.

DXR alpha 3 release

2011-07-21T20:05:00.003-04:00

I am pleased to announce the third release of DXR. Compared to the previous release, the UI has been tweaked and several bugs have been noticed and fixed. In particular, I have improved the support of links, and fixed the bug that prevented the type hierarchy from being properly realized. I have also introduced support for indexing the IDL code in Mozilla's codebase, as well as indexing generated code in general. I have also added yet another tree, comm-central.

Compared to the original implementation of DXR by Dave Humphrey, there remains one unimplemented feature, namely support for the callgraph. My plan for the next release will focus on implementing this feature as well as any other bugs I uncover via real-world testing. The other major features for the next release will be a JSON query API for data and improved support for multiple trees.

In a more general viewpoint, the plugin architecture has been much improved. There is now support for viewing code-coverage data in the source tree (I do not have a visible demo of this yet), and the support for IDL is entirely a separate plugin. Implementing these plugins has caused me to realize that there is need for better hooks in the current architecture (especially with regards to the generated HTML), and these will also be forthcoming in the next release.

The final point to make is that I have moved the viewsource code into its own repository, as well as adding support for a limited subset of the clang AST. The website does not properly support clang at this time owing to problems in the server's current toolchain configuration; when these issues are resolved, I will be demonstating the tool better.

Random discovery

2011-07-13T22:44:00.003-04:00

I've been playing around with the idea of replacing mork for leveldb, the two being at roughly the same "no feature database" level. The sanest way to do a decent head-to-head comparison involves picking the least powerful wrapping around this API (the message folder cache) and then reimplementing it twice. Actually, I originally intended to try implementing mdb with a leveldb backend for a drop-in replacement to mork. Five minutes successfully dissuaded me, as the mdb interfaces require you to implement about five interfaces to get to "open a database".

For realistic testing, I grabbed a real database and instrumented all of the accesses in real use cases (i.e., startup and shutdown). Since the real data is what I love to call my Profile from Hell™, there's enough data that I can get some reasonable statistical accuracy in timing. I'm also testing what is a path of note in Thunderbird startup, so I made sure to test cold startup, which, incidentally, is very annoying. A 1 second test takes several seconds to reload xpcshell.

The first performance results were very surprising to me. I expected that not touching the knobs would probably result in a mild performance regression (mork is fast by virtue of choosing the "space" option in the space/time tradeoff). What I wasn't expecting was something that was an order of magnitude slower. I eventually got off my butt and hooked up jprof to see what was going wrong. Unfortunately, I forgot that jprof's visualization of output results sucks, so I traipsed back to my very old post to pull down my script to turn the dumb HTML file into a more manageable dot file (which needed fixing, since the only commit to jprof in 3 years changed the output syntax on me).

Clearly, the output file implicates JS as being the hotpath. Since this is xpcshell and I had to hack the jprof initialization in, I decided to move the jprof initialization to the execution point to eliminate the effect of parsing my ~20K-line input file (I did say it loads a lot of data). When I last used jprof for serious performance tracking, I noted that the main regression appeared to be caused by XPCThrower::ThrowBadResult (about 60%, apparently). So here, the main regression appears to be... you guessed it, JS exceptions (the method names have changed in 3 years, though).

That is truly unexpected, since I'm not supposed to be actually changing any API. After looking back at the code and inspecting much more deeply, I found out that I actually was changing API. You see, the nsIMsgFolderCacheElement has two ways to access properties: as strings or as integers. Accessing integers clearly throws an error if the value isn't there; accessing strings also appears to throw an error. Assuming this to be the case, I explicitly threw an error in both cases in my new implementation. It turns out that the current implementation actually doesn't throw for strings (I'm not sure if it's intended to or not). Fixing that greatly improved the times. A brief summary of the real results is that mork is faster on startup, even on general property access, and slower on shutdown, only the last of which is not surprising.

In summary: throwing JS exceptions, at least via XPCOM, is very, very, very slow. If that code is a potential hotpath, just say no to exceptions.

Location information

2011-07-12T20:26:00.002-04:00

One of the hardest parts about writing a compiler is producing correct location information. Well, it is very easy to get the precise location of a token (most of the time, in any case), but the hard part is assigning token locations to actual AST productions, since they are composed of several tokens. Take a simple function definition: void foo(int bar) {}. Nearly every token in that definition can be argued to be the right location of the function. Hence showing only line information is common for compilers: in most normal usage, you get the same information no matter which token you pick. However, there are times when the actual column number is crucial: if you need to correlate something to the original source code (e.g., for rewriting or for DXR), you want that column number to be spot on.

Now let's consider pathological cases. Suppose we define that function in a templated class. Do I want the location of the template or the location of the template instantiation? The former is often better, but there are times you want the latter. But you can also make the function in a macro: #define FUNCTION(name) void name(int bar) {} and FUNCTION(foo). Do I want the location within the macro definition or the location in the macro instantiation? Macros let you be really evil: #define FUNCTION(name) void start##name(int bar) {}. Now which location do I want? Oh yeah, and while we're on the topic, there is also the issue of autogenerated code (e.g., I want the location to be what it was in the original file). So which location do I use?

There are two orthogonal issues here: which token do I use in the "final" version of the text, and which version of the text do I grab it from. There are several versions of the text (think of the lexer not as a single unit but instead of a chain of steps that pass the information between them); we don't care about some of the intermediate representations (e.g., what the code looks like after replacing trigraphs). The lowest level of these is the position in the last form of text, just before being parsed for real. It's also important to track the position through repeated invocations of macros (most of the time). We also want the location in the text file as it is when fed to the compiler to begin with, as well as the position in the original file before it is fed to whatever output the C/C++ source file.

Clang gives us some of this information for any SourceLocation. The source of the actual token is the spelling location. On the other hand, the instantiation location is the location of the outermost macro invocation to generate the production. It is possible to get the tree of locations by repeatedly calling getImmediateSpellingLocation, which only looks down one level of invocation. To get the result after following #line directives, you need to use the presumed location, which looks at the instantiation location. It is possible to pass in the spelling location to getPresumedLoc to produce the correct results, though. Unfortunately, precise location information goes out the window if your macro uses # or ## (it goes into "scratch space" whose line numbers don't correlate well enough to the original source code for me to make sense of).

The other direction is one of the possible methods to get the source location in the class. A function declaration merely has 6 of these: the start and end of the declaration, the location of the name identifier, the location of the type specifier, the location after the template stuff, and the location of the right brace. I would go in more detail, but I haven't yet catalogued all of the ways to get this information to be sure that the method names actually mean what they claim to mean.

DXR alpha 2 release

2011-07-06T12:59:00.003-04:00

I am pleased to announce a second alpha release of DXR. Several improvements have been made, including changes to the UI as well as better cooperation with macros. A complete list of changes can be found at the end. As this is the second release, I have expanded the live demo to include not one but two separate indexing trees: clang and mozilla-central, both of which are current as of last night.

The advantage of DXR is that it sees the source code by instrumenting the compiler at build time, so it is able to understand classes most of whose methods are defined by macros, like Clang's RecursiveASTVisitor. Like any source code browser, it is possible to click on an identifier and then go see information about the identifier, such as its points of declaration, or its definition. Unlike LXR and MXR, however, it knows what type of identifier it's working with, so you won't be offered the definition of BuiltinType::getKind if you look up the getKind method of an Expr object.

Another new feature is support for plugins, to allow people to use different compilers, add in support for more languages, or even augment the UI with new features like capturing line-coverage information. The current support is rudimentary, but there is already active work on a dehydra-based indexer.

A list of new features:

Improved search speed at runtime, and dropped glimpse as a prerequisite
The web UI works in newer versions of Firefox
Support for plugins has been added
Disk space requirements have been radically reduced
Setup configuration is easier
Link extents have been fixed in many cases
Declarations can now be seen along with definitions
Macros can now be browsed like source code

Google Groups Public Service Announcement

2011-06-30T19:20:00.003-04:00

For the past few days, it appears that Google Groups has stopped mirroring newsgroups properly; this included the various Mozilla mailing lists. It does, however, appear to be forwarding posted messages, so if you send a message via the UI and you don't see anything show up... don't panic, and don't repost it 5 times.

I don't know how long Google Groups will be down, but, in the meantime, you can use your favorite newsreader to read the newsgroups. Heck, Thunderbird has a built in news client. If you wish to use mozilla mailing lists, just add in the server news.mozilla.org. You can then happily see everything that you would be able to see with Google Groups, if it were working.

Mozilla-central and DXR

2011-06-29T17:33:00.004-04:00

Some of you may be wondering why it is taking me so long to build a DXR index of mozilla-central. Part of the answer is that I'm waiting to bring DXR on clang back up to the original instantiation in terms of feature support. The other part of the answer is that mozilla-central is rather big to index. How big? Well, some statistics await…

I first noticed a problem when I was compiling and found myself at 4 GiB of space remaining and dwindling fast. I'm used to fairly tight space restrictions (a result of malportioning the partitions on my last laptop), so that's not normally a source of concern. Except I had been at 10 GiB of free space an hour before that, before I started the run to index mozilla-central.

The original indexing algorithm is simple: for each translation unit (i.e., C++ file), I produce a corresponding CSV file of the "interesting" things I find in that translation unit—which includes all of the header files included. As a result, I emit the data for every header file each time it is included by some compiled file. The total size of all data files produced by the mozilla-central run turned out to be around 12GiB. When I collected all of the data and removed duplicate lines, the total size turned out to be about 573MiB.

Step back and think about what this means for a moment. Since "interesting" things to DXR basically boil down to all warnings, declarations, definitions, and references (macros and templates underrepresented), this implies that every declaration, definition, and reference is parsed by the compiler, on average, about 20-25 times. Or, if you take this as a proxy for the "interesting" lines of code, the compiler must read every line of code in mozilla-central about 20-25 times.

The solution for indexing is obviously not to output that much data in the first place. Since everyone who includes, say, nscore.h does so in the same way, there's no reason to reoutput its data in all of the thousands of files that end up including it. However, a file like nsTString.h (for the uninitiated, this is part of the standard internal string code interfaces, implemented using C's versions of templates, more commonly known as "the preprocessor") can be included multiple times but produce different results: one for nsString and one for nsCString in the same place. Also, there is the question of making it work even when people compile with -jN, since I have 4 cores that are begging for the work.

It was Taras who thought up the solution. What we do is we separate out all of the CSV data by the file that it comes in. Then, we store each of the CSV data in a separate file whose name is a function of both the file it comes in and its contents (actually, it's <file>.<sha1(contents)>.csv, for the curious). This also solves the problem of multiple compilers trying to write the same file at the same time: if we open with O_CREAT | O_EXCL and the open fails because someone else created the file… we don't need to do anything because the person who opens the file will write the same data we wanted to write! Applying this technique brings the total generated CSV file data down to around 1GiB (declaration/definition mappings account for the need for duplicates), or down to about 2 times the real data size instead of 20 times. Hence why the commit message for fixing this is titled Generate much less data. MUCH LESS.

Of course, that doesn't solve all of my problems. I still have several hundred MiBs of real data that need to be processed and turned into the SQL database and HTML files. Consuming the data in python requires a steady state of about 3-3.5 GiB of resident memory, which is a problem for me since I stupidly gave my VM only 4GiB of memory and no swap. Switching the blob serialization from using cPickle (which tries to keep track of duplicate references) to marshal (which doesn't) allowed me to postpone crashing until I generate the SQL database, where SQL allocates just enough memory to push me over the edge, despite generating all of the SQL statements using iterators (knowing that duplicate processing is handled more implicitly). I also switched from using multiple processes to using multiple threads to avoid Linux failing to fork Python due to not enough memory (shouldn't it only need to copy-on-write?).

Obviously, I need to do more work on shrinking the memory usage. I stripped out the use of the SQL for HTML generation and achieved phenomenal speedups (I swore that I had to have broken something since it went from a minute to near-instantaneous). I probably need to move to a light-weight database solution, for example, LevelDB, but I don't quite have a simple (key, value) situation but a (file, plugin, table, key, value) one. Still not hard to do, but more than I want to test for a first pass.

In short, DXR indexing for mozilla-central is being recreated as I write this. Enjoy.

Why autoconf sucks

2011-06-22T20:16:00.003-04:00

I'm going to go out on a limb and guess that the GNU autotools are one of the most heavily used build systems in existence. What I'm not going to guess is that, as a build system, it sucks. I will grant you that C and C++ code in particular are annoying to compile by virtue of the preprocessor mechanics, and I will also grant that autotools can be useful in trying to work out the hairiness of working on several close-but-not-quite-the-same platforms. But that doesn't justify why you need to make a build system that is so bad.

One of the jobs of autotools (the configure script in particular) is to figure out which compilers to use, how to invoke them, and what capabilities they support. For example, is char signed or unsigned? Or does the compiler support static_assert(expr) or need to resort to extern void func(int arg[expr ? 1 : -1])? Language standards progress, and, particularly in the case of C++, compilers can be slow to correct their implementations to the language.

The reason I bring this up is because I discovered today that my configure failed because my compiler "didn't produce an executable." Having had to deal with this error several times (my earlier work with dxr spent a lot of time figuring out how to manipulate $CXX and still get a workable compiler), I immediately opened up the log, expecting to have to track down configure guessing the wrong file is the executable (last time, it was a .sql file instead of .o). No, instead the problem was that the compiler had crashed (the reason essentially boiling down to std::string doesn't like being assigned NULL). That reason, this is the program that autoconf uses to check that the compiler works:

#line 1861 "configure"
#include "confdefs.h"

main(){return(0);}

(I literally copied it from mozilla's configure script, go look around line 1861 if you don't believe me). That is a problem because it's not legal C99 code. No, seriously, autoconf has decided to verify that my C compiler is working by relying on a feature so old that it's been removed (not deprecated) in a 12-year old specification. While I might understand that there are some incredibly broken compilers out there, I'm sure this line of code is far more likely to fail working compilers than the correct code would be, especially considering that it is probably harder to write a compiler to accept this code than not except it. About the only way I can imagine writing this "test" program to make it more failtastic is to use trigraphs (which is legal C code that gcc does not honor by default). Hey, you could be running on systems that don't have a `#' key, right?

Addendum: Okay, yes, I'm aware that the annoying code is a result of autoconf2.13 and that the newest autoconfs don't have this problem. In fact, after inspecting some source history (I probably have too much time on my hands), the offending program was changed by a merge of the experimental branch in late 1999. But the subtler point, which I want to make clearer, is that the problem with autoconf is that it spends time worrying about arcane configurations that the projects who use them probably don't even support. It also wraps the checks for these configurations in scripts which render the actual faults incomprehensible, including "helpfully" cleaning up after itself so you can't actually see the offending command lines and results. Like, for example, the fact that your compiler never produced a .o file to begin with.

Alpha release of dxr

2011-06-17T13:44:00.003-04:00

I am pleased to announce an alpha release of DXR built on top of Clang. A live demo of DXR can be found at http://dxr.mozilla.org/clang/, which is an index of a relatively recent copy of the Clang source code. Since this is merely an alpha release, expect to find bugs and inconsistencies in the output. For more information, you can go to #static on irc.mozilla.org or contact the static analysis mailing list. A list of most of the bugs I am aware of is at the end of this blog post.

So what is DXR? DXR is a smart code browser that works by using instrumented compilers to use what the compiler knows about the code to provide a database of the code. For C and C++ in particular, using an instrumented compiler is necessary, since it is the only reliable way to fix the issue of macros. Take, for instance, RecursiveASTVistor in the Clang codebase. Most of the almost 1200 functions are defined via macros as opposed to in raw code; as a consequence, the doxygen output for this class is useless: as far as I can tell, there are only five methods I can override to visit AST nodes. On the other hand, DXR neatly tells me all of the methods that are defined, and can point me to the place where that function is defined (within the macro, of course).

Where can you get the code? DXR is available both as a github repository (use the dxr-clang branch) and as a Mercurial repository. Instructions on how to use can be found on the wiki page.

The following is a list of known problems:

Links occur at odd boundaries
Some lines have id="l234"/> prepended
Non-root installs (i.e., installing to http://dxr.mozilla.org/clang/) cause issues. Interestingly, refreshing the page often causes things to work.
There is a long list of scrolling text when compiling code. Ignore it.
HTML generation produces IndexErrors
.csv files are created in the source directory and HTML code is generated.
Inheritance searches don't match the full hierarchy, only one or two levels.

Documentation lies

2011-06-10T16:46:00.002-04:00

For various reasons, I want to get the extent of a particular expression in clang. Most AST objects in clang have a method along the lines of getSourceRange(), which, on inspection, returns start and end locations for the object in question. Naturally, it's the perfect fit (more or less), so I start using it. However, it turns out that the documentation is a bit of a liar. I would expect the end location to return the location (either file offset or file/line) of the end of the expression, give or take a character depending on whether people prefer half-open or fully closed ranges. Instead, it returns the location of the last token in the expression. Getting the true last token requires this mess: sm.getFileOffset(Lexer::getLocForEndOfToken(end, 0, sm, features)). Oh yeah, in case you couldn't have guessed, that causes it to relex the file starting at that point. For an idea of my current mood, pick a random image from Jennifer's recent post and you'll likely capture it.

DXR updates

2011-06-10T02:55:00.002-04:00

It's been almost a week since I last discussed DXR, but, if you look at the commit log, you can see that I've not exactly been laying back and doing nothing. No, the main reason is because most of the changes I've been doing so far aren't exactly ground-breaking.

In terms of UI, the only thing that's changed is that I know actually link the variable declarations correctly, a result of discovering the typo that was causing it not to work properly in the midst of the other changes. From a user's perspective, I've also radically altered the invocation of DXR. Whereas before it involved a long series of steps consisting of "build here, export these variables, run this script, build there, run that script, then run this file, and I hope you did everything correctly otherwise you'll wait half an hour to find you didn't" (most of which takes place in different directories), it's now down to . dxr/setup-env.sh (if you invoke that incorrectly, you get a loud error message telling you how to do it correctly. Unfortunately, the nature of shells prohibits me from just doing the right thing in the first place), build your code, and then python dxr/dxr-index.py in the directory with the proper dxr.config. Vastly improved, then. But most of my changes are merely in cleaning up the code.

The first major change I made was replacing the libclang API with a real clang plugin. There's only one thing I've found harder (figuring out inheritance, not that I'm sure I've had it right in the first place), and there are a lot of things I've found easier. Given how crazy people get with build systems, latching onto a compiler makes things go a lot smoother. The biggest downside I've seen with clang is that it's documentation is lacking. RecursiveASTVisitor is the main visitor API I'm using, but the documentation for that class is complete and utter crap, a result of doxygen failing to handle the hurdle of comprehending macros. I ended up using the libindex-based dxr to dump a database of all of the functions in the class, of which there are something like 1289, or around 60 times the functions listed in the documentation. Another example is Decl, where the inheritance picture is actually helpful. It, however, manages to have failed to document DeclCXX.h, which is a rather glaring omission if what you are working with is C++ source.

The last set of changes I did was rearchitecting the code to make it hackable by other people. I have started on a basic pluggable architecture for actually implementing new language modules, although most of the information is still hardcoded to just use cxx-clang. In addition, I've begun work on ripping out SQL as the exchange medium of choice: the sidebar list is now directly generated using the post-processing ball of information, and linkification is now set up so that it can be generated independent of tokenization. In the process, I've greatly sped up HTML generation times only to regress a lot of it by tokenizing the file twice (the latter part will unfortunately remain until I get around to changing tokenization API). It shouldn't take that much longer for me to rip SQL fully out of the HTML builder and shove SQL generation into a parallel process for improved end-to-end time.

Some things I've discovered about python along the way. First, python closures don't let you mutate closed-over-variables. That breaks things. Second, if you have a very large python object, don't pass it around as an argument to multiprocessing: just make it a global and let the kernel's copy-on-write code make cloning cheap. Third, apparently the fastest way to concatenate strings in python is to use join with a list comprehension. Finally, python dynamic module importing sucks big time.

Where am I going from here? I'll have HTMLification (i.e., remove SQL queries and replace with ball lookups) fixed up tomorrow; after that, I'll make the cgi scripts work again. The next major change after that is getting inheritance and references in good shape, and then making sure that I can do namespaces correctly. At that point in time, I'll think I'll be able to make a prerelease of DXR.

Fakeserver and future changes

2011-06-08T02:48:00.003-04:00

This is perhaps a bit belated, but I thought I'd give a brief overview of where I think fakeserver should be going over the next several months (i.e., when I find time to work on it). For those who don't know, Fakeserver is a generalized testing framework for the 4 major mail protocols: IMAP, NNTP, SMTP, and POP. For various reasons, I'm actually getting around to fixing problems with it right now. The following are the features I am going to be adding:

Multiple connections

This is a long-standing bug in fakeserver, which I first discovered about 3 years ago, when I started testing the IMAP implementation. Fakeserver uses the same connection handler for every connection, which means the state of the connection is shared between all connections, obviously very problematic for a protocol as stateful as IMAP. In my defense, I cribbed from the stateless (more or less) HTTP server, and used the barely-stateful NNTP as my first testbed. This bug is probably the most API-breaking of any change to fakeserver code: every invocation of the server must replace new nsMailServer(new handler(daemon)) with new nsMailServer(function (d) { return new handler(d); }, daemon). Subsequent to that, handlers are no longer easily exposed by the server, which means all manipulation must be on the daemon end. This causes major changes to SMTP code and NNTP code for different reasons; pretty much everyone else hides between helper functions that act as a firewall to minimizing code changes.

Multi-process fakeserver

This change (which has no patch yet) will move the fakeserver running into another process. I have some working prototypes for manipulating objects across two different processes, but I don't yet have a good IPC mechanism (which Mozilla strangely lacks) for actually communicating this information. As for API changes, I haven't gotten far enough yet to know the impact of multiprocess fakeserver, but the answer will probably that handler information goes from "hard to get" to "impossible to get". On the plus side, this should essentially enable mozmill tests to be able to use fakeserver.

SSL fakeserver

I figure fakeserver needs SSL support--it's common in the mail world to use SSL instead of plaintext, so we need to support it. In terms of external API, the only change will be some added methods to start up an SSL server (and methods to get STARTTLS working to, provided my knowledge of how SSL works is correct). The API pseudo-internal to maild.js gets more convoluted, though: essentially, I need to support multiple pumping routines for communication. On the plus side, though, if the API I'm planning on implementing turns out to be feasible, we should also be able to get generic charset decoding for nearly free, for i18n tests.

LDAP fakeserver

LDAP address book code is almost completely untested. I'd like to see that fixed. However, LDAP is a binary protocol (BER, to be precise). If I can implement the SSL support in the API framework I want to, then it shouldn't be that much more to get a BER-to-text-ish layer thrown in on top of it. The downside is that I'm pretty much looking at using our own LDAP library to do BER encoding/decoding since I don't want to write that myself.

DXR thinking aloud

2011-06-04T18:40:00.002-04:00

A primary goal of DXR is to be easy to use. Like any simple statement, translating that into design decisions is inordinately difficult, and I best approach such issues by thinking out loud. Normally, I do this in IRC channels, but today I think it would be best to think in a louder medium, since the problem is harder.

There are three distinct things that need to be made "easy to use". The first is the generation of the database and the subsequent creation of the web interface. The second is extension of DXR to new languages, while the last is the customization of DXR to provide more information. All of them have significant issues.

Building with DXR

Starting with the first one, build systems are complicated. For a simple GNU-ish utility, ./configure && make is a functioning build system. But where DXR is most useful is on the large, hydra-like projects where figuring out how to build the program is itself a nightmare: Mozilla, OpenJDK, Eclipse, etc. There is also a substantial number of non-autoconf based systems which throw great wrenches in everything. At the very least, I know this much about DXR: I need to set environment variables before configuring and building (i.e., replace the compiler), I need to "watch" the build process (i.e., follow warning spew), and I need to do things after the build finishes (post-processing). Potential options:

Tell the user to run this command before the build and after the build. On the plus side, this means that DXR needs to know absolutely nothing about how the build system works. On the down side, this requires confusing instructions: in particular, since I'm setting environment variables, the user has to specifically type ". " in the shell to get them set up properly. There are a lot of people who do not have significant shell exposure to actually understand why that is necessary, and general usage is different enough from the commands that people are liable to make mistakes doing so.
Guess what the build system looks like and try to do it all by ourselves. This is pretty much the opposite extreme, in that it foists all the work on DXR. If your program is "normal", this won't be a problem. If your program isn't... it will be a world of pain. Take also into consideration that any automated approach is likely to fail hard on Mozilla code to begin with, which effectively makes this a non-starter.
Have the user input their build system to a configuration file and go from there. A step down from the previous item, but it increases the need for configuration files.
Have DXR spawn a shell for the build system. Intriguing, solves some problems but causes others.

Conclusion: well, I don't like any of those options. While the goal of essentially being able to "click" DXR and have it Just Work™ is nice, I have reservations about such an approach being able to work in practice. I think I'll go for a "#1 and punt on this issue to someone with more experience."

Multiple language

I could devote an entire week's worth of blog posts to this topic, I think, and I would wager that this is more complicated and nebulous than even build systems are. In the end, all we really need to worry about with build systems is replacing compilers with our versions and getting to the end; with languages, we actually need to be very introspective and invasive to do our job.

Probably the best place to start is actually laying out what needs to be done. If the end goal is to produce the source viewer, then we need to at least be able to do syntax highlighting. That by itself is difficult, but people have done it before: I think my gut preference at this point is to basically ask authors of DXR plugins to expose something akin to vim's syntax highlighting instead of asking them to write a full lexer for their language.

On the other end of the spectrum is generating the database. The idea is to use an instrumenting compiler, but while that works for C++ or Java, someone whose primary code is a website in Perl or a large Python utility has a hard time writing a compiler. Perhaps the best option here is just parsing the source code when we walk the tree. There is also the question about what to do with the build system: surely people might want help understanding what it is their Makefile.in is really doing.

So what does the database look like? For standard programming languages, we appear to have a wide-ranging and clear notion of types/classes, functions, and variables, with slightly vaguer notions of inheritance, macros (in both the lexical preprocessing sense and the type-based sense of C++'s templates), and visibility. Dynamic languages like JavaScript or Python might lack some reliable information (e.g., variables don't have types, although people often still act as if they have implicit type information), but they still uphold this general contract. If you consider instead things like CSS and HTML or Makefiles in the build system, this general scheme completely fails to hold, but you can still desire information in the database: for example, it would help to be able to pinpoint which CSS rules apply to a given HTML element.

This begs the question, how does one handle multiple languages in the database? As I ponder this, I realize that there are multiple domains of knowledge: what is available in one language is not necessarily available in another. Of the languages Mozilla uses, C, assembly, C++, and Objective-C[++] all share the same ability to access any information written in the other languages; contrast this to JS code, which can only interact with native code via the use of a subset of IDL or interactions with native functions. IDL is a third space, which is a middle ground between native and JS code, but is insufficiently compatible with either to be lumped in with one. Options:

Dump each language into the same tables with no distinction. This has problems in so far as some languages can't be shoehorned into the same models, but I think that in such cases, one is probably looking for different enough information anyways that it doesn't matter. The advantage of this is that searching for an identifier will bring it up everywhere. The disadvantage... is that it gets brought up everywhere.
Similar to #1, but make an extra column for language, and let people filter by language.
Going a step further, take the extra language information and build up the notion of different bindings: this foo.bar method on a python object may be implemented by this Python_foo_bar C binding. In other words, add another table which lists this cross-pollination and takes it into account when searching or providing detailed information<.
Instead of the language column in tables, make different tables for every language.
Instead of tables, use databases?

Hmm. I think the binding cross-reference is important. On closer thought, it's not really languages themselves that are the issue here, it's essentially the target bindings: if we have a system that is doing non-trivial build system work that involves cross-compiling, it matters if what we are doing is being done for the host or being done for the target. Apart from that, I think right now that the best approach is to have different tables.

Extraneous information

The previous discussion bleeds into this final one, since they both ultimately concern themselves with one thing: the database. This time, the question is how to handle generation of information beyond the "standard" set of information. Information, as I see it, comes in a few forms. There is additional information at the granularity of identifiers (this function consumes 234 bytes of space or this is the documentation for the function), lines (this line was not executed in the test suite), files (this file gets compiled to this binary library), and arguably directories or other concepts not totally mappable to constructs in the source tree (e.g., output libraries).

The main question here is not on the design of the database: it's only a question of extra tables or extra columns (or both!). Instead, the real question is in the design of the programmatic mechanisms. In dxr+dehydra, the simple answer is to load multiple scripts. For dxr+clang, however, the question becomes a lot more difficult since the code is written in C++ and isn't dynamically loading modules like dehydra does. It also begins to beg the question of the exposed API. On the other hand, I'm not sure I know enough of the problem space to be able to actually come up with solutions. I think I'll leave this one for later

Who's responsible for libxul

2011-06-02T13:32:00.003-04:00

As you might have gathered from my last post, I spend a fair amount of time thinking up ways of visualizing software metrics. Today's visualization is inspired by a lunch conversation I had yesterday. Someone asked "how much space does SVG take up in libxul?" This isn't a terribly hard problem to solve: we have a tool that can tell us the size of symbols (i.e., codesighs), and I have a tool that gives me a database of where every symbol is defined in source code.

Actually, it's not so simple. codesighs, as I might have predicted, doesn't appear to work that well, so I regressed back to nm. And when I actually poked the generated DXR database for mozilla-central using dehydra (I haven't had the guts to try my dxr-clang integration on m-c yet), I discovered that it appears to only lack the information about functions. Both static functions and member C++ functions—my suspicions of breakage are now confirmed. So I resorted to one of my "one-liner" scripts, as follows:

cat <<HEREDOC
<!DOCTYPE html>
<html><head>
<title>Code size by file</title>
<script type="application/javascript" src="https://www.google.com/jsapi"></script>
<script type="application/javascript">
google.load("visualization", "1", {packages: ["treemap"]});
google.setOnLoadCallback(drawChart);
function drawChart() {
  var data = new google.visualization.DataTable();
  data.addColumn('string', 'File');
  data.addColumn('string', 'Path');
  data.addColumn('number', 'Code size (B)');
HEREDOC
nm --format=bsd --size-sort /src/build/trunk/browser/dist/bin/libxul.so | cut -d' ' -f 3 > /tmp/libxul.symbols.txt
find -name "*.o"| xargs nm --format=bsd --size-sort --print-file-name | sed -e 's/:/ /g' | python -c '
import sys
symbols = set(open("/tmp/libxul.symbols.txt").readlines())
files = {}
for line in sys.stdin:
  args = line.split(" ")
  if args[-2] in "tTvVwW" and args[-1] in symbols:
    files[args[0]] = files.get(args[0], 0) + int(args[1], 16)
out_lines = set()
for f in files:
  f2 = f.replace("./", "")
  path = f2.split("/")
  str = "src/"
  for p in path[:-1]:
    out_lines.add((str + p + "/", str, 0))
    str += p + "/"
  out_lines.add((f2, str, files[f]))
print "data.addRows([" + ",\n".join([repr(list(x)) for x in out_lines]) + "]);"
'

cat <<HEREDOC
  data.addRow(["src/", null, 0]);
  var tree = new google.visualization.TreeMap(document.getElementById('tmap'));
  tree.draw(data, {maxDepth: 3, headerHeight: 0, noColor: "#ddd", maxColor: "#ddd",
    minColor: "#ddd", midColor: "#ddd"});
}
</script></head>
<body>
  <div id="tmap" style="width: 100%; height: 1000px;"></div>
</body>
</html>
HEREDOC

It's really 4 commands, which just happens to include two HEREDOC cats and a multi-line python script. The output is a ~~little~~not-so-little HTML file that loads a treemap visualization using the google API. The end result can be seen here. To answer the question posed yesterday: SVG accounts for about 5-6% of libxul, in terms of content, and about another 1% for the layout component; altogether, about as much as our xpconnect code accounts for libxul. For Thunderbird folks, I've taken the time to also similarly divvy up libxul, and that can be found here.

P.S., if you're complaining about the lack of hard numbers, blame Google for giving me a crappy API that doesn't allow me to make custom tooltips.

Visualization toolkits suck

2011-06-02T02:37:00.003-04:00

This is a rant in prelude to a blog post I expect to make tomorrow morning (or later today, depending on your current timezone). As someone who is mildly interested in data, I spend a fair amount of time thinking up things that would be interesting to just see dumped out visually. And I'm not particularly interested in small datasets: one of my smaller datasets I've been playing with is "every symbol in libxul.so"; one of my larger datasets is "every news message posted to Usenet this year, excluding binaries" (note: this is 13 GiB worth of data, and that's not 100% complete).

So while I have a fair amount of data, what I need is a simple way to visualize it. If what I have is a simple bar chart or scatter plot, it's possible to put it in Excel or LibreOffice... only to watch those programs choke on a mere few thousand data points (inputting a 120K file caused LibreOffice to hang for about 5 minutes to produce the scatter plot). But spreadsheet programs clearly lack the power for serious visualization information; the most glaring chart they lack is the box-and-whiskers plot. Of course, if the data I'm looking at isn't simple 1D or 2D data, then what I really need won't be satiable with them anyways.

I also need to visualize large tree data, typically in a tree map. Since the code for making squarified tree maps is more than I care to do for a simple vis project, I'd rather just use a simple toolkit. But which to use? Java-based toolkits (i.e., prefuse) require me to sit down and make a full-fledged application for what should be a quick data visualization, and I don't know any Flash to be able to use Flash toolkits (i.e., flare). For JavaScript, I've tried the JavaScript InfoVis Toolkit, Google's toolkit, and protovis, all without much luck. JIT and protovis both require too much baggage for a simple "what does this data look like", and Google's API is too inflexible to do anything more than "ooh, pretty treemap". Hence why my previous foray into an application for viewing code coverage used a Java applet: it was the only thing I could get working.

What I want is a toolkit that gracefully supports large datasets, allows me to easily drop data in and play with views (preferably one that doesn't try to dynamically change the display based on partial options reconfiguration like most office suites attempt), supports a variety of datasets, and has a fine-grained level of customizability. Kind of like SpotFire or Tableau, just a tad bit more in my price range. Ideally, it would also be easy to put on the web, too, although supporting crappy old IE versions isn't a major feature I need. Is that really too much to ask for?

Building with dxr-clang

2011-06-01T18:34:00.002-04:00

As I'm building yet another program from scratch (I've now run dxr on four separate trees in the past week, and I'm still looking for a good one to use for tests), let me take the time to explain how to set up DXR on your own computer. Instead of stuffing it in this blogpost, most of the information is instead on wiki.mozilla.org. One thing not on that page is that I currently have the sql files in the clang dumper dump to the source directory instead of the object directory, so the DXR config needs to have the source and object directory be the same setting, even if you don't actually build the source in-place!

clang-DXR

2011-05-27T20:22:00.003-04:00

As mentioned previously, the first thing I started doing was getting DXR to use libclang to build the indexing. As of right now, I have a tool which kind of works. In that it can successfully build a program but utterly fails to produce reliable SQL output due to constantly swallowed segfaults (I think). My test program uses cmake to build, so it "helpfully" hides the noise of what is actually going on, so debugging will have to wait until next week.

The main unexpected hurdle is that for all of the wonderful praise clang has had lavished on it, I have found it surprisingly difficult to use. I had expected to be able to do a more or less straightforward port of dxr.js, with some cosmetic changes to handle differences in naming, etc., between dehydra and libclang. That expectation is now hopelessly gone; libclang provides nothing near the clean API that dehydra does. For example, to get the fully-qualified name of a class, instead of being able to say type.name, I have to walk up the entire AST hierarchy of the class to find all of its containing classes and namespaces to do it myself. If I want to get one for a function (which, in C++, requires differentiating between overloads, so I need type parameters), I have to build my own type-to-string dumper. Indeed, no less than half of my code so far is merely trying to build the type names I need to dump out. In addition, it seems that the clang people are dismissive of an idea to include a higher level API than is currently present.

If you didn't notice from the links, by the way, dxr is now on github.

Summer DXR work

2011-05-23T17:14:00.003-04:00

So, far this summer, I will be mostly putting away Thunderbird work and will instead be focusing my attention on reviving DXR. Sometime this week, I expect to be updating the installation on dxr.mozilla.org (simply so I can match up better on DXR to what I'm doing locally).

What will I be doing on DXR? First and foremost, I will be making it easier to run DXR on anything that is not Mozilla. Or anything that is Mozilla, for that matter. This will be done by cleanly separating the build/instrumentation steps from the rest of DXR. In other words, setting CC/CXX/LD/etc. should be all you need to do build your program.

After that, I will be working on using Clang to get information instead of using gcc+dehydra. If I understand the current Apple development process, supporting clang is essential to supporting Mac OS X builds in the future. I will also work on getting IDL and JS support added.

One other thing I want to do is (time permitting) to get DXR to represent the results of different builds, so that you can get results other than just the current Linux build. I have a list of other ideas to play around with, but I'll leave that for later, since I don't know if I'll time to start them or not.

Don't expect dxr.mozilla.org to see all of the new features immediately. I'll update when I feel like it (i.e., I see enough stability to do it), and it's easier for me to work more locally on my laptop. I also find it easier to do rapid updates on a smaller project than Mozilla which takes quite some time to do clobber rebuilds; I don't know which project(s) I'll be using for all of my work yet, so don't bother asking.

Usage share of newsreaders, update

2011-01-21T17:06:00.003-05:00

A few months ago, I logged the usage share of various newsreaders for roughly the month of August. Since then, I ran updated tests, alternating monthly between logging by users and messages, which gives me statistics for September through November. Later months are not available because the newsserver I used has now gone away (without notifying users!), and I did not want to switch this script to the new one, since comparability is lost.

One of the uses I had for original statistics collection was to argue why NNTP support for Thunderbird still matters. During an IRC discussion, it was brought up that August is a poor month for logging since there is a tradition of using that month for vacation. Pulling up the data for the month of October, the last one for which I have this data, indicates that approximately 720,000 messages were posted that month, indicating that August is indeed a poor month for indicating volume.

Have the statistics changed much? Google Groups and Thunderbird are both within .2% absolute difference of the scores I calculated last time (44.02% and 12.3%, respectively). Down the line, things change: Outlook Express had 8.98%, followed by Forte Agent at 8.86%. Live Mail had 2.83% and MT-NewsWatcher had 2.51%. Indeed, the tail is longer, with 20.52% as compared to before.

As my new server has a longer retention time, I no longer wish to use the same script as before. My next goal is to log every header of every message posted this year, so that I may collect more information without having to list everything I need, particularly information useful in determining the user of mail-to-news gateways and information to help identify spamminess of messages. I have lots of ideas for possible analysis of data, but first I want usable data.

News URI handling

2011-01-17T14:11:00.001-05:00

I have built a version of Thunderbird that should fix news URI handling issues, obtainable from this site. This is a patch queue based off of trunk just after the 3.3a2 release branch, so it should have all of the features of 3.3a2 if not the version number.

In particular, both news and nntp links of any type should work, including news URIs without a server. If any of those links do not work, please tell me, including the circumstances in which they didn't work (e.g., where did you click it, was TB open, were you subscribed to the group or not, etc.). Also, there is a chance that this could regress other handling in news code or OS command line handling, so if you see such regresses, please also tell me.

Thanks in advance for your testing!

The Great Codec War

2011-01-15T20:17:00.004-05:00

At the Second Battle of Chrome, WebM seems to have struck a surprise victory against H.264, when Google announced that it was dropping support for H.264 in <video>. Well, maybe it was only a pyrrhic victory. Reactions seem to differ a lot, but I think a lot of them miss the mark.

I've seen some people (I'm looking at you, Ars) claim that this will help kill HTML 5 video. This claim seems to me to be bogus: HTML 5 video effectively died years ago when no one could agree on a codec. Of the several video sites I use, the only one to support HTML 5 is YouTube; everyone else uses Flash. Since it's already dead, you can hardly kill it by switching codecs. This just shifts the balance more in favor of WebM. And as for H.264 working nearly everywhere, AppleInsider, your chart is just Blatant Lies.

Another thing that people do is compare video codecs to image codecs, most particularly GIF. But H.264 is not GIF: GIF became wildly popular before Unisys seemed to realize that it violated LZW. It is also unclear, looking back a decade after the fact, if Unisys targeted only encoders or both (lzw.info implies both, but Mozilla had GIF code long before the patent expired, and I don't see any information about LZW licensing). H.264, however, clearly mentions licensing for the decoder. Furthermore, it was relatively easy to make a high-quality image codec that doesn't require stepping on patents (which we now call PNG); the video codec market is much more strangled to make that impossible.

While on the topic, I've also seen a few statements that point out that H.264 is an ISO standard and WebM is not. Since people love to make the comparison between H.264 and GIF, I will point out that GIF is not an ISO standard nor an RFC, ITU, W3C, or IEEE document (although the W3C does have a copy of it on their website, it appears to not be accessible from their website by internal links). The commentary about "open standards" typically means "I can implement it by reading this/these specification(s) without paying a fee to anybody", not "there exists an officially-approved, freely-available standard" (incidentally, ISO standards generally are NOT freely-available).

But what about Flash, most people say, both on the issue of support for H.264 (although it will be supporting WebM as well) as well as the fallacy of open support. The answer to that is two simple words: "Legacy content." Flash works for everybody but a few prissy control freaks, and so much stuff—more than just video, in fact—uses it that not supporting it is impractical. Remember, half the web's users do not have HTML 5-capable browsers.

All of that said, where things go in the future is very much an open question. I see several possible directions:

The U.S. declares software patents invalid. Mr. O'Callahan can tell you one scenario that could cause this. It's actually not implausible: the Supreme Court in Bilski seemed mildly skeptical of expansive patentability claims, and a relatively clean software patent claims would probably allow them to make a coherent "narrow" ruling on software patents in general. And, though the U.S. is not the world, an anti-software patent U.S. ruling would probably lead to nullification of software patents worldwide.
MPEG-LA changes their minds and allows royalty-free decoding (not encoding) of H.264. This solution is fairly implausible, unless MPEG-LA desperately decides to try this gambit to stop H.264 from becoming obsolete. The circumstances which would lead them to do this would probably be on the back of a steep descent in H.264 popularity, so the actual value of this outcome would be minor.
Apple caves in and allows either Flash or WebM on iOS. With alternative browsers on mobile allowing these options, that means only about 17% of the mobile market has no support for video other than H.264. Depending on the success of other OSs, this may force Apple to support one of the two alternatives to allow video to work on iOS. I don't know how plausible this is, but seeing as how Android is both newer than iOS and more popular, a long-term decline in Apple's fortunes is not unreasonable.
The world continues as it does today, with no single solution supporting everybody. Not ideal, but it is the path of least resistance. Unfortunately, it's also probably the most likely.

Developing new account types, Part 4: Displaying messages

2011-01-10T18:44:00.003-05:00

This series of blog posts discusses the creation of a new account type implemented in JavaScript. Over the course of these blogs, I use the development of my Web Forums extension to explain the necessary actions in creating new account types.

In the previous blog post, I showed how to implement the folder update. Our next step is to display the messages themselves. As of this posting, I will refer less frequently to my JSExtended-based framework (Kent James's SkinkGlue is a less powerful variant; a final version will likely be a hybrid of the two technologies)—it will be slowly phased out over the rest of these series of blog posts.

URLs and pseudo-URLs

As mentioned earlier, messages have several representations. Earlier, we used the message key and the message header as our representations; now, we will be using two more forms: message URIs and necko URLs [1]. The message URI is more or less a serialization of the folder and key unique identifier. It does not have any further property of a "regular" URL (hence the title); most importantly, it is not (necessarily) something that can be run with necko. To convert them to necko URLs, you need to use the message service.

Because message URIs require an extra step to convert to necko URLs, most of the message service uses the message URI instead of the URL (anytime you see a raw string or a variable named messageURI, or (most of the time) URI, it is this pseudo-URL that is being referred to). Displaying messages involves a call to the aptly-named DisplayMessage. Unfortunately, it's also not quite so aptly-named in that it can also effectively mean "fetch the contents of this message to a stream," but I will discuss this later.

This is where the bad news starts. First off, mailnews is a bit lazy when it comes to out parameters. Technically, XPCOM requires that you pass in pointers to all outparams to receive the values; a lot of the calls to DisplayMessage don't pass this value because they ignore it anyways. Second, one of the key calls needed in DisplayMessage turns out to be a [noscript] method on an internal Gecko object. What this means is you can't actually implement the message service in JavaScript.

There is good news, however. Many of the methods in nsIMsgMessageService are actually variants of "fetch the contents of this message"; indeed, the standard implementations typically funnel the methods to a FetchMessage. My solution is to reduce all of this to a single method that you have to implement, and you get your choice of two ways to run it. Owing to implementation design artifacts, I've done it both ways and can show it to you.

Body channel

The first way is to stream the body as a channel. This is probably not the preferred method. Telling us that you did this is simple:

wfService.prototype = {
  getMessageContents: function (aMsgHdr, aMsgWindow, aCallback) {
    let task = new LoadMessageTask(aMsgHdr);
    aCallback.deliverMessageBodyAsChannel(task, "text/html");
  }
};

Seriously, that's the full code to say that you have a channel. The channel itself implements nsIChannel, but we only use very few methods: asyncOpen (we never synchronously open), isPending, cancel, suspend, and resume. The primary purpose of the channel is just to funnel the input stream of the body (not the message headers; those will be written based on the message header). The channel implementation is moderately simple:

function LoadMessageTask(hdr) {
  this._hdr = hdr;
  this._uri = hdr.folder.getUriForMsg(hdr);
  this._server = hdr.folder.server;
}
LoadMessageTask.prototype = {
  runTask: function (protocol) {
    this._listener.onStartRequest(this, this._channelCtxt);
    this._pipe = Cc["@mozilla.org/pipe;1"].createInstance(Ci.nsIPipe);
    this._pipe.init(false, false, 4096, 0, null);
    /* load url */
  },
  onUrlLoaded: function (document) {
    let body = /* body */;
    this._pipe.outputStream.write(body, body.length);
    this._listener.onDataAvailable(this, this._channelCtxt,
      this._pipe.inputStream, 0, this._pipe.inputStream.available());
  },
  onTaskCompleted: function (protocol) {
  this._listener.onStopRequest(this, this._channelCtxt, Cr.NS_OK);
  },
  QueryInterface: XPCOMUtils.generateQI([Ci.nsIChannel, Ci.nsIRequest]),
  asyncOpen: function (listener, context) {
    if (this._listener)
      throw Cr.NS_ERROR_ALREADY_OPENED;
    this._listener = listener;
    this._channelCtxt = context;

    // Fire off the task!
    this._server.wrappedJSObject.runTask(this);
  }
};

There are some things to note. First, this code can synchronously callback onStartRequest from runTask, which is a necko no-no. However, our magic glue channel gracefully handles this (by posting the call to asyncOpen in another event). Loading the input stream is done with a pipe here, and I'm doing a quick-and-easy implementation that does not take into account potential internationalization issues. I also haven't bothered to implement the other methods I should here, mostly because this code is primarily an artifact of an earlier approach, whose only purpose now is demonstrating channel-based loading.

Body input streams

The second method of implementation is just to give us the message body as an input stream:

getMessageContents: function (aMsgHdr, aMsgWindow, aCallback) {
  let pipe = Cc["@mozilla.org/pipe;1"].createInstance(Ci.nsIPipe);
  pipe.init(false, false, 4096, 0, null);
  aCallback.deliverMessageBodyAsStream(pipe.inputStream, "text/html");
  aMsgHdr.folder.server.wrappedJSObject.runTask(
    new LoadMessageTask(aMsgHdr, pipe.outputStream));
}

function LoadMessageTask(hdr, outstream) {
  this._hdr = hdr;
  this._outputStream = outstream;
}
LoadMessageTask.prototype = {
  runTask: function (protocol) {
    protocol.loadUrl(/* url */, protocol._oneShot);
  },
  onUrlLoaded: function (document) {
    let body = /* body */;
    this._outputStream.write(body, body.length);
  },
  onTaskCompleted: function (protocol) {
    this._outputStream.close();
  }
};

Here, the basic appraoch is still the same: we open up a pipe, stuff our body in one end and give the other end to the stream code. However, we don't need to do the other work that comes with loading the URI, which streamlines the code greatly. We can also pass in to the callback method an underlying request that will take care of network load stopping, etc., for us if we so choose, but the argument is optional.

More implementation

Naturally, you have to add some more contract implementations to get all of the services to work right. The following is a sample of my chrome.manifest as it stands:

component {207a7d55-ec83-4181-a8e7-c0b3128db70b} components/wfFolder.js
component {6387e3a1-72d4-464a-b6b0-8bc817d2bbbc} components/wfServer.js
component {74347a0c-6ccf-4b7a-a429-edd208288c55} components/wfService.js
contract @mozilla.org/nsMsgDatabase/msgDB-webforum {e8b6b6ca-cc12-46c7-9a2c-a0855c311e07}
contract @mozilla.org/rdf/resource-factory;1?name=webforum {207a7d55-ec83-4181-a8e7-c0b3128db70b}
contract @mozilla.org/messenger/server;1?type=webforum {6387e3a1-72d4-464a-b6b0-8bc817d2bbbc}
contract @mozilla.org/messenger/protocol/info;1?type=webforum {74347a0c-6ccf-4b7a-a429-edd208288c55}
contract @mozilla.org/messenger/backend;1?type=webforum {74347a0c-6ccf-4b7a-a429-edd208288c55}
contract @mozilla.org/messenger/messageservice;1?type=webforum-message {7e3d2918-d073-4c98-9ec7-f419a05c29de}

The first and last CIDs, as you'll notice, were not implemented by me (well, kind of). The first is the CID of nsMsgDatabase that I've exposed in one of my comm-central patches; the latter is the CID of my extension message service implementation. Also of importance is that I included a second contract-ID for my service implementation, this is for my new interface msgIAccountBackend, which is the source of the getMessageContents method I implemented earlier, and which you also need to implement to get it to work.

Finally, you need to generate the message URI properly. Fortunately, this just requires you to implement one method:

wfFolder.prototype = {
  get baseMessageURI() {
    if (!this._inner["#mBaseMessageURI"])
      this._inner["#mBaseMessageURI"] = "webforum-message" +
        this._inner["#mURI"].substring("webforum".length);
    return this._inner["#mBaseMessageURI"];
  }
};

Under the hood

For those who wish to know more about is actually going on, I am going to describe the full loading process, from the moment you click on the header to the time you see the output.

Clicking on the header (after some Gecko code that I'll elide) leads you to nsMsgDBView::SelectionChanged. This code is kicked back to the front-end via nsIMsgWindow::commandUpdater's summarizeSelection method. For Thunderbird, this is the method that handles clearing some updates and also decides whether or not to show the message summary (which is "yes if there is a collapsed thread, this pref is set, and this is not a news folder" [2]). Summarization is a topic I'll handle later.

In the case of a regular message, the result of the loading is to display the message. The message URI is constructed, and then passed to nsMessenger::OpenURL, which calls either nsIMsgMessageService::DisplayMessage or nsIWebNavigation::LoadURI, depending on whether or not it can find the message service. The message service converts its URI to the necko URL and then passes that—since it's passed in with the docshell as a consumer—to LoadURI with slightly different flags. And thus begins the real message loading.

Loading URLs by the docshell is somewhat complicated, but it boils down to creating the channel, opening it via AsyncOpen. When the channel is opened (OnStartRequest is called), it tries to find someone who can display it, based on the content type. It turns out that there is a display handler in the core mailnews code that can display message/rfc822 messages, which it does by converting the text into text/html (via libmime) and using the standard HTML display widget. I'm going to largely treat libmime as a black box; it processes text as OnDataAvailable is called and spits out HTML via a mixture of OnDataAvailable and callbacks via the channel's url's header sink, or the channel's url's message window's header sink.

The special extension message service implementation goes a few steps further. By managing the display and channel code itself, it allows new implementors to not worry so much about some of the particular requirements during the loading process. Its AsyncOpen method is guaranteed to not run OnStartRequest synchronously, and also properly manages the load groups and content type manipulation. Furthermore, the channel manually synthesizes the full RFC 822 envelope (the code inspired by some compose code), and ensures that the nsIStreamListener methods are called with the proper request parameter (the original loaded channel must be the request passed).

Alternative implementation

It is still possible to do this without using the helper implementation. In that case, there are alternatives. The first thing to do is to implement the network handler, for which you'll definitely need a protocol implementation, and probably a channel and url as well. A url that does not implement nsIMsgMailNewsUrl and nsIMsgMessageUrl is likely to run into problems with some parts of the code. You can possibly get by without a message service for now, but I suspect it is necessary for some other portions of the code. To get the message header display right, you need a message/rfc822 content-type (which gets changed to text/html, so it has to be settable!).

A possible alternate implementation would be to send a straight text/html channel for the body and then manually call the methods on the header sink, i.e., bypass libmime altogether. A word of caution about this approach is that libmime can output different things based on the query parameters in the URL, and I don't know which of those outputs are used or not.

Next steps

Now that we have message display working, we pretty much have a working implementation of the process of getting new messages and displaying them. There are several ways I can go from here, but for now, I'll make part 5 deal with the account manager. Other parts that I am planning to do soon include dealing with subscription, filters, and other such code.

Notes

If you are not aware, "necko" refers to the networking portion of the Mozilla codebase. The terms "URI" and "URL" also have standard meanings, but for the purposes of this guide, they mean different things. I will try to keep them distinct, but I have a tendency to naturally prefer "URI" most of the time, so I may slip up.
Unfortunately, a lot of the front-end code has taken it upon itself to hardcode checks for certain implementations to enable/disable features. Hopefully, as Kent James and I progress on this work, these barriers can be reduced.

Random code coverage statistics

2011-01-07T23:45:00.003-05:00

Test coverage happened to come up in an IRC channel I frequent today, so I thought up some probably useless statistics on code coverage, and applied them to Thunderbird.

Since I lost the original lcov files, I reculled them from the output HTML data. Of the 112,024, only 65,012 were actually run (which matches the summary output, so I'm good). It turns out that, in total, there was a whopping 168,563,629 line executions in the test, or an average of 1,504.89 hits per line. If we only count among the lines that were hit, the average number of times run is 2,592.81.

Given the general paucity of tests in comm-central, why is this number so high? Well, it turns out that some functions in libmime run a lot. The most was mimebuf.cpp's line 215, which ran no fewer than 3,223,519 times, followed closely by line 224 at the still-impressive count of 3,222,934. The most outside of libmime (which swept the top 5) was nsMsgLineBuffer.cpp's lines 140-150, at the count of 1,828,695. I think we can safely say that those lines are well-covered.

The numbers for functions seem similarly skewed: 10,951 functions, 6,443 of them actually run. Between these, there were a total of 26,588,690 function calls, or 2,427.96 or 4,126.76 calls per function (depending on your count). And these high-flying functions are both in libmime, com18n.cpp, to be specific: NextChar_UTF8 and utf8_nextchar, with 1,782,545 calls each. Outside of libmime (who again sweeps the top 5) is nsMsgFolderCache::GetEnv, with a total of 450,400 function calls. I think we can safely say that said function is bug-free.

Predicted 2011 Mozilla work

2011-01-05T16:01:00.004-05:00

Another year, another time to predict what work I want to get to this year. And, of course, another chance to fail to do that work.

News submodule

This year, I am going to give myself a goal of bringing the total number of open bugs in the MailNews Core: Networking: NNTP component to below 100, or, at the very least, below 104 to make it the least buggy of the mailnews core protocol implementations. I've laid out for myself a map of all bugs in the component, so I know what needs to be worked on. My current work on news URIs by itself should get me almost there: I have patches awaiting review that fix bugs 37465, 108297, 226890, 403242, 498321, and 617287, as well as patches in my queue that fix bugs 108970, 110841, and 224335, with patches for bugs 80972, 108107, 108877, 133793, 167991, 327885, 411568, and 530193 likely to come. In other words, that's supporting no-authority news URLs.

Outside of that, I can easily pick up a few small bugs along the way to get that number down. What's likely not going to be fixed by me is venerable bug 43278, or any expired article issues&mdsash;in other words, any set of bugs that would require as much effort as the no-authority bug. I'm not quite leaving out the authentication-related bugs, but those are in the unlikelier side of the "maybe" pile.

Code coverage

My attempts to get decent JavaScript code coverage appear to have been thwarted once again (though I'm not giving up hope). If a few tweaks don't get my current approach working, I'll probably return to a simpler instrumentation-based approach (blech). I would still like to see at least the C++ code coverage analysis be run on a more regular basis now (at least weekly) so we can get a good timeline of code coverage through the ages. Building versions of mozilla a year in retrospect is not fun, especially given the annoyance of mozmill versioning.

Unfinished things

Once I get no-authority news URIs in the tree, I would like to return to new account types. Actually, the work I did has proven to be very helpful in removing the next road block (since I got intimate knowledge of how URIs are actually run behind the scenes as well as how necko works with the URIs). On the downside, my attempts to get JS to extend C++ classes appear to be getting less stable the more I work with them, so I'll probably abandon that approach and instead turn to another approach: writing an extension layer that makes it simpler to implement all of the functionality without having to get down-and-dirty. I feel justifying in saying that the less you look like an email server, the more you'll be happier not having to deal with the messy glue implementations.

Now, that said, I may still continue working in the vein of the blog posts, since it is still a nice documentation of how things go on just below the hood. In any case, the two things I most want to hide in the implementation are the database and the URL, half of which has already been discussed.

Some people have asked that I continue my guides to pork. However, I have become more persuaded that the current mime implementation needs to be tossed away and restarted from scratch, which reduces my primary motivation for learning it. Furthermore, pork (at least as built in elsa) is pretty much considered abandoned, although there are intentions to rebuild the tool on clang, now that it has a decent C++ parser.

I have been told by Mark Banner that he intends to get a new roadmap for the address book up in the near future. To the extent that it does not conflict with other goals I have, I will probably do some implementation under that. I may also decide to attempt again to work on address book integration with Linux desktops, given some experience I've had over the past year.

Updated code coverage

2010-10-16T10:26:00.002-04:00

It's been about seven months since I last ran code coverage tools on Thunderbird, so I thought I would do it again. In these intervening seven months, Thunderbird has moved to libxul, and the mozmill tests have become more important, which means I get to change my methodology slightly.

Problematic caveats first, then. For various reasons, my build for code-coverage results runs on a 64-bit machine which I have to ssh to get to and on which I lack administrative privileges. Previously, the build setup caused gcov to fail to work properly for the mozilla-central code, causing my build scripts to require hacks to only cover the comm-central code. It seems that something in either the environment, the code, or the building of libxul caused it to be fixed.

On the other hand, the environment prevented me from running the mozmill tests correctly. On this computer, the user accounts are set up via LDAP, so the gtk initialization code tried to get user information from libc, which got it from NSS, which got it from LDAP, which tried to get it from another LDAP library. Unfortunately, it chose to use the directory/c-sdk ldap instead of the system ldap causing a crash. The only solution was to disable ldap, which required a few tricks to work correctly. Oh, and somehow the tests failed if I didn't enable libxul.

My last issue was with mozmill. I had a plan to use Xvfb for the display for mozmill (the intent being that I could automate mozmill tests on several computers overnight via screen). Turns out that it someone complained about needing Xrandr, so I got to run all of the mozmill tests via twice-forwarded X connections.

Anyways, the results are in. These are the results before mozmill tests were run, and these are the results including mozmill tests. By comparison, these are the results from my last run (which do not include mozmill tests). For completeness sake, 41 xpcshell-tests failed and 10 mozmill tests failed. I do not have the record of which ones failed, however.

Finally, here is the HD view of the code-coverage treemap results:

By comparison, the old code-coverage treemap results:

I hope you enjoy the results!

Usage share of newsreaders

2010-09-04T20:08:00.003-04:00

I have noted before, by a nonscientific and utterly biased survey, that Thunderbird appeared to account for a significant share of the newsreader market (testing bug 16913 was what caused me to discover this fact). But actually finding any attempts to measure usage share of newsreaders via Google has actually been rather frustrating. You can easily find market shares of web browsers, desktop operating systems, server operating systems (though the numbers vary wildly?), and mobile platforms. But not things like email client shares or newsreader shares.

Okay, I am not about to find market shares of email clients. I have no access to anywhere near enough a representative sample that could work. But collecting newsreader market shares should not be that hard. After all, pretty much anyone can pick up a large, representative sample of news postings... connect to a NNTP server of your choice. So, seeing as how it's a three-day weekend, I thought I might as well collect the data myself. The other reason for my collecting this data was to demonstrate that a significant number of Thunderbird users are NNTP, so removing NNTP support would adversely affect the userbase.

Methodology

First off, I have to define what I mean by "usage share." Unlike other mediums, a relatively small numbers of users account for a relatively large share of NNTP postings. I've decided to measure it by the number of posts generated by each NNTP client, since it's easier to calculate, and I think it is more informative than the measuring by individual users.

I also have to pick the subset to log. For this set of data, I collected every single news article in the Big-8 newsgroups on my school's NNTP server (news.gatech.edu), which has a retention time of a month (30 days is the exact number, I think). I did not even attempt to filter out spam messages, and I did not account for cross-posting (my script managed to crash due to races a few times, so the totalized data which accounted for cross-posting was unreported).

Essentially, this is what I did. I ran a python which collected every group in the big 8 (determined by LIST ACTIVE wildmats) on the server. Then, it entered every group, performed an XOVER to find all messages, and then XHDR'd User-Agent, X-Mailer, and X-Newsreader to figure out what the user agent was. This script output, for every group, a total for each full string that represented the UA into a ~2MB csv file.

I collected all of the csv data into OpenOffice.org Calc and then ran a macro which attempted to collect the program number and the version from the UA strings. Unsurprisingly, I had to do some hacks to get it to recognize SeaMonkey and Thunderbird correctly (Mnenhy was not helping). I output tables that broke readers down by versions and by total program counts.

Results

It turns out that there is an incredibly long tail of newsreaders. There are about 250 different UA strings I found. Excluding one particularly prevalent bot and those postings for which I could not find a UA string, I found around 430,000 messages (there may be some other things dropped by copy-paste errors). Of these, the top 5 newsreaders account for just 79% of the total count. By contrast, the top 5 web browsers account for very nearly 100% of the total. Some interesting newsreaders I found in the long tail:

Mozilla 4.8 [en] (Windows NT 5.0; U)
Mozilla 3.04 (WinNT; U)
trn 4.0-test70 (17 January 1999)
Lynx/2.8.5rel.1 libwww-FM/2.14 SSL-MM/1.4.1 GNUTLS/0.8.12
MyBB

Finally, here is the table of the top newsreaders:

Newsreader	Total	Percent
Google Groups	189536	43.94%
Thunderbird	52258	12.11%
Forte Agent	47100	10.92%
Microsoft Outlook Express	41042	9.51%
Microsoft Windows Live Mail	11196	2.60%
MT-NewsWatcher	10872	2.52%
Other	79359	18.40%

That Google Groups has the highest market share is not surprising, but I was surprised by the strong showing of Forte Agent and the poor showing of traditional newsreaders (e.g., tin, rn-based newsreaders). I guess this goes to show you that Windows has a surprisingly large market share in the Big 8 newsgroups. For SeaMonkey enthusiasts, your newsreader has a mere 4,187 postings (with another ~5K provided by other Mozilla distributions, some of whom cannot be determined... Mnenhy made processing UA strings difficult).

In terms of individual versions, one of Outlook Express's versions clocks in #1 at 31,617 total posts, with Thunderbird 3.1.2 trailing at a "mere" 23,661. Thunderbird has around 14,000 on the 2.x branch, 11,000 on the 3.0.x branch, and 25,000 on the 3.1.x branch. There is apparently some spoofing going on for SeaMonkey users as well (I found a dozen or so Firefox entries, which I presumed is a SeaMonkey-spoofed UA string).

Another datum incidentally collected was the number of postings in each hierarchy. Here they are:

Hierarchy	Count	Largest Newsgroup
comp.*	64,360	comp.soft-sys.matlab (8,399)
humanities.*	2,460	humanities.lit.authors.shakespeare (1,455)
misc.*	28,518	misc.test (8,796)
news.*	31,635	news.list.filters (26,238)
rec.*	217,548	rec.games.pinball (14,707)
sci.*	47,948	sci.electronics.design (6,076)
soc.*	87,192	soc.retirement (6,053)
talk.*	12,513	talk.origins (6,498)

Remind me again why we have the humanities hierarchy? Almost 60% of its messages come from a single newsgroup, and it has just 8 newsgroups.

Future Work

What could be done in the future is to expand this research into binary newsgroups. However, merely counting posts becomes a more inappropriate metric because binary newsgroups use a lot of multipart messages, so just because someone uploads a ginormous binary does not mean it should be counted 50 times. I also don't have access to any binary newsservers.

Another opportunity for fixing is to discount spam. As a brief test, I looked into only those newsgroups which had the name `moderated'--this resulted in a paltry sample of 3,272 messages. The statistics also appear to not change much, but the newsgroups are likely not a representative sample of the Big 8 anyways.

Finally, this needs to be broadened and run repeatedly so it can collect snapshots of the data across time. This metric suffers poorly at capturing historical data, but it could be an excellent way to get data every few months from the future, so long as someone collects all of the data in the future.

Developing new account types, Part 3: Updating folders (part 3)

2010-06-07T18:30:00.004-04:00

This blog post is a continuation of my previous two posts, which is being broken up into multiple segments to lower the amount of text one has to read in a single sitting. The current step is to actually implement the folder update.

Only new messages

Now that we know how to add messages to the database, we need to figure out how to find the downloaded messages.

It should go without saying that checking to see if you actually need to update the folder should be the first thing you probably want to do in this function. In my extension, I need to download the front page of the specific board and check the topic list to see if it matches what is stored in the database.

For now, at least, I can rely on the forum telling me about the number of replies in a thread (one less than the number of total messages), as this is shown in the thread index of a forum. What I do is grab the reply count that I've seen and subtract that from the number that is listed to get the number of new messages I need to download. Then I need only to look at the last few messages to add them to the database.

At this point, I have two main issues to worry about. First, I am working with paginated return results. That means I actually need to load multiple documents. Second, I am not getting a list of messages, but a list of threads; therefore, I need a database that is associated with threads [8].

The database I use is a simple JSON object that exists for each folder, and so far only has a mapping of threads to the reply count that I've seen; I may give it more in later iterations of this extension.

Pagination is where the trickery in implementation comes in. First, I need to look at the thread index for new messages; if I have seen all of the messages in the last thread, I can stop looking at new pages. Otherwise, I have to grab the next page and continue recursing. Note that it is possible to hit a thread that I've fully seen and still have threads I've not seen: sticky messages can be infrequently updated yet still make it first on my list of messages.

The other issue is when loading threads. The link I end up scraping is to the first page of messages for that thread, which I may already have seen. So I need to skip over pages until I find the page that first has new messages. For now, I'm doing this naïvely by actually loading each page and counting the number of posts rather than trying to deconstruct URLs and calculating where to load. I then need to look at the last set of posts, not the first set, so I calculate the start position and read forwards. Since I'm using querySelectorAll, I get an array of results, so I don't worry about having to throw out a number of iterations; I can just start in the middle when iterating.

Once all of that is implemented, we can then put everything together to make a proper implementation of updateFolder, the function we started implementing a few pages ago. The end result is that, when all is said and done, you can load up the message pane (the last column is the number of messages in the thread):

By comparison, here is an equivalent view of the forum that I loaded this from:

Now, I wish to ask you, which user interface would you rather use to view the forum?

Some notes for implementors: be prepared to delete your msf files over and over again. I would recommend tackling the individual components in this order: first build a message, then your protocol object (I found it easier to test when the running tasks were already known to be working), and then start work on tying it all into the database. Leave issues like threading for after the basic stuff is laid out, then tackle determining which messages are new if it's not implicit in what you do (i.e., you don't have a "get new messages" query you can readily use). Pagination should be last: everything is easier to test if you only have a small number of messages you really need to test.

I apologize for the excessive length of this step; this happened to be pretty much the first step where most of the necessary technology had to be used. The next step is to actually be able to display the messages in our database, which should be shorter.

Notes

Kent James and I are both working on developing new account type extensions (he doing an Exchange connector and I this blog series); both of us have identified the narrow-mindedness of the database as an issue. It is therefore possible that my workaround here will not be necessary in the next few versions.

Developing new account types, Part 3: Updating folders (part 2)

2010-05-21T17:32:00.003-04:00

This blog post is a continuation of my previous post, which is being broken up into multiple segments to lower the amount of text one has to read in a single sitting. The current step is to actually implement the folder update.

Folder updating

To actually achieve our goal of getting a correct message list, we are going to modify the implementation of updateFolder. This function is called whenever a folder is selected in the folder pane; conceptually, you can view the function as causing the cached database to be resynchronized with the actual folder. For example, this is where a local folder would actually reparse the mailbox if the database was incorrect or missing.

This function essentially consists of three steps: figure out new messages, process them (i.e., apply filters), and then announce to the world that they exist. Some account types (like IMAP) may need to do more involved message processing, but this is the general gist of what goes on [4]. I'll ignore the processing step until I start talking about filters.

Database Details Devil

To start with, I'll cover the last step. Announcing to the world that a message exist boils down to adding a new header to the database. So how do you add a new header to the database? It requires three easy steps: create the header, populate the fields, and then add it to the database. With the proper listener setup, all of the other notification is done for you automatically. But as they say, the devil is in the details.

Let me begin by explaining some things about messages. There are five different representations of the message: the message key, the message header, the message ID, the message URI, and the necko URL object. Siddharth Agarwal has a nice diagram that shows how to convert between these representations. The last two are more concerned with displaying messages; it is the first three that are interesting right now.

Message keys are the internal database key for a message; the tuple (folder, key) is guaranteed to be unique by the database. Message keys are unsigned 32-bit integers (with 0xFFFFFFFF, or -1 in 2's complement, reserved as the "no message here" key). In general, any time a property needs to refer to another message, the message key is used; as a consequence, it means that such properties cannot refer to stuff across folders.

Message IDs are the RFC 5322 identifier for a message. These identifiers are supposed to be unique (for logical messages, not in a "the message at offset 0x234f3d in this file" sense). The most important use case for message IDs is that they are a critical component for threading.

The message header object is an object of type nsIMsgDBHdr. These are objects are directly backed by the database. However, many of the properties do not notify the database of changes, so you generally do not want to actually set them. Like all generalities [5], there are exceptions to this rule. Right now, we want to manipulate headers before adding them to database, and therefore we do not want to notify people of changes to not-yet-existing headers, so we want to actually use the fields of nsIMsgDBHdr.

So, the first thing you need to do is to decide what your message key is. Message keys are going to be used to get the message URI, so it should be a property that is easy to associate with methods. IMAP uses message UIDS, local folders the offset into the mbox [6], and NNTP uses the key numbers in the group. In my case, it appears that the forum assigns each post a unique number, so that is what I'll use.

After the message key, the most important properties are the major ones for display. The author attribute correlates to the "From" header, subject to the "Subject" header, and date to the "Date" header. All of these will be used to generate values in the thread pane columns; things would look strange without these.

The other major property in the display is flags. Flags, as the name implies, is an integer where each bit corresponds to a different flag. The most important of these are probably HasRe, Flagged, and New. Flags should be set with OrFlags and AndFlags instead of manipulating the value directly. And don't set these values with the mark* methods, as these cause notifications to be fired (remember that we haven't added the message to the database yet).

If you want to do real threading, you will want to set message IDs and references [7]. The References header is a space-separated list of message ID tokens (wrapped in angle brackets), although the parser routine in the database does a pretty good job of ignoring any random crap. The list is in the reverse order of hierarchy, so the last element is the message's parent, second-to-last the grandparent, etc.

Threading is implemented in the following manner. First, the database attempts to find a message for each message ID in reverse order. If it finds one, that is made the parent header and threading stops. Otherwise, if correct threading is enabled, an attempt is to made to find a thread which has that message ID. Otherwise, if use strict threading is not enabled, a thread that has a message which has the same subject (without Re) is used as the thread. If threading without re is disabled, the message has to have the HasRe flag checked to perform the last step. Finally, if a thread could not be found by this point, a new one is created.

To combine messages in a thread, then, the References field needs to be set for the messages. If people enable correct threading (this is done by default), you can use a simple trick: create a valid message ID for each thread and stuff that as the References header.

A practical example

In my case, I have an author (without email addresses), a subject (with possible non-ASCII text but without Re: stuff), a date in a standard format, as well as a simple per-thread unique identifier for message keys. I also want to make threads—although this will only be two-level threads. Ideally, I should also be flagging the sticky threads, but I'll leave that for a later version. So what does this code look like?

_loadThread: function (document, firstMsgId) {
  let database = this._folder.getDatabase();
  let conv = Cc['@mozilla.org/messenger/mimeconverter;1']
               .getService(Ci.nsIMimeConverter);
  let subject = /* one for the thread */
  let hostname = this._folder.server.hostName;
  let charset = document.characterSet;
  /* for each new message */ {
    let postID = /* generate msg key */;
    let author = /* get author name */;
    let date = new Date(/* get text string*/);
    let msgHdr = database.CreateNewHdr(postID);
    // The | is to prevent accidental message delivery
    msgHdr.author = conv.encodeMimePartIIStr_UTF8(
      author + " <" + author + "@" + hostname + "|>", true, charset, 0, 72);
    msgHdr.subject = conv.encodeMimePartIIStr_UTF8(subject, false, charset,
      0, 72);
    // PRTime is in µs, JS date in ms
    msgHdr.date = date * 1000;
    msgHdr.Charset = charset;
    msgHdr.messageId = postID + "@" + document.documentURI;
    if (firstMsgId) {
      msgHdr.setReferences("<" + firstMsgId + ">");
      msgHdr.OrFlags(Ci.nsMsgMessageFlags.HasRe);
    } else {
      firstMsgId = msgHdr.messageId;
   }
   msgHdr.OrFlags(Ci.nsMsgMessageFlags.New);
   database.AddNewHdrToDB(msgHdr, true);
  }
}

First, we get a reference to the database. Remember we implemented this in our last step, so this shouldn't present any problems. We also get the things that are shared in this thread: the subject, hostname of the server, and the charset. For each of the posts, we collect the post ID, the author, and the date of the post as text strings, and then convert them into an integer, string, and a date respectively.

Using the CreateNewHdr function, we get a new message header that we can manipulate. Since I'm trying to be aware of non-ASCII text, I'm using the MIME encoding strings to prepare the author and subject. Remember that the MIME specifications want you to encode non-ASCII text in the headers; the function we use is the simplest way to do the encoding.

If you're not working with actual email, the from string can be contorted. What I did was to create a fictituous email that could be theoretically tied back to the author in a systematic way (for a possible future compose code that does forum private messaging). The purpose of the pipe character at the end is to prevent accidental mail delivery; I also used the hostName and not the realHostName, so this email address would be traceable even if the user changes the host name on me.

The message date I have is a formatted string; the Date constructor is pretty handy at converting most forms of these strings into a usable JS Date object. Then I have a JS Date object, which is measured in milliseconds, whereas the date attribute is a PRTime, which is measured in microseconds, so I need to multiply by 1000 to actually set the property. Ironically, the date is actually stored in seconds in database and is converted to and from microseconds on the fly.

The Charset attribute, apparently only used for search right now, is derived from the character set as reported by the DOM. This means that it is the same character set as would be assumed by the layout engine, including character set overrides.

The message ID is simpler to generate: valid URIs are pretty much valid right-hand-sides of a message ID. A post is pretty much representable as a tuple of the thread page and the path to the post in the DOM, so this message ID is also an easy way to get to the message. References are also generated as I described above; in a later version, I may try to do sniffing to figure out from quoting who is replying to whom and recreate actual threads. Note that when setting the message ID, the outer angle brackets are optional.

The last thing I set is the flags. A complete listing of flags can be found on MDC. In this case, the only flags I care about are HasRe (since I want to generate "Re:" headers) and New; most of the others will probably be set by the user in the UI.

Finally, we add the header to the database. The last parameter tells the database to tell anyone listening that we have a new message. After we have loaded all of the messages, we need to commit the database:

database.Commit(Ci.nsMsgDBCommitType.kLargeCommit);

A brief note to make here: it doesn't really matter if you do a large or session commit, they both end up doing the same thing. Small commits end up doing nothing.

Notes

Like most synchronization stuff, you theoretically also have to deal with deletion on the remote side as well as read changes, etc. The more I think about it, the more I'm torn on whether or not I should implement it. For now, I'll recommend that you weigh the cost of trying to determine deleted messages versus the commonality of deletion or other modification.
Except, I am told, that all words that end in -tion in French are female.
Incidentally, this is a major part of the reason why there is a 4 GiB limit on mailbox size in Thunderbird and SeaMonkey.
What about In-Reply-To, you may ask. This information is pretty much redundant with References, so what happens is that, for the purposes of computing threading, this header is appended to the References header. And you do this before calling on the database header.

Developing new account types, Part 3: Updating folders (part 1)

2010-05-12T10:55:00.005-04:00

In the previous blog post, I showed how to get an empty message list displayed in the folder pane. The next step is to actually implement the folder update. Since this task involves several tasks, I will be breaking this step into multiple blog posts.

Getting a DOM for HTML

In terms of webscraping, I treat the first step as simply turning a URI into a DOM. The developer center actually has some good resources on this, if you have access to a document object. The issue, though, is getting a document object, since your code will likely be running from an XPCOM component [1]. What is needed then, is a utility method for loading the DOM. This is the code I've been using:

function asyncLoadDom(uri, callback) {
  let doc = Cc['@mozilla.org/appshell/window-mediator;1']
              .getService(Ci.nsIWindowMediator)
              .getMostRecentWindow("mail:3pane").document;
  let frame = doc.createElement("iframe");
  frame.setAttribute("type", "content");
  frame.setAttribute("collapsed", "true");
  doc.documentElement.appendChild(frame);
  let ds = frame.webNavigation;
  ds.allowPlugins = ds.allowJavascript = ds.allowImages = false;
  ds.allowSubframes = false;
  ds.allowMetaRedirects = true;
  frame.addEventListener("load", function (event) {
    if (event.originalTarget.location.href == "about:blank") return;
    callback(frame.contentDocument);
    doc.documentElement.removeChild(frame);
  }, true);
  frame.contentDocument.location.href = uri;
}

The first argument is the URI to load, as a string, and the second argument is the function to be called back with the DOM document as its sole argument. An added benefit to this method is that it also uses an asynchronous callback method, so you're not blocking the UI while you wait for the page to download. This code will likely not be called except by the protocol object, though, since we probably want to throttle the number of pages loaded up at once.

The protocol object

Earlier, I mentioned that one of the implemented objects wasn't actually mandatory. This object was the protocol object. An instance of this object is meant to wrap around an actual connection to the server; where you don't need to connect to a server, this object might not be worth implementing. In reality, it is still a useful thing to have if you have a non-trivial account type—any time a task is more complicated than "load this thing and use it," a protocol object can help with managing multiple subtasks.

For a wire protocol, the implementation of this object should be straightforward. It would essentially be a state machine, with an idle state entered after setting up the connection during which the instance can accept tasks to do. A state machine could also be done for webscraping-based account types, but I am using a more queue-based approach due to how I have structured the web loads.

At a high level, server requests are chunked at two levels. On the higher level, the application makes calls to functions like updateFolder; these calls I have decided to term tasks. The lower level requests are the requests you communicate to the server; for lack of any better terminology, I will refer to these as states[2]. In my implementation, I keep two queues, one for each of these.

Managing the queue for tasks is best done at the server. The overall logic is actually rather simple:

const kMaxProtocols = 2;
wfServer.prototype = {
  /* Queued tasks to run on the next open protocol */
  _queuedTasks: [],
  _protocols: [],
  runTask: function (task) {
    if (this._protocols.length < kMaxProtocols) {
      let protocol = new wfProtocol(this);
      protocol.loadTask(task);
      this._protocols.push(protocol);
      return;
    }
    for (let i = 0; i < this._protocols.length; i++) {
      if (!this._protocols[i].isRunning) {
        this._protocols[i].loadTask(task);
        return;
      }
    }
    this._queuedTasks.push(task);
  },
  getNextTask: function (task) {
    if (this._queuedTasks.length > 0)
      return this._queuedTasks.shift();
    return null;
 },
};

The runTask method is designed to be called with a task object; for the core mailnews protocols, this is primarily being called by the service [3]. For now, I've made the value for the maximum number of protocol objects unchangeable, but it is probably better to allow this value to be configurable via a per-server preference.

The core implementation of the protocol running object for webscraping is not too difficult:

const kMaxLoads = 4;
function wfProtocol(server) {
  this._server = server;
}
wfProtocol.prototype = {
  /// Queued URLs; first kMaxLoads are the currently running
  _urls: [],
  /// The current task
  _task: null,
  /// Load the next URL; if all URLs are finished, finish the task
  onUrlLoaded: function (url) {
    if (this._urls.length > kMaxLoads)
      this._urls[kMaxLoads].runUrl();
    this._urls.shift();
    if (this._urls.length == 0)
      this.finishTask();
  },
  /**
   * Queue the next URL to load.
   * Any extra arguments will be passed to the callback method.
   * The callback is called with this protocol as the this object.
   */
  loadUrl: function (url, callback) {
    let closure = this;
    let task = new UrlRunner(url, this);
    let argcalls = [null];
    for (let i = 2; i < arguments.length; i++)
      argcalls.push(arguments[i]);
    task.onUrlLoad = function (dom) {
      argcalls[0] = dom;
      callback.apply(closure, argcalls);
    };
    this._urls.push(task);
    if (this._urls.length <= kMaxLoads)
      task.runUrl();
  },
  /// Run the task
  loadTask: function (task) {
    this._task = task;
    this._task.runTask(this);
  },
  /// Handle a completed task
  finishTask: function () {
    let task = this._server.getNextTask();
    this._task.onTaskCompleted(this);
    if (task)
      this.loadTask(task);
  }
};
/// An object that represents a URL to be run
function UrlRunner(url, protocol) {
  this._url = url;
  this._protocol = protocol;
}
UrlRunner.prototype = {
  runUrl: function () {
    let real = this;
    asyncLoadDom(this._url, function (dom) {
      real.onUrlLoad(dom);
      real._protocol.onUrlLoaded(real._url);
    });
  },
  onUrlLoad: function (dom) {}
};

The protocol is initialized by calling loadTask, which calls runTask on the task object. This would make some calls to loadUrl which will load it (since the max has not been loaded yet). When the function is loaded, via UrlRunner.runUrl, the callback function is called and then the onUrlLoaded function is called to clean up the URL from the queue and run any more. When this function detects that there are no more URLs are being loaded—hence why the callback is called before this function is—finishTask is called on the task object.

The working of loadUrl bears special mention. The first argument is the URL (as a string) to be loaded. The second argument is the method on wfProtocol to be called when the URL is loaded. This implies that the actual code for implementing tasks is mostly contained on wfProtocol as opposed to the task objects. All subsequent arguments are passed in as arguments to the callback function; the first argument to this function is the DOM document.

Notes

Well, there is an nsIDOMParser which can turn text into a DOM without needing a document object. Unfortunately, it only supports XML. There is a patch for making it parse HTML, but it has gotten no traction in recent months.
Just to muddle it all up, the URL instances in most mailnews implementations are actually how the tasks are implemented, although I internally use a URL to represent a state (kind of). A potentially clarifying discussion can be found in mozilla.dev.apps.thunderbird.
I am not totally happy with the current model of the protocol system in mailnews, particularly with the technique of crossing over to the service to make the calls to the protocol. In my implementation, I've made those functions static functions on the protocol object. Since this is somewhat different from the current implementations and I'm not sure I want to keep this, I've couched my statements of how things work.

A new folder tree view for real

2010-04-27T21:45:00.003-04:00

Seeing as how the first build candidates of Thunderbird 3.1 beta 2 are currently being spun, it is time for me to update from the 3.0 builds to 3.1 builds (I have a policy of switching to the next branch of Thunderbird as my primary at the time of the last beta). I decided to take this opportunity to work out issues in my folder categories extension for real.

I've decided to give up on supporting 3.0 (trying to support two different broken versions of code is not fun), so the oldest supported version is now listed as 3.1 beta 2. In reality, it would work with any nightly since the broken code was fixed (it's still not fully fixed now, but it's just a cosmetic issue). The result is an experimental addon on addons.mozilla.org. For those of you dying for screenshots, this page on mozdev should satiate you.

Animated code coverage

2010-04-11T07:47:00.002-04:00

I recently spent a fair amount of time collecting historical code coverage data for Thunderbird; the result is 312 distinct files of raw lcov data covering the first year of Thunderbird in a mercurial repository. I also recently wrote a program that makes a treemap for each day (thanks to the geninfo man page and this treemap library), and then wrote another program to convert that treemap into a static PNG image:

view.setSize(1920,1080);
BufferedImage image = new BufferedImage(view.getWidth(),
  view.getHeight(), BufferedImage.TYPE_INT_RGB);
view.paint(image.getGraphics());
ImageIO.write(image, "png", new File(args[1]));
System.exit(0);

I ran that tool to create images for every single day, and then I made another short script to add dates to each of the images (ImageMagick works really well here):

DATE=$(echo $1 | cut -d'.' -f1)
convert -fill "#aaa" -pointsize 50 label:"$DATE" /tmp/label.png
composite -compose Multiply -gravity southwest /tmp/label.png $1 anno-$1

Now, with 312 images on hand, I decided to make them into a video:

mencoder mf://out/anno-*.png -mf w=1920:h=1080 -ovc lavc -lavcopts vcodec=ffv1 -of avi -ofps 3 -o output.avi

I then converted the high-def, lossless AVI into an Ogg file, and produced the following animated video of historical code coverage:

Use a web browser that supports playing box Ogg videos. It's the least you could do, considering how much time converting the AVI to Ogg took!

Okay, so no sound yet for the animation—the encoding is painful enough that I don't want to try it out right now. I also didn't filter out any of the days where the tests failed early, so you will occasionally see flashes of red. The data also doesn't have recent stuff (I am holding off until I can figure out how to run mozmill tests and get JS code coverage). Anyways, enjoy!

Developing new account types, Part 2: Message lists

2010-04-04T16:23:00.005-04:00

In the previous blog post, I showed how to get an account displayed in the folder pane. Now, we will prepare the necessary components of getting an empty message list displayed in the folder pane.

Database basics

As mentioned previously, the database is one of the key components of an account. It is, essentially, the object that actually stores the state of messages in folders and even some folder attributes themselves. The database is currently backed by a mork database (the .msf files you see in your profile storage); in principle, you could make your own database from scratch that doesn't use mork, but that is likely a very bad idea. [1]

Originally, as I understand it, the database was merely a cache of the data in the actual mailbox. Its purpose was to store the data that was needed to drive the user interface to prevent having to reparse the potentially large mailbox every time you opened up Netscape. The implicit assumption here was that blowing away the database was more or less lossless. Well, times change, and now such actions are no longer lossless: pretty much any per-folder or finer-grained property is stored in the message database; in many cases, these properties are not stored elsewhere.

The database itself is represented by the nsIMsgDatabase interface. Messages and threads are represented by the nsIMsgDBHdr and nsIMsgThread interfaces, respectively. Per-folder property stores are represented by nsIDBFolderInfo. Finally, the code to open a new database comes from nsIMsgDBService. Most of the database stuff just works; subclasses would implement only a few methods to override the default ones.

Getting databases

There are two main entry points for getting databases: msgDatabase, and getDBFolderInfoAndDB. Both of these must be implemented for anything to work:

wfFolder.prototype = {
  getDatabase: function () {
    if (this._inner["#mDatabase"])
      return this._inner["#mDatabase"];
    let dbService = Cc["@mozilla.org/msgDatabase/msgDBService;1"]
                      .getService(Ci.nsIMsgDBService);
    let db;
    try {
      db = dbService.openFolderDB(this._inner, false);
    } catch (e) {
      db = dbService.createNewDB(this._inner);
    }
    this._inner["#mDatabase"] = db;
    return db;
  },
  getDBFolderInfoAndDB: function (folderInfo) {
    let db = this.getDatabase();
    folderInfo.value = db.dBFolderInfo;
    return db;
  },
};

This portion of the code can turn out to be surprisingly complicated. What is listed is generally a safe option: if the database is incorrect (out of date or non-existent), blow away the database and re-retrieve the information from other sources. Recreating the database is done in the catch statement. Then we set the member variable to be the newly-created database (this is also used by nsMsgDBFolder code) and we return it. Retrieving the folder info should be self-explanatory.

You may notice that when the database is invalid, all we do is create a new database: we don't try to fix it. This is because these calls to get the database are interested in getting a version of the database quickly: this is one of the calls the folder pane makes, and it is synchronous. Imagine what would happen if, say, a local folder which had a 3GiB backing store needed to be reparsed during this call. The actual recovery of the database would most likely happen when the folder is told to update.

Other stuff can be added to these calls. Not everything is necessarily stored in the database: news folders store their read information in the newsrc file, so it needs to sync this with the database in the method too.

Displaying an empty message list

If you just try to implement this code and run, you will discover that this is not sufficient to load the database. The key is in the getIncomingServerType function, which is what tells the database service which implementation of nsIMsgDatabase to use. For now, we can just use the default implementation of nsMsgDatabase, but we can't change the parameter output (otherwise URIs will get messed up). The solution is to create a DB proxy:

function wfDatabase() {}
wfDatabase.prototype = {
  contractID: "@mozilla.org/nsMsgDatabase/msgDB-webforum",
  _xpcom_factory: {
    createInstance: function (outer, iid) {
     if (outer)
        throw Cr.NS_ERROR_NO_AGGREGATION;
      return Cc["@mozilla.org/nsMsgDatabase/msgDB-default"].createInstance(iid);
    }
  }
};

What this does is use some XPCOM magic to link creating one contract ID to creating the other. I have not yet used the extend-C++-in-JS glue to create the ability to subclass nsMsgDatabase due to the fact that the nsIMsgDatabase interface is more complicated than the others, as well as it being more C++-specific codewise and generally less useful to override methods.

The next thing to do to display the list is to write a simple no-op implementation for updateFolder (the default implementation doesn't do this, for some reason [2]):

updateFolder: function (msgwindow) {
  this._inner.NotifyFolderEvent(atoms["FolderLoaded"]);
}

Here, atoms is merely is an associative array that contains a list of necessary atoms for the code. The end result of all of these changes is the following screenshot:

In the next part, I'll cover how to replace that screenshot with one containing an actual folder list.

Notes

As annoying as it would be, implementing nsIMsgIncomingServer or nsIMsgFolder from scratch is still somewhat feasible. I don't think the same holds true for nsIMsgDatabase (or the other database helper interfaces): static_casts permeate the code here, with the note that it is a "closed system, cast ok".
If you're wondering why this post took so long to be produced, this is a major reason why. It turns out that not having this implementation causes the folder display to not display the database load, so it just displayed the server page with the server name changed to the folder name. That, on top of having no time to debug it.

Code coverage to the extreme

2010-04-02T12:02:00.005-04:00

If all goes well, sometime tonight I will have completed 362 builds of Thunderbird, one for each day from July 24, 2008 to July 23, 2009 excluding August 3, 2008, December 25, 2008, and July 4, 2009 (more may turn up as I get more data; bonus points if you can figure out the significance of each of those days!). Included for each build is either a build log to tell me why the build failed or a test log telling me what ran. Also included is a copy of the Thunderbird code coverage data.

What, you may ask, do I intend to do with a year's worth of code coverage data? I intend to use this data to help answer some questions I have about our code coverage. Already, I've wondered about a more general overview of code coverage data (see my last post for more details). Now, I want to pose some of the following questions:

Whose code is not covered?
Who is adding code right now without making sure to cover it?
Whose tests are responsible for most improving code coverage?
How is code coverage being impacted over time?

My answers to these questions involves taking a snapshot of the code coverage data over time. That, however, proves to be a little more difficult than you'd imagine. First of all, hg doesn't support, as far as I can tell, an "update to what the repo looked like at this time" (hg up -d goes to the revision that most matches that date, not to a snapshot at that time). So I had to write a few scripts to pull out the revisions to look at. Second, gloda ruined some of this data. Fortunately, that's easy to tell due to the <1KB log files complaining about no client.mk. Then there's the issue of my revision logs containing m-c data, not m-1.9.1, so I have to hack around the client.py for Thunderbird trying to pull a different revision.

Another source of complaints was actually building and running the things. The computers I'm doing this on are all 64-bit Linux. There are a few m-c revisions that cause 64-bit to break, and libthebes and gcov just can't seem to work together on 64-bit Linux. Plus, libpango has some breaking API changes between 2.22 and 2.24. One of the XPCOM tests seems to crash and sit there with a prompt saying "Do you want to debug me?" Finally, the test plugins seem to cause massive test failure due to assertions. Not to mention that these machines don't have lcov on them and I don't have sudo privileges (so I'm not running mozmill tests yet).

In short, it's somewhat surprising to me that this actually works. Just looking at some of the build generation shows some coarse changes: between October 2008 and June 2009, the size of the compressed test log files increase 6-fold, and the compressed lcov output has nearly doubled in the same period. Lcov also reported that the coverage increased from about 20% to around 40% as well.

Sometime later, I'll hope to get mozmill tests working, as well as improving the JS code coverage to actually work for Thunderbird (it doesn't like E4X nor some of the other files for no apparent reason). Since jscoverage works by modifying the JS code, I can run that without really needing the builds (archived nightlies plus tricking the build-system will work). When all that data is collected, or sometime before, I'll make a nice little web-app that shows all of this information so people can gawp at pretty pictures.

If you want to try this on your own, here is the shell script I used to actually collect data:

#!/bin/bash

if [ -z $1 ]; then
    echo "Need a date to build"
    exit 1
fi
DATE=$1

REV=$(grep $DATE comm-revs.log | cut -d' ' -f 3)
MOZREV=$(grep $DATE moz-revs.log | cut -d' ' -f 3)

if [ -z $REV -o -z $MOZREV ]; then
    echo "Illegal date"
    exit 2
fi

echo "Updating to $REV"
hg -R src update -r "$REV"
hg -R src/mozilla update -r "$MOZREV"
pushd src
python client.py --skip-comm --skip-mozilla checkout &> ../config-$REV.log
make -f client.mk configure &> ../config-$REV.log
popd

pushd obj/mozilla
#make -C .. clean &>/dev/null
for f in $(ls config/autoconf.mk nsprpub/config/autoconf.mk js/src/config/autoconf.mk); do
    sed -e 's/-fprofile-arcs -ftest-coverage//' -e 's/-lgcov//' -i $f
done
echo "Building mozilla..."
make -j3 &> ../../build-$REV.log
popd

pushd src
echo "Building comm-central..."
make -f client.mk build &> ../build-$REV.log || exit
popd

LCOV=lcov-1.8/bin/lcov
$LCOV -z -d obj
pushd obj/
echo "Running tests..."
rm -f mozilla/dist/bin/plugins/*
make -k check &>../tests-$REV.log
make -k xpcshell-tests 2>&1 >>../tests-$REV.log
popd
$LCOV -c -d obj -o $REV.info
echo 'Done!'

Don't bother complaining to me if it doesn't work for you. I just did what I needed to do to get it to reliably work. And be prepared to wait for a few hours to collect any non-trivial number of builds. It took me about 12 hours to get 6 months worth of data using 6 different computers; the next 6 months is still going on right now.

Visualizing code coverage

2010-03-25T23:12:00.005-04:00

One recent goal of Thunderbird development has been to increase test coverage. Murali Nandigama has prepared a nice document on getting code coverage data. Running this on just the xpcshell tests for a recent build gave me this output.

So the output of LCOV (which does the post-processing) is passable. With enough clicks, I can figure out which lines are being covered and which ones aren't. But if you step back and try to look at the big picture… that's hard to do. Some directories sure seem good at code coverage: I mean, we hit both the lines of code in there. On the other hand, we seem bad at covering IMAP, only hitting around 11,000 lines of code (note the difference of scale). There's got to be a better big picture.

The answer I came up with was to use a treemap. Basically, treemaps are a good way to display two key attributes of data on the leafs of a tree at once: one is the color, the other is the size (actually, you can probably manage to squeeze three attributes of data under certain conditions if you vary color/saturation independently, but I'm not going that far here). In this case, the hierarchy is the folder hierarchy under mailnews (I'm not interested in m-c coverage) with the leaves being individual files, size being number of functions in a file, and color being the ratio of functions. The result with the same coverage data is the following graphic:

I've also taken the liberty to label the top-level directories so you can read them without having the mouseover capabilities. Immediately, you can see some interesting points about mailnews:

The IMAP code is the largest of the protocol code in terms of functions by a considerable amount. Local code, NNTP, and compose are all roughly equal in size by the same metric.
Some of the extensions (SMIME and MDN, actually) are not tested at all. Import code is also poorly tested.
Some of the MIME code is well tested; others aren't. In fact, it's hard to test a function in libmime without testing half the functions in that file. Perhaps we should have more encrypted messages in our tests?
Speaking of libmime, it's spread out across several files. In other components, functions are centralized into fewer files: specifically protocol, server, and folder. Wonder why? :-)
nsAbCardProperty is quite well-tested. LDAP files are not. RDF files everywhere are pretty poorly-tested.

I suppose I should also see how mozmill tests change these results. I'd also like to see how this changes over the history of hg. I can provide the source code to people on request, too.

JSHydra and ASTs

2010-03-24T21:01:00.004-04:00

One goal I've had for a while with respect to JSHydra was to have it actually spit out an easy-to-understand AST, akin to the kind of AST you get from Pork, as opposed to the parse tree from SpiderMonkey. After reading around in a fashion, I've written a postprocessing script to do so.

The basic idea for the output format is along the lines of the JsonML AST format, with a mixture of pork and "I think this is what's happening" to top it off. The actual ["Type", {}, child1, child2] format I quickly gave up using because it proves cumbersome to look at; in the interest of keeping something akin to the Pork format, I moved to a more ad-hoc format, which loosely follows the visitor pattern they mention.

I've added this output format to the WebJSHydra reader (yes, it is a copy-paste in part of the webpork code), so you can play with it to your heart's content. Just don't make it large. It also doesn't support E4X, and I'm not entirely assured of its correctness. Also, I don't support the visitor yet, nor do I have a C or C++ version of the AST for static analysis tools.

A new folder tree view

2010-03-23T22:41:00.002-04:00

One complaint I have made a few times is that my hierarchy of accounts does not necessarily match up to the logical structure. For example, I have Mozilla-related folders splayed out across three accounts, one newsgroup, and two email accounts. They're different because, well, you can't combine mail folders, newsgroups, and RSS feeds all under one account.

Now, in Thunderbird 3, Joey Minta replaced the folder pane with a more extensible version. Having some time on my hands (I finally figured out the bug that was stopping me from completing part 2 of the ongoing Creating New Account Types series), I decided to try to make a simple extension that would create a categorized tree view. So this is what I made. Notes, though:

It doesn't actually work in Thunderbird 3, only some of the newer nightlies. It turns out that the folder tree view stuff changed between Thunderbird 3 and Thunderbird 3.1, and the newer version is what I used to make the extension.
Speaking of which, it turns out that there is a bug in gFolderTreeView.load. Just to make life fun, the strings in the bundles are different between Thunderbird 3 and 3.1. Argh!
Categorizing works by setting a property on DBFolderInfo, for now at least. So this means it doesn't appear to work on server folders.
Uncategorized folders fall under the categories of their parents. So, basically, at the beginning, everything is laid out like the all folders view just shifted one level down. As you categorize more stuff, portions are spliced under different categories.
Categories should be marked as having new or unread messages if any folders beneath them are so marked.

Once I can get it working in TB 3.0, I'll try to get it up onto amo.

Developing new account types, part 1: The folder pane

2010-02-05T12:14:00.010-05:00

In the previous blog post, I gave a broad overview on the overall structure of the backend interfaces and the components of account implementation. Now, we will prepare the necessary components of getting your extension's folder displayed in the folder pane.

Account implementation decisions

Before you start implementing, you have to decide how to structure the account. The first decision is what the internal account type will be. This will be the value of nsIMsgAccount::type and will dictate the contract IDs for several interfaces. The next decision is what the account URI scheme is. This will be the scheme for the URI and dictates the contract IDs for a few more interfaces; for mailbox accounts, this scheme will be mailbox. For my extension, I have decided to choose webforum for both of these.

Another important decision to make will be the server for which you will be doing most of your initial tests. It should be something that is manageable for debugging purposes. In my case, I've decided to bestow this honor on the Kompozer web forum, because it seems lower traffic than any other forum I'm reasonably interested in. As you may notice, I am starting my extension with the intention of focusing on phpBB access—it's sufficiently widely used that I expect that only supporting phpBB at first would still make a worthwhile extension.

Once you have decided that, you should take the time to study how things will be structured: what determines a folder? What determines a message? A thread? Replies? How are you going to be carrying out new actions, such as checking for new messages? What internal information are you going to need to save for accessing? Heck, what determines the "server" to begin with? In my case, the DOM inspector is an invaluable tool for answering this questions. Don't worry about how to figure out the list of possible subscribable folders yet. Subscription will come into play much later; we are going to start by just hardcoding this list somewhere.

In my case, I am choosing to structure the folders as a Category → Forum hierarchy. I'll pick a few of the smaller forums to use so I don't overwhelm debug logs.

Implementing protocol information

Since nsIMsgProtocolInfo is the shortest and simplest of the interfaces, let me start by implementing this one. There are a total of 12 attributes and 1 function on this interface, so the code will not be hard to write. Following is an implementation of the code [1]:

wfService.prototype = {
  contractID: ["@mozilla.org/messenger/protocol/info;1?type=webforum"],
  QueryInterface: XPCOMUtils.generateQI([Ci.nsIMsgProtocolInfo]),

  // Used by the account wizard and account manager
  get defaultLocalPath() {
    let dirSvc = Cc["@mozilla.org/file/directory_service;1"]
                   .getService(Ci.nsIProperties);
    let file = dirSvc.get("ProfD", Ci.nsIFile);
  file.append("WebForums");
    if (!file.exists())
      file.create(Ci.nsIFile.DIRECTORY_TYPE, 0775);
    return file;
  },
  get serverIID() { return Ci.nsIMsgIncomingServer; },
  get defaultDoBiff() { return true; },
  get requiresUsername() { return false; },
  getDefaultServerPort: function (secure) { return -1; },
  get canDelete() { return true; },

  // Used by UI code
  get canLoginAtStartup() { return true; },
  get canGetMessages() { return true; },
  get canGetIncomingMessages() { return false; },
  get showComposeMsgLink() { return false; },
  get specialFoldersDeletionAllowed() { return false; }
};

The meaning of each of the attributes can be found in more detail on the MDC page. The properties used by the account wizard mostly control initial preference values; those used by the UI code mostly control which UI elements are enabled. I have excluded from the implementation also those attributes which are unused.

Perhaps the most leeway you have is in implementing defaultLocalPath. In this case, I have adapted the RSS implementation, which does not allow users to change this location. The other implementation (used by IMAP, POP, NNTP, Movemail, and Local Folders) uses a preference to return the default path. An example implementation of this method is like thus:

get defaultLocalPath() {
  // This will probably be found in the constructor
  this._prefs = Cc["@mozilla.org/preferences-service;1"]
                  .getService(Ci.nsIPrefService)
                  .getBranch("extensions.webfora.");
  // Preference looks like [ProfD]WebForums
  let pref = this._prefs.getComplexValue("rootDir", Ci.nsIRelativeFilePref);
  return pref.file;
},

Once you have completed that, you should test that the service implementations work as expected via test snippets in the Error Console. The account manager can be mean when it comes to unusable account types [2], so this will help fix the most obvious bugs before the account manager attempts to do it for you.

Server and root folder discovery

Before I start going any further with code, let me take a minute to explain how servers and folders interact. The server objects themselves do surprisingly little in the UI; the most common property calls are probably rootFolder and type. This even includes what you might think of as server attributes: the bold display name, has new messages treeview properties, etc. Instead, those features can be found on the root folder, which is a "fake" folder object. Most of what we care about in this part happens on the root folder instead of the server; however, if you browse the implementation in nsMsgDBFolder, you can see that some of the property calls get forwarded back to the server for root folders.

The backend code will create server objects early on and hold onto them for the duration of the program (or until they are deleted). The server objects then create the root folders which then create subfolders as necessary. Links that go backwards (parent links and server links) are weak references to avoid refcount cycles. Most of this work is hidden in nsMsgDBFolder for you. After creation, various properties are accessed at will; some properties will be loaded in from the database info (a topic for later).

In more concrete code terms, the following is the steps in loading the folder pane:

The account manager loads the mail.accountmanager.accounts preference; the values here are a comma-separated list of account keys.
For each account key, an account is instantiated. Per-account data is read off of the mail.account.<key> preference branch; in specific, the server preference contains the server key to load and the identities preference is a comma-separated list of identity keys.
The identities and servers are then bootstrapped. In the case of servers, the server is created as an object with the @mozilla.org/messenger/server;1?type=<type> contract ID. The server pref branch is mail.server.<key>; key preferences here are type, the type for the contract ID; userName, the (optional) username of the server; and hostname, the (required) host of the server.
The account manager sets the key, type, username, and hostName properties, in that order on the server object instance and then retrieves the port property. The (type, username, hostName, port) tuple is the unique identifier for a server: no two servers can have the same combination of these values. Now your server is constructed and returned to the folder pane.
The folder pane retrieves the rootFolder of your server. If you happened to be saved in the expanded state, subFolders is recursively retrieved from folders as corresponding to the saved open state. The folder pane also calls performExpand() on the server if the root folder is expanded.

So that explains how your server gets created; how do your folders get created? nsMsgIncomingServer::GetRootFolder [3] calls nsMsgIncomingServer::CreateRootFolder, which calls serverURI and uses it to construct an RDF resource. serverURI creates a URI of the form localstoretype://[<username>@]<hostname> by default. This URI is actually the URI of your root folder; other code will assume that this invariant holds true (especially subscribe!). Other folders are created when you get the subFolders property. When the folder URI is parsed (which is pretty much the first time a useful property is called), getIncomingServerType is called to get the type of the server.

In summary, you may need to implement localStoreType and possible serverURI on your server, and subFolders, and getIncomingServerType, and CreateBaseMessageURI on your folder [4]. First we'll start by getting the root folder display working:

function wfServer() {
  JSExtendedUtils.makeCPPInherits(this,
    "@mozilla.org/messenger/jsincomingserver;1");
}
wfServer.prototype = {
  contractID: ["@mozilla.org/messenger/server;1?type=webforum"],
  QueryInterface: JSExtendedUtils.generateQI([]),
  get localStoreType() { return "webforum"; }
};


function wfFolder() {
  JSExtendedUtils.makeCPPInherits(this,
    "@mozilla.org/messenger/jsmsgfolder;1");
}
wfFolder.prototype = {
  contractID: "@mozilla.org/rdf/resource-factory;1?name=webforum",
  QueryInterface: JSExtendedUtils.generateQI([]),
  getIncomingServerType: function () { return "webforum"; }
};

At this point, I recommend you again check to make sure resources are properly registering via the Error Console. With that in hand, it's time to modify your preferences manually. I personally recommend changing settings via editing prefs.js while Thunderbird is off so you don't accidentally confuse the account manager. I'm using the keys account99 and server99 to make it plain which account is being edited. First, I copy the mail.identity.id3 pref branch (any identity would do) and change the id3 to id99. Then I copy the mail.account.account3 pref branch and change the 3's to 99's.

The next changes are the server preferences, which are going to be the most unique. directorydirectory-rel are set to a folder where I want to store stuff ([ProfD]WebForums/kompozer, in my case). download_on_biff and login_at_startup are set to false (to avoid dealing with biff for a bit longer). name is set to be the display name of the server. hostname and userName were set to the appropriate values for this account [5]. To the preference mail.accountmanager.accounts, I appended account99. With those changes done, I then start up Thunderbird to see the outcome:

Perhaps I should have chosen a shorter name for display.

Folder discovery

Now that the root folder is displayed, we need to get the folders added to the display pane. Somehow, we need to figure out what the folder hierarchy looks like—it has to be stored in some file, in other words. The NNTP code uses the newsrc file to store its folder tree, and local folders looks at the directory hierarchy for its map, to name two examples.

In my code, I'm going to choose the use of a JSON file to store this data. I've considered SQLite, but I don't really need synchronization (per-server files work nicely here), and I'm mostly doing simple lookups. Plus, I can probably handle automatic schema migration more easily in SQLite.

For this next part, we concentrate on a single property: subFolders. This function typically has two parts: it first checks for initialization (if so, it returns the enumerator to the stored values); if it's not initialized, the rest of the function, or perhaps a second function altogether, is used to create the subfolders.

Some code to initialize these subfolders is as follows (the logic to retrieve the database is not included and can instead be found in the source code for my extension):

 get subFolders() {
    if (this._folders)
      return array2enum(this._folders);// If we're here, we need to initialize.
    this._inner.QueryInterface(Ci.nsIMsgFolder);
    let serverDB = this._inner.server.wrappedJSObject._db;
    // Uninitialized -> no subfolders
    if (!serverDB.categories)
      return array2enum(this._folders = []);

    // First find our level
    let level = /* some logic */;

    let URI = this._inner.URI + '/';let folders = [];
    // Yes, we still use RDF
    let RDF = Cc["@mozilla.org/rdf/rdf-service;1"].getService(Ci.nsIRDFService);
    let netUtils = Cc["@mozilla.org/network/io-service;1"]
                     .getService(Ci.nsINetUtil);
    for each (let sub in level) {
      // Some URIs may contain spaces, etc. -> escape
      let folder = RDF.GetResource(URI + netUtils.escapeString(sub.name,
        Ci.nsINetUtil.ESCAPE_URL_PATH));
      folder.QueryInterface(Ci.nsIMsgFolder);.parent = this;
      folders.push(folder);
    }
    this._folders = folders;
    return array2enum(this._folders);}

There are a few major things to note. First, the new folders are created via the RDF resource. Both Thunderbird and SeaMonkey use RDF for folder access, so it is still a good idea to create via the RDF service so you don't confuse the caller code. Also, with that in mind, the subfolder name still needs to be escaped as well in the URI, hence the calls to nsINetUtil. The auxiliary function array2enum takes in a JS array and returns a proper nsISimpleEnumerator for the array. I've excluded it's definition here do to its simplicity and the length of this document; if you want to see it, you can view it from the extension source code. The last thing to note is that this code is using this._inner: this variable is a link to the nsMsgDBFolder implementation which was created for us by the JSExtendedUtils inheritance call. I will defer a more thorough treatment of this C++-JS glue until later.

Folder pane extras

At this point, you should have a simple, plain folder hierarchy, which is navigable if not fully usable. In terms of UI, though, it's not quite fully perfect: if you have an inbox, it will be rather indistinguishable from other folders; similarly, "fake" folders (think the [Gmail] folder if you have Gmail IMAP) show up as regular folders. These things are handled to a large degree by CSS.

A full list of the available of the styling points for the Thunderbird folder pane can be found on MDC. Extensions can also modify the folder pane views or add other, non-folder items. More information can be found at MDC's folder pane information page.

I would provide some example styling code here, but when I was doing testing, I discovered some related assertion failures that I have not yet had time to grok. In the interest of keeping to a posting every two weeks, I am going to defer this until either a mini "part 1.5" or the beginning of part 2, depending on how much time I will have available next week.

Notes

I will not, in general, post the full code for any of the classes, only enough to demonstrate what needs to be done. For example, the classID property is omitted in this example. Something to note is that I have a modification to XPCOMUtils locally that will accept arrays of contract IDs as opposed to a single one (wfService will be implementing more than one contract ID).
What it specifically does is attempt to get the server; if it fails, then it removes the account from the accounts pref. If you are compiling your own builds for your extension development profile, I recommend you remove the lines in nsMsgAccountManager::LoadAccount that remove the account on failure.
In general, I will mix the IDL and C++ names for methods and properties in the course of the guide. As a basic rule of thumb, if you see a :: in the name, it's a C++ name; otherwise, it's the IDL name.
getBaseMessageURI is a local function called by nsMsgDBFolder during initialization that is used to set up the URIs for getting individual messages. This function will be covered in more depth as we get messages working, but it is technically necessary for startup (a stub that does nothing is provided).
A strong temptation for accounts whose sources are some web address (for example, RSS or my web forums account) is to put the base address as the hostname property. However, as you would quickly realize, that plays havoc on URI parsing, and nsMsgDBFolder::parseURI is not virtual. A better option would probably be to leave the hostname as some identifier that you use only for guaranteeing uniqueness and to store the base URI somewhere else. Since all of my folders have independent URIs associated with them, I can safely ignore the issue until account creation and subscription are covered.

Developing new account types, part 0: An introduction

2010-01-22T11:54:00.003-05:00

Before I begin the actual discussion, let me give some background. The ability to develop new account types has been my biggest extension goal for about two years now. Probably because of its difficulty, I know of only two extensions that have tried to do it: what is now the RSS code, and Webmail. In the first case, the implementer resorted to creating a binary component for the incoming server; in the latter, the implementer wrote a fake IMAP (and POP, SMTP) server to proxy the information to the web interface.

Some preliminary points: making a new account type is not a Good First Extension. You will need a fair amount of XPCOM experience, and probably decent experience at delving into implementations of undocumented interfaces. How much XUL and DOM (for stuff like webscraping) you use is up to you. MDC has a guide on building a Thunderbird extension from scratch. It is also probably not a bad idea to get comfortable with manual preference editing.

I am also trying a different form of development in this guide. This is not being done via my more common method of manually editing HTML by hand, but by writing in Kompozer. I'm also attempting to get more code included in my posts, and hopefully some images as well (the last part will be hardest). Like my first guide, I do expect that this will be adapted into a series of documents on MDC at some point. Some more reference-oriented documentation will be posted on MDC as I write this.

I personally use a debug version of Thunderbird, on Linux, very near the tip as the source code as the basis for my extension development (my regular profile is some 370 MB of stuff I don't dare threaten with developmental work). This is the same build I do patch development on, so I will rely on patches in said tree from time to time. One patch in particular is required [1], but otherwise, it should work on 1.9.2 and probably 1.9.1 as well.

This guide is structured to first demonstrate the actual activity components (e.g., displaying messages) and only cover configuration (e.g., the wizard to create a new account) when the more basic stuff has been completed. Therefore, you will need to get comfortable with editing configuration files by hand if you follow these steps exactly.

Backend introduction

So, let's start with an overview of the backend interfaces in mailnews. A list of the interfaces a front-end widget might use to talk to an account is: nsIMsgAccount, nsIMsgDatabase, nsIMsgDBView [2], nsIMsgFolder, nsIMsgDBHdr, nsIMsgIdentity, nsIMsgIncomingServer, nsIMsgMailNewsUrl, nsIMsgMessageService, nsIMsgProtocolInfo, nsIChannel, nsIProtocolHandler, and nsIRDFResource. Many of these would need to be implemented, and a few of them are not in any way small; to implement nsIMsgFolder would require a total of 186 methods, setters, and getters (as of this writing), many of which are not well-documented.

In reality, implementations are not from scratch. Everything tends to boil down into two or five different implementing classes: the server, the service, the folder, the url, and the database (there is also typically a protocol implementation as well). Of these, only the service is implemented from scratch, and it gets the simplest interfaces to implement. When I said "two or five," I am referring to the fact that there are actually two types of accounts. The first type, which only has to implement a server and service, can be called mailbox accounts: all of the messages are downloaded into local folders [3]. The second type implements all of the above, as the messages are generally stored on the server and downloaded on demand (or cached).

Of these two types, the less interesting is the first one. I will therefore generally ignore this account type. If you want to make such an account type, look at the RSS implementation for guidelines. The primary distinction is that mailbox accounts lack their own folder types, and therefore databases and URLs. In such a case, all you need to worry about is delivering the messages.

Following is a description of the major implemented components:

Server: The server represents the source of messages for an account. It also serves as the per-account configuration information for implementers. For example, NNTP stores the maximum connection limit to a server off of this implementation.
Folder: The folder represents a container of messages. Ultimately, the UI interacts more with folders than with servers, at least on a regular basis. This is the most complex interface to deal with, primarily because it can be hard to tell precisely what you need to implement versus what (eventually) calls back on some other message.
Database: The database represents a store of a subset of message information. It generally stores by default what NNTP would call overview information (enough to create a threaded message list), plus some flags like read status, as well as some information that extensions which to preserve.
Service: The service is more of a "how-to" guide for accounts. This is the external endpoint for ultimately copying messages, viewing messages, etc. Note that this is the only service implementation, so the actual server communication code typically happens in a different implementation.
URL: URLs are what the name implies. It's how one refers to messages, folders, and servers, although only messages are typically instantiated with the object in question. They also tend to be used as the primary internal communication system.
Protocol: The protocol instance represents a connection to a server. Unlike the other implementations, this one is not mandatory and is typically not visible via the "main" interfaces (nsIChannel is perhaps the most useful one they export). I suspect this is primarily useful for binary protocols, but I have not yet delved far enough into creating a new account to say for certain.

Important interfaces and their interactions

The center of an account is represented by the nsIMsgAccount. To get an idea for the amount of interfaces involved, look at the collaboration diagrams for nsIMsgAccount and nsIMsgFolder.

nsIMsgAccount represents an account. The interface itself is not terribly useful—it's mostly just a step on the way to get to a server or an identity.

nsIMsgIdentity represents an identity. Identities are essentially a way of persisting compose settings; since their use is wholly related to compose code, I will not discuss them in detail until later parts of the guide.

nsIMsgIncomingServer, as mentioned earlier, represents a message source. This is one of the interfaces you will have to implement, although much of it is already done for you. Everything that is specific to a server hangs off of this interface; everything that is specific to a folder hangs off of nsIMsgFolder; folders are accessible via the root folder of a server.

nsIMsgFolder, as mentioned earlier, represents a container of messages. This is one of the interfaces that has to be implemented, unless you are using a mailbox account. All folders have a database.

nsIMsgDatabase represents the message store overview. This has to be implemented if you are implementing nsIMsgFolder (unless you want to be sneaky). Databases are used to get at thread and header information, via nsIMsgThread and nsIMsgDBHdr, respectively. Messages themselves have numerous representations: URIs, header objects, message keys, and (sometimes) message IDs. Conversion between these forms is common.

nsIDBFolderInfo represents folder properties normally stored in the database. All of these properties are also stored in the folder cache (nsIMsgFolderCache) to avoid opening up all of the databases just to figure out how many unread messages are in each folder.

nsIMsgAccountManager and nsIMsgBiffManager are two managers that handle account creation and the periodic mail download (generally called biff), respectively. Expect to see these calling your code a lot.

nsIMsgDBView represents the thread pane view. This is going to be the primary consumer of nsIMsgDatabase, and this is where you should go to look to find out what happens if, e.g., you select a new message.

nsIMsgFilterList, nsIMsgFilterPlugin, nsIMsgFilterService, and nsIMsgFilter are the interfaces that deal with filtering. None of these will have to be implemented to support filtering [4].

The nsIMsgSearch* interfaces are those that deal with search (there are around 9 of them). Most of these will not have to be implemented to support searching. More on this when searching is discussed.

nsIMsgWindow represents the bridge to the front-end. It is passed into many functions, although it may be null, typically when being invoked from the backend.

nsIMsgMailNewsUrl represents the URL object that loads a message. This will generally have to be implemented if nsIMsgFolder is.

nsIMsgProtocolInfo represents the basic information about an account type's capabilities. This interface is one that is required to be implemented. As the name implies, it is generally geared towards the capabilities of the connection to the server.

nsIMsgMessageService and nsIMsgMessageFetchPartService represent the ability to retrieve the message (and message parts, more often known as attachments [5]). This is another interface that one must implement if folders are being implemented.

The MIME, compose, and import interfaces are omitted from this list of backend interfaces, as these are topics that will not be discussed for a while, and I am not certain they are useful to know about making new account types at present.

Notes

The purpose behind this patch is to enable extensions to reuse files from base/utils like C++ components can. If you were to adapt this to use C++ instead of JS, this patch would not be necessary. As the comments in the linked bug indicate, there is no guarantee that this will be implemented for Thunderbird 3.1; however, in such a scenario, the specifically required binary components would be available for reuse on some webpage. More on this when a decision is made.
Strictly speaking, this interface uses other interfaces in the list to talk to you. That said, a lot of interaction with folders and databases happens through this interface.
I say local folders—not Local Folders—here because Global Inbox settings actually rely on POP-specific attributes. It is still possible, via a reimplementation, to change the delivery settings. Such a mechanism is outside the scope of this guide.
It's not strictly necessary to implement these, but if you want to add custom filter terms or actions or custom search terms, some interfaces will need to be implemented. Such actions are beyond the scope of this guide.
Classifying all message parts as attachments is a pretty big oversimplification. In general, the only time specific parts are requested in Thunderbird and SeaMonkey are when attachments are involved. For more information on message parts, please see RFC 2045, RFC 2046 (two of the five MIME specifications), as well as the IMAP FETCH subsection (for numbering).

Building packages: harder than they look

2010-01-04T15:39:00.002-05:00

For a course I'm TAing, we (the other TAs and I) decided to revamp the tools so that students could more easily install them on their own computers. This was really my first look into actually producing packages for other people. Here is the long tale:

Step 1: Build `simpl`

Okay, the basic, core tools here compile and work easily. The more complicated tale is the GUI, built on qt. qt 3, to be precise. Except the autodiscovery thinks we want to try building qt 4. A single post-configure change gets this working. Only took a few hours here (trying to go the qt4 route didn't work so well, and we had interesting endeavors trying to figure out how to get KDE headers to work).

Step 2: Build binutils

This wasn't all that hard at first. Configure ran nicely and without problems, and building... oops, there's a warning and someone turned on -Werror. Another reconfigure gets this building quickly.

Step 3: Build (cross-compiling) gcc

Configure... build... fail... reconfigure... rebuild... fail... Repeat for several hours. Make that days. Do I want these options? Or those options? Still failing. Try editing files mid-build, so if that gets it to work. And, no. Okay, let's try binutils again. Solution: make install binutils first, then build gcc. That works without problems.

Step 3.5: Test the build

I have a Makefile that just requires me to change a few lines to swap gcc versions and directories of everything. Do that, try it, and... it doesn't work. Something about libc not working correctly.

Step 4: Build newlib

By this point, I know the drill: copy the configure from elsewhere, configure, and build. Apparently there's a typo in one of the ARM assembly files. I teach myself a tiny bit more of ARM (this is turning out to be very educational!) and fix the file. Reconfigure, rebuild, install, and test again. This time, it's complaining about missing a few functions. I found some more documentation online, and wrote my own sbrk function (where "wrote" means copied from some file online and tweaked to make it build). Testing fails again, so I make myself a few more functions and everybody's happy.

Step 5: Build vba

As you might imagine, this one didn't work either. So many build errors. I look at what Debian did, so I ponder some more, talk it over with the other TAs, and give up. Skritch, skritch.

Step 5: Build vbam

This fork builds... oh, wait, I need cmake. Okay, this fork builds without problem. They don't have version package downloads for my build script to pull, so I just have it yank a specific svn revision. Nice, simple package to work with after the mess that is cross-compiling.

Step 6: Build gdb

No problems here. Worked fine the first time, no patching, no need to rebuild. Even the testing had no problems. Stunned me.

Step 7: Package and test on school computer

Problems:

Can't find libmpfr.so
cc1: /lib/libc.so.6: version `GLIBC_2.7' not found
as: /lib/libc.so.6: version `GLIBC_2.7' not found
(vbam) Segmentation fault

Solutions:

Statically compile libmpfr.so. Not too hard...
Statically link gcc. Not very trivial. Eventually, LDFLAGS=-static in the configure arguments works.
Statically link as (and other binutils). This requires manually copying the final line and adding in the -static argument. Every time I rebuild binutils.
Debug, find backtrace. It's in pthreads, called from SDL. Try statically linking SDL (no luck). Try using different SDL versions. Rebuild vbam with debug. Notice that the primary reason for fault is... no sound device. Patch vbam. Test again, it works!

For the sake of clarity, every time I had to test in the final step, I had to reupload the tarball, which started out at 49 MB and grew to 55 MB (thanks to static compilation). Sometimes I had to reupload it again, if the connection died in the middle (my internet connection started getting flaky... possibly related to the 100s of MB I was uploading a day. Or maybe the 100s of MB I was downloading (every time I restarted the script, it downloaded 100 MB of source archives....).

So, in short, I had to override build scripts for 2 different packages, patch another 2, and build 3 out of 5 packages statically. One package doesn't have a point release; the other three are spread out among three separate servers to download. Running the build script from scratch requires nearly 2GB of disk space and takes several hours. At least now I repackaged it in Makefile form so you don't have to restart all over from square one if you forgot to install cmake first. Building the final tarball requires a good minute on my system.

But, I've finally finished the experience. Plus, I won't have to do it again... after I build the 64-bit version.

Predicted work on Thunderbird

2010-01-02T14:18:00.003-05:00

It's a new year, so it's time for me to predict (and probably overestimate, who knows) what I would like to do and see in the realm of Thunderbird (and SeaMonkey) and other tidbits in the Mozilla realm.

News submodule

Thunderbird 3 improved the filter story dramatically here; the next two biggest itches are the complete inanity that is news URIs (too many bugs to count), and the venerable old crossposts bug. I still contend that the latter would best be served by per-account database functionality; in any case, it does require some database changes to work properly. I doubt I'll find time to look at that bug in particular this year.

The URI issues are more tractable, but I don't think I'll find time to hit them for 3.1; in any case, I now consider them to be the highest priority news bugs. So, to anyone with time on their hands: feel free to take one or two of these and start fixing. You'll get much kudos from Thunderbird Usenet users.

Other various "nice-to-haves" on my list: fixing subscribe, cleaning up some of the gunk in the code, adding support for RFC 3977 CAPABILITIES, possibly changing how news:a.group URIs work (open the folder view, not necessarily subscribing to them), among others. Combine-and-decode also falls under this list, but it's a lot less tractable than some of the other stuff.

Analysis tools

jshydra could use some more love: I hope to be able to be able to get a converter to a more natural AST working by the end of the year, as well as an automated test suite to verify correctness whenever I change m-c versions. I've also been working on-and-off on getting symbols for DXR via MSVC, which should hopefully also be finished this year.

Other Mozilla/Mailnews work

As I've mentioned before, my biggest goal for 3.1 is to be able to specify new account types in Javascript. I basically have the necessary framework completed locally, I just need to finish writing the tests and fix some bugs before getting it reviewed and committed; after that, I'll be writing a series of blog entries on developing an account type in JS, similar to (and hopefully better than) my pork guides. Speaking of which, I hope to finish that sometime this year as well. Possibly during summer again.

I've yet to see a roadmap for the address book in 3.1 and later, so I don't know what I'll be doing for the address book in this upcoming year. I expect, though, that I won't do anything near the scale of what I did for bug 413260. De-RDF and de-morkification are another two things I'd like to see worked on that I don't expect to get to this next year as well.

Time to see how much I'll actually get done this year!

Google Wave in Thunderbird 3

2009-12-09T13:51:00.004-05:00

While it's not in the format I would ideally want, I recently got Google Wave inside Thunderbird 3. How, you might ask. Simple: the new content tabs feature.

So, to do it, go into the Error Console, and type this line in: Components.classes['@mozilla.org/appshell/window-mediator;1'].getService(Components.interfaces.nsIWindowMediator).getMostRecentWindow("mail:3pane").document.getElementById("tabmail").openTab("contentTab", {contentPage: "https://wave.google.com/wave/?nouacheck"});. Note that Google Wave for some idiotic reason decides that Thunderbird isn't a valid UA to be using, so you have to convince it to disable the UA with the ?nouacheck. I thought browser sniffing died out years ago...

For bonus points, if you restart Thunderbird, the tab will stay open, so all you need to do is login again!

Thunderbird extensibility

2009-11-29T17:58:00.002-05:00

With Thunderbird 3.0rc1 now released, it is time, in my opinion, to start looking towards the goals that Thunderbird 3.next and future versions should have. One category of goals would be the extensibility of Thunderbird.

When I say "extensibility," I specifically refer to replacing backend components or adding new components to certain type categories. I do recognize that things like the power of the address book API is important for extensions, but I don't consider that "extensibility" (perhaps "API usability" is a better name?). I am also going to focus exclusively on mailnews components here.

This blog post is a set of my opinions on the state of extensibility in Thunderbird and SeaMonkey. With one exception, I am not recommending what should or shouldn't be worked on: I am just giving my biased beliefs on these topics. I also want to mention that I focus primarily on the backend, so I have a very distorted view of what can be done in extensions and how easily it can be done.

The first metric I consider is possibility, the ability of one to adequately and easily make an extension in the given field in Thunderbird 3. Since it is theoretically possible to replace nearly any component given enough effort, a key component is the ease with which one can do it. High numbers correspond to requiring a little bit of JS and a bit of UI to go along with it; low numbers generally indicate that thousands of lines of C++ reimplementing large swathes of platform code is needed.

The second metric I consider is difficulty, the amount of effort it would take to make this facet of extensibility rather close to perfect. For this metric, having a lower number is better: a very low number indicates that it would only take a few hours to produce a patch (if necessary) to fix it, while a very high number indicates that several people would have to work for a few months to produce a patch, not including the review cycles.

The final metric I consider is desirability, how useful it would be to improve this facet. Again, higher numbers are better.

A final note about numbers: they're just qualitative indicators of relative value. Don't read too much into actual values, as I more or less came up with these numbers and then tweaked them up or down as I wrote more of this blog. A low value for possibility in particular doesn't mean it's very difficult to do right now, it just means it's not as easy as some other things.

Facets of extensibility:

UI
Folder pane views
Alternative database views
Message visualization
Protocol-level extensions
Import
Synchronization
Search backends
Filter backends
Specifying new address book types
Message storage
Metadata storage
Specifying new account types

UI:

Possibility: 10
Difficulty: 1
Desirability: 10

Here, when I talk about UI, I specifically mean the ability to add, remove, replace, or rearrange elements of the UI, including toolbars, menus, and keyboard shortcuts, among others. To my knowledge, there aren't many problems with being able to modify the UI modulo the usability of XPCOM, Mozilla's toolkit, or other components; any problems that come up could be worked out mostly by adding an id attribute or perhaps reshuffling a portion of the dialog. Then again, as I mostly stick to the backend, I could be dead wrong about this.

Folder pane views:

Possibility: 9
Difficulty: 2
Desirability: 5

Right now my 18 accounts (19 if you include the "Smart Folders" account) are arrayed in a specific order with trees of various folders hanging off of them. Perhaps I don't want to see them like that. After all, there is rather little correlation between an account and the contents of folders (in my case at least). None of the other layouts are particularly useful for my needs as well. Why not make a layout of folders that suits my needs better? For that matter, why limit it to looking at folders at all?

In a supreme effort, Joey Minta replaced the folder pane implementation with an extensible JS version (with regressions tracked down and fixed by myriads of others). This is perhaps the only major part where SeaMonkey and Thunderbird diverge greatly: SeaMonkey has yet to port the patch, for good reason (the original produced some 33 regressions, so it's a rather risky and complex bug to port). Asides from that, there's probably not much that would have to be done to get easy-to-implement extensions working here.

Alternative database views:

Possibility: 4
Difficulty: 7
Desirability: 3

This concept loosely ties into the creation of new account types, but I think many of the more exotic account types could use other ways of selecting messages than a tree of threads. Even email lists could sometimes use better visualization; here is a graphical thread view discussed by Andrew Sutherland that struck my eyes a year ago.

If you don't want to set your sights so high, making essentially a new filtered view is a matter of mere C++ extension combined with a touch of UI; replacing the <tree> XUL tag would probably be a lot more involved. Making the latter part easier would involve removing or shifting around a fair amount of logic around.

Message display:

Possibility: 5
Difficulty: 8
Desirability: 4

Not all messages are best viewed as static rich text. For example, feed summaries in many cases don't include the full article, so it's sometimes better to think of it as the URI that the summary is associated with. I also imagine that there are some wacky message visualizations for some domain-specific messages that would be nice to play with. Though I say that, I'm at a loss to think of any of them as being particularly useful right now.

It's not terribly hard to change message display right now, as one can replace the preview pane or full window with another URI on message load—this is what RSS does right now. At the same time, though, a lot of information in libmime is rather locked away, and more primitive forms of extension (replacing consideration of parts in specific circumstances) would require changing mostly-hardcoded libmime code. Which would probably require a C++ infection first.

Protocol-level extensions:

Possibility: 1
Difficulty: 5
Desirability: 2

There are 38 official IMAP extensions; the IMAP client code implements far fewer. In addition, there is also the possibility that servers may implement their own custom XAWESOMEIMAPCOMMAND which might be ideal to implement in an extension. Of all of the facets I describe here, this is the most difficult to do in an extension right now: you'd have to rewrite the protocol objects themselves. Making this possible to do is also no cakewalk, as this is inherently connection-level, but the server/service interfaces tend to abstract away connection issues. As for desirability, I mostly consider this a "neat concept," but probably not worth spending time to sit down and actually do. There is one example which recently came up, though: the IMAP ANNOTATE command is something that seems perfect to implement in an extension.

A subcategory of this which is probably more useful is the ability to merely add in new authentication schemes. All of IMAP, NNTP, POP, and SMTP have a mechanism for generic SASL authentication schemes; HTTP authentication (for RSS and possibly others) also has a similar generic authentication measure (I don't actually know how well HTTP-authed RSS feeds work, but I'd be surprised if there were a major problem).

Import:

Possibility: 8
Difficulty: 4
Desirability: 4

Coding an importer into an extension isn't too hard: I've done it before. The hardest issue I had was the fact that import is actually multithreaded (unlike most actions, which merely run on event queues). My understanding is that this implies that you cannot write it in JS, only C++.

That said, though, I'm not sure that it's something to be concerned with. Import is not something that I think a lot of people will be doing time and time again (if they were, you've pretty much entered synchronization land). Instead, import is something that matters more for people redistributing mailnews code, such as Linux distributions. The interesting cases, then, would mostly be other system applications, which generally implies that you're writing stuff in native code anyways (although JSCtypes can access those native APIs from JS, as long as they are written in C and not C++ (so no qt) and you don't need to expand dozens of macros to get a simple method (so no gtk)).

Synchronization:

Possibility: 7
Difficulty: 3
Desirability: 9

By synchronization, I mean specifically the ability to synchronize data—be it preferences, mail, contacts, calendar, or anything else people come up with—between Thunderbird and any other accepting client, which includes other instances of Thunderbird or SeaMonkey, online web services, PDAs, and smartphones, among others. You can already do it now, as evidenced by two of the more popular extensions doing this. Indeed, until recently, comm-central had Palm synchronization code in its tree. The problem is that some APIs could stand to cater more to this use case; I would even go so far as to say that a centralized framework might be useful.

Search backends:

Possibility: 6
Difficulty: 6
Desirability: 8

I've never precisely tabulated how much mail I get in a day, but I reliably receive around 100 messages a day from someone called "bugzilla-daemon@mozilla.org", another 50 or so from various other mailing lists, on top of innumerable RSS feed messages (I subscribe to 60 or so feeds) and NNTP messages. Compared to some other people, that list seems small. In short, many users may be suffering from acute information overload, and how does one remedy that? With comprehensive searching and filtering.

It seems to me, therefore, that search extensibility is vital. For example, for triage purposes, I might want to search for all bugzilla threads whose bugs are currently fixed (irrespective of the bug's status when I received the email). This area has really improved recently in Thunderbird 3, but I don't think it's quite there yet. For example, searching on the current status of a bug in bugzilla is not really feasible under the gloda search engine, but it may be possible under the conventional search. The high value for the difficulty is due to the fact that I think to put this where it truly ought to be, one needs to do some massive database overhauls.

Filter backends:

Possibility: 5
Difficulty: 7
Desirability: 7

My rationale for the desirability here is similar to searching, but it's slightly lower since I think that filtering is slightly less useful than searching (then again, my modus operandi is typically a trigger-happy finger on the Delete key). Again, filters have had massive improvement in the course of Thunderbird 3 development, but I don't think they're quite where they should be.

What makes this more annoying than search in terms of ease of use and hacking is the fact that filters live in a neverland where the headers have not yet been added to the database, so some potentially useful operations (notably, thread lookup) won't work. Changing this would require one to audit carefully the entire new message process and handle the database manipulation in precise ways. Nevertheless, I think this stands out as one of the more likely things to be improved, since the APIs seem to be slowly moving this way as a result of the other new message bugs.

Creating new address book types:

Possibility: 6
Difficulty: 2
Desirability: 5

This was an idea that I was once a very big proponent of; in recent months, though, I've tempered my enthusiasm for this. Unlike accounts, I don't think there's a lot of reason to prefer a new address book type over synchronization. There is also the possibility of faking a new address book type by selecting an address book to be automatically and zealously synchronized.

At this point, it was rather possible to create a new type—provided you write it in C++, you do some internal sleights of hand (it's a MAPI address book! I swear! Or maybe "none," which (oddly enough) also seems to work…), and you remember to make sure it's an RDF resource. Actually, getting a very rudimentary, read-only SQL address book implementation to work only took a few hours. The remaining internal work, to my knowledge, is merely to finish eradicating RDF, overhaul nsDirPrefs, and stop assuming the presence of nsIAddrDatabase in so many places. I'm not including the related address book API overhauls in the difficulty metric, although it seems the hardest part there is getting people to review the changes.

Message storage:

Possibility: 2
Difficulty: 9
Desirability: 5

Message storage is the ability to specify other ways to store messages. Predominantly this is is the storage for local folders and offline storage, although theoretically one can consider the remote storage of new account types to fall under this depending on how the API is done. Simply put, right now it is really difficult to do this in an extension: for all of mailnews's heavy usage of XPCOM, this is one area where the using classes create instances via new.

This is probably the most difficult of the facets to make extensible, even more so than the ability to make new account types. Why? First you have to create a new API, and then make everyone who does offline storage or local folders use it. The next thing is to consider the optimizations made under the hood to speed up local copy/moves and work out how to optimize them for more general APIs. Finally, you have to set up the UI. Flame wars of what to make the default may be involved as well.

With all that said, I don't think it's particularly desirable. For all of its foibles, I'm not particularly convinced that the proposed replacements for mbox are appreciably better. With that said, a well-designed API for this feature would also make creating new account types easier, as it would likely cause simplification of the nsIMsgFolder interface.

Metadata storage:

Possibility: 2
Difficulty: 8
Desirability: 1

This facet of extensibility is very similar to what I call message storage, except this is concerned with the ability to replace the database storage format itself. Creating an extension to do this now is at least as hard as creating one that replaces the message storage, I think. On the other hand, the core work needed to make it easier to do seems to mostly involve creating a few new interfaces and a large automated rewrite (depending on how much you want to depart from the current mork interface). Switching between databases would probably be largely lossy, though.

Of all the ways to extend Thunderbird, I think this is one of the least interesting. Seperate from message storage (which tends to imply a need to rework metadata as well), there is little value to being able to create new storage backends for metadata. That is not to say that I think this area couldn't use an entirely new format, I just think that the work needed to make it more pluggable is less desirable. I put it in here mostly to bring up for discussion of an approach mentioned in bug 11050.

Creating new account types:

Possibility: 3
Difficulty: 9
Desirability: 10

Last, but not least, is what I would consider to be the holy grail of extensibility, to be able to create new account types. While I have several reasons for considering this so important, the best reason in my mind is that this, more than any other facet of extensibility, would be able to best showcase the ingenuity of the world at large.

Assigning possibility and difficulty numbers here is difficult, as something like this has not really been fully attempted in recent years. Making a server in the ilk of POP, movemail, or RSS (one whose mail is downloaded and stored locally) is probably rather possible and not too difficult; making one in the format of IMAP or NNTP appears to only have been attempted once, and in that case, the author just ended up writing an IMAP server to bridge the two ends. I myself have tried more than once to create a working prototype; my furthest effort got to the downloading mail stage before I lost the will to continue.

As far as I know, there is nothing absolutely stopping somebody from just implementing this, at least in C++. That said, truly exotic account types (instant messaging or social networking are the common examples here) would probably require large contortions to work right, and the frontend is littered with manual type checks for account types that would probably have to be overriden in a more generic format. One large sector of possible account types is hampered by a difficulty in turning HTML text into a DOM tree for easier manipulation (i.e., screenscraping). I am therefore assigning rather pessimistic values for possibility and difficulty, since implementation currently requires brute force to attempt and the difficulty of making this easier to use requires a prototype implementation to fully ascertain.

On top of that, though, there is the issue that many account types would also like to be able to send stuff via the compose window. That part is probably the single hardest part, as compose cannot fathom the existence of anything other than SMTP or NNTP. One would therefore have to create new APIs for extensions, ramrod support for these into compose, and probably fix up nsIMsgIdentity to not be so mail-centric. Right now, the easiest way to do it is probably to make an SMTP server that acts as a middleman. I doubt a good way to do this can be finished before 3.next, though.

With that said, of all the facets I mention, the ability to create new account types is certainly the one I will put the most effort into personally. I have a goal of producing a usable extension in this regard, implemented entirely in JS, by the first beta, and this is my highest-priority 3.next goal.

A guide to pork, part 5

2009-08-22T18:40:00.002-04:00

In the previous two sections of my guide, I discussed basics of functions and then went into the specifics of types and names, as represented by the Elsa AST nodes. In this section, I will cover classes and some more errata on declarations. As I have mentioned earlier, the subsections of this third step will be visited out of the order of their numbering.

What has been covered so far:
Step 1: Building and running your tool
Step 1.1: Running the patcher
Step 2: Using the patcher
Step 3: The structure of the Elsa AST
Step 3.1: Declarations and other top-level-esque fun
Step 3.1.3: Function
Step 3.1.5: Declaration
Step 3.1.6: TypeSpecifier
Step 3.1.8: Enumerator
Step 3.1.11: Declarator
Step 3.1.12: IDeclarator
Step 3.4: The AST objects that aren't classes
Step 3.4.4: CVFlags
Step 3.4.5: DeclFlags
Step 3.4.8: PQName
Step 3.4.9: SimpleTypeId
Step 3.4.11: TypeIntr

Step 3.1.9: `MemberList` (inside a class)

MemberList has only a single variable: ASTList<Member> list.

Step 3.1.10: `Member` (part of a class)

Member nodes represent a member of a class type. Like other nodes, this is mostly represented by its subclasses, MR_decl, MR_func, MR_access, MR_usingDecl, and MR_template. The node itself has two members, SourceLoc loc and SourceLoc endloc. End locations represent the location just after the semicolon or closing brace, such that the range of text matches [loc, endloc); if you recall, this is the same syntax that the patcher uses when working with ranges of location.

Each of the subclasses of Member only adds one variable, which is the type that member represents. MR_decl adds Declaration d, hence it is used for all declarations within the class, be it a variable declaration like int x, a type definition, or a function without a body. MR_func adds Function f, so it represents all functions that have their body in the class declaration (A(); is a declaration, but A() {} is a function). MR_usingDecl has as its member ND_usingDecl decl (which is covered under the section NamespaceDecl), and MR_template uses TemplateDeclaration d.

The final subclass of Member is MR_access, which has its member AccessKeyword k. This node represents all of the declarations like private:. Since the information keeping track of the access is stuffed in separate AST nodes, you may be wondering how to retrieve this information given only a specific member. The answer, naturally, lies in the auxiliary classes to the AST, something which I have avoided mentioning. Some nodes provide access to a Variable member, one of whose methods retrieves the access to the member. More information about this will be discussed when I talk about that class in detail.

A final thing to note is that Elsa will add some nodes into the AST by the time you use the visitor. These are the implicit methods dictated by the C++ standard. You can check if one of these members is implicit if the DeclFlags variable contains DF_IMPLICIT. Another flag that will also be set is the DF_MEMBER flag.

Step 3.1.7: `BaseClassSpec` (extending classes)

BaseClassSpec nodes represent a superclass for a class. It has three variables, bool isVirtual, AccessKeyword access, and PQName name, all of which are self-explanatory.

Step 3.4.1: `AccessKeyword` (controlling access)

AccessKeyword is an enumerated type with three important members. These are AK_PUBLIC, AK_PROTECTED, and AK_PRIVATE, all of which represent what you think they represent. There is also a AK_UNSPECIFIED member, but that should not be present by the time you get to the AST nodes. Naturally, there is also a const char *toString(AccessKeyword) method for converting these types into a string.

Step 3.4.7: `OperatorName` (operator overloading)

These nodes are informational nodes about operators. You should only find them within the PQ_operator type. The class OperatorName only has a single method const char *getOperatorName(). This is the basis for the PQ_operator name strings, so its results are as mentioned there.

The first subclass, ON_newDel, represents the memory operator overloads. It has two members, bool isNew and bool isArray. The first differentiates between operator new and operator delete, the latter differentiation between operator new and operator new[].

The second subclass, ON_operator, represents the standard operator overloads. It has only one member, OverloadableOp op, which represents the operator being overloaded. The names in the OverloadableOp enum all begin with OP_ and can be idiosyncratic. Example operators are OP_NOT, OP_BITNOT, OP_PLUSPLUS, OP_STAR, OP_AMPERSAND, OP_DIV, OP_LSHIFT, OP_ASSIGN, OP_MULTEQ, OP_GREATEREQ, OP_AND, OP_ARROW_STAR, OP_BRACKETS, and OP_PARENS. There are naturally more, but the other names should be derivable from this sample (pretty much all the idiosyncracies were added to the list); the full list is in cc_flags.h if you need to see it. There is also the standard toString(OverloadableOp) method if you are confused about a particular operator.

Note that some of the operators can be used in different ways. For example, OP_STAR both represents the multiplication operator and the pointer dereference operator. The way to differentiate between the two is via the number of arguments, although one must keep in mind that operators that are class members have one less argument. The postfix increment and decrement operators are differentiated from the prefix forms in that the postfix forms add a second int argument, which is incidentally always 0 if you don't explicitly call the function.

The final subclass is the type conversion operator, ON_conversion. This contains a single member, ASTTypeId type. The member type will have a terminal D_name in its declaration with a null name; the main purpose of the declaration under the ASTTypeId is to capture the pointers.

Step 3.4.2: `ASTTypeId` (a less powerful version of `Declaration`)

ASTTypeId is modelled after the Declaration node, but it's used in places where multiple declarations are not usable. Indeed, its most common usage is to represent a type (nominally TypeSpecifier) that can have pointers or references. It has two members, TypeSpecifier spec and Declarator decl, both of which act as their analogues in Declaration.

Step 3.1.4: `MemberInit` (simple constructors)

When working with constructors, the initialization of members is treated separately from the rest of the constructor. In Elsa, the nodes where this happens are the MemberInit nodes. These nodes contain a few members:

SourceLoc loc
SourceLoc endloc
PQName *name
FakeList<ArgExpression> *args

The source location and end locations have the standard meanings. The name attribute refers to the name of member being initialized. The arguments refer to the arguments of the function-like calls.

Step 3.1.14: `Initializer` (the last part of declarations)

The Initializer nodes represent various ways to initialize an object. The class itself has a single member, SourceLoc loc, but it has three subclasses, each representing some form of initialization.

IN_expr represents the standard forms of initialization people are used to seeing, something along the lines of int x = 3;. These nodes have a single member in addition, the Expression e member which represents the expression initializing the declaration.

IN_ctor represents the constructor-like initialization forms, such as int x(3);. These have a single member, FakeList<ArgExpression> *args, which represents the arguments within the parentheses.

IN_compound is the final form, which represents the array-like initialization for structs or arrays. For example, int x[1] = { 0 };. This has a single member as well, ASTList<Initializer> inits, which is a list of the initializers within the aggregate syntax. Some words of caution, though, is that aggregate initialization can have unexpected results: multidimensional arrays need not have nested braces, and, in C++0x (and gcc since a long time, though it gives you a warning), you can also omit the braces for nested structures. Bit-fields and statics are omitted from initializers, and, if you have less elements in the initializer than you need, the rest are "value-initialized" (i.e., the equivalent of 0). Elsa, unfortunately, does not aide you any further in deducing which element is actually initialized by any given initializer.

Step 3.1.13: `ExceptionSpec` (saying what you may throw)

ExceptionSpec nodes correspond to the throw declarations on function declarations. These nodes only contains one member, FakeList<ASTTypeId> *types, which represents the types that method is declared to be able to throw.

That is all I have for this part of the pork guide. Part 6 should finish up sections 3.1 and 3.4, so I look track to have part 7 start discussion statements and expressions. I will probably defer the auxilliary API until around part 9 or so, as I really need to play with it some more first.

A guide to pork, part 4

2009-08-17T10:38:00.002-04:00

The last portion of the guide started covering declarations. This week, I will be covering a lot more about declarations. In particular, types and names are covered in a lot more detail. I had intended to talk about classes in more detail as well, but the post was getting long enough as it was, so I'll save discussion for a fifth part.

What has been covered so far:
Step 1: Building and running your tool
Step 1.1: Running the patcher
Step 2: Using the patcher
Step 3: The structure of the Elsa AST
Step 3.1: Declarations and other top-level-esque fun
Step 3.1.3: Function
Step 3.1.6: TypeSpecifier
Step 3.1.11: Declarator
Step 3.1.12: IDeclarator
Step 3.4: The AST objects that aren't classes
Step 3.4.5: DeclFlags

Aside 1: An introduction to porky (continued)

It seems that Chris Jones finally blogged about porky. If you're interested, go read about it.

Aside 2: Pork Web

In the course of writing this guide, I got the idea of writing a tool to display the Elsa AST nodes without having to constantly fidget around with dumpAST. The result is Pork Web, which is also a good expository of how much a little CSS will get you.

Step 3.1.6: `TypeSpecifier` (continued)

In the last article, I mentioned TypeSpecifier but elided details of its subclasses, who hold the interesting information, because I held a misunderstanding of key pieces of information.

For projects that are sufficiently large to be considered good candidates for automated rewriting, chances are that basic types like int are going to be rather rare, in favor of typedefs that give more precise storage sizes (such as mozilla's PRInt32). The parsing of the AST in Elsa and pork happens at a different stage from the type verification, which means that typedefs have an impact on the structure of nodes. That is not to say that you can't get type information; it just means that you want to use Elsa's type information (embodied in Variable) for more accuracy here. Naturally, #define has no impact on type information, because we are dealing with preprocessed files.

Which of the subclasses of TypeSpecifier is used depends on the format. If you are using a standard type keyword like int, you get the TS_simple flavor, which I covered last week. Structures parsed as classes in C++ (i.e., class, struct, and union) are all TS_classSpec nodes; enums form TS_enumSpec nodes. Class nodes, if you do not provide an actual definition, are classified as TS_elaborated nodes. If all you have is a simple name, then the node is a TS_name node, regardless if that type is a class, enum, or other such type. Names will never be null; for anonymous constructs like enum {a} x;, a unique string beginning with __ will be used instead.

TS_name has two variables: a PQName *name, and a bool typenameUsed. Both of these parameters are self-explanatory. For the curious, the latter comes about via an elabarator of typename, such as in the below:
template<class T> class Y { T::A a; };

TS_elaborated again has two variables, the same PQName *name variable, as well as a TypeIntr keyword variable. The keyword variable is an explanation of which keyword was used as the elaboration.

TS_enumSpec has again two variables, this time a StringRef /*(const char *)*/ name, as well as a FakeList<Enumerator> elts, which contains the elements in the enumeration.

TS_classSpec is the most complex of the subclasses, as it represents the definition of a class. It contains the same name and keyword variables as TS_elaborated, but it also has the base classes in the form of a FakeList<BaseClassSpec> *bases and its members in a MemberList *members.

Step 3.4.9: `SimpleTypeId` (Primitives, if you come from Java)

The SimpleTypeId enum represents the primitive types defined by C++, namely char, bool, int, long, long long, short, wchar_t, float, double, and void, as well as their unsigned and signed counterparts (if they exist). The name of each of these follows the general scheme ST_UNSIGNED_INT, although short and long are ST_LONG_INT and ST_SHORT_INT, respectively (but not long long!).

That's not all, though. For simplicity, some places have fake type codes. The most common of these will be ST_ELLIPSIS, the varargs portion of functions; there is also ST_CDTOR, the return type for constructors and destructors. The source code also mentions GNU or C99 support for complex numbers, but I have not found the magic needed to get those to work.

Step 3.4.4: `CVFlags` (CV-qualified IDs)

Whenever something can be const or volatile, there is a CVFlags enum. It can either be CV_NONE (no qualifiers), CV_CONST, CV_VOLATILE, or both of the latter. There also exists a method sm::string toString(CVFlags cv) that will print a string representation of such a variable. Need I say more?

Step 3.1.5: `Declaration` (The outer part of declarations)

Any time a variable is declared, one of the wrappers is Declaration (which may itself be found in various places). This has just three members, a DeclFlags dflags variable that represents the flags on the declaration, a TypeSpecifier *spec that is the type of the declaration, and the FakeList<Declarator> *decllist that contains the rest of the declaration. All of these have been covered in more detail earlier.

Step 3.4.11: `TypeIntr` (Differentiation between classes and structures)

TypeIntr is a little enum that has four members: TI_STRUCT, TI_CLASS, TI_UNION, and TI_ENUM. The descriptions of them are, I think, straightfoward. There is also a top-level method to convert to a string representation, char const *toString(TypeIntr tr), which will do what you think it does.

Step 3.1.8: `Enumerator` (The members of enumerations)

Within the definition of an enum is a FakeList of Enumerator nodes. These have a standard location and a StringRef name. The values can be represented in the potentially null Expression *expr variable, or the actual value in int enumValue.

Step 3.4.8: `PQName` (Everybody's name)

In declarations and other places, in lieu of a string representing name, you have the AST node PQName. The name stands for "possibly qualified." It comes about because there is the necessity of finding the different components of a name.

This class has four subclasses, PQ_qualifier, PQ_name, PQ_operator, and PQ_template. In addition to these, it has a plethora of functions intended to help you with the task of printing these names, as well as overloaded operators to aid in output (to std::ostream and stringBuilder). They are:

SourceLoc loc
bool hasQualifiers()
sm::string qualifierString()
sm::string toString()
sm::string toString_noTemplArgs()
StringRef /* const char * */ getName()
sm::string toComponentString()
PQName *getUnqualifiedName() /* (And a const version) */
bool templateUsed()

PQ_qualifier represents a namespace or similar component to a qualified name. This is handled in a right-associative manner, such that std::tr1::shared_ptr would be the qualifier std, which qualifies tr1, which qualifies shared_ptr. This class has three variables: StringRef qualifier (the name to the left of the double-colon), TemplateArgument *templArgs (which represents the template arguments for templated class qualifiers), and PQName *rest (the right of the double-colon).

PQ_operator represents a PQName that is actually an operator overload. It has just two variables: OperatorName *o, the operator in question, and StringRef fakeName, a string representation of the operator. The latter is essentially a space-less name of the function (except that operater new and friends are represented as such, as well as conversion operators having the poor name of conversion-operator).

PQ_template represents a templated argument name. It again has two variables: the StringRef name of the base type and the TemplateArgument *templArgs that contains the arguments to the templatization. Note that if you are getting a member of a templated class, the name tree will have the PQ_qualifier node instead.

PQ_name is the other of PQName (note the minor spelling difference). This has a single variable StringRef name which is the name. This is by far the most common name node, since everything that is not an instantiated template or an operator name will have this in the name somewhere.

For standard names, all of the various string output methods save qualifierString (which returns the empty string) will return the same thing, the name variable from PQ_name or the fakeName from PQ_operator. The differences arise when you have templates or qualified names.

If you have a qualified name, the methods change rather predictably. qualifierString returns the entire qualification string before the tail node (e.g., std::auto_ptr<T> becomes std::). The toString method and toString_noTemplArgs return the fully qualified names (optionally without template instantation). toComponentString becomes idempotent to the qualifier variable. getName will be essentially identical to getUnqualifedName()->getName(): it returns the name of the right most declarator.

Templated names also modify stuff predictably. toString_noTemplArgs and getName return the base name, without template arguments; toString and toComponentString return the name with template arguments.

The interesting stuff happens when you have a templated qualifier (e.g., std::set<int>::iterator). In that case, the toString_noTemplArgs will not strip the template args from the qualifier.

hasQualifiers() is identical to the isPQ_qualifier() method. templateUsed() is true if the qualifier or template used the template keyword. This is a feature that would be used for disambiguation purposes, such as this example (taken from the ISO C++ spec):


struct X {
  template<std::size_t> X* alloc();
  template<std::size_t> static X* adjust();
};
template<class T> void f(T* p) {
  // T* p1 = p->alloc<200>(); (p->alloc)<200>() -- syntax error
  T* p2 = p->template alloc<200>();
}

The last method to talk about is getUnqualifiedName. This method simply returns the PQName at the end of the name.

With all of the methods discussed, the most important question you're probably wondering about is the easiest way to get the name of a PQName. If you're trying to find a method or class name, getName is your safest option. If you need to know the type arguments as well (say you're looking for particular instantations), getUnqualifiedName()->toString() is a better option.

If you're looking at class members, you can probably use toString_templNoArgs successfully (when you're looking for a particular function), unless you're interested in the qualifierString() (when you're looking for any function of the class). For cases where the namespace information is necessary, you probably want to investigate the name with the parallel type APIs of elsa, unless you want to maintain your own state for using declarations and other shenanigans that make the original type non-obvious.

Unfortunately, while I earlier said that I intended to reference classes in this part of pork, it looks like I have not the time this week to cover them as well. At this point, it seems likely that part 5 will cover classes and part 6 will cover templates and errata. I cannot say what part 7 will touch: it will either be more errata or a start on the expression and statement code.

More jshydra news

2009-08-04T17:16:00.002-04:00

Taking a break from my ongoing series on pork, it's now time for an overdue update on jshydra.

First off, I have pushed Andrew Sutherland's changes (most of them, anyways) to my repo. These consist of the ability to push arguments, proper JS constructor handling (which I had locally but didn't commit for some reason I long forgot), and some minor comment handling fixes. I also never mentioned my JS inheritance divination work from way back in May. I also fixed a bug and finally got around to making TOK_* variables visible in JS, like the JSOP_* variables.

David Dahl has decided to use jshydra to find dead code in JS. That bug also has some discussion on how to run jshydra, as well as some work-in-progress files to grab JS information from the mozilla build system in a jshydra-friendly format.

Andrew Sutherland also used jshydra to generate documentation for TB. His blog posting does it more justice than I ever could.

Last night, I finally got around to creating an analogue of David Humphrey's Dehydra Web for JSHydra, predictably called JSHydra Web. As a note of caution, please don't upload your massive, 100+KB JS file for perusing: you'll find the output hard to read, and I don't want to overload the server.

As always, for more information on jshydra, you can either contact me by email (found on bugzilla), by IRC (most topical place of discussion is #static), or via the mozilla.dev.static-analysis newsgroup.

A guide to pork, part 3

2009-08-01T22:15:00.006-04:00

In the previous installment, I covered details on the patcher API and the basics of the Elsa AST API. If I were to write this as a reference manual, this is the point at which I would be spewing out a lot of verbose information on the C++ AST which would be hard to use for an introductory patch. One goal of this series of articles is to produce something close to a reference manual, so the parts will be numbered in that order. Instead, I will present the information in an order more likely to facilitate understanding.

In summary:
Step 1: Building and running your tool
Step 1.1: Running the patcher
Step 2: Using the patcher
Step 3: The structure of the Elsa AST

Aside 1: An introduction to porky

Having had more time to evaluate the new porky wrappers since my announcement of its commit last week, let me introduce you to it briefly. The tool takes in a list of rewrite specifications such as type PRCondVar** => mozilla::CondVar**, which will automatically change everything of the first type to the second type. It can also transform method calls into other method calls or even new/delete expressions. I would go into more detail, but that's for Chris Jones to discuss. If he ever blogs about it.

Step 3 (continued):

The following is an image representation of the C++ AST, excluding specific Expression and Statement subclasses:

To examine AST examples in detail, let us consider the example of a typical hello world program in C++:


#include <iostream>
 
int main() {
  std::cout << "Hello World!" << std::endl;
  return 0;
}

After being preprocessed, this small program becomes 19,153 lines of C++ goodness, thanks to the many header files being recursively included. Although we only define a single function, g++ defines for us namespaces (with GCC-specific attributes), templates, template specialization, typedefs, structs, classes, unions, function declarations, and half of the other C++ language features.

Let us look at each of these in turn.

Step 3.1.3: `Function` (Function definitions)

The Function AST node represents the definition of a function. It contains these variables:

DeclFlags dflags
TypeSpecifier retspec
Declarator nameAndParams
S_compound /* (Statement) */ body
FakeList<MemberInit> inits
FakeList<Handler> handlers

Unlike most AST nodes, the Function node does not have a SourceLoc loc member; instead, it has a getLoc() method which returns the location of the nameAndParams member, which would represent the location of the name. In our example, this would be line 3, column 5 (the beginning of `main').

Most of the members are self-explanatory: they represent, in order, the declaration flags (such as static or inline), the type of the return, the name and parameters aglomeration, and the statements of the body. The last two will be less common and NULL in the example I have here. The inits member represents the intializers of a constructor, while the handlers represents try-catch blocks that are scoped for the entire method. An example of such a block:


class Base {
  Base(const char *name)
    try : data(name) { } catch (...) { std::cerr << "Oops!" << std::endl; }
  const std::string data;
};

Strictly speaking, the enclosing try-catch is not limited to constructors, although I doubt it would be used outside of them except for stress-testing compilers.

There is little that you will want to do with these objects that does not fall under the use of other objects. Probably the most burning question you have is how to get the name of the function. These are the shortest ways: func->nameAndParams->var->fullyQualifiedName0().c_str() (going to a const char *) and func->nameAndParams->decl->getDeclaratorId()->toString() (going to an sm::string). The latter form will probably be more helpful if you are looking for specific methods, since it overrides the == operator.

Step 3.4.5: `DeclFlags` (declaration modifiers)

DeclFlags is an enum that specifiers certain flags about declarations. Each of the values is in the form DF_, always uppercase. The standard declarations--auto, register, static, extern, mutable, inline, virtual, explicit, friend, and typedef--have values in this manner. Other flags in the enum have uses for the Variable constructs, which I will not go into detail now.

Step 3.1.6: `TypeSpecifier` (first half of declarations)

A TypeSpecifier node represents a declaration of type, such as char. If you recall your C/C++ syntax, the declaration char *x, y; declares only one variable as a pointer--the * is matched with the variable name and not the type itself; in the AST therefore, TypeSpecifier does not receive these pointers (there come about in Declarator nodes).

By themselves, these nodes only have a CVFlags cv variable (representing the const- and volatile-ness of the type), as well as a SourceLoc loc location member. Instead, it has five subclasses with more specific attributes.

TS_name, TS_elaborated, TS_classSpec, and TS_enumSpec will be discussed in a future part.

TS_simple nodes represent the built-in simple types, like char. It has a single additional member, a SimpleTypeId id member.

Step 3.1.11: `Declarator` (the other half of declarations)

A Declarator node represents the non-type part of a declaration. It contains these variables and methods:

IDeclarator *decl
Initializer *init
PQName *getDeclaratorId() /*(And a const version)*/

Step 3.1.12: `IDeclarator` (the real declaration part)

The IDeclarator node does the heavy work in terms of annotating declarations. In some corner cases, the AST for a declarator can get very deep; the parallel type structure makes working with declarations much easier.

With the exception of the D_name and D_bitfield subclasses, all subclasses contain at least an IDeclarator *base member. In addition, IDeclarator holds these variables and methods:

SourceLoc loc
PQName *getDeclaratorId() /*(And a const version)*/
IDeclarator *getBase() /*(And a const version)*/
IDeclarator *skipGroups()
bool bottomIsDfunc()
D_func getD_func()

The skipGroups method skips through any excess groupings (i.e., parentheses layers). getBase returns either the base of the declaration or NULL if it is a leaf. getD_func returns the bottom-most D_func node, while bottomIsDfunc will tell you if the declaration is a function (but not a function pointer). getDeclaratorId obviously returns the name of the object at the very base of the declaration tree.

The first subclass is D_name, which is the typical leaf of the declaration. It has a single PQName *name attribute, which returns the name of the variable or function being declared. The other leaf class is D_bitfield, which has both the name attribute as well as an Expression *bits representing the number of bits in the declaration.

D_pointer and D_reference represent a pointer or reference indirection, respectively; D_pointer additionally has a CVFlags cv variable representing the qualifications of its pointer type.

D_ptrToMember is similar to D_pointer, but it adds another PQName *nestedName attribute to represent the construct whose member the pointer is pointing to. For those who don't recognize this feature, it can be demonstrated in this C++ snippet:


struct Foo { int Bar() { return 0; } };
typedef int (Foo::*ptrToMember)();
// The declarator tree (following base):
// D_func->D_grouping->D_ptrToMember->D_name
ptrToMember p = &Foo::Bar;

D_array represents an array declaration. In addition to its base, it also has the possibly null Expression *size member to represent the size of the array. Multidimensional arrays have these members arranged from the outside in.

D_grouping is a dummy node used mostly for the purposes of AST disambiguation during the parsing phase (it represents the use of parentheses in declarations). The skipGroups function can be used to pass these nodes.

D_func is necessarily the most complex declarator. Its base is typically the name of the function, although function pointers can have nested declarators. It has a FakeList<ASTTypeId> *params member for the parameters, CVFlags cv member for the const member functions, and ExceptionSpec *exnSpec for the exception specifiers.

Predicting declarator trees is not difficult. In general, you can apply standard rules to find the declarator: each * and & at the beginning creates the respective declarator indirection node; a [] or () at the end creates the array and function nodes, respectively; surrounding with paranthesis yields a grouping node. Pointers to members are created when the syntax is used (look for the ::*), and the choice between bitfield and name as the leaf comes from obvious decisions. One also needs to remember that the structures on the left are parsed before the ones on the right, unless overriden by parentheses, so the obscene int (*(*asdf)())[0] is yielded as array, grouping, pointer, function, grouping, pointer, name. If you're wondering, it's a zero-sized array named "asdf" that contains pointers to functions that return poiinters to integers.

There is much more to talk about in the world of ASTs. This will get you started on function bodies and declarations; the next part of the guide will cover more in-depth knowledge on declarations and begin to introduce classes.

A guide to pork, part 2

2009-07-22T21:11:00.003-04:00

Last time, I covered the very basics of using pork. In this portion of the guide, I will cover enough to get you to be able to write a small patch.

Since the time I wrote the first part of the guide, Chris Jones committed some tool wrappers known collectively as porky, which may necessitate updates to first steps.

In summary:
Step 1: Building and running your tool
Step 1.1: Running the patcher

Step 2: Using the patcher

The patcher works internally (more or less) by keeping a list of ranges and their replacement text, which it eventually uses to build up hunks that it then spits out to an output stream. The public API it provides (as of the current tip, in any case) comes in two sections: some file utility functions and text replacement functions.

Locations can be represented by one of three different types. The first is SourceLoc, which is a bit-packed integer that the elsa AST nodes give you. Then there is CPPSourceLoc, which is an only slightly less manageable location format. The final form is UnboxedLoc, which is the easiest one to work with.

As I mentioned earlier, the patcher actually works with pairs of these objects. PairLoc and UnboxedPairLoc are pairs of CPPSourceLoc and UnboxedLoc, respectively. The two are constructed in a pretty intuitive manner (although note that as UnboxedLocs do not store the file, you need to pass that into its pair type). Note that ranges include the left but not the right endpoint.

The class Patcher itself contains two methods for patching stuff: printPatch, which replaces text, and insertBefore, which inserts the text before a location. If you want to delete text, the answer is to replace a range with the empty string.

While this is nice, the patcher does suffer from a few flaws. The biggest of these that I've found is really a flaw in elsa: not all nodes have source and end locations (only statements and expressions), requiring me to roll my own search functions. Fortunately, the file API of patcher helps here.

The other big flaw is the difficulty of coping with visually important but semantically meaningless clues, namely comments and whitespace. If you naïvely delete text, you may end up with comments whose referents no longer exist or blocks of whitespace where code once was. Inserted text may violate local code conventions. I have not yet expended the effort yet to get this to work; you will either have to do this yourself, bug taras to do it, or possibly both.

Now, if you want to see some code in action:


// Here, func is a pointer to an elsa AST expression node
// And type a string representing its replacement
// patcher is of course a Patcher object.
patcher.printPatch(type, PairLoc(func->loc, func->endloc));

// Elsewhere
UnboxedPairLoc findAndMakePair(Patcher p, const SourceLoc &loc,
    char toFind) {
  int lLine, lCol;
  StringRef file;
  sourceLocManager->decodeLineCol(loc, file, lLine, lCol);
  int lineNo = lLine, col;
  do {
    std::string line = patcher.getLine(lineNo++, file);
    col = line.find(toFind);
  } while (col == -1);

  return UnboxedPairLoc(file, UnboxedLoc(lLine, lCol),
    UnboxedLoc(lineNo - 1, col + 2));
}

Step 3: The structure of the Elsa AST

The core of pork is the ability to parse AST nodes. In general, these fall under three categories: top-level declarations (possibly within classes or namespaces), statement and expression nodes, and utility nodes.

The basic structure of an AST node class is like this:


// A typical node type
class TypeSpecifier {
public:
  // Almost all nodes have these
  // Those that don't wouldn't make sense
  SourceLoc loc;

  // These methods are for nodes with subtypes
  // if returns null if it isn't the correct type; as throws
  char const *kindName() const;
  TS_name const *ifTS_nameC() const;
  TS_name *ifTS_name();
  TS_name const *asTS_nameC() const;
  TS_name *asTS_name();
  bool isTS_name() const;

  // There's another parameter that you'll never use
  void debugPrint(std::ostream &, int indent);
  void traverse(ASTVistor &vis);
};
class TS_name: public TypeSpecifier {
public:
  // Typically has some more data nodes
  PQName *name;
  bool typenameUsed;
};

To use these nodes, pork follows a typical visitor pattern. The class ASTVisitor will visit all of the node types; ExpressionVisitor subtypes have individual methods for visiting subtypes of statements or expressions. You can choose to look at nodes in either a pre or postorder traversal. A previsit traversal function is in the form:
virtual bool visitTypeSpecifier(TypeSpecifier *);
(where the return is whether or not to dig down deeper), and a postvisit in the form:
virtual void postvisitTypeSpecifier(TypeSpecifier *);.

Hopefully, this is enough to get you started on being able to use pork. In my next part, I will cover the AST nodes in more detail.

A guide to pork, part 1

2009-07-20T21:10:00.003-04:00

As one of the first people to have actually used pork (apparently the third, after taras and cjones), I feel obliged to give a guide as to how to write an automatic patch generator, so as best to prevent people from asking the same question a fourth time. This also contains some ranting about some of my annoyances with pork (sm::string, I'm looking at you). So, without further ado, I present Part 1: It works!

A brief introduction

Pork essentially consists of three main areas of API (enumerated in order of my discovery): the patcher API, the C++ AST structure direct from the parser, and the annotated APIs that make finding information more than a bit easier. There is something which constitutes a sort of fourth API, the utilities that partially replicate functionality in the STL.

My original interest in pork came from an idea to rewrite libmime, which is roughly a basic C++ implementation in C, into the equivalent C++ code. Such a patch would be on the upper end of difficulty for a normal shell, python, or awk script to rewrite: I need to combine classes, rewrite function prototypes, rename variables, and refactor globs of code like
return ((MimeObjectClass*)&MIME_SUPERCLASS)->initialize(object);
into
return MimeLeaf::initialize();

Step 1: Building and running your tool

The first step is to build pork. Taras's guide will likely be more up-to-date than any instructions I give. Now you have an installation of pork. After that, you can plug in your own tool into the structure. I've personally handled this by making a tools/ subdirectory and making a very neat Makefile that automatically adds files to be compiled into the tools themselves.

Your tool will eventually be invoked tool <args> filename if you are using the pork-barrel script. All that pork-barrel does is to run the programs one at a time and to merge the outputted patch in the end; you don't need to use it (and I recommend you don't) as you start your tool. The files it runs on are preprocessed files, generally with the extension i or ii. Invoking gcc with -save-temps is a nice way of generating these files. You don't need to use mcpp if you're not overly concerned about stuff lurking in macros.

Step 1.1: Running the patcher

Once your tool processes its arguments, it will eventually be reading the C++ files and patching them. Here is some sample code to do that, which I provide without comment (it's just boilerplate):

#include "piglet.h" #include "expr_visitor.h" #include "patcher.h" class MainVisitor: public ExpressionVisitor { public: MainVisitor(Patcher &p): patcher(p) {} private: Patcher &patcher; }; int main(int argc, char **argv) { PigletParser parser; Patcher p; MainVisitor visitor(p); for (int i = 1; i < argc; i++) { TranslationUnit *unit = parser.getASTNoExc(argv[i]); unit->traverse(visitor); } return 0; }

The necessary APIs for the utilities will eventually be covered in more detail. Unfortunately, it's late, and you now have a working, if idempotent, pork utility. Next time, I'll discuss the basics of Patcher and ExpressionVisitor.

jshydra news

2009-05-06T21:20:00.003-04:00

Since I happen to have some downtime thanks to the short space between college and a summer job, and some spare time with four wisdom teeth newly missing from my mouth, I have returned to work on jshydra. I am in the midst of simplifying the build structure for new or non-Mozilla hackers, and am also patching up one of the main scripts I have, the documentation-association script.

On Monday, May 11, 2008, at 1:00 PM EDT (10:00 AM PDT, or 1700 UTC), I will be holding in the #static IRC room for the benefit of users a "learn jshydra" day. You may of course ask me questions any time I'm actually on IRC (nick: jcranmer or derivatives thereof).

I hope to finish up the build structure by then and get a wiki article on the topic started as well. A feature request list is already starting, including the ability to take JS out from an HTML file. If you have others, communicate it to me somehow, and I'll stick it somewhere where I can remember it.

Is this faster?

2009-05-02T21:13:00.003-04:00

Last Wednesday morning (in the EDT timezone that I go to school in), I took my final in Probability & Statistics. It was a moment that I didn't think too much about until this morning, when, in one of the newsgroups I frequent, there was a discussion as to how much faster one option was compared to another. This post come up:

A good idea would be to measure each iteration separately and then discard outliers by e.g. discarding those that exceed the abs diff between the mean and the stddev.

I leave it as an exercise to the reader to figure out why that's not a good idea. In any case, the last unit of the class dealt with the fun part of statistics, which is to actually evaluate whether observed data is statistically significant. The actual math involved isn't too bad, assuming you have someone spit out a cumulative distribution function for the t-distribution for you (here is Boost's code), but it's a bit convoluted to write here, so read Wikipedia's page. The correct tests are actually the two-sampled t-tests.

But I got to thinking. One thing I've wanted to see for a while is a profiling extension, one that would run some JS code snippet multiple times and produce various reports on profiling runs. Wouldn't it be nice if such an extension could compare two runs and determine if they was a statistically significant difference between them?

Bugday: help us unconfirm new bugs!

2009-04-01T08:28:00.002-04:00

Yesterday, Reed helpfully enabled the NEW -> UNCO transition in Mozilla's bugzilla installation, which will enable us to reverse some mistaken decisions in the past. Looking at the current list of bugs, we have way too many NEW bugs to be healthy (Five thousand three hundred eighty-five, to be precise, at this time of writing).

So please help us triage our components by finding NEW bugs that do not have clear steps to reproduce and unconfirming them. While you're at it, you might want to try to do other triage on the bugs.

A database proposal

2009-02-18T19:52:00.013-05:00

A sore point in the mailnews code is the message database code. Most of the backend ends up being a single amorphous blob with fuzzy boundaries amassing huge couplings between a server's implementation and the database. Add into account the fact that the database documentation (like most of mailnews, but worse) is often either poorly documented or sometimes just plain wrong, and you get a recipe for disaster. There's also the issue, probably the most important one, that the database has grown past its original intent.

Originally, the message was merely a cache of the information for the display. Since it was only a cache, it doesn't matter that much if it is blown away and reparsed from the original source. Well, there's a little matter of the ability to set an arbitrary property that isn't reflected in the mbox source. This capability, among other features, has made the message database a ticking time bomb. And, in essence, the bomb recently exploded when I attempted to make it usable from JavaScript.

So, in the mid-to-long-term, the database needs serious fixing, not the incremental band-aids applied all over it. It needs a real design to fit its modern and future purposes. Naturally, the first question is what does a database need to do. Following are salient points:

The database is really multiple, distinct components.: One part of the database is a relational database: metadata for a message that is not reflected in the message itself. If an extension wants to keep information on certain message properties (like how junk-y it is), it would stick the information in this relational database. The second part of the database is a combination of the message store and cache. This part is what the database used to be: a store of information easily recoverable from the message store. Note that this part of the database needs to be at least partially coupled with the message store, more on this later.
The relational database is separate from the cache database.
The cache database exposes a unique, persistent identifier for messages.: While the cache database can, and probably will, be regenerated often, the relational database is permanent. Indeed, the cache database blowing itself away should not cause the relational database to have to do anything. At present, the cache uses ephemeral IDs as unique identifers: IMAP UIDs (destroyed if UIDVALIDITY is sent), mbox file offsets (destroyed if the mbox changes), or NNTP article keys (can of worms there [1]). In my proposal, the cache would map these IDs to more persistent ones. Yes, it makes reconstructing the database more difficult, but it makes everyone else's lives easier.
The cache database may be rebuilt if the store is newer.
The cache database rebuild should be incremental.
The relational database should not be ever automatically rebuilt.: One of the main problems as it stands is the rebuild of the cache database. It has been, in general, assumed that rebuilding the database would never lose information, but the database has become the only store of some information. I am not certain of technical feasibility, but there is in general no need to reparse a 2GB mbox file if you compact out a few messages. Even in an IMAP UIDVALIDITY event, I expect that not all of the UIDs would be changed. Incrementalism would make the database more usable during painful rebuilds, but, naturally, it would require more careful coding.
The cache database's rebuild policy is caller-configurable.: What I mean about this is that the cache database will be accessible via one of three calls: an immediate call that will get the database, even if invalid; a call which will get the database but spawn an asynchronous rebuild event [2]; and a call that will block until the database finishes rebuilding, if necessary. The implications of having asynchronous rebuild would require the database to be thread-safe, but I expect that the future of the database already includes asynchronous calls. At the very least, it might help in some cases where we've run into thread safety issues in the past (such as import).
The cache database has access to the message store.
There are three types of store: local-only, local caching remote, and remote-only.
The folder can only access the store through the database.: These points are probably the ones I'm least comfortable with, but I think it's necessary. In the long-term, pluggable message stores and the store-specific mechanisms of database means that the cache database needs to have intimate access with the store. Having explicit interfaces for the message store should allow us to avoid having to subclass nsIMsgDatabase for the different storage types. Limiting access via the folder should help cut down the bloat on nsIMsgFolder. On the other hand, it would probably make the code do a lot more round-tripping, which could lead to more leaks.
The cache database is per-account, not per-folder.: A cleverly-designed per-account store could alleviate some problems. It would make working with cross-posted messages easier, and could, in principle, use less disk if you move messages between folders on the same local stores or caches. Copied messages could point to the same messages (in the spirit of filesystem hard links), so long as we don't permit local message modification.

If I haven't missed anything, that is how I see a future database system. Obviously, implementation would not be easy; I expect it would take at least a year or even two years of concentrated work to produce something close to these ideals. There are incremental steps to this future, but they seem to me to be towering steps at many cases (for example, introducing the database to the store, or making it usable from different threads). In any case, I'm interested in hearing feedback on this proposal.

[1]In recent months, some of Giganews' binary newsgroups had begun to press distressingly close to the signed-32 bit limit, which raised the question of what to do. One proposal would have been to reset the ids or maybe wrap around. A news client should be able to handle this case if practical to do so, IMO.

[2]I expect that this method would use the invalid database, although it could be implemented by having the various method calls block until validity. Since it's possible that a caller could use the blocking-get-database call as well, this approach makes significantly less sense to me.

JSHydra

2009-01-25T15:36:00.006-05:00

Over the past week or so, in between my myriads of projects, I managed to find time to revive a partially-completed tool called jshydra (properly capitalized as "JSHydra"). JSHydra, in both name and code, is derived from Dehydra and Treehydra: it is a static analyzer for JavaScript. I first decided that such a tool was needed when I was in the middle of a large refactoring of address book code.

The source code for jshydra can be found at my Mozilla user hg repo. Presently, it requires some hackery and file modifications to merely build the system. I use SpiderMonkey internal APIs (the parsing APIs, to be exact), so that's where most of the hackery comes into play.

For the time being, I'm probably going to put aside doing more work on jshydra, as I have more pressing work on my plate at this time. If you have any questions, feel free to contact me via IRC (handle: jcranmer (I should be in #mmgc)) or via my email address as listed in bugzilla.

My other life

2009-01-20T00:12:00.002-05:00

I have just opened up a new blog covering those topics that are not oriented towards my work with Mozilla or other similar technically-oriented projects.

Eight things you didn't know about me

2009-01-13T22:27:00.009-05:00

Apparently it's my turn for these meme, according to taras. Oh yes, and KaiRo too. The rules:

Link back to your original tagger and list the rules in your post.
Share seven facts about yourself.
Tag some (seven?) people by leaving names and links to their blogs.
Let them know they’ve been tagged.

So let's get this show on the road! Eight things you didn't know about me (why eight? Because I like to go one step further):

When I was tested around first grade, my auditory processing skills were rated as "retarded." Possibly related to this fact, I was apparently deaf or near-deaf at the same time, and I'm still rather poor with auditory processing to this day.
I nearly flunked 7th grade biology but got the second-highest grade in my 9th grade biology class, I believe averaging over 100%. Indeed, I probably still recall large hunks of biology although biology is my least favorite core science and I wish I could forget it.
Despite having a high school GPA of 3.99 (where the best grade is a 4.0, and AP credit adds 0.5 to the final grade), the first time in my entire life that I achieved a perfect 4.0 was my first semester of college. My grades have often been littered with scores that just make the next grade level, such as a 93.52 in one year of French, or a 89.50 in Psychology.
Nearly all of my programming knowledge I taught myself. The only languages I learned as part of a class were (in order) Python, FORTRAN, and Smalltalk. All other languages (roughly speaking, Java, C/C++, x86 assembly, PHP, bash scripting, awk, sed, etc.). I taught myself before any courses that used them taught it to us. One day, for Senior Switch Day (a high school tradition), I taught a Computer Architecture lecture covering, in order, how vtables are implemented in gcc, how to use setjmp and longjmp for exception handling, and how to write a stack walker in C. And yes, I do know that I'm going to hell for using setjmp and longjmp.
In 7th grade, I tied for 10th place in the state for the Mathematics League. I personally know 11 of the other people who did at least as well. One of those people I actually referred to earlier in this post. And it's not Haitao.
I was once in a fight in 7th grade. The fight happened like this. Step 1: I was knocked into a bench in a locker room. Step 2: I was knocked over this bench into the lockers in same locker room. Fight over. I don't think I actually bled, but it hurt, IIRC.
For my senior prom, I went with four girls, for a definition of "went" more exclusive than "went in the same dinner/limo group" (there were actually around 12 or so girls in our group). Incidentally, all four girls were Asian, which is fairly representative of the ethnic makeup of my high school (or at least among those I knew).
Because of my speech impediment (or so I've heard), I've been fairly often asked if I'm British. Technically speaking, it's not a lisp—my problems are with r's, not s's. I wonder if people here think I sound British (I certainly don't)?

Time for poking people:

Gary Kwong: Fellow intern and bug triager, I wonder what he's done.
Siddharth Agarwal: His blog has been pretty empty.
David Bienvenu: He needs the excuse to blog.
Jesse Ruderman: For finding so many typos in my blog postings.
Shawn Wilsher: mozStorage writer, and one with whom I've spent some time trying to debug a TB news problem…
timeless: Because…he's awesome?
Saul (whose blog is inaccessible): Because it doesn't take a computer scientist to know the problem with pyramid schemes.

Hey look, I got through the entire post without mentioning demorkification! Oh cra—

A problem with feature requests

2009-01-13T13:53:00.007-05:00

Among many of my secret lives, I personally follow several mailing lists, newsgroups, and technology updates for reasons beyond the scope of this posting. I follow the WHATWG mailings list somewhat closely. One issue that has been raging quite ferociously recently was whether or not to include RDFa, eRDF, RDF, or whatever into HTML 5.

Many of my readers, especially those for whom RDF is immediately associated with cumbersome, inflexible APIs that should be rid from programs, are probably wondering why one would want to include such a specification into HTML 5. Don't worry, you're not alone. Even Ian Hickson, the editor of the HTML 5 spec, is having problems trying to figure out why. To whit:

One of the outstanding issues for HTML5 is the question of whether HTML5 should solve the problem that RDFa solves, e.g. by embedding RDFa straight into HTML5, or by some other method. Before I can determine whether we should solve this problem, and before I can evaluate proposals for solving this problem, I need to learn what the problem is.

A bit of context: earlier in 2008, there was a previous thread about RDF measuring well in excess of 100 messages. Being a good editor, Hixie asked in this message about what problems it was trying to solve. The response? Seventy-three email messages, most of which promptly ignored the issue. Many sub-discussions centered around things such as quality of search engines, how it should be implemented, etc. The idea of trying to figure out why people should use it got lost in the wind.

And to me, this signifies a problem. One of the most important questions when deciding whether or not to include a feature is why. And it seems to me that this question is the one that is least pondered by proponents of new features. The answer is often some variant of "it's obvious" or a description of what the feature does. The last bit is like trying to answer a question of "Why do you want to put a door in the wall here?" with an answer "Because we can have quicker access to the other side of the wall." At first glance, it's acceptable, but in reality, it doesn't justify the feature (why then, do you want quicker access?).

There are more instances where I've seen this. One of them that aggravates me the most is the proposal to include closures in Java. There are several conflating issues in the entire controversy, so here's some background. There are three proposals for closures: CICE (usually with ARM included), which really isn't a closures proposal, more of a "let's decrease anonymous inner class verbosity;" FCM, a "lite" version of closures which basically just makes methods first-class objects, and BGGA, which is full-blown closures support. By now, when people refer to a closure proposals, it's the full BGGA closure; FCM has all but disappeared, and CICE+ARM is generally only mentioned as a compromise opportunity.

The BGGA proposal can be viewed as roughly comprising three parts. The first is the idea of function pointers, the second is the ability to convert a function pointer to an interface so long as the interface has a single method and the function signatures match, and the third is (in a nutshell) the ability to create control structures. I have seen a lot of valid arguments on both sides for the first two portions, but the third portion still mystifies. Yet it is this third part which truly differentiated BGGA from FCM, and it is there where almost all of BGGA's complexity comes into play.

Just one catch: Why do you want or need the ability to create control structures? One control structure almost invariably pops out: the with construct, or (in other words) syntactic sugar for a try { ... } finally { ... } block. This is where the ARM portion of the CICE proposal comes in—it would add the only construct desired by any sizable amount of people. Okay then, that's one, how about another? And therein lies the problem. It's hard to come up with other examples. Proponents always mention the with and assume that everything else is evident. For something that is definitely going to increase complexity and difficulty in programming greatly (e.g., return 5 would behave differently, in some cases, than return 5;), you better have more than one, easily manually-addable use case.

Another problem is underestimation of what it takes to include a feature. A 16 MB extension for a 6 MB program is completely untenable, so let's include it into the 6MB program! How about introducing multiple tokens as a CSS unit token (think about it for a moment...)?

The final thing that irks me with feature requests is the importance with which people attach. The news that Java 7 will definitely not be containing closures (adding a complex, controversial feature to a specification already behind schedule isn't exactly tenable) seems to have been treated with proclamations that Java is dead or that it will die as a result. I somehow can't imagine that millions of Java programmers will suddenly switch because Java won't have closures—indeed, no programming languages ever in the Top 5 have ever had closures.

Similarly, the announcement that JavaScript had been disabled in trunk Thunderbird builds for email was met with a few vocal opponents complaining (I don't know of any non-Mozilla product that ever had support for JavaScript in email to begin with). And most of my readers are no doubt aware of the furor that removing MNG support caused.

News submodule roadmap

2009-01-04T23:19:00.002-05:00

It's the new year! As the owner of the NNTP submodule of Mozilla Mailnews, let me lay out a rough roadmap on what I seek to get done on the submodule for some time to come.

For Thunderbird 3 (and SeaMonkey 2.0, of course), the ability to filter on any header is probably in and of itself sufficient to make people happy. The only other change I think reasonable to make it into 3.0 is making get messages actually get messages. More substantive changes will have to wait for later.

For 3.next, I think the most important thing to tackle is news URIs, as they are incredibly broken for most practical purposes. High importance is ensuring that news://<server>/message-id and news://<server>/group are usable via external protocol handlers and command line. Making server-less URIs work would also be delightful.

Also important to me is more protocol support: AUTHINFO SASL, STARTTLS, and CAPABILITIES in roughly that order. While I'm at it, I'll also clean up some of the cruft surrounding nsNNTPProtocol. I would also like to have a lot more comprehensive tests for 3.next.

What's not on my plate is more binaries support. Specifically, I'll not be working on combine-and-decode (as useful as it is in general). Offline love I think will have to wait for 3.next.next before I can find some time to work on it.

Finally, I'd like to get all of the news bugs neatly triaged into categories. As of me writing this message, I count some 150 bugs in the Networking: News component, and I'm sure there are a few more bugs floating around in other components that I haven't found. I'd like to remove dupes and categorize all of these into specific categories (at least locally). And, more importantly, remove the cruft of these bugs. Many of the NEW bugs should be UNCO because no one ever really confirmed them.

A new address book public repo

2008-12-08T14:53:00.002-05:00

Veteran readers may recall my old posting of the address book rewrite repository. My original idea did not turn out so well—I had about 5 heads at one point because of review comments and simultaneous patches. Not to mention the history (though fun to look at) was a pain to try to follow.

I therefore created a brand new version of the repo. In the new one, I'm structuring things a bit differently. Rather than trying to keep one branch going, I'm going to have multiple named branches.

The first one is default, or the comm-central import. The tip of the default branch is the tip of comm-central when I imported that.

One set of branches is the experimental let's-add-new-address-book-type branches. I already have a prototype SQL AB developement branch, sqlab. When I start experimenting with Evolution support, there will be an evolutionab branch. And so forth and so on. If you have custom AB types that you want to publish, email me a bundle and you'll get your very own named branch in this repo (for as long as it exists).

Another set of branches is the bugs I'll be working on. These branches will tangle around each other as a fix one bug or another, since some bugs depend on other bugs. I'll try to keep a last-idl tag up-to-date such that any changes on a branch after the last branch point or this tag (which ever comes later) do not change any IDL files.

Debugging palmsync

2008-12-05T19:34:00.003-05:00

Also known as "An Exercise in Frustration and Self-Torture." As part of preliminary work for mailing list sanity, I need to make some changes to palmsync. It's not like I haven't changed this code before, but the work I need to do here is more than a simple s/a/b/g command. So, time to fire up the 'ole Windows partition and test.

Pain point number one: trying to get necessary stuff to work. First you need the Palm CDK. After getting that (complete with throw-away email account), you now need something to test the other end of palmsync—the PDA. Back at home, I have a monstrously old PDA whose functioning I would not guarantee. Fortunately, there's a nice palm emulator which I can install.

Now I just needed to Hotsync. Another non-trivial task, as my computer does not have two serial ports between which I could slap a cable (it doesn't even have one serial port…). After figuring that part out comes another problem. The palmsync failed to register. "No problem," I say, "I'll just reinstall it." And it still fails. Turns out that the necessary registry key used %ProgramFiles%. Don't you just love the registry?

That's all set up, so I click the sync button and… it fails. That wouldn't seem to be a problem, as I've already had to diagnose many errors to get to this point. Except I seem to have hit the critical unsupported limit:

I'm using a custom-built version of a program (that's really not saying much, though)
Said program is built with a technically unsupported compiler (VC 7.1)…
…which is unsupported on my OS (Windows Vista)…
…using and old SDK (Windows 2000)…
…and it's a 32-bit on a 64-bit machine.
The emulator officially supports neither Vista…
…nor a 64-bit machine.
Hotsync doesn't officially support the 64-bit machine either.

Debugging this proved to be a pain. The conduit logs didn't seem to function. Trying to get the VS debugger's nose in there proved a futile task until I did a world rebuild. Which takes 5.5 hours on my system (blame ext3). I finally got the debugger in, only to find a barrier thanks to COM. Some more work managed to shove the debugger in there and finally allowed me to pinpoint the error. Sorry, errors. Suffice to say that it's a mess in there.

So how did I get palmsync under the debugger? First off, let me describe my VS setup: I have mailnews as a project in VS (an NMake project, to be precise), set up such that clicking the build button actually builds in the mailnews directory (thanks to some custom hacking around msys). Based off of some external documentation for debugging Palm conduits, I created a new configuration (called "Palmsync," imaginative little me) whose command ran the hotsync program with -ic as its sole argument. Popping that under the debugger the normal way in VS allowed me to break on Palm's side of the conduit. On the Mozilla side, debugging is done by firing up an instance of TB under the debugger like normal, initiating the hotsync, and breaking and debugging as normal.

Modulo the fact that palmsync is in reality extremely fragile and apparently too buggy to support my nearly-empty testing profiling, it works now. Time to fix some more old bugs solely to be able to get to the point where I can work on the preliminary work for mailing list sanity.

ABC (meme)

2008-11-28T21:33:00.002-05:00

Everyone's doing this, it seems.

A: ActiveSync
B: Bug 71728
C: CSS 2.1 spec
D: Pork (on MDC)
E: Hiragana (Wikipedia)
F: FailBlog
G: comp.lang.java.programmer
H: Hunter × Hunter (manga)
I: I can has cheezburger?
J: Java Language Specification, Third Edition
K: OpenJDK
L: I can has cheezburger?
M: [ School resource ]
N: [ School resource ]
O: Bleach (manga)
P: Planet Mozilla
Q: Questionable Content (webcomic)
R: [ Anime video site ]
S: /. (Slashdot)
T: [ School resource ]
U: BOFH (web... column)
V: VGCats (webcomic)
W: Worse Than Failure
X: XKCD (webcomic)
Y: YouTube (specifically, part of a walkthrough for Golden Sun)
Z: Zero Punctation (web video columnist)

A public service announcement

2008-11-28T21:21:00.002-05:00

If you are a programmer who is writing code that will be released to the world as open source, this announcement is for you.

If your code will be seen by the world at large, one of your first tasks should be to write documentation. Document all functions as soon as you write them (before is also helpful). Provide samples on how to use code as soon as you finish a module (or earlier, if possible). Do not wait until your 5.0 release. Do not wait until your 1.0 release. Do not even wait until your 0.5 release. Do it as you write your code. The sooner, the better.

Users of your code will thank you profusely if you manage to provide comprehensive documentation along with the actual binaries of reference builds. DO NOT make them have to scour source code or bug developers in IRC channels to figure out a simple task like "get all cards from an address book" or "how do I write a synchronization conduit?"