Beyond the Code

Ignoring caught exceptions in the debugger

The debugger in Firefox has long had the option to pause the execution of a script when an exception is thrown. However, the problem with this ‘pause on exceptions’ option is that it always pauses on *all* exceptions.  Most of the time when debugging a script, we are only interested in pausing on exceptions that are not going to be caught.

To make the ‘pause on exceptions’ option more useful, I’ve added an option to ‘ignore caught exceptions’. When an exception is thrown with this option turned on (the default), the debugger first walks up the JavaScript call stack, and checks the return address for each frame. If one of these return addresses is in the scope of a catch block, the exception is ignored. You can find the bug page for this feature here.

To figure out whether a given bytecode address is in the scope of a catch block, I’ve used the set of try notes that SpiderMonkey generates for each script. These are used internally to implement stack unwinding when an exception is thrown, and completely describe the scope of each catch block. In other words: they are exactly what we need.

The above approach is straightforward, and works great 80% of the time. There are a couple of caveats that you should be aware of, however. Most importantly, if an exception will be caught by C++ code, there’s no way for us to tell up front, so the exception won’t be ignored in that case. This is not a problem for any web based code, but it might be a problem when debugging chrome code.

Since perfect detection is impossible, the best we can do is an approximation that doesn’t give us any false positives. Unfortunately, we currently cannot distinguish conditional catch blocks (which are a SpiderMonkey feature) from unconditional ones, so we do get such false positives if the condition evaluates to false (we will still ignore the exception in this case). This is a problem we can fix, however (conditional catch blocks have a well defined bytecode sequence that we can detect), and in any case, it’s not a problem for any web based code, since conditional catch blocks are only implemented in Firefox.

I’ve just landed the final patch on mozilla-inbound, so you should be able to start playing with this new feature soon. You can turn ignoring caught exceptions on or off in the debugger menu. Note that the option is turned on by default, so you might notice some change in the debugger’s default behavior:

Meeting with the Dutch Mozilla Community

A few weeks ago, I attended the first official meetup of the Dutch Mozilla community.

THE DUTCH MOZILLA COMMUNITY IS SPECIAL

The Dutch Mozilla community is somewhat special: we’ve been around for quite some time, but – up until now – have not been as active as some of the other Mozilla communities. In fact, this meeting is the first time I’ve met most of our members face to face, despite the fact that most of us have been active contributors for years!

There are a couple of reasons why our community has not been as active so far. First of all, the Dutch community is still relatively small. The Netherlands being a small country, after all (our total population is barely twice that of the bay area), means that the pool of potential contributors is smaller as well.

Secondly, not too long ago almost all of our members were involved with localization. You can’t expect localizers to have a deep understanding of how Firefox work under the hood, to attend lots of conferences, give technical talks, etc. Developers are much better suited for that role, and it has only been a couple of years since Mozilla has started to hire developers in the Netherlands in earnest.

Lastly, despite (or maybe because of) the fact my country is small, people have a different sense of distance here than say people in the US. Back there, 30 minutes is considered a short drive. Over here, anything taking longer than 30 minutes to reach is considered a long distance away. This makes us reluctant to attend events on the other side of the country (popular belief notwithstanding, not all of us live in Amsterdam ;-))

THE DUTCH MOZILLA COMMUNITY HAS A LOT OF POTENTIAL

Times are changing, however. Over the past few years, our community has been growing at a slow but steady rate. More importantly, the ratio of developers to non-developers is increasing as well. The combination of these two factors means there is a lot of untapped potential within the Dutch Mozilla community.

Bas Schouten, one of my Dutch colleagues, and a developer on the graphics team, recognised this, so he sent out an e-mail in which he proposed to organise a meetup. Brian King, our community manager in Europe, followed up on this by getting a small group of us together at FOSDEM earlier this year, where the final plans for the meetup were made.

We decided to organise the meetup in Utrecht, due to its central location and good accessibility. The good folks at Seats2Meet were kind enough to provide us with a meeting space:

The goal of the meetup was simple: figure out how the Dutch Mozilla community can do better. There is a lot we can do to increase awareness of Mozilla and our mission under the general public, and the developer community in particular. In addition, we can do a lot better in our attempts to gain new local contributors.

THE FIRST HALF OF THE DAY: TEAM BUILDING EXERCISES

The first half of the day consisted mostly of team building exercises. I was unsure what to expect of this at first (being an antisocial jerk, I generally detest team building. I also hate dancing and singing). However, it turned out to be really useful: it gave everyone a good idea of each other’s opinion on the state of our community.

One thing that really struck me was that a lot of people seemed to think our community isn’t welcoming enough to newcomers. This particularly hit home because I think this is a problem with Mozilla in general (maybe we’re hiring too many antisocial jerks). Though the situation has improved a lot since I started out, it is still too hard for newcomers to start contributing.

In general, I think we as individuals should put a lot more effort in encouraging and coaching new contributors. When someone finally makes the decision they want to contribute to Mozilla, the first few weeks are crucial. It is very easy to get discouraged during that time, either because you don’t know where to start, how to fix something if it doesn’t work, who to ask questions if you get stuck, etc.

If a new contributor gets discouraged, he’s likely to leave forever. Over time, that’s a huge loss. If they would have had someone to help them get started, point them to the right people when they have questions, or simply listen to their frustrations and try to resolve the problem, they might not have left, and we might have gained a valuable contributor for years.

All we need to do is put in the effort to help these people out, rather than leave them on their own. It really doesn’t take that much time, and I’m personally convinced that the pay off is worth it. I am committed to this, so I’ve decided to put myself not the forward list for people who express interest in contributing via our local website.

My hope is that I can present these people with a friendly face. Right now all these people are getting is an auto-reply e-mail. This is great if you’re committed to presenting yourself as a big faceless organisation, but that’s not what Mozilla is about. We can, and *should* do better than that.

THE SECOND HALF OF THE DAY: DISCUSSING STRATEGIES

The second half of the day consisted more of brainstorming and discussing strategies for improving our community. What I mostly took away from this is that we have to do better where it comes to establishing a presence for Mozilla at conferences, events, etc. The Netherlands has a vibrant and active web developer community, with several large annual events, such as Kings of Code, Mobilism, etc. We currently have no presence at any of these.

It’s critically important that we improve the visibility of Mozilla in the Netherlands. Competitors such as Google have put large amount of funds into local marketing campaigns for their browser. The Chrome logo is visible everywhere I go, from bus stops to television ads. The Firefox logo does not command the same amount of mass-awareness. We *need* to do better.

Since we can’t simply outspend the likes of Google on marketing, the only way we can improve our visibility is by relying on the community to promote our brand. There are several ways to accomplish this. The most obvious one I already mentioned: being present at events. Having a booth at the large conferences goes a long way, but it’s even more important to have speakers present. Speakers carry the Mozilla message to the outside world, and direct people to your booth in the process.

There are many other things we can do, besides conferences. In light of our goal of gaining more contributors, I’m enthusiastic about the idea of organising workshops or hackathons for web developers, and app developers in particular. I believe these would be a great way to promote Firefox, primarily because of our developer tools.

