20.10.11

Implementing mozilla::ArrayLength and mozilla::ArrayEnd, and some followup work

Tags: , , , , , , — Jeff @ 16:03

In my last post I announced the addition of mozilla::ArrayLength and mozilla::ArrayEnd to the Mozilla Framework Based on Templates, and I noted I was leaving a description of how these methods were implemented to a followup post. This is that post.

The C++ template trick used to implement mozilla::ArrayLength

The implementations of these methods are surprisingly simple:

template<typename T, size_t N>
size_t
ArrayLength(T (&arr)[N])
{
  return N;
}

template<typename T, size_t N>
T*
ArrayEnd(T (&arr)[N])
{
  return arr + ArrayLength(arr);
}

The trick is this: you can templatize an array based on its compile-time length. Here we templatize both methods on: the type of the elements of the array, so that each is polymorphic; and the number of elements in the array. Then inside the method we can refer to that length, a constant known at compile time, and simply return it to implement the desired semantics.

Templatizing on the length of an array may not seem too unusual. The part that may be a little unfamiliar is how the array is described as a parameter of the template method: T (&arr)[N]. This declares the argument to be a reference to an array of N elements of type T. Its being a reference is important: we don’t actually care about the array contents at all, and we don’t want to copy them to call the method. All we care about is its type, which we can capture without further cost using a reference.

This technique is uncommon, but it’s not new to Mozilla. Perhaps you’ve wondered at some point why Mozilla’s string classes have both EqualsLiteral and EqualsASCII: the former for use only when comparing to “an actual literal string”, the latter for use when comparing to any const char*. You can probably guess why this interface occurs now: EqualsLiteral is a method templatized on the length of the actual literal string passed to it. It can be more efficient than EqualsASCII because it knows the length of the compared string.

Using this trick in other code

I did most of the work to convert NS_ARRAY_LENGTH to ArrayLength with a script. But I still had to look over the results of the script to make sure things were sane before proceeding with it. In doing so, I noticed a decent number of places where an array was created, then it and its length were being passed as arguments to another method. For example:

void nsHtml5Atoms::AddRefAtoms()
{
  NS_RegisterStaticAtoms(Html5Atoms_info, ArrayLength(Html5Atoms_info));
}

Using ArrayLength here is safer than hard-coding a length. But safer still would be to not require callers to pass an array and a length separately — rather to pass them together. We can do this by pushing the template trick down another level, into NS_RegisterStaticAtoms (or at least into an internal method used everywhere, if the external API must be preserved for some reason):

static nsresult
RegisterStaticAtoms(const nsStaticAtom* aAtoms, PRUint32 aAtomCount)
{
  // ...old implementation...
}

template<size_t N>
nsresult
NS_RegisterStaticAtoms(const nsStaticAtom (&aAtoms)[N])
{
  return RegisterStaticAtoms(aAtoms, N);
}

The pointer-and-length method generally still needs to stick around somewhere, and it does in this rewrite here. It’s just that it wouldn’t be the interface user code would see, or it wouldn’t be the primary interface (for example, it might be protected or similar).

NS_RegisterStaticAtoms was just one such method which could use improvement. In a quick skim I also see:

…as potential spots that could be improved — at least for some callers — with some additional templatization on array length.

I didn’t look super-closely at these, so I might have missed some. Or I might have been over-generous in what could be rewritten to templatize on length, seeing only the one or two places that pass fixed lengths and missing the majority of cases that don’t. But there’s definitely a lot of cleaning that could be done here.

A call for help

Passing arrays and lengths separately is dangerous if you don’t know what you’re doing. The trick used here eliminates it, in certain cases. The more we can use this pattern, the more we can fundamentally reduce the danger of separating data from its length.

I don’t have time to do the above work myself. (I barely had time to do the ArrayLength work, really. I only did it because I’d sort of started the ball rolling in a separate bug, so I felt some obligation to make sure it got done.) And it’s not particularly hard work, requiring especial knowledge of the relevant code. It’s a better use of my time for me to work on JavaScript engine code, or on other code I know particularly well, than to do this work. But for someone interested in getting started working on Gecko C++ code, it would be a good first project. I’ve filed bug 696242 for this task; if anyone’s interested in a good first bug for getting into Mozilla C++ coding, feel free to start with that one. If you have questions about what to do, in any way, feel free to ask them there.

On the other hand, if you have any questions about the technique in question, or the way it’s used in Mozilla, feel free to ask them here. But if you want to contribute to fixing the issues I’ve noted, let’s keep them to the bug, if possible.

3 Comments »

  1. FYI, nsCSSScanner::ReportUnexpectedParams is only ever used with one-element arrays! And there’s a patch already to get rid of the arrays, in bug 455389, hopefully landing Real Soon Now.

    Comment by Zack — 20.10.11 @ 19:53

  2. Most people shouldn’t be using nsDependentString with a fixed-size array, so it’s unlikely that it’s worth templating it. I would also be surprised if nsTArray::AppendElements is usually used with an known number of elements.

    Comment by Neil Rashbrook — 22.10.11 @ 06:01

  3. [...] how these methods are defined, and what C++ magic is used? See my next post.) Comments [...]

    Pingback by Where's Walden? » Computing the length or end of a compile-time constant-length array: {JS,NS}_ARRAY_{END,LENGTH} are out, mozilla::Array{Length,End} are in — 22.12.11 @ 16:55

RSS feed for comments on this post. TrackBack URI

Leave a comment

HTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>