diff --git a/clang/include/clang/Tooling/Syntax/Tree.h b/clang/include/clang/Tooling/Syntax/Tree.h --- a/clang/include/clang/Tooling/Syntax/Tree.h +++ b/clang/include/clang/Tooling/Syntax/Tree.h @@ -201,23 +201,19 @@ /// delimited-list(element, delimiter, termination, canBeEmpty) class List : public Tree { public: + using Tree::Tree; + static bool classof(const Node *N); + template struct ElementAndDelimiter { Element *element; Leaf *delimiter; }; - enum class TerminationKind { - Terminated, - MaybeTerminated, - Separated, - }; - - using Tree::Tree; - static bool classof(const Node *N); - /// Returns the elements and corresponding delimiters. Missing elements - /// and delimiters are represented as null pointers. + /// Iterator through elements and their corresponding delimiters. Missing + /// elements and delimiters are represented as null pointers. Below we give + /// examples of what this iteration looks like. /// - /// For example, in a separated list: + /// In a separated list: /// "a, b, c" <=> [("a" , ","), ("b" , "," ), ("c" , null)] /// "a, , c" <=> [("a" , ","), (null, "," ), ("c" , null)] /// "a, b c" <=> [("a" , ","), ("b" , null), ("c" , null)] @@ -228,14 +224,235 @@ /// "a; ; c;" <=> [("a" , ";"), (null, ";" ), ("c" , ";" )] /// "a; b c;" <=> [("a" , ";"), ("b" , null), ("c" , ";" )] /// "a; b; c" <=> [("a" , ";"), ("b" , ";" ), ("c" , null)] - std::vector> getElementsAsNodesAndDelimiters(); + /// + /// NOTE: This iterator *should* be a standard iterator, however until C++17 + /// we can only have reference proxies for input iterators, and + /// `ElementAndDelimiter` acts as one. + template class ElementAndDelimiterIterator { + public: + ElementAndDelimiterIterator &operator++() { + switch (getKind()) { + case IteratorKind::BeforeBegin: { + if (auto *Begin = getParent()->getFirstChild()) + setElementOrDelimiter(Begin); + else + setSentinel(IteratorKind::End); + return *this; + } + case IteratorKind::Element: { + auto *DelimiterOrElement = getDelimiterOrElement(); + assert(DelimiterOrElement); + auto *Next = DelimiterOrElement->getNextSibling(); + if (Next) { + setElementOrDelimiter(Next); + return *this; + } + if (getParent()->getTerminationKind() == TerminationKind::Separated && + isDelimiter(DelimiterOrElement)) + setSentinel(IteratorKind::MissingLastInSeparated); + else + setSentinel(IteratorKind::End); + return *this; + } + case IteratorKind::MissingLastInSeparated: { + setSentinel(IteratorKind::End); + return *this; + } + case IteratorKind::End: + llvm_unreachable("Incrementing end iterator."); + } + } + + ElementAndDelimiterIterator operator++(int) { + auto tmp = *this; + ++*this; + return tmp; + } + + // An `operator*` would return an `ElementAndDelimiter`, but it would return + // it as a value instead of the expected reference, since this + // `ElementAndDelimiter` isn't stored anywhere. Returning a value for the + // operator* breaks the specification of a common iterator. As such we + // prefer to not provide this operator at all to not create false + // expectations on the user. + // + // Instead we define `getElement()` and `getDelimiter()`. + + /// Returns what you would expect from `It->element`. + ElementType *getElement() const { + auto *ElementOrDelimiter = getElementOrDelimiter(); + if (ElementOrDelimiter && isElement(ElementOrDelimiter)) + return cast(ElementOrDelimiter); + return nullptr; + } + + /// Returns what you would expect from `It->delimiter`. + Leaf *getDelimiter() const { + auto *DelimiterOrElement = getDelimiterOrElement(); + if (DelimiterOrElement && isDelimiter(DelimiterOrElement)) + return cast(DelimiterOrElement); + return nullptr; + } + + bool operator==(const ElementAndDelimiterIterator &Other) const { + return Opaque == Other.Opaque; + } + + bool operator!=(const ElementAndDelimiterIterator &Other) const { + return !(*this == Other); + } + + private: + enum class IteratorKind { + BeforeBegin, + End, + Element, + MissingLastInSeparated // Models ElementAndDelimiter = (nullptr, nullptr). + }; + + // The pointer inside `Opaque` changes semantics according to the + // `IteratorKind`. For `NotSentinel` it stores the `Element` or, if the + // element is missing, the following `Delimiter`. Otherwise it + // stores the `Parent`. Invariant: Opaque != nullptr. + llvm::PointerIntPair Opaque; + + void setSentinel(IteratorKind K) { + assert(K != IteratorKind::Element); + auto *Parent = getParent(); + Opaque.setPointerAndInt(Parent, K); + } + void setElementOrDelimiter(Node *EOrD) { + Opaque.setPointerAndInt(EOrD, IteratorKind::Element); + } + + /// For the current `ElementAndDelimiter` returns the element if it is + /// present, otherwise returns the delimiter. + /// + /// Examples: + /// ElementAndDelimiter | ElementOrDelimiter + /// (Element, Delimiter)| Element + /// (Element, nullptr )| Element + /// (nullptr, Delimiter)| Delimiter + /// (nullptr, nullptr )| nullptr + Node *getElementOrDelimiter() const { + switch (getKind()) { + case IteratorKind::Element: { + return Opaque.getPointer(); + } + case IteratorKind::MissingLastInSeparated: + return nullptr; + case IteratorKind::BeforeBegin: + case IteratorKind::End: + llvm_unreachable("Dereferencing sentinel iterator"); + } + } + /// For the current `ElementAndDelimiter` returns the delimiter if it is + /// present, otherwise returns the element. + Node *getDelimiterOrElement() const { + auto *ElementOrDelimiter = getElementOrDelimiter(); + if (!ElementOrDelimiter) + return nullptr; + auto *Next = ElementOrDelimiter->getNextSibling(); + if (isElement(ElementOrDelimiter) && Next && isDelimiter(Next)) { + return Next; + } + return ElementOrDelimiter; + } + IteratorKind getKind() const { return Opaque.getInt(); } + + public: + List *getParent() { + switch (getKind()) { + case IteratorKind::Element: + return cast(getElementOrDelimiter()->getParent()); + case IteratorKind::BeforeBegin: + case IteratorKind::MissingLastInSeparated: + case IteratorKind::End: + return cast(Opaque.getPointer()); + } + } + const List *getParent() const { + return const_cast(this)->getParent(); + } + + private: + ElementAndDelimiterIterator(Node *N, IteratorKind K) : Opaque(N, K) {} + + public: + static ElementAndDelimiterIterator beforeBegin(List *Parent) { + assert(Parent); + return ElementAndDelimiterIterator( + Parent, IteratorKind::BeforeBegin); + } + + static ElementAndDelimiterIterator begin(List *Parent) { + return ++beforeBegin(Parent); + } + + static ElementAndDelimiterIterator end(List *Parent) { + assert(Parent); + return ElementAndDelimiterIterator(Parent, + IteratorKind::End); + } + }; + +protected: + // These function templates are specialized in syntax nodes inheriting from + // `List`, according to their `ElementType`s. + + template + ElementAndDelimiterIterator getElementAndDelimiterBeforeBegin() { + return ElementAndDelimiterIterator::beforeBegin(this); + } + template + ElementAndDelimiterIterator getElementAndDelimiterBegin() { + return ElementAndDelimiterIterator::begin(this); + } + template + ElementAndDelimiterIterator getElementAndDelimiterEnd() { + return ElementAndDelimiterIterator::end(this); + } + + /// Returns the elements of the list, and their corresponding delimiters. + /// Missing elements are represented as null pointers. + template + std::vector> getElementsAndDelimiters() { + std::vector> Result; + for (auto It = getElementAndDelimiterBegin(), + End = getElementAndDelimiterEnd(); + It != End; ++It) + Result.push_back({It.getElement(), It.getDelimiter()}); + return Result; + } /// Returns the elements of the list. Missing elements are represented /// as null pointers in the same way as in the return value of - /// `getElementsAsNodesAndDelimiters()`. + /// `getElementsAndDelimiters()`. + template std::vector getElements() { + std::vector Result; + for (auto It = getElementAndDelimiterBegin(), + End = getElementAndDelimiterEnd(); + It != End; ++It) + Result.push_back(It.getElement()); + return Result; + } + +public: + ElementAndDelimiterIterator + getElementsAsNodesAndDelimitersBeforeBegin(); + ElementAndDelimiterIterator getElementsAsNodesAndDelimitersBegin(); + ElementAndDelimiterIterator getElementsAsNodesAndDelimitersEnd(); + + std::vector> getElementsAsNodesAndDelimiters(); std::vector getElementsAsNodes(); - // These can't be implemented with the information we have! + enum class TerminationKind { + Terminated, + MaybeTerminated, + Separated, + }; + + TerminationKind getTerminationKind() const; /// Returns the appropriate delimiter for this list. /// @@ -243,14 +460,16 @@ /// elements to empty or one-element lists. clang::tok::TokenKind getDelimiterTokenKind() const; - TerminationKind getTerminationKind() const; - /// Whether this list can be empty in syntactically and semantically correct /// code. /// /// This list may be empty when the source code has errors even if /// canBeEmpty() returns false. bool canBeEmpty() const; + +private: + static bool isElement(Node *N); + static bool isDelimiter(Node *N); }; } // namespace syntax diff --git a/clang/lib/Tooling/Syntax/Nodes.cpp b/clang/lib/Tooling/Syntax/Nodes.cpp --- a/clang/lib/Tooling/Syntax/Nodes.cpp +++ b/clang/lib/Tooling/Syntax/Nodes.cpp @@ -230,92 +230,41 @@ // vector std::vector syntax::NestedNameSpecifier::getSpecifiers() { - auto SpecifiersAsNodes = getElementsAsNodes(); - std::vector Children; - for (const auto &Element : SpecifiersAsNodes) { - Children.push_back(llvm::cast(Element)); - } - return Children; + return getElements(); } std::vector> syntax::NestedNameSpecifier::getSpecifiersAndDoubleColons() { - auto SpecifiersAsNodesAndDoubleColons = getElementsAsNodesAndDelimiters(); - std::vector> - Children; - for (const auto &SpecifierAndDoubleColon : SpecifiersAsNodesAndDoubleColons) { - Children.push_back( - {llvm::cast(SpecifierAndDoubleColon.element), - SpecifierAndDoubleColon.delimiter}); - } - return Children; + return getElementsAndDelimiters(); } std::vector syntax::CallArguments::getArguments() { - auto ArgumentsAsNodes = getElementsAsNodes(); - std::vector Children; - for (const auto &ArgumentAsNode : ArgumentsAsNodes) { - Children.push_back(llvm::cast(ArgumentAsNode)); - } - return Children; + return getElements(); } std::vector> syntax::CallArguments::getArgumentsAndCommas() { - auto ArgumentsAsNodesAndCommas = getElementsAsNodesAndDelimiters(); - std::vector> Children; - for (const auto &ArgumentAsNodeAndComma : ArgumentsAsNodesAndCommas) { - Children.push_back( - {llvm::cast(ArgumentAsNodeAndComma.element), - ArgumentAsNodeAndComma.delimiter}); - } - return Children; + return getElementsAndDelimiters(); } std::vector syntax::ParameterDeclarationList::getParameterDeclarations() { - auto ParametersAsNodes = getElementsAsNodes(); - std::vector Children; - for (const auto &ParameterAsNode : ParametersAsNodes) { - Children.push_back(llvm::cast(ParameterAsNode)); - } - return Children; + return getElements(); } std::vector> syntax::ParameterDeclarationList::getParametersAndCommas() { - auto ParametersAsNodesAndCommas = getElementsAsNodesAndDelimiters(); - std::vector> - Children; - for (const auto &ParameterAsNodeAndComma : ParametersAsNodesAndCommas) { - Children.push_back( - {llvm::cast(ParameterAsNodeAndComma.element), - ParameterAsNodeAndComma.delimiter}); - } - return Children; + return getElementsAndDelimiters(); } std::vector syntax::DeclaratorList::getDeclarators() { - auto DeclaratorsAsNodes = getElementsAsNodes(); - std::vector Children; - for (const auto &DeclaratorAsNode : DeclaratorsAsNodes) { - Children.push_back(llvm::cast(DeclaratorAsNode)); - } - return Children; + return getElements(); } std::vector> syntax::DeclaratorList::getDeclaratorsAndCommas() { - auto DeclaratorsAsNodesAndCommas = getElementsAsNodesAndDelimiters(); - std::vector> - Children; - for (const auto &DeclaratorAsNodeAndComma : DeclaratorsAsNodesAndCommas) { - Children.push_back( - {llvm::cast(DeclaratorAsNodeAndComma.element), - DeclaratorAsNodeAndComma.delimiter}); - } - return Children; + return getElementsAndDelimiters(); } syntax::Expression *syntax::MemberExpression::getObject() { diff --git a/clang/lib/Tooling/Syntax/Tree.cpp b/clang/lib/Tooling/Syntax/Tree.cpp --- a/clang/lib/Tooling/Syntax/Tree.cpp +++ b/clang/lib/Tooling/Syntax/Tree.cpp @@ -311,92 +311,60 @@ } } +syntax::List::ElementAndDelimiterIterator +syntax::List::getElementsAsNodesAndDelimitersBeforeBegin() { + return syntax::List::ElementAndDelimiterIterator::beforeBegin( + this); +} +syntax::List::ElementAndDelimiterIterator +syntax::List::getElementsAsNodesAndDelimitersBegin() { + return syntax::List::ElementAndDelimiterIterator::begin(this); +} +syntax::List::ElementAndDelimiterIterator +syntax::List::getElementsAsNodesAndDelimitersEnd() { + return ElementAndDelimiterIterator::end(this); +} + +// Returns the elements of the list, and their corresponding delimiters. +// Missing elements are represented as null pointers. std::vector> syntax::List::getElementsAsNodesAndDelimiters() { - if (!getFirstChild()) - return {}; - - std::vector> Children; - syntax::Node *ElementWithoutDelimiter = nullptr; - for (auto *C = getFirstChild(); C; C = C->getNextSibling()) { - switch (C->getRole()) { - case syntax::NodeRole::ListElement: { - if (ElementWithoutDelimiter) { - Children.push_back({ElementWithoutDelimiter, nullptr}); - } - ElementWithoutDelimiter = C; - break; - } - case syntax::NodeRole::ListDelimiter: { - Children.push_back({ElementWithoutDelimiter, cast(C)}); - ElementWithoutDelimiter = nullptr; - break; - } - default: - llvm_unreachable( - "A list can have only elements and delimiters as children."); - } - } - - switch (getTerminationKind()) { - case syntax::List::TerminationKind::Separated: { - Children.push_back({ElementWithoutDelimiter, nullptr}); - break; - } - case syntax::List::TerminationKind::Terminated: - case syntax::List::TerminationKind::MaybeTerminated: { - if (ElementWithoutDelimiter) { - Children.push_back({ElementWithoutDelimiter, nullptr}); - } - break; - } - } - - return Children; + return getElementsAndDelimiters(); } -// Almost the same implementation of `getElementsAsNodesAndDelimiters` but -// ignoring delimiters +/// Returns the elements of the list. Missing elements are represented +/// as null pointers in the same way as in the return value of +/// `getElementsAndDelimiters()`. std::vector syntax::List::getElementsAsNodes() { - if (!getFirstChild()) - return {}; + return getElements(); +} - std::vector Children; - syntax::Node *ElementWithoutDelimiter = nullptr; - for (auto *C = getFirstChild(); C; C = C->getNextSibling()) { - switch (C->getRole()) { - case syntax::NodeRole::ListElement: { - if (ElementWithoutDelimiter) { - Children.push_back(ElementWithoutDelimiter); - } - ElementWithoutDelimiter = C; - break; - } - case syntax::NodeRole::ListDelimiter: { - Children.push_back(ElementWithoutDelimiter); - ElementWithoutDelimiter = nullptr; - break; - } - default: - llvm_unreachable("A list has only elements or delimiters."); - } +/// Expects a List child. +bool syntax::List::isElement(syntax::Node *N) { + assert(N); + assert(isa(N->getParent())); + switch (N->getRole()) { + case NodeRole::ListElement: + return true; + case NodeRole::ListDelimiter: + return false; + default: + llvm_unreachable("List children can only be elements or delimiters."); } +} - switch (getTerminationKind()) { - case syntax::List::TerminationKind::Separated: { - Children.push_back(ElementWithoutDelimiter); - break; - } - case syntax::List::TerminationKind::Terminated: - case syntax::List::TerminationKind::MaybeTerminated: { - if (ElementWithoutDelimiter) { - Children.push_back(ElementWithoutDelimiter); - } - break; - } +/// Expects a List child. +bool syntax::List::isDelimiter(syntax::Node *N) { + assert(N); + assert(isa(N->getParent())); + switch (N->getRole()) { + case NodeRole::ListElement: + return false; + case NodeRole::ListDelimiter: + return true; + default: + llvm_unreachable("List children can only be elements or delimiters."); } - - return Children; } clang::tok::TokenKind syntax::List::getDelimiterTokenKind() const { diff --git a/clang/unittests/Tooling/Syntax/TreeTest.cpp b/clang/unittests/Tooling/Syntax/TreeTest.cpp --- a/clang/unittests/Tooling/Syntax/TreeTest.cpp +++ b/clang/unittests/Tooling/Syntax/TreeTest.cpp @@ -11,6 +11,7 @@ #include "clang/Tooling/Syntax/BuildTree.h" #include "clang/Tooling/Syntax/Nodes.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/Support/raw_ostream.h" #include "gtest/gtest.h" using namespace clang; @@ -125,7 +126,7 @@ } class ListTest : public SyntaxTreeTest { -private: +protected: std::string dumpQuotedTokensOrNull(const Node *N) { return N ? "'" + StringRef(N->dumpTokens(Arena->getSourceManager())) @@ -135,7 +136,15 @@ : "null"; } -protected: + std::string + dumpElementAndDelimiter(const List::ElementAndDelimiter ED) { + std::string Storage; + llvm::raw_string_ostream OS(Storage); + OS << "(" << dumpQuotedTokensOrNull(ED.element) << ", " + << dumpQuotedTokensOrNull(ED.delimiter) << ")"; + return OS.str(); + } + std::string dumpElementsAndDelimiters(ArrayRef> EDs) { std::string Storage; @@ -145,8 +154,7 @@ llvm::interleaveComma( EDs, OS, [&OS, this](const List::ElementAndDelimiter &ED) { - OS << "(" << dumpQuotedTokensOrNull(ED.element) << ", " - << dumpQuotedTokensOrNull(ED.delimiter) << ")"; + OS << dumpElementAndDelimiter(ED); }); OS << "]"; @@ -351,4 +359,143 @@ EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']"); } +TEST_P(ListTest, List_Terminated_Iterator_Parent) { + if (!GetParam().isCXX()) { + return; + } + buildTree("", GetParam()); + + // "a b:: :: c" + auto *List = dyn_cast(syntax::createTree( + *Arena, + { + {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, + {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement}, + {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, + {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, + {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement}, + }, + NodeKind::NestedNameSpecifier)); + + EXPECT_EQ(List->getElementsAsNodesAndDelimitersBeforeBegin().getParent(), + List); + + for (auto It = List->getElementsAsNodesAndDelimitersBegin(), + End = List->getElementsAsNodesAndDelimitersEnd(); + It != End; ++It) + EXPECT_EQ(It.getParent(), List); + + EXPECT_EQ(List->getElementsAsNodesAndDelimitersEnd().getParent(), List); +} + +TEST_P(ListTest, List_Terminated_Iterator_Equality) { + if (!GetParam().isCXX()) { + return; + } + buildTree("", GetParam()); + + // "a b:: :: c" + auto *List = dyn_cast(syntax::createTree( + *Arena, + { + {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, + {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement}, + {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, + {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter}, + {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement}, + }, + NodeKind::NestedNameSpecifier)); + + // different iterators are different. + for (auto BeforeIt = List->getElementsAsNodesAndDelimitersBeforeBegin(), + End = List->getElementsAsNodesAndDelimitersEnd(); + BeforeIt != End; ++BeforeIt) { + auto It = BeforeIt; + ++It; + for (; It != End; ++It) { + EXPECT_NE(BeforeIt, It); + } + } + + // Equal iterators are equal. + for (auto It = List->getElementsAsNodesAndDelimitersBegin(), + It2 = List->getElementsAsNodesAndDelimitersBegin(), + End = List->getElementsAsNodesAndDelimitersEnd(); + It != End && It2 != End;) { + EXPECT_EQ(++It, ++It2); + } + + // Different sentinel iterators are different. + EXPECT_NE(List->getElementsAsNodesAndDelimitersBeforeBegin(), + List->getElementsAsNodesAndDelimitersEnd()); +} + +TEST_P(ListTest, List_Separated_Iterator_Parent) { + if (!GetParam().isCXX()) { + return; + } + buildTree("", GetParam()); + + // "a b, ," + auto *List = dyn_cast(syntax::createTree( + *Arena, + { + {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, + {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement}, + {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter}, + {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter}, + }, + NodeKind::CallArguments)); + + EXPECT_EQ(List->getElementsAsNodesAndDelimitersBeforeBegin().getParent(), + List); + + for (auto It = List->getElementsAsNodesAndDelimitersBegin(), + End = List->getElementsAsNodesAndDelimitersEnd(); + It != End; ++It) + EXPECT_EQ(It.getParent(), List); + + EXPECT_EQ(List->getElementsAsNodesAndDelimitersEnd().getParent(), List); +} + +TEST_P(ListTest, List_Separated_Iterator_Equality) { + if (!GetParam().isCXX()) { + return; + } + buildTree("", GetParam()); + + // "a b, ," + auto *List = dyn_cast(syntax::createTree( + *Arena, + { + {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement}, + {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement}, + {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter}, + {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter}, + }, + NodeKind::CallArguments)); + + // different iterators are different. + for (auto BeforeIt = List->getElementsAsNodesAndDelimitersBeforeBegin(), + End = List->getElementsAsNodesAndDelimitersEnd(); + BeforeIt != End; ++BeforeIt) { + auto It = BeforeIt; + ++It; + for (; It != End; ++It) { + EXPECT_NE(BeforeIt, It); + } + } + + // Equal iterators are equal. + for (auto It = List->getElementsAsNodesAndDelimitersBegin(), + It2 = List->getElementsAsNodesAndDelimitersBegin(), + End = List->getElementsAsNodesAndDelimitersEnd(); + It != End && It2 != End;) { + EXPECT_EQ(++It, ++It2); + } + + // Different sentinel iterators are different. + EXPECT_NE(List->getElementsAsNodesAndDelimitersBeforeBegin(), + List->getElementsAsNodesAndDelimitersEnd()); +} } // namespace