diff options
author | jonmv <venstad@gmail.com> | 2023-03-30 15:04:13 +0200 |
---|---|---|
committer | jonmv <venstad@gmail.com> | 2023-03-30 15:34:03 +0200 |
commit | db06ad61bdb8eac1d35800eea6b5cae56e392e1d (patch) | |
tree | 90d025814c9828bf34ed5fd6579aa3e6b91c7375 /container-core | |
parent | 95bdba88075024110dab52fdcdf17a171081fad0 (diff) |
Avoid creating an exponential number of compound-names with many segments
Diffstat (limited to 'container-core')
-rw-r--r-- | container-core/src/main/java/com/yahoo/processing/request/CompoundName.java | 70 | ||||
-rw-r--r-- | container-core/src/test/java/com/yahoo/processing/request/CompoundNameTestCase.java | 47 |
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()); } + } |