From 3f802805f41eade4fe9a0c8f6544dbd2a96fa418 Mon Sep 17 00:00:00 2001 From: Jon Bratseth Date: Mon, 30 Sep 2019 15:27:41 +0200 Subject: Resolve left-wildcard variants precisely --- .../search/query/profile/DimensionBinding.java | 22 ++--- .../search/query/profile/DimensionValues.java | 23 +++--- .../search/query/profile/QueryProfileCompiler.java | 59 ++++++++++++-- .../profile/compiled/CompiledQueryProfile.java | 2 +- .../query/profile/test/QueryProfileTestCase.java | 20 +++++ .../profile/test/QueryProfileVariantsTestCase.java | 93 ++++++++++------------ 6 files changed, 138 insertions(+), 81 deletions(-) diff --git a/container-search/src/main/java/com/yahoo/search/query/profile/DimensionBinding.java b/container-search/src/main/java/com/yahoo/search/query/profile/DimensionBinding.java index 00c7cf98b47..0059b761734 100644 --- a/container-search/src/main/java/com/yahoo/search/query/profile/DimensionBinding.java +++ b/container-search/src/main/java/com/yahoo/search/query/profile/DimensionBinding.java @@ -15,7 +15,7 @@ import java.util.Map; public class DimensionBinding { /** The dimensions of this */ - private List dimensions=null; + private List dimensions; /** The values matching those dimensions */ private DimensionValues values; @@ -24,30 +24,32 @@ public class DimensionBinding { private Map context; public static final DimensionBinding nullBinding = - new DimensionBinding(Collections.unmodifiableList(Collections.emptyList()), DimensionValues.empty, null); + new DimensionBinding(Collections.unmodifiableList(Collections.emptyList()), DimensionValues.empty, null); public static final DimensionBinding invalidBinding = - new DimensionBinding(Collections.unmodifiableList(Collections.emptyList()), DimensionValues.empty, null); + new DimensionBinding(Collections.unmodifiableList(Collections.emptyList()), DimensionValues.empty, null); /** Whether the value array contains only nulls */ private boolean containsAllNulls; /** Creates a binding from a variant and a context. Any of the arguments may be null. */ public static DimensionBinding createFrom(List dimensions, Map context) { - if (dimensions==null || dimensions.size()==0) { - if (context==null) return nullBinding; - if (dimensions==null) return new DimensionBinding(null,DimensionValues.empty,context); // Null, but must preserve context + if (dimensions == null || dimensions.size() == 0) { + if (context == null) return nullBinding; + if (dimensions == null) return new DimensionBinding(null, DimensionValues.empty, context); // Null, but must preserve context } - return new DimensionBinding(dimensions,extractDimensionValues(dimensions,context),context); + return new DimensionBinding(dimensions, extractDimensionValues(dimensions, context), context); } /** Creates a binding from a variant and a context. Any of the arguments may be null. */ public static DimensionBinding createFrom(List dimensions, DimensionValues dimensionValues) { - if (dimensionValues==null || dimensionValues==DimensionValues.empty) return nullBinding; - if (dimensions==null) return new DimensionBinding(null,dimensionValues,null); // Null, but preserve raw material for creating a context later (in createFor) + if (dimensionValues==null || dimensionValues == DimensionValues.empty) return nullBinding; - return new DimensionBinding(dimensions,dimensionValues,null); + // If null, preserve raw material for creating a context later (in createFor) + if (dimensions == null) return new DimensionBinding(null, dimensionValues, null); + + return new DimensionBinding(dimensions, dimensionValues, null); } /** Returns a binding for a (possibly) new set of variants. Variants may be null, but not bindings */ diff --git a/container-search/src/main/java/com/yahoo/search/query/profile/DimensionValues.java b/container-search/src/main/java/com/yahoo/search/query/profile/DimensionValues.java index c7c020220dc..1a36f4917d9 100644 --- a/container-search/src/main/java/com/yahoo/search/query/profile/DimensionValues.java +++ b/container-search/src/main/java/com/yahoo/search/query/profile/DimensionValues.java @@ -10,12 +10,14 @@ import java.util.Map; * An immutable set of dimension values. * Note that this may contain more or fewer values than needed given a set of dimensions. * Any missing values are treated as null. + * + * @author bratseth */ public class DimensionValues implements Comparable { private final String[] values; - public static final DimensionValues empty=new DimensionValues(new String[] {}); + public static final DimensionValues empty = new DimensionValues(new String[] {}); public static DimensionValues createFrom(String[] values) { if (values==null || values.length==0 || containsAllNulls(values)) return empty; @@ -27,7 +29,7 @@ public class DimensionValues implements Comparable { * the right size, and where no copying is done. * * @param values the dimension values. This need not be normalized to the right size. - * The input array is copied by this. + * The input array is copied by this. */ private DimensionValues(String[] values) { if (values==null) throw new NullPointerException("Dimension values cannot be null"); @@ -115,26 +117,25 @@ public class DimensionValues implements Comparable { } public Map asContext(List dimensions) { - Map context=new HashMap<>(); - if (dimensions==null) return context; - for (int i=0; i context = new HashMap<>(); + if (dimensions == null) return context; + for (int i = 0; i < dimensions.size(); i++) + context.put(dimensions.get(i), get(i)); return context; } - /** Returns the string at the given index, or null if it has no value at this index. */ + /** Returns the string at the given index, or null if it has no value at this index */ public String get(int index) { - if (index>=values.length) return null; + if (index >= values.length) return null; return values[index]; } /** Returns the number of values in this (some of which may be null) */ public int size() { return values.length; } - /** Returns copy of the values in this in an array */ + /** Returns a copy of the values in this in an array */ public String[] getValues() { - return Arrays.copyOf(values,values.length); + return Arrays.copyOf(values, values.length); } } diff --git a/container-search/src/main/java/com/yahoo/search/query/profile/QueryProfileCompiler.java b/container-search/src/main/java/com/yahoo/search/query/profile/QueryProfileCompiler.java index 826c9949bcf..accef7ba154 100644 --- a/container-search/src/main/java/com/yahoo/search/query/profile/QueryProfileCompiler.java +++ b/container-search/src/main/java/com/yahoo/search/query/profile/QueryProfileCompiler.java @@ -10,6 +10,7 @@ import com.yahoo.search.query.profile.types.QueryProfileType; import java.util.Collection; import java.util.HashSet; import java.util.Map; +import java.util.Optional; import java.util.Set; import java.util.logging.Level; import java.util.logging.Logger; @@ -40,14 +41,12 @@ public class QueryProfileCompiler { // Resolve values for each existing variant and combine into a single data structure Set variants = collectVariants(CompoundName.empty, in, DimensionBinding.nullBinding); variants.add(new DimensionBindingForPath(DimensionBinding.nullBinding, CompoundName.empty)); // if this contains no variants - if (log.isLoggable(Level.FINE)) - log.fine("Compiling " + in.toString() + " having " + variants.size() + " variants"); - int i = 0; + log.fine(() -> "Compiling " + in.toString() + " having " + variants.size() + " variants"); for (DimensionBindingForPath variant : variants) { - if (log.isLoggable(Level.FINER)) - log.finer(" Compiling variant " + i++ + ": " + variant); - for (Map.Entry entry : in.listValues(variant.path(), variant.binding().getContext(), null).entrySet()) + log.finer(() -> " Compiling variant " + variant); + for (Map.Entry entry : in.listValues(variant.path(), variant.binding().getContext(), null).entrySet()) { values.put(variant.path().append(entry.getKey()), variant.binding(), entry.getValue()); + } for (Map.Entry entry : in.listTypes(variant.path(), variant.binding().getContext()).entrySet()) types.put(variant.path().append(entry.getKey()), variant.binding(), entry.getValue()); for (CompoundName reference : in.listReferences(variant.path(), variant.binding().getContext())) @@ -62,7 +61,7 @@ public class QueryProfileCompiler { } /** - * Returns all the unique combinations of dimension values which have values set reachable from this profile. + * Returns all the unique combinations of dimension values which have values reachable from this profile. * * @param profile the profile we are collecting the variants of * @param currentVariant the variant we must have to arrive at this point in the query profile graph @@ -74,15 +73,59 @@ public class QueryProfileCompiler { if (profile instanceof BackedOverridableQueryProfile) variants.addAll(collectVariantsInThis(path, ((BackedOverridableQueryProfile) profile).getBacking(), currentVariant)); - Set parentVariants = new HashSet<>(); + Set parentVariants; for (QueryProfile inheritedProfile : profile.inherited()) { parentVariants = collectVariants(path, inheritedProfile, currentVariant); variants.addAll(parentVariants); variants.addAll(combined(variants, parentVariants)); // parents and children may have different variant dimensions } + + variants.addAll(leftExpanded(variants)); return variants; } + /** + * For variants which are underspecified on the left we must explicitly resolve each possible combination + * of actual left-side values. + * + * I.e if we have the variants [-,b=b1], [a=a1,-], [a=a2,-], + * this returns the variants [a=a1,b=b1], [a=a2,b=b1] + * + * This is necessary because left-specified values takes precedence, such that resolving [a=a1,b=b1] would + * lead us to the compiled profile [a=a1,-], which may contain default values for properties where + * we should have preferred variant values in [-,b=b1]. + */ + private static Set leftExpanded(Set variants) { + Set expanded = new HashSet<>(); + for (var variant : variants) { + if (hasLeftWildcard(variant.binding())) + expanded.addAll(leftExpanded(variant, variants)); + } + return expanded; + } + + private static boolean hasLeftWildcard(DimensionBinding variant) { + for (int i = 0; i < variant.getValues().size() - 1; i++) { // -1 to not check the rightmost + if (variant.getValues().get(i) == null) + return true; + } + return false; + } + + private static Set leftExpanded(DimensionBindingForPath variantToExpand, + Set variants) { + Set expanded = new HashSet<>(); + for (var variant : variants) { + if ( ! variantToExpand.path().equals(variant.path())) continue; + + DimensionBinding combined = variantToExpand.binding().combineWith(variant.binding); + if ( ! combined.isInvalid() ) + expanded.add(new DimensionBindingForPath(combined, variantToExpand.path())); + } + return expanded; + } + + /** Generates a set of all the (legal) combinations of the variants in the given sets */ private static Set combined(Set v1s, Set v2s) { diff --git a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/CompiledQueryProfile.java b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/CompiledQueryProfile.java index e6fedada35d..d6e93701ca1 100644 --- a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/CompiledQueryProfile.java +++ b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/CompiledQueryProfile.java @@ -23,7 +23,7 @@ import java.util.regex.Pattern; */ public class CompiledQueryProfile extends AbstractComponent implements Cloneable { - private static final Pattern namePattern=Pattern.compile("[$a-zA-Z_/][-$a-zA-Z0-9_/()]*"); + private static final Pattern namePattern = Pattern.compile("[$a-zA-Z_/][-$a-zA-Z0-9_/()]*"); private final CompiledQueryProfileRegistry registry; diff --git a/container-search/src/test/java/com/yahoo/search/query/profile/test/QueryProfileTestCase.java b/container-search/src/test/java/com/yahoo/search/query/profile/test/QueryProfileTestCase.java index 9f890b249d2..3c276157f72 100644 --- a/container-search/src/test/java/com/yahoo/search/query/profile/test/QueryProfileTestCase.java +++ b/container-search/src/test/java/com/yahoo/search/query/profile/test/QueryProfileTestCase.java @@ -9,6 +9,7 @@ import com.yahoo.search.query.profile.QueryProfile; import com.yahoo.search.query.profile.QueryProfileProperties; import com.yahoo.search.query.profile.QueryProfileRegistry; import com.yahoo.search.query.profile.compiled.CompiledQueryProfile; +import com.yahoo.yolean.trace.TraceNode; import org.junit.Test; import java.util.Arrays; @@ -592,4 +593,23 @@ public class QueryProfileTestCase { assertTrue(q.properties().getBoolean("clustering.timeline", false)); } + @Test + public void testSubstitutionInTrace() { + QueryProfile profile = new QueryProfile("test"); + profile.set("property", "%{foo}", null); + CompiledQueryProfile cProfile = profile.compile(null); + + Query query = new Query("?foo=value&tracelevel=4", cProfile); + assertEquals("value", query.properties().get("property")); + assertTrue(traceContains("foo=value", query)); + } + + // NB: NOT RECURSIVE + private boolean traceContains(String string, Query query) { + for (TraceNode node : query.getContext(true).getTrace().traceNode().children()) + if (node.payload().toString().contains(string)) + return true; + return false; + } + } diff --git a/container-search/src/test/java/com/yahoo/search/query/profile/test/QueryProfileVariantsTestCase.java b/container-search/src/test/java/com/yahoo/search/query/profile/test/QueryProfileVariantsTestCase.java index 18329a817a5..d9bf4a1db97 100644 --- a/container-search/src/test/java/com/yahoo/search/query/profile/test/QueryProfileVariantsTestCase.java +++ b/container-search/src/test/java/com/yahoo/search/query/profile/test/QueryProfileVariantsTestCase.java @@ -70,18 +70,17 @@ public class QueryProfileVariantsTestCase { } @Test - public void testVariantSubstitution() { + public void testMultipleMatchingVariantsAndDefault() { QueryProfile profile = new QueryProfile("test"); - profile.setDimensions(new String[] { "langReg", "region", "site" }); - profile.set("property", "%{site}", null); - profile.set("property", "fp", new String[] { null, null, "frontpage"}, null); - profile.set("streams", "ntk_stream_fresh", new String[] { "en-GB", "GB" }, null); + profile.setDimensions(new String[] { "a", "b" }); + profile.set("property1", "property1_default", null); + profile.set("property1", "property1_variantB", new String[] { null, "b1" }, null); + profile.set("property2", "property2_variantA", new String[] { "a1", null }, null); CompiledQueryProfile cProfile = profile.compile(null); - Query query = new Query("?langReg=en-GB®ion=GB&site=frontpage&tracelevel=4", cProfile); - assertEquals("frontpage", query.properties().get("property")); - assertEquals("ntk_stream_fresh", query.properties().get("streams")); - assertTrue(traceContains("property=frontpage", query)); + Query query = new Query("?a=a1&b=b1&b=b1", cProfile); + assertEquals("property1_variantB", query.properties().get("property1")); + assertEquals("property2_variantA", query.properties().get("property2")); } @Test @@ -166,13 +165,13 @@ public class QueryProfileVariantsTestCase { @Test public void testVariantsOfExplicitCompound() { QueryProfile a1 = new QueryProfile("a1"); - a1.set("b","a.b", null); + a1.set("b", "a.b", null); - QueryProfile profile=new QueryProfile("test"); + QueryProfile profile = new QueryProfile("test"); profile.setDimensions(new String[] {"x"}); - profile.set("a",a1, null); - profile.set("a.b","a.b.x1",new String[] {"x1"}, null); - profile.set("a.b","a.b.x2",new String[] {"x2"}, null); + profile.set("a", a1, null); + profile.set("a.b", "a.b.x1", new String[] {"x1"}, null); + profile.set("a.b", "a.b.x2", new String[] {"x2"}, null); CompiledQueryProfile cprofile = profile.compile(null); @@ -271,53 +270,53 @@ public class QueryProfileVariantsTestCase { @Test public void testVariantNotInBase() { - QueryProfile test=new QueryProfile("test"); + QueryProfile test = new QueryProfile("test"); test.setDimensions(new String[] {"x"}); - test.set("InX1Only","x1",new String[] {"x1"}, null); + test.set("InX1Only", "x1", new String[] { "x1" }, null); CompiledQueryProfile ctest = test.compile(null); - assertEquals("x1",ctest.get("InX1Only", toMap("x=x1"))); - assertEquals(null,ctest.get("InX1Only", toMap("x=x2"))); - assertEquals(null,ctest.get("InX1Only")); + assertEquals("x1", ctest.get("InX1Only", toMap("x=x1"))); + assertEquals(null, ctest.get("InX1Only", toMap("x=x2"))); + assertEquals(null, ctest.get("InX1Only")); } @Test public void testVariantNotInBaseSpaceVariantValue() { - QueryProfile test=new QueryProfile("test"); - test.setDimensions(new String[] {"x"}); - test.set("InX1Only","x1",new String[] {"x 1"}, null); + QueryProfile test = new QueryProfile("test"); + test.setDimensions(new String[] { "x" }); + test.set("InX1Only", "x1", new String[] { "x 1" }, null); CompiledQueryProfile ctest = test.compile(null); - assertEquals("x1",ctest.get("InX1Only", toMap("x=x 1"))); - assertEquals(null,ctest.get("InX1Only", toMap("x=x 2"))); - assertEquals(null,ctest.get("InX1Only")); + assertEquals("x1", ctest.get("InX1Only", toMap("x=x 1"))); + assertEquals(null, ctest.get("InX1Only", toMap("x=x 2"))); + assertEquals(null, ctest.get("InX1Only")); } @Test public void testDimensionsInSuperType() { - QueryProfile parent=new QueryProfile("parent"); - parent.setDimensions(new String[] {"x","y"}); - QueryProfile child=new QueryProfile("child"); + QueryProfile parent = new QueryProfile("parent"); + parent.setDimensions(new String[] {"x", "y"}); + QueryProfile child = new QueryProfile("child"); child.addInherited(parent); - child.set("a","a.default", null); - child.set("a","a.x1.y1",new String[] {"x1","y1"}, null); - child.set("a","a.x1.y2",new String[] {"x1","y2"}, null); + child.set("a", "a.default", null); + child.set("a", "a.x1.y1", new String[] {"x1", "y1"}, null); + child.set("a", "a.x1.y2", new String[] {"x1", "y2"}, null); CompiledQueryProfile cchild = child.compile(null); assertEquals("a.default", cchild.get("a")); - assertEquals("a.x1.y1", cchild.get("a", toMap("x=x1","y=y1"))); - assertEquals("a.x1.y2", cchild.get("a", toMap("x=x1","y=y2"))); + assertEquals("a.x1.y1", cchild.get("a", toMap("x=x1", "y=y1"))); + assertEquals("a.x1.y2", cchild.get("a", toMap("x=x1", "y=y2"))); } @Test public void testDimensionsInSuperTypeRuntime() { - QueryProfile parent=new QueryProfile("parent"); - parent.setDimensions(new String[] {"x","y"}); - QueryProfile child=new QueryProfile("child"); + QueryProfile parent = new QueryProfile("parent"); + parent.setDimensions(new String[] { "x", "y" }); + QueryProfile child = new QueryProfile("child"); child.addInherited(parent); - child.set("a","a.default", null); + child.set("a", "a.default", null); child.set("a", "a.x1.y1", new String[]{"x1", "y1"}, null); child.set("a", "a.x1.y2", new String[]{"x1", "y2"}, null); Properties overridable=new QueryProfileProperties(child.compile(null)); @@ -1143,15 +1142,15 @@ public class QueryProfileVariantsTestCase { } public static Map toMap(QueryProfile profile, String[] dimensionValues) { - Map context=new HashMap<>(); + Map context = new HashMap<>(); List dimensions; - if (profile.getVariants()!=null) - dimensions=profile.getVariants().getDimensions(); + if (profile.getVariants() != null) + dimensions = profile.getVariants().getDimensions(); else - dimensions=((BackedOverridableQueryProfile)profile).getBacking().getVariants().getDimensions(); + dimensions = ((BackedOverridableQueryProfile)profile).getBacking().getVariants().getDimensions(); - for (int i=0; i