[MsgPack] MsgPackDocument::readFromBlob now merges

[tpr]

Summary

The readFromBlob method can now be used to read MsgPack into a Document
that already contains something, merging the two. There is a new Merger
argument to readFromBlob, a callback function to resolve conflicts.

Change-Id: Icf3e959217fe33cd907a41516c0386aef2847c0c

[tpr]

V2: Pass map key to merger function.

[tpr]

V3: Removed unneeded nullptr arg.

[scott.linder]

Dinesh is working on merging metadata in ROCm CompilerSupport using MsgPackDocument, and it fell out that merging YAML metadata was also handled transparently. What is the advantage to doing this via a function pointer passed to readFromBlob? It doesn't seem to save any copies as you still need to be able to compare the nodes; is it just a matter of readability? Would it be reasonable to also add a callback for fromYAML?

[foad]

llvm/include/llvm/BinaryFormat/MsgPackDocument.h

380–381

Can't the body of this default merger be just llvm_unreachable();?

[tpr]

In D79671#2030708, @scott.linder wrote:

Dinesh is working on merging metadata in ROCm CompilerSupport using MsgPackDocument, and it fell out that merging YAML metadata was also handled transparently. What is the advantage to doing this via a function pointer passed to readFromBlob? It doesn't seem to save any copies as you still need to be able to compare the nodes; is it just a matter of readability? Would it be reasonable to also add a callback for fromYAML?

I too tried doing it by reading the second blob into a MsgPackDocument and merging it into the first one from there. But I think that does involve more copies/allocation/etc because a map in the second document would actually get created as a std::map before having its elements merged into the corresponding map in the first document.

I guess the same thing as I have done could be done for the YAML reading code.

[tpr]

llvm/include/llvm/BinaryFormat/MsgPackDocument.h

380–381

Probably, although that is a change in behavior from before, which I'd rather not do as I think I am not the only user of it. (Also, even if we did do that, it should be "return false" so that the readFromBlob call returns false for failure.)

[foad]

llvm/include/llvm/BinaryFormat/MsgPackDocument.h

380–381

I don't get it. Surely in existing use cases, DestNode is nil so the merger will not be called. And if it *was* called, there's no point in it returning true unless it actually copies some data from SrcNode to DestNode, otherwise it'll claim to have done a merge but actually it ignored the new incoming data and left the document exactly as it was (i.e. empty). What am I missing?

[tpr]

llvm/include/llvm/BinaryFormat/MsgPackDocument.h

380–381

It's a bit of a corner case, but, in the code before, I think you could have a map containing two entries of the same name, both maps, and it would merge them together. Having two entries of the same name is probably not legal MsgPack in some sense.

[scott.linder]

In D79671#2032032, @tpr wrote:

In D79671#2030708, @scott.linder wrote:

Dinesh is working on merging metadata in ROCm CompilerSupport using MsgPackDocument, and it fell out that merging YAML metadata was also handled transparently. What is the advantage to doing this via a function pointer passed to readFromBlob? It doesn't seem to save any copies as you still need to be able to compare the nodes; is it just a matter of readability? Would it be reasonable to also add a callback for fromYAML?

I too tried doing it by reading the second blob into a MsgPackDocument and merging it into the first one from there. But I think that does involve more copies/allocation/etc because a map in the second document would actually get created as a std::map before having its elements merged into the corresponding map in the first document.

I guess the same thing as I have done could be done for the YAML reading code.

I see now, it seems like in the new version we still create the empty std::map and std::array, but as we identify them as conflicting immediately afterwards we never populate them. So we still have the same number of dead objects floating around, but we avoid populating them and then just copying out their contents, which saves us allocations and copies.

The other concern I have is that this may make it difficult to do semantic merges which need more context than the current node being merged. I think this is OK for HSA currently, because we just need to fail when we come across mismatching version nodes.

llvm/include/llvm/BinaryFormat/MsgPackDocument.h

373

Nil is a valid map key in MsgPack, so this is ambiguous; can we use an Empty entry, or just use an Optional<DocNode> where None represents the non-map case?

380–381

Isn't the behavior already changing? In the old code any existing document is discarded and you essentially parse a fresh document to replace it. In the new code the default is effectively inverted, and if you don't do anything special in your Merger you get the existing document with only distinct bits added in from the newly parsed one. If we are completely changing the semantics anyway it seems reasonable to fix odd bits like this.

