Improvements to cppbor

1. Add pretty-printing (moved from IdentityCredentialSupport)
2. Add EncodedItem to make it easy to add already-encoded CBOR.
3. Add Map canonicalization.
4. Add support for adding enums as integers.

Test: cppbor_test_external
Change-Id: I641c87567a11de4641b2fcadebe72dd832fceb51
diff --git a/Android.bp b/Android.bp
index beb588e..e57f1d7 100644
--- a/Android.bp
+++ b/Android.bp
@@ -25,6 +25,7 @@
     ],
     shared_libs: [
         "libbase",
+        "libcrypto",
     ]
 }
 
@@ -34,7 +35,7 @@
         "tests/cppbor_test.cpp"
     ],
     shared_libs: [
-        "libcppbor",
+        "libcppbor_external",
         "libbase",
     ],
     static_libs: [
@@ -49,7 +50,7 @@
         "tests/cppbor_test.cpp"
     ],
     shared_libs: [
-        "libcppbor",
+        "libcppbor_external",
         "libbase",
     ],
     static_libs: [
diff --git a/include/cppbor/cppbor.h b/include/cppbor/cppbor.h
index 8fb7cc6..5ee055e 100644
--- a/include/cppbor/cppbor.h
+++ b/include/cppbor/cppbor.h
@@ -64,6 +64,7 @@
 class Map;
 class Null;
 class Semantic;
+class EncodedItem;
 
 /**
  * Returns the size of a CBOR header that contains the additional info value addlInfo.
@@ -196,6 +197,37 @@
 };
 
 /**
+ * EncodedItem represents a bit of already-encoded CBOR. Caveat emptor: It does no checking to
+ * ensure that the provided data is a valid encoding, cannot be meaninfully-compared with other
+ * kinds of items and you cannot use the as*() methods to find out what's inside it.
+ */
+class EncodedItem : public Item {
+  public:
+    explicit EncodedItem(std::vector<uint8_t> value) : mValue(std::move(value)) {}
+
+    bool operator==(const EncodedItem& other) const& { return mValue == other.mValue; }
+
+    // Type can't be meaningfully-obtained. We could extract the type from the first byte and return
+    // it, but you can't do any of the normal things with an EncodedItem so there's no point.
+    MajorType type() const override {
+        assert(false);
+        return static_cast<MajorType>(-1);
+    }
+    size_t encodedSize() const override { return mValue.size(); }
+    uint8_t* encode(uint8_t* pos, const uint8_t* end) const override {
+        if (end - pos < static_cast<ssize_t>(mValue.size())) return nullptr;
+        return std::copy(mValue.begin(), mValue.end(), pos);
+    }
+    void encode(EncodeCallback encodeCallback) const override {
+        std::for_each(mValue.begin(), mValue.end(), encodeCallback);
+    }
+    std::unique_ptr<Item> clone() const override { return std::make_unique<EncodedItem>(mValue); }
+
+  private:
+    std::vector<uint8_t> mValue;
+};
+
+/**
  * Int is an abstraction that allows Uint and Nint objects to be manipulated without caring about
  * the sign.
  */
@@ -235,7 +267,7 @@
         encodeHeader(mValue, encodeCallback);
     }
 
-    virtual std::unique_ptr<Item> clone() const override { return std::make_unique<Uint>(mValue); }
+    std::unique_ptr<Item> clone() const override { return std::make_unique<Uint>(mValue); }
 
   private:
     uint64_t mValue;
@@ -271,7 +303,7 @@
         encodeHeader(addlInfo(), encodeCallback);
     }
 
-    virtual std::unique_ptr<Item> clone() const override { return std::make_unique<Nint>(mValue); }
+    std::unique_ptr<Item> clone() const override { return std::make_unique<Nint>(mValue); }
 
   private:
     uint64_t addlInfo() const { return -1ll - mValue; }
@@ -286,6 +318,9 @@
   public:
     static constexpr MajorType kMajorType = BSTR;
 
+    // Construct an empty Bstr
+    explicit Bstr() {}
+
     // Construct from a vector
     explicit Bstr(std::vector<uint8_t> v) : mValue(std::move(v)) {}
 
