src/test/java/com/google/devtools/build/lib/util/StringIndexerTest.java

// Copyright 2014 The Bazel Authors. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package com.google.devtools.build.lib.util;

import static com.google.common.truth.Truth.assertThat;

import com.google.common.base.Function;
import com.google.common.base.Strings;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.devtools.build.lib.testutil.TestUtils;
import java.util.List;
import java.util.SortedMap;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;

/**
 * Test for the StringIndexer classes.
 */
public abstract class StringIndexerTest {

  private static final int ATTEMPTS = 1000;
  private SortedMap<Integer, String> mappings;
  protected StringIndexer indexer;
  private final Object lock = new Object();

  @Before
  public final void createIndexer() throws Exception  {
    indexer = newIndexer();
    mappings = Maps.newTreeMap();
  }

  protected abstract StringIndexer newIndexer();

  protected void assertSize(int expected) {
    assertThat(indexer.size()).isEqualTo(expected);
  }

  protected void assertNoIndex(String s) {
    int size = indexer.size();
    assertThat(indexer.getIndex(s)).isEqualTo(-1);
    assertThat(indexer.size()).isEqualTo(size);
  }

  protected void assertIndex(int expected, String s) {
    // System.out.println("Adding " + s + ", expecting " + expected);
    int index = indexer.getOrCreateIndex(s);
    // System.out.println(csi);
    assertThat(index).isEqualTo(expected);
    mappings.put(expected, s);
  }

  protected void assertContent() {
    for (int i = 0; i < indexer.size(); i++) {
      assertThat(mappings.get(i)).isNotNull();
      assertThat(mappings).containsEntry(i, indexer.getStringForIndex(i));
    }
  }

  private void assertConcurrentUpdates(Function<Integer, String> keyGenerator) throws Exception {
    final AtomicInteger safeIndex = new AtomicInteger(-1);
    List<String> keys = Lists.newArrayListWithCapacity(ATTEMPTS);
    ThreadPoolExecutor executor = new ThreadPoolExecutor(3, 3, 5, TimeUnit.SECONDS,
        new ArrayBlockingQueue<Runnable>(ATTEMPTS));
    synchronized(lock) {
      for (int i = 0; i < ATTEMPTS; i++) {
        final String key = keyGenerator.apply(i);
        keys.add(key);
        executor.execute(
            () -> {
              int index = indexer.getOrCreateIndex(key);
              if (safeIndex.get() < index) {
                safeIndex.set(index);
              }
              indexer.addString(key);
            });
      }
    }
    try {
      while(!executor.getQueue().isEmpty()) {
        // Validate that we can execute concurrent queries too.
        if (safeIndex.get() >= 0) {
          int index = safeIndex.get();
          // Retrieve string using random existing index and validate reverse mapping.
          String key = indexer.getStringForIndex(index);
          assertThat(key).isNotNull();
          assertThat(indexer.getIndex(key)).isEqualTo(index);
        }
      }
    } finally {
      executor.shutdown();
      executor.awaitTermination(TestUtils.WAIT_TIMEOUT_SECONDS, TimeUnit.SECONDS);
    }
    for (String key : keys) {
      // Validate mapping between keys and indices.
      assertThat(indexer.getStringForIndex(indexer.getIndex(key))).isEqualTo(key);
    }
  }

  @Test
  public void concurrentAddChildNode() throws Exception {
    assertConcurrentUpdates(from -> Strings.repeat("a", from + 1));
  }

  @Test
  public void concurrentSplitNodeSuffix() throws Exception {
    assertConcurrentUpdates(from -> Strings.repeat("b", ATTEMPTS - from));
  }

  @Test
  public void concurrentAddBranch() throws Exception {
    assertConcurrentUpdates(from -> String.format("%08o", from));
  }

  @RunWith(JUnit4.class)
  public static class CompactStringIndexerTest extends StringIndexerTest {
    @Override
    protected StringIndexer newIndexer() {
      return new CompactStringIndexer(1);
    }

    @Test
    public void basicOperations() {
      assertSize(0);
      assertNoIndex("abcdef");
      assertIndex(0, "abcdef"); // root node creation
      assertIndex(0, "abcdef"); // root node match
      assertSize(1);
      assertIndex(2, "abddef"); // node branching, index 1 went to "ab" node.
      assertSize(3);
      assertIndex(1, "ab");
      assertSize(3);
      assertIndex(3, "abcdefghik"); // new leaf creation
      assertSize(4);
      assertIndex(4, "abcdefgh");  // node split
      assertSize(5);
      assertNoIndex("a");
      assertNoIndex("abc");
      assertNoIndex("abcdefg");
      assertNoIndex("abcdefghil");
      assertNoIndex("abcdefghikl");
      assertContent();
      indexer.clear();
      assertSize(0);
      assertThat(indexer.getStringForIndex(0)).isNull();
      assertThat(indexer.getStringForIndex(1000)).isNull();
    }

