1// Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
2// Licensed under the MIT License:
3//
4// Permission is hereby granted, free of charge, to any person obtaining a copy
5// of this software and associated documentation files (the "Software"), to deal
6// in the Software without restriction, including without limitation the rights
7// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8// copies of the Software, and to permit persons to whom the Software is
9// furnished to do so, subject to the following conditions:
10//
11// The above copyright notice and this permission notice shall be included in
12// all copies or substantial portions of the Software.
13//
14// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20// THE SOFTWARE.
21
22#pragma once
23
24#if defined(__GNUC__) && !KJ_HEADER_WARNINGS
25#pragma GCC system_header
26#endif
27
28#include "string.h"
29
30namespace kj {
31
32class StringTree {
33 // A long string, represented internally as a tree of strings. This data structure is like a
34 // String, but optimized for concatenation and iteration at the expense of seek time. The
35 // structure is intended to be used for building large text blobs from many small pieces, where
36 // repeatedly concatenating smaller strings into larger ones would waste copies. This structure
37 // is NOT intended for use cases requiring random access or computing substrings. For those,
38 // you should use a Rope, which is a much more complicated data structure.
39 //
40 // The proper way to construct a StringTree is via kj::strTree(...), which works just like
41 // kj::str(...) but returns a StringTree rather than a String.
42 //
43 // KJ_STRINGIFY() functions that construct large strings from many smaller strings are encouraged
44 // to return StringTree rather than a flat char container.
45
46public:
47 inline StringTree(): size_(0) {}
48 inline StringTree(String&& text): size_(text.size()), text(kj::mv(text)) {}
49
50 StringTree(Array<StringTree>&& pieces, StringPtr delim);
51 // Build a StringTree by concatenating the given pieces, delimited by the given delimiter
52 // (e.g. ", ").
53
54 inline size_t size() const { return size_; }
55
56 template <typename Func>
57 void visit(Func&& func) const;
58
59 String flatten() const;
60 // Return the contents as a string.
61
62 // TODO(someday): flatten() when *this is an rvalue and when branches.size() == 0 could simply
63 // return `kj::mv(text)`. Requires reference qualifiers (Clang 3.3 / GCC 4.8).
64
65 char* flattenTo(char* __restrict__ target) const;
66 char* flattenTo(char* __restrict__ target, char* limit) const;
67 // Copy the contents to the given character array. Does not add a NUL terminator. Returns a
68 // pointer just past the end of what was filled.
69
70private:
71 size_t size_;
72 String text;
73
74 struct Branch;
75 Array<Branch> branches; // In order.
76
77 inline void fill(char* pos, size_t branchIndex);
78 template <typename First, typename... Rest>
79 void fill(char* pos, size_t branchIndex, First&& first, Rest&&... rest);
80 template <typename... Rest>
81 void fill(char* pos, size_t branchIndex, StringTree&& first, Rest&&... rest);
82 template <typename... Rest>
83 void fill(char* pos, size_t branchIndex, Array<char>&& first, Rest&&... rest);
84 template <typename... Rest>
85 void fill(char* pos, size_t branchIndex, String&& first, Rest&&... rest);
86
87 template <typename... Params>
88 static StringTree concat(Params&&... params);
89 static StringTree&& concat(StringTree&& param) { return kj::mv(param); }
90
91 template <typename T>
92 static inline size_t flatSize(const T& t) { return t.size(); }
93 static inline size_t flatSize(String&& s) { return 0; }
94 static inline size_t flatSize(StringTree&& s) { return 0; }
95
96 template <typename T>
97 static inline size_t branchCount(const T& t) { return 0; }
98 static inline size_t branchCount(String&& s) { return 1; }
99 static inline size_t branchCount(StringTree&& s) { return 1; }
100
101 template <typename... Params>
102 friend StringTree strTree(Params&&... params);
103};
104
105inline StringTree&& KJ_STRINGIFY(StringTree&& tree) { return kj::mv(tree); }
106inline const StringTree& KJ_STRINGIFY(const StringTree& tree) { return tree; }
107
108inline StringTree KJ_STRINGIFY(Array<StringTree>&& trees) { return StringTree(kj::mv(trees), ""); }
109
110template <typename... Params>
111StringTree strTree(Params&&... params);
112// Build a StringTree by stringifying the given parameters and concatenating the results.
113// If any of the parameters stringify to StringTree rvalues, they will be incorporated as
114// branches to avoid a copy.
115
116// =======================================================================================
117// Inline implementation details
118
119namespace _ { // private
120
121template <typename... Rest>
122char* fill(char* __restrict__ target, const StringTree& first, Rest&&... rest) {
123 // Make str() work with stringifiers that return StringTree by patching fill().
124
125 first.flattenTo(target);
126 return fill(target + first.size(), kj::fwd<Rest>(rest)...);
127}
128
129template <typename... Rest>
130char* fillLimited(char* __restrict__ target, char* limit, const StringTree& first, Rest&&... rest) {
131 // Make str() work with stringifiers that return StringTree by patching fill().
132
133 target = first.flattenTo(target, limit);
134 return fillLimited(target + first.size(), limit, kj::fwd<Rest>(rest)...);
135}
136
137template <typename T> constexpr bool isStringTree() { return false; }
138template <> constexpr bool isStringTree<StringTree>() { return true; }
139
140inline StringTree&& toStringTreeOrCharSequence(StringTree&& tree) { return kj::mv(tree); }
141inline StringTree toStringTreeOrCharSequence(String&& str) { return StringTree(kj::mv(str)); }
142
143template <typename T>
144inline auto toStringTreeOrCharSequence(T&& value)
145 -> decltype(toCharSequence(kj::fwd<T>(value))) {
146 static_assert(!isStringTree<Decay<T>>(),
147 "When passing a StringTree into kj::strTree(), either pass it by rvalue "
148 "(use kj::mv(value)) or explicitly call value.flatten() to make a copy.");
149
150 return toCharSequence(kj::fwd<T>(value));
151}
152
153} // namespace _ (private)
154
155struct StringTree::Branch {
156 size_t index;
157 // Index in `text` where this branch should be inserted.
158
159 StringTree content;
160};
161
162template <typename Func>
163void StringTree::visit(Func&& func) const {
164 size_t pos = 0;
165 for (auto& branch: branches) {
166 if (branch.index > pos) {
167 func(text.slice(pos, branch.index));
168 pos = branch.index;
169 }
170 branch.content.visit(func);
171 }
172 if (text.size() > pos) {
173 func(text.slice(pos, text.size()));
174 }
175}
176
177inline void StringTree::fill(char* pos, size_t branchIndex) {
178 KJ_IREQUIRE(pos == text.end() && branchIndex == branches.size(),
179 kj::str(text.end() - pos, ' ', branches.size() - branchIndex).cStr());
180}
181
182template <typename First, typename... Rest>
183void StringTree::fill(char* pos, size_t branchIndex, First&& first, Rest&&... rest) {
184 pos = _::fill(pos, kj::fwd<First>(first));
185 fill(pos, branchIndex, kj::fwd<Rest>(rest)...);
186}
187
188template <typename... Rest>
189void StringTree::fill(char* pos, size_t branchIndex, StringTree&& first, Rest&&... rest) {
190 branches[branchIndex].index = pos - text.begin();
191 branches[branchIndex].content = kj::mv(first);
192 fill(pos, branchIndex + 1, kj::fwd<Rest>(rest)...);
193}
194
195template <typename... Rest>
196void StringTree::fill(char* pos, size_t branchIndex, String&& first, Rest&&... rest) {
197 branches[branchIndex].index = pos - text.begin();
198 branches[branchIndex].content = StringTree(kj::mv(first));
199 fill(pos, branchIndex + 1, kj::fwd<Rest>(rest)...);
200}
201
202template <typename... Params>
203StringTree StringTree::concat(Params&&... params) {
204 StringTree result;
205 result.size_ = _::sum({params.size()...});
206 result.text = heapString(
207 _::sum({StringTree::flatSize(kj::fwd<Params>(params))...}));
208 result.branches = heapArray<StringTree::Branch>(
209 _::sum({StringTree::branchCount(kj::fwd<Params>(params))...}));
210 result.fill(result.text.begin(), 0, kj::fwd<Params>(params)...);
211 return result;
212}
213
214template <typename... Params>
215StringTree strTree(Params&&... params) {
216 return StringTree::concat(_::toStringTreeOrCharSequence(kj::fwd<Params>(params))...);
217}
218
219} // namespace kj
220