Alternatively we could just have Merger be Optional and retain the behavior completely if it is not present.

llvm/lib/BinaryFormat/MsgPackDocument.cpp

157

Shouldn't this check for Empty? Why is Nil special concerning merges?

Is this because we represent an empty document as a Nil node? I didn't notice that in the original review, but I think we need to represent an empty document in a way that is distinct from one of the possible documents (in this case we can't distinguish an empty document from a document containing a single Nil node).

[dineshkb-amd]

llvm/include/llvm/BinaryFormat/MsgPackDocument.h

381

Can we consider *DestNode = SrcNode if DestNode and SrcNode are of same type to be closer to old behavior.

llvm/lib/BinaryFormat/MsgPackDocument.cpp

143

One of the logical cases to consider for mergers involving ArrayNodes is that the "Merger" callback provider can append Node elements to DestNode. e.g. lets say the document looking like

Root{"K1" : [ {"P" : p1} ] } is merged with Root{"K1" : ["P" : p2} ] } where {} represents a map and [] represents an array. The expected result is Root{"K1" : [ {"P" : p1}, {"P" : p2} ] }

This is one of the cases when we deal with merging metadata in ROCm CompilerSupport. Can this be achieved with current callback if so shouldn't the Array index be modified to the number of elements added?

[tpr]

V4: Addressed review comments:
    * Separated the idea of an empty node from a nil node
    * Made default merge behavior to fail on any conflict
    * Array merging now appends

[tpr]

llvm/include/llvm/BinaryFormat/MsgPackDocument.h

380–381

OK, I've gone with Jay's suggestion of the default being to fail on any conflict.

llvm/lib/BinaryFormat/MsgPackDocument.cpp

143

Modified to append when merging arrays.

157

Good point. I have now separated the idea of an empty node from a nil one.

[tpr]

With the nil/empty change, there is a change in behavior in that doing a map lookup "map[key]" with a key not previously in the map creates a new map entry that is empty rather than nil. That is more correct, but I have just discovered some code in LLPC relying on the old behavior. I can fix the LLPC code, but is the change in behavior going to cause any HSA problems?

[tpr]

V5: API change so client can choose whether array merging does merge or append.

[scott.linder]

In D79671#2041363, @tpr wrote:

With the nil/empty change, there is a change in behavior in that doing a map lookup "map[key]" with a key not previously in the map creates a new map entry that is empty rather than nil. That is more correct, but I have just discovered some code in LLPC relying on the old behavior. I can fix the LLPC code, but is the change in behavior going to cause any HSA problems?

Sorry, I didn't notice this right away. Thank you for checking, I don't believe we have anywhere that relies on the old behavior, we don't really have any cases where a nil node is valid in HSA metadata.

[scott.linder]

LGTM, thank you for bearing with us taking a while to review. I left a small request but feel free to commit without updating the review.

llvm/include/llvm/BinaryFormat/MsgPackDocument.h

43

Small nit, could this be moved into the enum in MsgPackReader.h with a similar comment?

[tpr]

llvm/include/llvm/BinaryFormat/MsgPackDocument.h

43

Will do, thanks.

