cmdline/token_range.h - platform/art - Gitiles

 /*
  * Copyright (C) 2015 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #ifndef ART_CMDLINE_TOKEN_RANGE_H_
 #define ART_CMDLINE_TOKEN_RANGE_H_

 #include <assert.h>
 #include <algorithm>
 #include <memory>
 #include <string>
 #include <vector>

 #include "android-base/strings.h"

 namespace art {
 // A range of tokens to make token matching algorithms easier.
 //
 // We try really hard to avoid copying and store only a pointer and iterators to the
 // interiors of the vector, so a typical copy constructor never ends up doing a deep copy.
 // It is up to the user to play nice and not to mutate the strings in-place.
 //
 // Tokens are only copied if a mutating operation is performed (and even then only
 // if it *actually* mutates the token).
 struct TokenRange {
   // Short-hand for a vector of strings. A single string and a token is synonymous.
   using TokenList = std::vector<std::string>;

   // Copying-from-vector constructor.
   explicit TokenRange(const TokenList& token_list)
     : token_list_(new TokenList(token_list)),
       begin_(token_list_->begin()),
       end_(token_list_->end())
   {}

   // Copying-from-iterator constructor
   template <typename ForwardIterator>
   TokenRange(ForwardIterator it_begin, ForwardIterator it_end)
     : token_list_(new TokenList(it_begin, it_end)),
       begin_(token_list_->begin()),
       end_(token_list_->end())
   {}

 #if 0
   // Copying-from-vector constructor.
   TokenRange(const TokenList& token_list ATTRIBUTE_UNUSED,
              TokenList::const_iterator it_begin,
              TokenList::const_iterator it_end)
     : token_list_(new TokenList(it_begin, it_end)),
       begin_(token_list_->begin()),
       end_(token_list_->end()) {
     assert(it_begin >= token_list.begin());
     assert(it_end <= token_list.end());
   }
 #endif

   // Copying from char array constructor, convertings into tokens (strings) along the way.
   TokenRange(const char* token_list[], size_t length)
     : token_list_(new TokenList(&token_list[0], &token_list[length])),
       begin_(token_list_->begin()),
       end_(token_list_->end())
   {}

   // Non-copying move-from-vector constructor. Takes over the token vector.
   explicit TokenRange(TokenList&& token_list)
     : token_list_(new TokenList(std::forward<TokenList>(token_list))),
       begin_(token_list_->begin()),
       end_(token_list_->end())
   {}

   // Non-copying constructor. Retain reference to existing list of tokens.
   TokenRange(std::shared_ptr<TokenList> token_list,
              TokenList::const_iterator it_begin,
              TokenList::const_iterator it_end)
     : token_list_(token_list),
       begin_(it_begin),
       end_(it_end) {
     assert(it_begin >= token_list->begin());
     assert(it_end <= token_list->end());
   }

   // Non-copying copy constructor.
   TokenRange(const TokenRange&) = default;

   // Non-copying move constructor.
   TokenRange(TokenRange&&) = default;

   // Non-copying constructor. Retains reference to an existing list of tokens, with offset.
   explicit TokenRange(std::shared_ptr<TokenList> token_list)
     : token_list_(token_list),
       begin_(token_list_->begin()),
       end_(token_list_->end())
   {}

   // Iterator type for begin() and end(). Guaranteed to be a RandomAccessIterator.
   using iterator = TokenList::const_iterator;

   // Iterator type for const begin() and const end(). Guaranteed to be a RandomAccessIterator.
   using const_iterator = iterator;

   // Create a token range by splitting a string. Each separator gets their own token.
   // Since the separator are retained as tokens, it might be useful to call
   // RemoveToken afterwards.
   static TokenRange Split(const std::string& string, std::initializer_list<char> separators) {
     TokenList new_token_list;

     std::string tok;
     for (auto&& c : string) {
       for (char sep : separators) {
         if (c == sep) {
           // We spotted a separator character.
           // Push back everything before the last separator as a new token.
           // Push back the separator as a token.
           if (!tok.empty()) {
             new_token_list.push_back(tok);
             tok = "";
           }
           new_token_list.push_back(std::string() + sep);
         } else {
           // Build up the token with another character.
           tok += c;
         }
       }
     }

     if (!tok.empty()) {
       new_token_list.push_back(tok);
     }

     return TokenRange(std::move(new_token_list));
   }

   // A RandomAccessIterator to the first element in this range.
   iterator begin() const {
     return begin_;
   }

   // A RandomAccessIterator to one past the last element in this range.
   iterator end() const {
     return end_;
   }

   // The size of the range, i.e. how many tokens are in it.
   size_t Size() const {
     return std::distance(begin_, end_);
   }

   // Are there 0 tokens in this range?
   bool IsEmpty() const {
     return Size() > 0;
   }

   // Look up a token by it's offset.
   const std::string& GetToken(size_t offset) const {
     assert(offset < Size());
     return *(begin_ + offset);
   }

   // Does this token range equal the other range?
   // Equality is defined as having both the same size, and
   // each corresponding token being equal.
   bool operator==(const TokenRange& other) const {
     if (this == &other) {
       return true;
     }

     if (Size() != other.Size()) {
       return false;
     }

     return std::equal(begin(), end(), other.begin());
   }

   // Look up the token at the requested index.
   const std::string& operator[](int index) const {
     assert(index >= 0 && static_cast<size_t>(index) < Size());
     return *(begin() + index);
   }

   // Does this current range start with the other range?
   bool StartsWith(const TokenRange& other) const {
     if (this == &other) {
       return true;
     }

     if (Size() < other.Size()) {
       return false;
     }

     auto& smaller = Size() < other.Size() ? *this : other;
     auto& greater = Size() < other.Size() ? other : *this;

     return std::equal(smaller.begin(), smaller.end(), greater.begin());
   }

   // Remove all characters 'c' from each token, potentially copying the underlying tokens.
   TokenRange RemoveCharacter(char c) const {
     TokenList new_token_list(begin(), end());

     bool changed = false;
     for (auto&& token : new_token_list) {
       auto it = std::remove_if(token.begin(), token.end(), [&](char ch) {
         if (ch == c) {
           changed = true;
           return true;
         }
         return false;
       });
       token.erase(it, token.end());
     }

     if (!changed) {
       return *this;
     }

     return TokenRange(std::move(new_token_list));
   }

   // Remove all tokens matching this one, potentially copying the underlying tokens.
   TokenRange RemoveToken(const std::string& token) {
     return RemoveIf([&](const std::string& tok) { return tok == token; });
   }

   // Discard all empty tokens, potentially copying the underlying tokens.
   TokenRange DiscardEmpty() const {
     return RemoveIf([](const std::string& token) { return token.empty(); });
   }

   // Create a non-copying subset of this range.
   // Length is trimmed so that the Slice does not go out of range.
   TokenRange Slice(size_t offset, size_t length = std::string::npos) const {
     assert(offset < Size());

     if (length != std::string::npos && offset + length > Size()) {
       length = Size() - offset;
     }

     iterator it_end;
     if (length == std::string::npos) {
       it_end = end();
     } else {
       it_end = begin() + offset + length;
     }

     return TokenRange(token_list_, begin() + offset, it_end);
   }

   // Try to match the string with tokens from this range.
   // Each token is used to match exactly once (after which the next token is used, and so on).
   // The matching happens from left-to-right in a non-greedy fashion.
   // If the currently-matched token is the wildcard, then the new outputted token will
   // contain as much as possible until the next token is matched.
   //
   // For example, if this == ["a:", "_", "b:] and "_" is the match string, then
   // MatchSubstrings on "a:foob:" will yield: ["a:", "foo", "b:"]
   //
   // Since the string matching can fail (e.g. ["foo"] against "bar"), then this
   // function can fail, in which cause it will return null.
   std::unique_ptr<TokenRange> MatchSubstrings(const std::string& string,
                                               const std::string& wildcard) const {
     TokenList new_token_list;

     size_t wildcard_idx = std::string::npos;
     size_t string_idx = 0;

     // Function to push all the characters matched as a wildcard so far
     // as a brand new token. It resets the wildcard matching.
     // Empty wildcards are possible and ok, but only if wildcard matching was on.
     auto maybe_push_wildcard_token = [&]() {
       if (wildcard_idx != std::string::npos) {
         size_t wildcard_length = string_idx - wildcard_idx;
         std::string wildcard_substr = string.substr(wildcard_idx, wildcard_length);
         new_token_list.push_back(std::move(wildcard_substr));

         wildcard_idx = std::string::npos;
       }
     };

     for (iterator it = begin(); it != end(); ++it) {
       const std::string& tok = *it;

       if (tok == wildcard) {
         maybe_push_wildcard_token();
         wildcard_idx = string_idx;
         continue;
       }

       size_t next_token_idx = string.find(tok);
       if (next_token_idx == std::string::npos) {
         // Could not find token at all
         return nullptr;
       } else if (next_token_idx != string_idx && wildcard_idx == std::string::npos) {
         // Found the token at a non-starting location, and we weren't
         // trying to parse the wildcard.
         return nullptr;
       }

       new_token_list.push_back(string.substr(next_token_idx, tok.size()));
       maybe_push_wildcard_token();
       string_idx += tok.size();
     }

     size_t remaining = string.size() - string_idx;
     if (remaining > 0) {
       if (wildcard_idx == std::string::npos) {
         // Some characters were still remaining in the string,
         // but it wasn't trying to match a wildcard.
         return nullptr;
       }
     }

     // If some characters are remaining, the rest must be a wildcard.
     string_idx += remaining;
     maybe_push_wildcard_token();

     return std::unique_ptr<TokenRange>(new TokenRange(std::move(new_token_list)));
   }

   // Do a quick match token-by-token, and see if they match.
   // Any tokens with a wildcard in them are only matched up until the wildcard.
   // If this is true, then the wildcard matching later on can still fail, so this is not
   // a guarantee that the argument is correct, it's more of a strong hint that the
   // user-provided input *probably* was trying to match this argument.
   //
   // Returns how many tokens were either matched (or ignored because there was a
   // wildcard present). 0 means no match. If the size() tokens are returned.
   size_t MaybeMatches(const TokenRange& token_list, const std::string& wildcard) const {
     auto token_it = token_list.begin();
     auto token_end = token_list.end();
     auto name_it = begin();
     auto name_end = end();

     size_t matched_tokens = 0;

     while (token_it != token_end && name_it != name_end) {
       // Skip token matching when the corresponding name has a wildcard in it.
       const std::string& name = *name_it;

       size_t wildcard_idx = name.find(wildcard);
       if (wildcard_idx == std::string::npos) {  // No wildcard present
         // Did the definition token match the user token?
         if (name != *token_it) {
           return matched_tokens;
         }
       } else {
         std::string name_prefix = name.substr(0, wildcard_idx);

         // Did the user token start with the up-to-the-wildcard prefix?
         if (!StartsWith(*token_it, name_prefix)) {
           return matched_tokens;
         }
       }

       ++token_it;
       ++name_it;
       ++matched_tokens;
     }

     // If we got this far, it's either a full match or the token list was too short.
     return matched_tokens;
   }

   // Flatten the token range by joining every adjacent token with the separator character.
   // e.g. ["hello", "world"].join('$') == "hello$world"
   std::string Join(char separator) const {
     TokenList tmp(begin(), end());
     return android::base::Join(tmp, separator);
     // TODO: Join should probably take an offset or iterators
   }

  private:
   static bool StartsWith(const std::string& larger, const std::string& smaller) {
     if (larger.size() >= smaller.size()) {
       return std::equal(smaller.begin(), smaller.end(), larger.begin());
     }

     return false;
   }

   template <typename TPredicate>
   TokenRange RemoveIf(const TPredicate& predicate) const {
     // If any of the tokens in the token lists are empty, then
     // we need to remove them and compress the token list into a smaller one.
     bool remove = false;
     for (auto it = begin_; it != end_; ++it) {
       auto&& token = *it;

       if (predicate(token)) {
         remove = true;
         break;
       }
     }

     // Actually copy the token list and remove the tokens that don't match our predicate.
     if (remove) {
       auto token_list = std::make_shared<TokenList>(begin(), end());
       TokenList::iterator new_end =
           std::remove_if(token_list->begin(), token_list->end(), predicate);
       token_list->erase(new_end, token_list->end());

       assert(token_list_->size() > token_list->size() && "Nothing was actually removed!");

       return TokenRange(token_list);
     }

     return *this;
   }

   const std::shared_ptr<std::vector<std::string>> token_list_;
   const iterator begin_;
   const iterator end_;
 };
 }  // namespace art

 #endif  // ART_CMDLINE_TOKEN_RANGE_H_
	/*
	* Copyright (C) 2015 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#ifndef ART_CMDLINE_TOKEN_RANGE_H_
	#define ART_CMDLINE_TOKEN_RANGE_H_

	#include <assert.h>
	#include <algorithm>
	#include <memory>
	#include <string>
	#include <vector>

	#include "android-base/strings.h"

	namespace art {
	// A range of tokens to make token matching algorithms easier.
	//
	// We try really hard to avoid copying and store only a pointer and iterators to the
	// interiors of the vector, so a typical copy constructor never ends up doing a deep copy.
	// It is up to the user to play nice and not to mutate the strings in-place.
	//
	// Tokens are only copied if a mutating operation is performed (and even then only
	// if it actually mutates the token).
	struct TokenRange {
	// Short-hand for a vector of strings. A single string and a token is synonymous.
	using TokenList = std::vector<std::string>;

	// Copying-from-vector constructor.
	explicit TokenRange(const TokenList& token_list)
	: token_list_(new TokenList(token_list)),
	begin_(token_list_->begin()),
	end_(token_list_->end())
	{}

	// Copying-from-iterator constructor
	template <typename ForwardIterator>
	TokenRange(ForwardIterator it_begin, ForwardIterator it_end)
	: token_list_(new TokenList(it_begin, it_end)),
	begin_(token_list_->begin()),
	end_(token_list_->end())
	{}

	#if 0
	// Copying-from-vector constructor.
	TokenRange(const TokenList& token_list ATTRIBUTE_UNUSED,
	TokenList::const_iterator it_begin,
	TokenList::const_iterator it_end)
	: token_list_(new TokenList(it_begin, it_end)),
	begin_(token_list_->begin()),
	end_(token_list_->end()) {
	assert(it_begin >= token_list.begin());
	assert(it_end <= token_list.end());
	}
	#endif

	// Copying from char array constructor, convertings into tokens (strings) along the way.
	TokenRange(const char* token_list[], size_t length)
	: token_list_(new TokenList(&token_list[0], &token_list[length])),
	begin_(token_list_->begin()),
	end_(token_list_->end())
	{}

	// Non-copying move-from-vector constructor. Takes over the token vector.
	explicit TokenRange(TokenList&& token_list)
	: token_list_(new TokenList(std::forward<TokenList>(token_list))),
	begin_(token_list_->begin()),
	end_(token_list_->end())
	{}

	// Non-copying constructor. Retain reference to existing list of tokens.
	TokenRange(std::shared_ptr<TokenList> token_list,
	TokenList::const_iterator it_begin,
	TokenList::const_iterator it_end)
	: token_list_(token_list),
	begin_(it_begin),
	end_(it_end) {
	assert(it_begin >= token_list->begin());
	assert(it_end <= token_list->end());
	}

	// Non-copying copy constructor.
	TokenRange(const TokenRange&) = default;

	// Non-copying move constructor.
	TokenRange(TokenRange&&) = default;

	// Non-copying constructor. Retains reference to an existing list of tokens, with offset.
	explicit TokenRange(std::shared_ptr<TokenList> token_list)
	: token_list_(token_list),
	begin_(token_list_->begin()),
	end_(token_list_->end())
	{}

	// Iterator type for begin() and end(). Guaranteed to be a RandomAccessIterator.
	using iterator = TokenList::const_iterator;

	// Iterator type for const begin() and const end(). Guaranteed to be a RandomAccessIterator.
	using const_iterator = iterator;

	// Create a token range by splitting a string. Each separator gets their own token.
	// Since the separator are retained as tokens, it might be useful to call
	// RemoveToken afterwards.
	static TokenRange Split(const std::string& string, std::initializer_list<char> separators) {
	TokenList new_token_list;

	std::string tok;
	for (auto&& c : string) {
	for (char sep : separators) {
	if (c == sep) {
	// We spotted a separator character.
	// Push back everything before the last separator as a new token.
	// Push back the separator as a token.
	if (!tok.empty()) {
	new_token_list.push_back(tok);
	tok = "";
	}
	new_token_list.push_back(std::string() + sep);
	} else {
	// Build up the token with another character.
	tok += c;
	}
	}
	}

	if (!tok.empty()) {
	new_token_list.push_back(tok);
	}

	return TokenRange(std::move(new_token_list));
	}

	// A RandomAccessIterator to the first element in this range.
	iterator begin() const {
	return begin_;
	}

	// A RandomAccessIterator to one past the last element in this range.
	iterator end() const {
	return end_;
	}

	// The size of the range, i.e. how many tokens are in it.
	size_t Size() const {
	return std::distance(begin_, end_);
	}

	// Are there 0 tokens in this range?
	bool IsEmpty() const {
	return Size() > 0;
	}

	// Look up a token by it's offset.
	const std::string& GetToken(size_t offset) const {
	assert(offset < Size());
	return *(begin_ + offset);
	}

	// Does this token range equal the other range?
	// Equality is defined as having both the same size, and
	// each corresponding token being equal.
	bool operator==(const TokenRange& other) const {
	if (this == &other) {
	return true;
	}

	if (Size() != other.Size()) {
	return false;
	}

	return std::equal(begin(), end(), other.begin());
	}

	// Look up the token at the requested index.
	const std::string& operator[](int index) const {
	assert(index >= 0 && static_cast<size_t>(index) < Size());
	return *(begin() + index);
	}

	// Does this current range start with the other range?
	bool StartsWith(const TokenRange& other) const {
	if (this == &other) {
	return true;
	}

	if (Size() < other.Size()) {
	return false;
	}

	auto& smaller = Size() < other.Size() ? *this : other;
	auto& greater = Size() < other.Size() ? other : *this;

	return std::equal(smaller.begin(), smaller.end(), greater.begin());
	}

	// Remove all characters 'c' from each token, potentially copying the underlying tokens.
	TokenRange RemoveCharacter(char c) const {
	TokenList new_token_list(begin(), end());

	bool changed = false;
	for (auto&& token : new_token_list) {
	auto it = std::remove_if(token.begin(), token.end(), [&](char ch) {
	if (ch == c) {
	changed = true;
	return true;
	}
	return false;
	});
	token.erase(it, token.end());
	}

	if (!changed) {
	return *this;
	}

	return TokenRange(std::move(new_token_list));
	}

	// Remove all tokens matching this one, potentially copying the underlying tokens.
	TokenRange RemoveToken(const std::string& token) {
	return RemoveIf([&](const std::string& tok) { return tok == token; });
	}

	// Discard all empty tokens, potentially copying the underlying tokens.
	TokenRange DiscardEmpty() const {
	return RemoveIf([](const std::string& token) { return token.empty(); });
	}

	// Create a non-copying subset of this range.
	// Length is trimmed so that the Slice does not go out of range.
	TokenRange Slice(size_t offset, size_t length = std::string::npos) const {
	assert(offset < Size());

	if (length != std::string::npos && offset + length > Size()) {
	length = Size() - offset;
	}

	iterator it_end;
	if (length == std::string::npos) {
	it_end = end();
	} else {
	it_end = begin() + offset + length;
	}

	return TokenRange(token_list_, begin() + offset, it_end);
	}

	// Try to match the string with tokens from this range.
	// Each token is used to match exactly once (after which the next token is used, and so on).
	// The matching happens from left-to-right in a non-greedy fashion.
	// If the currently-matched token is the wildcard, then the new outputted token will
	// contain as much as possible until the next token is matched.
	//
	// For example, if this == ["a:", "_", "b:] and "_" is the match string, then
	// MatchSubstrings on "a:foob:" will yield: ["a:", "foo", "b:"]
	//
	// Since the string matching can fail (e.g. ["foo"] against "bar"), then this
	// function can fail, in which cause it will return null.
	std::unique_ptr<TokenRange> MatchSubstrings(const std::string& string,
	const std::string& wildcard) const {
	TokenList new_token_list;

	size_t wildcard_idx = std::string::npos;
	size_t string_idx = 0;

	// Function to push all the characters matched as a wildcard so far
	// as a brand new token. It resets the wildcard matching.
	// Empty wildcards are possible and ok, but only if wildcard matching was on.
	auto maybe_push_wildcard_token = [&]() {
	if (wildcard_idx != std::string::npos) {
	size_t wildcard_length = string_idx - wildcard_idx;
	std::string wildcard_substr = string.substr(wildcard_idx, wildcard_length);
	new_token_list.push_back(std::move(wildcard_substr));

	wildcard_idx = std::string::npos;
	}
	};

	for (iterator it = begin(); it != end(); ++it) {
	const std::string& tok = *it;

	if (tok == wildcard) {
	maybe_push_wildcard_token();
	wildcard_idx = string_idx;
	continue;
	}

	size_t next_token_idx = string.find(tok);
	if (next_token_idx == std::string::npos) {
	// Could not find token at all
	return nullptr;
	} else if (next_token_idx != string_idx && wildcard_idx == std::string::npos) {
	// Found the token at a non-starting location, and we weren't
	// trying to parse the wildcard.
	return nullptr;
	}

	new_token_list.push_back(string.substr(next_token_idx, tok.size()));
	maybe_push_wildcard_token();
	string_idx += tok.size();
	}

	size_t remaining = string.size() - string_idx;
	if (remaining > 0) {
	if (wildcard_idx == std::string::npos) {
	// Some characters were still remaining in the string,
	// but it wasn't trying to match a wildcard.
	return nullptr;
	}
	}

	// If some characters are remaining, the rest must be a wildcard.
	string_idx += remaining;
	maybe_push_wildcard_token();

	return std::unique_ptr<TokenRange>(new TokenRange(std::move(new_token_list)));
	}

	// Do a quick match token-by-token, and see if they match.
	// Any tokens with a wildcard in them are only matched up until the wildcard.
	// If this is true, then the wildcard matching later on can still fail, so this is not
	// a guarantee that the argument is correct, it's more of a strong hint that the
	// user-provided input probably was trying to match this argument.
	//
	// Returns how many tokens were either matched (or ignored because there was a
	// wildcard present). 0 means no match. If the size() tokens are returned.
	size_t MaybeMatches(const TokenRange& token_list, const std::string& wildcard) const {
	auto token_it = token_list.begin();
	auto token_end = token_list.end();
	auto name_it = begin();
	auto name_end = end();

	size_t matched_tokens = 0;

	while (token_it != token_end && name_it != name_end) {
	// Skip token matching when the corresponding name has a wildcard in it.
	const std::string& name = *name_it;

	size_t wildcard_idx = name.find(wildcard);
	if (wildcard_idx == std::string::npos) { // No wildcard present
	// Did the definition token match the user token?
	if (name != *token_it) {
	return matched_tokens;
	}
	} else {
	std::string name_prefix = name.substr(0, wildcard_idx);

	// Did the user token start with the up-to-the-wildcard prefix?
	if (!StartsWith(*token_it, name_prefix)) {
	return matched_tokens;
	}
	}

	++token_it;
	++name_it;
	++matched_tokens;
	}

	// If we got this far, it's either a full match or the token list was too short.
	return matched_tokens;
	}

	// Flatten the token range by joining every adjacent token with the separator character.
	// e.g. ["hello", "world"].join('$') == "hello$world"
	std::string Join(char separator) const {
	TokenList tmp(begin(), end());
	return android::base::Join(tmp, separator);
	// TODO: Join should probably take an offset or iterators
	}

	private:
	static bool StartsWith(const std::string& larger, const std::string& smaller) {
	if (larger.size() >= smaller.size()) {
	return std::equal(smaller.begin(), smaller.end(), larger.begin());
	}

	return false;
	}

	template <typename TPredicate>
	TokenRange RemoveIf(const TPredicate& predicate) const {
	// If any of the tokens in the token lists are empty, then
	// we need to remove them and compress the token list into a smaller one.
	bool remove = false;
	for (auto it = begin_; it != end_; ++it) {
	auto&& token = *it;

	if (predicate(token)) {
	remove = true;
	break;
	}
	}

	// Actually copy the token list and remove the tokens that don't match our predicate.
	if (remove) {
	auto token_list = std::make_shared<TokenList>(begin(), end());
	TokenList::iterator new_end =
	std::remove_if(token_list->begin(), token_list->end(), predicate);
	token_list->erase(new_end, token_list->end());

	assert(token_list_->size() > token_list->size() && "Nothing was actually removed!");

	return TokenRange(token_list);
	}

	return *this;
	}

	const std::shared_ptr<std::vector<std::string>> token_list_;
	const iterator begin_;
	const iterator end_;
	};
	} // namespace art

	#endif // ART_CMDLINE_TOKEN_RANGE_H_