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 @@ -28,6 +28,8 @@ #include "clang/Tooling/Syntax/Tokens.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/iterator.h" +#include "llvm/ADT/iterator_range.h" #include "llvm/Support/Allocator.h" #include @@ -201,10 +203,16 @@ /// delimited-list(element, delimiter, termination, canBeEmpty) class List : public Tree { public: - template struct ElementAndDelimiter { - Element *element; - Leaf *delimiter; - }; + using Tree::Tree; + static bool classof(const Node *N); + + // These can't be implemented with the information we have! + + /// Returns the appropriate delimiter for this list. + /// + /// Useful for discovering the correct delimiter to use when adding + /// elements to empty or one-element lists. + clang::tok::TokenKind getDelimiterTokenKind() const; enum class TerminationKind { Terminated, @@ -212,8 +220,71 @@ Separated, }; - using Tree::Tree; - static bool classof(const Node *N); + 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; + +public: + template struct ElementAndDelimiter { + Element *element; + Leaf *delimiter; + bool operator==(const ElementAndDelimiter &Other) const { + return element == Other.element && delimiter == Other.delimiter; + } + }; + + class ElementAndDelimiterIterator + : public llvm::iterator_facade_base> { + public: + ElementAndDelimiterIterator(llvm::Optional> ED) + : EDI(ED) {} + + ElementAndDelimiterIterator &operator++() { + assert(EDI.hasValue() && "Incrementing sentinel iterator."); + if (auto *Delimiter = EDI.getValue().delimiter) + EDI = getElementAndDelimiterAfterDelimiter(Delimiter); + else if (auto *Element = EDI.getValue().element) + EDI = getElementAndDelimiterAfterElement(Element); + else + EDI = None; + return *this; + } + + ElementAndDelimiter &operator*() { + assert(EDI.hasValue() && "Dereferencing sentinel iterator."); + return EDI.getValue(); + } + + const ElementAndDelimiter &operator*() const { + assert(EDI.hasValue() && "Dereferencing sentinel iterator."); + return EDI.getValue(); + } + + bool operator==(const ElementAndDelimiterIterator &Other) const { + return EDI == Other.EDI; + } + + private: + llvm::Optional> EDI; + }; + + ElementAndDelimiterIterator getBegin(); + ElementAndDelimiterIterator getEnd(); + + using ElementsAndDelimitersRange = + llvm::iterator_range; + + ElementsAndDelimitersRange getRange() { + return ElementsAndDelimitersRange(getBegin(), getEnd()); + } + /// Returns the elements and corresponding delimiters. Missing elements /// and delimiters are represented as null pointers. /// @@ -235,22 +306,13 @@ /// `getElementsAsNodesAndDelimiters()`. std::vector getElementsAsNodes(); - // These can't be implemented with the information we have! - - /// Returns the appropriate delimiter for this list. - /// - /// Useful for discovering the correct delimiter to use when adding - /// 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: + // Auxiliary methods for implementing `ElementAndDelimiterIterator`. + static ElementAndDelimiter getWithDelimiter(Node *Element); + static llvm::Optional> + getElementAndDelimiterAfterDelimiter(Leaf *Delimiter); + static llvm::Optional> + getElementAndDelimiterAfterElement(Node *Element); }; } // 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,91 +230,78 @@ // vector std::vector syntax::NestedNameSpecifier::getSpecifiers() { - auto SpecifiersAsNodes = getElementsAsNodes(); - std::vector Children; - for (const auto &Element : SpecifiersAsNodes) { - Children.push_back(llvm::cast(Element)); - } + auto Children = std::vector(); + for (auto C : getRange()) + Children.push_back(cast(C.element)); + return Children; } 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}); - } + auto Children = + std::vector>(); + for (auto C : getRange()) + Children.push_back({cast(C.element), C.delimiter}); + return Children; } std::vector syntax::CallArguments::getArguments() { - auto ArgumentsAsNodes = getElementsAsNodes(); - std::vector Children; - for (const auto &ArgumentAsNode : ArgumentsAsNodes) { - Children.push_back(llvm::cast(ArgumentAsNode)); - } + auto Children = std::vector(); + for (auto C : getRange()) + Children.push_back(cast(C.element)); + return Children; } 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}); - } + auto Children = + std::vector>(); + for (auto C : getRange()) + Children.push_back({cast(C.element), C.delimiter}); + return Children; } std::vector syntax::ParameterDeclarationList::getParameterDeclarations() { - auto ParametersAsNodes = getElementsAsNodes(); - std::vector Children; - for (const auto &ParameterAsNode : ParametersAsNodes) { - Children.push_back(llvm::cast(ParameterAsNode)); - } + auto Children = std::vector(); + for (auto C : getRange()) + Children.push_back(cast(C.element)); + return Children; } std::vector> syntax::ParameterDeclarationList::getParametersAndCommas() { - auto ParametersAsNodesAndCommas = getElementsAsNodesAndDelimiters(); - std::vector> - Children; - for (const auto &ParameterAsNodeAndComma : ParametersAsNodesAndCommas) { + auto Children = std::vector< + syntax::List::ElementAndDelimiter>(); + for (auto C : getRange()) Children.push_back( - {llvm::cast(ParameterAsNodeAndComma.element), - ParameterAsNodeAndComma.delimiter}); - } + {cast(C.element), C.delimiter}); + return Children; } std::vector syntax::DeclaratorList::getDeclarators() { - auto DeclaratorsAsNodes = getElementsAsNodes(); - std::vector Children; - for (const auto &DeclaratorAsNode : DeclaratorsAsNodes) { - Children.push_back(llvm::cast(DeclaratorAsNode)); - } + auto Children = std::vector(); + for (auto C : getRange()) + Children.push_back(cast(C.element)); + return Children; } std::vector> syntax::DeclaratorList::getDeclaratorsAndCommas() { - auto DeclaratorsAsNodesAndCommas = getElementsAsNodesAndDelimiters(); - std::vector> - Children; - for (const auto &DeclaratorAsNodeAndComma : DeclaratorsAsNodesAndCommas) { + auto Children = std::vector< + syntax::List::ElementAndDelimiter>(); + for (auto C : getRange()) Children.push_back( - {llvm::cast(DeclaratorAsNodeAndComma.element), - DeclaratorAsNodeAndComma.delimiter}); - } + {cast(C.element), C.delimiter}); + return Children; } 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 @@ -9,6 +9,7 @@ #include "clang/Basic/TokenKinds.h" #include "clang/Tooling/Syntax/Nodes.h" #include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/Optional.h" #include "llvm/ADT/STLExtras.h" #include "llvm/Support/Casting.h" #include @@ -294,45 +295,102 @@ } } -std::vector> -syntax::List::getElementsAsNodesAndDelimiters() { - if (!getFirstChild()) - return {}; +syntax::List::ElementAndDelimiter +syntax::List::getWithDelimiter(syntax::Node *Element) { + assert(Element && Element->getRole() == syntax::NodeRole::ListElement); + auto *Next = Element->getNextSibling(); + if (!Next) + return {Element, nullptr}; + switch (Next->getRole()) { + case syntax::NodeRole::ListElement: + return {Element, nullptr}; + case syntax::NodeRole::ListDelimiter: + return {Element, cast(Next)}; + default: + llvm_unreachable( + "A list can have only elements and delimiters as children."); + } +} - 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."); +llvm::Optional> +syntax::List::getElementAndDelimiterAfterDelimiter(syntax::Leaf *Delimiter) { + assert(Delimiter && Delimiter->getRole() == syntax::NodeRole::ListDelimiter); + auto *List = cast(Delimiter->getParent()); + auto *Next = Delimiter->getNextSibling(); + if (!Next) { + switch (List->getTerminationKind()) { + // List is separated and ends with delimiter + // => missing last ElementAndDelimiter. + case syntax::List::TerminationKind::Separated: + return llvm::Optional>( + {nullptr, nullptr}); + case syntax::List::TerminationKind::Terminated: + case syntax::List::TerminationKind::MaybeTerminated: + return None; } } + switch (Next->getRole()) { + case syntax::NodeRole::ListElement: + return getWithDelimiter(Next); + + // Consecutive Delimiters => missing Element + case syntax::NodeRole::ListDelimiter: + return llvm::Optional>( + {nullptr, cast(Next)}); + default: + llvm_unreachable( + "A list can have only elements and delimiters as children."); + } +} + +llvm::Optional> +syntax::List::getElementAndDelimiterAfterElement(syntax::Node *Element) { + assert(Element && Element->getRole() == syntax::NodeRole::ListElement); + auto *Next = Element->getNextSibling(); + // a b, x => End of list, this was the last ElementAndDelimiter. + if (!Next) + return None; + + switch (Next->getRole()) { + // x b, c => next ElementAndDelimiter starts with 'b'. + case syntax::NodeRole::ListElement: + return getWithDelimiter(Next); + + // a x, c => next ElementAndDelimiter starts after ','. + case syntax::NodeRole::ListDelimiter: + return getElementAndDelimiterAfterDelimiter(cast(Next)); - switch (getTerminationKind()) { - case syntax::List::TerminationKind::Separated: { - Children.push_back({ElementWithoutDelimiter, nullptr}); - break; + default: + llvm_unreachable( + "A list can have only elements and delimiters as children."); } - case syntax::List::TerminationKind::Terminated: - case syntax::List::TerminationKind::MaybeTerminated: { - if (ElementWithoutDelimiter) { - Children.push_back({ElementWithoutDelimiter, nullptr}); - } - break; +} + +syntax::List::ElementAndDelimiterIterator syntax::List::getEnd() { + return llvm::Optional>(None); +} + +syntax::List::ElementAndDelimiterIterator syntax::List::getBegin() { + auto *First = getFirstChild(); + if (!First) + return getEnd(); + switch (First->getRole()) { + case syntax::NodeRole::ListElement: + return llvm::Optional>(getWithDelimiter(First)); + case syntax::NodeRole::ListDelimiter: + return llvm::Optional>( + {nullptr, cast(First)}); + default: + llvm_unreachable( + "A list can have only elements and delimiters as children."); } +} + +std::vector> +syntax::List::getElementsAsNodesAndDelimiters() { + auto Children = std::vector>(); + for (auto C : getRange()) { + Children.push_back(C); } return Children; @@ -341,42 +399,9 @@ // Almost the same implementation of `getElementsAsNodesAndDelimiters` but // ignoring delimiters std::vector syntax::List::getElementsAsNodes() { - 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); - } - ElementWithoutDelimiter = C; - break; - } - case syntax::NodeRole::ListDelimiter: { - Children.push_back(ElementWithoutDelimiter); - ElementWithoutDelimiter = nullptr; - break; - } - default: - llvm_unreachable("A list has only 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; - } + auto Children = std::vector(); + for (auto C : getRange()) { + Children.push_back(C.element); } return Children;