diff --git a/re2/parse.cc b/re2/parse.cc
index 8471b3f..bbb8eb0 100644
--- a/re2/parse.cc
+++ b/re2/parse.cc
@@ -102,6 +102,11 @@
 
   // Processes the end of input, returning the final regexp.
   Regexp* DoFinish();
+  
+  // Finishes the regexp if necessary, preparing it for use
+  // in a more complicated expression.
+  // If it is a CharClassBuilder, converts into a CharClass.
+  Regexp* FinishRegexp(Regexp*);
 
   // These routines don't manipulate the parse stack
   // directly, but they do need to look at flags_.
@@ -174,6 +179,24 @@
   }
 }
 
+// Finishes the regexp if necessary, preparing it for use in
+// a more complex expression.
+// If it is a CharClassBuilder, converts into a CharClass.
+Regexp* Regexp::ParseState::FinishRegexp(Regexp* re) {
+  if (re == NULL)
+    return NULL;
+  re->down_ = NULL;
+
+  if (re->op_ == kRegexpCharClass && re->ccb_ != NULL) {
+    CharClassBuilder* ccb = re->ccb_;
+    re->ccb_ = NULL;
+    re->cc_ = ccb->GetCharClass();
+    delete ccb;
+  }
+
+  return re;
+}
+
 // Pushes the given regular expression onto the stack.
 // Could check for too much memory used here.
 bool Regexp::ParseState::PushRegexp(Regexp* re) {
@@ -185,14 +208,14 @@
   // analysis does better with fewer character classes.
   // Similarly, [Aa] can be rewritten as a literal A with ASCII case folding.
   if (re->op_ == kRegexpCharClass) {
-    if (re->cc_->size() == 1) {
-      Rune r = re->cc_->begin()->lo;
+    if (re->ccb_->size() == 1) {
+      Rune r = re->ccb_->begin()->lo;
       re->Decref();
       re = new Regexp(kRegexpLiteral, flags_);
       re->rune_ = r;
-    } else if (re->cc_->size() == 2) {
-      Rune r = re->cc_->begin()->lo;
-      if ('A' <= r && r <= 'Z' && re->cc_->Contains(r + 'a' - 'A')) {
+    } else if (re->ccb_->size() == 2) {
+      Rune r = re->ccb_->begin()->lo;
+      if ('A' <= r && r <= 'Z' && re->ccb_->Contains(r + 'a' - 'A')) {
         re->Decref();
         re = new Regexp(kRegexpLiteral, flags_ | FoldCase);
         re->rune_ = r + 'a' - 'A';
@@ -279,7 +302,7 @@
 // Add lo-hi to the class, along with their fold-equivalent characters.
 // If lo-hi is already in the class, assume that the fold-equivalent
 // chars are there too, so there's no work to do.
-static void AddFoldedRange(CharClass* cc, Rune lo, Rune hi, int depth) {
+static void AddFoldedRange(CharClassBuilder* cc, Rune lo, Rune hi, int depth) {
   // AddFoldedRange calls itself recursively for each rune in the fold cycle.
   // Most folding cycles are small: there aren't any bigger than four in the
   // current Unicode tables.  make_unicode_casefold.py checks that
@@ -335,14 +358,15 @@
   // Do case folding if needed.
   if ((flags_ & FoldCase) && CycleFoldRune(r) != r) {
     Regexp* re = new Regexp(kRegexpCharClass, flags_ & ~FoldCase);
+    re->ccb_ = new CharClassBuilder;
     Rune r1 = r;
     do {
       if (!(flags_ & NeverNL) || r != '\n') {
-        re->cc()->AddRange(r, r);
+        re->ccb_->AddRange(r, r);
       }
       r = CycleFoldRune(r);
     } while (r != r1);
-    re->cc()->RemoveAbove(rune_max_);
+    re->ccb_->RemoveAbove(rune_max_);
     return PushRegexp(re);
   }
 
@@ -394,8 +418,9 @@
     return PushSimpleOp(kRegexpAnyChar);
   // Rewrite . into [^\n]
   Regexp* re = new Regexp(kRegexpCharClass, flags_ & ~FoldCase);
-  re->cc_->AddRange(0, '\n' - 1);
-  re->cc_->AddRange('\n' + 1, rune_max_);
+  re->ccb_ = new CharClassBuilder;
+  re->ccb_->AddRange(0, '\n' - 1);
+  re->ccb_->AddRange('\n' + 1, rune_max_);
   return PushRegexp(re);
 }
 
@@ -420,9 +445,9 @@
     fl = fl ^ NonGreedy;
   Regexp* re = new Regexp(op, fl);
   re->AllocSub(1);
-  re->sub_[0] = stacktop_;
-  re->simple_ = re->ComputeSimple();
   re->down_ = stacktop_->down_;
+  re->sub()[0] = FinishRegexp(stacktop_);
+  re->simple_ = re->ComputeSimple();
   stacktop_ = re;
   return true;
 }
@@ -449,16 +474,17 @@
   re->min_ = min;
   re->max_ = max;
   re->AllocSub(1);
-  re->sub_[0] = stacktop_;
+  re->down_ = stacktop_->down_;
+  re->sub()[0] = FinishRegexp(stacktop_);
   re->simple_ = re->ComputeSimple();
 
-  re->down_ = stacktop_->down_;
   stacktop_ = re;
   return true;
 }
 
-// Pseudo-operators marking left paren and pipe operators
-// in the regexp stack.
+// Pseudo-operators - only on parse stack.
+
+// Markers for left paren and pipe operators in the regexp stack.
 const RegexpOp kLeftParen = static_cast<RegexpOp>(kMaxRegexpOp+1);
 const RegexpOp kVerticalBar = static_cast<RegexpOp>(kMaxRegexpOp+2);
 
@@ -485,7 +511,7 @@
 }
 
 // Adds r to cc, along with r's upper case if foldascii is set.
-static void AddLiteral(CharClass* cc, Rune r, bool foldascii) {
+static void AddLiteral(CharClassBuilder* cc, Rune r, bool foldascii) {
   cc->AddRange(r, r);
   if (foldascii && 'a' <= r && r <= 'z')
     cc->AddRange(r + 'A' - 'a', r + 'A' - 'a');
@@ -513,21 +539,24 @@
          r1->op() == kRegexpCharClass ||
          r1->op() == kRegexpAnyChar) &&
         (r3 = r2->down_) != NULL) {
+      Rune rune;
       switch (r3->op()) {
         case kRegexpLiteral:  // convert to char class
+          rune = r3->rune_;
           r3->op_ = kRegexpCharClass;
-          r3->cc_ = new CharClass;
-          AddLiteral(r3->cc_, r3->rune_, r3->parse_flags_ & Regexp::FoldCase);
+          r3->cc_ = NULL;
+          r3->ccb_ = new CharClassBuilder;
+          AddLiteral(r3->ccb_, rune, r3->parse_flags_ & Regexp::FoldCase);
           // fall through
         case kRegexpCharClass:
           if (r1->op() == kRegexpLiteral)
-            AddLiteral(r3->cc_, r1->rune_, r1->parse_flags_ & Regexp::FoldCase);
+            AddLiteral(r3->ccb_, r1->rune_, r1->parse_flags_ & Regexp::FoldCase);
           else if (r1->op() == kRegexpCharClass)
-            r3->cc_->AddCharClass(r1->cc());
-          if (r1->op() == kRegexpAnyChar || r3->cc_->full()) {
+            r3->ccb_->AddCharClass(r1->ccb_);
+          if (r1->op() == kRegexpAnyChar || r3->ccb_->full()) {
+            delete r3->ccb_;
+            r3->ccb_ = NULL;
             r3->op_ = kRegexpAnyChar;
-            delete r3->cc_;
-            r3->cc_ = NULL;
           }
           // fall through
         case kRegexpAnyChar:
@@ -579,7 +608,7 @@
     re->op_ = kRegexpCapture;
     // re->cap_ is already set
     re->AllocSub(1);
-    re->sub_[0] = r1;
+    re->sub()[0] = FinishRegexp(r1);
     re->simple_ = re->ComputeSimple();
   } else {
     re->Decref();
@@ -598,7 +627,7 @@
     return NULL;
   }
   stacktop_ = NULL;
-  return re;
+  return FinishRegexp(re);
 }
 
 // Collapse the regexps on top of the stack, down to the
@@ -623,19 +652,23 @@
     return;
 
   // Construct op (alternation or concatenation), flattening op of op.
-  Regexp* re = new Regexp(op, flags_);
-  re->AllocSub(n);
+  Regexp** subs = new Regexp*[n];
   next = NULL;
+  int i = n;
   for (sub = stacktop_; sub != NULL && !IsMarker(sub->op()); sub = next) {
-    next = sub->down_;  // in case we sub->Decref().
+    next = sub->down_;
     if (sub->op_ == op) {
+      Regexp** sub_subs = sub->sub();
       for (int k = sub->nsub_ - 1; k >= 0; k--)
-        re->sub_[--n] = sub->sub_[k]->Incref();
+        subs[--i] = sub_subs[k]->Incref();
       sub->Decref();
     } else {
-      re->sub_[--n] = sub;
+      subs[--i] = FinishRegexp(sub);
     }
   }
+  
+  Regexp* re = ConcatOrAlternate(op, subs, n, flags_);
+  delete[] subs;
   re->simple_ = re->ComputeSimple();
   re->down_ = next;
   stacktop_ = re;
@@ -665,8 +698,8 @@
 }
 
 // Incremental conversion of concatenated literals into strings.
-// If top of stack is literal, literal or literal, string or string, literal
-// or string, string, collapse into single string.
+// If top of stack is (literal, literal) or (literal, string) or (string, literal)
+// or (string, string), collapse into single string.
 // Don't walk down the stack -- the parser calls this frequently
 // enough that below the bottom two is known to be collapsed.
 // Only called when another regexp is about to be pushed
@@ -689,8 +722,11 @@
 
   if (re2->op_ == kRegexpLiteral) {
     // convert into string
+    Rune rune = re2->rune_;
     re2->op_ = kRegexpLiteralString;
-    re2->AddRuneToString(re2->rune_);
+    re2->nrunes_ = 0;
+    re2->runes_ = NULL;
+    re2->AddRuneToString(rune);
   }
 
   // push re1 into re2.
@@ -983,7 +1019,7 @@
 
 // Add a range to the character class, but exclude newline if asked.
 // Also handle case folding.
-static void AddRange(CharClass* cc, Rune lo, Rune hi,
+static void AddRange(CharClassBuilder* cc, Rune lo, Rune hi,
                      Regexp::ParseFlags parse_flags) {
 
   // Take out \n if the flags say so.
@@ -1037,7 +1073,7 @@
 }
 
 // Add a UGroup to the character class.
-static void AddUGroup(CharClass *cc, UGroup *g,
+static void AddUGroup(CharClassBuilder *cc, UGroup *g,
                       Regexp::ParseFlags parse_flags) {
   for (int i = 0; i < g->nr16; i++) {
     AddRange(cc, g->r16[i].lo, g->r16[i].hi, parse_flags);
@@ -1048,7 +1084,7 @@
 }
 
 // Add the negation of a UGroup to the character class.
-static void AddNegatedUGroup(CharClass* cc, UGroup *g,
+static void AddNegatedUGroup(CharClassBuilder* cc, UGroup *g,
                              Regexp::ParseFlags parse_flags) {
   int next = 0;
   for (int i = 0; i < g->nr16; i++) {
@@ -1095,7 +1131,7 @@
 // Maybe parses a Unicode character group like \p{Han} or \P{Han}
 // (the latter is a negated group).
 ParseStatus ParseUnicodeGroup(StringPiece* s, Regexp::ParseFlags parse_flags,
-                              CharClass *cc,
+                              CharClassBuilder *cc,
                               RegexpStatus* status) {
   // Decide whether to parse.
   if (!(parse_flags & Regexp::UnicodeGroups))
@@ -1160,7 +1196,7 @@
 // Sets *s to span the remainder of the string.
 // Adds the ranges corresponding to the class to ranges.
 static ParseStatus ParseCCName(StringPiece* s, Regexp::ParseFlags parse_flags,
-                               CharClass *cc,
+                               CharClassBuilder *cc,
                                RegexpStatus* status) {
   // Check begins with [:
   const char* p = s->data();
@@ -1257,6 +1293,7 @@
   }
   bool negated = false;
   Regexp* re = new Regexp(kRegexpCharClass, flags_ & ~FoldCase);
+  re->ccb_ = new CharClassBuilder;
   s->remove_prefix(1);  // '['
   if (s->size() > 0 && (*s)[0] == '^') {
     s->remove_prefix(1);  // '^'
@@ -1264,7 +1301,7 @@
     if (!(flags_ & ClassNL) || (flags_ & NeverNL)) {
       // If NL can't match implicitly, then pretend
       // negated classes include a leading \n.
-      re->cc_->AddRange('\n', '\n');
+      re->ccb_->AddRange('\n', '\n');
     }
   }
   bool first = true;  // ] is okay as first char in class
@@ -1290,7 +1327,7 @@
 
     // Look for [:alnum:] etc.
     if (s->size() > 2 && (*s)[0] == '[' && (*s)[1] == ':') {
-      switch (ParseCCName(s, flags_, re->cc_, status)) {
+      switch (ParseCCName(s, flags_, re->ccb_, status)) {
         case kParseOk:
           continue;
         case kParseError:
@@ -1305,7 +1342,7 @@
     if (s->size() > 2 &&
         (*s)[0] == '\\' &&
         ((*s)[1] == 'p' || (*s)[1] == 'P')) {
-      switch (ParseUnicodeGroup(s, flags_, re->cc_, status)) {
+      switch (ParseUnicodeGroup(s, flags_, re->ccb_, status)) {
         case kParseOk:
           continue;
         case kParseError:
@@ -1319,7 +1356,7 @@
     // Look for Perl character class symbols (extension).
     UGroup *g = MaybeParsePerlCCEscape(s, flags_);
     if (g != NULL) {
-      AddUGroup(re->cc_, g, flags_);
+      AddUGroup(re->ccb_, g, flags_);
       continue;
     }
 
@@ -1334,7 +1371,7 @@
     // Regexp::ClassNL is set.  In an explicit range or singleton
     // like we just parsed, we do not filter \n out, so set ClassNL
     // in the flags.
-    AddRange(re->cc_, rr.lo, rr.hi, flags_ | Regexp::ClassNL);
+    AddRange(re->ccb_, rr.lo, rr.hi, flags_ | Regexp::ClassNL);
   }
   if (s->size() == 0) {
     status->set_code(kRegexpMissingBracket);
@@ -1345,8 +1382,8 @@
   s->remove_prefix(1);  // ']'
 
   if (negated)
-    re->cc_->Negate();
-  re->cc_->RemoveAbove(rune_max_);
+    re->ccb_->Negate();
+  re->ccb_->RemoveAbove(rune_max_);
 
   *out_re = re;
   return true;
@@ -1752,7 +1789,8 @@
 
         if (t[1] == 'p' || t[1] == 'P') {
           Regexp* re = new Regexp(kRegexpCharClass, ps.flags() & ~FoldCase);
-          switch (ParseUnicodeGroup(&t, ps.flags(), re->cc_, status)) {
+          re->ccb_ = new CharClassBuilder;
+          switch (ParseUnicodeGroup(&t, ps.flags(), re->ccb_, status)) {
             case kParseOk:
               if (!ps.PushRegexp(re))
                 return NULL;
@@ -1769,7 +1807,8 @@
         UGroup *g = MaybeParsePerlCCEscape(&t, ps.flags());
         if (g != NULL) {
           Regexp* re = new Regexp(kRegexpCharClass, ps.flags() & ~FoldCase);
-          AddUGroup(re->cc_, g, ps.flags());
+          re->ccb_ = new CharClassBuilder;
+          AddUGroup(re->ccb_, g, ps.flags());
           if (!ps.PushRegexp(re))
             return NULL;
           break;
diff --git a/re2/re2.cc b/re2/re2.cc
index 8f96f83..e2b4382 100644
--- a/re2/re2.cc
+++ b/re2/re2.cc
@@ -110,6 +110,7 @@
   prog_ = NULL;
   rprog_ = NULL;
   named_groups_ = NULL;
+  num_captures_ = -1;
 
   RegexpStatus status;
   int flags = Regexp::ClassNL;
@@ -796,7 +797,11 @@
 int RE2::NumberOfCapturingGroups() const {
   if (suffix_regexp_ == NULL)
     return -1;
-  return suffix_regexp_->NumCaptures();
+  ANNOTATE_BENIGN_RACE(&num_captures_, "benign race: in the worst case"
+    " multiple threads end up doing the same work in parallel.");
+  if (num_captures_ == -1)
+    num_captures_ = suffix_regexp_->NumCaptures();
+  return num_captures_;
 }
 
 // Checks that the rewrite string is well-formed with respect to this
diff --git a/re2/re2.h b/re2/re2.h
index 3676875..c0d4902 100644
--- a/re2/re2.h
+++ b/re2/re2.h
@@ -675,6 +675,7 @@
                                            // (or points to empty string)
   mutable ErrorCode        error_code_;    // Error code
   mutable string           error_arg_;     // Fragment of regexp showing error
+  mutable int              num_captures_;  // Number of capturing groups
 
   // Map from capture names to indices
   mutable const map<string, int>* named_groups_;
diff --git a/re2/regexp.cc b/re2/regexp.cc
index bbbb1ec..7b21fbe 100644
--- a/re2/regexp.cc
+++ b/re2/regexp.cc
@@ -3,7 +3,7 @@
 // license that can be found in the LICENSE file.
 
 // Regular expression representation.
-// Tested by parse_unittest.cc
+// Tested by parse_test.cc
 
 #include "util/util.h"
 #include "re2/regexp.h"
@@ -15,29 +15,13 @@
 // Constructor.  Allocates vectors as appropriate for operator.
 Regexp::Regexp(RegexpOp op, ParseFlags parse_flags)
   : op_(op),
-    parse_flags_(parse_flags),
-    ref_(1),
     simple_(false),
-    num_captures_(-1),
-    cap_(-1),
-    max_(0),
-    min_(0),
-    nrunes_(0),
+    parse_flags_(static_cast<uint16>(parse_flags)),
+    ref_(1),
     nsub_(0),
-    rune_(0),
-    cc_(NULL),
-    sub_(NULL),
-    runes_(NULL),
-    name_(NULL),
     down_(NULL) {
-
-  switch (op_) {
-    default:
-      break;
-    case kRegexpCharClass:
-      cc_ = new CharClass;
-      break;
-  }
+  subone_ = NULL;
+  memset(the_union_, 0, sizeof the_union_);
 }
 
 // Destructor.  Assumes already cleaned up children.
@@ -46,29 +30,86 @@
 // that could cause arbitrarily deep recursion, so
 // required Decref() to have handled them for us.
 Regexp::~Regexp() {
-  if (sub_)
+  if (nsub_ > 0)
     LOG(DFATAL) << "Regexp not destroyed.";
 
-  delete cc_;
-  delete name_;
-  delete[] runes_;
+  switch (op_) {
+    default:
+      break;
+    case kRegexpCapture:
+      delete name_;
+      break;
+    case kRegexpLiteralString:
+      delete[] runes_;
+      break;
+    case kRegexpCharClass:
+      cc_->Delete();
+      delete ccb_;
+      break;
+  }
 }
 
 // If it's possible to destroy this regexp without recurring,
 // do so and return true.  Else return false.
 bool Regexp::QuickDestroy() {
-  if (sub_ == NULL) {
+  if (nsub_ == 0) {
     delete this;
     return true;
   }
   return false;
 }
 
+static map<Regexp*, int> ref_map;
+static Mutex ref_mutex;
+
+int Regexp::Ref() {
+  if (ref_ < kMaxRef)
+    return ref_;
+  
+  MutexLock l(&ref_mutex);
+  return ref_map[this];
+}
+
+// Increments reference count, returns object as convenience.
+Regexp* Regexp::Incref() {
+  if (ref_ >= kMaxRef-1) {
+    // Store ref count in overflow map.
+    MutexLock l(&ref_mutex);
+    if (ref_ == kMaxRef) {  // already overflowed
+      ref_map[this]++;
+      return this;
+    }
+    // overflowing now
+    ref_map[this] = kMaxRef;
+    ref_ = kMaxRef;
+    return this;
+  }
+
+  ref_++;
+  return this;
+}
+
+// Decrements reference count and deletes this object if count reaches 0.
+void Regexp::Decref() {
+  if (ref_ == kMaxRef) {
+    // Ref count is stored in overflow map.
+    MutexLock l(&ref_mutex);
+    int r = ref_map[this] - 1;
+    if (r < kMaxRef) {
+      ref_ = r;
+      ref_map.erase(this);
+    } else {
+      ref_map[this] = r;
+    }
+    return;
+  }
+  ref_--;
+  if (ref_ == 0)
+    Destroy();
+}
+
 // Deletes this object; ref count has count reached 0.
 void Regexp::Destroy() {
-  if (ref_ < 0)
-    LOG(DFATAL) << "Bad reference count " << ref_;
-
   if (QuickDestroy())
     return;
 
@@ -81,17 +122,22 @@
     stack = re->down_;
     if (re->ref_ != 0)
       LOG(DFATAL) << "Bad reference count " << re->ref_;
-    if (re->sub_ != NULL) {
+    if (re->nsub_ > 0) {
+      Regexp** subs = re->sub();
       for (int i = 0; i < re->nsub_; i++) {
-        Regexp* sub = re->sub_[i];
-        if (--sub->ref_ == 0 && !sub->QuickDestroy()) {
+        Regexp* sub = subs[i];
+        if (sub->ref_ == kMaxRef)
+          sub->Decref();
+        else
+          --sub->ref_;
+        if (sub->ref_ == 0 && !sub->QuickDestroy()) {
           sub->down_ = stack;
           stack = sub;
         }
       }
-      if (re->sub_ != re->smallsub_)
-        delete[] re->sub_;
-      re->sub_ = NULL;
+      if (re->nsub_ > 1)
+        delete[] subs;
+      re->nsub_ = 0;
     }
     delete re;
   }
@@ -120,7 +166,7 @@
     return sub;
   Regexp* re = new Regexp(kRegexpPlus, flags);
   re->AllocSub(1);
-  re->sub_[0] = sub;
+  re->sub()[0] = sub;
   return re;
 }
 
@@ -129,7 +175,7 @@
     return sub;
   Regexp* re = new Regexp(kRegexpStar, flags);
   re->AllocSub(1);
-  re->sub_[0] = sub;
+  re->sub()[0] = sub;
   return re;
 }
 
@@ -138,30 +184,44 @@
     return sub;
   Regexp* re = new Regexp(kRegexpQuest, flags);
   re->AllocSub(1);
-  re->sub_[0] = sub;
+  re->sub()[0] = sub;
+  return re;
+}
+
+Regexp* Regexp::ConcatOrAlternate(RegexpOp op, Regexp** sub, int nsub, ParseFlags flags) {
+  if (nsub > kMaxNsub) {
+    // Too many subexpressions to fit in a single Regexp.
+    // Make a two-level tree.  Two levels gets us to 65535^2.
+    int nbigsub = (nsub+kMaxNsub-1)/kMaxNsub;
+    Regexp* re = new Regexp(op, flags);
+    re->AllocSub(nbigsub);
+    Regexp** subs = re->sub();
+    for (int i = 0; i < nbigsub - 1; i++)
+      subs[i] = ConcatOrAlternate(op, sub+i*kMaxNsub, kMaxNsub, flags);
+    subs[nbigsub - 1] = ConcatOrAlternate(op, sub+(nbigsub-1)*kMaxNsub, nsub - (nbigsub-1)*kMaxNsub, flags);
+    return re;
+  }
+
+  Regexp* re = new Regexp(op, flags);
+  re->AllocSub(nsub);
+  Regexp** subs = re->sub();
+  for (int i = 0; i < nsub; i++)
+    subs[i] = sub[i];
   return re;
 }
 
 Regexp* Regexp::Concat(Regexp** sub, int nsub, ParseFlags flags) {
-  Regexp* re = new Regexp(kRegexpConcat, flags);
-  re->AllocSub(nsub);
-  for (int i = 0; i < nsub; i++)
-    re->sub_[i] = sub[i];
-  return re;
+  return ConcatOrAlternate(kRegexpConcat, sub, nsub, flags);
 }
 
 Regexp* Regexp::Alternate(Regexp** sub, int nsub, ParseFlags flags) {
-  Regexp* re = new Regexp(kRegexpAlternate, flags);
-  re->AllocSub(nsub);
-  for (int i = 0; i < nsub; i++)
-    re->sub_[i] = sub[i];
-  return re;
+  return ConcatOrAlternate(kRegexpAlternate, sub, nsub, flags);
 }
 
 Regexp* Regexp::Capture(Regexp* sub, ParseFlags flags, int cap) {
   Regexp* re = new Regexp(kRegexpCapture, flags);
   re->AllocSub(1);
-  re->sub_[0] = sub;
+  re->sub()[0] = sub;
   re->cap_ = cap;
   return re;
 }
@@ -169,7 +229,7 @@
 Regexp* Regexp::Repeat(Regexp* sub, ParseFlags flags, int min, int max) {
   Regexp* re = new Regexp(kRegexpRepeat, flags);
   re->AllocSub(1);
-  re->sub_[0] = sub;
+  re->sub()[0] = sub;
   re->min_ = min;
   re->max_ = max;
   return re;
@@ -194,7 +254,6 @@
 
 Regexp* Regexp::NewCharClass(CharClass* cc, ParseFlags flags) {
   Regexp* re = new Regexp(kRegexpCharClass, flags);
-  delete re->cc_;
   re->cc_ = cc;
   return re;
 }
@@ -264,14 +323,9 @@
 };
 
 int Regexp::NumCaptures() {
-  ANNOTATE_BENIGN_RACE(&num_captures_, "benign race: in the worst case"
-    " multiple threads end up doing the same work in parallel.");
-  if (num_captures_ == -1) {
-    NumCapturesWalker w;
-    w.Walk(this, 0);
-    num_captures_ = w.ncapture();
-  }
-  return num_captures_;
+  NumCapturesWalker w;
+  w.Walk(this, 0);
+  return w.ncapture();
 }
 
 // Walker class to build map of named capture groups and their indices.
@@ -335,21 +389,22 @@
 
   // Some number of anchors.
   int i = 0;
-  while (i < nsub_ && sub_[i]->op_ == kRegexpBeginText)
+  Regexp** sub = this->sub();
+  while (i < nsub_ && sub[i]->op_ == kRegexpBeginText)
     i++;
   if (i == 0)
     return false;
 
   // Then a literal or a concatenation.
   if (i < nsub_) {
-    Regexp* re = sub_[i];
+    Regexp* re = sub[i];
     switch (re->op_) {
       default:
         return false;
 
       case kRegexpLiteralString:
         // Convert to string in proper encoding.
-        if (re->parse_flags_ & Latin1) {
+        if (re->parse_flags() & Latin1) {
           prefix->resize(re->nrunes_);
           for (int j = 0; j < re->nrunes_; j++)
             (*prefix)[j] = re->runes_[j];
@@ -370,7 +425,7 @@
         break;
 
       case kRegexpLiteral:
-        if ((re->parse_flags_ & Latin1) || re->rune_ < Runeself) {
+        if ((re->parse_flags() & Latin1) || re->rune_ < Runeself) {
           prefix->append(1, re->rune_);
         } else {
           char buf[UTFmax];
@@ -378,7 +433,7 @@
         }
         break;
     }
-    *foldcase = (sub_[i]->parse_flags_ & FoldCase);
+    *foldcase = (sub[i]->parse_flags() & FoldCase);
     i++;
   }
 
@@ -386,29 +441,29 @@
   Regexp* re;
   if (i < nsub_) {
     for (int j = i; j < nsub_; j++)
-      sub_[j]->Incref();
-    re = Concat(sub_ + i, nsub_ - i, parse_flags_);
+      sub[j]->Incref();
+    re = Concat(sub + i, nsub_ - i, parse_flags());
   } else {
-    re = new Regexp(kRegexpEmptyMatch, parse_flags_);
+    re = new Regexp(kRegexpEmptyMatch, parse_flags());
   }
   *suffix = re;
   return true;
 }
 
-// Character class is a balanced binary tree (STL set)
+// Character class builder is a balanced binary tree (STL set)
 // containing non-overlapping, non-abutting RuneRanges.
 // The less-than operator used in the tree treats two
 // ranges as equal if they overlap at all, so that
 // lookups for a particular Rune are possible.
 
-CharClass::CharClass() {
+CharClassBuilder::CharClassBuilder() {
   nrunes_ = 0;
   upper_ = 0;
   lower_ = 0;
 }
 
 // Add lo-hi to the class; return whether class got bigger.
-bool CharClass::AddRange(Rune lo, Rune hi) {
+bool CharClassBuilder::AddRange(Rune lo, Rune hi) {
   if (hi < lo)
     return false;
 
@@ -474,24 +529,22 @@
   return true;
 }
 
-bool CharClass::AddCharClass(CharClass *cc) {
-  bool added = false;
+void CharClassBuilder::AddCharClass(CharClassBuilder *cc) {
   for (iterator it = cc->begin(); it != cc->end(); ++it)
-    added |= AddRange(it->lo, it->hi);
-  return added;
+    AddRange(it->lo, it->hi);
 }
 
-bool CharClass::Contains(Rune r) {
+bool CharClassBuilder::Contains(Rune r) {
   return ranges_.find(RuneRange(r, r)) != end();
 }
 
 // Does the character class behave the same on A-Z as on a-z?
-bool CharClass::FoldsASCII() {
+bool CharClassBuilder::FoldsASCII() {
   return ((upper_ ^ lower_) & AlphaMask) == 0;
 }
 
-CharClass* CharClass::Copy() {
-  CharClass* cc = new CharClass;
+CharClassBuilder* CharClassBuilder::Copy() {
+  CharClassBuilder* cc = new CharClassBuilder;
   for (iterator it = begin(); it != end(); ++it)
     cc->ranges_.insert(RuneRange(it->lo, it->hi));
   cc->upper_ = upper_;
@@ -500,7 +553,9 @@
   return cc;
 }
 
-void CharClass::RemoveAbove(Rune r) {
+
+
+void CharClassBuilder::RemoveAbove(Rune r) {
   if (r >= Runemax)
     return;
 
@@ -519,6 +574,7 @@
   }
 
   for (;;) {
+    
     iterator it = ranges_.find(RuneRange(r + 1, Runemax));
     if (it == end())
       break;
@@ -533,7 +589,7 @@
   }
 }
 
-void CharClass::Negate() {
+void CharClassBuilder::Negate() {
   // Build up negation and then copy in.
   // Could edit ranges in place, but C++ won't let me.
   vector<RuneRange> v;
@@ -567,4 +623,75 @@
   nrunes_ = Runemax+1 - nrunes_;
 }
 
+// Character class is a sorted list of ranges.
+// The ranges are allocated in the same block as the header,
+// necessitating a special allocator and Delete method.
+
+CharClass* CharClass::New(int maxranges) {
+  CharClass* cc;
+  uint8* data = new uint8[sizeof *cc + maxranges*sizeof cc->ranges_[0]];
+  cc = reinterpret_cast<CharClass*>(data);
+  cc->ranges_ = reinterpret_cast<RuneRange*>(data + sizeof *cc);
+  cc->nranges_ = 0;
+  cc->folds_ascii_ = false;
+  cc->nrunes_ = 0;
+  return cc;
+}
+
+void CharClass::Delete() {
+  if (this == NULL)
+    return;
+  uint8 *data = reinterpret_cast<uint8*>(this);
+  delete[] data;
+}
+
+CharClass* CharClass::Negate() {
+  CharClass* cc = CharClass::New(nranges_+1);
+  cc->folds_ascii_ = folds_ascii_;
+  cc->nrunes_ = Runemax + 1 - nrunes_;
+  int n = 0;
+  int nextlo = 0;
+  for (CharClass::iterator it = begin(); it != end(); ++it) {
+    if (it->lo == nextlo) {
+      nextlo = it->hi + 1;
+    } else {
+      cc->ranges_[n++] = RuneRange(nextlo, it->lo - 1);
+      nextlo = it->hi + 1;
+    }
+  }
+  if (nextlo <= Runemax)
+    cc->ranges_[n++] = RuneRange(nextlo, Runemax);
+  cc->nranges_ = n;
+  return cc;
+}
+
+bool CharClass::Contains(Rune r) {
+  RuneRange* rr = ranges_;
+  int n = nranges_;
+  while (n > 0) {
+    int m = n/2;
+    if (rr[m].hi < r) {
+      rr += m+1;
+      n -= m+1;
+    } else if (r < rr[m].lo) {
+      n = m;
+    } else {  // rr[m].lo <= r && r <= rr[m].hi
+      return true;
+    }
+  }
+  return false;
+}
+
+CharClass* CharClassBuilder::GetCharClass() {
+  CharClass* cc = CharClass::New(ranges_.size());
+  int n = 0;
+  for (iterator it = begin(); it != end(); ++it)
+    cc->ranges_[n++] = *it;
+  cc->nranges_ = n;
+  DCHECK_LE(n, ranges_.size());
+  cc->nrunes_ = nrunes_;
+  cc->folds_ascii_ = FoldsASCII();
+  return cc;
+}
+
 }  // namespace re2
diff --git a/re2/regexp.h b/re2/regexp.h
index 749418e..7d0c5f5 100644
--- a/re2/regexp.h
+++ b/re2/regexp.h
@@ -146,7 +146,7 @@
   // Matches empty string at end of text.
   kRegexpEndText,
 
-  // Matches character class given by ranges_.
+  // Matches character class given by cc_.
   kRegexpCharClass,
 
   kMaxRegexpOp = kRegexpCharClass,
@@ -228,12 +228,44 @@
   }
 };
 
-// Character class: contains non-overlapping, non-abutting RuneRanges.
-typedef set<RuneRange, RuneRangeLess> RuneRangeSet;
+class CharClassBuilder;
 
 class CharClass {
  public:
-  CharClass();
+  void Delete();
+
+  typedef RuneRange* iterator;
+  iterator begin() { return ranges_; }
+  iterator end() { return ranges_ + nranges_; }
+
+  int size() { return nrunes_; }
+  bool empty() { return nrunes_ == 0; }
+  bool full() { return nrunes_ == Runemax+1; }
+  bool FoldsASCII() { return folds_ascii_; }
+
+  bool Contains(Rune r);
+  CharClass* Negate();
+
+ private:
+  CharClass();  // not implemented
+  ~CharClass();  // not implemented
+  static CharClass* New(int maxranges);
+  
+  friend class CharClassBuilder;
+
+  bool folds_ascii_;
+  int nrunes_;
+  RuneRange *ranges_;
+  int nranges_;
+  DISALLOW_EVIL_CONSTRUCTORS(CharClass);
+};
+
+// Character class set: contains non-overlapping, non-abutting RuneRanges.
+typedef set<RuneRange, RuneRangeLess> RuneRangeSet;
+
+class CharClassBuilder {
+ public:
+  CharClassBuilder();
 
   typedef RuneRangeSet::iterator iterator;
   iterator begin() { return ranges_.begin(); }
@@ -243,14 +275,14 @@
   bool empty() { return nrunes_ == 0; }
   bool full() { return nrunes_ == Runemax+1; }
 
-  const RuneRangeSet& ranges() { return ranges_; }
   bool Contains(Rune r);
   bool FoldsASCII();
   bool AddRange(Rune lo, Rune hi);  // returns whether class changed
-  CharClass* Copy();
-  bool AddCharClass(CharClass* cc);
+  CharClassBuilder* Copy();
+  void AddCharClass(CharClassBuilder* cc);
   void Negate();
   void RemoveAbove(Rune r);
+  CharClass* GetCharClass();
 
  private:
   static const uint32 AlphaMask = (1<<26) - 1;
@@ -258,7 +290,7 @@
   uint32 lower_;  // bitmap of a-z
   int nrunes_;
   RuneRangeSet ranges_;
-  DISALLOW_EVIL_CONSTRUCTORS(CharClass);
+  DISALLOW_EVIL_CONSTRUCTORS(CharClassBuilder);
 };
 
 class Regexp {
@@ -302,29 +334,37 @@
                    UnicodeGroups,
 
     // Internal use only.
-    WasDollar    = 1<<30,  // on kRegexpEndText: was $ in regexp text
+    WasDollar    = 1<<15,  // on kRegexpEndText: was $ in regexp text
   };
 
   // Get.  No set, Regexps are logically immutable once created.
-  RegexpOp op() { return op_; }
-  Regexp** sub() { return sub_; }
+  RegexpOp op() { return static_cast<RegexpOp>(op_); }
   int nsub() { return nsub_; }
-  int min() { return min_; }
-  int max() { return max_; }
-  Rune rune() { return rune_; }
-  CharClass* cc() { return cc_; }
-  enum ParseFlags parse_flags() { return parse_flags_; }
-  int cap() { return cap_; }
-  const string* name() { return name_; }
   bool simple() { return simple_; }
-  Rune* runes() { return runes_; }
-  int nrunes() { return nrunes_; }
+  enum ParseFlags parse_flags() { return static_cast<ParseFlags>(parse_flags_); }
+  int Ref();  // For testing.
+
+  Regexp** sub() {
+    if(nsub_ <= 1)
+      return &subone_;
+    else
+      return submany_;
+  }
+
+  int min() { DCHECK_EQ(op_, kRegexpRepeat); return min_; }
+  int max() { DCHECK_EQ(op_, kRegexpRepeat); return max_; }
+  Rune rune() { DCHECK_EQ(op_, kRegexpLiteral); return rune_; }
+  CharClass* cc() { DCHECK_EQ(op_, kRegexpCharClass); return cc_; }
+  int cap() { DCHECK_EQ(op_, kRegexpCapture); return cap_; }
+  const string* name() { DCHECK_EQ(op_, kRegexpCapture); return name_; }
+  Rune* runes() { DCHECK_EQ(op_, kRegexpLiteralString); return runes_; }
+  int nrunes() { DCHECK_EQ(op_, kRegexpLiteralString); return nrunes_; }
 
   // Increments reference count, returns object as convenience.
-  Regexp* Incref() { ref_++; return this; }
+  Regexp* Incref();
 
   // Decrements reference count and deletes this object if count reaches 0.
-  void Decref() { if(--ref_ <= 0) Destroy(); }
+  void Decref();
 
   // Parses string s to produce regular expression, returned.
   // Caller must release return value with re->Decref().
@@ -426,12 +466,17 @@
   // Computes whether Regexp is already simple.
   bool ComputeSimple();
 
+  // Constructor that generates a concatenation or alternation,
+  // enforcing the limit on the number of subexpressions for
+  // a particular Regexp.
+  static Regexp* ConcatOrAlternate(RegexpOp op, Regexp** subs, int nsubs, ParseFlags flags);
+
   // Allocate space for n sub-regexps.
   void AllocSub(int n) {
-    if (n <= arraysize(smallsub_))
-      sub_ = smallsub_;
-    else
-      sub_ = new Regexp*[n];
+    if (n < 0 || static_cast<uint16>(n) != n)
+      LOG(FATAL) << "Cannot AllocSub " << n;
+    if (n > 1)
+      submany_ = new Regexp*[n];
     nsub_ = n;
   }
 
@@ -439,41 +484,71 @@
   void AddRuneToString(Rune r);
 
   // Operator.  See description of operators above.
-  enum RegexpOp op_;
+  // uint8 instead of RegexpOp to control space usage.
+  uint8 op_;
+
+  // Is this regexp structure already simple
+  // (has it been returned by Simplify)?
+  // uint8 instead of bool to control space usage.
+  uint8 simple_;
 
   // Flags saved from parsing and used during execution.
   // (Only FoldCase is used.)
-  ParseFlags parse_flags_;
+  // uint16 instead of ParseFlags to control space usage.
+  uint16 parse_flags_;
 
   // Reference count.  Exists so that SimplifyRegexp can build
   // regexp structures that are dags rather than trees to avoid
   // exponential blowup in space requirements.
-  int ref_;
+  // uint16 to control space usage.
+  // The standard regexp routines will never generate a
+  // ref greater than the maximum repeat count (100),
+  // but even so, Incref and Decref consult an overflow map
+  // when ref_ reaches kMaxRef.
+  uint16 ref_;
+  static const uint16 kMaxRef = 0xffff;
 
-  // Is this regexp structure already simple
-  // (has it been returned by Simplify)?
-  bool simple_;
-
-  // How many capturing groups?  -1 if unknown.
-  int num_captures_;
-
-  // Arguments to operator.  See description of operators above.
-  int cap_;
-  int max_;
-  int min_;
-  int nrunes_;
-  int nsub_;
-  Rune rune_;
-
-  CharClass* cc_;
-  Regexp* smallsub_[2];
-  Regexp** sub_;
-  Rune* runes_;
-  string* name_;
+  // Subexpressions.
+  // uint16 to control space usage.
+  // Concat and Alternate handle larger numbers of subexpressions
+  // by building concatenation or alternation trees.
+  // Other routines should call Concat or Alternate instead of
+  // filling in sub() by hand.
+  uint16 nsub_;
+  static const uint16 kMaxNsub = 0xffff;
+  union {
+    Regexp** submany_;  // if nsub_ > 1
+    Regexp* subone_;  // if nsub_ == 1
+  };
 
   // Extra space for parse and teardown stacks.
   Regexp* down_;
 
+  // Arguments to operator.  See description of operators above.
+  union {
+    struct {  // Repeat
+      int max_;
+      int min_;
+    };
+    struct {  // Capture
+      int cap_;
+      string* name_;
+    };
+    struct {  // LiteralString
+      int nrunes_;
+      Rune* runes_;
+    };
+    struct {  // CharClass
+      // These two could be in separate union members,
+      // but it wouldn't save any space (there are other two-word structs)
+      // and keeping them separate avoids confusion during parsing.
+      CharClass* cc_;
+      CharClassBuilder* ccb_;
+    };
+    Rune rune_;  // Literal
+    void *the_union_[2];  // as big as any other element, for memset
+  };
+
   DISALLOW_EVIL_CONSTRUCTORS(Regexp);
 };
 
diff --git a/re2/simplify.cc b/re2/simplify.cc
index 58a0973..2c9dbe3 100644
--- a/re2/simplify.cc
+++ b/re2/simplify.cc
@@ -40,6 +40,7 @@
 // Assuming the simple_ flags on the children are accurate,
 // is this Regexp* simple?
 bool Regexp::ComputeSimple() {
+  Regexp** subs;
   switch (op_) {
     case kRegexpNoMatch:
     case kRegexpEmptyMatch:
@@ -57,21 +58,26 @@
     case kRegexpConcat:
     case kRegexpAlternate:
       // These are simple as long as the subpieces are simple.
+      subs = sub();
       for (int i = 0; i < nsub_; i++)
-        if (!sub_[i]->simple_)
+        if (!subs[i]->simple_)
           return false;
       return true;
     case kRegexpCharClass:
       // Simple as long as the char class is not empty, not full.
+      if (ccb_ != NULL)
+        return !ccb_->empty() && !ccb_->full();
       return !cc_->empty() && !cc_->full();
     case kRegexpCapture:
-      return sub_[0]->simple_;
+      subs = sub();
+      return subs[0]->simple_;
     case kRegexpStar:
     case kRegexpPlus:
     case kRegexpQuest:
-      if (!sub_[0]->simple_)
+      subs = sub();
+      if (!subs[0]->simple_)
         return false;
-      switch (sub_[0]->op_) {
+      switch (subs[0]->op_) {
         case kRegexpStar:
         case kRegexpPlus:
         case kRegexpQuest:
@@ -168,7 +174,7 @@
                                   Regexp* pre_arg,
                                   Regexp** child_args,
                                   int nchild_args) {
-  switch (re->op_) {
+  switch (re->op()) {
     case kRegexpNoMatch:
     case kRegexpEmptyMatch:
     case kRegexpLiteral:
@@ -190,8 +196,9 @@
       // These are simple as long as the subpieces are simple.
       // Two passes to avoid allocation in the common case.
       bool changed = false;
+      Regexp** subs = re->sub();
       for (int i = 0; i < re->nsub_; i++) {
-        Regexp* sub = re->sub_[i];
+        Regexp* sub = subs[i];
         Regexp* newsub = child_args[i];
         if (newsub != sub) {
           changed = true;
@@ -206,24 +213,25 @@
         re->simple_ = true;
         return re->Incref();
       }
-      Regexp* nre = new Regexp(re->op_, re->parse_flags_);
+      Regexp* nre = new Regexp(re->op(), re->parse_flags());
       nre->AllocSub(re->nsub_);
+      Regexp** nre_subs = nre->sub();
       for (int i = 0; i <re->nsub_; i++)
-        nre->sub_[i] = child_args[i];
+        nre_subs[i] = child_args[i];
       nre->simple_ = true;
       return nre;
     }
 
     case kRegexpCapture: {
       Regexp* newsub = child_args[0];
-      if (newsub == re->sub_[0]) {
+      if (newsub == re->sub()[0]) {
         newsub->Decref();
         re->simple_ = true;
         return re->Incref();
       }
-      Regexp* nre = new Regexp(kRegexpCapture, re->parse_flags_);
+      Regexp* nre = new Regexp(kRegexpCapture, re->parse_flags());
       nre->AllocSub(1);
-      nre->sub_[0] = newsub;
+      nre->sub()[0] = newsub;
       nre->cap_ = re->cap_;
       nre->simple_ = true;
       return nre;
@@ -235,11 +243,11 @@
       Regexp* newsub = child_args[0];
       // Special case: repeat the empty string as much as
       // you want, but it's still the empty string.
-      if (newsub->op_ == kRegexpEmptyMatch)
+      if (newsub->op() == kRegexpEmptyMatch)
         return newsub;
 
       // These are simple as long as the subpiece is simple.
-      if (newsub == re->sub_[0]) {
+      if (newsub == re->sub()[0]) {
         newsub->Decref();
         re->simple_ = true;
         return re->Incref();
@@ -250,9 +258,9 @@
           re->parse_flags() == newsub->parse_flags())
         return newsub;
 
-      Regexp* nre = new Regexp(re->op_, re->parse_flags_);
+      Regexp* nre = new Regexp(re->op(), re->parse_flags());
       nre->AllocSub(1);
-      nre->sub_[0] = newsub;
+      nre->sub()[0] = newsub;
       nre->simple_ = true;
       return nre;
     }
@@ -261,11 +269,11 @@
       Regexp* newsub = child_args[0];
       // Special case: repeat the empty string as much as
       // you want, but it's still the empty string.
-      if (newsub->op_ == kRegexpEmptyMatch)
+      if (newsub->op() == kRegexpEmptyMatch)
         return newsub;
 
       Regexp* nre = SimplifyRepeat(newsub, re->min_, re->max_,
-                                   re->parse_flags_);
+                                   re->parse_flags());
       newsub->Decref();
       nre->simple_ = true;
       return nre;
@@ -278,7 +286,7 @@
     }
   }
 
-  LOG(ERROR) << "Simplify case not handled: " << re->op_;
+  LOG(ERROR) << "Simplify case not handled: " << re->op();
   return re->Incref();
 }
 
@@ -288,8 +296,9 @@
                                 Regexp::ParseFlags parse_flags) {
   Regexp* re = new Regexp(kRegexpConcat, parse_flags);
   re->AllocSub(2);
-  re->sub_[0] = re1;
-  re->sub_[1] = re2;
+  Regexp** subs = re->sub();
+  subs[0] = re1;
+  subs[1] = re2;
   return re;
 }
 
@@ -315,9 +324,10 @@
     Regexp* nre = new Regexp(kRegexpConcat, f);
     nre->AllocSub(min);
     VLOG(1) << "Simplify " << min;
+    Regexp** nre_subs = nre->sub();
     for (int i = 0; i < min-1; i++)
-      nre->sub_[i] = re->Incref();
-    nre->sub_[min-1] = Regexp::Plus(re->Incref(), f);
+      nre_subs[i] = re->Incref();
+    nre_subs[min-1] = Regexp::Plus(re->Incref(), f);
     return nre;
   }
 
@@ -338,8 +348,9 @@
   if (min > 0) {
     nre = new Regexp(kRegexpConcat, f);
     nre->AllocSub(min);
+    Regexp** nre_subs = nre->sub();
     for (int i = 0; i < min; i++)
-      nre->sub_[i] = re->Incref();
+      nre_subs[i] = re->Incref();
   }
 
   // Build and attach suffix: (x(x(x)?)?)?
@@ -370,9 +381,9 @@
 
   // Special cases
   if (cc->empty())
-    return new Regexp(kRegexpNoMatch, re->parse_flags_);
+    return new Regexp(kRegexpNoMatch, re->parse_flags());
   if (cc->full())
-    return new Regexp(kRegexpAnyChar, re->parse_flags_);
+    return new Regexp(kRegexpAnyChar, re->parse_flags());
 
   return re->Incref();
 }
diff --git a/re2/testing/charclass_test.cc b/re2/testing/charclass_test.cc
index 217cef8..a3764d4 100644
--- a/re2/testing/charclass_test.cc
+++ b/re2/testing/charclass_test.cc
@@ -82,21 +82,26 @@
     { {-1} } },
 };
 
+template<class CharClass>
 static void Broke(const char *desc, const CCTest* t, CharClass* cc) {
-  printf("\n");
-  printf("CharClass added: [%s]", desc);
-  for (int k = 0; t->add[k].lo >= 0; k++)
-    printf(" %d-%d", t->add[k].lo, t->add[k].hi);
-  printf("\n");
-  if (t->remove >= 0)
-    printf("Removed > %d\n", t->remove);
-  printf("\twant:");
-  for (int k = 0; t->final[k].lo >= 0; k++)
-    printf(" %d-%d", t->final[k].lo, t->final[k].hi);
-  printf("\n");
+  if (t == NULL) {
+    printf("\t%s:", desc);
+  } else {
+    printf("\n");
+    printf("CharClass added: [%s]", desc);
+    for (int k = 0; t->add[k].lo >= 0; k++)
+      printf(" %d-%d", t->add[k].lo, t->add[k].hi);
+    printf("\n");
+    if (t->remove >= 0)
+      printf("Removed > %d\n", t->remove);
+    printf("\twant:");
+    for (int k = 0; t->final[k].lo >= 0; k++)
+      printf(" %d-%d", t->final[k].lo, t->final[k].hi);
+    printf("\n");
+    printf("\thave:");
+  }
 
-  printf("\thave:");
-  for (CharClass::iterator it = cc->begin(); it != cc->end(); ++it)
+  for (typename CharClass::iterator it = cc->begin(); it != cc->end(); ++it)
     printf(" %d-%d", it->lo, it->hi);
   printf("\n");
 }
@@ -108,8 +113,29 @@
   return false;
 }
 
+// Helpers to make templated CorrectCC work with both CharClass and CharClassBuilder.
+
+CharClass* Negate(CharClass *cc) {
+  return cc->Negate();
+}
+
+void Delete(CharClass* cc) {
+  cc->Delete();
+}
+
+CharClassBuilder* Negate(CharClassBuilder* cc) {
+  CharClassBuilder* ncc = cc->Copy();
+  ncc->Negate();
+  return ncc;
+}
+
+void Delete(CharClassBuilder* cc) {
+  delete cc;
+}
+
+template<class CharClass>
 bool CorrectCC(CharClass *cc, CCTest *t, const char *desc) {
-  CharClass::iterator it = cc->begin();
+  typename CharClass::iterator it = cc->begin();
   int size = 0;
   for (int j = 0; t->final[j].lo >= 0; j++, ++it) {
     if (it == cc->end() ||
@@ -141,46 +167,55 @@
     }
   }
 
-  CharClass* ncc = cc->Copy();
-  ncc->Negate();
+  CharClass* ncc = Negate(cc);
   for (int j = 0; j < 101; j++) {
     if (j == 100)
       j = Runemax;
     if (ShouldContain(t, j) == ncc->Contains(j)) {
       Broke(desc, t, cc);
+      Broke("ncc", NULL, ncc);
       printf("want ncc contains(%d)!=%d, got %d\n",
              j, ShouldContain(t, j), ncc->Contains(j));
-      delete ncc;
+      Delete(ncc);
       return false;
     }
     if (ncc->size() != Runemax+1 - cc->size()) {
       Broke(desc, t, cc);
+      Broke("ncc", NULL, ncc);
       printf("ncc size should be %d is %d\n",
              Runemax+1 - cc->size(), ncc->size());
-      delete ncc;
+      Delete(ncc);
       return false;
     }
   }
-  delete ncc;
+  Delete(ncc);
   return true;
 }
 
-TEST(TestCharClass, Adds) {
+TEST(TestCharClassBuilder, Adds) {
   int nfail = 0;
   for (int i = 0; i < arraysize(tests); i++) {
-    CharClass cc;
+    CharClassBuilder ccb;
     CCTest* t = &tests[i];
     for (int j = 0; t->add[j].lo >= 0; j++)
-      cc.AddRange(t->add[j].lo, t->add[j].hi);
+      ccb.AddRange(t->add[j].lo, t->add[j].hi);
     if (t->remove >= 0)
-      cc.RemoveAbove(t->remove);
-    if (!CorrectCC(&cc, t, "before copy"))
+      ccb.RemoveAbove(t->remove);
+    if (!CorrectCC(&ccb, t, "before copy (CharClassBuilder)"))
       nfail++;
+    CharClass* cc = ccb.GetCharClass();
+    if (!CorrectCC(cc, t, "before copy (CharClass)"))
+      nfail++;
+    cc->Delete();
 
-    CharClass *cc1 = cc.Copy();
-    if (!CorrectCC(cc1, t, "after copy"))
+    CharClassBuilder *ccb1 = ccb.Copy();
+    if (!CorrectCC(ccb1, t, "after copy (CharClassBuilder)"))
       nfail++;
-    delete cc1;
+    cc = ccb.GetCharClass();
+    if (!CorrectCC(cc, t, "after copy (CharClass)"))
+      nfail++;
+    cc->Delete();
+    delete ccb1;
   }
   EXPECT_EQ(nfail, 0);
 }
diff --git a/re2/testing/regexp_test.cc b/re2/testing/regexp_test.cc
new file mode 100644
index 0000000..6685c37
--- /dev/null
+++ b/re2/testing/regexp_test.cc
@@ -0,0 +1,43 @@
+// Copyright 2006 The RE2 Authors.  All Rights Reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Test parse.cc, dump.cc, and tostring.cc.
+
+#include <string>
+#include <vector>
+#include "util/test.h"
+#include "re2/regexp.h"
+
+namespace re2 {
+
+// Test that overflowed ref counts work.
+TEST(Regexp, BigRef) {
+  Regexp* re;
+  
+  re = Regexp::Parse("x", Regexp::NoParseFlags, NULL);
+  for (int i = 0; i < 100000; i++)
+    re->Incref();
+  for (int i = 0; i < 100000; i++)
+    re->Decref();
+  CHECK_EQ(re->Ref(), 1);
+  re->Decref();
+}
+
+// Test that very large Concats work.
+// Depends on overflowed ref counts working.
+TEST(Regexp, BigConcat) {
+  Regexp* x;
+  x = Regexp::Parse("x", Regexp::NoParseFlags, NULL);
+  vector<Regexp*> v(90000, x);  // ToString bails out at 100000
+  for (int i = 0; i < v.size(); i++)
+    x->Incref();
+  CHECK_EQ(x->Ref(), 1 + v.size()) << x->Ref();
+  Regexp* re = Regexp::Concat(&v[0], v.size(), Regexp::NoParseFlags);
+  CHECK_EQ(re->ToString(), string(v.size(), 'x'));
+  re->Decref();
+  CHECK_EQ(x->Ref(), 1) << x->Ref();
+  x->Decref();
+}
+
+}  // namespace re2
diff --git a/re2/tostring.cc b/re2/tostring.cc
index 9792eac..a4aabbe 100644
--- a/re2/tostring.cc
+++ b/re2/tostring.cc
@@ -3,7 +3,7 @@
 // license that can be found in the LICENSE file.
 
 // Format a regular expression structure as a string.
-// Tested by parse_unittest.cc
+// Tested by parse_test.cc
 
 #include "util/util.h"
 #include "re2/regexp.h"
@@ -250,8 +250,6 @@
 
     case kRegexpCharClass: {
       if (re->cc()->size() == 0) {
-        // Simplify is supposed to rewrite this to NoMatch.
-        LOG(DFATAL) << "Empty char class in ToString.";
         t_->append("[^\\x00-\\x{10ffff}]");
         break;
       }
@@ -260,14 +258,13 @@
       // non-character 0xFFFE.
       CharClass* cc = re->cc();
       if (cc->Contains(0xFFFE)) {
-        cc = cc->Copy();
-        cc->Negate();
+        cc = cc->Negate();
         t_->append("^");
       }
       for (CharClass::iterator i = cc->begin(); i != cc->end(); ++i)
         AppendCCRange(t_, i->lo, i->hi);
       if (cc != re->cc())
-        delete cc;
+        cc->Delete();
       t_->append("]");
       break;
     }
diff --git a/re2/walker-inl.h b/re2/walker-inl.h
index 2d3158e..4d2045f 100644
--- a/re2/walker-inl.h
+++ b/re2/walker-inl.h
@@ -191,12 +191,13 @@
       }
       default: {
         if (re->nsub_ > 0) {
+          Regexp** sub = re->sub();
           if (s->n < re->nsub_) {
-            if (use_copy && s->n > 0 && re->sub_[s->n - 1] == re->sub_[s->n]) {
+            if (use_copy && s->n > 0 && sub[s->n - 1] == sub[s->n]) {
               s->child_args[s->n] = Copy(s->child_args[s->n - 1]);
               s->n++;
             } else {
-              stack_->push(WalkState<T>(re->sub_[s->n], s->pre_arg));
+              stack_->push(WalkState<T>(sub[s->n], s->pre_arg));
             }
             continue;
           }