@@ -323,8 +358,9 @@
     }
 
     const std::vector<uint8_t>& value() const { return mValue; }
+    std::vector<uint8_t>&& moveValue() { return std::move(mValue); }
 
-    virtual std::unique_ptr<Item> clone() const override { return std::make_unique<Bstr>(mValue); }
+    std::unique_ptr<Item> clone() const override { return std::make_unique<Bstr>(mValue); }
 
   private:
     void encodeValue(EncodeCallback encodeCallback) const;
@@ -333,7 +369,7 @@
 };
 
 /**
- * Bstr is a concrete Item that implements major type 3.
+ * Tstr is a concrete Item that implements major type 3.
  */
 class Tstr : public Item {
   public:
@@ -373,8 +409,9 @@
     }
 
     const std::string& value() const { return mValue; }
+    std::string&& moveValue() { return std::move(mValue); }
 
-    virtual std::unique_ptr<Item> clone() const override { return std::make_unique<Tstr>(mValue); }
+    std::unique_ptr<Item> clone() const override { return std::make_unique<Tstr>(mValue); }
 
   private:
     void encodeValue(EncodeCallback encodeCallback) const;
@@ -443,13 +480,16 @@
     template <typename T>
     Array&& add(T&& v) &&;
 
-    const std::unique_ptr<Item>& operator[](size_t index) const { return mEntries[index]; }
-    std::unique_ptr<Item>& operator[](size_t index) { return mEntries[index]; }
+    const std::unique_ptr<Item>& operator[](size_t index) const { return get(index); }
+    std::unique_ptr<Item>& operator[](size_t index) { return get(index); }
+
+    const std::unique_ptr<Item>& get(size_t index) const { return mEntries[index]; }
+    std::unique_ptr<Item>& get(size_t index) { return mEntries[index]; }
 
     MajorType type() const override { return kMajorType; }
     const Array* asArray() const override { return this; }
 
-    virtual std::unique_ptr<Item> clone() const override;
+    std::unique_ptr<Item> clone() const override;
 
     uint64_t addlInfo() const override { return size(); }
 };
@@ -495,7 +535,7 @@
     }
 
     template <typename Key, typename Enable>
-    std::pair<std::unique_ptr<Item>&, bool> get(Key key);
+    const std::unique_ptr<Item>& get(Key key) const;
 
     std::pair<const std::unique_ptr<Item>&, const std::unique_ptr<Item>&> operator[](
             size_t index) const {
@@ -511,7 +551,23 @@
     MajorType type() const override { return kMajorType; }
     const Map* asMap() const override { return this; }
 
-    virtual std::unique_ptr<Item> clone() const override;
+    // Sorts the map in canonical order, as defined in RFC 7049. Use this before encoding if you
+    // want canonicalization; cppbor does not canonicalize by default, though the integer encodings
+    // are always canonical and cppbor does not support indefinite-length encodings, so map order
+    // canonicalization is the only thing that needs to be done.
+    //
+    // Note that this canonicalization algorithm moves the map contents twice, so it isn't
+    // particularly efficient. Avoid using it unnecessarily on large maps. It does nothing for empty
+    // or single-entry maps, though, so it's recommended to always call it when you need a canonical
+    // map, even if the map is known to have less than two entries. That way if a maintainer later
+    // adds another item canonicalization will be preserved.
+    Map& canonicalize() &;
+    Map&& canonicalize() && {
+        canonicalize();
+        return std::move(*this);
+    }
+
+    std::unique_ptr<Item> clone() const override;
 
     uint64_t addlInfo() const override { return size(); }
 
@@ -558,7 +614,7 @@
 
     uint64_t addlInfo() const override { return value(); }
 
-    virtual std::unique_ptr<Item> clone() const override {
+    std::unique_ptr<Item> clone() const override {
         assertInvariant();
         return std::make_unique<Semantic>(mValue, mEntries[0]->clone());
     }
@@ -618,7 +674,7 @@
 
     bool value() const { return mValue; }
 
-    virtual std::unique_ptr<Item> clone() const override { return std::make_unique<Bool>(mValue); }
+    std::unique_ptr<Item> clone() const override { return std::make_unique<Bool>(mValue); }
 
   private:
     bool mValue;
@@ -646,9 +702,37 @@
         encodeHeader(NULL_V, encodeCallback);
     }
 
-    virtual std::unique_ptr<Item> clone() const override { return std::make_unique<Null>(); }
+    std::unique_ptr<Item> clone() const override { return std::make_unique<Null>(); }
 };
 
