A couple days ago I found this ugly passage in a United States legal opinion:

The white race deems itself to be the dominant race in this country. And so it is in prestige, in achievements, in education, in wealth and in power. So, I doubt not, it will continue to be for all time if it remains true to its great heritage and holds fast to the principles of constitutional liberty.

Take a guess who wrote it, and in what context. A hint, then the answer, after the jump.

Snipped from irrelevant context:

<jorendorff> In this case I see nearby code asserting that IsCompiled() is true, so I think I have it right

Assertions do more than point out mistakes in code. They also document that code’s intended behavior, permitting faster iteration and modification to that code by future users. Assertions are often more valuable as documentation, than they are as a means to detect bugs. (Although not always. *eyes fuzzers beadily*)

So don’t just assert the tricky requirements: assert the more-obvious ones, too. You may save the next person changing the code (and the person reviewing it, who could be you!) a lot of time.

Managing dynamic memory allocations in C++

C++ supports dynamic allocation of objects using new. For new objects to not leak, they must be deleted. This is quite difficult to do correctly in complex code. Smart pointers are the canonical solution. Mozilla has historically used nsAutoPtr, and C++98 provided std::auto_ptr, to manage singly-owned new objects. But nsAutoPtr and std::auto_ptr have a bug: they can be “copied.”

The following code allocates an int. When is that int destroyed? Does destroying ptr1 or ptr2 handle the task? What does ptr1 contain after ptr2‘s gone out of scope?

typedef auto_ptr<int> auto_int;
{
  auto_int ptr1(new int(17));
  {
    auto_int ptr2 = ptr1;
    // destroy ptr2
  }
  // destroy ptr1
}

Copying or assigning an auto_ptr implicitly moves the new object, mutating the input. When ptr2 = ptr1 happens, ptr1 is set to nullptr and ptr2 has a pointer to the allocated int. When ptr2 goes out of scope, it destroys the allocated int. ptr1 is nullptr when it goes out of scope, so destroying it does nothing.

Fixing auto_ptr

Implicit-move semantics are safe but very unclear. And because these operations mutate their input, they can’t take a const reference. For example, auto_ptr has an auto_ptr::auto_ptr(auto_ptr&) constructor but not an auto_ptr::auto_ptr(const auto_ptr&) copy constructor. This breaks algorithms requiring copyability.

We can solve these problems with a smart pointer that prohibits copying/assignment unless the input is a temporary value. (C++11 calls these rvalue references, but I’ll use “temporary value” for readability.) If the input’s a temporary value, we can move the resource out of it without disrupting anyone else’s view of it: as a temporary it’ll die before anyone could observe it. (The rvalue reference concept is incredibly subtle. Read that article series a dozen times, and maybe you’ll understand half of it. I’ve spent multiple full days digesting it and still won’t claim full understanding.)

Presenting mozilla::UniquePtr

I’ve implemented mozilla::UniquePtr in #include "mozilla/UniquePtr.h" to fit the bill. It’s based on C++11’s std::unique_ptr (not always available right now). UniquePtr provides auto_ptr‘s safety while providing movability but not copyability.

UniquePtr template parameters

Using UniquePtr requires the type being owned and what will ultimately be done to generically delete it. The type is the first template argument; the deleter is the (optional) second. The default deleter performs delete for non-array types and delete[] for array types. (This latter improves upon auto_ptr and nsAutoPtr [and the derivative nsAutoArrayPtr], which fail horribly when used with new[].)

UniquePtr<int> i1(new int(8));
UniquePtr<int[]> arr1(new int[17]());

Deleters are callable values, that are called whenever a UniquePtr‘s object should be destroyed. If a custom deleter is used, it’s a really good idea for it to be empty (per mozilla::IsEmpty<D>) so that UniquePtr<T, D> is as space-efficient as a raw pointer.

struct FreePolicy
{
  void operator()(void* ptr) {
    free(ptr);
  }
};

{
  void* m = malloc(4096);
  UniquePtr<void, FreePolicy> mem(m);
  int* i = static_cast<int*>(malloc(sizeof(int)));
  UniquePtr<int, FreePolicy> integer(i);

  // integer.getDeleter()(i) is called
  // mem.getDeleter()(m) is called
}

Basic UniquePtr construction and assignment