The devtools team has done a really awesome job. I believe our developer tools are now as good as, if not better than those of other browsers. This situation was very different only a short while ago, so many people who have become disappointed by Firefox and switched to another browser might not be aware how much better we have gotten since then. And what better way to showcase our developer tools than a workshop?

We also discussed whether it would make sense to organise workshops around Firefox OS. However, we quickly decided against it, because Firefox OS phones won’t be available in the Netherlands any time soon. On the other hand, workshops centred around mobile app development would be a great opportunity to promote Firefox OS.

The number of apps for Firefox is still relatively small. On the other hand we have a very large user base, so there are many opportunities here for mobile app developers. The message that you can make money developing for Firefox OS is an important one, and we would do well to drive it home.

CONCLUSION

The above things is what I mainly took away from our meetup. Overall, I think our it was extremely useful that we got together. Now, all we have to do is follow up on what we discussed. Like I said before, I am personally very excited about coaching new contributors and organising workshops. I would also love to speak more often at Dutch conferences.

Of course, we all have busy schedules, so it’s likely that not everything we want to do will materialize. However, as an open organisation committed to the idea of open source we have a responsibility to put ourselves out there, so I’m hoping we’ll see a lot more of each other in the months to come.

The are many other topics we discussed, but since I wasn’t directly involved with those, I don’t have as much to say about them. I’d like to wrap up by thanking Brian King and Tim van den Broek for their efforts in making this event happen. Furthermore, I would like to thank Alex Lakatos for coming along and moderating the brainstorm sessions. We could not have been effective without you, Alex. Thanks!

Last, but not least, a big thank you to everyone from the Dutch Mozilla community for being there in your free time. I had a great time meeting you all, and I hope to see you again at our next meetup!

My Take on the Donglegate Debacle

So I just read up on what’s called #donglegate (really? thats a thing now?) on Twitter. Apparently, a developer at PlayHaven got fired for making a sexually tinted joke at Pycon, after Adria Richards, a developer evangelist at SendHaven publicly called him out for it on her Twitter. Here’s the full story.

After having a somewhat spirited debate about it with @Niacursshi (who, by the way, proves that you can be passionate about a topic and still be respectful towards someone that disagrees with you. Kudos!) I felt like putting my thoughts on the matter on paper, so here goes:

I’d like to start by clearing two things up. First of all, under no circumstances, ever, is it acceptable to threaten someone with violence because you disagree with something they said or did. If you threatened Adria for what she did, you are a terrible human being, and do not deserve to live in a free country.

Second, Adria did not get those guys fired. That decision was made by PlayHaven, not her. She did, however, opt to publicly shame someone for what in my view was a private conversation. And that’s the part I’m not ok with.

What many people seem to be confused about is this: sexual and sexist are not the same thing. There is nothing mysogynist about two guys making penis jokes to each other. In fact, it turns out that women make penis jokes as well. Point in case? Adria herself:

 

Apparently, its ok for her to make sexual jokes in a public channel, but its not ok if men do it. If that’s not a double standard, I don’t know what is. Adria seems to think that only men can be sexist, because they are in a position of power. She made a similar point about racism a couple of years ago:

 

 

I’m sorry, but that’s not how it works. By making it seem that only men can be sexist when they make sexual jokes, you are in fact being sexist yourself, and in the process, pitting men and women against each other instead of bringing them together (as you should).

What upsets me more than most is that sexism *does* in fact exist in our industry, but it’s mostly hidden beneath the surface. This makes it very hard for women to speak up when they do run into it, and more often than not, they are not taken seriously.

By misrepresenting what sexism is, and looking for it in places where it is not, you are making a bad situation worse, and giving ammunition to people who’re trying to discredit women who speak up about real harrassment. You’re losing them valuable allies.

Update: I just saw some rumors on Twitter that Adria has been sacked. I hope that’s not the case. I think she did something naive at best, and hypocritical at worst. I’m criticising that behaviour, but I don’t think she deserved to be fired. Nobody did. It’s sad that our industry feels it needs to overreact to things like this.

What I Worked On During the DevTools Work Week

Last week, I was at the DevTools work week. For those of you who don’t know: I’m a member for the Jetpack team, which recently became part of the DevTools team, so this was the first time I met everyone on the team.

My primary role is that of platform developer, but good platform bugs for Jetpack have been hard to come by. DevTools, on the other hand, has dozens of platform bugs they would love to see fixed. As a result, this particular workweek was very exciting (and exhausting!)

Debugger Support

I spent most of my time hacking on bugs 808588, 816988, and 820012. These bugs are closely related, as they all amount to the same problem: we are currently unable to attach the debugger to certain scripts (Jim, if you are reading this, I’m sorry I used the word attach here). This particular problem also impacts the Jetpack team, since it makes it impossible to debug add-on scripts as well.

Panos Astithas already spent some time on bug 820012, and came very close to fixing it. The root of the problem was a bug in our algorithm for setting breakpoints. Panos wrote a patch to fix this, which partially solved the issue, but not enough for the problem to go away.

It took me some time to figure out what was going on, but in the end I decided to rewrite our algorithm for setting breakpoints completely. With this fix in place, we were able to attach the debugger to scripts loaded with nsIScriptLoader.

Unfortunately, we were still unable to debug add-on scripts, because another bug (bug 808960) makes it impossible to load add-on scripts in the debugger. In fact, half of the time, add-on scripts won’t even show up in the debugger in the latest Nightly.

To illustrate this, I created the most annoying add-on in the world. It listens for any tabs being opened, and automatically closes them again one second later. If we try to debug this add-on’s main.js script in the debugger, here is what we see:

As you can see, the add-on script doesn’t even show up. I created a patch for this problem too. With both patches applied, this problem goes away, and we are even able to set breakpoints in the add-on script, as you can see here below:

Being able to debug add-on scripts is extremely useful for add-on developers (it certainly is a lot nicer than console.log debugging!). Both patches already landed in Nightly, so you should be able to play with it right away.

One caveat though: it looks like one of my patches introduced a regression (bug 851836) that can cause Firefox to crash if you run into it. The issue is pretty rare though, and I’m already looking into it, so this problem should be resolved by the end of this week.

ES6 Modules

For those of you who are curious where we are at with ES6 modules: I also met up with Jason Orendorff during the work week. He is pretty overcommitted right now, so it was tough getting reviews from him for a while (I totally understand that by the way: one of the downsides of being awesome like Jason is that everybody wants your attention).

Unfortunately, as a result, most of the patches I wrote to add parser support for modules are now bit rotted (bug 568953), because of a refactor by Brian Hackett that splits the analysis and AST building parts of the parser up into separate parts. It’s going to take some time rebasing all of them and getting them landed, but Jason and I are going to look into that this week.

On the plus side, I also got a chance to talk to Jason about how module loader semantics are supposed to work. This part of the spec has been in flux for a while, but now seems to be stabilizing. Over the next couple of weeks, Jason and I will be translating this part of the spec into an implementation plan. Once we have that, we should be able to move forward a lot faster than we have so far.

