cannam@135: // Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
cannam@135: // Licensed under the MIT License:
cannam@135: //
cannam@135: // Permission is hereby granted, free of charge, to any person obtaining a copy
cannam@135: // of this software and associated documentation files (the "Software"), to deal
cannam@135: // in the Software without restriction, including without limitation the rights
cannam@135: // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
cannam@135: // copies of the Software, and to permit persons to whom the Software is
cannam@135: // furnished to do so, subject to the following conditions:
cannam@135: //
cannam@135: // The above copyright notice and this permission notice shall be included in
cannam@135: // all copies or substantial portions of the Software.
cannam@135: //
cannam@135: // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
cannam@135: // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
cannam@135: // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
cannam@135: // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
cannam@135: // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
cannam@135: // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
cannam@135: // THE SOFTWARE.
cannam@135: 
cannam@135: #ifndef KJ_STRING_TREE_H_
cannam@135: #define KJ_STRING_TREE_H_
cannam@135: 
cannam@135: #if defined(__GNUC__) && !KJ_HEADER_WARNINGS
cannam@135: #pragma GCC system_header
cannam@135: #endif
cannam@135: 
cannam@135: #include "string.h"
cannam@135: 
cannam@135: namespace kj {
cannam@135: 
cannam@135: class StringTree {
cannam@135:   // A long string, represented internally as a tree of strings.  This data structure is like a
cannam@135:   // String, but optimized for concatenation and iteration at the expense of seek time.  The
cannam@135:   // structure is intended to be used for building large text blobs from many small pieces, where
cannam@135:   // repeatedly concatenating smaller strings into larger ones would waste copies.  This structure
cannam@135:   // is NOT intended for use cases requiring random access or computing substrings.  For those,
cannam@135:   // you should use a Rope, which is a much more complicated data structure.
cannam@135:   //
cannam@135:   // The proper way to construct a StringTree is via kj::strTree(...), which works just like
cannam@135:   // kj::str(...) but returns a StringTree rather than a String.
cannam@135:   //
cannam@135:   // KJ_STRINGIFY() functions that construct large strings from many smaller strings are encouraged
cannam@135:   // to return StringTree rather than a flat char container.
cannam@135: 
cannam@135: public:
cannam@135:   inline StringTree(): size_(0) {}
cannam@135:   inline StringTree(String&& text): size_(text.size()), text(kj::mv(text)) {}
cannam@135: 
cannam@135:   StringTree(Array<StringTree>&& pieces, StringPtr delim);
cannam@135:   // Build a StringTree by concatenating the given pieces, delimited by the given delimiter
cannam@135:   // (e.g. ", ").
cannam@135: 
cannam@135:   inline size_t size() const { return size_; }
cannam@135: 
cannam@135:   template <typename Func>
cannam@135:   void visit(Func&& func) const;
cannam@135: 
cannam@135:   String flatten() const;
cannam@135:   // Return the contents as a string.
cannam@135: 
cannam@135:   // TODO(someday):  flatten() when *this is an rvalue and when branches.size() == 0 could simply
cannam@135:   //   return `kj::mv(text)`.  Requires reference qualifiers (Clang 3.3 / GCC 4.8).
cannam@135: 
cannam@135:   void flattenTo(char* __restrict__ target) const;
cannam@135:   // Copy the contents to the given character array.  Does not add a NUL terminator.
cannam@135: 
cannam@135: private:
cannam@135:   size_t size_;
cannam@135:   String text;
cannam@135: 
cannam@135:   struct Branch;
cannam@135:   Array<Branch> branches;  // In order.
cannam@135: 
cannam@135:   inline void fill(char* pos, size_t branchIndex);
cannam@135:   template <typename First, typename... Rest>
cannam@135:   void fill(char* pos, size_t branchIndex, First&& first, Rest&&... rest);
cannam@135:   template <typename... Rest>
cannam@135:   void fill(char* pos, size_t branchIndex, StringTree&& first, Rest&&... rest);
cannam@135:   template <typename... Rest>
cannam@135:   void fill(char* pos, size_t branchIndex, Array<char>&& first, Rest&&... rest);
cannam@135:   template <typename... Rest>
cannam@135:   void fill(char* pos, size_t branchIndex, String&& first, Rest&&... rest);
cannam@135: 
cannam@135:   template <typename... Params>
cannam@135:   static StringTree concat(Params&&... params);
cannam@135:   static StringTree&& concat(StringTree&& param) { return kj::mv(param); }
cannam@135: 
cannam@135:   template <typename T>
cannam@135:   static inline size_t flatSize(const T& t) { return t.size(); }
cannam@135:   static inline size_t flatSize(String&& s) { return 0; }
cannam@135:   static inline size_t flatSize(StringTree&& s) { return 0; }
cannam@135: 
cannam@135:   template <typename T>
cannam@135:   static inline size_t branchCount(const T& t) { return 0; }
cannam@135:   static inline size_t branchCount(String&& s) { return 1; }
cannam@135:   static inline size_t branchCount(StringTree&& s) { return 1; }
cannam@135: 
cannam@135:   template <typename... Params>
cannam@135:   friend StringTree strTree(Params&&... params);
cannam@135: };
cannam@135: 
cannam@135: inline StringTree&& KJ_STRINGIFY(StringTree&& tree) { return kj::mv(tree); }
cannam@135: inline const StringTree& KJ_STRINGIFY(const StringTree& tree) { return tree; }
cannam@135: 
cannam@135: inline StringTree KJ_STRINGIFY(Array<StringTree>&& trees) { return StringTree(kj::mv(trees), ""); }
cannam@135: 
cannam@135: template <typename... Params>
cannam@135: StringTree strTree(Params&&... params);
cannam@135: // Build a StringTree by stringifying the given parameters and concatenating the results.
cannam@135: // If any of the parameters stringify to StringTree rvalues, they will be incorporated as
cannam@135: // branches to avoid a copy.
cannam@135: 
cannam@135: // =======================================================================================
cannam@135: // Inline implementation details
cannam@135: 
cannam@135: namespace _ {  // private
cannam@135: 
cannam@135: template <typename... Rest>
cannam@135: char* fill(char* __restrict__ target, const StringTree& first, Rest&&... rest) {
cannam@135:   // Make str() work with stringifiers that return StringTree by patching fill().
cannam@135: 
cannam@135:   first.flattenTo(target);
cannam@135:   return fill(target + first.size(), kj::fwd<Rest>(rest)...);
cannam@135: }
cannam@135: 
cannam@135: template <typename T> constexpr bool isStringTree() { return false; }
cannam@135: template <> constexpr bool isStringTree<StringTree>() { return true; }
cannam@135: 
cannam@135: inline StringTree&& toStringTreeOrCharSequence(StringTree&& tree) { return kj::mv(tree); }
cannam@135: inline StringTree toStringTreeOrCharSequence(String&& str) { return StringTree(kj::mv(str)); }
cannam@135: 
cannam@135: template <typename T>
cannam@135: inline auto toStringTreeOrCharSequence(T&& value)
cannam@135:     -> decltype(toCharSequence(kj::fwd<T>(value))) {
cannam@135:   static_assert(!isStringTree<Decay<T>>(),
cannam@135:       "When passing a StringTree into kj::strTree(), either pass it by rvalue "
cannam@135:       "(use kj::mv(value)) or explicitly call value.flatten() to make a copy.");
cannam@135: 
cannam@135:   return toCharSequence(kj::fwd<T>(value));
cannam@135: }
cannam@135: 
cannam@135: }  // namespace _ (private)
cannam@135: 
cannam@135: struct StringTree::Branch {
cannam@135:   size_t index;
cannam@135:   // Index in `text` where this branch should be inserted.
cannam@135: 
cannam@135:   StringTree content;
cannam@135: };
cannam@135: 
cannam@135: template <typename Func>
cannam@135: void StringTree::visit(Func&& func) const {
cannam@135:   size_t pos = 0;
cannam@135:   for (auto& branch: branches) {
cannam@135:     if (branch.index > pos) {
cannam@135:       func(text.slice(pos, branch.index));
cannam@135:       pos = branch.index;
cannam@135:     }
cannam@135:     branch.content.visit(func);
cannam@135:   }
cannam@135:   if (text.size() > pos) {
cannam@135:     func(text.slice(pos, text.size()));
cannam@135:   }
cannam@135: }
cannam@135: 
cannam@135: inline void StringTree::fill(char* pos, size_t branchIndex) {
cannam@135:   KJ_IREQUIRE(pos == text.end() && branchIndex == branches.size(),
cannam@135:               kj::str(text.end() - pos, ' ', branches.size() - branchIndex).cStr());
cannam@135: }
cannam@135: 
cannam@135: template <typename First, typename... Rest>
cannam@135: void StringTree::fill(char* pos, size_t branchIndex, First&& first, Rest&&... rest) {
cannam@135:   pos = _::fill(pos, kj::fwd<First>(first));
cannam@135:   fill(pos, branchIndex, kj::fwd<Rest>(rest)...);
cannam@135: }
cannam@135: 
cannam@135: template <typename... Rest>
cannam@135: void StringTree::fill(char* pos, size_t branchIndex, StringTree&& first, Rest&&... rest) {
cannam@135:   branches[branchIndex].index = pos - text.begin();
cannam@135:   branches[branchIndex].content = kj::mv(first);
cannam@135:   fill(pos, branchIndex + 1, kj::fwd<Rest>(rest)...);
cannam@135: }
cannam@135: 
cannam@135: template <typename... Rest>
cannam@135: void StringTree::fill(char* pos, size_t branchIndex, String&& first, Rest&&... rest) {
cannam@135:   branches[branchIndex].index = pos - text.begin();
cannam@135:   branches[branchIndex].content = StringTree(kj::mv(first));
cannam@135:   fill(pos, branchIndex + 1, kj::fwd<Rest>(rest)...);
cannam@135: }
cannam@135: 
cannam@135: template <typename... Params>
cannam@135: StringTree StringTree::concat(Params&&... params) {
cannam@135:   StringTree result;
cannam@135:   result.size_ = _::sum({params.size()...});
cannam@135:   result.text = heapString(
cannam@135:       _::sum({StringTree::flatSize(kj::fwd<Params>(params))...}));
cannam@135:   result.branches = heapArray<StringTree::Branch>(
cannam@135:       _::sum({StringTree::branchCount(kj::fwd<Params>(params))...}));
cannam@135:   result.fill(result.text.begin(), 0, kj::fwd<Params>(params)...);
cannam@135:   return result;
cannam@135: }
cannam@135: 
cannam@135: template <typename... Params>
cannam@135: StringTree strTree(Params&&... params) {
cannam@135:   return StringTree::concat(_::toStringTreeOrCharSequence(kj::fwd<Params>(params))...);
cannam@135: }
cannam@135: 
cannam@135: }  // namespace kj
cannam@135: 
cannam@135: #endif  // KJ_STRING_TREE_H_