1 // Copyright 2021 The Abseil Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/strings/internal/cord_rep_btree_reader.h"
16
17 #include <iostream>
18 #include <random>
19 #include <string>
20 #include <vector>
21
22 #include "gmock/gmock.h"
23 #include "gtest/gtest.h"
24 #include "absl/base/config.h"
25 #include "absl/base/internal/raw_logging.h"
26 #include "absl/strings/cord.h"
27 #include "absl/strings/internal/cord_internal.h"
28 #include "absl/strings/internal/cord_rep_btree.h"
29 #include "absl/strings/internal/cord_rep_test_util.h"
30 #include "absl/strings/string_view.h"
31
32 namespace absl {
33 ABSL_NAMESPACE_BEGIN
34 namespace cord_internal {
35 namespace {
36
37 using ::testing::Eq;
38 using ::testing::IsEmpty;
39 using ::testing::Ne;
40 using ::testing::Not;
41
42 using ::absl::cordrep_testing::CordRepBtreeFromFlats;
43 using ::absl::cordrep_testing::MakeFlat;
44 using ::absl::cordrep_testing::CordToString;
45 using ::absl::cordrep_testing::CreateFlatsFromString;
46 using ::absl::cordrep_testing::CreateRandomString;
47
48 using ReadResult = CordRepBtreeReader::ReadResult;
49
TEST(CordRepBtreeReaderTest,Next)50 TEST(CordRepBtreeReaderTest, Next) {
51 constexpr size_t kChars = 3;
52 const size_t cap = CordRepBtree::kMaxCapacity;
53 int counts[] = {1, 2, cap, cap * cap, cap * cap + 1, cap * cap * 2 + 17};
54
55 for (int count : counts) {
56 std::string data = CreateRandomString(count * kChars);
57 std::vector<CordRep*> flats = CreateFlatsFromString(data, kChars);
58 CordRepBtree* node = CordRepBtreeFromFlats(flats);
59
60 CordRepBtreeReader reader;
61 absl::string_view chunk = reader.Init(node);
62 EXPECT_THAT(chunk, Eq(data.substr(0, chunk.length())));
63
64 size_t consumed = chunk.length();
65 EXPECT_THAT(reader.consumed(), Eq(consumed));
66
67 while (consumed < data.length()) {
68 chunk = reader.Next();
69 EXPECT_THAT(chunk, Eq(data.substr(consumed, chunk.length())));
70
71 consumed += chunk.length();
72 EXPECT_THAT(reader.consumed(), Eq(consumed));
73 }
74
75 EXPECT_THAT(consumed, Eq(data.length()));
76 EXPECT_THAT(reader.consumed(), Eq(data.length()));
77
78 CordRep::Unref(node);
79 }
80 }
81
TEST(CordRepBtreeReaderTest,Skip)82 TEST(CordRepBtreeReaderTest, Skip) {
83 constexpr size_t kChars = 3;
84 const size_t cap = CordRepBtree::kMaxCapacity;
85 int counts[] = {1, 2, cap, cap * cap, cap * cap + 1, cap * cap * 2 + 17};
86
87 for (int count : counts) {
88 std::string data = CreateRandomString(count * kChars);
89 std::vector<CordRep*> flats = CreateFlatsFromString(data, kChars);
90 CordRepBtree* node = CordRepBtreeFromFlats(flats);
91
92 for (size_t skip1 = 0; skip1 < data.length() - kChars; ++skip1) {
93 for (size_t skip2 = 0; skip2 < data.length() - kChars; ++skip2) {
94 CordRepBtreeReader reader;
95 absl::string_view chunk = reader.Init(node);
96 size_t consumed = chunk.length();
97
98 chunk = reader.Skip(skip1);
99 ASSERT_THAT(chunk, Eq(data.substr(consumed + skip1, chunk.length())));
100 consumed += chunk.length() + skip1;
101 ASSERT_THAT(reader.consumed(), Eq(consumed));
102
103 if (consumed >= data.length()) continue;
104
105 size_t skip = std::min(data.length() - consumed - 1, skip2);
106 chunk = reader.Skip(skip);
107 ASSERT_THAT(chunk, Eq(data.substr(consumed + skip, chunk.length())));
108 }
109 }
110
111 CordRep::Unref(node);
112 }
113 }
114
TEST(CordRepBtreeReaderTest,SkipBeyondLength)115 TEST(CordRepBtreeReaderTest, SkipBeyondLength) {
116 CordRepBtree* tree = CordRepBtree::Create(MakeFlat("abc"));
117 tree = CordRepBtree::Append(tree, MakeFlat("def"));
118 CordRepBtreeReader reader;
119 reader.Init(tree);
120 EXPECT_THAT(reader.Skip(100), IsEmpty());
121 EXPECT_THAT(reader.consumed(), Eq(6));
122 CordRep::Unref(tree);
123 }
124
TEST(CordRepBtreeReaderTest,Seek)125 TEST(CordRepBtreeReaderTest, Seek) {
126 constexpr size_t kChars = 3;
127 const size_t cap = CordRepBtree::kMaxCapacity;
128 int counts[] = {1, 2, cap, cap * cap, cap * cap + 1, cap * cap * 2 + 17};
129
130 for (int count : counts) {
131 std::string data = CreateRandomString(count * kChars);
132 std::vector<CordRep*> flats = CreateFlatsFromString(data, kChars);
133 CordRepBtree* node = CordRepBtreeFromFlats(flats);
134
135 for (size_t seek = 0; seek < data.length() - 1; ++seek) {
136 CordRepBtreeReader reader;
137 reader.Init(node);
138 absl::string_view chunk = reader.Seek(seek);
139 ASSERT_THAT(chunk, Not(IsEmpty()));
140 ASSERT_THAT(chunk, Eq(data.substr(seek, chunk.length())));
141 ASSERT_THAT(reader.consumed(), Eq(seek + chunk.length()));
142 }
143
144 CordRep::Unref(node);
145 }
146 }
147
TEST(CordRepBtreeReaderTest,SeekBeyondLength)148 TEST(CordRepBtreeReaderTest, SeekBeyondLength) {
149 CordRepBtree* tree = CordRepBtree::Create(MakeFlat("abc"));
150 tree = CordRepBtree::Append(tree, MakeFlat("def"));
151 CordRepBtreeReader reader;
152 reader.Init(tree);
153 EXPECT_THAT(reader.Seek(6), IsEmpty());
154 EXPECT_THAT(reader.consumed(), Eq(6));
155 EXPECT_THAT(reader.Seek(100), IsEmpty());
156 EXPECT_THAT(reader.consumed(), Eq(6));
157 CordRep::Unref(tree);
158 }
159
TEST(CordRepBtreeReaderTest,Read)160 TEST(CordRepBtreeReaderTest, Read) {
161 std::string data = "abcdefghijklmno";
162 std::vector<CordRep*> flats = CreateFlatsFromString(data, 5);
163 CordRepBtree* node = CordRepBtreeFromFlats(flats);
164
165 CordRep* tree;
166 CordRepBtreeReader reader;
167 absl::string_view chunk;
168
169 // Read zero bytes
170 chunk = reader.Init(node);
171 chunk = reader.Read(0, chunk.length(), tree);
172 EXPECT_THAT(tree, Eq(nullptr));
173 EXPECT_THAT(chunk, Eq("abcde"));
174 EXPECT_THAT(reader.consumed(), Eq(5));
175 EXPECT_THAT(reader.Next(), Eq("fghij"));
176
177 // Read in full
178 chunk = reader.Init(node);
179 chunk = reader.Read(15, chunk.length(), tree);
180 EXPECT_THAT(tree, Ne(nullptr));
181 EXPECT_THAT(CordToString(tree), Eq("abcdefghijklmno"));
182 EXPECT_THAT(chunk, Eq(""));
183 EXPECT_THAT(reader.consumed(), Eq(15));
184 CordRep::Unref(tree);
185
186 // Read < chunk bytes
187 chunk = reader.Init(node);
188 chunk = reader.Read(3, chunk.length(), tree);
189 ASSERT_THAT(tree, Ne(nullptr));
190 EXPECT_THAT(CordToString(tree), Eq("abc"));
191 EXPECT_THAT(chunk, Eq("de"));
192 EXPECT_THAT(reader.consumed(), Eq(5));
193 EXPECT_THAT(reader.Next(), Eq("fghij"));
194 CordRep::Unref(tree);
195
196 // Read < chunk bytes at offset
197 chunk = reader.Init(node);
198 chunk = reader.Read(2, chunk.length() - 2, tree);
199 ASSERT_THAT(tree, Ne(nullptr));
200 EXPECT_THAT(CordToString(tree), Eq("cd"));
201 EXPECT_THAT(chunk, Eq("e"));
202 EXPECT_THAT(reader.consumed(), Eq(5));
203 EXPECT_THAT(reader.Next(), Eq("fghij"));
204 CordRep::Unref(tree);
205
206 // Read from consumed chunk
207 chunk = reader.Init(node);
208 chunk = reader.Read(3, 0, tree);
209 ASSERT_THAT(tree, Ne(nullptr));
210 EXPECT_THAT(CordToString(tree), Eq("fgh"));
211 EXPECT_THAT(chunk, Eq("ij"));
212 EXPECT_THAT(reader.consumed(), Eq(10));
213 EXPECT_THAT(reader.Next(), Eq("klmno"));
214 CordRep::Unref(tree);
215
216 // Read across chunks
217 chunk = reader.Init(node);
218 chunk = reader.Read(12, chunk.length() - 2, tree);
219 ASSERT_THAT(tree, Ne(nullptr));
220 EXPECT_THAT(CordToString(tree), Eq("cdefghijklmn"));
221 EXPECT_THAT(chunk, Eq("o"));
222 EXPECT_THAT(reader.consumed(), Eq(15));
223 CordRep::Unref(tree);
224
225 // Read across chunks landing on exact edge boundary
226 chunk = reader.Init(node);
227 chunk = reader.Read(10 - 2, chunk.length() - 2, tree);
228 ASSERT_THAT(tree, Ne(nullptr));
229 EXPECT_THAT(CordToString(tree), Eq("cdefghij"));
230 EXPECT_THAT(chunk, Eq("klmno"));
231 EXPECT_THAT(reader.consumed(), Eq(15));
232 CordRep::Unref(tree);
233
234 CordRep::Unref(node);
235 }
236
TEST(CordRepBtreeReaderTest,ReadExhaustive)237 TEST(CordRepBtreeReaderTest, ReadExhaustive) {
238 constexpr size_t kChars = 3;
239 const size_t cap = CordRepBtree::kMaxCapacity;
240 int counts[] = {1, 2, cap, cap * cap + 1, cap * cap * cap * 2 + 17};
241
242 for (int count : counts) {
243 std::string data = CreateRandomString(count * kChars);
244 std::vector<CordRep*> flats = CreateFlatsFromString(data, kChars);
245 CordRepBtree* node = CordRepBtreeFromFlats(flats);
246
247 for (size_t read_size : {kChars - 1, kChars, kChars + 7, cap * cap}) {
248 CordRepBtreeReader reader;
249 absl::string_view chunk = reader.Init(node);
250
251 // `consumed` tracks the end of last consumed chunk which is the start of
252 // the next chunk: we always read with `chunk_size = chunk.length()`.
253 size_t consumed = 0;
254 size_t remaining = data.length();
255 while (remaining > 0) {
256 CordRep* tree;
257 size_t n = (std::min)(remaining, read_size);
258 chunk = reader.Read(n, chunk.length(), tree);
259 EXPECT_THAT(tree, Ne(nullptr));
260 if (tree) {
261 EXPECT_THAT(CordToString(tree), Eq(data.substr(consumed, n)));
262 CordRep::Unref(tree);
263 }
264
265 consumed += n;
266 remaining -= n;
267 EXPECT_THAT(reader.consumed(), Eq(consumed + chunk.length()));
268
269 if (remaining > 0) {
270 ASSERT_FALSE(chunk.empty());
271 ASSERT_THAT(chunk, Eq(data.substr(consumed, chunk.length())));
272 } else {
273 ASSERT_TRUE(chunk.empty()) << chunk;
274 }
275 }
276 }
277
278 CordRep::Unref(node);
279 }
280 }
281
282 } // namespace
283 } // namespace cord_internal
284 ABSL_NAMESPACE_END
285 } // namespace absl
286