As you’d expect, no-argument construction initializes to nullptr, a single pointer initializes to that pointer, and a pointer and a deleter initialize embedded pointer and deleter both.

UniquePtr<int> i1;
assert(i1 == nullptr);
UniquePtr<int> i2(new int(8));
assert(i2 != nullptr);
UniquePtr<int, FreePolicy> i3(nullptr, FreePolicy());

Move construction and assignment

All remaining constructors and assignment operators accept only nullptr or compatible, temporary UniquePtr values. These values have well-defined ownership, in marked contrast to raw pointers.

class B
{
    int i;

  public:
    B(int i) : i(i) {}
    virtual ~B() {} // virtual required so delete (B*)(pointer to D) calls ~D()
};

class D : public B
{
  public:
    D(int i) : B(i) {}
};

UniquePtr<B> MakeB(int i)
{
  typedef UniquePtr<B>::DeleterType BDeleter;

  // OK to convert UniquePtr<D, BDeleter> to UniquePtr<B>:
  // Note: For UniquePtr interconversion, both pointer and deleter
  //       types must be compatible!  Thus BDeleter here.
  return UniquePtr<D, BDeleter>(new D(i));
}

UniquePtr<B> b1(MakeB(66)); // OK: temporary value moved into b1

UniquePtr<B> b2(b1); // ERROR: b1 not a temporary, would confuse
                     // single ownership, forbidden

UniquePtr<B> b3;

b3 = b1;  // ERROR: b1 not a temporary, would confuse
          // single ownership, forbidden

b3 = MakeB(76); // OK: return value moved into b3
b3 = nullptr;   // OK: can't confuse ownership of nullptr

What if you really do want to move a resource from one UniquePtr to another? You can explicitly request a move using mozilla::Move() from #include "mozilla/Move.h".

int* i = new int(37);
UniquePtr<int> i1(i);

UniquePtr<int> i2(Move(i1));
assert(i1 == nullptr);
assert(i2.get() == i);

i1 = Move(i2);
assert(i1.get() == i);
assert(i2 == nullptr);

Move transforms the type of its argument into a temporary value type. Move doesn’t have any effects of its own. Rather, it’s the job of users such as UniquePtr to ascribe special semantics to operations accepting temporary values. (If no special semantics are provided, temporary values match only const reference types as in C++98.)

Observing a UniquePtr‘s value

The dereferencing operators (-> and *) and conversion to bool behave as expected for any smart pointer. The raw pointer value can be accessed using get() if absolutely needed. (This should be uncommon, as the only pointer to the resource should live in the UniquePtr.) UniquePtr may also be compared against nullptr (but not against raw pointers).

int* i = new int(8);
UniquePtr<int> p(i);
if (p)
  *p = 42;
assert(p != nullptr);
assert(p.get() == i);
assert(*p == 42);

Changing a UniquePtr‘s value

Three mutation methods beyond assignment are available. A UniquePtr may be reset() to a raw pointer or to nullptr. The raw pointer may be extracted, and the UniquePtr cleared, using release(). Finally, UniquePtrs may be swapped.

int* i = new int(42);
int* i2;
UniquePtr<int> i3, i4;
{
  UniquePtr<int> integer(i);
  assert(i == integer.get());

  i2 = integer.release();
  assert(integer == nullptr);

  integer.reset(i2);
  assert(integer.get() == i2);

  integer.reset(new int(93)); // deletes i2

  i3 = Move(integer); // better than release()

  i3.swap(i4);
  Swap(i3, i4); // mozilla::Swap, that is
}

When a UniquePtr loses ownership of its resource, the embedded deleter will dispose of the managed pointer, in accord with the single-ownership concept. release() is the sole exception: it clears the UniquePtr and returns the raw pointer previously in it, without calling the deleter. This is a somewhat dangerous idiom. (Mozilla’s smart pointers typically call this forget(), and WebKit’s WTF calls this leak(). UniquePtr uses release() only for consistency with unique_ptr.) It’s generally much better to make the user take a UniquePtr, then transfer ownership using Move().

Array fillips

