[yaml] Add support for Anchors and Aliases to yaml::Input

[njames93]

Summary

Adds the necessary machinery to refer to anchors when parsing yaml

yaml
---
Foo: &FB 'FooBar'
Bar: *FB
...

This will be parsed as a dictionary containing {Foo: 'FooBar', Bar: 'FooBar'}

[njames93]

Remove recursive nature of alias expansion as alias nodes cannot be anchored.

[njames93]

Missed something from last update.

[jhenderson]

Thanks for looking at this. Does the Yaml I/O documentation need updating (see llvm/docs/YamlIO.rst)?

Unfortunately, this area of code isn't really one I'm familiar enough with to review in detail, and I don't have time brush up on it sufficiently to be able to, so someone else will need to do the review.

[njames93]

In D128770#3631774, @jhenderson wrote:

Thanks for looking at this. Does the Yaml I/O documentation need updating (see llvm/docs/YamlIO.rst)?

I decided against updating the docs link to the YAML specification and this change is simply about bringing the YamlIO implementation more inline with the actual specification.

llvm/include/llvm/Support/YAMLTraits.h

static bool classof(const HNode *n) {
       return SequenceNode::classof(n->_node);
     }
 
     static bool classof(const SequenceHNode *) { return true; }
 
     std::vector<std::unique_ptr<HNode>> Entries;
   };
 
+  class AliasHNode : public HNode {
+    void anchor() override;
+
+  public:
+    AliasHNode(Node *N, HNode *Aliased) : HNode(N), Aliased(Aliased) {}
+
+    static bool classof(const HNode *n) { return AliasNode::classof(n->_node); }
+
+    static bool classof(const AliasNode *) { return true; }
+
+    HNode *Aliased;
+  };
+
   std::unique_ptr<Input::HNode> createHNodes(Node *node);
   void setError(HNode *hnode, const Twine &message);
+  void setErrorWithExpansion(HNode *Node, const Twine &Message);
   void setError(Node *node, const Twine &message);
   void setError(const SMRange &Range, const Twine &message);
 
   void reportWarning(HNode *hnode, const Twine &message);
   void reportWarning(Node *hnode, const Twine &message);
   void reportWarning(const SMRange &Range, const Twine &message);
 
+  HNode *ignoreAlias(HNode *N);
+  HNode *getCurrentIgnoringAlias() { return ignoreAlias(CurrentNode); }
+
+  void diagnoseAliasExpansion(HNode *StartingNode);
+
 public:
   // These are only used by operator>>. They could be private
   // if those templated things could be made friends.
   bool setCurrentDocument();
   bool nextDocument();
 
   /// Returns the current node that's being parsed by the YAML Parser.
   const Node *getCurrentNode() const;
 
   void setAllowUnknownKeys(bool Allow) override;
 
 private:
   SourceMgr                           SrcMgr; // must be before Strm
   std::unique_ptr<llvm::yaml::Stream> Strm;
   std::unique_ptr<HNode>              TopNode;
+  llvm::StringMap<HNode *> AnchorMap;
   std::error_code                     EC;
   BumpPtrAllocator                    StringAllocator;
   document_iterator                   DocIterator;
   llvm::BitVector                     BitValuesUsed;
   HNode *CurrentNode = nullptr;
   bool                                ScalarMatchFound = false;
   bool AllowUnknownKeys = false;
 };

llvm/lib/Support/YAMLParser.cpp

