Damien Martin-Guillerez | f88f4d8 | 2015-09-25 13:56:55 +0000 | [diff] [blame] | 1 | // Copyright 2014 The Bazel Authors. All rights reserved. |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 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 | // 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. |
| 14 | package com.google.devtools.build.lib.util; |
| 15 | |
| 16 | import static com.google.common.truth.Truth.assertThat; |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 17 | |
| 18 | import com.google.common.base.Function; |
| 19 | import com.google.common.base.Strings; |
| 20 | import com.google.common.collect.Lists; |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 21 | import com.google.common.collect.Maps; |
| 22 | import com.google.devtools.build.lib.testutil.TestUtils; |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 23 | import java.util.List; |
| 24 | import java.util.SortedMap; |
| 25 | import java.util.concurrent.ArrayBlockingQueue; |
Googler | 028fe87 | 2016-03-02 15:46:28 +0000 | [diff] [blame] | 26 | import java.util.concurrent.ConcurrentHashMap; |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 27 | import java.util.concurrent.ThreadPoolExecutor; |
| 28 | import java.util.concurrent.TimeUnit; |
| 29 | import java.util.concurrent.atomic.AtomicInteger; |
lberki | aea56b3 | 2017-05-30 12:35:33 +0200 | [diff] [blame] | 30 | import org.junit.Before; |
| 31 | import org.junit.Test; |
| 32 | import org.junit.runner.RunWith; |
| 33 | import org.junit.runners.JUnit4; |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 34 | |
| 35 | /** |
| 36 | * Test for the StringIndexer classes. |
| 37 | */ |
| 38 | public abstract class StringIndexerTest { |
| 39 | |
| 40 | private static final int ATTEMPTS = 1000; |
| 41 | private SortedMap<Integer, String> mappings; |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 42 | protected StringIndexer indexer; |
Florian Weikert | a165f24 | 2015-12-02 15:25:03 +0000 | [diff] [blame] | 43 | private final Object lock = new Object(); |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 44 | |
| 45 | @Before |
Florian Weikert | a165f24 | 2015-12-02 15:25:03 +0000 | [diff] [blame] | 46 | public final void createIndexer() throws Exception { |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 47 | indexer = newIndexer(); |
| 48 | mappings = Maps.newTreeMap(); |
| 49 | } |
| 50 | |
| 51 | protected abstract StringIndexer newIndexer(); |
| 52 | |
| 53 | protected void assertSize(int expected) { |
lberki | aea56b3 | 2017-05-30 12:35:33 +0200 | [diff] [blame] | 54 | assertThat(indexer.size()).isEqualTo(expected); |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 55 | } |
| 56 | |
| 57 | protected void assertNoIndex(String s) { |
| 58 | int size = indexer.size(); |
lberki | aea56b3 | 2017-05-30 12:35:33 +0200 | [diff] [blame] | 59 | assertThat(indexer.getIndex(s)).isEqualTo(-1); |
| 60 | assertThat(indexer.size()).isEqualTo(size); |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 61 | } |
| 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); |
lberki | aea56b3 | 2017-05-30 12:35:33 +0200 | [diff] [blame] | 67 | assertThat(index).isEqualTo(expected); |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 68 | mappings.put(expected, s); |
| 69 | } |
| 70 | |
| 71 | protected void assertContent() { |
| 72 | for (int i = 0; i < indexer.size(); i++) { |
lberki | aea56b3 | 2017-05-30 12:35:33 +0200 | [diff] [blame] | 73 | assertThat(mappings.get(i)).isNotNull(); |
Ulf Adams | 795895a | 2015-03-06 15:58:35 +0000 | [diff] [blame] | 74 | assertThat(mappings).containsEntry(i, indexer.getStringForIndex(i)); |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 75 | } |
| 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 Weikert | a165f24 | 2015-12-02 15:25:03 +0000 | [diff] [blame] | 83 | synchronized(lock) { |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 84 | for (int i = 0; i < ATTEMPTS; i++) { |
| 85 | final String key = keyGenerator.apply(i); |
| 86 | keys.add(key); |
laurentlb | 5980012 | 2017-07-03 11:42:25 -0400 | [diff] [blame] | 87 | 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 Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 95 | } |
| 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); |
lberki | aea56b3 | 2017-05-30 12:35:33 +0200 | [diff] [blame] | 104 | assertThat(key).isNotNull(); |
| 105 | assertThat(indexer.getIndex(key)).isEqualTo(index); |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 106 | } |
| 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. |
lberki | 78cfa8d | 2017-05-30 17:00:48 +0200 | [diff] [blame] | 114 | assertThat(indexer.getStringForIndex(indexer.getIndex(key))).isEqualTo(key); |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 115 | } |
| 116 | } |
| 117 | |
| 118 | @Test |
| 119 | public void concurrentAddChildNode() throws Exception { |
laurentlb | 5980012 | 2017-07-03 11:42:25 -0400 | [diff] [blame] | 120 | assertConcurrentUpdates(from -> Strings.repeat("a", from + 1)); |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 121 | } |
| 122 | |
| 123 | @Test |
| 124 | public void concurrentSplitNodeSuffix() throws Exception { |
laurentlb | 5980012 | 2017-07-03 11:42:25 -0400 | [diff] [blame] | 125 | assertConcurrentUpdates(from -> Strings.repeat("b", ATTEMPTS - from)); |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 126 | } |
| 127 | |
| 128 | @Test |
| 129 | public void concurrentAddBranch() throws Exception { |
laurentlb | 5980012 | 2017-07-03 11:42:25 -0400 | [diff] [blame] | 130 | assertConcurrentUpdates(from -> String.format("%08o", from)); |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 131 | } |
| 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); |
lberki | aea56b3 | 2017-05-30 12:35:33 +0200 | [diff] [blame] | 163 | assertThat(indexer.getStringForIndex(0)).isNull(); |
| 164 | assertThat(indexer.getStringForIndex(1000)).isNull(); |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 165 | } |
| 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); |
lberki | aea56b3 | 2017-05-30 12:35:33 +0200 | [diff] [blame] | 228 | 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 Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 232 | } |
| 233 | } |
| 234 | |
| 235 | @RunWith(JUnit4.class) |
| 236 | public static class CanonicalStringIndexerTest extends StringIndexerTest{ |
| 237 | @Override |
| 238 | protected StringIndexer newIndexer() { |
Kristina Chodorow | 05f0440 | 2016-03-03 16:44:51 +0000 | [diff] [blame] | 239 | return new CanonicalStringIndexer(new ConcurrentHashMap<String, Integer>(), |
| 240 | new ConcurrentHashMap<Integer, String>()); |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 241 | } |
| 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); |
lberki | aea56b3 | 2017-05-30 12:35:33 +0200 | [diff] [blame] | 266 | assertThat(indexer.getStringForIndex(0)).isNull(); |
| 267 | assertThat(indexer.getStringForIndex(1000)).isNull(); |
Han-Wen Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 268 | } |
| 269 | |
| 270 | @Test |
| 271 | public void addStringResult() { |
| 272 | assertSize(0); |
lberki | aea56b3 | 2017-05-30 12:35:33 +0200 | [diff] [blame] | 273 | 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 Nienhuys | d08b27f | 2015-02-25 16:45:20 +0100 | [diff] [blame] | 278 | } |
| 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 | } |