llvm/include/llvm/BinaryFormat/MsgPackDocument.h

 
 /// A node in a MsgPack Document. This is a simple copyable and
 /// passable-by-value type that does not own any memory.
 class DocNode {
   friend Document;
 
 public:
   typedef std::map<DocNode, DocNode> MapTy;
   typedef std::vector<DocNode> ArrayTy;
 
 private:
   // Using KindAndDocument allows us to squeeze Kind and a pointer to the
   // owning Document into the same word. Having a pointer to the owning
   // Document makes the API of DocNode more convenient, and allows its use in
   // YAMLIO.
   const KindAndDocument *KindAndDoc;
 
 protected:
   // The union of different values.
   union {
     int64_t Int;
     uint64_t UInt;
     bool Bool;
     double Float;
     StringRef Raw;
     ArrayTy *Array;
     MapTy *Map;
   };
 
 public:
+  // Default constructor gives an empty node with no associated Document. All
+  // you can do with it is "isEmpty()".
   DocNode() : KindAndDoc(nullptr) {}
 
   // Type methods
   bool isMap() const { return getKind() == Type::Map; }
   bool isArray() const { return getKind() == Type::Array; }
   bool isScalar() const { return !isMap() && !isArray(); }
   bool isString() const { return getKind() == Type::String; }
 
-  // Accessors
-  bool isEmpty() const { return !KindAndDoc; }
+  // Accessors. isEmpty() returns true for both a default-constructed DocNode
+  // that has no associated Document, and the result of getEmptyNode(), which
+  // does have an associated document.
+  bool isEmpty() const { return !KindAndDoc || getKind() == Type::Empty; }
   Type getKind() const { return KindAndDoc->Kind; }
   Document *getDocument() const { return KindAndDoc->Doc; }
 
   int64_t &getInt() {
     assert(getKind() == Type::Int);
     return Int;
   }
 
MapDocNode &getMap(bool Convert = false) {
     // This could be a static_cast, except MapDocNode is a forward reference.
     return *reinterpret_cast<MapDocNode *>(this);
   }
 
   /// Comparison operator, used for map keys.
   friend bool operator<(const DocNode &Lhs, const DocNode &Rhs) {
     // This has to cope with one or both of the nodes being default-constructed,
     // such that KindAndDoc is not set.
-    if (Lhs.KindAndDoc != Rhs.KindAndDoc) {
-      if (!Rhs.KindAndDoc)
-        return false;
-      if (!Lhs.KindAndDoc)
+    if (Rhs.isEmpty())
+    if (Lhs.KindAndDoc != Rhs.KindAndDoc) {
+      if (Lhs.isEmpty())
         return true;
       return (unsigned)Lhs.getKind() < (unsigned)Rhs.getKind();
     }
     switch (Lhs.getKind()) {
     case Type::Int:
       return Lhs.Int < Rhs.Int;
     case Type::UInt:
       return Lhs.UInt < Rhs.UInt;

 class ArrayDocNode : public DocNode {
 public:
   ArrayDocNode() {}
   ArrayDocNode(DocNode &N) : DocNode(N) { assert(getKind() == Type::Array); }
 
   // Array access methods.
   size_t size() const { return Array->size(); }
   bool empty() const { return !size(); }
+  DocNode &back() const { return Array->back(); }
   ArrayTy::iterator begin() { return Array->begin(); }
   ArrayTy::iterator end() { return Array->end(); }
   void push_back(DocNode N) {
-    assert(N.getDocument() == getDocument());
+    assert(N.isEmpty() || N.getDocument() == getDocument());
     Array->push_back(N);
   }
 
-  /// Element access. This extends the array if necessary.
+  /// Element access. This extends the array if necessary, with empty nodes.
   DocNode &operator[](size_t Index);
 };
 
 /// Simple in-memory representation of a document of msgpack objects with
 /// ability to find and create array and map elements.  Does not currently cope
 /// with any extension types.
 class Document {
   // Maps, arrays and strings used by nodes in the document. No attempt is made
   // to free unused ones.
   std::vector<std::unique_ptr<DocNode::MapTy>> Maps;
   std::vector<std::unique_ptr<DocNode::ArrayTy>> Arrays;
   std::vector<std::unique_ptr<char[]>> Strings;
 
   // The root node of the document.
   DocNode Root;
 
   // The KindAndDocument structs pointed to by nodes in the document.
-  KindAndDocument KindAndDocs[size_t(Type::Extension) + 1];
+  KindAndDocument KindAndDocs[size_t(Type::Empty) + 1];
 
   // Whether YAML output uses hex for UInt.
   bool HexMode = false;
 
 public:
   Document() {
     clear();
-    for (unsigned T = 0; T != size_t(Type::Extension) + 1; ++T)
+    for (unsigned T = 0; T != unsigned(Type::Empty) + 1; ++T)
       KindAndDocs[T] = {this, Type(T)};
   }
 
   /// Get ref to the document's root element.
   DocNode &getRoot() { return Root; }
 
   /// Restore the Document to an empty state.
-  void clear() { getRoot() = getNode(); }
+  void clear() { getRoot() = getEmptyNode(); }
+
+  /// Create an empty node associated with this Document.
+  DocNode getEmptyNode() {
+    auto N = DocNode(&KindAndDocs[size_t(Type::Empty)]);
+    return N;
+  }
 
   /// Create a nil node associated with this Document.
   DocNode getNode() {
     auto N = DocNode(&KindAndDocs[size_t(Type::Nil)]);
     return N;
   }
 
   /// Create an Int node associated with this Document.
public:
   /// Create an empty Array node associated with this Document.
   ArrayDocNode getArrayNode() {
     auto N = DocNode(&KindAndDocs[size_t(Type::Array)]);
     Arrays.push_back(std::unique_ptr<DocNode::ArrayTy>(new DocNode::ArrayTy));
     N.Array = Arrays.back().get();
     return N.getArray();
   }
 
-  /// Read a MsgPack document from a binary MsgPack blob.
-  /// The blob data must remain valid for the lifetime of this Document (because
-  /// a string object in the document contains a StringRef into the original
-  /// blob).
-  /// If Multi, then this sets root to an array and adds top-level objects to
-  /// it. If !Multi, then it only reads a single top-level object, even if there
-  /// are more, and sets root to that.
-  /// Returns false if failed due to illegal format.
-  bool readFromBlob(StringRef Blob, bool Multi);
+  /// Read a document from a binary msgpack blob, merging into anything already
+  /// in the Document. The blob data must remain valid for the lifetime of this
+  /// Document (because a string object in the document contains a StringRef
+  /// into the original blob). If Multi, then this sets root to an array and
+  /// adds top-level objects to it. If !Multi, then it only reads a single
+  /// top-level object, even if there are more, and sets root to that. Returns
+  /// false if failed due to illegal format or merge error.
+  ///
+  /// The Merger arg is a callback function that is called when the merge has a
+  /// conflict, that is, it is trying to set an item that is already set. If the
+  /// conflict cannot be resolved, the callback function returns -1. If the
+  /// conflict can be resolved, the callback returns a non-negative number and
+  /// sets *DestNode to the resolved node. The returned non-negative number is
+  /// significant only for an array node; it is then the array index to start
+  /// populating at. That allows Merger to choose whether to merge array
+  /// elements (returns 0) or append new elements (returns existing size).
+  ///
+  /// If SrcNode is an array or map, the resolution must be that *DestNode is an
+  /// array or map respectively, although it could be the array or map
+  /// (respectively) that was already there. MapKey is the key if *DestNode is a
+  /// map entry, a nil node otherwise.
+  ///
+  /// The default for Merger is to disallow any conflict.
+  bool readFromBlob(
+      StringRef Blob, bool Multi,
+      function_ref<int(DocNode *DestNode, DocNode SrcNode, DocNode MapKey)>
+          Merger = [](DocNode *DestNode, DocNode SrcNode, DocNode MapKey) {
+            return -1;
+          });
 
   /// Write a MsgPack document to a binary MsgPack blob.
   void writeToBlob(std::string &Blob);
 
   /// Copy a string into the Document's strings list, and return the copy that
   /// is owned by the Document.
   StringRef addString(StringRef S) {
     Strings.push_back(std::unique_ptr<char[]>(new char[S.size()]));

llvm/include/llvm/BinaryFormat/MsgPackReader.h

enum class Type : uint8_t {
   Nil,
   Boolean,
   Float,
   String,
   Binary,
   Array,
   Map,
   Extension,
+  Empty, // Used by MsgPackDocument to represent an empty node
 };
 
 /// Extension types are composed of a user-defined type ID and an uninterpreted
 /// sequence of bytes.
 struct ExtensionType {
   /// User-defined extension type.
   int8_t Type;
   /// Raw bytes of the extension object.

llvm/lib/BinaryFormat/MsgPackDocument.cpp

 /// lifetime of the Document.
 DocNode &MapDocNode::operator[](StringRef S) {
   return (*this)[getDocument()->getNode(S)];
 }
 
 /// Member access for MapDocNode.
 DocNode &MapDocNode::operator[](DocNode Key) {
   assert(!Key.isEmpty());
-  MapTy::value_type Entry(Key, DocNode());
-  auto ItAndInserted = Map->insert(Entry);
-  if (ItAndInserted.second) {
+  DocNode &N = (*Map)[Key];
+  if (N.isEmpty()) {
     // Ensure a new element has its KindAndDoc initialized.
-    ItAndInserted.first->second = getDocument()->getNode();
+    N = getDocument()->getEmptyNode();
   }
-  return ItAndInserted.first->second;
+  return N;
 }
 
 /// Array element access. This extends the array if necessary.
 DocNode &ArrayDocNode::operator[](size_t Index) {
   if (size() <= Index) {
     // Ensure new elements have their KindAndDoc initialized.
-    Array->resize(Index + 1, getDocument()->getNode());
+    Array->resize(Index + 1, getDocument()->getEmptyNode());
   }
   return (*Array)[Index];
 }
 
 // A level in the document reading stack.
 struct StackLevel {
+  StackLevel(DocNode Node, size_t StartIndex, size_t Length,
+             DocNode *MapEntry = nullptr)
+      : Node(Node), Index(StartIndex), End(StartIndex + Length),
+        MapEntry(MapEntry) {}
   DocNode Node;
-  size_t Length;
+  size_t Index;
+  size_t End;
   // Points to map entry when we have just processed a map key.
   DocNode *MapEntry;
+  DocNode MapKey;
 };
 
-// Read a document from a binary msgpack blob.
+// Read a document from a binary msgpack blob, merging into anything already in
+// the Document.
 // The blob data must remain valid for the lifetime of this Document (because a
 // string object in the document contains a StringRef into the original blob).
 // If Multi, then this sets root to an array and adds top-level objects to it.
 // If !Multi, then it only reads a single top-level object, even if there are
 // more, and sets root to that.
-// Returns false if failed due to illegal format.
-bool Document::readFromBlob(StringRef Blob, bool Multi) {
+// Returns false if failed due to illegal format or merge error.
+
+bool Document::readFromBlob(
+    StringRef Blob, bool Multi,
+    function_ref<int(DocNode *DestNode, DocNode SrcNode, DocNode MapKey)>
+        Merger) {
   msgpack::Reader MPReader(Blob);
   SmallVector<StackLevel, 4> Stack;
   if (Multi) {
     // Create the array for multiple top-level objects.
     Root = getArrayNode();
-    Stack.push_back(StackLevel({Root, (size_t)-1, nullptr}));
+    Stack.push_back(StackLevel(Root, 0, (size_t)-1));
   }
   do {
     // On to next element (or key if doing a map key next).
     // Read the value.
     Object Obj;
     if (!MPReader.read(Obj)) {
       if (Multi && Stack.size() == 1) {
         // OK to finish here as we've just done a top-level element with Multi
do {
     case Type::Array:
       Node = getArrayNode();
       break;
     default:
       return false; // Raw and Extension not supported
     }
 
     // Store it.
+    DocNode *DestNode = nullptr;
     if (Stack.empty())
-      Root = Node;
+      DestNode = &Root;
     else if (Stack.back().Node.getKind() == Type::Array) {
       // Reading an array entry.
       auto &Array = Stack.back().Node.getArray();
-      Array.push_back(Node);
+      DestNode = &Array[Stack.back().Index++];
     } else {
       auto &Map = Stack.back().Node.getMap();
       if (!Stack.back().MapEntry) {
         // Reading a map key.
+        Stack.back().MapKey = Node;
         Stack.back().MapEntry = &Map[Node];
-      } else {
-        // Reading the value for the map key read in the last iteration.
-        *Stack.back().MapEntry = Node;
-        Stack.back().MapEntry = nullptr;
-      }
-    }
+        continue;
+      }
+      DestNode = Stack.back().MapEntry;
+      ++Stack.back().Index;
+    int MergeResult = 0;
+    if (!DestNode->isEmpty()) {
+      // In a merge, there is already a value at this position. Call the
+      // callback to attempt to resolve the conflict. The resolution must result
+      // in an array or map if Node is an array or map respectively.
+      DocNode MapKey = !Stack.empty() && !Stack.back().MapKey.isEmpty()
+                           ? Stack.back().MapKey
+                           : getNode();
+      MergeResult = Merger(DestNode, Node, MapKey);
+      if (MergeResult < 0)
+        return false; // Merge conflict resolution failed
+      assert(!((Node.isMap() && !DestNode->isMap()) ||
+               (Node.isArray() && !DestNode->isArray())));
+    } else
+      *DestNode = Node;
 
     // See if we're starting a new array or map.
-    switch (Node.getKind()) {
+    switch (DestNode->getKind()) {
     case msgpack::Type::Array:
     case msgpack::Type::Map:
-      Stack.push_back(StackLevel({Node, Obj.Length, nullptr}));
+      Stack.push_back(StackLevel(*DestNode, MergeResult, Obj.Length, nullptr));
       break;
     default:
       break;
     }
 
     // Pop finished stack levels.
     while (!Stack.empty()) {
-      if (Stack.back().Node.getKind() == msgpack::Type::Array) {
-        if (Stack.back().Node.getArray().size() != Stack.back().Length)
-          break;
-      } else {
-        if (Stack.back().MapEntry ||
-            Stack.back().Node.getMap().size() != Stack.back().Length)
-          break;
-      }
+      if (Stack.back().MapEntry)
+      if (Stack.back().Index != Stack.back().End)
       Stack.pop_back();
     }
   } while (!Stack.empty());
   return true;
 }
 
 struct WriterStackLevel {
   DocNode Node;

llvm/unittests/BinaryFormat/MsgPackDocumentTest.cpp

 TEST(MsgPackDocument, TestReadInt) {
   Document Doc;
   bool Ok = Doc.readFromBlob(StringRef("\xd0\x00", 2), /*Multi=*/false);
   ASSERT_TRUE(Ok);
   ASSERT_EQ(Doc.getRoot().getKind(), Type::Int);
   ASSERT_EQ(Doc.getRoot().getInt(), 0);
 }
 
-TEST(MsgPackDocument, TestReadArray) {
+TEST(MsgPackDocument, TestReadMergeArray) {
   Document Doc;
   bool Ok = Doc.readFromBlob(StringRef("\x92\xd0\x01\xc0"), /*Multi=*/false);
   ASSERT_TRUE(Ok);
   ASSERT_EQ(Doc.getRoot().getKind(), Type::Array);
   auto A = Doc.getRoot().getArray();
   ASSERT_EQ(A.size(), 2u);
   auto SI = A[0];
   ASSERT_EQ(SI.getKind(), Type::Int);
   ASSERT_EQ(SI.getInt(), 1);
   auto SN = A[1];
   ASSERT_EQ(SN.getKind(), Type::Nil);
+
+  Ok = Doc.readFromBlob(StringRef("\x91\xd0\x2a"), /*Multi=*/false,
+                        [](DocNode *DestNode, DocNode SrcNode, DocNode MapKey) {
+                          // Allow array, merging into existing elements, ORing
+                          // ints.
+                          if (DestNode->getKind() == Type::Int &&
+                              SrcNode.getKind() == Type::Int) {
+                            *DestNode = DestNode->getDocument()->getNode(
+                                DestNode->getInt() | SrcNode.getInt());
+                            return 0;
+                          }
+                          return DestNode->isArray() && SrcNode.isArray() ? 0
+                                                                          : -1;
+                        });
+  ASSERT_TRUE(Ok);
+  A = Doc.getRoot().getArray();
+  ASSERT_EQ(A.size(), 2u);
+  SI = A[0];
+  ASSERT_EQ(SI.getKind(), Type::Int);
+  ASSERT_EQ(SI.getInt(), 43);
+  SN = A[1];
+  ASSERT_EQ(SN.getKind(), Type::Nil);
+}
+
+TEST(MsgPackDocument, TestReadAppendArray) {
+  Document Doc;
+  bool Ok = Doc.readFromBlob(StringRef("\x92\xd0\x01\xc0"), /*Multi=*/false);
+  ASSERT_TRUE(Ok);
+  ASSERT_EQ(Doc.getRoot().getKind(), Type::Array);
+  auto A = Doc.getRoot().getArray();
+  ASSERT_EQ(A.size(), 2u);
+  auto SI = A[0];
+  ASSERT_EQ(SI.getKind(), Type::Int);
+  ASSERT_EQ(SI.getInt(), 1);
+  auto SN = A[1];
+  ASSERT_EQ(SN.getKind(), Type::Nil);
+
+  Ok = Doc.readFromBlob(StringRef("\x91\xd0\x2a"), /*Multi=*/false,
+                        [](DocNode *DestNode, DocNode SrcNode, DocNode MapKey) {
+                          // Allow array, appending after existing elements
+                          return DestNode->isArray() && SrcNode.isArray()
+                                     ? DestNode->getArray().size()
+                                     : -1;
+                        });
+  ASSERT_TRUE(Ok);
+  A = Doc.getRoot().getArray();
+  ASSERT_EQ(A.size(), 3u);
+  SI = A[0];
+  ASSERT_EQ(SI.getKind(), Type::Int);
+  ASSERT_EQ(SI.getInt(), 1);
+  SN = A[1];
+  ASSERT_EQ(SN.getKind(), Type::Nil);
+  SI = A[2];
+  ASSERT_EQ(SI.getKind(), Type::Int);
+  ASSERT_EQ(SI.getInt(), 42);
 }
 
-TEST(MsgPackDocument, TestReadMap) {
+TEST(MsgPackDocument, TestReadMergeMap) {
   Document Doc;
   bool Ok = Doc.readFromBlob(StringRef("\x82\xa3"
                                        "foo"
                                        "\xd0\x01\xa3"
                                        "bar"
                                        "\xd0\x02"),
                              /*Multi=*/false);
   ASSERT_TRUE(Ok);
   ASSERT_EQ(Doc.getRoot().getKind(), Type::Map);
   auto M = Doc.getRoot().getMap();
   ASSERT_EQ(M.size(), 2u);
   auto FooS = M["foo"];
   ASSERT_EQ(FooS.getKind(), Type::Int);
   ASSERT_EQ(FooS.getInt(), 1);
   auto BarS = M["bar"];
   ASSERT_EQ(BarS.getKind(), Type::Int);
   ASSERT_EQ(BarS.getInt(), 2);
+
+  Ok = Doc.readFromBlob(StringRef("\x82\xa3"
+                                  "foz"
+                                  "\xd0\x03\xa3"
+                                  "baz"
+                                  "\xd0\x04"),
+                        /*Multi=*/false,
+                        [](DocNode *DestNode, DocNode SrcNode, DocNode MapKey) {
+                          return DestNode->isMap() && SrcNode.isMap() ? 0 : -1;
+                        });
+  ASSERT_TRUE(Ok);
+  ASSERT_EQ(M.size(), 4u);
+  FooS = M["foo"];
+  ASSERT_EQ(FooS.getKind(), Type::Int);
+  ASSERT_EQ(FooS.getInt(), 1);
+  BarS = M["bar"];
+  ASSERT_EQ(BarS.getKind(), Type::Int);
+  ASSERT_EQ(BarS.getInt(), 2);
+  auto FozS = M["foz"];
+  ASSERT_EQ(FozS.getKind(), Type::Int);
+  ASSERT_EQ(FozS.getInt(), 3);
+  auto BazS = M["baz"];
+  ASSERT_EQ(BazS.getKind(), Type::Int);
+  ASSERT_EQ(BazS.getInt(), 4);
+
+  Ok = Doc.readFromBlob(
+      StringRef("\x82\xa3"
+                "foz"
+                "\xd0\x06\xa3"
+                "bay"
+                "\xd0\x08"),
+      /*Multi=*/false, [](DocNode *Dest, DocNode Src, DocNode MapKey) {
+        // Merger function that merges two ints by ORing their values, as long
+        // as the map key is "foz".
+        if (Src.isMap())
+          return Dest->isMap();
+        if (Src.isArray())
+          return Dest->isArray();
+        if (MapKey.isString() && MapKey.getString() == "foz" &&
+            Dest->getKind() == Type::Int && Src.getKind() == Type::Int) {
+          *Dest = Src.getDocument()->getNode(Dest->getInt() | Src.getInt());
+          return true;
+        }
+        return false;
+      });
+  ASSERT_TRUE(Ok);
+  ASSERT_EQ(M.size(), 5u);
+  FooS = M["foo"];
+  ASSERT_EQ(FooS.getKind(), Type::Int);
+  ASSERT_EQ(FooS.getInt(), 1);
+  BarS = M["bar"];
+  ASSERT_EQ(BarS.getKind(), Type::Int);
+  ASSERT_EQ(BarS.getInt(), 2);
+  FozS = M["foz"];
+  ASSERT_EQ(FozS.getKind(), Type::Int);
+  ASSERT_EQ(FozS.getInt(), 7);
+  BazS = M["baz"];
+  ASSERT_EQ(BazS.getKind(), Type::Int);
+  ASSERT_EQ(BazS.getInt(), 4);
+  auto BayS = M["bay"];
+  ASSERT_EQ(BayS.getKind(), Type::Int);
+  ASSERT_EQ(BayS.getInt(), 8);
 }
 
 TEST(MsgPackDocument, TestWriteInt) {
   Document Doc;
   Doc.getRoot() = Doc.getNode(int64_t(1));
   std::string Buffer;
   Doc.writeToBlob(Buffer);
   ASSERT_EQ(Buffer, "\x01");