Linus Torvalds is a terrible role model for the Open Source community

The main factor holding me back as a developer has always been my own lack of self-confidence. If I procrastrinate, it is usually because I feel intimidated by some piece of code. I wouldnt dive into C++ programming, because I felt I wasn’t smart enough for something like that. I wouldn’t dive into graphics programming, because that was something for people way smarter than me. And I certainly wouldn’t dive into something as complex as a JavaScript engine, because surely my tiny brain couldn’t comprehend something so complex.

That was a couple of years ago. Yet here we are, and I’ve done all of these things. Not only have I learned C++, I’ve actually become *good* at it (there, I said it). Meanwhile, I’m actually contributing to SpiderMonkey in a meaningful way, and the damn thing looks less and less like a black box to me. I’ve come a long way. But I can’t help but wonder. If I hadn’t been this unsure about my own abilities, how much farther could I have been by now? We have people like Tom Schuster (who I greatly admire, by the way) working on SpiderMonkey, and he’s still in high school. I wouldn’t have even dared to touch code like that at that age.

I suspect I’m not alone in this feeling. One of my favorite quotes is that writing code is not engineering, its a craft. That means it has an artistic aspect to it, something that is very personal, and people care deeply about. That’s why so many developers feel like you are attacking them personally when you insult their code. Surely, if my code sucks, that must mean I suck as a developer, right? It’s all to easy to get discouraged when that happens, or to give up on writing code all together.

Which brings me to my main point. Unless I really am the only developer out there who has self-confidence issues (and I really doubt I am), why are we collectively looking up to people like Linus Torvalds? Here is a man that seems to make it a point to be rude and obnoxious to people for no other reason that he can. A few famous examples are the Tanenbaum-Torvalds debate, this rant on C++, and the latest example, this explosion against a Red Hat developer.

Sure, more often than not, Linus has a valid point (I agree with all of his points in the above examples), but he could have made it with non of the obnoxiousness, and still get it across. Being obnoxious does not help to strengthen your argument, it only helps to antagonize people, and damage their self esteem. Being told in public that something you made, and by extension, *you* are moronic, can be extremely humiliating.

Some people learn not to take this kind of criticism personally. Most don’t. Saying that this is just the way the open source community works, so you have to deal with it, shows a complete disregard for the way most people work. We are not machines. We are human beings. We have feelings. To disregard those feelings as irrelevant is callous, and as far as I’m concerned signs of a narrow mind.

Other people accept this tone from Torvalds because he knows them personally, and they know he respects their work. While that may be ok, these interactions happen in public, and other people might not know that these two know each other. It still sends across the message that it is ok for developers to talk to each other like that.

Why do we accept this kind of behavior, even revere it? Is it because Torvalds is so much smarter than us, and we want to be just as smart as him one day? Does the fact that he acts condescending and rude towards other reinforce our view of him as some kind of programmer God? Or is it that by berating others, Torvalds makes us feel better about our own feelings of inadequacy?

No matter what the reason, Torvalds should know better than this. Whether he wants to or not, he is a leading figure in the open source community. Whatever he does is seen as a standard of what is acceptable in the community as a whole. Torvalds either doesn’t recognize this, or doesn’t care. He can be as obnoxious as he likes. He is Benevolent Dictator For Life, after all, and his kernel has become way too important to just ignore him.

Acting like a dick just because you can is not a sign of strong leadership, however. Even being passionate about something you care about (and Torvalds *is* passionate) is no excuse. A true leader doesn’t need to be obnoxious to get his point across. As long as we don’t stop revering people like Torvalds, however, it will be impossible to change that idea.

Linus Torvalds may be a great developer, but he’s a terrible role model for the Open Source community.

Why forcing your remote employees to become non-remote is a dick move

Yesterday, I read on AllThingsD that Marissa Mayer is confronting her remote employees with a choice: either work from an office, or quit. Being a remote employee myself, I couldn’t help but wonder what possible motivation she might have had for this decision. After thinking about it for a while, I can only conclude that this is a simple cost reduction move. By convincing remote employees to leave on their own account, Yahoo can avoid having to pay severance, which they are legally required to do if they simply lay them off.

I mean, think about it. Remote employees are remote for a reason. Do you really think we prefer working from home over working from an office? It might seem fun for a while, but it gets lonely really quickly. I miss the daily interaction you get with colleagues when working from an office. Idle conversation at the coffee machine may seem like a waste of time, but it reinforces the feeling that you’re part of a team, and more importantly: that there are people out there who care about your work. You need to be extremely self motivated in order to work from home.

Some people seem to have the preconception that remote employees prefer to work from home because it allows them to slack off without getting caught. This really ticks me off. People like that really have no idea what drives us as developers. I consider my job a huge privilege. I paid for doing what I love. How many people can say that? I am under contract for 32 hours a week, but nobody checks if I actually put in that many hours. That’s a huge amount of trust people put in you. Why on earth would I want to abuse that? If i have an unproductive day working from an office, at least I know I put in the hours that were expected of me. If I have an unproductive day working from home, I feel guilty writing those hours down, and I end up working in the weekends to catch up. If anything, I put in *more* hours when working remote, because it’s a lot harder to separate my work from my personal life.

So why do I work remote then? Because I have no choice. Mozilla has no office in the Netherlands. If they made the decision to force employees to work from an office tomorrow, I’d have to move to either Paris, London, or Berlin. Moving to another country is a huge transition. I have roots here: friends and family, not to mention a girlfriend that is highly reluctant to move abroad, that I’m not willing to give up just like that. I might eventually move abroad (I’ve really fallen in love with Toronto during my last visit), but then it will be because it’s *my* choice, not because my employer is forcing me into it.

Of course, it would have been different if Mozilla had told me that they’d only hire me if I’d agree to move to San Francisco. They’re not obliged to support remote employees, after all, and I could always just decide not to sign the contract and walk away at that point. That’s perfectly fine. But changing the rules halfway through the game? That’s just a dick move as far as I’m concerned. No job is worth making such life altering decisions for, unless it is *your* decision. And Yahoo! knows it. I would not be surprised if most Yahoo! employees decide to walk away instead of letting themselves be manipulated like this. That’s the point, after all.

By the way, if your argument is that remote employees are inherently less productive, because they have more barriers to deal with, I agree with you. Like I said earlier, its hard to stay motivated sometimes when you have no-one to talk to, and getting the information you need from someone over e-mail or irc is infinitely less efficient than just walking over to his/her desk and asking about it. However, keep in mind that the alternative is that would not able to work for Mozilla at all. I like to believe that my skills are still worthwhile, even when I’m not operating at 100% of my capacity. As long as I do my job well, my physical location shouldn’t matter.

