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_consume.h"
16
17 #include <functional>
18 #include <utility>
19
20 #include "gmock/gmock.h"
21 #include "gtest/gtest.h"
22 #include "absl/strings/internal/cord_internal.h"
23 #include "absl/strings/internal/cord_rep_flat.h"
24
25 namespace absl {
26 ABSL_NAMESPACE_BEGIN
27 namespace cord_internal {
28 namespace {
29
30 using testing::InSequence;
31 using testing::MockFunction;
32
33 // Returns the depth of a node
Depth(const CordRep * rep)34 int Depth(const CordRep* rep) {
35 return (rep->tag == CONCAT) ? rep->concat()->depth() : 0;
36 }
37
38 // Creates a concatenation of the specified nodes.
CreateConcat(CordRep * left,CordRep * right)39 CordRepConcat* CreateConcat(CordRep* left, CordRep* right) {
40 auto* concat = new CordRepConcat();
41 concat->tag = CONCAT;
42 concat->left = left;
43 concat->right = right;
44 concat->length = left->length + right->length;
45 concat->set_depth(1 + (std::max)(Depth(left), Depth(right)));
46 return concat;
47 }
48
49 // Creates a flat with the length set to `length`
CreateFlatWithLength(size_t length)50 CordRepFlat* CreateFlatWithLength(size_t length) {
51 auto* flat = CordRepFlat::New(length);
52 flat->length = length;
53 return flat;
54 }
55
56 // Creates a substring node on the specified child.
CreateSubstring(CordRep * child,size_t start,size_t length)57 CordRepSubstring* CreateSubstring(CordRep* child, size_t start, size_t length) {
58 auto* rep = new CordRepSubstring();
59 rep->length = length;
60 rep->tag = SUBSTRING;
61 rep->start = start;
62 rep->child = child;
63 return rep;
64 }
65
66 // Flats we use in the tests
67 CordRep* flat[6];
68
69 // Creates a test tree
CreateTestTree()70 CordRep* CreateTestTree() {
71 flat[0] = CreateFlatWithLength(1);
72 flat[1] = CreateFlatWithLength(7);
73 CordRepConcat* left = CreateConcat(flat[0], CreateSubstring(flat[1], 2, 4));
74
75 flat[2] = CreateFlatWithLength(9);
76 flat[3] = CreateFlatWithLength(13);
77 CordRepConcat* right1 = CreateConcat(flat[2], flat[3]);
78
79 flat[4] = CreateFlatWithLength(15);
80 flat[5] = CreateFlatWithLength(19);
81 CordRepConcat* right2 = CreateConcat(flat[4], flat[5]);
82
83 CordRepConcat* right = CreateConcat(right1, CreateSubstring(right2, 5, 17));
84 return CreateConcat(left, right);
85 }
86
TEST(CordRepConsumeTest,Consume)87 TEST(CordRepConsumeTest, Consume) {
88 InSequence in_sequence;
89 CordRep* tree = CreateTestTree();
90 MockFunction<void(CordRep*, size_t, size_t)> consume;
91 EXPECT_CALL(consume, Call(flat[0], 0, 1));
92 EXPECT_CALL(consume, Call(flat[1], 2, 4));
93 EXPECT_CALL(consume, Call(flat[2], 0, 9));
94 EXPECT_CALL(consume, Call(flat[3], 0, 13));
95 EXPECT_CALL(consume, Call(flat[4], 5, 10));
96 EXPECT_CALL(consume, Call(flat[5], 0, 7));
97 Consume(tree, consume.AsStdFunction());
98 for (CordRep* rep : flat) {
99 EXPECT_TRUE(rep->refcount.IsOne());
100 CordRep::Unref(rep);
101 }
102 }
103
TEST(CordRepConsumeTest,ConsumeShared)104 TEST(CordRepConsumeTest, ConsumeShared) {
105 InSequence in_sequence;
106 CordRep* tree = CreateTestTree();
107 MockFunction<void(CordRep*, size_t, size_t)> consume;
108 EXPECT_CALL(consume, Call(flat[0], 0, 1));
109 EXPECT_CALL(consume, Call(flat[1], 2, 4));
110 EXPECT_CALL(consume, Call(flat[2], 0, 9));
111 EXPECT_CALL(consume, Call(flat[3], 0, 13));
112 EXPECT_CALL(consume, Call(flat[4], 5, 10));
113 EXPECT_CALL(consume, Call(flat[5], 0, 7));
114 Consume(CordRep::Ref(tree), consume.AsStdFunction());
115 for (CordRep* rep : flat) {
116 EXPECT_FALSE(rep->refcount.IsOne());
117 CordRep::Unref(rep);
118 }
119 CordRep::Unref(tree);
120 }
121
TEST(CordRepConsumeTest,Reverse)122 TEST(CordRepConsumeTest, Reverse) {
123 InSequence in_sequence;
124 CordRep* tree = CreateTestTree();
125 MockFunction<void(CordRep*, size_t, size_t)> consume;
126 EXPECT_CALL(consume, Call(flat[5], 0, 7));
127 EXPECT_CALL(consume, Call(flat[4], 5, 10));
128 EXPECT_CALL(consume, Call(flat[3], 0, 13));
129 EXPECT_CALL(consume, Call(flat[2], 0, 9));
130 EXPECT_CALL(consume, Call(flat[1], 2, 4));
131 EXPECT_CALL(consume, Call(flat[0], 0, 1));
132 ReverseConsume(tree, consume.AsStdFunction());
133 for (CordRep* rep : flat) {
134 EXPECT_TRUE(rep->refcount.IsOne());
135 CordRep::Unref(rep);
136 }
137 }
138
TEST(CordRepConsumeTest,ReverseShared)139 TEST(CordRepConsumeTest, ReverseShared) {
140 InSequence in_sequence;
141 CordRep* tree = CreateTestTree();
142 MockFunction<void(CordRep*, size_t, size_t)> consume;
143 EXPECT_CALL(consume, Call(flat[5], 0, 7));
144 EXPECT_CALL(consume, Call(flat[4], 5, 10));
145 EXPECT_CALL(consume, Call(flat[3], 0, 13));
146 EXPECT_CALL(consume, Call(flat[2], 0, 9));
147 EXPECT_CALL(consume, Call(flat[1], 2, 4));
148 EXPECT_CALL(consume, Call(flat[0], 0, 1));
149 ReverseConsume(CordRep::Ref(tree), consume.AsStdFunction());
150 for (CordRep* rep : flat) {
151 EXPECT_FALSE(rep->refcount.IsOne());
152 CordRep::Unref(rep);
153 }
154 CordRep::Unref(tree);
155 }
156
TEST(CordRepConsumeTest,UnreachableFlat)157 TEST(CordRepConsumeTest, UnreachableFlat) {
158 InSequence in_sequence;
159 CordRepFlat* flat1 = CreateFlatWithLength(10);
160 CordRepFlat* flat2 = CreateFlatWithLength(20);
161 CordRepConcat* concat = CreateConcat(flat1, flat2);
162 CordRepSubstring* tree = CreateSubstring(concat, 15, 10);
163 MockFunction<void(CordRep*, size_t, size_t)> consume;
164 EXPECT_CALL(consume, Call(flat2, 5, 10));
165 Consume(tree, consume.AsStdFunction());
166 EXPECT_TRUE(flat2->refcount.IsOne());
167 CordRep::Unref(flat2);
168 }
169
170 } // namespace
171 } // namespace cord_internal
172 ABSL_NAMESPACE_END
173 } // namespace absl
174