diff options
author | Henning Baldersheim <balder@yahoo-inc.com> | 2024-05-06 14:58:30 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2024-05-06 14:58:30 +0200 |
commit | b57b7783563828f9a9b0502af6c15739383571e7 (patch) | |
tree | 5f59b9e8cd970d4f38b130d33574556e4be48e75 /container-core/src | |
parent | 2dc47f13e2b4656121bb245c60ab5ea339339a68 (diff) | |
parent | d84936fbe83b8b78425f10b2992d830b886ff15e (diff) |
Merge pull request #26651 from vespa-engine/jonmv/DP-to-reduce-number-of-created-compound-names
Avoid creating an exponential number of compound-names with many segm…
Diffstat (limited to 'container-core/src')
-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 | 63 |
2 files changed, 82 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 b4536a1c56b..440df4f9be9 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; + if (end == start) throw new IllegalArgumentException("'" + name + "' is not a legal compound name. " + + "Consecutive, leading or trailing dots are not allowed."); + String subName = this.name.substring(start, end); + CompoundName cached = cache.get(subName); + children[j] = 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 b5143f89c78..7523a68501f 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,32 @@ 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 + void testIllegalCompound() { + assertEquals("'a.' is not a legal compound name. Names can not end with a dot.", + assertThrows(IllegalArgumentException.class, + () -> CompoundName.from("a.")) + .getMessage()); + assertEquals("'.b' is not a legal compound name. Consecutive, leading or trailing dots are not allowed.", + assertThrows(IllegalArgumentException.class, + () -> CompoundName.from(".b")) + .getMessage()); + assertEquals("'a..b' is not a legal compound name. Consecutive, leading or trailing dots are not allowed.", + assertThrows(IllegalArgumentException.class, + () -> CompoundName.from("a..b")) + .getMessage()); } @Test @@ -82,7 +100,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 +111,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 +139,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 +147,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 +158,7 @@ public class CompoundNameTestCase { } @Test - final void testGetLowerCasedName() { + void testGetLowerCasedName() { assertEquals(Lowercase.toLowerCase(NAME), C_NAME.getLowerCasedName()); } @@ -223,4 +241,5 @@ public class CompoundNameTestCase { assertEquals("[one]", CompoundName.from("one").asList().toString()); assertEquals("[one, two, three]", CompoundName.from("one.two.three").asList().toString()); } + } |