In any case, if you want the benefits of allowing remote employees (having a global talent pool to fish from can be a real asset) but at the same time want to minimize the overhead associated with this, the right thing to do is not discouraging your employees from working remotely. Instead, you should do the opposite: encourage them to become local. Mozilla gets this. Yahoo! doesn’t, Either that, or their goal is not to minimize overhead, but simply to get rid of unwanted employees. I seriously doubt the former, since Marissa Mayer is a smart individual, but that really only leaves one explanation in my book.

Why I’m enthusiastic about the Add-on SDK

Why browser development is hard (and what we can do about it)

It should hardly come as a surprise to anyone when I tell you that browser development is hard.

Most browser code is written in C++. This is problematic for a number of reasons. First of all, C++ code takes a long time to compile. Compiling Firefox from scratch can easily take up to 15 minutes or more, even on a high-end system. This makes it very hard to quickly write and test something. On top of that, C++ code is error prone and hard to maintain.

Another problem is that as a project becomes older, it accumulates ‘cruft': design decisions which seemed like a good idea at the time but have proven to cause more problems than they solve, interfaces that were bypassed in order to gain a bit more performance, quick hacks that were added under deadline pressure etc.

In practice, the accumulation of cruft is impossible to avoid, and once it is there, it is nearly impossible to get rid of it, because other code has come to depend on it. As a result, cruft becomes an increasingly large burden as a project gets older. This is especially problematic when dealing with C++ code, for the reasons I mentioned earlier.

Since Gecko is an older project than WebKit, the problems it has due to cruft are correspondingly larger as well. Although WebKit is slowly starting to run into the same problems as we are, this makes it very hard for us to keep up. That we are able to do so at all is a testament to the the passion and skill of our contributors.

Having said that, the burden of cruft is not going away, and is only going to get worse over time, so we need a strategy to deal with it. The most obvious solution is to find more contributors. However, C++ has a high barrier of entry, making such contributors hard to find.

A better solution, which in my opinion we should be moving towards, is to keep only the performance critical code in C++, and move as much platform code as we can from C++ to JavaScript. Having less code in C++ will lead to reduced compilation times. On top of that, JavaScript is less error prone and easier to maintain, which will alleviate the burden caused by cruft.

How the Add-on SDK can help

To move platform code from C++ to JavaScript, JavaScript code needs to be able to call into C++ code. Within Gecko, we use two technologies to accomplish this: XPCOM and XPConnect. XPCOM is a component framework that allows you to write components in a language agnostic way, and XPConnect is a reflection layer that allows you to use components written in one language from the other language.

The problem with XPConnect is that it is cumbersome to use. It has a verbose API, and since XPCOM components are language agnostic, their interface can not use idioms that are common in JavaScript code, but not in C++ code, such as higher-order functions.

Because XPConnect is so painful to use, many add-on developers have written their own abstraction layer on top of it, in order to smooth over some of XPConnects rough edges, and to provide an API that feels more native to
JavaScript.

Unfortunately, almost every add-on developer write his own abstraction, so that almost every add-on reinvents the wheel in one way or another. Whenever something like that happens, its a sign that the API you are providing does not meet the needs of its users.

It’s from this observation that the idea for the Add-on SDK was born: the goal of the SDK is to provide a set of high-level platform APIs that feel native to JavaScript and are easy to use, on top of low-level APIs such as
XPConnect.

Originally, the Add-on SDK was primarily geared towards add-ons (hence the name). This is still reflected in the API’s we currently provide: these are mainly geared towards the kind of functionality we expect add-ons to require.

In the future, however, our goal is to make the Add-on SDK the SDK of choice for all new Firefox features, not just add-ons. By providing a powerful set of platform APIs in JavaScript, we hope to attract new contributors, and create a strong incentive to write as little platform code in C++ as possible. If we do our job right (and I’m really hoping we will), the Add-on SDK could be the solution to the cruft problem.

How to get there

As a first step towards making the SDK the platform API of choice, we need to make it part of Firefox itself. We just accomplished a major step in that direction by landing the SDK’s APIs and module loader on mozilla-central. They are on track to be shipped for Firefox 21.

Obviously, we are not there yet. Another step will be to figure out what kind of API’s we need to extend the usefulness of the SDK beyond that of creating add-ons. If those API’s are not powerful enough, or inconvenient to use,
platform developers will avoid them, so doing this step right will be crucial to our success.

Figuring out what kind of API’s we need will be one of the focuses of our upcoming workweek in March, during which we hope to get a much better picture of what kind of functionality platform developers expect from the SDK.

Last, but not least, another exicting development is that the SDK team has recently become part of the Developer Tools team. Developer Tools is a natural target audience for the SDK. By working closely together we hope to make the creation of developer tools easier, and improve the SDK at the same time.

Creating an add-on using the add-on SDK

Introduction

In this article, I’m going to talk about my experience creating a Firefox add-on using the add-on SDK. Although I’ve been a member of the add-on SDK team for some time now, I’ve never actually used the SDK to create an add-on. Dogfooding is extremely important if you want to deliver a high quality product, so it was time to remedy that situation.

Every add-on begins with an idea. Coming up with a good idea for an add-on is not as easy as I thought though. Almost every idea I came up with could be implemented as a webpage as well, so implementing it as an add-on would not have provided any added value.

So, in what cases does an add-on provide added value over a webpage? Well, for one thing, unlike a webpage, the lifetime of an add-on is not restricted to that of a single site. This makes an add-on the implementation of choice if you want to keep track of information over multiple sites. With that in the back of my head, I started thinking if there was some kind of information I would like to keep track of.

A big problem for me is that I’m easily distracted by websites such as Twitter. I probably spend way more time on such sites than I should, but I’ve never been able to quantify just how much. Wouldn’t it be neat if I could create an add-on that gave me an overview of what fraction of my time was spent on which websites? An idea was born.

Using the canvas API to draw pie charts

Before thinking about how to get the data I need, I wanted to have a way to visualise it. For this, I decided to use the canvas API. Although not particularly fast, canvas is great for making simple vector based drawings. The API is simple enough that even beginning programmers can create something awesome looking with it.

The code I wrote takes a table of key/value pairs, creates a histogram from it, and then draws the sectors of a pie chart based on that histogram. It also sorts the pie sectors from large to small, and groups the last sectors together so that there are never more sectors than available colors (I couldn’t come up with a good algorithm for picking colors, so I decided to hardcode those instead).

For those of you that are interested, the canvas code can be found here below:

function Pie(table) {
    this.table_ = table;
};
 
Pie.colors = [
    "#FF8080",
    "#80FF80",
    "#8080FF",
    "#FFFF80",
    "#FF80FF",
    "#80FFFF",
    "#808080"
];
 
