Resolve left-wildcard variants precisely

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<String> dimensions=null;
+    private List<String> dimensions;
 
     /** The values matching those dimensions */
     private DimensionValues values;
@@ -24,30 +24,32 @@ public class DimensionBinding {
     private Map<String,String> context;
 
     public static final DimensionBinding nullBinding =
-        new DimensionBinding(Collections.<String>unmodifiableList(Collections.<String>emptyList()), DimensionValues.empty, null);
+        new DimensionBinding(Collections.unmodifiableList(Collections.emptyList()), DimensionValues.empty, null);
 
     public static final DimensionBinding invalidBinding =
-        new DimensionBinding(Collections.<String>unmodifiableList(Collections.<String>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<String> dimensions, Map<String,String> 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<String> 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<DimensionValues> {
 
     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<DimensionValues> {
      * 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<DimensionValues> {
     }
 
     public Map<String,String> asContext(List<String> dimensions) {
-        Map<String,String> context=new HashMap<>();
-        if (dimensions==null) return context;
-        for (int i=0; i<dimensions.size(); i++) {
-            context.put(dimensions.get(i),get(i));
-        }
+        Map<String,String> 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, <b>or null if it has no value at this index.</b> */
+    /** 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<DimensionBindingForPath> 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<String, Object> entry : in.listValues(variant.path(), variant.binding().getContext(), null).entrySet())
+            log.finer(() -> "  Compiling variant " + variant);
+            for (Map.Entry<String, Object> entry : in.listValues(variant.path(), variant.binding().getContext(), null).entrySet()) {
                 values.put(variant.path().append(entry.getKey()), variant.binding(), entry.getValue());
+            }
             for (Map.Entry<CompoundName, QueryProfileType> 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<DimensionBindingForPath> parentVariants = new HashSet<>();
+        Set<DimensionBindingForPath> 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<DimensionBindingForPath> leftExpanded(Set<DimensionBindingForPath> variants) {
+        Set<DimensionBindingForPath> 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<DimensionBindingForPath> leftExpanded(DimensionBindingForPath variantToExpand,
+                                                             Set<DimensionBindingForPath> variants) {
+        Set<DimensionBindingForPath> 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<DimensionBindingForPath> combined(Set<DimensionBindingForPath> v1s,
                                                          Set<DimensionBindingForPath> 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&region=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<String,String> toMap(QueryProfile profile, String[] dimensionValues) {
-        Map<String,String> context=new HashMap<>();
+        Map<String, String> context = new HashMap<>();
         List<String> 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<dimensionValues.length; i++)
-            context.put(dimensions.get(i),dimensionValues[i]); // Lookup dim. names to ease test...
+        for (int i = 0; i < dimensionValues.length; i++)
+            context.put(dimensions.get(i), dimensionValues[i]); // Lookup dim. names to ease test...
         return context;
     }
 
@@ -1164,12 +1163,4 @@ public class QueryProfileVariantsTestCase {
         return context;
     }
 
-    // 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;
-    }
-
 }