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