blob: b242f37d2bd5d65f8078b5230cd49b95b8e0f004 [file] [log] [blame]
Damien Martin-Guillerezf88f4d82015-09-25 13:56:55 +00001// Copyright 2014 The Bazel Authors. All rights reserved.
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +01002//
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// http://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.
14package com.google.devtools.build.lib.util;
15
16import static com.google.common.truth.Truth.assertThat;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010017
18import com.google.common.base.Function;
19import com.google.common.base.Strings;
20import com.google.common.collect.Lists;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010021import com.google.common.collect.Maps;
22import com.google.devtools.build.lib.testutil.TestUtils;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010023import java.util.List;
24import java.util.SortedMap;
25import java.util.concurrent.ArrayBlockingQueue;
Googler028fe872016-03-02 15:46:28 +000026import java.util.concurrent.ConcurrentHashMap;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010027import java.util.concurrent.ThreadPoolExecutor;
28import java.util.concurrent.TimeUnit;
29import java.util.concurrent.atomic.AtomicInteger;
lberkiaea56b32017-05-30 12:35:33 +020030import org.junit.Before;
31import org.junit.Test;
32import org.junit.runner.RunWith;
33import org.junit.runners.JUnit4;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010034
35/**
36 * Test for the StringIndexer classes.
37 */
38public abstract class StringIndexerTest {
39
40 private static final int ATTEMPTS = 1000;
41 private SortedMap<Integer, String> mappings;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010042 protected StringIndexer indexer;
Florian Weikerta165f242015-12-02 15:25:03 +000043 private final Object lock = new Object();
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010044
45 @Before
Florian Weikerta165f242015-12-02 15:25:03 +000046 public final void createIndexer() throws Exception {
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010047 indexer = newIndexer();
48 mappings = Maps.newTreeMap();
49 }
50
51 protected abstract StringIndexer newIndexer();
52
53 protected void assertSize(int expected) {
lberkiaea56b32017-05-30 12:35:33 +020054 assertThat(indexer.size()).isEqualTo(expected);
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010055 }
56
57 protected void assertNoIndex(String s) {
58 int size = indexer.size();
lberkiaea56b32017-05-30 12:35:33 +020059 assertThat(indexer.getIndex(s)).isEqualTo(-1);
60 assertThat(indexer.size()).isEqualTo(size);
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010061 }
62
63 protected void assertIndex(int expected, String s) {
64 // System.out.println("Adding " + s + ", expecting " + expected);
65 int index = indexer.getOrCreateIndex(s);
66 // System.out.println(csi);
lberkiaea56b32017-05-30 12:35:33 +020067 assertThat(index).isEqualTo(expected);
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010068 mappings.put(expected, s);
69 }
70
71 protected void assertContent() {
72 for (int i = 0; i < indexer.size(); i++) {
lberkiaea56b32017-05-30 12:35:33 +020073 assertThat(mappings.get(i)).isNotNull();
Ulf Adams795895a2015-03-06 15:58:35 +000074 assertThat(mappings).containsEntry(i, indexer.getStringForIndex(i));
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010075 }
76 }
77
78 private void assertConcurrentUpdates(Function<Integer, String> keyGenerator) throws Exception {
79 final AtomicInteger safeIndex = new AtomicInteger(-1);
80 List<String> keys = Lists.newArrayListWithCapacity(ATTEMPTS);
81 ThreadPoolExecutor executor = new ThreadPoolExecutor(3, 3, 5, TimeUnit.SECONDS,
82 new ArrayBlockingQueue<Runnable>(ATTEMPTS));
Florian Weikerta165f242015-12-02 15:25:03 +000083 synchronized(lock) {
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010084 for (int i = 0; i < ATTEMPTS; i++) {
85 final String key = keyGenerator.apply(i);
86 keys.add(key);
laurentlb59800122017-07-03 11:42:25 -040087 executor.execute(
88 () -> {
89 int index = indexer.getOrCreateIndex(key);
90 if (safeIndex.get() < index) {
91 safeIndex.set(index);
92 }
93 indexer.addString(key);
94 });
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010095 }
96 }
97 try {
98 while(!executor.getQueue().isEmpty()) {
99 // Validate that we can execute concurrent queries too.
100 if (safeIndex.get() >= 0) {
101 int index = safeIndex.get();
102 // Retrieve string using random existing index and validate reverse mapping.
103 String key = indexer.getStringForIndex(index);
lberkiaea56b32017-05-30 12:35:33 +0200104 assertThat(key).isNotNull();
105 assertThat(indexer.getIndex(key)).isEqualTo(index);
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100106 }
107 }
108 } finally {
109 executor.shutdown();
110 executor.awaitTermination(TestUtils.WAIT_TIMEOUT_SECONDS, TimeUnit.SECONDS);
111 }
112 for (String key : keys) {
113 // Validate mapping between keys and indices.
lberki78cfa8d2017-05-30 17:00:48 +0200114 assertThat(indexer.getStringForIndex(indexer.getIndex(key))).isEqualTo(key);
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100115 }
116 }
117
118 @Test
119 public void concurrentAddChildNode() throws Exception {
laurentlb59800122017-07-03 11:42:25 -0400120 assertConcurrentUpdates(from -> Strings.repeat("a", from + 1));
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100121 }
122
123 @Test
124 public void concurrentSplitNodeSuffix() throws Exception {
laurentlb59800122017-07-03 11:42:25 -0400125 assertConcurrentUpdates(from -> Strings.repeat("b", ATTEMPTS - from));
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100126 }
127
128 @Test
129 public void concurrentAddBranch() throws Exception {
laurentlb59800122017-07-03 11:42:25 -0400130 assertConcurrentUpdates(from -> String.format("%08o", from));
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100131 }
132
133 @RunWith(JUnit4.class)
134 public static class CompactStringIndexerTest extends StringIndexerTest {
135 @Override
136 protected StringIndexer newIndexer() {
137 return new CompactStringIndexer(1);
138 }
139
140 @Test
141 public void basicOperations() {
142 assertSize(0);
143 assertNoIndex("abcdef");
144 assertIndex(0, "abcdef"); // root node creation
145 assertIndex(0, "abcdef"); // root node match
146 assertSize(1);
147 assertIndex(2, "abddef"); // node branching, index 1 went to "ab" node.
148 assertSize(3);
149 assertIndex(1, "ab");
150 assertSize(3);
151 assertIndex(3, "abcdefghik"); // new leaf creation
152 assertSize(4);
153 assertIndex(4, "abcdefgh"); // node split
154 assertSize(5);
155 assertNoIndex("a");
156 assertNoIndex("abc");
157 assertNoIndex("abcdefg");
158 assertNoIndex("abcdefghil");
159 assertNoIndex("abcdefghikl");
160 assertContent();
161 indexer.clear();
162 assertSize(0);
lberkiaea56b32017-05-30 12:35:33 +0200163 assertThat(indexer.getStringForIndex(0)).isNull();
164 assertThat(indexer.getStringForIndex(1000)).isNull();
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100165 }
166
167 @Test
168 public void parentIndexUpdate() {
169 assertSize(0);
170 assertIndex(0, "abcdefghik"); // Create 3 nodes with single common parent "abcdefgh".
171 assertIndex(2, "abcdefghlm"); // Index 1 went to "abcdefgh".
172 assertIndex(3, "abcdefghxyz");
173 assertSize(4);
174 assertIndex(5, "abcdpqr"); // Split parent. Index 4 went to "abcd".
175 assertSize(6);
176 assertIndex(1, "abcdefgh"); // Check branch node indices.
177 assertIndex(4, "abcd");
178 assertSize(6);
179 assertContent();
180 }
181
182 @Test
183 public void emptyRootNode() {
184 assertSize(0);
185 assertIndex(0, "abc");
186 assertNoIndex("");
187 assertIndex(2, "def"); // root node key is now empty string and has index 1.
188 assertSize(3);
189 assertIndex(1, "");
190 assertSize(3);
191 assertContent();
192 }
193
194 protected void setupTestContent() {
195 assertSize(0);
196 assertIndex(0, "abcdefghi"); // Create leafs
197 assertIndex(2, "abcdefjkl");
198 assertIndex(3, "abcdefmno");
199 assertIndex(4, "abcdefjklpr");
200 assertIndex(6, "abcdstr");
201 assertIndex(8, "012345");
202 assertSize(9);
203 assertIndex(1, "abcdef"); // Validate inner nodes
204 assertIndex(5, "abcd");
205 assertIndex(7, "");
206 assertSize(9);
207 assertContent();
208 }
209
210 @Test
211 public void dumpContent() {
212 indexer = newIndexer();
213 indexer.addString("abc");
214 String content = indexer.toString();
215 assertThat(content).contains("size = 1");
216 assertThat(content).contains("contentSize = 5");
217 indexer = newIndexer();
218 setupTestContent();
219 content = indexer.toString();
220 assertThat(content).contains("size = 9");
221 assertThat(content).contains("contentSize = 60");
222 System.out.println(indexer);
223 }
224
225 @Test
226 public void addStringResult() {
227 assertSize(0);
lberkiaea56b32017-05-30 12:35:33 +0200228 assertThat(indexer.addString("abcdef")).isTrue();
229 assertThat(indexer.addString("abcdgh")).isTrue();
230 assertThat(indexer.addString("abcd")).isFalse();
231 assertThat(indexer.addString("ab")).isTrue();
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100232 }
233 }
234
235 @RunWith(JUnit4.class)
236 public static class CanonicalStringIndexerTest extends StringIndexerTest{
237 @Override
238 protected StringIndexer newIndexer() {
Kristina Chodorow05f04402016-03-03 16:44:51 +0000239 return new CanonicalStringIndexer(new ConcurrentHashMap<String, Integer>(),
240 new ConcurrentHashMap<Integer, String>());
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100241 }
242
243 @Test
244 public void basicOperations() {
245 assertSize(0);
246 assertNoIndex("abcdef");
247 assertIndex(0, "abcdef");
248 assertIndex(0, "abcdef");
249 assertSize(1);
250 assertIndex(1, "abddef");
251 assertSize(2);
252 assertIndex(2, "ab");
253 assertSize(3);
254 assertIndex(3, "abcdefghik");
255 assertSize(4);
256 assertIndex(4, "abcdefgh");
257 assertSize(5);
258 assertNoIndex("a");
259 assertNoIndex("abc");
260 assertNoIndex("abcdefg");
261 assertNoIndex("abcdefghil");
262 assertNoIndex("abcdefghikl");
263 assertContent();
264 indexer.clear();
265 assertSize(0);
lberkiaea56b32017-05-30 12:35:33 +0200266 assertThat(indexer.getStringForIndex(0)).isNull();
267 assertThat(indexer.getStringForIndex(1000)).isNull();
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100268 }
269
270 @Test
271 public void addStringResult() {
272 assertSize(0);
lberkiaea56b32017-05-30 12:35:33 +0200273 assertThat(indexer.addString("abcdef")).isTrue();
274 assertThat(indexer.addString("abcdgh")).isTrue();
275 assertThat(indexer.addString("abcd")).isTrue();
276 assertThat(indexer.addString("ab")).isTrue();
277 assertThat(indexer.addString("ab")).isFalse();
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100278 }
279
280 protected void setupTestContent() {
281 assertSize(0);
282 assertIndex(0, "abcdefghi");
283 assertIndex(1, "abcdefjkl");
284 assertIndex(2, "abcdefmno");
285 assertIndex(3, "abcdefjklpr");
286 assertIndex(4, "abcdstr");
287 assertIndex(5, "012345");
288 assertSize(6);
289 assertIndex(6, "abcdef");
290 assertIndex(7, "abcd");
291 assertIndex(8, "");
292 assertIndex(2, "abcdefmno");
293 assertSize(9);
294 assertContent();
295 }
296 }
297
298}