Index: llvm/trunk/include/llvm/Option/ArgList.h =================================================================== --- llvm/trunk/include/llvm/Option/ArgList.h +++ llvm/trunk/include/llvm/Option/ArgList.h @@ -10,6 +10,7 @@ #ifndef LLVM_OPTION_ARGLIST_H #define LLVM_OPTION_ARGLIST_H +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/SmallString.h" #include "llvm/ADT/StringRef.h" @@ -28,40 +29,57 @@ class Option; /// arg_iterator - Iterates through arguments stored inside an ArgList. +template class arg_iterator { - /// The current argument. - SmallVectorImpl::const_iterator Current; + /// The current argument and the end of the sequence we're iterating. + BaseIter Current, End; - /// The argument list we are iterating over. - const ArgList &Args; - - /// Optional filters on the arguments which will be match. Most clients - /// should never want to iterate over arguments without filters, so we won't - /// bother to factor this into two separate iterator implementations. - // - // FIXME: Make efficient; the idea is to provide efficient iteration over - // all arguments which match a particular id and then just provide an - // iterator combinator which takes multiple iterators which can be - // efficiently compared and returns them in order. - OptSpecifier Id0, Id1, Id2; + /// Optional filters on the arguments which will be match. To avoid a + /// zero-sized array, we store one specifier even if we're asked for none. + OptSpecifier Ids[NumOptSpecifiers ? NumOptSpecifiers : 1]; + + void SkipToNextArg() { + for (; Current != End; ++Current) { + // Skip erased elements. + if (!*Current) + continue; + + // Done if there are no filters. + if (!NumOptSpecifiers) + return; + + // Otherwise require a match. + const Option &O = (*Current)->getOption(); + for (auto Id : Ids) { + if (!Id.isValid()) + break; + if (O.matches(Id)) + return; + } + } + } - void SkipToNextArg(); + typedef std::iterator_traits Traits; public: - typedef Arg * const * value_type; - typedef Arg * const & reference; - typedef Arg * const * pointer; - typedef std::forward_iterator_tag iterator_category; - typedef std::ptrdiff_t difference_type; - - arg_iterator(SmallVectorImpl::const_iterator it, const ArgList &Args, - OptSpecifier Id0 = 0U, OptSpecifier Id1 = 0U, - OptSpecifier Id2 = 0U) - : Current(it), Args(Args), Id0(Id0), Id1(Id1), Id2(Id2) { + typedef typename Traits::value_type value_type; + typedef typename Traits::reference reference; + typedef typename Traits::pointer pointer; + typedef std::forward_iterator_tag iterator_category; + typedef std::ptrdiff_t difference_type; + + arg_iterator( + BaseIter Current, BaseIter End, + const OptSpecifier (&Ids)[NumOptSpecifiers ? NumOptSpecifiers : 1] = {}) + : Current(Current), End(End) { + for (unsigned I = 0; I != NumOptSpecifiers; ++I) + this->Ids[I] = Ids[I]; SkipToNextArg(); } + // FIXME: This conversion function makes no sense. operator const Arg*() { return *Current; } + reference operator*() const { return *Current; } pointer operator->() const { return Current; } @@ -94,15 +112,31 @@ class ArgList { public: typedef SmallVector arglist_type; - typedef arglist_type::iterator iterator; - typedef arglist_type::const_iterator const_iterator; - typedef arglist_type::reverse_iterator reverse_iterator; - typedef arglist_type::const_reverse_iterator const_reverse_iterator; + typedef arg_iterator iterator; + typedef arg_iterator const_iterator; + typedef arg_iterator reverse_iterator; + typedef arg_iterator + const_reverse_iterator; + + template using filtered_iterator = + arg_iterator; + template using filtered_reverse_iterator = + arg_iterator; private: /// The internal list of arguments. arglist_type Args; + typedef std::pair OptRange; + static OptRange emptyRange() { return {-1u, 0u}; } + + /// The first and last index of each different OptSpecifier ID. + DenseMap OptRanges; + + /// Get the range of indexes in which options with the specified IDs might + /// reside, or (0, 0) if there are no such options. + OptRange getRange(std::initializer_list Ids) const; + protected: // Make the default special members protected so they won't be used to slice // derived objects, but can still be used by derived objects to implement @@ -113,24 +147,28 @@ // InputArgList which deletes the contents of the container. If we could fix // up the ownership here (delegate storage/ownership to the derived class so // it can be a container of unique_ptr) this would be simpler. - ArgList(ArgList &&RHS) : Args(std::move(RHS.Args)) { RHS.Args.clear(); } + ArgList(ArgList &&RHS) + : Args(std::move(RHS.Args)), OptRanges(std::move(RHS.OptRanges)) { + RHS.Args.clear(); + RHS.OptRanges.clear(); + } ArgList &operator=(ArgList &&RHS) { Args = std::move(RHS.Args); RHS.Args.clear(); + OptRanges = std::move(RHS.OptRanges); + RHS.OptRanges.clear(); return *this; } // Protect the dtor to ensure this type is never destroyed polymorphically. ~ArgList() = default; public: - /// @name Arg Access /// @{ /// append - Append \p A to the arg list. void append(Arg *A); - arglist_type &getArgs() { return Args; } const arglist_type &getArgs() const { return Args; } unsigned size() const { return Args.size(); } @@ -139,30 +177,36 @@ /// @name Arg Iteration /// @{ - iterator begin() { return Args.begin(); } - iterator end() { return Args.end(); } - - reverse_iterator rbegin() { return Args.rbegin(); } - reverse_iterator rend() { return Args.rend(); } + iterator begin() { return {Args.begin(), Args.end()}; } + iterator end() { return {Args.end(), Args.end()}; } - const_iterator begin() const { return Args.begin(); } - const_iterator end() const { return Args.end(); } + reverse_iterator rbegin() { return {Args.rbegin(), Args.rend()}; } + reverse_iterator rend() { return {Args.rend(), Args.rend()}; } - const_reverse_iterator rbegin() const { return Args.rbegin(); } - const_reverse_iterator rend() const { return Args.rend(); } + const_iterator begin() const { return {Args.begin(), Args.end()}; } + const_iterator end() const { return {Args.end(), Args.end()}; } - arg_iterator filtered_begin(OptSpecifier Id0 = 0U, OptSpecifier Id1 = 0U, - OptSpecifier Id2 = 0U) const { - return arg_iterator(Args.begin(), *this, Id0, Id1, Id2); - } - arg_iterator filtered_end() const { - return arg_iterator(Args.end(), *this); - } - - iterator_range filtered(OptSpecifier Id0 = 0U, - OptSpecifier Id1 = 0U, - OptSpecifier Id2 = 0U) const { - return make_range(filtered_begin(Id0, Id1, Id2), filtered_end()); + const_reverse_iterator rbegin() const { return {Args.rbegin(), Args.rend()}; } + const_reverse_iterator rend() const { return {Args.rend(), Args.rend()}; } + + template + iterator_range> + filtered(OptSpecifiers ...Ids) const { + OptRange Range = getRange({Ids...}); + auto B = Args.begin() + Range.first; + auto E = Args.begin() + Range.second; + using Iterator = filtered_iterator; + return make_range(Iterator(B, E, {Ids...}), Iterator(E, E, {Ids...})); + } + + template + iterator_range> + filtered_reverse(OptSpecifiers ...Ids) const { + OptRange Range = getRange({Ids...}); + auto B = Args.rend() - Range.second; + auto E = Args.rend() - Range.first; + using Iterator = filtered_reverse_iterator; + return make_range(Iterator(B, E, {Ids...}), Iterator(E, E, {Ids...})); } /// @} @@ -179,43 +223,34 @@ /// hasArg - Does the arg list contain any option matching \p Id. /// /// \p Claim Whether the argument should be claimed, if it exists. - bool hasArgNoClaim(OptSpecifier Id) const { - return getLastArgNoClaim(Id) != nullptr; - } - bool hasArg(OptSpecifier Id) const { - return getLastArg(Id) != nullptr; - } - bool hasArg(OptSpecifier Id0, OptSpecifier Id1) const { - return getLastArg(Id0, Id1) != nullptr; + template + bool hasArgNoClaim(OptSpecifiers ...Ids) const { + return getLastArgNoClaim(Ids...) != nullptr; + } + template + bool hasArg(OptSpecifiers ...Ids) const { + return getLastArg(Ids...) != nullptr; + } + + /// Return the last argument matching \p Id, or null. + template + Arg *getLastArg(OptSpecifiers ...Ids) const { + Arg *Res = nullptr; + for (Arg *A : filtered(Ids...)) { + Res = A; + Res->claim(); + } + return Res; + } + + /// Return the last argument matching \p Id, or null. Do not "claim" the + /// option (don't mark it as having been used). + template + Arg *getLastArgNoClaim(OptSpecifiers ...Ids) const { + for (Arg *A : filtered_reverse(Ids...)) + return A; + return nullptr; } - bool hasArg(OptSpecifier Id0, OptSpecifier Id1, OptSpecifier Id2) const { - return getLastArg(Id0, Id1, Id2) != nullptr; - } - - /// getLastArg - Return the last argument matching \p Id, or null. - /// - /// \p Claim Whether the argument should be claimed, if it exists. - Arg *getLastArgNoClaim(OptSpecifier Id) const; - Arg *getLastArgNoClaim(OptSpecifier Id0, OptSpecifier Id1) const; - Arg *getLastArgNoClaim(OptSpecifier Id0, OptSpecifier Id1, - OptSpecifier Id2) const; - Arg *getLastArgNoClaim(OptSpecifier Id0, OptSpecifier Id1, OptSpecifier Id2, - OptSpecifier Id3) const; - Arg *getLastArg(OptSpecifier Id) const; - Arg *getLastArg(OptSpecifier Id0, OptSpecifier Id1) const; - Arg *getLastArg(OptSpecifier Id0, OptSpecifier Id1, OptSpecifier Id2) const; - Arg *getLastArg(OptSpecifier Id0, OptSpecifier Id1, OptSpecifier Id2, - OptSpecifier Id3) const; - Arg *getLastArg(OptSpecifier Id0, OptSpecifier Id1, OptSpecifier Id2, - OptSpecifier Id3, OptSpecifier Id4) const; - Arg *getLastArg(OptSpecifier Id0, OptSpecifier Id1, OptSpecifier Id2, - OptSpecifier Id3, OptSpecifier Id4, OptSpecifier Id5) const; - Arg *getLastArg(OptSpecifier Id0, OptSpecifier Id1, OptSpecifier Id2, - OptSpecifier Id3, OptSpecifier Id4, OptSpecifier Id5, - OptSpecifier Id6) const; - Arg *getLastArg(OptSpecifier Id0, OptSpecifier Id1, OptSpecifier Id2, - OptSpecifier Id3, OptSpecifier Id4, OptSpecifier Id5, - OptSpecifier Id6, OptSpecifier Id7) const; /// getArgString - Return the input argument string at \p Index. virtual const char *getArgString(unsigned Index) const = 0; @@ -230,8 +265,7 @@ /// @{ /// getLastArgValue - Return the value of the last argument, or a default. - StringRef getLastArgValue(OptSpecifier Id, - StringRef Default = "") const; + StringRef getLastArgValue(OptSpecifier Id, StringRef Default = "") const; /// getAllArgValues - Get the values of all instances of the given argument /// as strings. @@ -273,7 +307,7 @@ /// AddAllArgValues - Render the argument values of all arguments /// matching the given ids. void AddAllArgValues(ArgStringList &Output, OptSpecifier Id0, - OptSpecifier Id1 = 0U, OptSpecifier Id2 = 0U) const; + OptSpecifier Id1 = 0U, OptSpecifier Id2 = 0U) const; /// AddAllArgsTranslated - Render all the arguments matching the /// given ids, but forced to separate args and using the provided Index: llvm/trunk/lib/Option/ArgList.cpp =================================================================== --- llvm/trunk/lib/Option/ArgList.cpp +++ llvm/trunk/lib/Option/ArgList.cpp @@ -19,203 +19,44 @@ using namespace llvm; using namespace llvm::opt; -void arg_iterator::SkipToNextArg() { - for (; Current != Args.end(); ++Current) { - // Done if there are no filters. - if (!Id0.isValid()) - break; - - // Otherwise require a match. - const Option &O = (*Current)->getOption(); - if (O.matches(Id0) || - (Id1.isValid() && O.matches(Id1)) || - (Id2.isValid() && O.matches(Id2))) - break; - } -} - void ArgList::append(Arg *A) { Args.push_back(A); -} - -void ArgList::eraseArg(OptSpecifier Id) { - Args.erase( - remove_if(*this, [=](Arg *A) { return A->getOption().matches(Id); }), - end()); -} - -Arg *ArgList::getLastArgNoClaim(OptSpecifier Id) const { - // FIXME: Make search efficient? - for (const_reverse_iterator it = rbegin(), ie = rend(); it != ie; ++it) - if ((*it)->getOption().matches(Id)) - return *it; - return nullptr; -} - -Arg *ArgList::getLastArgNoClaim(OptSpecifier Id0, OptSpecifier Id1) const { - // FIXME: Make search efficient? - for (const_reverse_iterator it = rbegin(), ie = rend(); it != ie; ++it) - if ((*it)->getOption().matches(Id0) || - (*it)->getOption().matches(Id1)) - return *it; - return nullptr; -} - -Arg *ArgList::getLastArgNoClaim(OptSpecifier Id0, OptSpecifier Id1, - OptSpecifier Id2) const { - // FIXME: Make search efficient? - for (const_reverse_iterator it = rbegin(), ie = rend(); it != ie; ++it) - if ((*it)->getOption().matches(Id0) || (*it)->getOption().matches(Id1) || - (*it)->getOption().matches(Id2)) - return *it; - return nullptr; -} - -Arg *ArgList::getLastArgNoClaim(OptSpecifier Id0, OptSpecifier Id1, - OptSpecifier Id2, OptSpecifier Id3) const { - // FIXME: Make search efficient? - for (const_reverse_iterator it = rbegin(), ie = rend(); it != ie; ++it) - if ((*it)->getOption().matches(Id0) || (*it)->getOption().matches(Id1) || - (*it)->getOption().matches(Id2) || (*it)->getOption().matches(Id3)) - return *it; - return nullptr; -} - -Arg *ArgList::getLastArg(OptSpecifier Id) const { - Arg *Res = nullptr; - for (const_iterator it = begin(), ie = end(); it != ie; ++it) { - if ((*it)->getOption().matches(Id)) { - Res = *it; - Res->claim(); - } - } - - return Res; -} - -Arg *ArgList::getLastArg(OptSpecifier Id0, OptSpecifier Id1) const { - Arg *Res = nullptr; - for (const_iterator it = begin(), ie = end(); it != ie; ++it) { - if ((*it)->getOption().matches(Id0) || - (*it)->getOption().matches(Id1)) { - Res = *it; - Res->claim(); - - } - } - - return Res; -} - -Arg *ArgList::getLastArg(OptSpecifier Id0, OptSpecifier Id1, - OptSpecifier Id2) const { - Arg *Res = nullptr; - for (const_iterator it = begin(), ie = end(); it != ie; ++it) { - if ((*it)->getOption().matches(Id0) || - (*it)->getOption().matches(Id1) || - (*it)->getOption().matches(Id2)) { - Res = *it; - Res->claim(); - } - } - - return Res; -} -Arg *ArgList::getLastArg(OptSpecifier Id0, OptSpecifier Id1, - OptSpecifier Id2, OptSpecifier Id3) const { - Arg *Res = nullptr; - for (const_iterator it = begin(), ie = end(); it != ie; ++it) { - if ((*it)->getOption().matches(Id0) || - (*it)->getOption().matches(Id1) || - (*it)->getOption().matches(Id2) || - (*it)->getOption().matches(Id3)) { - Res = *it; - Res->claim(); - } + // Update ranges for the option and all of its groups. + for (Option O = A->getOption().getUnaliasedOption(); O.isValid(); + O = O.getGroup()) { + auto &R = + OptRanges.insert(std::make_pair(O.getID(), emptyRange())).first->second; + R.first = std::min(R.first, Args.size() - 1); + R.second = Args.size(); } - - return Res; } -Arg *ArgList::getLastArg(OptSpecifier Id0, OptSpecifier Id1, - OptSpecifier Id2, OptSpecifier Id3, - OptSpecifier Id4) const { - Arg *Res = nullptr; - for (const_iterator it = begin(), ie = end(); it != ie; ++it) { - if ((*it)->getOption().matches(Id0) || - (*it)->getOption().matches(Id1) || - (*it)->getOption().matches(Id2) || - (*it)->getOption().matches(Id3) || - (*it)->getOption().matches(Id4)) { - Res = *it; - Res->claim(); - } - } - - return Res; -} - -Arg *ArgList::getLastArg(OptSpecifier Id0, OptSpecifier Id1, - OptSpecifier Id2, OptSpecifier Id3, - OptSpecifier Id4, OptSpecifier Id5) const { - Arg *Res = nullptr; - for (const_iterator it = begin(), ie = end(); it != ie; ++it) { - if ((*it)->getOption().matches(Id0) || - (*it)->getOption().matches(Id1) || - (*it)->getOption().matches(Id2) || - (*it)->getOption().matches(Id3) || - (*it)->getOption().matches(Id4) || - (*it)->getOption().matches(Id5)) { - Res = *it; - Res->claim(); - } - } - - return Res; -} - -Arg *ArgList::getLastArg(OptSpecifier Id0, OptSpecifier Id1, - OptSpecifier Id2, OptSpecifier Id3, - OptSpecifier Id4, OptSpecifier Id5, - OptSpecifier Id6) const { - Arg *Res = nullptr; - for (const_iterator it = begin(), ie = end(); it != ie; ++it) { - if ((*it)->getOption().matches(Id0) || - (*it)->getOption().matches(Id1) || - (*it)->getOption().matches(Id2) || - (*it)->getOption().matches(Id3) || - (*it)->getOption().matches(Id4) || - (*it)->getOption().matches(Id5) || - (*it)->getOption().matches(Id6)) { - Res = *it; - Res->claim(); - } - } - - return Res; -} - -Arg *ArgList::getLastArg(OptSpecifier Id0, OptSpecifier Id1, - OptSpecifier Id2, OptSpecifier Id3, - OptSpecifier Id4, OptSpecifier Id5, - OptSpecifier Id6, OptSpecifier Id7) const { - Arg *Res = nullptr; - for (const_iterator it = begin(), ie = end(); it != ie; ++it) { - if ((*it)->getOption().matches(Id0) || - (*it)->getOption().matches(Id1) || - (*it)->getOption().matches(Id2) || - (*it)->getOption().matches(Id3) || - (*it)->getOption().matches(Id4) || - (*it)->getOption().matches(Id5) || - (*it)->getOption().matches(Id6) || - (*it)->getOption().matches(Id7)) { - Res = *it; - Res->claim(); - } - } - - return Res; +void ArgList::eraseArg(OptSpecifier Id) { + // Zero out the removed entries but keep them around so that we don't + // need to invalidate OptRanges. + for (Arg *const &A : filtered(Id)) { + // Avoid the need for a non-const filtered iterator variant. + Arg **ArgsBegin = Args.data(); + ArgsBegin[&A - ArgsBegin] = nullptr; + } + OptRanges.erase(Id.getID()); +} + +ArgList::OptRange +ArgList::getRange(std::initializer_list Ids) const { + OptRange R = emptyRange(); + for (auto Id : Ids) { + auto I = OptRanges.find(Id.getID()); + if (I != OptRanges.end()) { + R.first = std::min(R.first, I->second.first); + R.second = std::max(R.second, I->second.second); + } + } + // Map an empty {-1, 0} range to {0, 0} so it can be used to form iterators. + if (R.first == -1u) + R.first = 0; + return R; } bool ArgList::hasFlag(OptSpecifier Pos, OptSpecifier Neg, bool Default) const { @@ -231,8 +72,7 @@ return Default; } -StringRef ArgList::getLastArgValue(OptSpecifier Id, - StringRef Default) const { +StringRef ArgList::getLastArgValue(OptSpecifier Id, StringRef Default) const { if (Arg *A = getLastArg(Id)) return A->getValue(); return Default; @@ -262,7 +102,7 @@ void ArgList::AddAllArgsExcept(ArgStringList &Output, ArrayRef Ids, ArrayRef ExcludeIds) const { - for (const Arg *Arg : Args) { + for (const Arg *Arg : *this) { bool Excluded = false; for (OptSpecifier Id : ExcludeIds) { if (Arg->getOption().matches(Id)) { @@ -325,14 +165,14 @@ } void ArgList::ClaimAllArgs(OptSpecifier Id0) const { - for (auto Arg : filtered(Id0)) + for (auto *Arg : filtered(Id0)) Arg->claim(); } void ArgList::ClaimAllArgs() const { - for (const_iterator it = begin(), ie = end(); it != ie; ++it) - if (!(*it)->isClaimed()) - (*it)->claim(); + for (auto *Arg : *this) + if (!Arg->isClaimed()) + Arg->claim(); } const char *ArgList::GetOrMakeJoinedArgString(unsigned Index,