Pie.prototype.draw = function (context, x, y, radius) {
    var total = 0;
    for (var key in this.table_) 
        total += this.table_[key];
 
    var sectors = [];
    for (var key in this.table_)
        sectors.push({
            name: key,
            frac: this.table_[key] / total
        });
 
    sectors = sectors.sort(function (a, b) {
        return b.frac - a. frac;
    });
 
    sectors = sectors.slice(0, Pie.colors.length - 1).concat([{
        name: 'Other',
        frac: sectors.slice(Pie.colors.length - 1)
                     .reduce(function (frac, sector) {
            return frac + sector.frac;
        }, 0)
    }]);
 
    var startAngle = -0.5 * Math.PI;
    context.strokeStyle = "#FFFFFF";
    sectors.forEach(function (sector, index) {
        var endAngle = startAngle + 2 * Math.PI * sector.frac;
        context.fillStyle = Pie.colors[index];
 
        context.beginPath();
        context.moveTo(x, y);
        context.arc(x, y, radius, startAngle, endAngle, false);
        context.lineTo(x, y);
        context.fill();
 
        context.beginPath();
        context.moveTo(x, y);
        context.arc(x, y, radius, startAngle, endAngle, false);
        context.lineTo(x, y);
        context.stroke();
 
        var angle = startAngle + (endAngle - startAngle) / 2;
        context.fillStyle = "#FFFFFF";
 
        context.beginPath();
        context.moveTo(x + Math.cos(angle) * radius,
                       y + Math.sin(angle) * radius);
        context.lineTo(x + Math.cos(angle) * (radius + 8),
                       y + Math.sin(angle) * (radius + 8));
        context.stroke();
 
        context.textAlign = angle < 0.5 * Math.PI ? "left" : "right";
        context.fillText(sector.name, x + Math.cos(angle) * (radius + 16),
                                      y + Math.sin(angle) * (radius + 16));
 
        startAngle = endAngle;
    });
};

Using the above code, and given a table of key/value pairs, a canvas context, and the desired x,y position and radius, drawing a pie chart is now as simple as writing the following two lines:

var pie = new Pie(table);
pie.draw(context, x, y, radius);

With the preliminary work now in place, we can start creating the actual add-on. My goal was to create an add-on that keeps track of how much time I spend on a particular webpage, and provides some interface that shows a pie chart from this data.

Using the timers API to periodically update a table

The first surprise I ran into is that setTimeout is not available as a global function in the main script of your add-on. It turns out that this is because add-ons do not run within the same environment as ordinary websites. That means the Window object isn’t there, and since it lives on the Window object, neither is the setTimeout function.

Luckily, the SDK developers were smart enough to recognise the importance of the setTimeout API, so they provided the same API as part of the SDK itself. Using this timers API, we can write some code that periodically updates a table based on the name of the current website (curName) and the time recorded during the previous update (oldTime):

var table = {};
var curName, oldTime;
 
function updateTable() {
    var newTime = new Date().getTime();
    table[curName] += newTime - oldTime;
    oldTime = newTime;
    require('timers').setTimeout(updateTable, 1000);
};
 
require('timers').setTimeout(updateTable, 1000);

Note the use of the require function above. This function is predefined, and is used to load external modules in your add-on script. The SDK provides a set of built-in modules, such as the timers module, that provides the timers API we discussed earlier. It is also possible to write your own modules and load those, allowing you to better structure your add-on.

Using the tabs API to obtain information about the active tab

The above code isn’t particularly useful yet. We still need a way to provide curName and oldTime with an initial value, and to update the value of curName when the user visits another page. I decided to write another function, setUrl, that is used for both purposes. It is called once on initialisation, and once every time the user switches to another page:

function setUrl(url) {
    var match = url.match(/\/\/([^\/]*)\//);
    curName = match && match[1] ? match[1] : url;
    if (!(curName in table))
        table[curName] = 0;
    oldTime = new Date().getTime();
}

Presumably, whenever setUrl is called, the value of url is the URL of the website the user is currently visiting. For simplicity, we are only interested in the domain part of the URL, so we use a regular expression to extract it. The only remaining problem now is how to tell when setUrl needs to be called, and how to obtain the value of the url parameter.

As it turns out, the SDK provides an API, called the tabs API, that allows us to manipulate and obtain information about the tabs bar in the browser. In particular, the tabs API allows us to obtain the currently active tab, and query it for the URL of the page it is currently displaying, which is what we’re interested in.

We could have used a polling scheme, querying the currently active page every second or so. Since we already use a timer to periodically update a table, this would fit nicely into our current design. In general, however, polling is inefficient, and the SDK provides a better way, in the form of event listeners.

The events that we are interested in are called activate, deactivate, and ready. The first two events are not associated with any particular tab, and are triggered when a tab becomes active/unactive. The latter is associated with a particular tab, and is triggered when a page load in that tab has completed. What we want to do is add a listener for the ready event when to a tab when it becomes active, and then remove it when it becomes unactive again, like so:

function onready(tab) {
    setUrl(tab.url);
}
 
function onactivate(tab) {
    setUrl(tab.url);
    tab.on('ready', onready);
}
 
function ondeactivate(tab) {
    tab.removeListener('ready', onready);
}
 
var tabs = require('tabs');
tabs.on('activate', onactivate);
tabs.on('deactivate', ondeactivate);

One gotcha I ran into with the above code is that when the add-on is loaded, the currently active tab is already active, so the activate event won’t be triggered for it. This is easily solved, of course, by calling the handler for the activate event explicitly:

onactivate(tabs.activeTab);

Using the panel API to display a HTML page in a panel

At this point, we have an add-on that keeps track of how much time the user spends on each website. All we need now is some interface that allows us to show a pie chart from this information. Since we used the canvas API, this interface needs to display a simple HTML page with a canvas element in it. It turns out that this is easy, since the SDK provides an API, called the panels API, that allows you to create separate windows (or panels) displaying a HTML page.

Here is the HTML page I created:

<html>
    <head>
    </head>
    <body>
        <canvas width='492' height='492'></canvas>
    </body>
</html>

And here’s the code that creates a panel for it:

var panel = new require('panel').Panel({
    width: 512,
    height: 512,
    contentURL: require('self').data.url('index.html'),
    contentScriptFile: require('self').data.url('panel.js')
});

The contentScriptFile property needs some explanation. As I explained earlier, add-ons run in a different environment than actual webpages. That includes webpages displayed in a panel. Therefore, if you want to run some script on this page, you need to provide that separately from the script for the add-on itself. You can’t just embed the script in the HTML page either, because you usually want some way for both scripts to communicate.

The SDK provides a solution for this problem, called content scripts. A content script is a script that you provide to your page using the SDK, and that can communicate with the add-on script using a simple message passing API. This is probably best illustrated by an example. Here is the content script that I used for the panel (it also contains the pie chart code I showed earlier, but thats not displayed here):

self.port.on('draw', function (table) {
    var canvas = document.getElementsByTagName('canvas')[0];
    var context = canvas.getContext('2d');
    context.clearRect(0, 0, canvas.width, canvas.height);
    var pie = new Pie(table);
    var x = canvas.width / 2;
    var y = canvas.height / 2;
    var radius = 0.5 * Math.min(x, y);
    pie.draw(context, x, y, radius);
});

This code draws a pie chart in response to some event. The self.port object is provided to the content script by the SDK, and allows it to listen to the arrival of events sent by the add-on script. All we need now is for the add-on script to send an event to the content script whenever the table is updated. I did this by adding a single line to the updateTable function I showed earlier):