Node *Document::parseBlockNode() {
   Token T = peekNext();
   // Handle properties.
   Token AnchorInfo;
   Token TagInfo;
 parse_property:
   switch (T.Kind) {
   case Token::TK_Alias:
     getNext();
-    return new (NodeAllocator) AliasNode(stream.CurrentDoc, T.Range.substr(1));
+    {
+      auto *Result =
+          new (NodeAllocator) AliasNode(stream.CurrentDoc, T.Range.substr(1));
+      Result->setSourceRange(SMRange(SMLoc::getFromPointer(T.Range.begin()),
+                                     SMLoc::getFromPointer(T.Range.end())));
+      return Result;
+    }
   case Token::TK_Anchor:
     if (AnchorInfo.Kind == Token::TK_Anchor) {
       setError("Already encountered an anchor for this node!", T);
       return nullptr;
     }
     AnchorInfo = getNext(); // Consume TK_Anchor.
     T = peekNext();
     goto parse_property;

llvm/lib/Support/YAMLTraits.cpp

 std::error_code Input::error() { return EC; }
 
 // Pin the vtables to this file.
 void Input::HNode::anchor() {}
 void Input::EmptyHNode::anchor() {}
 void Input::ScalarHNode::anchor() {}
 void Input::MapHNode::anchor() {}
 void Input::SequenceHNode::anchor() {}
+void Input::AliasHNode::anchor() {}
 
 bool Input::outputting() const {
   return false;
 }
 
 bool Input::setCurrentDocument() {
   if (DocIterator != Strm->end()) {
     Node *N = DocIterator->getRoot();
if (DocIterator != Strm->end()) {
     TopNode = createHNodes(N);
     CurrentNode = TopNode.get();
     return true;
   }
   return false;
 }
 
 bool Input::nextDocument() {
+  // Anchors shouldn't persist between documents.
+  AnchorMap.clear();
   return ++DocIterator != Strm->end();
 }
 
 const Node *Input::getCurrentNode() const {
   return CurrentNode ? CurrentNode->_node : nullptr;
 }
 
 bool Input::mapTag(StringRef Tag, bool Default) {
bool Input::mapTag(StringRef Tag, bool Default) {
   // Return true iff found tag matches supplied tag.
   return Tag.equals(foundTag);
 }
 
 void Input::beginMapping() {
   if (EC)
     return;
   // CurrentNode can be null if the document is empty.
-  MapHNode *MN = dyn_cast_or_null<MapHNode>(CurrentNode);
+  MapHNode *MN = dyn_cast_or_null<MapHNode>(getCurrentIgnoringAlias());
   if (MN) {
     MN->ValidKeys.clear();
   }
 }
 
 std::vector<StringRef> Input::keys() {
-  MapHNode *MN = dyn_cast<MapHNode>(CurrentNode);
+  MapHNode *MN = dyn_cast<MapHNode>(getCurrentIgnoringAlias());
   std::vector<StringRef> Ret;
   if (!MN) {
-    setError(CurrentNode, "not a mapping");
+    setErrorWithExpansion(CurrentNode, "not a mapping");
     return Ret;
   }
   for (auto &P : MN->Mapping)
     Ret.push_back(P.first());
   return Ret;
 }
 
 bool Input::preflightKey(const char *Key, bool Required, bool, bool &UseDefault,
                          void *&SaveInfo) {
   UseDefault = false;
   if (EC)
     return false;
 
   // CurrentNode is null for empty documents, which is an error in case required
   // nodes are present.
   if (!CurrentNode) {
     if (Required)
       EC = make_error_code(errc::invalid_argument);
     return false;
   }
 
-  MapHNode *MN = dyn_cast<MapHNode>(CurrentNode);
+  MapHNode *MN = dyn_cast<MapHNode>(getCurrentIgnoringAlias());
   if (!MN) {
-    if (Required || !isa<EmptyHNode>(CurrentNode))
-      setError(CurrentNode, "not a mapping");
-    else
+    if (Required || !isa<EmptyHNode>(getCurrentIgnoringAlias())) {
+      setErrorWithExpansion(CurrentNode, "not a mapping");
+    } else
       UseDefault = true;
     return false;
   }
   MN->ValidKeys.push_back(Key);
   HNode *Value = MN->Mapping[Key].first.get();
   if (!Value) {
-    if (Required)
-      setError(CurrentNode, Twine("missing required key '") + Key + "'");
-    else
+    if (Required) {
+      setErrorWithExpansion(CurrentNode,
+                            Twine("missing required key '") + Key + "'");
+    } else
       UseDefault = true;
     return false;
   }
   SaveInfo = CurrentNode;
   CurrentNode = Value;
   return true;
 }
 
 void Input::postflightKey(void *saveInfo) {
   CurrentNode = reinterpret_cast<HNode *>(saveInfo);
 }
 
 void Input::endMapping() {
   if (EC)
     return;
   // CurrentNode can be null if the document is empty.
-  MapHNode *MN = dyn_cast_or_null<MapHNode>(CurrentNode);
+  MapHNode *MN = dyn_cast_or_null<MapHNode>(getCurrentIgnoringAlias());
   if (!MN)
     return;
   for (const auto &NN : MN->Mapping) {
     if (!is_contained(MN->ValidKeys, NN.first())) {
       const SMRange &ReportLoc = NN.second.second;
       if (!AllowUnknownKeys) {
         setError(ReportLoc, Twine("unknown key '") + NN.first() + "'");
         break;
       } else
         reportWarning(ReportLoc, Twine("unknown key '") + NN.first() + "'");
     }
   }
 }
 
 void Input::beginFlowMapping() { beginMapping(); }
 
 void Input::endFlowMapping() { endMapping(); }
 
 unsigned Input::beginSequence() {
-  if (SequenceHNode *SQ = dyn_cast<SequenceHNode>(CurrentNode))
+  if (SequenceHNode *SQ = dyn_cast<SequenceHNode>(getCurrentIgnoringAlias()))
     return SQ->Entries.size();
-  if (isa<EmptyHNode>(CurrentNode))
+  if (isa<EmptyHNode>(getCurrentIgnoringAlias()))
     return 0;
   // Treat case where there's a scalar "null" value as an empty sequence.
-  if (ScalarHNode *SN = dyn_cast<ScalarHNode>(CurrentNode)) {
+  if (ScalarHNode *SN = dyn_cast<ScalarHNode>(getCurrentIgnoringAlias())) {
     if (isNull(SN->value()))
       return 0;
   }
   // Any other type of HNode is an error.
-  setError(CurrentNode, "not a sequence");
+  setErrorWithExpansion(CurrentNode, "not a sequence");
   return 0;
 }
 
 void Input::endSequence() {
 }
 
 bool Input::preflightElement(unsigned Index, void *&SaveInfo) {
   if (EC)
     return false;
-  if (SequenceHNode *SQ = dyn_cast<SequenceHNode>(CurrentNode)) {
+  if (SequenceHNode *SQ = dyn_cast<SequenceHNode>(getCurrentIgnoringAlias())) {
     SaveInfo = CurrentNode;
     CurrentNode = SQ->Entries[Index].get();
     return true;
   }
   return false;
 }
 
 void Input::postflightElement(void *SaveInfo) {
   CurrentNode = reinterpret_cast<HNode *>(SaveInfo);
 }
 
 unsigned Input::beginFlowSequence() { return beginSequence(); }
 
 bool Input::preflightFlowElement(unsigned index, void *&SaveInfo) {
   if (EC)
     return false;
-  if (SequenceHNode *SQ = dyn_cast<SequenceHNode>(CurrentNode)) {
+  if (SequenceHNode *SQ = dyn_cast<SequenceHNode>(getCurrentIgnoringAlias())) {
     SaveInfo = CurrentNode;
     CurrentNode = SQ->Entries[index].get();
     return true;
   }
   return false;
 }
 
 void Input::postflightFlowElement(void *SaveInfo) {
   CurrentNode = reinterpret_cast<HNode *>(SaveInfo);
 }
 
 void Input::endFlowSequence() {
 }
 
 void Input::beginEnumScalar() {
   ScalarMatchFound = false;
 }
 
 bool Input::matchEnumScalar(const char *Str, bool) {
   if (ScalarMatchFound)
     return false;
-  if (ScalarHNode *SN = dyn_cast<ScalarHNode>(CurrentNode)) {
+  if (ScalarHNode *SN = dyn_cast<ScalarHNode>(getCurrentIgnoringAlias())) {
     if (SN->value().equals(Str)) {
       ScalarMatchFound = true;
       return true;
     }
   }
   return false;
 }
 
 bool Input::matchEnumFallback() {
   if (ScalarMatchFound)
     return false;
   ScalarMatchFound = true;
   return true;
 }
 
 void Input::endEnumScalar() {
   if (!ScalarMatchFound) {
-    setError(CurrentNode, "unknown enumerated scalar");
+    setErrorWithExpansion(CurrentNode, "unknown enumerated scalar");
   }
 }
 
 bool Input::beginBitSetScalar(bool &DoClear) {
   BitValuesUsed.clear();
-  if (SequenceHNode *SQ = dyn_cast<SequenceHNode>(CurrentNode)) {
+  if (SequenceHNode *SQ = dyn_cast<SequenceHNode>(getCurrentIgnoringAlias())) {
     BitValuesUsed.resize(SQ->Entries.size());
   } else {
-    setError(CurrentNode, "expected sequence of bit values");
+    setErrorWithExpansion(CurrentNode, "expected sequence of bit values");
   }
   DoClear = true;
   return true;
 }
 
 bool Input::bitSetMatch(const char *Str, bool) {
   if (EC)
     return false;
-  if (SequenceHNode *SQ = dyn_cast<SequenceHNode>(CurrentNode)) {
+  if (SequenceHNode *SQ = dyn_cast<SequenceHNode>(getCurrentIgnoringAlias())) {
     unsigned Index = 0;
     for (auto &N : SQ->Entries) {
       if (ScalarHNode *SN = dyn_cast<ScalarHNode>(N.get())) {
         if (SN->value().equals(Str)) {
           BitValuesUsed[Index] = true;
           return true;
         }
       } else {
-        setError(CurrentNode, "unexpected scalar in sequence of bit values");
+        setErrorWithExpansion(CurrentNode,
+                              "unexpected scalar in sequence of bit values");
       }
       ++Index;
     }
   } else {
-    setError(CurrentNode, "expected sequence of bit values");
+    setErrorWithExpansion(CurrentNode, "expected sequence of bit values");
   }
   return false;
 }
 
 void Input::endBitSetScalar() {
   if (EC)
     return;
-  if (SequenceHNode *SQ = dyn_cast<SequenceHNode>(CurrentNode)) {
+  if (SequenceHNode *SQ = dyn_cast<SequenceHNode>(getCurrentIgnoringAlias())) {
     assert(BitValuesUsed.size() == SQ->Entries.size());
     for (unsigned i = 0; i < SQ->Entries.size(); ++i) {
       if (!BitValuesUsed[i]) {
         setError(SQ->Entries[i].get(), "unknown bit value");
         return;
       }
     }
   }
 }
 
 void Input::scalarString(StringRef &S, QuotingType) {
-  if (ScalarHNode *SN = dyn_cast<ScalarHNode>(CurrentNode)) {
+  if (ScalarHNode *SN = dyn_cast<ScalarHNode>(getCurrentIgnoringAlias())) {
     S = SN->value();
   } else {
-    setError(CurrentNode, "unexpected scalar");
+    setErrorWithExpansion(CurrentNode, "unexpected scalar");
   }
 }
 
 void Input::blockScalarString(StringRef &S) { scalarString(S, QuotingType::None); }
 
 void Input::scalarTag(std::string &Tag) {
   Tag = CurrentNode->_node->getVerbatimTag();
 }
 
 void Input::setError(HNode *hnode, const Twine &message) {
   assert(hnode && "HNode must not be NULL");
   setError(hnode->_node, message);
 }
 
+void Input::setErrorWithExpansion(HNode *Node, const Twine &Message) {
+  setError(Node, Message);
+  diagnoseAliasExpansion(Node);
+}
+
 NodeKind Input::getNodeKind() {
-  if (isa<ScalarHNode>(CurrentNode))
+  auto *IgAlias = getCurrentIgnoringAlias();
+  if (isa<ScalarHNode>(IgAlias))
     return NodeKind::Scalar;
-  else if (isa<MapHNode>(CurrentNode))
+  else if (isa<MapHNode>(IgAlias))
     return NodeKind::Map;
-  else if (isa<SequenceHNode>(CurrentNode))
+  else if (isa<SequenceHNode>(IgAlias))
     return NodeKind::Sequence;
   llvm_unreachable("Unsupported node kind");
 }
 
 void Input::setError(Node *node, const Twine &message) {
   Strm->printError(node, message);
   EC = make_error_code(errc::invalid_argument);
 }

 void Input::reportWarning(Node *node, const Twine &message) {
   Strm->printError(node, message, SourceMgr::DK_Warning);
 }
 
 void Input::reportWarning(const SMRange &range, const Twine &message) {
   Strm->printError(range, message, SourceMgr::DK_Warning);
 }
 
+void Input::diagnoseAliasExpansion(HNode *StartingNode) {
+  auto *Alias = ignoreAlias(StartingNode);
+  if (Alias != StartingNode)
+    Strm->printError(Alias->_node, "Expanded from alias", SourceMgr::DK_Note);
+}
+
+Input::HNode *Input::ignoreAlias(HNode *N) {
+  if (auto *Alias = dyn_cast_or_null<AliasHNode>(N))
+    return Alias->Aliased;
+  return N;
+}
+
 std::unique_ptr<Input::HNode> Input::createHNodes(Node *N) {
+  auto WrapAnchor = [this, N](std::unique_ptr<HNode> X) {
+    if (!N->getAnchor().empty())
+      AnchorMap[N->getAnchor()] = X.get();
+    return X;
+  };
   SmallString<128> StringStorage;
   if (ScalarNode *SN = dyn_cast<ScalarNode>(N)) {
     StringRef KeyStr = SN->getValue(StringStorage);
     if (!StringStorage.empty()) {
       // Copy string to permanent storage
       KeyStr = StringStorage.str().copy(StringAllocator);
     }
-    return std::make_unique<ScalarHNode>(N, KeyStr);
+    return WrapAnchor(std::make_unique<ScalarHNode>(N, KeyStr));
   } else if (BlockScalarNode *BSN = dyn_cast<BlockScalarNode>(N)) {
     StringRef ValueCopy = BSN->getValue().copy(StringAllocator);
-    return std::make_unique<ScalarHNode>(N, ValueCopy);
+    return WrapAnchor(std::make_unique<ScalarHNode>(N, ValueCopy));
   } else if (SequenceNode *SQ = dyn_cast<SequenceNode>(N)) {
     auto SQHNode = std::make_unique<SequenceHNode>(N);
     for (Node &SN : *SQ) {
       auto Entry = createHNodes(&SN);
       if (EC)
         break;
       SQHNode->Entries.push_back(std::move(Entry));
     }
-    return std::move(SQHNode);
+    return WrapAnchor(std::move(SQHNode));
   } else if (MappingNode *Map = dyn_cast<MappingNode>(N)) {
     auto mapHNode = std::make_unique<MapHNode>(N);
     for (KeyValueNode &KVN : *Map) {
       Node *KeyNode = KVN.getKey();
       ScalarNode *Key = dyn_cast_or_null<ScalarNode>(KeyNode);
       Node *Value = KVN.getValue();
       if (!Key || !Value) {
         if (!Key)
for (KeyValueNode &KVN : *Map) {
         KeyStr = StringStorage.str().copy(StringAllocator);
       }
       auto ValueHNode = createHNodes(Value);
       if (EC)
         break;
       mapHNode->Mapping[KeyStr] =
           std::make_pair(std::move(ValueHNode), KeyNode->getSourceRange());
     }
-    return std::move(mapHNode);
+    return WrapAnchor(std::move(mapHNode));
   } else if (isa<NullNode>(N)) {
-    return std::make_unique<EmptyHNode>(N);
+    return WrapAnchor(std::make_unique<EmptyHNode>(N));
+  } else if (auto *Alias = dyn_cast<AliasNode>(N)) {
+    auto Iter = AnchorMap.find(Alias->getName());
+    if (Iter == AnchorMap.end()) {
+      setError(Alias, "No anchor found named '" + Alias->getName() + "'");
+      return nullptr;
+    }
+    // Don't wrap anchor here as Alias nodes cannot be anchored.
+    return std::make_unique<AliasHNode>(Alias, Iter->getValue());
   } else {
     setError(N, "unknown node kind");
     return nullptr;
   }
 }
 
 void Input::setError(const Twine &Message) {
   setError(CurrentNode, Message);

llvm/unittests/Support/YAMLIOTest.cpp

 //===----------------------------------------------------------------------===//
 
 struct FooBar {
   int foo;
   int bar;
 };
 typedef std::vector<FooBar> FooBarSequence;
 
+static constexpr bool operator==(const FooBar &L, const FooBar &R) {
+  return L.foo == R.foo && L.bar == R.bar;
+}
+
 LLVM_YAML_IS_SEQUENCE_VECTOR(FooBar)
 
 struct FooBarContainer {
   FooBarSequence fbs;
 };
 
 namespace llvm {
 namespace yaml {
TEST(YAMLIO, TestMalformedContainerSequenceMapRead) {
     Input yin("---\nfbs: 'scalar'\n...\n", nullptr, suppressErrorMessages);
     yin >> cont;
     // This should be an error.
     EXPECT_TRUE(!!yin.error());
     EXPECT_EQ(cont.fbs.size(), 0UL);
   }
 }
 
+TEST(YAMLIO, TestAnchorRead) {
+  FooBarContainer cont;
+  Input yin(R"(---
+fbs:
+ - &Anchor # Anchors can be applied to maps.
+   foo: &Foo 2 # Anchors can be applied to scalars.
+   bar: 3
+ - bar: *Foo
+   foo: *Foo
+ - *Anchor   
+ - &Anchor # Anchors can be redefined
+   foo: &Foo 6
+   bar: *Foo
+ - *Anchor
+ - &Foo # And redefined to a different type
+   foo: &Anchor 10
+   bar: *Anchor
+ - *Foo
+...
+)",
+            nullptr);
+  yin >> cont;
+
+  EXPECT_FALSE(yin.error());
+  ASSERT_EQ(cont.fbs.size(), 7UL);
+  EXPECT_EQ(cont.fbs[0].foo, 2);
+  EXPECT_EQ(cont.fbs[0].bar, 3);
+  EXPECT_EQ(cont.fbs[1].foo, cont.fbs[1].foo);
+  EXPECT_EQ(cont.fbs[1].bar, cont.fbs[1].foo);
+  EXPECT_EQ(cont.fbs[2], cont.fbs[0]);
+  EXPECT_EQ(cont.fbs[3].foo, 6);
+  EXPECT_EQ(cont.fbs[3].bar, cont.fbs[3].foo);
+  EXPECT_EQ(cont.fbs[4], cont.fbs[3]);
+  EXPECT_EQ(cont.fbs[5].foo, 10);
+  EXPECT_EQ(cont.fbs[5].bar, cont.fbs[5].foo);
+  EXPECT_EQ(cont.fbs[6], cont.fbs[5]);
+}
+
 //
 // Test writing then reading back a sequence of mappings
 //
 TEST(YAMLIO, TestSequenceMapWriteAndRead) {
   std::string intermediate;
   {
     FooBar entry1;
     entry1.foo = 10;