UniquePtr<T> and UniquePtr<T[]> share the same interface, with a few substantial differences. UniquePtr<T[]> defines an operator[] to permit indexing. As mentioned earlier, UniquePtr<T[]> by default will delete[] its resource, rather than delete it. As a corollary, UniquePtr<T[]> requires an exact type match when constructed or mutated using a pointer. (It’s an error to delete[] an array through a pointer to the wrong array element type, because delete[] has to know the element size to destruct each element. Not accepting other pointer types thus eliminates this class of errors.)

struct B {};
struct D : B {};
UniquePtr<B[]> bs;
// bs.reset(new D[17]()); // ERROR: requires B*, not D*
bs.reset(new B[5]());
bs[1] = B();

And a mozilla::MakeUnique helper function

Typing out new T every time a UniquePtr is created or initialized can get old. We’ve added a helper function, MakeUnique<T>, that combines new object (or array) creation with creation of a corresponding UniquePtr. The nice thing about MakeUnique is that it’s in some sense foolproof: if you only create new objects in UniquePtrs, you can’t leak or double-delete unless you leak the UniquePtr‘s owner, misuse a get(), or drop the result of release() on the floor. I recommend always using MakeUnique instead of new for single-ownership objects.

struct S { S(int i, double d) {} };

UniquePtr<S> s1 = MakeUnique<S>(17, 42.0);   // new S(17, 42.0)
UniquePtr<int> i1 = MakeUnique<int>(42);     // new int(42)
UniquePtr<int[]> i2 = MakeUnique<int[]>(17); // new int[17]()


// Given familiarity with UniquePtr, these work particularly
// well with C++11 auto: just recognize MakeUnique means new,
// T means single object, and T[] means array.
auto s2 = MakeUnique<S>(17, 42.0); // new S(17, 42.0)
auto i3 = MakeUnique<int>(42);     // new int(42)
auto i4 = MakeUnique<int[]>(17);   // new int[17]()

MakeUnique<T>(...args) computes new T(...args). MakeUnique of an array takes an array length and constructs the correspondingly-sized array.

In the long run we probably should expect everyone to recognize the MakeUnique idiom so that we can use auto here and cut down on redundant typing. In the short run, feel free to do whichever you prefer.

Update: Beware! Due to compiler limitations affecting gcc less than 4.6, passing literal nullptr as an argument to a MakeUnique call will fail to compile only on b2g-ics. Everywhere else will pass. You have been warned. The only alternative I can think of is to pass static_cast<T*>(nullptr) instead, or assign to a local variable and pass that instead. Love that b2g compiler!

Conclusion

UniquePtr was a free-time hacking project last Christmas week, that I mostly finished but ran out of steam on when work resumed. Only recently have I found time to finish it up and land it, yet we already have a couple hundred uses of it and MakeUnique. Please add more uses, and make our existing new code safer!

A final note: please use UniquePtr instead of mozilla::Scoped. UniquePtr is more standard, better-tested, and better-documented (particularly on the vast expanses of the web, where most unique_ptr documentation also suffices for UniquePtr). Scoped is now deprecated — don’t use it in new code!

Spurred on by gps‘s recent mach blogging (and a blogging dry spell to rectify), I thought it’d be worth noting a new mach feature I landed in mozilla-inbound yesterday: build-complete notifications on Linux.

On OS X, mach build spawns a desktop notification when a build completes. It’s handy when the terminal where the build’s running is out of view — often the case given how long builds take. I learned about this feature when stuck on a loaner Mac for a few months due to laptop issues, and I found the notification quite handy. When I returned to Linux, I wanted the same thing there. evilpie had already filed bug 981146 with a patch using DBus notifications, but he didn’t have time to finish it. So I picked it up and did the last 5% to land it. Woo notifications!

(Minor caveat: you won’t get a notification if your build completes in under five minutes. Five minutes is probably too long; some systems build fast enough that you’d never get a notification. gps thinks this should be shorter and ideally configurable. I’m not aware of an existing bug for this.)

I said previously that I had two law posts to make. Here’s the non-Mozilla-related post.

Introduction

I’ve blogged about visiting the Supreme Court for oral arguments before. I had the opportunity to do so again for the extremely interesting week of January 13 earlier this year. I attended oral arguments concerning the Appointments Clause, assembly restrictions in Massachusetts, bankruptcy shenanigans, and railroad property law. A month ago, the first decision, in the property law case, Marvin M. Brandt Revocable Trust v. United States, was announced. I’m going to blog about it a little, because I think it’s cool and because of its impact on rail trails.