+/**
+ * Returns pretty-printed CBOR for |item|
+ *
+ * If a byte-string is larger than |maxBStrSize| its contents will not be printed, instead the value
+ * of the form "<bstr size=1099016 sha1=ef549cca331f73dfae2090e6a37c04c23f84b07b>" will be
+ * printed. Pass zero for |maxBStrSize| to disable this.
+ *
+ * The |mapKeysToNotPrint| parameter specifies the name of map values to not print. This is useful
+ * for unit tests.
+ */
+std::string prettyPrint(const Item* item, size_t maxBStrSize = 32,
+                        const std::vector<std::string>& mapKeysNotToPrint = {});
+
+/**
+ * Returns pretty-printed CBOR for |value|.
+ *
+ * Only valid CBOR should be passed to this function.
+ *
+ * If a byte-string is larger than |maxBStrSize| its contents will not be printed, instead the value
+ * of the form "<bstr size=1099016 sha1=ef549cca331f73dfae2090e6a37c04c23f84b07b>" will be
+ * printed. Pass zero for |maxBStrSize| to disable this.
+ *
+ * The |mapKeysToNotPrint| parameter specifies the name of map values to not print. This is useful
+ * for unit tests.
+ */
+std::string prettyPrint(const std::vector<uint8_t>& encodedCbor, size_t maxBStrSize = 32,
+                        const std::vector<std::string>& mapKeysNotToPrint = {});
+
 template <typename T>
 std::unique_ptr<T> downcastItem(std::unique_ptr<Item>&& v) {
     static_assert(std::is_base_of_v<Item, T> && !std::is_abstract_v<T>,
@@ -717,6 +801,7 @@
  *     (e1), unique_ptr (e2), reference (e3) or value (e3).  If provided by reference or value, will
  *     be moved if possible.  If provided by pointer, ownership is taken.
  * (f) null pointer;
+ * (g) enums, using the underlying integer value.
  */
 template <typename T>
 std::unique_ptr<Item> makeItem(T v) {
@@ -753,6 +838,8 @@
         p = new T(std::move(v));
     } else if constexpr (/* case f */ std::is_null_pointer_v<T>) {
         p = new Null();
+    } else if constexpr (/* case g */ std::is_enum_v<T>) {
+        return makeItem(static_cast<std::underlying_type_t<T>>(v));
     } else {
         // It's odd that this can't be static_assert(false), since it shouldn't be evaluated if one
         // of the above ifs matches.  But static_assert(false) always triggers.
@@ -805,17 +892,20 @@
     return std::move(*this);
 }
 
-template <typename Key, typename = std::enable_if_t<std::is_integral_v<Key> ||
-                                                    details::is_text_type_v<Key>::value>>
-std::pair<std::unique_ptr<Item>&, bool> Map::get(Key key) {
+static const std::unique_ptr<Item> kEmptyItemPtr;
+
+template <typename Key,
+          typename = std::enable_if_t<std::is_integral_v<Key> || std::is_enum_v<Key> ||
+                                      details::is_text_type_v<Key>::value>>
+const std::unique_ptr<Item>& Map::get(Key key) const {
     assertInvariant();
     auto keyItem = details::makeItem(key);
     for (size_t i = 0; i < mEntries.size(); i += 2) {
         if (*keyItem == *mEntries[i]) {
-            return {mEntries[i + 1], true};
+            return mEntries[i + 1];
         }
     }
-    return {keyItem, false};
+    return kEmptyItemPtr;
 }
 
 template <typename T>
diff --git a/include/cppbor/cppbor_parse.h b/include/cppbor/cppbor_parse.h
index 1b10ce1..f1b3647 100644
--- a/include/cppbor/cppbor_parse.h
+++ b/include/cppbor/cppbor_parse.h
@@ -31,7 +31,7 @@
  * successfully-parsed item and the error message string is empty.  If parsing fails, the Item
  * pointer is null, the buffer pointer points to the first byte that was unparseable (the first byte
  * of a data item header that is malformed in some way, e.g. an invalid value, or a length that is
- * too large for the remining buffer, etc.) and the string contains an error message describing the
+ * too large for the remaining buffer, etc.) and the string contains an error message describing the
  * problem encountered.
  */
 ParseResult parse(const uint8_t* begin, const uint8_t* end);
@@ -44,7 +44,7 @@
  * successfully-parsed item and the error message string is empty.  If parsing fails, the Item
  * pointer is null, the buffer pointer points to the first byte that was unparseable (the first byte
  * of a data item header that is malformed in some way, e.g. an invalid value, or a length that is
- * too large for the remining buffer, etc.) and the string contains an error message describing the
+ * too large for the remaining buffer, etc.) and the string contains an error message describing the
  * problem encountered.
  */
 inline ParseResult parse(const std::vector<uint8_t>& encoding) {
@@ -59,13 +59,30 @@
  * successfully-parsed item and the error message string is empty.  If parsing fails, the Item
  * pointer is null, the buffer pointer points to the first byte that was unparseable (the first byte
  * of a data item header that is malformed in some way, e.g. an invalid value, or a length that is
- * too large for the remining buffer, etc.) and the string contains an error message describing the
+ * too large for the remaining buffer, etc.) and the string contains an error message describing the
  * problem encountered.
  */
 inline ParseResult parse(const uint8_t* begin, size_t size) {
     return parse(begin, begin + size);
 }
 
+/**
+ * Parse the first CBOR data item (possibly compound) from the value contained in a Bstr.
+ *
+ * Returns a tuple of Item pointer, buffer pointer and error message.  If parsing is successful, the
+ * Item pointer is non-null, the buffer pointer points to the first byte after the
+ * successfully-parsed item and the error message string is empty.  If parsing fails, the Item
+ * pointer is null, the buffer pointer points to the first byte that was unparseable (the first byte
+ * of a data item header that is malformed in some way, e.g. an invalid value, or a length that is
+ * too large for the remaining buffer, etc.) and the string contains an error message describing the
+ * problem encountered.
+ */
+inline ParseResult parse(const Bstr* bstr) {
+    if (!bstr)
+        return ParseResult(nullptr, nullptr, "Null Bstr pointer");
+    return parse(bstr->value());
+}
+
 class ParseClient;
 
 /**
diff --git a/src/cppbor.cpp b/src/cppbor.cpp
index 5a45dd9..7cd0f30 100644
--- a/src/cppbor.cpp
+++ b/src/cppbor.cpp
@@ -16,6 +16,14 @@
 
 #include "cppbor.h"
 
+#include <inttypes.h>
+#include <openssl/sha.h>
+
+#include "cppbor_parse.h"
+
+using std::string;
+using std::vector;
+
 #ifndef __TRUSTY__
 #include <android-base/logging.h>
 #define LOG_TAG "CppBor"
@@ -44,6 +52,187 @@
     }
 }
 
+bool cborAreAllElementsNonCompound(const CompoundItem* compoundItem) {
+    if (compoundItem->type() == ARRAY) {
+        const Array* array = compoundItem->asArray();
+        for (size_t n = 0; n < array->size(); n++) {
+            const Item* entry = (*array)[n].get();
+            switch (entry->type()) {
+                case ARRAY:
+                case MAP:
+                    return false;
+                default:
+                    break;
+            }
+        }
+    } else {
+        const Map* map = compoundItem->asMap();
+        for (size_t n = 0; n < map->size(); n++) {
+            auto [keyEntry, valueEntry] = (*map)[n];
+            switch (keyEntry->type()) {
+                case ARRAY:
+                case MAP:
+                    return false;
+                default:
+                    break;
+            }
+            switch (valueEntry->type()) {
+                case ARRAY:
+                case MAP:
+                    return false;
+                default:
+                    break;
+            }
+        }
+    }
+    return true;
+}
+
+bool prettyPrintInternal(const Item* item, string& out, size_t indent, size_t maxBStrSize,
+                         const vector<string>& mapKeysToNotPrint) {
+    if (!item) {
+        out.append("<NULL>");
+        return false;
+    }
+
+    char buf[80];
+
+    string indentString(indent, ' ');
+
+    switch (item->type()) {
+        case UINT:
+            snprintf(buf, sizeof(buf), "%" PRIu64, item->asUint()->unsignedValue());
+            out.append(buf);
+            break;
+
+        case NINT:
+            snprintf(buf, sizeof(buf), "%" PRId64, item->asNint()->value());
+            out.append(buf);
+            break;
+
+        case BSTR: {
+            const Bstr* bstr = item->asBstr();
+            const vector<uint8_t>& value = bstr->value();
+            if (value.size() > maxBStrSize) {
+                unsigned char digest[SHA_DIGEST_LENGTH];
+                SHA_CTX ctx;
+                SHA1_Init(&ctx);
+                SHA1_Update(&ctx, value.data(), value.size());
+                SHA1_Final(digest, &ctx);
+                char buf2[SHA_DIGEST_LENGTH * 2 + 1];
+                for (size_t n = 0; n < SHA_DIGEST_LENGTH; n++) {
+                    snprintf(buf2 + n * 2, 3, "%02x", digest[n]);
+                }
+                snprintf(buf, sizeof(buf), "<bstr size=%zd sha1=%s>", value.size(), buf2);
+                out.append(buf);
+            } else {
+                out.append("{");
+                for (size_t n = 0; n < value.size(); n++) {
+                    if (n > 0) {
+                        out.append(", ");
+                    }
+                    snprintf(buf, sizeof(buf), "0x%02x", value[n]);
+                    out.append(buf);
+                }
+                out.append("}");
+            }
+        } break;
+
+        case TSTR:
+            out.append("'");
+            {
+                // TODO: escape "'" characters
+                out.append(item->asTstr()->value().c_str());
+            }
+            out.append("'");
+            break;
+
+        case ARRAY: {
+            const Array* array = item->asArray();
+            if (array->size() == 0) {
+                out.append("[]");
+            } else if (cborAreAllElementsNonCompound(array)) {
+                out.append("[");
+                for (size_t n = 0; n < array->size(); n++) {
+                    if (!prettyPrintInternal((*array)[n].get(), out, indent + 2, maxBStrSize,
+                                             mapKeysToNotPrint)) {
+                        return false;
+                    }
+                    out.append(", ");
+                }
+                out.append("]");
+            } else {
+                out.append("[\n" + indentString);
+                for (size_t n = 0; n < array->size(); n++) {
+                    out.append("  ");
+                    if (!prettyPrintInternal((*array)[n].get(), out, indent + 2, maxBStrSize,
+                                             mapKeysToNotPrint)) {
+                        return false;
+                    }
+                    out.append(",\n" + indentString);
+                }
+                out.append("]");
+            }
+        } break;
+
+        case MAP: {
+            const Map* map = item->asMap();
+
+            if (map->size() == 0) {
+                out.append("{}");
+            } else {
+                out.append("{\n" + indentString);
+                for (size_t n = 0; n < map->size(); n++) {
+                    out.append("  ");
+
+                    auto [map_key, map_value] = (*map)[n];
+
+                    if (!prettyPrintInternal(map_key.get(), out, indent + 2, maxBStrSize,
+                                             mapKeysToNotPrint)) {
+                        return false;
+                    }
+                    out.append(" : ");
+                    if (map_key->type() == TSTR &&
+                        std::find(mapKeysToNotPrint.begin(), mapKeysToNotPrint.end(),
+                                  map_key->asTstr()->value()) != mapKeysToNotPrint.end()) {
+                        out.append("<not printed>");
+                    } else {
+                        if (!prettyPrintInternal(map_value.get(), out, indent + 2, maxBStrSize,
+                                                 mapKeysToNotPrint)) {
+                            return false;
+                        }
+                    }
+                    out.append(",\n" + indentString);
+                }
+                out.append("}");
+            }
+        } break;
+
+        case SEMANTIC: {
+            const Semantic* semantic = item->asSemantic();
+            snprintf(buf, sizeof(buf), "tag %" PRIu64 " ", semantic->value());
+            out.append(buf);
+            prettyPrintInternal(semantic->child().get(), out, indent, maxBStrSize,
+                                mapKeysToNotPrint);
+        } break;
+
+        case SIMPLE:
+            const Bool* asBool = item->asSimple()->asBool();
+            const Null* asNull = item->asSimple()->asNull();
+            if (asBool != nullptr) {
+                out.append(asBool->value() ? "true" : "false");
+            } else if (asNull != nullptr) {
+                out.append("null");
+            } else {
+                LOG(ERROR) << "Only boolean/null is implemented for SIMPLE";
+                return false;
+            }
+            break;
+    }
+
+    return true;
+}
+
 }  // namespace
 
 size_t headerSize(uint64_t addlInfo) {
@@ -204,6 +393,53 @@
     CHECK(mEntries.size() % 2 == 0);
 }
 
+bool mapKeyLess(const std::pair<std::unique_ptr<Item>&, std::unique_ptr<Item>&>& a,
+                const std::pair<std::unique_ptr<Item>&, std::unique_ptr<Item>&>& b) {
+    auto keyA = a.first->encode();
+    auto keyB = b.first->encode();
+
+    // CBOR map canonicalization rules are:
+
+    // 1. If two keys have different lengths, the shorter one sorts earlier.
+    if (keyA.size() < keyB.size()) return true;
+    if (keyA.size() > keyB.size()) return false;
+
+    // 2. If two keys have the same length, the one with the lower value in
+    // (byte-wise) lexical order sorts earlier.
+    return std::lexicographical_compare(keyA.begin(), keyA.end(), keyB.begin(), keyB.end());
+}
+
+Map& Map::canonicalize() & {
+    assertInvariant();
+
+    if (size() < 2) {
+        // Empty or single-entry map; no need to reorder.
+        return *this;
+    }
+
+    // The entries of a Map are stored in a flat vector.  We can't easily apply
+    // std::sort on that, so instead we move all of the entries into a vector of
+    // std::pair, sort that, then move all of the entries back into the original
+    // flat vector.
+    vector<std::pair<std::unique_ptr<Item>, std::unique_ptr<Item>>> temp;
+    temp.reserve(size());
+
+    for (size_t i = 0; i < mEntries.size() - 1; i += 2) {
+        temp.push_back({std::move(mEntries[i]), std::move(mEntries[i + 1])});
+    }
+
+    std::sort(temp.begin(), temp.end(), mapKeyLess);
+
+    mEntries.resize(0);
+    mEntries.reserve(temp.size() * 2);  // Should be a NOP since capacity should be unchanged.
+    for (auto& entry : temp) {
+        mEntries.push_back(std::move(entry.first));
+        mEntries.push_back(std::move(entry.second));
+    }
+
+    return *this;
+}
+
 std::unique_ptr<Item> Map::clone() const {
     assertInvariant();
     auto res = std::make_unique<Map>();
@@ -225,4 +461,20 @@
     CHECK(mEntries.size() == 1);
 }
 
+string prettyPrint(const Item* item, size_t maxBStrSize, const vector<string>& mapKeysToNotPrint) {
+    string out;
+    prettyPrintInternal(item, out, 0, maxBStrSize, mapKeysToNotPrint);
+    return out;
+}
+string prettyPrint(const vector<uint8_t>& encodedCbor, size_t maxBStrSize,
+                   const vector<string>& mapKeysToNotPrint) {
+    auto [item, _, message] = parse(encodedCbor);
+    if (item == nullptr) {
+        LOG(ERROR) << "Data to pretty print is not valid CBOR: " << message;
+        return "";
+    }
+
+    return prettyPrint(item.get(), maxBStrSize, mapKeysToNotPrint);
+}
+
 }  // namespace cppbor
diff --git a/src/cppbor_parse.cpp b/src/cppbor_parse.cpp
index 4715152..357b9ee 100644
--- a/src/cppbor_parse.cpp
+++ b/src/cppbor_parse.cpp
@@ -32,7 +32,7 @@
 std::string insufficientLengthString(size_t bytesNeeded, size_t bytesAvail,
                                      const std::string& type) {
     char buf[1024];
-    snprintf(buf, sizeof(buf), "Need %zu byte(s) for %s, have %zu", bytesNeeded, type.c_str(),
+    snprintf(buf, sizeof(buf), "Need %zu byte(s) for %s, have %zu.", bytesNeeded, type.c_str(),
              bytesAvail);
     return std::string(buf);
 }
diff --git a/tests/cppbor_test.cpp b/tests/cppbor_test.cpp
index baa7c3b..4588b2e 100644
--- a/tests/cppbor_test.cpp
+++ b/tests/cppbor_test.cpp
@@ -871,6 +871,48 @@
     EXPECT_EQ(*clone->asSemantic(), copy);
 }
 
+TEST(MapCanonicalizationTest, CanonicalizationTest) {
+    Map map;
+    map.add("hello", 1)
+            .add("h", 1)
+            .add(1, 1)
+            .add(-4, 1)
+            .add(-5, 1)
+            .add(2, 1)
+            .add("hellp", 1)
+            .add(254, 1)
+            .add(27, 1);
+
+    EXPECT_EQ(prettyPrint(&map),
+              "{\n"
+              "  'hello' : 1,\n"
+              "  'h' : 1,\n"
+              "  1 : 1,\n"
+              "  -4 : 1,\n"
+              "  -5 : 1,\n"
+              "  2 : 1,\n"
+              "  'hellp' : 1,\n"
+              "  254 : 1,\n"
+              "  27 : 1,\n"
+              "}");
+
+    map.canonicalize();
+
+    // Canonically ordered by key encoding.
+    EXPECT_EQ(prettyPrint(&map),
+              "{\n"
+              "  1 : 1,\n"
+              "  2 : 1,\n"
+              "  -4 : 1,\n"
+              "  -5 : 1,\n"
+              "  27 : 1,\n"
+              "  254 : 1,\n"
+              "  'h' : 1,\n"
+              "  'hello' : 1,\n"
+              "  'hellp' : 1,\n"
+              "}");
+}
+
 class MockParseClient : public ParseClient {
   public:
     MOCK_METHOD4(item, ParseClient*(std::unique_ptr<Item>& item, const uint8_t* hdrBegin,
@@ -1432,17 +1474,17 @@
     Array compoundItem(1, 2, 3, 4, 5, Map(4, 5, "a", "b"));
     auto clone = compoundItem.clone();
     Map item(1, 2, "key", "value", "item", std::move(compoundItem));
-    auto [value1, found1] = item.get(1);
-    EXPECT_TRUE(found1);
+    auto& value1 = item.get(1);
+    EXPECT_NE(value1.get(), nullptr);
     EXPECT_EQ(*value1, Uint(2));
-    auto [value2, found2] = item.get("key");
-    EXPECT_TRUE(found2);
+    auto& value2 = item.get("key");
+    EXPECT_NE(value2.get(), nullptr);
     EXPECT_EQ(*value2, Tstr("value"));
-    auto [value3, found3] = item.get("item");
-    EXPECT_TRUE(found3);
+    auto& value3 = item.get("item");
+    EXPECT_NE(value3.get(), nullptr);
     EXPECT_EQ(*value3, *clone);
-    auto [value4, found4] = item.get("wrong");
-    EXPECT_FALSE(found4);
+    auto& value4 = item.get("wrong");
+    EXPECT_EQ(value4.get(), nullptr);
 }
 
 TEST(EmptyBstrTest, Bstr) {