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