DependencyTreeCache implements Serializable { public Set<T> getDependencies(T node) { HashSet<T> result = new HashSet<>(); LinkedList<T> pendingKeys = new LinkedList<>(); pendingKeys.add(node); try { while (!pendingKeys.isEmpty()) { T path = pendingKeys.removeLast(); if (result.add(path)) { getOrParseDependencies(path).forEach(pendingKeys::add); } } } catch (InterruptedException e) { Thread.currentThread().interrupt(); throw new RuntimeException( "Interrupted while finding dependencies for " + node, e); } return result; } DependencyTreeCache(
            SerializableFunction<T, Collection<T>> dependencyParser); Set<T> getDependencies(T node); void clear();  }
@Test public void multipleLevels_allIncluded_noneParsedAgain() { MockParser parser = new MockParser().addResult("/a", "/b") .addResult("/b", "/c").addResult("/c"); DependencyTreeCache<String> cache = new DependencyTreeCache<>(parser); Set<String> dependencies = cache.getDependencies("/a"); parser.assertConsumed(); Assert.assertEquals(new HashSet<>(Arrays.asList("/a", "/b", "/c")), dependencies); Set<String> dependencies2 = cache.getDependencies("/a"); Assert.assertEquals(dependencies, dependencies2); }
@Test public void sharedDependency_onlyParsedOnce() { MockParser parser = new MockParser().addResult("/a", "/b", "/c") .addResult("/b", "/d").addResult("/c", "/d").addResult("/d"); DependencyTreeCache<String> cache = new DependencyTreeCache<>(parser); Set<String> dependencies = cache.getDependencies("/a"); parser.assertConsumed(); Assert.assertEquals( new HashSet<>(Arrays.asList("/a", "/b", "/c", "/d")), dependencies); }
@Test public void concurrentParse_onlyParsedOnce() throws InterruptedException { MockParser parser = new MockParser(); parser.addResult("/a", "/b"); parser.addResult("/b", 100); DependencyTreeCache<String> cache = new DependencyTreeCache<>(parser); long start = System.currentTimeMillis(); Set<String> threadResult = new HashSet<>(); Thread thread = new Thread(() -> { threadResult.addAll(cache.getDependencies("/a")); }); thread.start(); Set<String> dependencies = cache.getDependencies("/a"); thread.join(); long end = System.currentTimeMillis(); Assert.assertEquals(new HashSet<>(Arrays.asList("/a", "/b")), dependencies); Assert.assertEquals(dependencies, threadResult); long duration = (end - start); Assert.assertTrue("Parsing should take less than 200 ms", duration < 200); Assert.assertTrue( "Parsing should take at least 100 ms, was " + duration, duration >= 100); }
@Test public void parallelParsing_potentialSpeedup() throws InterruptedException { int maxDuration = Integer.MIN_VALUE; int minDuration = Integer.MAX_VALUE; int iterationCount = 0; while (minDuration > 75 || maxDuration < 75) { if (iterationCount++ > 30) { Assert.fail( "Did not observe both slowdown and speedup. Max duration: " + maxDuration + ", min duration: " + minDuration); } MockParser parser = new MockParser().addResult("/a", 25, "/b", "/c") .addResult("/b", 25).addResult("/c", 25); DependencyTreeCache<String> cache = new DependencyTreeCache<>( parser); Thread thread = new Thread(() -> cache.getDependencies("/a")); long start = System.currentTimeMillis(); thread.start(); cache.getDependencies("/a"); thread.join(); long end = System.currentTimeMillis(); int duration = (int) (end - start); Assert.assertTrue( "Duration should never be less than 50, was " + duration, duration >= 50); maxDuration = Math.max(maxDuration, duration); minDuration = Math.min(minDuration, duration); } }