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   bool keepDelimiter_;
 217
 218  public:
 219   explicit StringResplitter(char delimiter, bool keepDelimiter = false)
 220       : delimiter_(delimiter), keepDelimiter_(keepDelimiter) {}
 221
 222   template <class Source>
 223   class Generator : public GenImpl<StringPiece, Generator<Source>> {
 224     Source source_;
 225     char delimiter_;
 226     bool keepDelimiter_;
 227
 228    public:
 229     Generator(Source source, char delimiter, bool keepDelimiter)
 230         : source_(std::move(source)),
 231           delimiter_(delimiter),
 232           keepDelimiter_(keepDelimiter) {}
 233
 234     template <class Body>
 235     bool apply(Body&& body) const {
 236       auto splitter =
 237           streamSplitter(this->delimiter_, [this, &body](StringPiece s) {
 238             // The stream ended with a delimiter; our contract is to swallow
 239             // the final empty piece.
 240             if (s.empty()) {
 241               return true;
 242             }
 243             if (s.back() != this->delimiter_) {
 244               return body(s);
 245             }
 246             if (!keepDelimiter_) {
 247               s.pop_back(); // Remove the 1-character delimiter
 248             }
 249             return body(s);
 250           });
 251       if (!source_.apply(splitter)) {
 252         return false;
 253       }
 254       return splitter.flush();
 255     }
 256
 257     static constexpr bool infinite = Source::infinite;
 258   };
 259
 260   template<class Source,
 261            class Value,
 262            class Gen = Generator<Source>>
 263   Gen compose(GenImpl<Value, Source>&& source) const {
 264     return Gen(std::move(source.self()), delimiter_, keepDelimiter_);
 265   }
 266
 267   template<class Source,
 268            class Value,
 269            class Gen = Generator<Source>>
 270   Gen compose(const GenImpl<Value, Source>& source) const {
 271     return Gen(source.self(), delimiter_, keepDelimiter_);
 272   }
 273 };
 274
 275 template <class DelimiterType = char>
 276 class SplitStringSource
 277     : public GenImpl<StringPiece, SplitStringSource<DelimiterType>> {
 278   StringPiece source_;
 279   DelimiterType delimiter_;
 280  public:
 281   SplitStringSource(const StringPiece source,
 282                     DelimiterType delimiter)
 283     : source_(source)
 284     , delimiter_(std::move(delimiter)) { }
 285
 286   template <class Body>
 287   bool apply(Body&& body) const {
 288     StringPiece rest(source_);
 289     StringPiece prefix;
 290     while (size_t delim_len = splitPrefix(rest, prefix, this->delimiter_)) {
 291       prefix.subtract(delim_len);  // Remove the delimiter
 292       if (!body(prefix)) {
 293         return false;
 294       }
 295     }
 296     if (!rest.empty()) {
 297       if (!body(rest)) {
 298         return false;
 299       }
 300     }
 301     return true;
 302   }
 303 };
 304
 305 /**
 306  * Unsplit - For joining tokens from a generator into a string.  This is
 307  * the inverse of `split` above.
 308  *
 309  * This type is primarily used through the 'unsplit' function.
 310  */
 311 template<class Delimiter,
 312          class Output>
 313 class Unsplit : public Operator<Unsplit<Delimiter, Output>> {
 314   Delimiter delimiter_;
 315  public:
 316   explicit Unsplit(const Delimiter& delimiter)
 317     : delimiter_(delimiter) {
 318   }
 319
 320   template<class Source,
 321            class Value>
 322   Output compose(const GenImpl<Value, Source>& source) const {
 323     Output outputBuffer;
 324     UnsplitBuffer<Delimiter, Output> unsplitter(delimiter_, &outputBuffer);
 325     unsplitter.compose(source);
 326     return outputBuffer;
 327   }
 328 };
 329
 330 /**
 331  * UnsplitBuffer - For joining tokens from a generator into a string,
 332  * and inserting them into a custom buffer.
 333  *
 334  * This type is primarily used through the 'unsplit' function.
 335  */
 336 template<class Delimiter,
 337          class OutputBuffer>
 338 class UnsplitBuffer : public Operator<UnsplitBuffer<Delimiter, OutputBuffer>> {
 339   Delimiter delimiter_;
 340   OutputBuffer* outputBuffer_;
 341  public:
 342   UnsplitBuffer(const Delimiter& delimiter, OutputBuffer* outputBuffer)
 343     : delimiter_(delimiter)
 344     , outputBuffer_(outputBuffer) {
 345     CHECK(outputBuffer);
 346   }
 347
 348   template<class Source,
 349            class Value>
 350   void compose(const GenImpl<Value, Source>& source) const {
 351     // If the output buffer is empty, we skip inserting the delimiter for the
 352     // first element.
 353     bool skipDelim = outputBuffer_->empty();
 354     source | [&](Value v) {
 355       if (skipDelim) {
 356         skipDelim = false;
 357         toAppend(std::forward<Value>(v), outputBuffer_);
 358       } else {
 359         toAppend(delimiter_, std::forward<Value>(v), outputBuffer_);
 360       }
 361     };
 362   }
 363 };
 364
 365
 366 /**
 367  * Hack for static for-like constructs
 368  */
 369 template<class Target, class=void>
 370 inline Target passthrough(Target target) { return target; }
 371
 372 #pragma GCC diagnostic push
 373 #ifdef __clang__
 374 // Clang isn't happy with eatField() hack below.
 375 #pragma GCC diagnostic ignored "-Wreturn-stack-address"
 376 #endif  // __clang__
 377
 378 /**
 379  * ParseToTuple - For splitting a record and immediatlely converting it to a
 380  * target tuple type. Primary used through the 'eachToTuple' helper, like so:
 381  *
 382  *  auto config
 383  *    = split("1:a 2:b", ' ')
 384  *    | eachToTuple<int, string>()
 385  *    | as<vector<tuple<int, string>>>();
 386  *
 387  */
 388 template<class TargetContainer,
 389          class Delimiter,
 390          class... Targets>
 391 class SplitTo {
 392   Delimiter delimiter_;
 393  public:
 394   explicit SplitTo(Delimiter delimiter)
 395     : delimiter_(delimiter) {}
 396
 397   TargetContainer operator()(StringPiece line) const {
 398     int i = 0;
 399     StringPiece fields[sizeof...(Targets)];
 400     // HACK(tjackson): Used for referencing fields[] corresponding to variadic
 401     // template parameters.
 402     auto eatField = [&]() -> StringPiece& { return fields[i++]; };
 403     if (!split(delimiter_,
 404                line,
 405                detail::passthrough<StringPiece&, Targets>(eatField())...)) {
 406       throw std::runtime_error("field count mismatch");
 407     }
 408     i = 0;
 409     return TargetContainer(To<Targets>()(eatField())...);
 410   }
 411 };
 412
 413 #pragma GCC diagnostic pop
 414
 415 } // namespace detail
 416
 417 } // namespace gen
 418 } // namespace folly