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 @@ -204,6 +206,12 @@ template struct ElementAndDelimiter { Element *element; Leaf *delimiter; + bool operator==(const ElementAndDelimiter &Other) const { + return element == Other.element && delimiter == Other.delimiter; + } + bool operator!=(const ElementAndDelimiter &Other) const { + return !(*this == Other); + } }; enum class TerminationKind { @@ -214,10 +222,12 @@ 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 would 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,6 +238,57 @@ /// "a; ; c;" <=> [("a" , ";"), (null, ";" ), ("c" , ";" )] /// "a; b c;" <=> [("a" , ";"), ("b" , null), ("c" , ";" )] /// "a; b; c" <=> [("a" , ";"), ("b" , ";" ), ("c" , null)] + 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 of the list, and their corresponding delimiters. + // Missing elements are represented as null pointers. Iterating through + // `getElementsAsNodesAndDelimiters()` is equivalent to iterating through + // `getRange()` std::vector> getElementsAsNodesAndDelimiters(); /// Returns the elements of the list. Missing elements are represented @@ -251,6 +312,13 @@ /// This list may be empty when the source code has errors even if /// canBeEmpty() returns false. bool canBeEmpty() const; + +private: + 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,77 @@ // vector std::vector syntax::NestedNameSpecifier::getSpecifiers() { - auto SpecifiersAsNodes = getElementsAsNodes(); std::vector Children; - for (const auto &Element : SpecifiersAsNodes) { - Children.push_back(llvm::cast(Element)); - } + 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}); - } + 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)); - } + 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}); - } + 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)); - } + 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) { + 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)); - } + 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) { + 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,91 +295,110 @@ } } -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."); - } +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."); } +} - 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}); +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; } - break; } + 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."); } - - return Children; } -// Almost the same implementation of `getElementsAsNodesAndDelimiters` but -// ignoring delimiters -std::vector syntax::List::getElementsAsNodes() { - if (!getFirstChild()) - return {}; +llvm::Optional> +syntax::List::getElementAndDelimiterAfterElement(syntax::Node *Element) { + assert(Element && Element->getRole() == syntax::NodeRole::ListElement); + auto *Next = Element->getNextSibling(); + if (!Next) + // This was the last element of the list. + return None; + + switch (Next->getRole()) { + case syntax::NodeRole::ListElement: + // We have something of the form "a b ..." => 'b' starts the next + // `ElementAndDelimiter`. + return getWithDelimiter(Next); + + case syntax::NodeRole::ListDelimiter: + // We have something of the form "a , ..." => whatever comes after the comma + // starts the next `ElementAndDelimiter`. + return getElementAndDelimiterAfterDelimiter(cast(Next)); - 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."); - } + default: + llvm_unreachable( + "A list can have only elements and delimiters as children."); } +} - 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; - } +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() { + return std::vector>( + getBegin(), getEnd()); +} +std::vector syntax::List::getElementsAsNodes() { + std::vector Children; + std::transform( + getBegin(), getEnd(), std::back_inserter(Children), + [](ElementAndDelimiter ED) { return ED.element; }); return Children; }