string_tokenizer.h 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360
  1. // Copyright (c) 2011 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef BASE_STRINGS_STRING_TOKENIZER_H_
  5. #define BASE_STRINGS_STRING_TOKENIZER_H_
  6. #include <algorithm>
  7. #include <string>
  8. #include "base/check.h"
  9. #include "base/strings/string_piece.h"
  10. #include "base/strings/string_util.h"
  11. namespace base {
  12. // StringTokenizerT is a simple string tokenizer class. It works like an
  13. // iterator that with each step (see the Advance method) updates members that
  14. // refer to the next token in the input string. The user may optionally
  15. // configure the tokenizer to return delimiters. For the optional
  16. // WhitespacePolicy parameter, kSkipOver will cause the tokenizer to skip
  17. // over whitespace characters. The tokenizer never stops on a whitespace
  18. // character.
  19. //
  20. // EXAMPLE 1:
  21. //
  22. // char input[] = "this is a test";
  23. // CStringTokenizer t(input, input + strlen(input), " ");
  24. // while (t.GetNext()) {
  25. // printf("%s\n", t.token().c_str());
  26. // }
  27. //
  28. // Output:
  29. //
  30. // this
  31. // is
  32. // a
  33. // test
  34. //
  35. //
  36. // EXAMPLE 2:
  37. //
  38. // std::string input = "no-cache=\"foo, bar\", private";
  39. // StringTokenizer t(input, ", ");
  40. // t.set_quote_chars("\"");
  41. // while (t.GetNext()) {
  42. // printf("%s\n", t.token().c_str());
  43. // }
  44. //
  45. // Output:
  46. //
  47. // no-cache="foo, bar"
  48. // private
  49. //
  50. //
  51. // EXAMPLE 3:
  52. //
  53. // bool next_is_option = false, next_is_value = false;
  54. // std::string input = "text/html; charset=UTF-8; foo=bar";
  55. // StringTokenizer t(input, "; =");
  56. // t.set_options(StringTokenizer::RETURN_DELIMS);
  57. // while (t.GetNext()) {
  58. // if (t.token_is_delim()) {
  59. // switch (*t.token_begin()) {
  60. // case ';':
  61. // next_is_option = true;
  62. // break;
  63. // case '=':
  64. // next_is_value = true;
  65. // break;
  66. // }
  67. // } else {
  68. // const char* label;
  69. // if (next_is_option) {
  70. // label = "option-name";
  71. // next_is_option = false;
  72. // } else if (next_is_value) {
  73. // label = "option-value";
  74. // next_is_value = false;
  75. // } else {
  76. // label = "mime-type";
  77. // }
  78. // printf("%s: %s\n", label, t.token().c_str());
  79. // }
  80. // }
  81. //
  82. //
  83. // EXAMPLE 4:
  84. //
  85. // std::string input = "this, \t is, \t a, \t test";
  86. // StringTokenizer t(input, ",",
  87. // StringTokenizer::WhitespacePolicy::kSkipOver);
  88. // while (t.GetNext()) {
  89. // printf("%s\n", t.token().c_str());
  90. // }
  91. //
  92. // Output:
  93. //
  94. // this
  95. // is
  96. // a
  97. // test
  98. //
  99. //
  100. template <class str, class const_iterator>
  101. class StringTokenizerT {
  102. public:
  103. typedef typename str::value_type char_type;
  104. // Options that may be pass to set_options()
  105. enum {
  106. // Specifies the delimiters should be returned as tokens
  107. RETURN_DELIMS = 1 << 0,
  108. // Specifies that empty tokens should be returned. Treats the beginning and
  109. // ending of the string as implicit delimiters, though doesn't return them
  110. // as tokens if RETURN_DELIMS is also used.
  111. RETURN_EMPTY_TOKENS = 1 << 1,
  112. };
  113. // Policy indicating what to do with whitespace characters. Whitespace is
  114. // defined to be the characters indicated here:
  115. // https://www.w3schools.com/jsref/jsref_regexp_whitespace.asp
  116. enum class WhitespacePolicy {
  117. // Whitespace should be treated the same as any other non-delimiter
  118. // character.
  119. kIncludeInTokens,
  120. // Whitespace is skipped over and not included in the resulting token.
  121. // Whitespace will also delimit other tokens, however it is never returned
  122. // even if RETURN_DELIMS is set. If quote chars are set (See set_quote_chars
  123. // below) Whitespace will be included in a token when processing quotes.
  124. kSkipOver,
  125. };
  126. // The string object must live longer than the tokenizer. In particular, this
  127. // should not be constructed with a temporary. The deleted rvalue constructor
  128. // blocks the most obvious instances of this (e.g. passing a string literal to
  129. // the constructor), but caution must still be exercised.
  130. StringTokenizerT(
  131. const str& string,
  132. const str& delims,
  133. WhitespacePolicy whitespace_policy = WhitespacePolicy::kIncludeInTokens) {
  134. Init(string.begin(), string.end(), delims, whitespace_policy);
  135. }
  136. // Don't allow temporary strings to be used with string tokenizer, since
  137. // Init() would otherwise save iterators to a temporary string.
  138. StringTokenizerT(str&&, const str& delims) = delete;
  139. StringTokenizerT(
  140. const_iterator string_begin,
  141. const_iterator string_end,
  142. const str& delims,
  143. WhitespacePolicy whitespace_policy = WhitespacePolicy::kIncludeInTokens) {
  144. Init(string_begin, string_end, delims, whitespace_policy);
  145. }
  146. // Set the options for this tokenizer. By default, this is 0.
  147. void set_options(int options) { options_ = options; }
  148. // Set the characters to regard as quotes. By default, this is empty. When
  149. // a quote char is encountered, the tokenizer will switch into a mode where
  150. // it ignores delimiters that it finds. It switches out of this mode once it
  151. // finds another instance of the quote char. If a backslash is encountered
  152. // within a quoted string, then the next character is skipped.
  153. void set_quote_chars(const str& quotes) { quotes_ = quotes; }
  154. // Call this method to advance the tokenizer to the next delimiter. This
  155. // returns false if the tokenizer is complete. This method must be called
  156. // before calling any of the token* methods.
  157. bool GetNext() {
  158. if (quotes_.empty() && options_ == 0)
  159. return QuickGetNext();
  160. else
  161. return FullGetNext();
  162. }
  163. // Start iterating through tokens from the beginning of the string.
  164. void Reset() {
  165. token_end_ = start_pos_;
  166. }
  167. // Returns true if token is a delimiter. When the tokenizer is constructed
  168. // with the RETURN_DELIMS option, this method can be used to check if the
  169. // returned token is actually a delimiter. Returns true before the first
  170. // time GetNext() has been called, and after GetNext() returns false.
  171. bool token_is_delim() const { return token_is_delim_; }
  172. // If GetNext() returned true, then these methods may be used to read the
  173. // value of the token.
  174. const_iterator token_begin() const { return token_begin_; }
  175. const_iterator token_end() const { return token_end_; }
  176. str token() const { return str(token_begin_, token_end_); }
  177. BasicStringPiece<char_type> token_piece() const {
  178. return MakeBasicStringPiece<char_type>(token_begin_, token_end_);
  179. }
  180. private:
  181. void Init(const_iterator string_begin,
  182. const_iterator string_end,
  183. const str& delims,
  184. WhitespacePolicy whitespace_policy) {
  185. start_pos_ = string_begin;
  186. token_begin_ = string_begin;
  187. token_end_ = string_begin;
  188. end_ = string_end;
  189. delims_ = delims;
  190. options_ = 0;
  191. token_is_delim_ = true;
  192. whitespace_policy_ = whitespace_policy;
  193. }
  194. bool ShouldSkip(char_type c) const {
  195. return whitespace_policy_ == WhitespacePolicy::kSkipOver &&
  196. IsAsciiWhitespace(c);
  197. }
  198. // Skip over any contiguous whitespace characters according to the whitespace
  199. // policy.
  200. void SkipWhitespace() {
  201. while (token_end_ != end_ && ShouldSkip(*token_end_))
  202. ++token_end_;
  203. }
  204. // Implementation of GetNext() for when we have no quote characters. We have
  205. // two separate implementations because AdvanceOne() is a hot spot in large
  206. // text files with large tokens.
  207. bool QuickGetNext() {
  208. token_is_delim_ = false;
  209. for (;;) {
  210. token_begin_ = token_end_;
  211. if (token_end_ == end_) {
  212. token_is_delim_ = true;
  213. return false;
  214. }
  215. ++token_end_;
  216. if (delims_.find(*token_begin_) == str::npos &&
  217. !ShouldSkip(*token_begin_)) {
  218. break;
  219. }
  220. // else skip over delimiter or skippable character.
  221. }
  222. while (token_end_ != end_ && delims_.find(*token_end_) == str::npos &&
  223. !ShouldSkip(*token_end_)) {
  224. ++token_end_;
  225. }
  226. return true;
  227. }
  228. // Implementation of GetNext() for when we have to take quotes into account.
  229. bool FullGetNext() {
  230. AdvanceState state;
  231. SkipWhitespace();
  232. for (;;) {
  233. if (token_is_delim_) {
  234. // Last token was a delimiter. Note: This is also the case at the start.
  235. //
  236. // ... D T T T T D ...
  237. // ^ ^
  238. // | |
  239. // | |token_end_| : The next character to look at or |end_|.
  240. // |
  241. // |token_begin_| : Points to delimiter or |token_end_|.
  242. //
  243. // The next token is always a non-delimiting token. It could be empty,
  244. // however.
  245. token_is_delim_ = false;
  246. token_begin_ = token_end_;
  247. // Slurp all non-delimiter characters into the token.
  248. while (token_end_ != end_ && AdvanceOne(&state, *token_end_)) {
  249. ++token_end_;
  250. }
  251. // If it's non-empty, or empty tokens were requested, return the token.
  252. if (token_begin_ != token_end_ || (options_ & RETURN_EMPTY_TOKENS))
  253. return true;
  254. }
  255. DCHECK(!token_is_delim_);
  256. // Last token was a regular token.
  257. //
  258. // ... T T T D T T ...
  259. // ^ ^
  260. // | |
  261. // | token_end_ : The next character to look at. Always one
  262. // | char beyond the token boundary.
  263. // |
  264. // token_begin_ : Points to beginning of token. Note: token could
  265. // be empty, in which case
  266. // token_begin_ == token_end_.
  267. //
  268. // The next token is always a delimiter. It could be |end_| however, but
  269. // |end_| is also an implicit delimiter.
  270. token_is_delim_ = true;
  271. token_begin_ = token_end_;
  272. if (token_end_ == end_)
  273. return false;
  274. // Look at the delimiter.
  275. ++token_end_;
  276. if (options_ & RETURN_DELIMS)
  277. return true;
  278. }
  279. return false;
  280. }
  281. bool IsDelim(char_type c) const { return delims_.find(c) != str::npos; }
  282. bool IsQuote(char_type c) const { return quotes_.find(c) != str::npos; }
  283. struct AdvanceState {
  284. bool in_quote;
  285. bool in_escape;
  286. char_type quote_char;
  287. AdvanceState() : in_quote(false), in_escape(false), quote_char('\0') {}
  288. };
  289. // Returns true if a delimiter or, depending on policy, whitespace was not
  290. // hit.
  291. bool AdvanceOne(AdvanceState* state, char_type c) {
  292. if (state->in_quote) {
  293. if (state->in_escape) {
  294. state->in_escape = false;
  295. } else if (c == '\\') {
  296. state->in_escape = true;
  297. } else if (c == state->quote_char) {
  298. state->in_quote = false;
  299. }
  300. } else {
  301. if (IsDelim(c) || ShouldSkip(c))
  302. return false;
  303. state->in_quote = IsQuote(state->quote_char = c);
  304. }
  305. return true;
  306. }
  307. const_iterator start_pos_;
  308. const_iterator token_begin_;
  309. const_iterator token_end_;
  310. const_iterator end_;
  311. str delims_;
  312. str quotes_;
  313. int options_;
  314. bool token_is_delim_;
  315. WhitespacePolicy whitespace_policy_;
  316. };
  317. typedef StringTokenizerT<std::string, std::string::const_iterator>
  318. StringTokenizer;
  319. typedef StringTokenizerT<std::u16string, std::u16string::const_iterator>
  320. String16Tokenizer;
  321. typedef StringTokenizerT<std::string, const char*> CStringTokenizer;
  322. } // namespace base
  323. #endif // BASE_STRINGS_STRING_TOKENIZER_H_