Before I do that, I’d like to note that the Marvin M. Brandt Revocable Trust v. United States article on Wikipedia is entirely my work (and my mistakes 🙂 ). (At present. Release the vandals in 3, 2, 1….) It’s the first article I’ve written start to finish. I’m more than a bit proud of that. And I’m particularly excited to have done it in such a cool area of law. 🙂

Background

Back in the 1800s as the United States expanded toward the Pacific Ocean, it needed to be able to efficiently transport goods and people across that distance. At the time, the solution was railroads. So Congress passed acts incenting railroad creation by granting rights of way across federal land. After initially granting rights of way to specific, named railroads in separate bills, Congress streamlined the process in the General Railroad Right-of-Way Act of 1875. Under this act, any railroad meeting certain conditions could get a right of way, til those provisions’ repeal in 1976.

The facts

Fast-foward to (coincidentally) 1976. The United States granted a land patent (that is, a document making clear — “patent” — title to land) to Melvin Brandt for 83 acres in Wyoming, as part of a land swap. One limitation on the grant was that it was subject to a railroad right-of-way originally granted to the Laramie Hahn’s Peak & Pacific Railway Company under the 1875 Act. The grant mentioned no other limitations on the right-of-way.

LHP&P never really worked as a railroad, and it passed through several hands. In 2004 the ultimate owners legally abandoned it. What happened to the right-of-way? This is where things got complicated.

The United States wanted the right-of-way land, so it filed suit to quiet title in its favor to clear up ownership. The United States resolved claims with everyone along the way — except for Marvin Brandt, Melvin’s son.

Brandt’s position

Brandt argued that the right of way was an easement. An easement is a restriction on your ownership of land, that says some other person can enter into and (perhaps) use it for some particular purpose. So your house’s land may have an easement across it for a sidewalk, that allows people to go on the sidewalk, walk through, and briefly stop on it, and you have to accept that. You still own the land; you just don’t quite have free rein over it. (This is why you’re usually responsible for clearing snow off your sidewalk. It’s your land, your fault if someone slips and twists an ankle and it was reasonably foreseeable.) When an easement terminates, the land is unburdened by the easement. No physical property changes hands, the easement just doesn’t exist, and the land owner can again prevent entry and use of his land.

Brandt buttressed this argument by pointing to Great Northern Railway Company v. United States. In this 1942 case, the Supreme Court decided whether Great Northern could drill for oil and gas on an 1875 Act right-of-way. The United States said no, it couldn’t — the right-of-way was in the nature of an easement, only an easement had been granted, all signs (language, legislative history, early interpretation, Congress’s construction of it in subsequent acts) said it was an easement. The 1942 Court agreed. Open and shut case for Brandt, right? Yes and no.

The United States’s position

The United States argued that 1875 Act rights of way were a “limited fee made on implied condition of reverter”. Let’s unpack this gibberish. “fee” is roughly “ownership”, and “reverter” refers to what happens to the property after some condition (here, abandonment) holds. The United States thought railroad rights of way were an unusual sort of easement. Easements don’t typically let you come in and tear things up, but it’s necessary for railroads to dig, bore, build up, lay track, and so on. So these “railroad easements” were a fee in those regards. And in regard to reversion after abandonment, ownership reverted to the United States.

In light of Great Northern, this may sound ridiculous. But the United States found language in earlier cases, and to an extent in Great Northern, saying that railroad easements had “attributes of the fee”. And two cases predating Great Northern had treated 1875 Act rights of way as limited fees. The problem was, in those cases the Supreme Court had conflated 1875 Act rights-of-way with rights-of-way under acts before 1871. In 1871, Congress changed policy from basically giving railroads land, to only letting them lay tracks on it. Congress wanted to encourage settlement, not just the arbitrary enrichment of railroads (who had become incredibly huge land owners in the West). The Court conflated the two because, in at least one of the cases, neither side had filed briefs, and the Court made a legal mistake.

The United States argued that Great Northern didn’t really say 1875 Act rights of way were easements.

Oral argument

