Avoid creating an exponential number of compound-names with many segments

2 files changed, 66 insertions, 51 deletions

diff --git a/container-core/src/main/java/com/yahoo/processing/request/CompoundName.java b/container-core/src/main/java/com/yahoo/processing/request/CompoundName.java
index 0edff9162b5..51f7ae040eb 100644
--- a/container-core/src/main/java/com/yahoo/processing/request/CompoundName.java
+++ b/container-core/src/main/java/com/yahoo/processing/request/CompoundName.java
@@ -8,6 +8,7 @@ import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.List;
 import java.util.Map;
+import java.util.Objects;
 
 import static com.yahoo.text.Lowercase.toLowerCase;
 
@@ -74,41 +75,52 @@ public final class CompoundName {
      * @param compounds the compounds of this name
      */
     private CompoundName(String name, String [] compounds, boolean useCache) {
-        if (name == null) throw new NullPointerException("Name can not be null");
-
-        this.name = name;
+        this.name = Objects.requireNonNull(name, "Name can not be null");
         this.lowerCasedName = toLowerCase(name);
-        if (compounds.length == 1 && compounds[0].isEmpty()) {
-            this.compounds = List.of();
-            this.hashCode = 0;
-            rest = this;
-            first = this;
+        if (compounds.length == 1) {
+            if (compounds[0].isEmpty()) {
+                this.compounds = List.of();
+                this.hashCode = 0;
+                rest = first = this;
+                return;
+            }
+            this.compounds = new ImmutableArrayList(compounds);
+            this.hashCode = this.compounds.hashCode();
+            rest = first = empty;
             return;
         }
-        this.compounds = new ImmutableArrayList(compounds);
-        this.hashCode = this.compounds.hashCode();
-
-        if (compounds.length > 1) {
-            String restName = name.substring(compounds[0].length()+1);
-            if (useCache) {
-                rest = cache.computeIfAbsent(restName, (key) -> new CompoundName(key, Arrays.copyOfRange(compounds, 1, compounds.length), useCache));
-            } else {
-                rest = new CompoundName(restName, Arrays.copyOfRange(compounds, 1, compounds.length), useCache);
+        CompoundName[] children = new CompoundName[compounds.length];
+        for (int i = 0; i + 1 < children.length; i++) {
+            int start = 0, end = i == 0 ? -1 : children[0].name.length();
+            for (int j = 0; j + i < children.length; j++) {
+                end += compounds[j + i].length() + 1;
+                String subName = this.name.substring(start, end);
+                CompoundName cached = cache.get(subName);
+                children[j] = start == end ? empty
+                                           : cached != null
+                                           ? cached
+                                           : new CompoundName(subName,
+                                                              this.lowerCasedName.substring(start, end),
+                                                              Arrays.copyOfRange(compounds, j, j + i + 1),
+                                                              i == 0 ? empty : children[j + 1],
+                                                              i == 0 ? empty : children[j]);
+                if (useCache && cached == null) cache.put(subName, children[j]);
+                start += compounds[j].length() + 1;
             }
-        } else {
-            rest = empty;
         }
+        this.compounds = new ImmutableArrayList(compounds);
+        this.hashCode = this.compounds.hashCode();
+        this.rest = children[1];
+        this.first = children[0];
+    }
 
-        if (compounds.length > 1) {
-            String firstName = name.substring(0, name.length() - (compounds[compounds.length-1].length()+1));
-            if (useCache) {
-                first = cache.computeIfAbsent(firstName, (key) -> new CompoundName(key, Arrays.copyOfRange(compounds, 0, compounds.length-1), useCache));
-            } else {
-                first = new CompoundName(firstName, Arrays.copyOfRange(compounds, 0, compounds.length-1), useCache);
-            }
-        } else {
-            first = empty;
-        }
+    private CompoundName(String name, String lowerCasedName, String[] compounds, CompoundName rest, CompoundName first) {
+        this.name = name;
+        this.lowerCasedName = lowerCasedName;
+        this.compounds = new ImmutableArrayList(compounds);
+        this.hashCode = this.compounds.hashCode();
+        this.rest = rest;
+        this.first = first;
     }
 
     private static List<String> parse(String s) {
diff --git a/container-core/src/test/java/com/yahoo/processing/request/CompoundNameTestCase.java b/container-core/src/test/java/com/yahoo/processing/request/CompoundNameTestCase.java
index eccc4dd8842..35e7ef84756 100644
--- a/container-core/src/test/java/com/yahoo/processing/request/CompoundNameTestCase.java
+++ b/container-core/src/test/java/com/yahoo/processing/request/CompoundNameTestCase.java
@@ -13,7 +13,7 @@ import static org.junit.jupiter.api.Assertions.*;
 /**
  * Module local test of the basic property name building block.
  *
- * @author <a href="mailto:steinar@yahoo-inc.com">Steinar Knutsen</a>
+ * @author Steinar Knutsen
  */
 public class CompoundNameTestCase {
 
@@ -30,22 +30,22 @@ public class CompoundNameTestCase {
     }
 
     @Test
-    final void testLast() {
+    void testLast() {
         assertEquals(NAME.substring(NAME.lastIndexOf('.') + 1), C_NAME.last());
     }
 
     @Test
-    final void testFirst() {
+    void testFirst() {
         assertEquals(NAME.substring(0, NAME.indexOf('.')), C_NAME.first());
     }
 
     @Test
-    final void testRest() {
+    void testRest() {
         verifyStrict(NAME.substring(NAME.indexOf('.') + 1), C_NAME.rest());
     }
 
     @Test
-    final void testRestN() {
+    void testRestN() {
         verifyStrict("a.b.c.d.e", C_abcde.rest(0));
         verifyStrict("b.c.d.e", C_abcde.rest(1));
         verifyStrict("c.d.e", C_abcde.rest(2));
@@ -53,8 +53,9 @@ public class CompoundNameTestCase {
         verifyStrict("e", C_abcde.rest(4));
         verifyStrict(CompoundName.empty, C_abcde.rest(5));
     }
+
     @Test
-    final void testFirstN() {
+    void testFirstN() {
         verifyStrict("a.b.c.d.e", C_abcde.first(5));
         verifyStrict("a.b.c.d", C_abcde.first(4));
         verifyStrict("a.b.c", C_abcde.first(3));
@@ -64,15 +65,16 @@ public class CompoundNameTestCase {
     }
 
     @Test
-    final void testPrefix() {
-        CompoundName abc = CompoundName.from("a.b.c");
-        assertTrue(abc.hasPrefix(CompoundName.empty));
-        assertTrue(abc.hasPrefix(CompoundName.from("a")));
-        assertTrue(abc.hasPrefix(CompoundName.from("a.b")));
-        assertTrue(abc.hasPrefix(CompoundName.from("a.b.c")));
+    void testPrefix() {
+        CompoundName abcc = CompoundName.from("a.b.cc");
+        assertTrue(abcc.hasPrefix(CompoundName.empty));
+        assertTrue(abcc.hasPrefix(CompoundName.from("a")));
+        assertTrue(abcc.hasPrefix(CompoundName.from("a.b")));
+        assertTrue(abcc.hasPrefix(CompoundName.from("a.b.cc")));
 
-        assertFalse(abc.hasPrefix(CompoundName.from("a.b.c.d")));
-        assertFalse(abc.hasPrefix(CompoundName.from("a.b.d")));
+        assertFalse(abcc.hasPrefix(CompoundName.from("a.b.c")));
+        assertFalse(abcc.hasPrefix(CompoundName.from("a.b.c.d")));
+        assertFalse(abcc.hasPrefix(CompoundName.from("a.b.d")));
     }
 
     @Test
@@ -82,7 +84,7 @@ public class CompoundNameTestCase {
     }
 
     @Test
-    final void testSize() {
+    void testSize() {
         Splitter s = Splitter.on('.');
         Iterable<String> i = s.split(NAME);
         int n = 0;
@@ -93,23 +95,23 @@ public class CompoundNameTestCase {
     }
 
     @Test
-    final void testGet() {
+    void testGet() {
         String s = C_NAME.get(0);
         assertEquals(NAME.substring(0, NAME.indexOf('.')), s);
     }
 
     @Test
-    final void testIsCompound() {
+    void testIsCompound() {
         assertTrue(C_NAME.isCompound());
     }
 
     @Test
-    final void testIsEmpty() {
+    void testIsEmpty() {
         assertFalse(C_NAME.isEmpty());
     }
 
     @Test
-    final void testAsList() {
+    void testAsList() {
         List<String> l = C_NAME.asList();
         Splitter peoplesFront = Splitter.on('.');
         Iterable<String> answer = peoplesFront.split(NAME);
@@ -121,7 +123,7 @@ public class CompoundNameTestCase {
     }
 
     @Test
-    final void testEqualsObject() {
+    void testEqualsObject() {
         assertNotEquals(C_NAME, NAME);
         assertNotEquals(C_NAME, null);
         verifyStrict(C_NAME, C_NAME);
@@ -129,7 +131,7 @@ public class CompoundNameTestCase {
     }
 
     @Test
-    final void testEmptyNonEmpty() {
+    void testEmptyNonEmpty() {
         assertTrue(CompoundName.empty.isEmpty());
         assertEquals(0, CompoundName.empty.size());
         assertFalse(CompoundName.from("a").isEmpty());
@@ -140,7 +142,7 @@ public class CompoundNameTestCase {
     }
 
     @Test
-    final void testGetLowerCasedName() {
+    void testGetLowerCasedName() {
         assertEquals(Lowercase.toLowerCase(NAME), C_NAME.getLowerCasedName());
     }
 
@@ -223,4 +225,5 @@ public class CompoundNameTestCase {
         assertEquals("[one]", CompoundName.from("one").asList().toString());
         assertEquals("[one, two, three]", CompoundName.from("one.two.three").asList().toString());
     }
+
 }