folly/gen/String-inl.h

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #ifndef FOLLY_GEN_STRING_H_
  18 #error This file may only be included from folly/gen/String.h
  19 #endif
  20
  21 #include <folly/Conv.h>
  22 #include <folly/Portability.h>
  23 #include <folly/String.h>
  24
  25 namespace folly {
  26 namespace gen {
  27 namespace detail {
  28
  29 /**
  30  * Finds the first occurrence of delimiter in "in", advances "in" past the
  31  * delimiter.  Populates "prefix" with the consumed bytes, including the
  32  * delimiter.
  33  *
  34  * Returns the number of trailing bytes of "prefix" that make up the
  35  * delimiter, or 0 if the delimiter was not found.
  36  */
  37 inline size_t splitPrefix(StringPiece& in,
  38                           StringPiece& prefix,
  39                           char delimiter) {
  40   size_t found = in.find(delimiter);
  41   if (found != StringPiece::npos) {
  42     ++found;
  43     prefix.assign(in.data(), in.data() + found);
  44     in.advance(found);
  45     return 1;
  46   }
  47   prefix.clear();
  48   return 0;
  49 }
  50
  51 /**
  52  * As above, but supports multibyte delimiters.
  53  */
  54 inline size_t splitPrefix(StringPiece& in,
  55                           StringPiece& prefix,
  56                           StringPiece delimiter) {
  57   auto found = in.find(delimiter);
  58   if (found != StringPiece::npos) {
  59     found += delimiter.size();
  60     prefix.assign(in.data(), in.data() + found);
  61     in.advance(found);
  62     return delimiter.size();
  63   }
  64   prefix.clear();
  65   return 0;
  66 }
  67
  68 /**
  69  * As above, but splits by any of the EOL terms: \r, \n, or \r\n.
  70  */
  71 inline size_t splitPrefix(StringPiece& in,
  72                          StringPiece& prefix,
  73                          MixedNewlines) {
  74   const auto kCRLF = "\r\n";
  75   const size_t kLenCRLF = 2;
  76
  77   auto p = in.find_first_of(kCRLF);
  78   if (p != std::string::npos) {
  79     const auto in_start = in.data();
  80     size_t delim_len = 1;
  81     in.advance(p);
  82     // Either remove an MS-DOS CR-LF 2-byte newline, or eat 1 byte at a time.
  83     if (in.removePrefix(kCRLF)) {
  84       delim_len = kLenCRLF;
  85     } else {
  86       in.advance(delim_len);
  87     }
  88     prefix.assign(in_start, in.data());
  89     return delim_len;
  90   }
  91   prefix.clear();
  92   return 0;
  93 }
  94
  95 inline const char* ch(const unsigned char* p) {
  96   return reinterpret_cast<const char*>(p);
  97 }
  98
  99 // Chop s into pieces of at most maxLength, feed them to cb
 100 template <class Callback>
 101 bool consumeFixedSizeChunks(Callback& cb, StringPiece& s, uint64_t maxLength) {
 102   while (!s.empty()) {
 103     auto num_to_add = s.size();
 104     if (maxLength) {
 105       num_to_add = std::min<uint64_t>(num_to_add, maxLength);
 106     }
 107     if (!cb(StringPiece(s.begin(), num_to_add))) {
 108       return false;
 109     }
 110     s.advance(num_to_add);
 111   }
 112   return true;
 113 }
 114
 115 // Consumes all of buffer, plus n chars from s.
 116 template <class Callback>
 117 bool consumeBufferPlus(Callback& cb, IOBuf& buf, StringPiece& s, uint64_t n) {
 118   buf.reserve(0, n);
 119   memcpy(buf.writableTail(), s.data(), n);
 120   buf.append(n);
 121   s.advance(n);
 122   if (!cb(StringPiece(detail::ch(buf.data()), buf.length()))) {
 123     return false;
 124   }
 125   buf.clear();
 126   return true;
 127 }
 128
 129 } // namespace detail
 130
 131 template <class Callback>
 132 bool StreamSplitter<Callback>::flush() {
 133   CHECK(maxLength_ == 0 || buffer_.length() < maxLength_);
 134   if (!pieceCb_(StringPiece(detail::ch(buffer_.data()), buffer_.length()))) {
 135     return false;
 136   }
 137   // We are ready to handle another stream now.
 138   buffer_.clear();
 139   return true;
 140 }
 141
 142 template <class Callback>
 143 bool StreamSplitter<Callback>::operator()(StringPiece in) {
 144   StringPiece prefix;
 145   // NB This code assumes a 1-byte delimiter. It's not too hard to support
 146   // multibyte delimiters, just remember that maxLength_ chunks can end up
 147   // falling in the middle of a delimiter.
 148   bool found = detail::splitPrefix(in, prefix, delimiter_);
 149   if (buffer_.length() != 0) {
 150     if (found) {
 151       uint64_t num_to_add = prefix.size();
 152       if (maxLength_) {
 153         CHECK(buffer_.length() < maxLength_);
 154         // Consume as much of prefix as possible without exceeding maxLength_
 155         num_to_add = std::min(maxLength_ - buffer_.length(), num_to_add);
 156       }
 157
 158       // Append part of the prefix to the buffer, and send it to the callback
 159       if (!detail::consumeBufferPlus(pieceCb_, buffer_, prefix, num_to_add)) {
 160         return false;
 161       }
 162
 163       if (!detail::consumeFixedSizeChunks(pieceCb_, prefix, maxLength_)) {
 164         return false;
 165       }
 166
 167       found = detail::splitPrefix(in, prefix, delimiter_);
 168       // Post-conditions:
 169       //  - we consumed all of buffer_ and all of the first prefix.
 170       //  - found, in, and prefix reflect the second delimiter_ search
 171     } else if (maxLength_ && buffer_.length() + in.size() >= maxLength_) {
 172       // Send all of buffer_, plus a bit of in, to the callback
 173       if (!detail::consumeBufferPlus(
 174                pieceCb_, buffer_, in, maxLength_ - buffer_.length())) {
 175         return false;
 176       }
 177       // Post-conditions:
 178       //  - we consumed all of buffer, and the minimal # of bytes from in
 179       //  - found is false
 180     } // Otherwise: found is false & we cannot invoke the callback this turn
 181   }
 182   // Post-condition: buffer_ is nonempty only if found is false **and**
 183   // len(buffer + in) < maxLength_.
 184
 185   // Send lines to callback directly from input (no buffer)
 186   while (found) {  // Buffer guaranteed to be empty
 187     if (!detail::consumeFixedSizeChunks(pieceCb_, prefix, maxLength_)) {
 188       return false;
 189     }
 190     found = detail::splitPrefix(in, prefix, delimiter_);
 191   }
 192
 193   // No more delimiters left; consume 'in' until it is shorter than maxLength_
 194   if (maxLength_) {
 195     while (in.size() >= maxLength_) {  // Buffer is guaranteed to be empty
 196       if (!pieceCb_(StringPiece(in.begin(), maxLength_))) {
 197         return false;
 198       }
 199       in.advance(maxLength_);
 200     }
 201   }
 202
 203   if (!in.empty()) {  // Buffer may be nonempty
 204     // Incomplete line left, append to buffer
 205     buffer_.reserve(0, in.size());
 206     memcpy(buffer_.writableTail(), in.data(), in.size());
 207     buffer_.append(in.size());
 208   }
 209   CHECK(maxLength_ == 0 || buffer_.length() < maxLength_);
 210   return true;
 211 }
 212
 213 namespace detail {
 214
 215 class StringResplitter : public Operator<StringResplitter> {
 216   char delimiter_;
 217   bool keepDelimiter_;
 218
 219  public:
 220   explicit StringResplitter(char delimiter, bool keepDelimiter = false)
 221       : delimiter_(delimiter), keepDelimiter_(keepDelimiter) {}
 222
 223   template <class Source>
 224   class Generator : public GenImpl<StringPiece, Generator<Source>> {
 225     Source source_;
 226     char delimiter_;
 227     bool keepDelimiter_;
 228
 229    public:
 230     Generator(Source source, char delimiter, bool keepDelimiter)
 231         : source_(std::move(source)),
 232           delimiter_(delimiter),
 233           keepDelimiter_(keepDelimiter) {}
 234
 235     template <class Body>
 236     bool apply(Body&& body) const {
 237       auto splitter =
 238           streamSplitter(this->delimiter_, [this, &body](StringPiece s) {
 239             // The stream ended with a delimiter; our contract is to swallow
 240             // the final empty piece.
 241             if (s.empty()) {
 242               return true;
 243             }
 244             if (s.back() != this->delimiter_) {
 245               return body(s);
 246             }
 247             if (!keepDelimiter_) {
 248               s.pop_back(); // Remove the 1-character delimiter
 249             }
 250             return body(s);
 251           });
 252       if (!source_.apply(splitter)) {
 253         return false;
 254       }
 255       return splitter.flush();
 256     }
 257
 258     static constexpr bool infinite = Source::infinite;
 259   };
 260
 261   template<class Source,
 262            class Value,
 263            class Gen = Generator<Source>>
 264   Gen compose(GenImpl<Value, Source>&& source) const {
 265     return Gen(std::move(source.self()), delimiter_, keepDelimiter_);
 266   }
 267
 268   template<class Source,
 269            class Value,
 270            class Gen = Generator<Source>>
 271   Gen compose(const GenImpl<Value, Source>& source) const {
 272     return Gen(source.self(), delimiter_, keepDelimiter_);
 273   }
 274 };
 275
 276 template <class DelimiterType = char>
 277 class SplitStringSource
 278     : public GenImpl<StringPiece, SplitStringSource<DelimiterType>> {
 279   StringPiece source_;
 280   DelimiterType delimiter_;
 281  public:
 282   SplitStringSource(const StringPiece source,
 283                     DelimiterType delimiter)
 284     : source_(source)
 285     , delimiter_(std::move(delimiter)) { }
 286
 287   template <class Body>
 288   bool apply(Body&& body) const {
 289     StringPiece rest(source_);
 290     StringPiece prefix;
 291     while (size_t delim_len = splitPrefix(rest, prefix, this->delimiter_)) {
 292       prefix.subtract(delim_len);  // Remove the delimiter
 293       if (!body(prefix)) {
 294         return false;
 295       }
 296     }
 297     if (!rest.empty()) {
 298       if (!body(rest)) {
 299         return false;
 300       }
 301     }
 302     return true;
 303   }
 304 };
 305
 306 /**
 307  * Unsplit - For joining tokens from a generator into a string.  This is
 308  * the inverse of `split` above.
 309  *
 310  * This type is primarily used through the 'unsplit' function.
 311  */
 312 template<class Delimiter,
 313          class Output>
 314 class Unsplit : public Operator<Unsplit<Delimiter, Output>> {
 315   Delimiter delimiter_;
 316  public:
 317   explicit Unsplit(const Delimiter& delimiter)
 318     : delimiter_(delimiter) {
 319   }
 320
 321   template<class Source,
 322            class Value>
 323   Output compose(const GenImpl<Value, Source>& source) const {
 324     Output outputBuffer;
 325     UnsplitBuffer<Delimiter, Output> unsplitter(delimiter_, &outputBuffer);
 326     unsplitter.compose(source);
 327     return outputBuffer;
 328   }
 329 };
 330
 331 /**
 332  * UnsplitBuffer - For joining tokens from a generator into a string,
 333  * and inserting them into a custom buffer.
 334  *
 335  * This type is primarily used through the 'unsplit' function.
 336  */
 337 template<class Delimiter,
 338          class OutputBuffer>
 339 class UnsplitBuffer : public Operator<UnsplitBuffer<Delimiter, OutputBuffer>> {
 340   Delimiter delimiter_;
 341   OutputBuffer* outputBuffer_;
 342  public:
 343   UnsplitBuffer(const Delimiter& delimiter, OutputBuffer* outputBuffer)
 344     : delimiter_(delimiter)
 345     , outputBuffer_(outputBuffer) {
 346     CHECK(outputBuffer);
 347   }
 348
 349   template<class Source,
 350            class Value>
 351   void compose(const GenImpl<Value, Source>& source) const {
 352     // If the output buffer is empty, we skip inserting the delimiter for the
 353     // first element.
 354     bool skipDelim = outputBuffer_->empty();
 355     source | [&](Value v) {
 356       if (skipDelim) {
 357         skipDelim = false;
 358         toAppend(std::forward<Value>(v), outputBuffer_);
 359       } else {
 360         toAppend(delimiter_, std::forward<Value>(v), outputBuffer_);
 361       }
 362     };
 363   }
 364 };
 365
 366
 367 /**
 368  * Hack for static for-like constructs
 369  */
 370 template<class Target, class=void>
 371 inline Target passthrough(Target target) { return target; }
 372
 373 FOLLY_PUSH_WARNING
 374 #ifdef __clang__
 375 // Clang isn't happy with eatField() hack below.
 376 #pragma GCC diagnostic ignored "-Wreturn-stack-address"
 377 #endif  // __clang__
 378
 379 /**
 380  * ParseToTuple - For splitting a record and immediatlely converting it to a
 381  * target tuple type. Primary used through the 'eachToTuple' helper, like so:
 382  *
 383  *  auto config
 384  *    = split("1:a 2:b", ' ')
 385  *    | eachToTuple<int, string>()
 386  *    | as<vector<tuple<int, string>>>();
 387  *
 388  */
 389 template<class TargetContainer,
 390          class Delimiter,
 391          class... Targets>
 392 class SplitTo {
 393   Delimiter delimiter_;
 394  public:
 395   explicit SplitTo(Delimiter delimiter)
 396     : delimiter_(delimiter) {}
 397
 398   TargetContainer operator()(StringPiece line) const {
 399     int i = 0;
 400     StringPiece fields[sizeof...(Targets)];
 401     // HACK(tjackson): Used for referencing fields[] corresponding to variadic
 402     // template parameters.
 403     auto eatField = [&]() -> StringPiece& { return fields[i++]; };
 404     if (!split(delimiter_,
 405                line,
 406                detail::passthrough<StringPiece&, Targets>(eatField())...)) {
 407       throw std::runtime_error("field count mismatch");
 408     }
 409     i = 0;
 410     return TargetContainer(To<Targets>()(eatField())...);
 411   }
 412 };
 413
 414 FOLLY_POP_WARNING
 415
 416 } // namespace detail
 417
 418 } // namespace gen
 419 } // namespace folly