AAPT2: Ensure style strings are always first in StringPool

Move the styled strings to a separate section of the StringPool so
that sorting can never mess up the order of Styles.

Bug: 63570514
Test: make aapt2_tests
Change-Id: Id2ce1355b92be1bb31ce0daa7e54ae9b5b6c2ffe

16 files changed, 407 insertions, 437 deletions

diff --git a/tools/aapt2/ResourceParser.cpp b/tools/aapt2/ResourceParser.cpp
index 9a37913f0edc..a5783a532e23 100644
--- a/tools/aapt2/ResourceParser.cpp
+++ b/tools/aapt2/ResourceParser.cpp
@@ -268,8 +268,7 @@ bool ResourceParser::Parse(xml::XmlPullParser* parser) {
       continue;
     }
 
-    if (!parser->element_namespace().empty() ||
-        parser->element_name() != "resources") {
+    if (!parser->element_namespace().empty() || parser->element_name() != "resources") {
       diag_->Error(DiagMessage(source_.WithLine(parser->line_number()))
                    << "root element must be <resources>");
       return false;
@@ -328,8 +327,7 @@ bool ResourceParser::ParseResources(xml::XmlPullParser* parser) {
     parsed_resource.comment = std::move(comment);
 
     // Extract the product name if it exists.
-    if (Maybe<StringPiece> maybe_product =
-            xml::FindNonEmptyAttribute(parser, "product")) {
+    if (Maybe<StringPiece> maybe_product = xml::FindNonEmptyAttribute(parser, "product")) {
       parsed_resource.product = maybe_product.value().to_string();
     }
 
@@ -348,10 +346,8 @@ bool ResourceParser::ParseResources(xml::XmlPullParser* parser) {
   for (const ResourceName& stripped_resource : stripped_resources) {
     if (!table_->FindResource(stripped_resource)) {
       // Failed to find the resource.
-      diag_->Error(DiagMessage(source_)
-                   << "resource '" << stripped_resource
-                   << "' "
-                      "was filtered out but no product variant remains");
+      diag_->Error(DiagMessage(source_) << "resource '" << stripped_resource
+                                        << "' was filtered out but no product variant remains");
       error = true;
     }
   }
@@ -589,7 +585,7 @@ std::unique_ptr<Item> ResourceParser::ParseXml(xml::XmlPullParser* parser,
     // This can only be a StyledString.
     std::unique_ptr<StyledString> styled_string =
         util::make_unique<StyledString>(table_->string_pool.MakeRef(
-            style_string, StringPool::Context(StringPool::Context::kStylePriority, config_)));
+            style_string, StringPool::Context(StringPool::Context::kNormalPriority, config_)));
     styled_string->untranslatable_sections = std::move(untranslatable_sections);
     return std::move(styled_string);
   }
diff --git a/tools/aapt2/ResourceParser_test.cpp b/tools/aapt2/ResourceParser_test.cpp
index d47a529036bc..1683c64a6a5c 100644
--- a/tools/aapt2/ResourceParser_test.cpp
+++ b/tools/aapt2/ResourceParser_test.cpp
@@ -117,7 +117,7 @@ TEST_F(ResourceParserTest, ParseStyledString) {
   StyledString* str = test::GetValue<StyledString>(&table_, "string/foo");
   ASSERT_THAT(str, NotNull());
 
-  EXPECT_THAT(*str->value->str, Eq("This is my aunt\u2019s fickle string"));
+  EXPECT_THAT(str->value->value, Eq("This is my aunt\u2019s fickle string"));
   EXPECT_THAT(str->value->spans, SizeIs(2));
   EXPECT_THAT(str->untranslatable_sections, IsEmpty());
 
@@ -190,7 +190,7 @@ TEST_F(ResourceParserTest, RecordUntranslateableXliffSectionsInStyledString) {
 
   StyledString* str = test::GetValue<StyledString>(&table_, "string/foo");
   ASSERT_THAT(str, NotNull());
-  EXPECT_THAT(*str->value->str, Eq("There are %1$d apples"));
+  EXPECT_THAT(str->value->value, Eq("There are %1$d apples"));
   ASSERT_THAT(str->untranslatable_sections, SizeIs(1));
 
   // We expect indices and lengths that span to include the whitespace
diff --git a/tools/aapt2/ResourceUtils.cpp b/tools/aapt2/ResourceUtils.cpp
index 6e6a2ba6fc50..f193fe0c6593 100644
--- a/tools/aapt2/ResourceUtils.cpp
+++ b/tools/aapt2/ResourceUtils.cpp
@@ -700,7 +700,7 @@ std::unique_ptr<Item> ParseBinaryResValue(const ResourceType& type, const Config
           spans++;
         }
         return util::make_unique<StyledString>(dst_pool->MakeRef(
-            style_str, StringPool::Context(StringPool::Context::kStylePriority, config)));
+            style_str, StringPool::Context(StringPool::Context::kNormalPriority, config)));
       } else {
         if (type != ResourceType::kString && util::StartsWith(str, "res/")) {
           // This must be a FileReference.
diff --git a/tools/aapt2/ResourceValues.cpp b/tools/aapt2/ResourceValues.cpp
index 947e091e2d48..eb59175edf3b 100644
--- a/tools/aapt2/ResourceValues.cpp
+++ b/tools/aapt2/ResourceValues.cpp
@@ -253,10 +253,9 @@ StyledString* StyledString::Clone(StringPool* new_pool) const {
 }
 
 void StyledString::Print(std::ostream* out) const {
-  *out << "(styled string) \"" << *value->str << "\"";
+  *out << "(styled string) \"" << value->value << "\"";
   for (const StringPool::Span& span : value->spans) {
-    *out << " " << *span.name << ":" << span.first_char << ","
-         << span.last_char;
+    *out << " " << *span.name << ":" << span.first_char << "," << span.last_char;
   }
 }
 
diff --git a/tools/aapt2/StringPool.cpp b/tools/aapt2/StringPool.cpp
index 57da5f01dcd1..705b1ab052af 100644
--- a/tools/aapt2/StringPool.cpp
+++ b/tools/aapt2/StringPool.cpp
@@ -27,7 +27,7 @@
 #include "util/BigBuffer.h"
 #include "util/Util.h"
 
-using android::StringPiece;
+using ::android::StringPiece;
 
 namespace aapt {
 
@@ -75,9 +75,14 @@ const std::string* StringPool::Ref::operator->() const {
   return &entry_->value;
 }
 
-const std::string& StringPool::Ref::operator*() const { return entry_->value; }
+const std::string& StringPool::Ref::operator*() const {
+  return entry_->value;
+}
 
-size_t StringPool::Ref::index() const { return entry_->index; }
+size_t StringPool::Ref::index() const {
+  // Account for the styles, which *always* come first.
+  return entry_->pool_->styles_.size() + entry_->index_;
+}
 
 const StringPool::Context& StringPool::Ref::GetContext() const {
   return entry_->context;
@@ -104,8 +109,7 @@ StringPool::StyleRef::~StyleRef() {
   }
 }
 
-StringPool::StyleRef& StringPool::StyleRef::operator=(
-    const StringPool::StyleRef& rhs) {
+StringPool::StyleRef& StringPool::StyleRef::operator=(const StringPool::StyleRef& rhs) {
   if (rhs.entry_ != nullptr) {
     rhs.entry_->ref_++;
   }
@@ -118,7 +122,7 @@ StringPool::StyleRef& StringPool::StyleRef::operator=(
 }
 
 bool StringPool::StyleRef::operator==(const StyleRef& rhs) const {
-  if (entry_->str != rhs.entry_->str) {
+  if (entry_->value != rhs.entry_->value) {
     return false;
   }
 
@@ -137,7 +141,9 @@ bool StringPool::StyleRef::operator==(const StyleRef& rhs) const {
   return true;
 }
 
-bool StringPool::StyleRef::operator!=(const StyleRef& rhs) const { return !operator==(rhs); }
+bool StringPool::StyleRef::operator!=(const StyleRef& rhs) const {
+  return !operator==(rhs);
+}
 
 const StringPool::StyleEntry* StringPool::StyleRef::operator->() const {
   return entry_;
@@ -147,23 +153,24 @@ const StringPool::StyleEntry& StringPool::StyleRef::operator*() const {
   return *entry_;
 }
 
-size_t StringPool::StyleRef::index() const { return entry_->str.index(); }
+size_t StringPool::StyleRef::index() const {
+  return entry_->index_;
+}
 
 const StringPool::Context& StringPool::StyleRef::GetContext() const {
-  return entry_->str.GetContext();
+  return entry_->context;
 }
 
 StringPool::Ref StringPool::MakeRef(const StringPiece& str) {
   return MakeRefImpl(str, Context{}, true);
 }
 
-StringPool::Ref StringPool::MakeRef(const StringPiece& str,
-                                    const Context& context) {
+StringPool::Ref StringPool::MakeRef(const StringPiece& str, const Context& context) {
   return MakeRefImpl(str, context, true);
 }
 
-StringPool::Ref StringPool::MakeRefImpl(const StringPiece& str,
-                                        const Context& context, bool unique) {
+StringPool::Ref StringPool::MakeRefImpl(const StringPiece& str, const Context& context,
+                                        bool unique) {
   if (unique) {
     auto iter = indexed_strings_.find(str);
     if (iter != std::end(indexed_strings_)) {
@@ -171,82 +178,87 @@ StringPool::Ref StringPool::MakeRefImpl(const StringPiece& str,
     }
   }
 
-  Entry* entry = new Entry();
+  std::unique_ptr<Entry> entry(new Entry());
   entry->value = str.to_string();
   entry->context = context;
-  entry->index = strings_.size();
+  entry->index_ = strings_.size();
   entry->ref_ = 0;
-  strings_.emplace_back(entry);
-  indexed_strings_.insert(std::make_pair(StringPiece(entry->value), entry));
-  return Ref(entry);
+  entry->pool_ = this;
+
+  Entry* borrow = entry.get();
+  strings_.emplace_back(std::move(entry));
+  indexed_strings_.insert(std::make_pair(StringPiece(borrow->value), borrow));
+  return Ref(borrow);
 }
 
 StringPool::StyleRef StringPool::MakeRef(const StyleString& str) {
   return MakeRef(str, Context{});
 }
 
-StringPool::StyleRef StringPool::MakeRef(const StyleString& str,
-                                         const Context& context) {
-  Entry* entry = new Entry();
+StringPool::StyleRef StringPool::MakeRef(const StyleString& str, const Context& context) {
+  std::unique_ptr<StyleEntry> entry(new StyleEntry());
   entry->value = str.str;
   entry->context = context;
-  entry->index = strings_.size();
+  entry->index_ = styles_.size();
   entry->ref_ = 0;
-  strings_.emplace_back(entry);
-  indexed_strings_.insert(std::make_pair(StringPiece(entry->value), entry));
-
-  StyleEntry* style_entry = new StyleEntry();
-  style_entry->str = Ref(entry);
   for (const aapt::Span& span : str.spans) {
-    style_entry->spans.emplace_back(
-        Span{MakeRef(span.name), span.first_char, span.last_char});
+    entry->spans.emplace_back(Span{MakeRef(span.name), span.first_char, span.last_char});
   }
-  style_entry->ref_ = 0;
-  styles_.emplace_back(style_entry);
-  return StyleRef(style_entry);
+
+  StyleEntry* borrow = entry.get();
+  styles_.emplace_back(std::move(entry));
+  return StyleRef(borrow);
 }
 
 StringPool::StyleRef StringPool::MakeRef(const StyleRef& ref) {
-  Entry* entry = new Entry();
-  entry->value = *ref.entry_->str;
-  entry->context = ref.entry_->str.entry_->context;
-  entry->index = strings_.size();
+  std::unique_ptr<StyleEntry> entry(new StyleEntry());
+  entry->value = ref.entry_->value;
+  entry->context = ref.entry_->context;
+  entry->index_ = styles_.size();
   entry->ref_ = 0;
-  strings_.emplace_back(entry);
-  indexed_strings_.insert(std::make_pair(StringPiece(entry->value), entry));
-
-  StyleEntry* style_entry = new StyleEntry();
-  style_entry->str = Ref(entry);
   for (const Span& span : ref.entry_->spans) {
-    style_entry->spans.emplace_back(
-        Span{MakeRef(*span.name), span.first_char, span.last_char});
+    entry->spans.emplace_back(Span{MakeRef(*span.name), span.first_char, span.last_char});
+  }
+
+  StyleEntry* borrow = entry.get();
+  styles_.emplace_back(std::move(entry));
+  return StyleRef(borrow);
+}
+
+void StringPool::ReAssignIndices() {
+  // Assign the style indices.
+  const size_t style_len = styles_.size();
+  for (size_t index = 0; index < style_len; index++) {
+    styles_[index]->index_ = index;
+  }
+
+  // Assign the string indices.
+  const size_t string_len = strings_.size();
+  for (size_t index = 0; index < string_len; index++) {
+    strings_[index]->index_ = index;
   }
-  style_entry->ref_ = 0;
-  styles_.emplace_back(style_entry);
-  return StyleRef(style_entry);
 }
 
 void StringPool::Merge(StringPool&& pool) {
-  indexed_strings_.insert(pool.indexed_strings_.begin(),
-                          pool.indexed_strings_.end());
-  pool.indexed_strings_.clear();
-  std::move(pool.strings_.begin(), pool.strings_.end(),
-            std::back_inserter(strings_));
-  pool.strings_.clear();
-  std::move(pool.styles_.begin(), pool.styles_.end(),
-            std::back_inserter(styles_));
+  // First, change the owning pool for the incoming strings.
+  for (std::unique_ptr<Entry>& entry : pool.strings_) {
+    entry->pool_ = this;
+  }
+
+  // Now move the styles, strings, and indices over.
+  std::move(pool.styles_.begin(), pool.styles_.end(), std::back_inserter(styles_));
   pool.styles_.clear();
+  std::move(pool.strings_.begin(), pool.strings_.end(), std::back_inserter(strings_));
+  pool.strings_.clear();
+  indexed_strings_.insert(pool.indexed_strings_.begin(), pool.indexed_strings_.end());
+  pool.indexed_strings_.clear();
 
-  // Assign the indices.
-  const size_t len = strings_.size();
-  for (size_t index = 0; index < len; index++) {
-    strings_[index]->index = index;
-  }
+  ReAssignIndices();
 }
 
-void StringPool::HintWillAdd(size_t stringCount, size_t styleCount) {
-  strings_.reserve(strings_.size() + stringCount);
-  styles_.reserve(styles_.size() + styleCount);
+void StringPool::HintWillAdd(size_t string_count, size_t style_count) {
+  strings_.reserve(strings_.size() + string_count);
+  styles_.reserve(styles_.size() + style_count);
 }
 
 void StringPool::Prune() {
@@ -262,47 +274,42 @@ void StringPool::Prune() {
 
   auto end_iter2 =
       std::remove_if(strings_.begin(), strings_.end(),
-                     [](const std::unique_ptr<Entry>& entry) -> bool {
-                       return entry->ref_ <= 0;
-                     });
-
-  auto end_iter3 =
-      std::remove_if(styles_.begin(), styles_.end(),
-                     [](const std::unique_ptr<StyleEntry>& entry) -> bool {
-                       return entry->ref_ <= 0;
-                     });
-
-  // Remove the entries at the end or else we'll be accessing
-  // a deleted string from the StyleEntry.
+                     [](const std::unique_ptr<Entry>& entry) -> bool { return entry->ref_ <= 0; });
+  auto end_iter3 = std::remove_if(
+      styles_.begin(), styles_.end(),
+      [](const std::unique_ptr<StyleEntry>& entry) -> bool { return entry->ref_ <= 0; });
+
+  // Remove the entries at the end or else we'll be accessing a deleted string from the StyleEntry.
   strings_.erase(end_iter2, strings_.end());
   styles_.erase(end_iter3, styles_.end());
 
-  // Reassign the indices.
-  const size_t len = strings_.size();
-  for (size_t index = 0; index < len; index++) {
-    strings_[index]->index = index;
-  }
+  ReAssignIndices();
 }
 
-void StringPool::Sort(
-    const std::function<bool(const Entry&, const Entry&)>& cmp) {
-  std::sort(
-      strings_.begin(), strings_.end(),
-      [&cmp](const std::unique_ptr<Entry>& a,
-             const std::unique_ptr<Entry>& b) -> bool { return cmp(*a, *b); });
-
-  // Assign the indices.
-  const size_t len = strings_.size();
-  for (size_t index = 0; index < len; index++) {
-    strings_[index]->index = index;
+template <typename E>
+static void SortEntries(
+    std::vector<std::unique_ptr<E>>& entries,
+    const std::function<int(const StringPool::Context&, const StringPool::Context&)>& cmp) {
+  using UEntry = std::unique_ptr<E>;
+
+  if (cmp != nullptr) {
+    std::sort(entries.begin(), entries.end(), [&cmp](const UEntry& a, const UEntry& b) -> bool {
+      int r = cmp(a->context, b->context);
+      if (r == 0) {
+        r = a->value.compare(b->value);
+      }
+      return r < 0;
+    });
+  } else {
+    std::sort(entries.begin(), entries.end(),
+              [](const UEntry& a, const UEntry& b) -> bool { return a->value < b->value; });
   }
+}
 
-  // Reorder the styles.
-  std::sort(styles_.begin(), styles_.end(),
-            [](const std::unique_ptr<StyleEntry>& lhs,
-               const std::unique_ptr<StyleEntry>& rhs) -> bool {
-              return lhs->str.index() < rhs->str.index();
-            });
+void StringPool::Sort(const std::function<int(const Context&, const Context&)>& cmp) {
+  SortEntries(styles_, cmp);
+  SortEntries(strings_, cmp);
+  ReAssignIndices();
 }
 
 template <typename T>
@@ -327,60 +334,31 @@ static size_t EncodedLengthUnits(size_t length) {
   return length > kMaxSize ? 2 : 1;
 }
 
-bool StringPool::Flatten(BigBuffer* out, const StringPool& pool, bool utf8) {
-  const size_t start_index = out->size();
-  android::ResStringPool_header* header =
-      out->NextBlock<android::ResStringPool_header>();
-  header->header.type = android::RES_STRING_POOL_TYPE;
-  header->header.headerSize = sizeof(*header);
-  header->stringCount = pool.size();
+static void EncodeString(const std::string& str, const bool utf8, BigBuffer* out) {
   if (utf8) {
-    header->flags |= android::ResStringPool_header::UTF8_FLAG;
-  }
-
-  uint32_t* indices =
-      pool.size() != 0 ? out->NextBlock<uint32_t>(pool.size()) : nullptr;
-
-  uint32_t* style_indices = nullptr;
-  if (!pool.styles_.empty()) {
-    header->styleCount = pool.styles_.back()->str.index() + 1;
-    style_indices = out->NextBlock<uint32_t>(header->styleCount);
-  }
-
-  const size_t before_strings_index = out->size();
-  header->stringsStart = before_strings_index - start_index;
-
-  for (const auto& entry : pool) {
-    *indices = out->size() - before_strings_index;
-    indices++;
+    const std::string& encoded = str;
+    const ssize_t utf16_length =
+        utf8_to_utf16_length(reinterpret_cast<const uint8_t*>(str.data()), str.size());
+    CHECK(utf16_length >= 0);
 
-    if (utf8) {
-      const std::string& encoded = entry->value;
-      const ssize_t utf16_length = utf8_to_utf16_length(
-          reinterpret_cast<const uint8_t*>(entry->value.data()),
-          entry->value.size());
-      CHECK(utf16_length >= 0);
+    const size_t total_size = EncodedLengthUnits<char>(utf16_length) +
+                              EncodedLengthUnits<char>(encoded.length()) + encoded.size() + 1;
 
-      const size_t total_size = EncodedLengthUnits<char>(utf16_length) +
-                                EncodedLengthUnits<char>(encoded.length()) +
-                                encoded.size() + 1;
+    char* data = out->NextBlock<char>(total_size);
 
-      char* data = out->NextBlock<char>(total_size);
-
-      // First encode the UTF16 string length.
-      data = EncodeLength(data, utf16_length);
+    // First encode the UTF16 string length.
+    data = EncodeLength(data, utf16_length);
 
-      // Now encode the size of the real UTF8 string.
-      data = EncodeLength(data, encoded.length());
-      strncpy(data, encoded.data(), encoded.size());
+    // Now encode the size of the real UTF8 string.
+    data = EncodeLength(data, encoded.length());
+    strncpy(data, encoded.data(), encoded.size());
 
     } else {
-      const std::u16string encoded = util::Utf8ToUtf16(entry->value);
+      const std::u16string encoded = util::Utf8ToUtf16(str);
       const ssize_t utf16_length = encoded.size();
 
       // Total number of 16-bit words to write.
-      const size_t total_size =
-          EncodedLengthUnits<char16_t>(utf16_length) + encoded.size() + 1;
+      const size_t total_size = EncodedLengthUnits<char16_t>(utf16_length) + encoded.size() + 1;
 
       char16_t* data = out->NextBlock<char16_t>(total_size);
 
@@ -395,31 +373,55 @@ bool StringPool::Flatten(BigBuffer* out, const StringPool& pool, bool utf8) {
       // The null-terminating character is already here due to the block of data
       // being set to 0s on allocation.
     }
+}
+
+bool StringPool::Flatten(BigBuffer* out, const StringPool& pool, bool utf8) {
+  const size_t start_index = out->size();
+  android::ResStringPool_header* header = out->NextBlock<android::ResStringPool_header>();
+  header->header.type = util::HostToDevice16(android::RES_STRING_POOL_TYPE);
+  header->header.headerSize = util::HostToDevice16(sizeof(*header));
+  header->stringCount = util::HostToDevice32(pool.size());
+  header->styleCount = util::HostToDevice32(pool.styles_.size());
+  if (utf8) {
+    header->flags |= android::ResStringPool_header::UTF8_FLAG;
   }
 
-  out->Align4();
+  uint32_t* indices = pool.size() != 0 ? out->NextBlock<uint32_t>(pool.size()) : nullptr;
+  uint32_t* style_indices =
+      pool.styles_.size() != 0 ? out->NextBlock<uint32_t>(pool.styles_.size()) : nullptr;
 
-  if (!pool.styles_.empty()) {
-    const size_t before_styles_index = out->size();
-    header->stylesStart = before_styles_index - start_index;
+  const size_t before_strings_index = out->size();
+  header->stringsStart = before_strings_index - start_index;
 
-    size_t current_index = 0;
-    for (const auto& entry : pool.styles_) {
-      while (entry->str.index() > current_index) {
-        style_indices[current_index++] = out->size() - before_styles_index;
+  // Styles always come first.
+  for (const std::unique_ptr<StyleEntry>& entry : pool.styles_) {
+    *indices++ = out->size() - before_strings_index;
+    EncodeString(entry->value, utf8, out);
+  }
 
-        uint32_t* span_offset = out->NextBlock<uint32_t>();
-        *span_offset = android::ResStringPool_span::END;
-      }
-      style_indices[current_index++] = out->size() - before_styles_index;
-
-      android::ResStringPool_span* span =
-          out->NextBlock<android::ResStringPool_span>(entry->spans.size());
-      for (const auto& s : entry->spans) {
-        span->name.index = s.name.index();
-        span->firstChar = s.first_char;
-        span->lastChar = s.last_char;
-        span++;
+  for (const std::unique_ptr<Entry>& entry : pool.strings_) {
+    *indices++ = out->size() - before_strings_index;
+    EncodeString(entry->value, utf8, out);
+  }
+
+  out->Align4();
+
+  if (style_indices != nullptr) {
+    const size_t before_styles_index = out->size();
+    header->stylesStart = util::HostToDevice32(before_styles_index - start_index);
+
+    for (const std::unique_ptr<StyleEntry>& entry : pool.styles_) {
+      *style_indices++ = out->size() - before_styles_index;
+
+      if (!entry->spans.empty()) {
+        android::ResStringPool_span* span =
+            out->NextBlock<android::ResStringPool_span>(entry->spans.size());
+        for (const Span& s : entry->spans) {
+          span->name.index = util::HostToDevice32(s.name.index());
+          span->firstChar = util::HostToDevice32(s.first_char);
+          span->lastChar = util::HostToDevice32(s.last_char);
+          span++;
+        }
       }
 
       uint32_t* spanEnd = out->NextBlock<uint32_t>();
@@ -436,7 +438,7 @@ bool StringPool::Flatten(BigBuffer* out, const StringPool& pool, bool utf8) {
     memset(padding, 0xff, padding_length);
     out->Align4();
   }
-  header->header.size = out->size() - start_index;
+  header->header.size = util::HostToDevice32(out->size() - start_index);
   return true;
 }
 
diff --git a/tools/aapt2/StringPool.h b/tools/aapt2/StringPool.h
index d1232a29b5aa..8350d0d09108 100644
--- a/tools/aapt2/StringPool.h
+++ b/tools/aapt2/StringPool.h
@@ -42,12 +42,16 @@ struct StyleString {
   std::vector<Span> spans;
 };
 
+// A StringPool for storing the value of String and StyledString resources.
+// Styles and Strings are stored separately, since the runtime variant of this
+// class -- ResStringPool -- requires that styled strings *always* appear first, since their
+// style data is stored as an array indexed by the same indices as the main string pool array.
+// Otherwise, the style data array would have to be sparse and take up more space.
 class StringPool {
  public:
   class Context {
    public:
     enum : uint32_t {
-      kStylePriority = 0u,
       kHighPriority = 1u,
       kNormalPriority = 0x7fffffffu,
       kLowPriority = 0xffffffffu,
@@ -58,8 +62,8 @@ class StringPool {
     Context() = default;
     Context(uint32_t p, const ConfigDescription& c) : priority(p), config(c) {}
     explicit Context(uint32_t p) : priority(p) {}
-    explicit Context(const ConfigDescription& c)
-        : priority(kNormalPriority), config(c) {}
+    explicit Context(const ConfigDescription& c) : priority(kNormalPriority), config(c) {
+    }
   };
 
   class Entry;
@@ -116,13 +120,14 @@ class StringPool {
    public:
     std::string value;
     Context context;
-    size_t index;
 
    private:
     friend class StringPool;
     friend class Ref;
 
+    size_t index_;
     int ref_;
+    const StringPool* pool_;
   };
 
   struct Span {
@@ -133,18 +138,18 @@ class StringPool {
 
   class StyleEntry {
    public:
-    Ref str;
+    std::string value;
+    Context context;
     std::vector<Span> spans;
 
    private:
     friend class StringPool;
     friend class StyleRef;
 
+    size_t index_;
     int ref_;
   };
 
-  using const_iterator = std::vector<std::unique_ptr<Entry>>::const_iterator;
-
   static bool FlattenUtf8(BigBuffer* out, const StringPool& pool);
   static bool FlattenUtf16(BigBuffer* out, const StringPool& pool);
 
@@ -152,92 +157,61 @@ class StringPool {
   StringPool(StringPool&&) = default;
   StringPool& operator=(StringPool&&) = default;
 
-  /**
-   * Adds a string to the pool, unless it already exists. Returns
-   * a reference to the string in the pool.
-   */
+  // Adds a string to the pool, unless it already exists. Returns a reference to the string in the
+  // pool.
   Ref MakeRef(const android::StringPiece& str);
 
-  /**
-   * Adds a string to the pool, unless it already exists, with a context
-   * object that can be used when sorting the string pool. Returns
-   * a reference to the string in the pool.
-   */
+  // Adds a string to the pool, unless it already exists, with a context object that can be used
+  // when sorting the string pool. Returns a reference to the string in the pool.
   Ref MakeRef(const android::StringPiece& str, const Context& context);
 
-  /**
-   * Adds a style to the string pool and returns a reference to it.
-   */
+  // Adds a style to the string pool and returns a reference to it.
   StyleRef MakeRef(const StyleString& str);
 
-  /**
-   * Adds a style to the string pool with a context object that
-   * can be used when sorting the string pool. Returns a reference
-   * to the style in the string pool.
-   */
+  // Adds a style to the string pool with a context object that can be used when sorting the string
+  // pool. Returns a reference to the style in the string pool.
   StyleRef MakeRef(const StyleString& str, const Context& context);
 
-  /**
-   * Adds a style from another string pool. Returns a reference to the
-   * style in the string pool.
-   */
+  // Adds a style from another string pool. Returns a reference to the style in the string pool.
   StyleRef MakeRef(const StyleRef& ref);
 
-  /**
-   * Moves pool into this one without coalescing strings. When this
-   * function returns, pool will be empty.
-   */
+  // Moves pool into this one without coalescing strings. When this function returns, pool will be
+  // empty.
   void Merge(StringPool&& pool);
 
-  /**
-   * Returns the number of strings in the table.
-   */
-  inline size_t size() const;
+  inline const std::vector<std::unique_ptr<Entry>>& strings() const {
+    return strings_;
+  }
 
-  /**
-   * Reserves space for strings and styles as an optimization.
-   */
+  // Returns the number of strings in the table.
+  inline size_t size() const {
+    return styles_.size() + strings_.size();
+  }
+
+  // Reserves space for strings and styles as an optimization.
   void HintWillAdd(size_t string_count, size_t style_count);
 
-  /**
-   * Sorts the strings according to some comparison function.
-   */
-  void Sort(const std::function<bool(const Entry&, const Entry&)>& cmp);
+  // Sorts the strings according to their Context using some comparison function.
+  // Equal Contexts are further sorted by string value, lexicographically.
+  // If no comparison function is provided, values are only sorted lexicographically.
+  void Sort(const std::function<int(const Context&, const Context&)>& cmp = nullptr);
 
-  /**
-   * Removes any strings that have no references.
-   */
+  // Removes any strings that have no references.
   void Prune();
 
  private:
   DISALLOW_COPY_AND_ASSIGN(StringPool);
 
-  friend const_iterator begin(const StringPool& pool);
-  friend const_iterator end(const StringPool& pool);
-
   static bool Flatten(BigBuffer* out, const StringPool& pool, bool utf8);
 
   Ref MakeRefImpl(const android::StringPiece& str, const Context& context, bool unique);
+  void ReAssignIndices();
 
   std::vector<std::unique_ptr<Entry>> strings_;
   std::vector<std::unique_ptr<StyleEntry>> styles_;
   std::unordered_multimap<android::StringPiece, Entry*> indexed_strings_;
 };
 
-//
-// Inline implementation
-//
-
-inline size_t StringPool::size() const { return strings_.size(); }
-
-inline StringPool::const_iterator begin(const StringPool& pool) {
-  return pool.strings_.begin();
-}
-
-inline StringPool::const_iterator end(const StringPool& pool) {
-  return pool.strings_.end();
-}
-
 }  // namespace aapt
 
 #endif  // AAPT_STRING_POOL_H
diff --git a/tools/aapt2/StringPool_test.cpp b/tools/aapt2/StringPool_test.cpp
index f64a8cf20928..b1e5ce2e28a8 100644
--- a/tools/aapt2/StringPool_test.cpp
+++ b/tools/aapt2/StringPool_test.cpp
@@ -23,8 +23,12 @@
 #include "test/Test.h"
 #include "util/Util.h"
 
-using android::StringPiece;
-using android::StringPiece16;
+using ::android::StringPiece;
+using ::android::StringPiece16;
+using ::testing::Eq;
+using ::testing::Ne;
+using ::testing::NotNull;
+using ::testing::Pointee;
 
 namespace aapt {
 
@@ -32,129 +36,127 @@ TEST(StringPoolTest, InsertOneString) {
   StringPool pool;
 
   StringPool::Ref ref = pool.MakeRef("wut");
-  EXPECT_EQ(*ref, "wut");
+  EXPECT_THAT(*ref, Eq("wut"));
 }
 
 TEST(StringPoolTest, InsertTwoUniqueStrings) {
   StringPool pool;
 
-  StringPool::Ref ref = pool.MakeRef("wut");
-  StringPool::Ref ref2 = pool.MakeRef("hey");
+  StringPool::Ref ref_a = pool.MakeRef("wut");
+  StringPool::Ref ref_b = pool.MakeRef("hey");
 
-  EXPECT_EQ(*ref, "wut");
-  EXPECT_EQ(*ref2, "hey");
+  EXPECT_THAT(*ref_a, Eq("wut"));
+  EXPECT_THAT(*ref_b, Eq("hey"));
 }
 
 TEST(StringPoolTest, DoNotInsertNewDuplicateString) {
   StringPool pool;
 
-  StringPool::Ref ref = pool.MakeRef("wut");
-  StringPool::Ref ref2 = pool.MakeRef("wut");
+  StringPool::Ref ref_a = pool.MakeRef("wut");
+  StringPool::Ref ref_b = pool.MakeRef("wut");
 
-  EXPECT_EQ(*ref, "wut");
-  EXPECT_EQ(*ref2, "wut");
-  EXPECT_EQ(1u, pool.size());
+  EXPECT_THAT(*ref_a, Eq("wut"));
+  EXPECT_THAT(*ref_b, Eq("wut"));
+  EXPECT_THAT(pool.size(), Eq(1u));
 }
 
 TEST(StringPoolTest, MaintainInsertionOrderIndex) {
   StringPool pool;
 
-  StringPool::Ref ref = pool.MakeRef("z");
-  StringPool::Ref ref2 = pool.MakeRef("a");
-  StringPool::Ref ref3 = pool.MakeRef("m");
+  StringPool::Ref ref_a = pool.MakeRef("z");
+  StringPool::Ref ref_b = pool.MakeRef("a");
+  StringPool::Ref ref_c = pool.MakeRef("m");
 
-  EXPECT_EQ(0u, ref.index());
-  EXPECT_EQ(1u, ref2.index());
-  EXPECT_EQ(2u, ref3.index());
+  EXPECT_THAT(ref_a.index(), Eq(0u));
+  EXPECT_THAT(ref_b.index(), Eq(1u));
+  EXPECT_THAT(ref_c.index(), Eq(2u));
 }
 
 TEST(StringPoolTest, PruneStringsWithNoReferences) {
   StringPool pool;
 
-  StringPool::Ref refA = pool.MakeRef("foo");
+  StringPool::Ref ref_a = pool.MakeRef("foo");
+
+  {
+    StringPool::Ref ref_b = pool.MakeRef("wut");
+    EXPECT_THAT(*ref_b, Eq("wut"));
+    EXPECT_THAT(pool.size(), Eq(2u));
+    pool.Prune();
+    EXPECT_THAT(pool.size(), Eq(2u));
+  }
+  EXPECT_THAT(pool.size(), Eq(2u));
+
   {
-    StringPool::Ref ref = pool.MakeRef("wut");
-    EXPECT_EQ(*ref, "wut");
-    EXPECT_EQ(2u, pool.size());
+    StringPool::Ref ref_c = pool.MakeRef("bar");
+    EXPECT_THAT(pool.size(), Eq(3u));
+
+    pool.Prune();
+    EXPECT_THAT(pool.size(), Eq(2u));
   }
-  StringPool::Ref refB = pool.MakeRef("bar");
+  EXPECT_THAT(pool.size(), Eq(2u));
 
-  EXPECT_EQ(3u, pool.size());
   pool.Prune();
-  EXPECT_EQ(2u, pool.size());
-  StringPool::const_iterator iter = begin(pool);
-  EXPECT_EQ((*iter)->value, "foo");
-  EXPECT_LT((*iter)->index, 2u);
-  ++iter;
-  EXPECT_EQ((*iter)->value, "bar");
-  EXPECT_LT((*iter)->index, 2u);
+  EXPECT_THAT(pool.size(), Eq(1u));
 }
 
-TEST(StringPoolTest, SortAndMaintainIndexesInReferences) {
+TEST(StringPoolTest, SortAndMaintainIndexesInStringReferences) {
   StringPool pool;
 
-  StringPool::Ref ref = pool.MakeRef("z");
-  StringPool::StyleRef ref2 = pool.MakeRef(StyleString{{"a"}});
-  StringPool::Ref ref3 = pool.MakeRef("m");
+  StringPool::Ref ref_a = pool.MakeRef("z");
+  StringPool::Ref ref_b = pool.MakeRef("a");
+  StringPool::Ref ref_c = pool.MakeRef("m");
 
-  EXPECT_EQ(*ref, "z");
-  EXPECT_EQ(0u, ref.index());
+  EXPECT_THAT(*ref_a, Eq("z"));
+  EXPECT_THAT(ref_a.index(), Eq(0u));
 
-  EXPECT_EQ(*(ref2->str), "a");
-  EXPECT_EQ(1u, ref2.index());
+  EXPECT_THAT(*ref_b, Eq("a"));
+  EXPECT_THAT(ref_b.index(), Eq(1u));
 
-  EXPECT_EQ(*ref3, "m");
-  EXPECT_EQ(2u, ref3.index());
+  EXPECT_THAT(*ref_c, Eq("m"));
+  EXPECT_THAT(ref_c.index(), Eq(2u));
 
-  pool.Sort([](const StringPool::Entry& a, const StringPool::Entry& b) -> bool {
-    return a.value < b.value;
-  });
+  pool.Sort();
 
-  EXPECT_EQ(*ref, "z");
-  EXPECT_EQ(2u, ref.index());
+  EXPECT_THAT(*ref_a, Eq("z"));
+  EXPECT_THAT(ref_a.index(), Eq(2u));
 
-  EXPECT_EQ(*(ref2->str), "a");
-  EXPECT_EQ(0u, ref2.index());
+  EXPECT_THAT(*ref_b, Eq("a"));
+  EXPECT_THAT(ref_b.index(), Eq(0u));
 
-  EXPECT_EQ(*ref3, "m");
-  EXPECT_EQ(1u, ref3.index());
+  EXPECT_THAT(*ref_c, Eq("m"));
+  EXPECT_THAT(ref_c.index(), Eq(1u));
 }
 
 TEST(StringPoolTest, SortAndStillDedupe) {
   StringPool pool;
 
-  StringPool::Ref ref = pool.MakeRef("z");
-  StringPool::Ref ref2 = pool.MakeRef("a");
-  StringPool::Ref ref3 = pool.MakeRef("m");
+  StringPool::Ref ref_a = pool.MakeRef("z");
+  StringPool::Ref ref_b = pool.MakeRef("a");
+  StringPool::Ref ref_c = pool.MakeRef("m");
 
-  pool.Sort([](const StringPool::Entry& a, const StringPool::Entry& b) -> bool {
-    return a.value < b.value;
-  });
+  pool.Sort();
 
-  StringPool::Ref ref4 = pool.MakeRef("z");
-  StringPool::Ref ref5 = pool.MakeRef("a");
-  StringPool::Ref ref6 = pool.MakeRef("m");
+  StringPool::Ref ref_d = pool.MakeRef("z");
+  StringPool::Ref ref_e = pool.MakeRef("a");
+  StringPool::Ref ref_f = pool.MakeRef("m");
 
-  EXPECT_EQ(ref4.index(), ref.index());
-  EXPECT_EQ(ref5.index(), ref2.index());
-  EXPECT_EQ(ref6.index(), ref3.index());
+  EXPECT_THAT(ref_d.index(), Eq(ref_a.index()));
+  EXPECT_THAT(ref_e.index(), Eq(ref_b.index()));
+  EXPECT_THAT(ref_f.index(), Eq(ref_c.index()));
 }
 
 TEST(StringPoolTest, AddStyles) {
   StringPool pool;
 
-  StyleString str{{"android"}, {Span{{"b"}, 2, 6}}};
-
-  StringPool::StyleRef ref = pool.MakeRef(str);
-
-  EXPECT_EQ(0u, ref.index());
-  EXPECT_EQ(std::string("android"), *(ref->str));
-  ASSERT_EQ(1u, ref->spans.size());
+  StringPool::StyleRef ref = pool.MakeRef(StyleString{{"android"}, {Span{{"b"}, 2, 6}}});
+  EXPECT_THAT(ref.index(), Eq(0u));
+  EXPECT_THAT(ref->value, Eq("android"));
+  ASSERT_THAT(ref->spans.size(), Eq(1u));
 
   const StringPool::Span& span = ref->spans.front();
-  EXPECT_EQ(*(span.name), "b");
-  EXPECT_EQ(2u, span.first_char);
-  EXPECT_EQ(6u, span.last_char);
+  EXPECT_THAT(*span.name, Eq("b"));
+  EXPECT_THAT(span.first_char, Eq(2u));
+  EXPECT_THAT(span.last_char, Eq(6u));
 }
 
 TEST(StringPoolTest, DoNotDedupeStyleWithSameStringAsNonStyle) {
@@ -163,9 +165,25 @@ TEST(StringPoolTest, DoNotDedupeStyleWithSameStringAsNonStyle) {
   StringPool::Ref ref = pool.MakeRef("android");
 
   StyleString str{{"android"}};
-  StringPool::StyleRef styleRef = pool.MakeRef(str);
+  StringPool::StyleRef style_ref = pool.MakeRef(StyleString{{"android"}});
+
+  EXPECT_THAT(ref.index(), Ne(style_ref.index()));
+}
+
+TEST(StringPoolTest, StylesAndStringsAreSeparateAfterSorting) {
+  StringPool pool;
+
+  StringPool::StyleRef ref_a = pool.MakeRef(StyleString{{"beta"}});
+  StringPool::Ref ref_b = pool.MakeRef("alpha");
+  StringPool::StyleRef ref_c = pool.MakeRef(StyleString{{"alpha"}});
+
+  EXPECT_THAT(ref_b.index(), Ne(ref_c.index()));
 
-  EXPECT_NE(ref.index(), styleRef.index());
+  pool.Sort();
+
+  EXPECT_THAT(ref_c.index(), Eq(0u));
+  EXPECT_THAT(ref_a.index(), Eq(1u));
+  EXPECT_THAT(ref_b.index(), Eq(2u));
 }
 
 TEST(StringPoolTest, FlattenEmptyStringPoolUtf8) {
@@ -177,7 +195,7 @@ TEST(StringPoolTest, FlattenEmptyStringPoolUtf8) {
 
   std::unique_ptr<uint8_t[]> data = util::Copy(buffer);
   ResStringPool test;
-  ASSERT_EQ(test.setTo(data.get(), buffer.size()), NO_ERROR);
+  ASSERT_THAT(test.setTo(data.get(), buffer.size()), Eq(NO_ERROR));
 }
 
 TEST(StringPoolTest, FlattenOddCharactersUtf16) {
@@ -193,9 +211,9 @@ TEST(StringPoolTest, FlattenOddCharactersUtf16) {
   ASSERT_EQ(test.setTo(data.get(), buffer.size()), NO_ERROR);
   size_t len = 0;
   const char16_t* str = test.stringAt(0, &len);
-  EXPECT_EQ(1u, len);
-  EXPECT_EQ(u'\u093f', *str);
-  EXPECT_EQ(0u, str[1]);
+  EXPECT_THAT(len, Eq(1u));
+  EXPECT_THAT(str, Pointee(Eq(u'\u093f')));
+  EXPECT_THAT(str[1], Eq(0u));
 }
 
 constexpr const char* sLongString =
@@ -210,18 +228,20 @@ TEST(StringPoolTest, Flatten) {
 
   StringPool pool;
 
-  StringPool::Ref ref1 = pool.MakeRef("hello");
-  StringPool::Ref ref2 = pool.MakeRef("goodbye");
-  StringPool::Ref ref3 = pool.MakeRef(sLongString);
-  StringPool::Ref ref4 = pool.MakeRef("");
-  StringPool::StyleRef ref5 = pool.MakeRef(
-      StyleString{{"style"}, {Span{{"b"}, 0, 1}, Span{{"i"}, 2, 3}}});
+  StringPool::Ref ref_a = pool.MakeRef("hello");
+  StringPool::Ref ref_b = pool.MakeRef("goodbye");
+  StringPool::Ref ref_c = pool.MakeRef(sLongString);
+  StringPool::Ref ref_d = pool.MakeRef("");
+  StringPool::StyleRef ref_e =
+      pool.MakeRef(StyleString{{"style"}, {Span{{"b"}, 0, 1}, Span{{"i"}, 2, 3}}});
+
+  // Styles are always first.
+  EXPECT_THAT(ref_e.index(), Eq(0u));
 
-  EXPECT_EQ(0u, ref1.index());
-  EXPECT_EQ(1u, ref2.index());
-  EXPECT_EQ(2u, ref3.index());
-  EXPECT_EQ(3u, ref4.index());
-  EXPECT_EQ(4u, ref5.index());
+  EXPECT_THAT(ref_a.index(), Eq(1u));
+  EXPECT_THAT(ref_b.index(), Eq(2u));
+  EXPECT_THAT(ref_c.index(), Eq(3u));
+  EXPECT_THAT(ref_d.index(), Eq(4u));
 
   BigBuffer buffers[2] = {BigBuffer(1024), BigBuffer(1024)};
   StringPool::FlattenUtf8(&buffers[0], pool);
@@ -234,38 +254,37 @@ TEST(StringPoolTest, Flatten) {
     ResStringPool test;
     ASSERT_EQ(test.setTo(data.get(), buffer.size()), NO_ERROR);
 
-    EXPECT_EQ(std::string("hello"), util::GetString(test, 0));
-    EXPECT_EQ(StringPiece16(u"hello"), util::GetString16(test, 0));
+    EXPECT_THAT(util::GetString(test, 1), Eq("hello"));
+    EXPECT_THAT(util::GetString16(test, 1), Eq(u"hello"));
 
-    EXPECT_EQ(std::string("goodbye"), util::GetString(test, 1));
-    EXPECT_EQ(StringPiece16(u"goodbye"), util::GetString16(test, 1));
+    EXPECT_THAT(util::GetString(test, 2), Eq("goodbye"));
+    EXPECT_THAT(util::GetString16(test, 2), Eq(u"goodbye"));
 
-    EXPECT_EQ(StringPiece(sLongString), util::GetString(test, 2));
-    EXPECT_EQ(util::Utf8ToUtf16(sLongString), util::GetString16(test, 2).to_string());
+    EXPECT_THAT(util::GetString(test, 3), Eq(sLongString));
+    EXPECT_THAT(util::GetString16(test, 3), Eq(util::Utf8ToUtf16(sLongString)));
 
     size_t len;
-    EXPECT_TRUE(test.stringAt(3, &len) != nullptr ||
-                test.string8At(3, &len) != nullptr);
-
-    EXPECT_EQ(std::string("style"), util::GetString(test, 4));
-    EXPECT_EQ(StringPiece16(u"style"), util::GetString16(test, 4));
-
-    const ResStringPool_span* span = test.styleAt(4);
-    ASSERT_NE(nullptr, span);
-    EXPECT_EQ(std::string("b"), util::GetString(test, span->name.index));
-    EXPECT_EQ(StringPiece16(u"b"), util::GetString16(test, span->name.index));
-    EXPECT_EQ(0u, span->firstChar);
-    EXPECT_EQ(1u, span->lastChar);
+    EXPECT_TRUE(test.stringAt(4, &len) != nullptr || test.string8At(4, &len) != nullptr);
+
+    EXPECT_THAT(util::GetString(test, 0), Eq("style"));
+    EXPECT_THAT(util::GetString16(test, 0), Eq(u"style"));
+
+    const ResStringPool_span* span = test.styleAt(0);
+    ASSERT_THAT(span, NotNull());
+    EXPECT_THAT(util::GetString(test, span->name.index), Eq("b"));
+    EXPECT_THAT(util::GetString16(test, span->name.index), Eq(u"b"));
+    EXPECT_THAT(span->firstChar, Eq(0u));
+    EXPECT_THAT(span->lastChar, Eq(1u));
     span++;
 
-    ASSERT_NE(ResStringPool_span::END, span->name.index);
-    EXPECT_EQ(std::string("i"), util::GetString(test, span->name.index));
-    EXPECT_EQ(StringPiece16(u"i"), util::GetString16(test, span->name.index));
-    EXPECT_EQ(2u, span->firstChar);
-    EXPECT_EQ(3u, span->lastChar);
+    ASSERT_THAT(span->name.index, Ne(ResStringPool_span::END));
+    EXPECT_THAT(util::GetString(test, span->name.index), Eq("i"));
+    EXPECT_THAT(util::GetString16(test, span->name.index), Eq(u"i"));
+    EXPECT_THAT(span->firstChar, Eq(2u));
+    EXPECT_THAT(span->lastChar, Eq(3u));
     span++;
 
-    EXPECT_EQ(ResStringPool_span::END, span->name.index);
+    EXPECT_THAT(span->name.index, Eq(ResStringPool_span::END));
   }
 }
 
diff --git a/tools/aapt2/compile/PseudolocaleGenerator.cpp b/tools/aapt2/compile/PseudolocaleGenerator.cpp
index a031ea4c31ec..871ed4f01e77 100644
--- a/tools/aapt2/compile/PseudolocaleGenerator.cpp
+++ b/tools/aapt2/compile/PseudolocaleGenerator.cpp
@@ -120,7 +120,7 @@ std::unique_ptr<StyledString> PseudolocalizeStyledString(StyledString* string,
 
   // All Span indices are UTF-16 based, according to the resources.arsc format expected by the
   // runtime. So we will do all our processing in UTF-16, then convert back.
-  const std::u16string text16 = util::Utf8ToUtf16(*string->value->str);
+  const std::u16string text16 = util::Utf8ToUtf16(string->value->value);
 
   // Convenient wrapper around the text that allows us to work with StringPieces.
   const StringPiece16 text(text16);
diff --git a/tools/aapt2/compile/PseudolocaleGenerator_test.cpp b/tools/aapt2/compile/PseudolocaleGenerator_test.cpp
index b08e1dab35a9..711558aa51c1 100644
--- a/tools/aapt2/compile/PseudolocaleGenerator_test.cpp
+++ b/tools/aapt2/compile/PseudolocaleGenerator_test.cpp
@@ -31,7 +31,7 @@ TEST(PseudolocaleGeneratorTest, PseudolocalizeStyledString) {
       util::make_unique<StyledString>(pool.MakeRef(original_style)).get(),
       Pseudolocalizer::Method::kNone, &pool);
 
-  EXPECT_EQ(original_style.str, *new_string->value->str);
+  EXPECT_EQ(original_style.str, new_string->value->value);
   ASSERT_EQ(original_style.spans.size(), new_string->value->spans.size());
 
   EXPECT_EQ(std::string("i"), *new_string->value->spans[0].name);
@@ -52,7 +52,7 @@ TEST(PseudolocaleGeneratorTest, PseudolocalizeStyledString) {
       util::make_unique<StyledString>(pool.MakeRef(original_style)).get(),
       Pseudolocalizer::Method::kAccent, &pool);
 
-  EXPECT_EQ(std::string("[Ĥéļļö ŵöŕļð¡ one two]"), *new_string->value->str);
+  EXPECT_EQ(std::string("[Ĥéļļö ŵöŕļð¡ one two]"), new_string->value->value);
   ASSERT_EQ(original_style.spans.size(), new_string->value->spans.size());
 
   EXPECT_EQ(std::u16string(u"[").size(), new_string->value->spans[0].first_char);
@@ -79,7 +79,7 @@ TEST(PseudolocaleGeneratorTest, PseudolocalizeAdjacentNestedTags) {
       Pseudolocalizer::Method::kAccent, &pool);
   ASSERT_NE(nullptr, new_string);
   ASSERT_EQ(2u, new_string->value->spans.size());
-  EXPECT_EQ(std::string("[ɓöļð one]"), *new_string->value->str);
+  EXPECT_EQ(std::string("[ɓöļð one]"), new_string->value->value);
 
   EXPECT_EQ(std::string("b"), *new_string->value->spans[0].name);
   EXPECT_EQ(std::u16string(u"[").size(), new_string->value->spans[0].first_char);
@@ -101,7 +101,7 @@ TEST(PseudolocaleGeneratorTest, PseudolocalizeAdjacentTagsUnsorted) {
       Pseudolocalizer::Method::kAccent, &pool);
   ASSERT_NE(nullptr, new_string);
   ASSERT_EQ(2u, new_string->value->spans.size());
-  EXPECT_EQ(std::string("[ɓöļð one]"), *new_string->value->str);
+  EXPECT_EQ(std::string("[ɓöļð one]"), new_string->value->value);
 
   EXPECT_EQ(std::string("b"), *new_string->value->spans[0].name);
   EXPECT_EQ(std::u16string(u"[").size(), new_string->value->spans[0].first_char);
@@ -126,7 +126,7 @@ TEST(PseudolocaleGeneratorTest, PseudolocalizeNestedAndAdjacentTags) {
   ASSERT_EQ(4u, new_string->value->spans.size());
   EXPECT_EQ(std::string(
                 "[Ţĥîš šéñţéñçé îš ñöţ ŵĥåţ ýöû ţĥîñķ îţ îš åţ åļļ. one two three four five six]"),
-            *new_string->value->str);
+            new_string->value->value);
 
   EXPECT_EQ(std::string("b"), *new_string->value->spans[0].name);
   EXPECT_EQ(std::u16string(u"[Ţĥîš šéñţéñçé îš").size(), new_string->value->spans[0].first_char);
@@ -165,7 +165,7 @@ TEST(PseudolocaleGeneratorTest, PseudolocalizePartsOfString) {
   ASSERT_NE(nullptr, new_string);
   ASSERT_EQ(2u, new_string->value->spans.size());
   EXPECT_EQ(std::string("[Ţĥîš šĥöûļð NOT ɓé þšéûðöļöçåļîžéð. one two three four]"),
-            *new_string->value->str);
+            new_string->value->value);
 
   EXPECT_EQ(std::string("em"), *new_string->value->spans[0].name);
   EXPECT_EQ(std::u16string(u"[Ţĥîš").size(), new_string->value->spans[0].first_char);
@@ -265,7 +265,7 @@ TEST(PseudolocaleGeneratorTest, RespectUntranslateableSections) {
   ASSERT_NE(nullptr, new_styled_string);
 
   // "world" should be untranslated.
-  EXPECT_NE(std::string::npos, new_styled_string->value->str->find("world"));
+  EXPECT_NE(std::string::npos, new_styled_string->value->value.find("world"));
 
   String* new_string = test::GetValueForConfig<String>(table.get(), "android:string/bar",
                                                        test::ParseConfigOrDie("en-rXA"));
diff --git a/tools/aapt2/flatten/TableFlattener.cpp b/tools/aapt2/flatten/TableFlattener.cpp
index f4d02262f25c..e5993a65366d 100644
--- a/tools/aapt2/flatten/TableFlattener.cpp
+++ b/tools/aapt2/flatten/TableFlattener.cpp
@@ -557,19 +557,15 @@ class PackageFlattener {
 }  // namespace
 
 bool TableFlattener::Consume(IAaptContext* context, ResourceTable* table) {
-  // We must do this before writing the resources, since the string pool IDs may
-  // change.
-  table->string_pool.Sort(
-      [](const StringPool::Entry& a, const StringPool::Entry& b) -> bool {
-        int diff = a.context.priority - b.context.priority;
-        if (diff < 0) return true;
-        if (diff > 0) return false;
-        diff = a.context.config.compare(b.context.config);
-        if (diff < 0) return true;
-        if (diff > 0) return false;
-        return a.value < b.value;
-      });
+  // We must do this before writing the resources, since the string pool IDs may change.
   table->string_pool.Prune();
+  table->string_pool.Sort([](const StringPool::Context& a, const StringPool::Context& b) -> int {
+    int diff = util::compare(a.priority, b.priority);
+    if (diff == 0) {
+      diff = a.config.compare(b.config);
+    }
+    return diff;
+  });
 
   // Write the ResTable header.
   ChunkWriter table_writer(buffer_);
diff --git a/tools/aapt2/flatten/XmlFlattener.cpp b/tools/aapt2/flatten/XmlFlattener.cpp
index bfebedef2a1e..331ef784a7da 100644
--- a/tools/aapt2/flatten/XmlFlattener.cpp
+++ b/tools/aapt2/flatten/XmlFlattener.cpp
@@ -180,8 +180,7 @@ class XmlFlattenerVisitor : public xml::Visitor {
     flatNode->lineNumber = util::HostToDevice32(node->line_number);
     flatNode->comment.index = util::HostToDevice32(-1);
 
-    ResXMLTree_namespaceExt* flat_ns =
-        writer.NextBlock<ResXMLTree_namespaceExt>();
+    ResXMLTree_namespaceExt* flat_ns = writer.NextBlock<ResXMLTree_namespaceExt>();
     AddString(node->namespace_prefix, kLowPriority, &flat_ns->prefix);
     AddString(node->namespace_uri, kLowPriority, &flat_ns->uri);
 
@@ -289,8 +288,7 @@ class XmlFlattenerVisitor : public xml::Visitor {
   BigBuffer* buffer_;
   XmlFlattenerOptions options_;
 
-  // Scratch vector to filter attributes. We avoid allocations
-  // making this a member.
+  // Scratch vector to filter attributes. We avoid allocations making this a member.
   std::vector<xml::Attribute*> filtered_attrs_;
 };
 
@@ -307,10 +305,9 @@ bool XmlFlattener::Flatten(IAaptContext* context, xml::Node* node) {
   }
 
   // Sort the string pool so that attribute resource IDs show up first.
-  visitor.pool.Sort(
-      [](const StringPool::Entry& a, const StringPool::Entry& b) -> bool {
-        return a.context.priority < b.context.priority;
-      });
+  visitor.pool.Sort([](const StringPool::Context& a, const StringPool::Context& b) -> int {
+    return util::compare(a.priority, b.priority);
+  });
 
   // Now we flatten the string pool references into the correct places.
   for (const auto& ref_entry : visitor.string_refs) {
@@ -328,15 +325,13 @@ bool XmlFlattener::Flatten(IAaptContext* context, xml::Node* node) {
     // Write the array of resource IDs, indexed by StringPool order.
     ChunkWriter res_id_map_writer(buffer_);
     res_id_map_writer.StartChunk<ResChunk_header>(RES_XML_RESOURCE_MAP_TYPE);
-    for (const auto& str : visitor.pool) {
-      ResourceId id = {str->context.priority};
-      if (id.id == kLowPriority || !id.is_valid()) {
-        // When we see the first non-resource ID,
-        // we're done.
+    for (const auto& str : visitor.pool.strings()) {
+      ResourceId id(str->context.priority);
+      if (str->context.priority == kLowPriority || !id.is_valid()) {
+        // When we see the first non-resource ID, we're done.
         break;
       }
-
-      *res_id_map_writer.NextBlock<uint32_t>() = id.id;
+      *res_id_map_writer.NextBlock<uint32_t>() = util::HostToDevice32(id.id);
     }
     res_id_map_writer.Finish();
   }
diff --git a/tools/aapt2/proto/ProtoHelpers.cpp b/tools/aapt2/proto/ProtoHelpers.cpp
index 38bf4e3bd8eb..6b21364b5eb2 100644
--- a/tools/aapt2/proto/ProtoHelpers.cpp
+++ b/tools/aapt2/proto/ProtoHelpers.cpp
@@ -18,8 +18,7 @@
 
 namespace aapt {
 
-void SerializeStringPoolToPb(const StringPool& pool,
-                             pb::StringPool* out_pb_pool) {
+void SerializeStringPoolToPb(const StringPool& pool, pb::StringPool* out_pb_pool) {
   BigBuffer buffer(1024);
   StringPool::FlattenUtf8(&buffer, pool);
 
@@ -28,14 +27,12 @@ void SerializeStringPoolToPb(const StringPool& pool,
 
   size_t offset = 0;
   for (const BigBuffer::Block& block : buffer) {
-    data->insert(data->begin() + offset, block.buffer.get(),
-                 block.buffer.get() + block.size);
+    data->insert(data->begin() + offset, block.buffer.get(), block.buffer.get() + block.size);
     offset += block.size;
   }
 }
 
-void SerializeSourceToPb(const Source& source, StringPool* src_pool,
-                         pb::Source* out_pb_source) {
+void SerializeSourceToPb(const Source& source, StringPool* src_pool, pb::Source* out_pb_source) {
   StringPool::Ref ref = src_pool->MakeRef(source.path);
   out_pb_source->set_path_idx(static_cast<uint32_t>(ref.index()));
   if (source.line) {
@@ -43,8 +40,7 @@ void SerializeSourceToPb(const Source& source, StringPool* src_pool,
   }
 }
 
-void DeserializeSourceFromPb(const pb::Source& pb_source,
-                             const android::ResStringPool& src_pool,
+void DeserializeSourceFromPb(const pb::Source& pb_source, const android::ResStringPool& src_pool,
                              Source* out_source) {
   if (pb_source.has_path_idx()) {
     out_source->path = util::GetString(src_pool, pb_source.path_idx());
@@ -80,8 +76,7 @@ SymbolState DeserializeVisibilityFromPb(
   return SymbolState::kUndefined;
 }
 
-void SerializeConfig(const ConfigDescription& config,
-                     pb::ConfigDescription* out_pb_config) {
+void SerializeConfig(const ConfigDescription& config, pb::ConfigDescription* out_pb_config) {
   android::ResTable_config flat_config = config;
   flat_config.size = sizeof(flat_config);
   flat_config.swapHtoD();
@@ -99,8 +94,7 @@ bool DeserializeConfigDescriptionFromPb(const pb::ConfigDescription& pb_config,
     return false;
   }
 
-  config = reinterpret_cast<const android::ResTable_config*>(
-      pb_config.data().data());
+  config = reinterpret_cast<const android::ResTable_config*>(pb_config.data().data());
   out_config->copyFromDtoH(*config);
   return true;
 }
diff --git a/tools/aapt2/proto/TableProtoDeserializer.cpp b/tools/aapt2/proto/TableProtoDeserializer.cpp
index 4b5619235c06..37d5ed0cf59d 100644
--- a/tools/aapt2/proto/TableProtoDeserializer.cpp
+++ b/tools/aapt2/proto/TableProtoDeserializer.cpp
@@ -195,8 +195,7 @@ class PackagePbDeserializer {
           spans++;
         }
         return util::make_unique<StyledString>(pool->MakeRef(
-            style_str,
-            StringPool::Context(StringPool::Context::kStylePriority, config)));
+            style_str, StringPool::Context(StringPool::Context::kNormalPriority, config)));
       }
       return util::make_unique<String>(
           pool->MakeRef(str, StringPool::Context(config)));
diff --git a/tools/aapt2/proto/TableProtoSerializer.cpp b/tools/aapt2/proto/TableProtoSerializer.cpp
index d87d64e1cb46..730442c62836 100644
--- a/tools/aapt2/proto/TableProtoSerializer.cpp
+++ b/tools/aapt2/proto/TableProtoSerializer.cpp
@@ -87,7 +87,9 @@ class PbSerializerVisitor : public RawValueVisitor {
     pb_prim->set_data(val.data);
   }
 
-  void VisitItem(Item* item) override { LOG(FATAL) << "unimplemented item"; }
+  void VisitItem(Item* item) override {
+    LOG(FATAL) << "unimplemented item";
+  }
 
   void Visit(Attribute* attr) override {
     pb::Attribute* pb_attr = pb_compound_value()->mutable_attr();
@@ -207,19 +209,15 @@ class PbSerializerVisitor : public RawValueVisitor {
 }  // namespace
 
 std::unique_ptr<pb::ResourceTable> SerializeTableToPb(ResourceTable* table) {
-  // We must do this before writing the resources, since the string pool IDs may
-  // change.
-  table->string_pool.Sort(
-      [](const StringPool::Entry& a, const StringPool::Entry& b) -> bool {
-        int diff = a.context.priority - b.context.priority;
-        if (diff < 0) return true;
-        if (diff > 0) return false;
-        diff = a.context.config.compare(b.context.config);
-        if (diff < 0) return true;
-        if (diff > 0) return false;
-        return a.value < b.value;
-      });
+  // We must do this before writing the resources, since the string pool IDs may change.
   table->string_pool.Prune();
+  table->string_pool.Sort([](const StringPool::Context& a, const StringPool::Context& b) -> int {
+    int diff = util::compare(a.priority, b.priority);
+    if (diff == 0) {
+      diff = a.config.compare(b.config);
+    }
+    return diff;
+  });
 
   auto pb_table = util::make_unique<pb::ResourceTable>();
   SerializeStringPoolToPb(table->string_pool, pb_table->mutable_string_pool());
diff --git a/tools/aapt2/unflatten/BinaryResourceParser.cpp b/tools/aapt2/unflatten/BinaryResourceParser.cpp
index f3116701056b..728d1f4207c4 100644
--- a/tools/aapt2/unflatten/BinaryResourceParser.cpp
+++ b/tools/aapt2/unflatten/BinaryResourceParser.cpp
@@ -38,20 +38,17 @@ namespace aapt {
 
 using namespace android;
 
-using android::base::StringPrintf;
+using ::android::base::StringPrintf;
 
 namespace {
 
-/*
- * Visitor that converts a reference's resource ID to a resource name,
- * given a mapping from resource ID to resource name.
- */
+// Visitor that converts a reference's resource ID to a resource name, given a mapping from
+// resource ID to resource name.
 class ReferenceIdToNameVisitor : public ValueVisitor {
  public:
   using ValueVisitor::Visit;
 
-  explicit ReferenceIdToNameVisitor(
-      const std::map<ResourceId, ResourceName>* mapping)
+  explicit ReferenceIdToNameVisitor(const std::map<ResourceId, ResourceName>* mapping)
       : mapping_(mapping) {
     CHECK(mapping_ != nullptr);
   }
@@ -99,7 +96,7 @@ bool BinaryResourceParser::Parse() {
   if (parser.chunk()->type != android::RES_TABLE_TYPE) {
     context_->GetDiagnostics()->Error(DiagMessage(source_)
                                       << StringPrintf("unknown chunk of type 0x%02x",
-                                                      (int)parser.chunk()->type));
+                                                      static_cast<int>(parser.chunk()->type)));
     return false;
   }
 
@@ -115,7 +112,7 @@ bool BinaryResourceParser::Parse() {
       context_->GetDiagnostics()->Warn(
           DiagMessage(source_) << StringPrintf(
               "unexpected chunk of type 0x%02x trailing RES_TABLE_TYPE",
-              (int)parser.chunk()->type));
+              static_cast<int>(parser.chunk()->type)));
     }
   }
   return true;
@@ -165,9 +162,8 @@ bool BinaryResourceParser::ParseTable(const ResChunk_header* chunk) {
 
       default:
         context_->GetDiagnostics()->Warn(
-            DiagMessage(source_)
-            << "unexpected chunk type "
-            << (int)util::DeviceToHost16(parser.chunk()->type));
+            DiagMessage(source_) << "unexpected chunk type "
+                                 << static_cast<int>(util::DeviceToHost16(parser.chunk()->type)));
         break;
     }
   }
@@ -245,8 +241,7 @@ bool BinaryResourceParser::ParsePackage(const ResChunk_header* chunk) {
             return false;
           }
         } else {
-          context_->GetDiagnostics()->Warn(DiagMessage(source_)
-                                           << "unexpected string pool");
+          context_->GetDiagnostics()->Warn(DiagMessage(source_) << "unexpected string pool");
         }
         break;
 
@@ -270,9 +265,8 @@ bool BinaryResourceParser::ParsePackage(const ResChunk_header* chunk) {
 
       default:
         context_->GetDiagnostics()->Warn(
-            DiagMessage(source_)
-            << "unexpected chunk type "
-            << (int)util::DeviceToHost16(parser.chunk()->type));
+            DiagMessage(source_) << "unexpected chunk type "
+                                 << static_cast<int>(util::DeviceToHost16(parser.chunk()->type)));
         break;
     }
   }
diff --git a/tools/aapt2/util/Util.h b/tools/aapt2/util/Util.h
index b9ada7704a26..ad3989ea430f 100644
--- a/tools/aapt2/util/Util.h
+++ b/tools/aapt2/util/Util.h
@@ -70,12 +70,6 @@ bool EndsWith(const android::StringPiece& str, const android::StringPiece& suffi
 android::StringPiece TrimWhitespace(const android::StringPiece& str);
 
 /**
- * UTF-16 isspace(). It basically checks for lower range characters that are
- * whitespace.
- */
-inline bool isspace16(char16_t c) { return c < 0x0080 && isspace(c); }
-
-/**
  * Returns an iterator to the first character that is not alpha-numeric and that
  * is not in the allowedChars set.
  */
@@ -104,6 +98,16 @@ bool IsJavaPackageName(const android::StringPiece& str);
 Maybe<std::string> GetFullyQualifiedClassName(const android::StringPiece& package,
                                               const android::StringPiece& class_name);
 
+template <typename T>
+typename std::enable_if<std::is_arithmetic<T>::value, int>::type compare(const T& a, const T& b) {
+  if (a < b) {
+    return -1;
+  } else if (a > b) {
+    return 1;
+  }
+  return 0;
+}
+
 /**
  * Makes a std::unique_ptr<> with the template parameter inferred by the compiler.
  * This will be present in C++14 and can be removed then.