Oral argument was pretty interesting. I read half a dozen briefs and the lower court opinion in the case, so I was moderately prepared to follow argument. In some ways I was almost on par with the justices. Justice Breyer candidly admitted to fumbling with his recollections of A. James Casner‘s property law class, about which he briefly rambled (as is his wont — he’s known for rambling 🙂 ).

Oral argument generally trended against the United States. Sparks flew when the United States attorney began argument. Justice Alito bluntly told him the United States should receive a “prize for understatement” for “acknowledg[ing in its brief] that there is language in [] Great Northern and in the government’s brief in that case that lends some support to [Brandt’s] argument.” Alito recited the brief’s subject headings, all forcefully arguing that the right-of-way was an easement and only an easement.

The argument didn’t go much better from there on for the United States. Various justices wanted to know how much land would be affected by a judgment that these rights-of-way were easements — permitting takings claims for just compensation, especially when the land had already been taken by the United States. No answer was forthcoming, because the records had been taken so long ago and were so geographically distributed. Breyer in particular repeatedly asked if there were any other easement-but-not-always constructs in the common law of property.

Opinions

The Court announced an opinion on March 10, just under two months after oral argument. Fast turnarounds typically indicate uncomplicated cases, and this was such a case. The justices divided 8-1 for Brandt, uncritically adopting his position. Chief Justice Roberts wrote the opinion, which began with a half-dozen pages of history of the West and particularly of LHP&P. (Definitely give it a read if you like Western history.) Roberts emphasized that the United States lost because it had won in Great Northern and faulted it for its “stark change in position”. He also asserted that 1875 Act railroad rights of way must be analyzed as common law easements — not a strange amalgam as the United States had argued.

Justice Sotomayor dissented alone. She argued that Great Northern had decided only one aspect of the property interest in railroad rights of way, and it hadn’t decided how reversion should play out. She also thought that railroad rights of way shouldn’t be analyzed under the common law, because of the extent to which they went beyond what normal easements allowed.

In the end the United States was roundly rebuked and defeated. Sometimes 8-1 decisions are a matter of some recognized, fundamental disagreement; see for example many of Justice Thomas’s solo dissents. But when a decision goes this way, in a case barely implicating deep jurisprudential disputes, you have to second-guess yourself a bit when you’re on the losing side. It’s one thing to lose with others agreeing with you. But when no one else sees it as you do, perhaps you’re the one who’s wrong.

Why did the United States pursue the case to a resounding loss? This particular case arose a bit weirdly. It was pushed by various property-rights groups, at the start. And for where it was raised, in the Tenth Circuit, existing circuit precedent said Brandt’s argument would lose, which it did. Brandt appealed to the Supreme Court, citing the circuit split: a good way to get your case heard, but no guarantee. What possibly tipped the balance was that the United States, despite winning, agreed the Court should hear the case. Why?

It looks to me like the United States got greedy. It saw an opportunity to wipe out the other circuits’ bad precedents, and it blinded itself to the weakness of its argument.

Consequences

What happens to Brandt specifically? The case returns to the Tenth Circuit to respond to the decision, but it’s unclear to me what’s supposed to happen there. I’d think they’d just quiet title in Brandt and be done, but the Rails-to-Trails Conservancy says it’ll keep working in the Tenth Circuit to “narrow the ultimate impact of the Supreme Court’s ruling”. How they can work against a predetermined quiet title action, I don’t know. (It’s possible this is just a face-saving claim on their part.) And it’s possible the United States might just acquire the right of way using eminent domain. (Why not do that and avoid suit? Money, of course. If it owns the land, no just compensation to pay. If not, that’s money out of the government’s pocket.) So Brandt’s not quite out of the woods yet, pun probably intended.

But Brandt’s particular plight isn’t the important thing here. It’s all the other places where suddenly takings claims can go forward. No one knows how many of these there are. Statutes of limitations and estoppel will preclude many claims, but not all of them. It’s still an unresolved mess.

Lessons

This touches a deeper concern. The United States acted here because it wanted to create rail trails, converting useless railroad corridors into bike trails. I like bikes. I like bike trails. But the law authorizing rail trails was enacted with flagrant disregard for the actual ownership of railroads in disuse. The CBO estimated the law wouldn’t cost a penny, but it now could cost $500 million, maybe more after this decision. We should demand a higher standard of Congress in the laws it passes.