[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

370–371

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

370–371

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

370–371

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

370–371

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

363

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?

370–371

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

158

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

371

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

llvm/lib/BinaryFormat/MsgPackDocument.cpp

142

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

370–371

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

llvm/lib/BinaryFormat/MsgPackDocument.cpp

142

Modified to append when merging arrays.

158

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:
   DocNode() : KindAndDoc(nullptr) {}
 
   // Type methods
+  bool isNil() const { return getKind() == Type::Nil; }
   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; }
   Type getKind() const { return KindAndDoc->Kind; }
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 can be resolved, the callback function must set *DestNode to the
+  /// resolved node and return true, otherwise it returns false. 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 allow array and map merging,
+  /// and disallow any other conflict.
+  bool readFromBlob(
+      StringRef Blob, bool Multi,
+      function_ref<bool(DocNode *DestNode, DocNode SrcNode, DocNode MapKey)>
+          Merger = [](DocNode *DestNode, DocNode SrcNode, DocNode MapKey) {
+            return (DestNode->isMap() && SrcNode.isMap()) ||
+                   (DestNode->isArray() && SrcNode.isArray());
+          });
 
   /// 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/lib/BinaryFormat/MsgPackDocument.cpp

if (size() <= Index) {
     // Ensure new elements have their KindAndDoc initialized.
     Array->resize(Index + 1, getDocument()->getNode());
   }
   return (*Array)[Index];
 }
 
 // A level in the document reading stack.
 struct StackLevel {
+  StackLevel(DocNode Node, size_t Length, DocNode *MapEntry = nullptr)
+      : Node(Node), Length(Length), MapEntry(MapEntry), Count(0) {}
   DocNode Node;
   size_t Length;
   // Points to map entry when we have just processed a map key.
   DocNode *MapEntry;
+  DocNode MapKey;
+  size_t Count;
 };
 
-// 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<bool(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, (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().Count++];
     } 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;
+      if (DestNode->isEmpty())
+        *DestNode = getNode();
+      ++Stack.back().Count;
+    }
+    if (!DestNode->isNil()) {
+      // 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();
+      if (!Merger(DestNode, Node, MapKey))
+        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, 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().Count != Stack.back().Length)
       Stack.pop_back();
     }
   } while (!Stack.empty());
   return true;
 }
 
 struct WriterStackLevel {
   DocNode Node;

llvm/unittests/BinaryFormat/MsgPackDocumentTest.cpp

TEST(MsgPackDocument, TestReadArray) {
   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);
 }
 
-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);
+  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");