function updateTable() { 
    var newTime = new Date().getTime();
    table[curName] += newTime - oldTime;
    oldTime = newTime;
    panel.port.emit('draw', table);
    require('timers').setTimeout(updateTable, 1000);
};

Using the widget API to show a panel

We’re almost done! The only remaining problem is this: when a panel is created, it does not automatically appear. The last thing we need is therefore some interface that allows users to show/hide the panel at any given time. This is where the widget API comes in. The widget API provides a very simple means of adding an icon to the add-on bar in Firefox, and associating some behaviour with it. In fact, widgets and panels are so closely associated that there’s even some special property to associate a panel with a widget directly:

var widget = new require("widget").Widget({
    id: 'widget',
    label: 'My Addon',
    contentURL: "http://www.mozilla.org/favicon.ico",
    panel: panel
});

Conclusion

That’s it. Were’ done! The picture here below shows a screenshot of the final result:

We’ve used the canvas API to draw a pie charts, the timers API to periodically update a table, the tabs API to obtain information about the active tab, the panel API to display a HTML page in a panel, and the widget API to show the panel.

Hopefully, this little post-mortem has given you some idea on what it takes to create add-ons using the SDK. The API’s that it provides are straightforward, and powerful enough for almost every basic task you can come up with. The concept of content scripts takes a bit of time getting used to, but the SDK developers have gone through great lengths to make sure that they are easy to use.

How Strings Are Implemented In SpiderMonkey

In this article, I am going to explain how SpiderMonkey, the JavaScript engine used by Firefox, implements strings. Strings are an important part of any scripting language, and JavaScript is no exception. Because they are so important, JavaScript includes strings as a primitive data type. Primitive data types are directly supported by the language, and as such it is the responsibility of the engine to implement them.

Because most scripts make extensive use of them, it is important that strings are implemented as efficiently as possible. For instance, concatenating multiple strings is a common operation in most scripts. In a naive implementation, this operation would take O(n2) steps (where n is the sum of the lengths of the strings involved). In a more sophisticated implementation, this operation would take only O(n) steps.

SpiderMonkey’s string implementation is quite sophisticated. The current iteration has mostly been the work of Luke Wagner and Alan Pierce, two of our super smart engine hackers. Unfortunately, because it is so sophisticated, the implementation is also quite complex. To manage this complexity, the implementation has been broken up into multiple classes, and organized into a single inheritance hierarchy. This class hierarchy will be the subject of the first section.

For maximum efficiency, SpiderMonkey contains multiple string implementations, each of which corresponds to a different class. Because each implementation is appropriate in different situations, we want to be able to switch between implementations at run-time. This is something that is normally not possible without introducing another level of indirection. This extra level of indirection can be avoided by implementing inheritance with tagged unions instead of virtual functions. Tagged unions will be discussed in section two.

Class Hierarchy

In this section, I will give an overview of the different classes that make up SpiderMonkey’s string implementation, and how they are related to each other. All string classes are organized into a single inheritance hierarchy, as shown by the following class diagram:

At the top of the hierarchy, we find the class JSString. For each string in JavaScript, there is a corresponding instance of this class. Conceptually, a JSString is just an array of jschars with a given length. Under the hood, however, its implementation might be completely different; for maximum efficiency, SpiderMonkey contains multiple implementations of JSString, each of which is appropriate in different situations.

The boxes labeled in white represent concrete classes. Each concrete class corresponds to a particular implementation of JSString. For instance, JSRope is optimized to represent concatenated strings, and JSDependentString to represent substrings. Later in this article, each concrete class will be discussed in more detail.

The boxes labeled in gray represent abstract classes. Each abstract class establishes one or more invariants. An invariant is a guarantee that a concrete class must implement. For instance, any concrete class that inherits from JSLinearString must represent a string as a contiguous array of jschars. Abstract classes and their invariants will be discussed in a later section.

Tagged Unions

In the previous section, I introduced the class hierarchy that makes up SpiderMonkey’s string implementation. In this section, I will explain how inheritance is implemented in this hierarchy.

In C++, inheritance is traditionally implemented with virtual functions. Instead, we use something called tagged unions. Tagged unions have several advantages over virtual functions. First of all, they are often more efficient. More importantly, however, they allow an object to change it type at run-time. This allows us to switch string implementations without introducing another level of indirection.

To implement a class hierarchy with a tagged union, we need to know all the classes in the hierarchy up front. Then, instead of storing the representation of each class in the class itself, we store them in the class at the top of the hierarchy. Because only one representation is needed at once, we store all of them into a single union, combined with a type field that indicated the one currently in use. This combination of a type field and a union is what tagged unions derive their name from.

To better understand how tagged unions can be used to implement inheritance, consider the following example:

class A {
public:
    bool isB() const
    {
        return type == TYPE_B;
    }
 
    bool isC() const
    {
        return type == TYPE_C;
    }
 
    B&amp; asB()
    {
        assert(isB());
        return *(B *) this;
    }
 
    C&amp; asC()
    {
        assert(isC());
        return *(C *) this;
    }
 
    void f()
    {
        if (isB())// do stuff specific to B
        else {
            assert(isC());// do stuff specific to C
        }
    }
 
private:
    enum {
        TYPE_B,
        TYPE_C
    } type;
    union {
        struct {} B;
        struct {} C;
    } data;
};
 
class B : public A {
public:
    void g(); // do stuff specific to B};
 
class C : public A {
public:
    void h(); // do stuff specific to C};

Suppose we start out with a pointer to an object of class A. To access any of the methods in class B or C via this pointer, we first have to perform a run-time check whether the object it points to is actually of this type. This check is performed by calling the method A::isB or A::isC, respectively. Only when the check succeeds can we cast the object to the respective class, by calling the method A::asB or A::asC, respectively.

Abstract Classes

In the previous section I explained how tagged unions can be used to implement inheritance. We are now ready to take a closer look at the individual classes that make up SpiderMonkey’s string implementation. This section begins by introducing the abstract classes.

The abstract classes are JSString,  JSLinearString, and JSFlatString. These classes do not correspond with any particular string implementation. Instead, as I explained earlier, their purpose is to establish one or more invariants for the classes that inherit from it.

An invariant is a guarantee that a concrete class must implement, without any dynamic checks. Examples of such invariants are that the string must be represented as a contiguous arrays of jschars, or that it must be zero-terminated (neither of these invariants are true in general). As a general rule, the farther we go down in the class hierarchy, the stronger the invariants established by each class.

The class JSString, being at the top of the hierarchy, is the most abstract class. Classes that inherit from it are required to implement a string with a given length, but nothing else. The class JSLinearString, which inherits from JSString, establishes the same invariant, but adds the requirement that classes that inherit from it must represent this string as a single contiguous array of jschars. Similarly, the class JSFixedString establishes the same invariants as JSLinearString, but adds the requirement that the string must be zero-terminated.

The following table gives an overview of each abstract class and their corresponding invariants:

JSString provides two methods, ensureLinear and ensureFlat, that are used to ensure that its underlying implementation inherits from JSLinearString or JSFlatString, respectively. The general usage pattern when working with JSStrings is this:

  1. Establish the invariants that you want your string to have.
  2. Make sure the string satisfies these invariants by calling either ensureLinear or ensureFlat
  3. Use the string by accessing it through the resulting abstract class.

Let’s take a closer look at the implementation  of ensureLinear and ensureFlat:

JS_ALWAYS_INLINE JSLinearString *
JSString::ensureLinear(JSContext *cx)
{
    return isLinear()
           ? asLinear()
           : asRope().flatten(cx);
}
 
JS_ALWAYS_INLINE JSFlatString *
JSString::ensureFlat(JSContext *cx)
{  
    return isFlat()
           ? asFlat()
           : isDependent()
             ? asDependent().undepend(cx)
             : asRope().flatten(cx);
}

The methods JSRope::flatten and JSDependentString:: undepend convert a JSRope to a JSExtensibleString, and a JSDependentString to a JSFixedString, respectively, by changing the class of the object at run-time, something that is only possible because we implemented inheritance with tagged unions.

JSFixedString

In the previous section, I introduced the abstract classes, and explained how they are use. Now it’s time to move on to the concrete classes. This section begins by introducing the simplest concrete class, JSFixedString.

The class JSFixedString inherits from JSFlatString. Therefore, it must be implement a string with a given length that is represented as a contiguous, zero-terminated array of jschars. It does this by explicitly storing a length and a pointer to the zero-terminated array:

When working with pointers in C, an important concept is that of ownership. A pointer that has been obtained with a call to the function JS_malloc is said to be owned. The owner of a pointer is responsible for issuing the corresponding call to the function JS_free when the memory pointed to is no longer needed.

A JSFixedString is initialized with an owned pointer. That is, to initialize a JSFixedString, a block of memory is allocated with a call to JS_malloc, its contents initialized with a C-style string, and then a pointer to this block is passed as an argument to JSFixedString‘s constructor. On initialization, a JSFixedString is said to grab ownership of this pointer, which means that it becomes responsible for issuing the corresponding call to JS_free.

Because of a JSFixedString grabs ownership of its pointer, you should never initialize it with an unowned pointer, because such a pointer is by definition already owned by somebody else. Moreover, since a JSFixedString calls JS_free as soon as it’s finalized or converted into something else, you should never initialize it with a pointer that is used by other objects if the lifetime of those objects extends that of the JSFixedString itself. Otherwise, JSFixedString will call JS_free on this pointer, before the other objects are deleted, causing their copies of the pointer to become invalid.

The SpiderMonkey API provides two functions, JS_NewStringCopyN and JS_NewStringCopyZ, that can be used to create instances of JSFixedString.

JSExternalString

In the previous section, I introduced the class JSFixedString. I also explained that you shouldn’t try to initialize this class with an unowned pointer. In some cases, that is really what you want though, for instance when you have a pointer that is managed by some third party library over which you have no control (you could always make a copy of course, but that is needlessly inefficient).

This section introduces the class JSExternalString. This class is a specialization of JSFixedString; it behaves almost exactly the same, except for one difference: it does not grab ownership of its pointer. This means you can initialize a JSExternalString with an unowned pointer without having to make a copy:

The SpiderMonkey API provides a single function, JS_NewExternalString, that can be used to create instances of JSExternalString. Use this function with care though: since a JSExternalString never calls JS_free on its pointer, you are responsible for doing so.

Not calling JS_free on a pointer when it is no longer being used can easily lead to memory leaks, so even though JSExternalString is more efficient, it is almost always better to use JSFixedString, since that class keeps track of when to call JS_free for you. Sure, this takes one extra string copy, but the performance impact of this is almost always negligible.

If you do decide to use JSExternalString, though, you need to know when each instance is finalized. After all, you should not call JS_free on a pointer when it is still being used by an instance of JSExternalString. The SpiderMonkey API provides a single function JS_AddExternalStringFinalizer, which is used to register a callback that will be called each time an instance of JSExternalString is finalized.

JSInlineString

The previous sections introduced the classes JSFixedString and JSExternalString. These classes represent a string as a pointer to a block of memory on the heap. These blocks need to be allocated, and these allocations are relatively expensive. In particular, when dealing with large numbers of small strings, heap allocations can quickly become expensive.

This section introduces the class JSInlineString. This class is an optimization of JSFixedString; it represents a string as a pointer to a block of memory inside the object itself (hence the term inline):

Because we use a tagged union, every string class shares the same representation. Therefore, the representation of the simplest class has the same size as that of the most complex one. JSInlineString exploits this by using the unused part of the representation as inline storage. The number of characters that can be stored this way is 2 * sizeof(void *) / sizeof(jschar). Since jschars are 16-bit, on a platform with 32-bit pointers this allows us to store strings of up to 4 characters long.

The SpiderMonkey API does not provide any functions to create instances of JSInlineString. They are only created implicitly, as optimization in functions that are normally create instances of JSFixedString.

JSShortString

In the previous section, I introduced the class JSInlineString. This class can store strings of up to 4 characters long without allocating a memory block on the heap. The only problem is: 4 characters isn’t all that long. Most short strings are longer than 4 characters. This limits the usefulness over JSInlineString as an optimization.

This section introduces the class JSShortString. This class is a further optimization of JSInlineString; it can store most short strings without allocating a memory block on the heap:

Because JSInlineString already takes up the entire representation as inline storage, the only way for JSShortString to store longer strings is by increasing the size of its representation. When an instance JSShortString is created, it is allocated from a different memory pool than the other string classes, using a memory block that is twice as large.

The fact that instances of JSShortString are allocated from a different memory pool makes them somewhat special. In particular instances of JSShortString cannot change their type at run-time (since that would require them to move to the main memory pool). Fortunately, this is not a problem, since JSShortString already inherits from JSFlatString, and there is never a need to convert an object to a more abstract type.

As with JSInlineString, instances of JSShortString are only created implicitly.

JSDependentString

In this section, I will introduce the concrete class JSDependentString. This class is optimized to represent substrings. Before we can understand how and why it works, however, we must first know a few things about how substrings are created.

Let s be a string with length n. Suppose we want to create a substring s’ of s with length n’. The naive method to creating a substring consists of the following 3 steps:

  1. Allocate a memory block s’ of size n + 1:
  2. Copy n’ bytes from s to s’:
  3. Set the last byte of s’ to ‘\0′:

Now suppose we want to create a substring s” of the substring s’ with length n”. Again, using the same 3 steps as before:

  1. Allocate a memory block s” of size n” + 1:
  2. Copy n’ bytes from s’ to s”:
  3. Set the last byte of s” to ‘\0′:

To create a substring of a substring this way we had to allocate 2 blocks of memory and copy n’ + n” bytes. In general, to obtain the k-th substring of a string with length n would take O(n2) steps using this method.

Not surprisingly, the naive way to obtain substrings is needlessly inefficient. The intermediate result s’ is never used for anything other than computing the final result s’‘, so it would have been more efficient to compute s” directly. Unfortunately, we can’t tell if s’ will only be used as an intermediate result when it is created. Even if we could, we can’t simply skip its creation, because s” is defined in terms of s’, not s.

The solution here is to use something called lazy evaluation: instead of creating the substring immediately and storing the result, we store everything that is needed to create the substring at a later time, when the result is actually needed. When such a “delayed” substring is used to create another substring, they can be combined to form a single composite operation:

As you can see in the image above, this is exactly what JSDependentString does: it stores a pointer to the original string (the base), a pointer into the base string that marks the start of the substring, and the length of the substring, so that it can be obtained at a later time. The base is an instance of JSLinearString.

Since JSDependentString inherits from JSLinearString, it can serve as the base of another substring, thus creating a composite operation. When the substring is actually needed inside the engine, a JSDependentString can be converted to a JSFixedString, by calling the internal method JSDependentString::undepend.

The SpiderMonkey API provides a single function, JS_NewDependentString, that can be used to obtain instances of JSDependentString. As should be obvious by now, it is recommended to use this function whenever possible, since it is often more efficient than creating a substring directly.

JSRope

In this section, I will introduce the concrete class JSRope. This class is optimized to represent concatenations. Before we can understand how and why it works, however, we must first know a few things about how concatenations are created.

Let s1, s2 and s3 be strings with lengths n1, n2 and n3, respectively. Suppose we want to concatenate s1 and s2 to form the string s1s2. The naive method to concatenate two strings consists of the following 4 steps:

  1. Allocate a memory block s1s2 of size n1 + n2:
  2. Copy s1 to the first n1 bytes of s1s2:
  3. Copy s2 to the next n2 bytes of s1s2:
  4. Set the last byte of s1s2 to ‘\0′:

Now suppose we want to concatenate s1s2 and s3 to form the string s1s2s3. Again, using the same 4 steps as before:

  1. Allocate a memory block s1s2s3 of size n1 + n2 + n3 + 1:
  2. Copy s1s2 to the first n1 + n2 bytes of s1s2s3:
  3. Copy s3 to the next n3 bytes of s1s2s3:
  4. Set the last byte of s1s2s3 to ‘\0′:

To concatenate 3 strings this way we had to allocate 2 blocks of memory and copy 2 * (n1 + n2) + n3 + 1 bytes. In general, to concatenate k strings s1, s2, …, sk with lengths n1, n2, …, nk, respectively, would take O(N2) steps using this method (where N = n1 + n2 + … + nk).

Obviously, for large N, the naive method to concatenate strings quickly becomes too expensive. Can we do better? It turns out that we can. To understand how, let’s take another look at our previous example of concatenating 3 strings. It should be obvious that the intermediate result in this computation, s1s2, is never used for anything other than computing the final result s1s2s3.

The creation of s1s2 could have been avoided had we known the lengths of all the strings to be concatenated in advance. In that case, we could have concatenated all three strings at once, using the following 5 steps:

  1. Allocate a memory block s1s2s3 of size n1 + n2 + n3 + 1:
  2. Copy s1 to the first n1 bytes of s1s2s3:
  3. Copy s2 to the next n2 bytes of s1s2s3:
  4. Copy s3 to the next n3 bytes of s1s2s3:
  5. Set the last byte of s1s2s3 to ‘\0′:

To concatenate 3 strings this way we had to allocate 1 block of memory and copy n1 + n2 + n3 + 1 bytes. In general, to concatenate k strings s1, s2, …, sk with lengths n1, n2, …, nk, respectively, would take O(N) steps using this method (where N = n1 + n2 + … + nk).

It should be obvious that the above method to concatenate strings is much more efficient than the naive one. However, it critically depends on the assumption that the lengths of all the strings to be concatenated are known in advance. Unfortunately, in most code, this assumption simply does not hold, as the following example shows:

while (...)
    s += ...

The solution here is to use lazy evaluation again: instead of creating the concatenation immediately and storing the result, we store everything that is needed to create the concatenation at a later time, when the result is actually required. When such a “delayed” concatenation is used to create another concatenation, they can be combined to form a single composite operation:

As you can see in the image above, is is exactly what JSRope does: it stores a pointer to the left and right hand sides of a concatenation, so that it can be performed at a later time. Both sides of the concatenation are instances of JSString.

Since JSRope inherits from JSString, it can serve as the left or right hand side of another concatenation, thus creating a composite operation. When the concatenation of the concatenation is actually needed inside the engine, a JSRope can be converted to an JSExtensibleString, by calling the internal method JSRope::flatten (the reason why we convert to aJSExtensibleString instead of a JSFixedString will become clear in the next section).

The SpiderMonkey API provides a single function, JS_ConcatStrings, that can be used to concatenate strings using JSRope (note that JS_ConcatString does not always create a JSRope though, since it contains several other optimizations).

JSExtensibleString

In this section I will introduce the cass JSExtensibleString. This class implements a performance optimization for the JSRope::flatten algorithm. To understand why we need this optimization, and how it works, read on below.

As we’ve seen in the previous section, by using JSRope, we can reduce the complexity of code that exhibits the pattern here below from O(N2) to O(N):

while (...)
    s += ...

Traditionally, most engines, including SpiderMonkey, have also been able to run code that exhibits the pattern here below with a complexity of O(N):

while (...) {
    s += ...
    s.flatten()
}

Using JSRope doesn’t save us in this case, since it’s flattened immediately after it’s creation. Without JSRope, we can’t tell the lengths of all the strings to be concatenated in advance, so we have to fall back to the naive method for concatenating strings.

Let s1, s2 and s3 be strings with lengths n1, n2 and n3, respectively. Suppose we want to concatenate them to form the string s1s2s3. Using the naive method for concatenating strings, we would first have to create the intermediate string s1s2:

However, we can improve the performance of the naive algorithm at this point by allocating a larger block of memory for s1s2 than strictly necessary in the first step, say 2p bytes, where p is the smallest integer such that n1 + n2 + 1 <= 2p:

If we are lucky, n1 + n2 + n3 + 1 <= 2as well, so that when we want to concatenate  s1s2 and s3 to form s1s2s3, we can simply copy s3 into s1s2‘s extra space, thus avoiding both an allocation and a string copy:

Because sometimes n1 + n2 + n3 + 1 > 2p, this optimization doesn’t always work. However, by allocating memory in this manner, as the smallest power of two that is still large enough to contain the result, we have reduced the complexity to O(N) on average (where N is the total length of the strings to be concatenated), even though some operations are more expensive than others.

The class JSExtensibleString is responsible for implementing the above performance optimization. It is very similar to JSFixedString, except that it allocates its own memory (so it can never contain external pointers), and stores an additional capacity, which is the actual amount of memory it allocated (as opposed to the amount it actually needs, i.e. the length + 1):

Perhaps surprisingly, the SpiderMonkey API does not provide any functions to create instances of JSExtensibleString. They are only created indirectly, as a result of calling the internal method JSRope::flatten on a JSRope.