1 /*
2  * Copyright (C) 2018 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include "perfetto/ext/base/string_view.h"
18 
19 #include <forward_list>
20 #include <unordered_map>
21 #include <unordered_set>
22 
23 #include "test/gtest_and_gmock.h"
24 
25 namespace perfetto {
26 namespace base {
27 namespace {
28 
TEST(StringViewTest,BasicCases)29 TEST(StringViewTest, BasicCases) {
30   EXPECT_EQ(StringView(), StringView(""));
31   EXPECT_EQ(StringView(""), StringView(""));
32   EXPECT_EQ(StringView(""), StringView("", 0));
33   EXPECT_EQ(StringView("ab"), StringView("ab", 2));
34   EXPECT_EQ(StringView("ax", 1), StringView("ay", 1));
35   EXPECT_EQ(StringView("ax", 1), StringView("a"));
36   EXPECT_EQ(StringView("ax", 1), "a");
37   EXPECT_EQ(StringView("foo|", 3).ToStdString(), std::string("foo"));
38   EXPECT_TRUE(StringView("x") != StringView(""));
39   EXPECT_TRUE(StringView("") != StringView("y"));
40   EXPECT_TRUE(StringView("a") != StringView("b"));
41   EXPECT_EQ(StringView().size(), 0ul);
42   EXPECT_EQ(StringView().data(), nullptr);
43   EXPECT_EQ(StringView("").size(), 0ul);
44   EXPECT_NE(StringView("").data(), nullptr);
45   EXPECT_TRUE(StringView("").empty());
46   EXPECT_FALSE(StringView("x").empty());
47 
48   {
49     StringView x("abc");
50     EXPECT_EQ(x.size(), 3u);
51     EXPECT_EQ(x.data()[0], 'a');
52     EXPECT_EQ(x.data()[2], 'c');
53     EXPECT_TRUE(x == "abc");
54     EXPECT_TRUE(x == StringView("abc"));
55     EXPECT_TRUE(x != StringView("abcd"));
56     EXPECT_FALSE(x == StringView("aBc"));
57     EXPECT_TRUE(x.CaseInsensitiveEq("aBc"));
58     EXPECT_TRUE(x.CaseInsensitiveEq("AbC"));
59     EXPECT_FALSE(x.CaseInsensitiveEq("AbCd"));
60     EXPECT_FALSE(x.CaseInsensitiveEq("ab"));
61     EXPECT_FALSE(x.CaseInsensitiveEq("abcd"));
62     EXPECT_FALSE(x.CaseInsensitiveEq(""));
63   }
64 
65   // Test find(char).
66   EXPECT_EQ(StringView().find('x'), StringView::npos);
67   EXPECT_EQ(StringView("").find('x'), StringView::npos);
68   EXPECT_EQ(StringView("foo").find('x'), StringView::npos);
69   EXPECT_EQ(StringView("foo").find('f'), 0u);
70   EXPECT_EQ(StringView("foo").find('o'), 1u);
71 
72   // Test rfind(char).
73   EXPECT_EQ(StringView().rfind('x'), StringView::npos);
74   EXPECT_EQ(StringView("").rfind('x'), StringView::npos);
75   EXPECT_EQ(StringView("foo").rfind('x'), StringView::npos);
76   EXPECT_EQ(StringView("foo").rfind('f'), 0u);
77   EXPECT_EQ(StringView("foo").rfind('o'), 2u);
78 
79   // Test find(const char*).
80   EXPECT_EQ(StringView().find("x"), StringView::npos);
81   EXPECT_EQ(StringView("").find("x"), StringView::npos);
82   EXPECT_EQ(StringView("foo").find("x"), StringView::npos);
83   EXPECT_EQ(StringView("foo").find("foobar"), StringView::npos);
84   EXPECT_EQ(StringView("foo").find("f", 1), StringView::npos);
85   EXPECT_EQ(StringView("foo").find("f"), 0u);
86   EXPECT_EQ(StringView("foo").find("fo"), 0u);
87   EXPECT_EQ(StringView("foo").find("oo"), 1u);
88   EXPECT_EQ(StringView("foo").find("o"), 1u);
89   EXPECT_EQ(StringView("foo").find("o", 2), 2u);
90   EXPECT_EQ(StringView("foo").find("o", 3), StringView::npos);
91   EXPECT_EQ(StringView("foo").find("o", 10), StringView::npos);
92   EXPECT_EQ(StringView("foobar").find("bar", 3), 3u);
93   EXPECT_EQ(StringView("foobar").find("bartender"), StringView::npos);
94   EXPECT_EQ(StringView("foobar").find("bartender", 3), StringView::npos);
95   EXPECT_EQ(StringView("foo").find(""), 0u);  // std::string behaves the same.
96 
97   // Test substr().
98   EXPECT_EQ(StringView().substr(0, 0).ToStdString(), "");
99   EXPECT_EQ(StringView().substr(3, 1).ToStdString(), "");
100   EXPECT_EQ(StringView("foo").substr(3, 1).ToStdString(), "");
101   EXPECT_EQ(StringView("foo").substr(4, 0).ToStdString(), "");
102   EXPECT_EQ(StringView("foo").substr(4, 1).ToStdString(), "");
103   EXPECT_EQ(StringView("foo").substr(0, 1).ToStdString(), "f");
104   EXPECT_EQ(StringView("foo").substr(0, 3).ToStdString(), "foo");
105   EXPECT_EQ(StringView("foo").substr(0, 99).ToStdString(), "foo");
106   EXPECT_EQ(StringView("foo").substr(1, 2).ToStdString(), "oo");
107   EXPECT_EQ(StringView("foo").substr(1, 3).ToStdString(), "oo");
108   EXPECT_EQ(StringView("foo").substr(1, 99).ToStdString(), "oo");
109   EXPECT_EQ(StringView("xyz").substr(0).ToStdString(), "xyz");
110   EXPECT_EQ(StringView("xyz").substr(2).ToStdString(), "z");
111   EXPECT_EQ(StringView("xyz").substr(3).ToStdString(), "");
112 
113   // Test the < operator.
114   EXPECT_FALSE(StringView() < StringView());
115   EXPECT_FALSE(StringView() < StringView(""));
116   EXPECT_TRUE(StringView() < StringView("foo"));
117   EXPECT_TRUE(StringView("") < StringView("foo"));
118   EXPECT_FALSE(StringView() < StringView("foo", 0));
119   EXPECT_FALSE(StringView("foo") < StringView("foo"));
120   EXPECT_TRUE(StringView("foo") < StringView("fooo"));
121   EXPECT_FALSE(StringView("fooo") < StringView("foo"));
122   EXPECT_TRUE(StringView("bar") < StringView("foo"));
123 
124   // Test the <= operator.
125   EXPECT_TRUE(StringView() <= StringView());
126   EXPECT_TRUE(StringView() <= StringView(""));
127   EXPECT_TRUE(StringView() <= StringView("foo"));
128   EXPECT_TRUE(StringView("") <= StringView("foo"));
129   EXPECT_TRUE(StringView() <= StringView("foo", 0));
130   EXPECT_TRUE(StringView("foo") <= StringView("foo"));
131   EXPECT_TRUE(StringView("foo") <= StringView("fooo"));
132   EXPECT_FALSE(StringView("fooo") <= StringView("foo"));
133   EXPECT_TRUE(StringView("bar") <= StringView("foo"));
134 
135   // Test the > operator.
136   EXPECT_FALSE(StringView() > StringView());
137   EXPECT_FALSE(StringView() > StringView(""));
138   EXPECT_FALSE(StringView() > StringView("foo"));
139   EXPECT_FALSE(StringView("") > StringView("foo"));
140   EXPECT_FALSE(StringView() > StringView("foo", 0));
141   EXPECT_FALSE(StringView("foo") > StringView("foo"));
142   EXPECT_FALSE(StringView("foo") > StringView("fooo"));
143   EXPECT_TRUE(StringView("fooo") > StringView("foo"));
144   EXPECT_FALSE(StringView("bar") > StringView("foo"));
145 
146   // Test the >= operator.
147   EXPECT_TRUE(StringView() >= StringView());
148   EXPECT_TRUE(StringView() >= StringView(""));
149   EXPECT_FALSE(StringView() >= StringView("foo"));
150   EXPECT_FALSE(StringView("") >= StringView("foo"));
151   EXPECT_TRUE(StringView() >= StringView("foo", 0));
152   EXPECT_TRUE(StringView("foo") >= StringView("foo"));
153   EXPECT_FALSE(StringView("foo") >= StringView("fooo"));
154   EXPECT_TRUE(StringView("fooo") >= StringView("foo"));
155   EXPECT_FALSE(StringView("bar") >= StringView("foo"));
156 }
157 
TEST(StringViewTest,HashCollisions)158 TEST(StringViewTest, HashCollisions) {
159   std::unordered_map<uint64_t, StringView> hashes;
160   std::unordered_set<StringView> sv_set;
161   auto insert_sv = [&hashes, &sv_set](StringView sv) {
162     hashes.emplace(sv.Hash(), sv);
163     size_t prev_set_size = sv_set.size();
164     sv_set.insert(sv);
165     ASSERT_EQ(sv_set.size(), prev_set_size + 1);
166   };
167 
168   insert_sv("");
169   EXPECT_EQ(hashes.size(), 1u);
170   size_t last_size = 1;
171   std::forward_list<std::string> strings;
172   for (uint8_t c = 0; c < 0x80; c++) {
173     char buf[500];
174     memset(buf, static_cast<char>(c), sizeof(buf));
175     for (size_t i = 1; i <= sizeof(buf); i++) {
176       strings.emplace_front(buf, i);
177       StringView sv(strings.front());
178       auto other = hashes.find(sv.Hash());
179       if (other == hashes.end()) {
180         insert_sv(sv);
181         ++last_size;
182         ASSERT_EQ(hashes.size(), last_size);
183         continue;
184       }
185       EXPECT_TRUE(false) << "H(" << sv.ToStdString() << ") = "
186                          << "H(" << other->second.ToStdString() << ")";
187     }
188   }
189 }
190 
191 }  // namespace
192 }  // namespace base
193 }  // namespace perfetto
194