string-tree.h

// Copyright (c) 2013, Kenton Varda <temporal@gmail.com>
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this
//    list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright notice,
//    this list of conditions and the following disclaimer in the documentation
//    and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
// ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#ifndef KJ_STRING_TREE_H_
#define KJ_STRING_TREE_H_

#include "string.h"

namespace kj {

class StringTree {
  // A long string, represented internally as a tree of strings.  This data structure is like a
  // String, but optimized for concatenation and iteration at the expense of seek time.  The
  // structure is intended to be used for building large text blobs from many small pieces, where
  // repeatedly concatenating smaller strings into larger ones would waste copies.  This structure
  // is NOT intended for use cases requiring random access or computing substrings.  For those,
  // you should use a Rope, which is a much more complicated data structure.
  //
  // The proper way to construct a StringTree is via kj::strTree(...), which works just like
  // kj::str(...) but returns a StringTree rather than a String.
  //
  // KJ_STRINGIFY() functions that construct large strings from many smaller strings are encouraged
  // to return StringTree rather than a flat char container.

public:
  inline StringTree(): size_(0) {}
  inline StringTree(String&& text): size_(text.size()), text(kj::mv(text)) {}

  StringTree(Array<StringTree>&& pieces, StringPtr delim);
  // Build a StringTree by concatenating the given pieces, delimited by the given delimiter
  // (e.g. ", ").

  inline size_t size() const { return size_; }

  template <typename Func>
  void visit(Func&& func) const;

  String flatten() const;
  // Return the contents as a string.

  // TODO(someday):  flatten() when *this is an rvalue and when branches.size() == 0 could simply
  //   return `kj::mv(text)`.  Requires reference qualifiers (Clang 3.3 / GCC 4.8).

  void flattenTo(char* __restrict__ target) const;
  // Copy the contents to the given character array.  Does not add a NUL terminator.

private:
  size_t size_;
  String text;

  struct Branch;
  Array<Branch> branches;  // In order.

  inline void fill(char* pos, size_t branchIndex);
  template <typename First, typename... Rest>
  void fill(char* pos, size_t branchIndex, First&& first, Rest&&... rest);
  template <typename... Rest>
  void fill(char* pos, size_t branchIndex, StringTree&& first, Rest&&... rest);
  template <typename... Rest>
  void fill(char* pos, size_t branchIndex, Array<char>&& first, Rest&&... rest);
  template <typename... Rest>
  void fill(char* pos, size_t branchIndex, String&& first, Rest&&... rest);

  template <typename... Params>
  static StringTree concat(Params&&... params);
  static StringTree&& concat(StringTree&& param) { return kj::mv(param); }

  template <typename T>
  static inline size_t flatSize(const T& t) { return t.size(); }
  static inline size_t flatSize(String&& s) { return 0; }
  static inline size_t flatSize(StringTree&& s) { return 0; }

  template <typename T>
  static inline size_t branchCount(const T& t) { return 0; }
  static inline size_t branchCount(String&& s) { return 1; }
  static inline size_t branchCount(StringTree&& s) { return 1; }

  template <typename... Params>
  friend StringTree strTree(Params&&... params);
};

inline StringTree&& KJ_STRINGIFY(StringTree&& tree) { return kj::mv(tree); }
inline const StringTree& KJ_STRINGIFY(const StringTree& tree) { return tree; }

inline StringTree KJ_STRINGIFY(Array<StringTree>&& trees) { return StringTree(kj::mv(trees), ""); }

template <typename... Params>
StringTree strTree(Params&&... params);
// Build a StringTree by stringifying the given parameters and concatenating the results.
// If any of the parameters stringify to StringTree rvalues, they will be incorporated as
// branches to avoid a copy.

// =======================================================================================
// Inline implementation details

namespace _ {  // private

template <typename... Rest>
char* fill(char* __restrict__ target, const StringTree& first, Rest&&... rest) {
  // Make str() work with stringifiers that return StringTree by patching fill().

  first.flattenTo(target);
  return fill(target + first.size(), kj::fwd<Rest>(rest)...);
}

template <typename T> constexpr bool isStringTree() { return false; }
template <> constexpr bool isStringTree<StringTree>() { return true; }

inline StringTree&& toStringTreeOrCharSequnece(StringTree&& tree) { return kj::mv(tree); }
inline StringTree toStringTreeOrCharSequnece(String&& str) { return StringTree(kj::mv(str)); }

template <typename T>
inline auto toStringTreeOrCharSequnece(T&& value)
    -> decltype(toCharSequence(kj::fwd<T>(value))) {
  static_assert(!isStringTree<Decay<T>>(),
      "When passing a StringTree into kj::strTree(), either pass it by rvalue "
      "(use kj::mv(value)) or explicitly call value.flatten() to make a copy.");

  return toCharSequence(kj::fwd<T>(value));
}

}  // namespace _ (private)

struct StringTree::Branch {
  size_t index;
  // Index in `text` where this branch should be inserted.

  StringTree content;
};

template <typename Func>
void StringTree::visit(Func&& func) const {
  size_t pos = 0;
  for (auto& branch: branches) {
    if (branch.index > pos) {
      func(text.slice(pos, branch.index));
      pos = branch.index;
    }
    branch.content.visit(func);
  }
  if (text.size() > pos) {
    func(text.slice(pos, text.size()));
  }
}

inline void StringTree::fill(char* pos, size_t branchIndex) {
  KJ_IREQUIRE(pos == text.end() && branchIndex == branches.size(),
              kj::str(text.end() - pos, ' ', branches.size() - branchIndex).cStr());
}

template <typename First, typename... Rest>
void StringTree::fill(char* pos, size_t branchIndex, First&& first, Rest&&... rest) {
  pos = _::fill(pos, kj::fwd<First>(first));
  fill(pos, branchIndex, kj::fwd<Rest>(rest)...);
}

template <typename... Rest>
void StringTree::fill(char* pos, size_t branchIndex, StringTree&& first, Rest&&... rest) {
  branches[branchIndex].index = pos - text.begin();
  branches[branchIndex].content = kj::mv(first);
  fill(pos, branchIndex + 1, kj::fwd<Rest>(rest)...);
}

template <typename... Rest>
void StringTree::fill(char* pos, size_t branchIndex, String&& first, Rest&&... rest) {
  branches[branchIndex].index = pos - text.begin();
  branches[branchIndex].content = StringTree(kj::mv(first));
  fill(pos, branchIndex + 1, kj::fwd<Rest>(rest)...);
}

template <typename... Params>
StringTree StringTree::concat(Params&&... params) {
  StringTree result;
  result.size_ = _::sum({params.size()...});
  result.text = heapString(
      _::sum({StringTree::flatSize(kj::fwd<Params>(params))...}));
  result.branches = heapArray<StringTree::Branch>(
      _::sum({StringTree::branchCount(kj::fwd<Params>(params))...}));
  result.fill(result.text.begin(), 0, kj::fwd<Params>(params)...);
  return result;
}

template <typename... Params>
StringTree strTree(Params&&... params) {
  return StringTree::concat(_::toStringTreeOrCharSequnece(kj::fwd<Params>(params))...);
}

}  // namespace kj

#endif  // KJ_STRING_TREE_H_