    @Test
    public void parentIndexUpdate() {
      assertSize(0);
      assertIndex(0, "abcdefghik");  // Create 3 nodes with single common parent "abcdefgh".
      assertIndex(2, "abcdefghlm");  // Index 1 went to "abcdefgh".
      assertIndex(3, "abcdefghxyz");
      assertSize(4);
      assertIndex(5, "abcdpqr"); // Split parent. Index 4 went to "abcd".
      assertSize(6);
      assertIndex(1, "abcdefgh"); // Check branch node indices.
      assertIndex(4, "abcd");
      assertSize(6);
      assertContent();
    }

    @Test
    public void emptyRootNode() {
      assertSize(0);
      assertIndex(0, "abc");
      assertNoIndex("");
      assertIndex(2, "def");  // root node key is now empty string and has index 1.
      assertSize(3);
      assertIndex(1, "");
      assertSize(3);
      assertContent();
    }

    protected void setupTestContent() {
      assertSize(0);
      assertIndex(0, "abcdefghi");  // Create leafs
      assertIndex(2, "abcdefjkl");
      assertIndex(3, "abcdefmno");
      assertIndex(4, "abcdefjklpr");
      assertIndex(6, "abcdstr");
      assertIndex(8, "012345");
      assertSize(9);
      assertIndex(1, "abcdef");  // Validate inner nodes
      assertIndex(5, "abcd");
      assertIndex(7, "");
      assertSize(9);
      assertContent();
    }

    @Test
    public void dumpContent() {
      indexer = newIndexer();
      indexer.addString("abc");
      String content = indexer.toString();
      assertThat(content).contains("size = 1");
      assertThat(content).contains("contentSize = 5");
      indexer = newIndexer();
      setupTestContent();
      content = indexer.toString();
      assertThat(content).contains("size = 9");
      assertThat(content).contains("contentSize = 60");
      System.out.println(indexer);
    }

    @Test
    public void addStringResult() {
      assertSize(0);
      assertThat(indexer.addString("abcdef")).isTrue();
      assertThat(indexer.addString("abcdgh")).isTrue();
      assertThat(indexer.addString("abcd")).isFalse();
      assertThat(indexer.addString("ab")).isTrue();
    }
  }

  @RunWith(JUnit4.class)
  public static class CanonicalStringIndexerTest extends StringIndexerTest{
    @Override
    protected StringIndexer newIndexer() {
      return new CanonicalStringIndexer(new ConcurrentHashMap<String, Integer>(),
          new ConcurrentHashMap<Integer, String>());
    }

    @Test
    public void basicOperations() {
      assertSize(0);
      assertNoIndex("abcdef");
      assertIndex(0, "abcdef");
      assertIndex(0, "abcdef");
      assertSize(1);
      assertIndex(1, "abddef");
      assertSize(2);
      assertIndex(2, "ab");
      assertSize(3);
      assertIndex(3, "abcdefghik");
      assertSize(4);
      assertIndex(4, "abcdefgh");
      assertSize(5);
      assertNoIndex("a");
      assertNoIndex("abc");
      assertNoIndex("abcdefg");
      assertNoIndex("abcdefghil");
      assertNoIndex("abcdefghikl");
      assertContent();
      indexer.clear();
      assertSize(0);
      assertThat(indexer.getStringForIndex(0)).isNull();
      assertThat(indexer.getStringForIndex(1000)).isNull();
    }

    @Test
    public void addStringResult() {
      assertSize(0);
      assertThat(indexer.addString("abcdef")).isTrue();
      assertThat(indexer.addString("abcdgh")).isTrue();
      assertThat(indexer.addString("abcd")).isTrue();
      assertThat(indexer.addString("ab")).isTrue();
      assertThat(indexer.addString("ab")).isFalse();
    }

    protected void setupTestContent() {
      assertSize(0);
      assertIndex(0, "abcdefghi");
      assertIndex(1, "abcdefjkl");
      assertIndex(2, "abcdefmno");
      assertIndex(3, "abcdefjklpr");
      assertIndex(4, "abcdstr");
      assertIndex(5, "012345");
      assertSize(6);
      assertIndex(6, "abcdef");
      assertIndex(7, "abcd");
      assertIndex(8, "");
      assertIndex(2, "abcdefmno");
      assertSize(9);
      assertContent();
    }
  }

}