diff options
author | Jon Bratseth <bratseth@yahoo-inc.com> | 2016-06-15 23:09:44 +0200 |
---|---|---|
committer | Jon Bratseth <bratseth@yahoo-inc.com> | 2016-06-15 23:09:44 +0200 |
commit | 72231250ed81e10d66bfe70701e64fa5fe50f712 (patch) | |
tree | 2728bba1131a6f6e5bdf95afec7d7ff9358dac50 /predicate-search-core |
Publish
Diffstat (limited to 'predicate-search-core')
53 files changed, 4847 insertions, 0 deletions
diff --git a/predicate-search-core/OWNERS b/predicate-search-core/OWNERS new file mode 100644 index 00000000000..569bf1cc3a1 --- /dev/null +++ b/predicate-search-core/OWNERS @@ -0,0 +1 @@ +bjorncs diff --git a/predicate-search-core/pom.xml b/predicate-search-core/pom.xml new file mode 100644 index 00000000000..ad5d6002b66 --- /dev/null +++ b/predicate-search-core/pom.xml @@ -0,0 +1,57 @@ +<?xml version="1.0"?> +<!-- Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. --> +<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" + xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd"> + <modelVersion>4.0.0</modelVersion> + <parent> + <groupId>com.yahoo.vespa</groupId> + <artifactId>parent</artifactId> + <version>6-SNAPSHOT</version> + <relativePath>../parent/pom.xml</relativePath> + </parent> + <artifactId>predicate-search-core</artifactId> + <version>6-SNAPSHOT</version> + <packaging>jar</packaging> + <name>${project.artifactId}</name> + <dependencies> + <dependency> + <groupId>junit</groupId> + <artifactId>junit</artifactId> + <scope>test</scope> + </dependency> + <dependency> + <groupId>org.antlr</groupId> + <artifactId>antlr-runtime</artifactId> + </dependency> + <dependency> + <groupId>com.yahoo.vespa</groupId> + <artifactId>vespajlib</artifactId> + <version>${project.version}</version> + </dependency> + <dependency> + <groupId>com.yahoo.vespa</groupId> + <artifactId>annotations</artifactId> + <version>${project.version}</version> + </dependency> + <dependency> + <groupId>com.fasterxml.jackson.core</groupId> + <artifactId>jackson-core</artifactId> + <scope>provided</scope> + </dependency> + </dependencies> + <build> + <plugins> + <plugin> + <groupId>org.antlr</groupId> + <artifactId>antlr3-maven-plugin</artifactId> + <executions> + <execution> + <goals> + <goal>antlr</goal> + </goals> + </execution> + </executions> + </plugin> + </plugins> + </build> +</project> diff --git a/predicate-search-core/src/main/antlr3/com/yahoo/document/predicate/parser/Predicate.g b/predicate-search-core/src/main/antlr3/com/yahoo/document/predicate/parser/Predicate.g new file mode 100644 index 00000000000..963d87c3218 --- /dev/null +++ b/predicate-search-core/src/main/antlr3/com/yahoo/document/predicate/parser/Predicate.g @@ -0,0 +1,118 @@ +grammar Predicate; + +@header { +package com.yahoo.document.predicate.parser; + +import com.yahoo.document.predicate.Conjunction; +import com.yahoo.document.predicate.Disjunction; +import com.yahoo.document.predicate.FeatureRange; +import com.yahoo.document.predicate.FeatureSet; +import com.yahoo.document.predicate.Negation; +import com.yahoo.document.predicate.Predicate; +import com.yahoo.document.predicate.Predicates; +} + +@lexer::header { +package com.yahoo.document.predicate.parser; + +import com.yahoo.document.predicate.Predicate; +} + +@members { + @Override + public void emitErrorMessage(String message) { + throw new IllegalArgumentException(message); + } +} + +@lexer::members { + @Override + public void emitErrorMessage(String message) { + throw new IllegalArgumentException(message); + } +} + +predicate returns [Predicate n] + : d=disjunction EOF { n = d; } + ; + +disjunction returns [Predicate n] + : c=conjunction { n = c; } + ( OR c2=conjunction { n = new Disjunction(n, c2); } + ( OR c3=conjunction { ((Disjunction)n).addOperand(c3); } )* )? + ; + +conjunction returns [Predicate n] + : u=unary_node { n = u; } + ( AND u2=unary_node { n = new Conjunction(n, u2); } + ( AND u3=unary_node { ((Conjunction)n).addOperand(u3); } )* )? + ; + +unary_node returns [Predicate n] + : l=leaf { n = l; } + | ( not=NOT )? '(' d=disjunction ')' { n = d; if (not != null) { n = new Negation(n); } } + ; + +leaf returns [Predicate n] + : k=value ( not=NOT )? IN + ( mv=multivalue[k] { n = mv; } + | r=range[k] { n = r; } + ) { if (not != null) { n = new Negation(n); } } + | TRUE { n = Predicates.value(true); } + | FALSE { n = Predicates.value(false); } + ; + +multivalue[String key] returns [FeatureSet n] + : '[' v1=value { n = new FeatureSet(key, v1); } + ( ',' v2=value { n.addValue(v2); })* ']' + ; + +value returns [String s] + : VALUE { s = $VALUE.text; } + | STRING { s = $STRING.text; } + | INTEGER { s = $INTEGER.text; } + | k=keyword { s = k; } + ; + +range[String key] returns [FeatureRange r] + : '[' { r = new FeatureRange(key); } + ( i1=INTEGER { r.setFromInclusive(Long.parseLong(i1.getText())); } )? + '..' + ( i2=INTEGER { r.setToInclusive(Long.parseLong(i2.getText())); } )? + ( '(' partition (',' partition)* ')' )? + ']' + ; + +partition + : value ('='|'=-') (INTEGER INTEGER /* second integer becomes negative */ | INTEGER '+[' INTEGER? '..' INTEGER? ']') + ; + +keyword returns [String s] + : OR { s = $OR.text; } + | AND { s = $AND.text; } + | NOT { s = $NOT.text; } + | IN { s = $IN.text; } + | TRUE { s = $TRUE.text; } + | FALSE { s = $FALSE.text; } + ; + +INTEGER : ( '-' | '+' )? ('1'..'9' ( '0'..'9' )* | '0') ; + +OR : 'OR' | 'or' ; +AND : 'AND' | 'and' ; +NOT : 'NOT' | 'not' ; +IN : 'IN' | 'in' ; +TRUE : 'TRUE' | 'true' ; +FALSE : 'FALSE' | 'false' ; + +VALUE : ( 'a'..'z' | 'A'..'Z' | '0'..'9' | '_' )+ ; + +STRING + : ( '\'' ( ~('\'') | '\\\'' )* '\'' + | '\"' ( ~('\"') | '\\\"' )* '\"' ) + { setText(Predicate.asciiDecode(getText().substring(1, getText().length() - 1))); } + ; + +WS : (' ' | '\t')+ + {$channel = HIDDEN;} + ; diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/BinaryFormat.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/BinaryFormat.java new file mode 100644 index 00000000000..89dcbc59d99 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/BinaryFormat.java @@ -0,0 +1,167 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import com.yahoo.slime.Cursor; +import com.yahoo.slime.Inspector; +import com.yahoo.slime.Slime; + +import java.util.Objects; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class BinaryFormat { + + final static String NODE_TYPE = "type"; + final static String KEY = "key"; + final static String SET = "feature_set"; + final static String RANGE_MIN = "range_min"; + final static String RANGE_MAX = "range_max"; + final static String CHILDREN = "children"; + final static String PARTITIONS = "partitions"; + final static String EDGE_PARTITIONS = "edge_partitions"; + final static String HASHED_PARTITIONS = "hashed_partitions"; + final static String HASHED_EDGE_PARTITIONS = "hashed_edge_partitions"; + final static String HASH = "hash"; + final static String PAYLOAD = "payload"; + final static String LABEL = "label"; + final static String VALUE = "value"; + final static String LOWER_BOUND = "lower_bound"; + final static String UPPER_BOUND = "upper_bound"; + + final static int TYPE_CONJUNCTION = 1; + final static int TYPE_DISJUNCTION = 2; + final static int TYPE_NEGATION = 3; + final static int TYPE_FEATURE_SET = 4; + final static int TYPE_FEATURE_RANGE = 5; + final static int TYPE_TRUE = 6; + final static int TYPE_FALSE = 7; + + public static byte[] encode(Predicate predicate) { + Objects.requireNonNull(predicate, "predicate"); + Slime slime = new Slime(); + encode(predicate, slime.setObject()); + return com.yahoo.slime.BinaryFormat.encode(slime); + } + + public static Predicate decode(byte[] buf) { + Objects.requireNonNull(buf, "buf"); + Slime slime = com.yahoo.slime.BinaryFormat.decode(buf); + return decode(slime.get()); + } + + private static Predicate decode(Inspector in) { + switch ((int)in.field(NODE_TYPE).asLong()) { + case TYPE_CONJUNCTION: + Conjunction conjunction = new Conjunction(); + in = in.field(CHILDREN); + for (int i = 0, len = in.children(); i < len; ++i) { + conjunction.addOperand(decode(in.entry(i))); + } + return conjunction; + + case TYPE_DISJUNCTION: + Disjunction disjunction = new Disjunction(); + in = in.field(CHILDREN); + for (int i = 0, len = in.children(); i < len; ++i) { + disjunction.addOperand(decode(in.entry(i))); + } + return disjunction; + + case TYPE_NEGATION: + return new Negation(decode(in.field(CHILDREN).entry(0))); + + case TYPE_FEATURE_RANGE: + FeatureRange featureRange = new FeatureRange(in.field(KEY).asString()); + if (in.field(RANGE_MIN).valid()) { + featureRange.setFromInclusive(in.field(RANGE_MIN).asLong()); + } + if (in.field(RANGE_MAX).valid()) { + featureRange.setToInclusive(in.field(RANGE_MAX).asLong()); + } + Inspector p_in = in.field(PARTITIONS); + for (int i = 0, len = p_in.children(); i < len; ++i) { + featureRange.addPartition(new RangePartition(p_in.entry(i).asString())); + } + p_in = in.field(EDGE_PARTITIONS); + for (int i = 0, len = p_in.children(); i < len; ++i) { + Inspector obj = p_in.entry(i); + featureRange.addPartition(new RangeEdgePartition( + obj.field(LABEL).asString(), obj.field(VALUE).asLong(), + (int)obj.field(LOWER_BOUND).asLong(), (int)obj.field(UPPER_BOUND).asLong())); + } + return featureRange; + + case TYPE_FEATURE_SET: + FeatureSet featureSet = new FeatureSet(in.field(KEY).asString()); + in = in.field(SET); + for (int i = 0, len = in.children(); i < len; ++i) { + featureSet.addValue(in.entry(i).asString()); + } + return featureSet; + + case TYPE_TRUE: + return new BooleanPredicate(true); + + case TYPE_FALSE: + return new BooleanPredicate(false); + + default: + throw new UnsupportedOperationException(String.valueOf(in.field(NODE_TYPE).asLong())); + } + } + + private static void encode(Predicate predicate, Cursor out) { + if (predicate instanceof Conjunction) { + out.setLong(NODE_TYPE, TYPE_CONJUNCTION); + out = out.setArray(CHILDREN); + for (Predicate operand : ((Conjunction)predicate).getOperands()) { + encode(operand, out.addObject()); + } + } else if (predicate instanceof Disjunction) { + out.setLong(NODE_TYPE, TYPE_DISJUNCTION); + out = out.setArray(CHILDREN); + for (Predicate operand : ((Disjunction)predicate).getOperands()) { + encode(operand, out.addObject()); + } + } else if (predicate instanceof FeatureRange) { + FeatureRange range = (FeatureRange) predicate; + out.setLong(NODE_TYPE, TYPE_FEATURE_RANGE); + out.setString(KEY, range.getKey()); + Long from = range.getFromInclusive(); + if (from != null) { + out.setLong(RANGE_MIN, from); + } + Long to = range.getToInclusive(); + if (to != null) { + out.setLong(RANGE_MAX, to); + } + Cursor p_out = out.setArray(HASHED_PARTITIONS); + for (RangePartition p : range.getPartitions()) { + p_out.addLong(PredicateHash.hash64(p.getLabel())); + } + p_out = out.setArray(HASHED_EDGE_PARTITIONS); + for (RangeEdgePartition p : range.getEdgePartitions()) { + Cursor obj = p_out.addObject(); + obj.setLong(HASH, PredicateHash.hash64(p.getLabel())); + obj.setLong(VALUE, p.getValue()); + obj.setLong(PAYLOAD, p.encodeBounds()); + } + } else if (predicate instanceof FeatureSet) { + out.setLong(NODE_TYPE, TYPE_FEATURE_SET); + out.setString(KEY, ((FeatureSet)predicate).getKey()); + out = out.setArray(SET); + for (String value : ((FeatureSet)predicate).getValues()) { + out.addString(value); + } + } else if (predicate instanceof Negation) { + out.setLong(NODE_TYPE, TYPE_NEGATION); + out = out.setArray(CHILDREN); + encode(((Negation)predicate).getOperand(), out.addObject()); + } else if (predicate instanceof BooleanPredicate) { + out.setLong(NODE_TYPE, ((BooleanPredicate)predicate).getValue() ? TYPE_TRUE : TYPE_FALSE); + } else { + throw new UnsupportedOperationException(predicate.getClass().getName()); + } + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/BooleanPredicate.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/BooleanPredicate.java new file mode 100644 index 00000000000..507d48bf241 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/BooleanPredicate.java @@ -0,0 +1,54 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class BooleanPredicate extends PredicateValue { + + private boolean value; + + public BooleanPredicate(boolean value) { + this.value = value; + } + + public boolean getValue() { + return value; + } + + public BooleanPredicate setValue(boolean value) { + this.value = value; + return this; + } + + @Override + public BooleanPredicate clone() throws CloneNotSupportedException { + return (BooleanPredicate)super.clone(); + } + + @Override + public int hashCode() { + return value ? Boolean.TRUE.hashCode() : Boolean.FALSE.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof BooleanPredicate)) { + return false; + } + BooleanPredicate rhs = (BooleanPredicate)obj; + if (value != rhs.value) { + return false; + } + return true; + } + + @Override + protected void appendTo(StringBuilder out) { + out.append(value ? "true" : "false"); + } + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/Conjunction.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Conjunction.java new file mode 100644 index 00000000000..d917e374b69 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Conjunction.java @@ -0,0 +1,93 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collection; +import java.util.Iterator; +import java.util.List; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class Conjunction extends PredicateOperator { + + private List<Predicate> operands; + + public Conjunction(Predicate... operands) { + this(Arrays.asList(operands)); + } + + public Conjunction(List<? extends Predicate> operands) { + this.operands = new ArrayList<>(operands); + } + + public Conjunction addOperand(Predicate operand) { + operands.add(operand); + return this; + } + + public Conjunction addOperands(Collection<? extends Predicate> operands) { + this.operands.addAll(operands); + return this; + } + + public Conjunction setOperands(Collection<? extends Predicate> operands) { + this.operands.clear(); + this.operands.addAll(operands); + return this; + } + + @Override + public List<Predicate> getOperands() { + return operands; + } + + @Override + public Conjunction clone() throws CloneNotSupportedException { + Conjunction obj = (Conjunction)super.clone(); + obj.operands = new ArrayList<>(operands.size()); + for (Predicate operand : operands) { + obj.operands.add(operand.clone()); + } + return obj; + } + + @Override + public int hashCode() { + return operands.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof Conjunction)) { + return false; + } + Conjunction rhs = (Conjunction)obj; + if (!operands.equals(rhs.operands)) { + return false; + } + return true; + } + + @Override + protected void appendTo(StringBuilder out) { + for (Iterator<Predicate> it = operands.iterator(); it.hasNext(); ) { + Predicate operand = it.next(); + if (operand instanceof Disjunction || operand instanceof FeatureConjunction) { + out.append('('); + operand.appendTo(out); + out.append(')'); + } else { + operand.appendTo(out); + } + if (it.hasNext()) { + out.append(" and "); + } + } + } + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/Disjunction.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Disjunction.java new file mode 100644 index 00000000000..c5fa6ba1f70 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Disjunction.java @@ -0,0 +1,93 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collection; +import java.util.Iterator; +import java.util.List; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class Disjunction extends PredicateOperator { + + private List<Predicate> operands; + + public Disjunction(Predicate... operands) { + this(Arrays.asList(operands)); + } + + public Disjunction(List<? extends Predicate> operands) { + this.operands = new ArrayList<>(operands); + } + + public Disjunction addOperand(Predicate operand) { + operands.add(operand); + return this; + } + + public Disjunction addOperands(Collection<? extends Predicate> operands) { + this.operands.addAll(operands); + return this; + } + + public Disjunction setOperands(Collection<? extends Predicate> operands) { + this.operands.clear(); + this.operands.addAll(operands); + return this; + } + + @Override + public List<Predicate> getOperands() { + return operands; + } + + @Override + public Disjunction clone() throws CloneNotSupportedException { + Disjunction obj = (Disjunction)super.clone(); + obj.operands = new ArrayList<>(operands.size()); + for (Predicate operand : operands) { + obj.operands.add(operand.clone()); + } + return obj; + } + + @Override + public int hashCode() { + return operands.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof Disjunction)) { + return false; + } + Disjunction rhs = (Disjunction)obj; + if (!operands.equals(rhs.operands)) { + return false; + } + return true; + } + + @Override + protected void appendTo(StringBuilder out) { + for (Iterator<Predicate> it = operands.iterator(); it.hasNext(); ) { + Predicate operand = it.next(); + if (operand instanceof Conjunction) { + out.append('('); + operand.appendTo(out); + out.append(')'); + } else { + operand.appendTo(out); + } + if (it.hasNext()) { + out.append(" or "); + } + } + } + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureConjunction.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureConjunction.java new file mode 100644 index 00000000000..ba6bb32e05f --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureConjunction.java @@ -0,0 +1,104 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; + +/** + * A FeatureConjunction is a special type of Conjunction where + * all children are either a FeatureSet or a Negation (with an underlying FeatureSet). + * The underlying FeatureSets may only have one value. + * + * @author bjorncs + */ +public class FeatureConjunction extends PredicateOperator { + private final List<Predicate> operands; + + public FeatureConjunction(List<Predicate> operands) { + validateOperands(operands); + this.operands = new ArrayList<>(operands); + } + + private static void validateOperands(List<Predicate> operands) { + if (operands.size() <= 1) { + throw new IllegalArgumentException("Number of operands must 2 or more, was: " + operands.size()); + } + if (!operands.stream() + .allMatch(FeatureConjunction::isValidFeatureConjunctionOperand)) { + throw new IllegalArgumentException( + "A FeatureConjunction may only contain instances of Negation and FeatureSet, " + + "and a FeatureSet may only have one value."); + } + + long uniqueKeys = operands.stream().map(FeatureConjunction::getFeatureSetKey).distinct().count(); + if (operands.size() > uniqueKeys) { + throw new IllegalArgumentException("Each FeatureSet key must have a unique key."); + } + } + + private static String getFeatureSetKey(Predicate predicate) { + if (predicate instanceof FeatureSet) { + return ((FeatureSet) predicate).getKey(); + } else { + Negation negation = (Negation) predicate; + return ((FeatureSet) negation.getOperand()).getKey(); + } + } + + public static boolean isValidFeatureConjunctionOperand(Predicate operand) { + return operand instanceof Negation + && ((Negation) operand).getOperand() instanceof FeatureSet + && isValidFeatureConjunctionOperand(((Negation) operand).getOperand()) + || operand instanceof FeatureSet && ((FeatureSet) operand).getValues().size() == 1; + } + + @Override + public List<Predicate> getOperands() { + return operands; + } + + @Override + protected void appendTo(StringBuilder out) { + for (Iterator<Predicate> it = operands.iterator(); it.hasNext(); ) { + Predicate operand = it.next(); + if (operand instanceof Disjunction) { + out.append('('); + operand.appendTo(out); + out.append(')'); + } else { + operand.appendTo(out); + } + if (it.hasNext()) { + out.append(" conj "); + } + } + } + + @Override + public FeatureConjunction clone() throws CloneNotSupportedException { + return new FeatureConjunction(operands); + } + + @Override + public int hashCode() { + return operands.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof FeatureConjunction)) { + return false; + } + FeatureConjunction rhs = (FeatureConjunction)obj; + if (!operands.equals(rhs.operands)) { + return false; + } + return true; + } + + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureRange.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureRange.java new file mode 100644 index 00000000000..2ca09ee98f0 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureRange.java @@ -0,0 +1,190 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import java.util.ArrayList; +import java.util.List; +import java.util.Objects; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class FeatureRange extends PredicateValue { + + private String key; + private Long from; + private Long to; + private List<RangePartition> partitions; + private List<RangeEdgePartition> edgePartitions; + + public FeatureRange(String key) { + this(key, null, null); + } + + public FeatureRange(String key, Long fromInclusive, Long toInclusive) { + setKey(key); + setFromInclusive(fromInclusive); + setToInclusive(toInclusive); + partitions = new ArrayList<>(); + edgePartitions = new ArrayList<>(); + } + + public FeatureRange setKey(String key) { + Objects.requireNonNull(key, "key"); + this.key = key; + return this; + } + + public String getKey() { + return key; + } + + public FeatureRange setFromInclusive(Long from) { + if (from != null && to != null && from > to) { + throw new IllegalArgumentException("Expected 'from' less than or equal to " + to + ", got " + from + "."); + } + this.from = from; + return this; + } + + public Long getFromInclusive() { + return from; + } + + public FeatureRange setToInclusive(Long to) { + if (from != null && to != null && from > to) { + throw new IllegalArgumentException("Expected 'to' greater than or equal to " + from + ", got " + to + "."); + } + this.to = to; + return this; + } + + public Long getToInclusive() { + return to; + } + + public void addPartition(RangePartition p) { + if (p instanceof RangeEdgePartition) { + edgePartitions.add((RangeEdgePartition)p); + } else { + partitions.add(p); + } + } + + public List<RangeEdgePartition> getEdgePartitions() { + return edgePartitions; + } + + public List<RangePartition> getPartitions() { + return partitions; + } + + public void clearPartitions() { + partitions.clear(); + edgePartitions.clear(); + } + + @Override + public FeatureRange clone() throws CloneNotSupportedException { + return (FeatureRange)super.clone(); + } + + @Override + public int hashCode() { + return ((key.hashCode() + (from != null ? from.hashCode() : 0)) * 31 + (to != null ? to.hashCode() : 0)) * 31; + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof FeatureRange)) { + return false; + } + FeatureRange rhs = (FeatureRange)obj; + if (!key.equals(rhs.key)) { + return false; + } + if (!Objects.equals(from, rhs.from)) { + return false; + } + if (!Objects.equals(to, rhs.to)) { + return false; + } + return partitions.equals(rhs.partitions) && edgePartitions.equals(rhs.edgePartitions); + } + + @Override + protected void appendTo(StringBuilder out) { + appendQuotedTo(key, out); + out.append(" in ["); + if (from != null) { + out.append(from); + } + out.append(".."); + if (to != null) { + out.append(to); + } + if (!partitions.isEmpty() || !edgePartitions.isEmpty()) { + out.append(" ("); + for (RangeEdgePartition p : edgePartitions) { + p.appendTo(out); + out.append(','); + } + for (RangePartition p : partitions) { + p.appendTo(out); + out.append(','); + } + out.deleteCharAt(out.length() - 1); // Remove extra ',' + out.append(")"); + } + out.append("]"); + } + + public static FeatureRange buildFromMixedIn(String key, List<String> partitions, int arity) { + Long fromInclusive = null; + Long toInclusive = null; + long from = 0; + long to = 0; + for (String p : partitions) { + String[] parts = p.split(","); + if (parts.length == 1) { + String[] subparts = parts[0].split("=|-"); + int offset = subparts.length == 3? 0 : 1; + if (subparts.length < 3 || subparts.length > 4) { + throw new IllegalArgumentException("MIXED_IN range partition must be on the form label=val-val"); + } + from = Long.parseLong(subparts[offset + 1]); + to = Long.parseLong(subparts[offset + 2]); + if (parts[0].contains("=-")) { + long tmp = from; + from = -to; + to = -tmp; + } + } else { + if (parts.length != 3) { + throw new IllegalArgumentException("MIXED_IN range edge partition must be on the form label=val,val,payload"); + } + long value = Long.parseLong(parts[1]); + long payload = Long.parseLong(parts[2]); + if ((payload & 0xc0000000) == 0x80000000L) { + from = value + (payload & 0xffff); + to = value + arity - 1; + } else if ((payload & 0xc0000000) == 0x40000000L) { + from = value; + to = value + (payload & 0xffff); + } else { + from = value + (payload >> 16); + to = value + (payload & 0xffff); + } + } + if (fromInclusive == null || fromInclusive > from) { + fromInclusive = from; + } + if (toInclusive == null || toInclusive > to) { + toInclusive = to; + } + } + return new FeatureRange(key, fromInclusive, toInclusive); + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureSet.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureSet.java new file mode 100644 index 00000000000..be560514995 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureSet.java @@ -0,0 +1,119 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import java.util.Arrays; +import java.util.Collection; +import java.util.Iterator; +import java.util.Objects; +import java.util.Set; +import java.util.TreeSet; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class FeatureSet extends PredicateValue { + + private Set<String> values; + private String key; + + public FeatureSet(String key, String... values) { + this(key, Arrays.asList(values)); + } + + public FeatureSet(String key, Collection<String> values) { + Objects.requireNonNull(key, "key"); + if (values == null) { + throw new NullPointerException("values"); + } + this.key = key; + this.values = new TreeSet<>(values); + } + + public FeatureSet setKey(String key) { + Objects.requireNonNull(key, "key"); + this.key = key; + return this; + } + + public String getKey() { + return key; + } + + public FeatureSet addValue(String value) { + Objects.requireNonNull(value, "value"); + values.add(value); + return this; + } + + public FeatureSet addValues(Collection<String> values) { + if (values == null) { + throw new NullPointerException("values"); + } + this.values.addAll(values); + return this; + } + + public FeatureSet setValues(Collection<String> values) { + if (values == null) { + throw new NullPointerException("values"); + } + this.values.clear(); + this.values.addAll(values); + return this; + } + + public Set<String> getValues() { + return values; + } + + @Override + public FeatureSet clone() throws CloneNotSupportedException { + FeatureSet obj = (FeatureSet)super.clone(); + obj.values = new TreeSet<>(values); + return obj; + } + + @Override + public int hashCode() { + return (key.hashCode() + values.hashCode()) * 31; + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof FeatureSet)) { + return false; + } + FeatureSet rhs = (FeatureSet)obj; + if (!key.equals(rhs.key)) { + return false; + } + if (!values.equals(rhs.values)) { + return false; + } + return true; + } + + @Override + protected void appendTo(StringBuilder out) { + appendInAsTo("in", out); + } + + protected void appendNegatedTo(StringBuilder out) { + appendInAsTo("not in", out); + } + + private void appendInAsTo(String in, StringBuilder out) { + appendQuotedTo(key, out); + out.append(' ').append(in).append(" ["); + for (Iterator<String> it = values.iterator(); it.hasNext(); ) { + appendQuotedTo(it.next(), out); + if (it.hasNext()) { + out.append(", "); + } + } + out.append("]"); + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/Negation.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Negation.java new file mode 100644 index 00000000000..c5a4cb802ee --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Negation.java @@ -0,0 +1,72 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import java.util.List; +import java.util.Objects; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class Negation extends PredicateOperator { + + private Predicate operand; + + public Negation(Predicate operand) { + Objects.requireNonNull(operand, "operand"); + this.operand = operand; + } + + public Negation setOperand(Predicate operand) { + Objects.requireNonNull(operand, "operand"); + this.operand = operand; + return this; + } + + public Predicate getOperand() { + return operand; + } + + @Override + public List<Predicate> getOperands() { + return java.util.Arrays.asList(operand); + } + + @Override + public Negation clone() throws CloneNotSupportedException { + Negation obj = (Negation)super.clone(); + obj.operand = operand.clone(); + return obj; + } + + @Override + public int hashCode() { + return operand.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof Negation)) { + return false; + } + Negation rhs = (Negation)obj; + if (!operand.equals(rhs.operand)) { + return false; + } + return true; + } + + @Override + protected void appendTo(StringBuilder out) { + if (operand instanceof FeatureSet) { + ((FeatureSet)operand).appendNegatedTo(out); + } else { + out.append("not ("); + operand.appendTo(out); + out.append(')'); + } + } + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/Predicate.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Predicate.java new file mode 100644 index 00000000000..2446d3e3524 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Predicate.java @@ -0,0 +1,79 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import com.yahoo.document.predicate.parser.PredicateLexer; +import com.yahoo.document.predicate.parser.PredicateParser; +import com.yahoo.text.Ascii; +import org.antlr.runtime.ANTLRStringStream; +import org.antlr.runtime.CommonTokenStream; +import org.antlr.runtime.RecognitionException; + +import java.nio.charset.StandardCharsets; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public abstract class Predicate implements Cloneable { + + private final static char QUOTE_CHAR = '\''; + private final static Ascii.Encoder ASCII_ENCODER = Ascii.newEncoder(StandardCharsets.UTF_8, QUOTE_CHAR); + private final static Ascii.Decoder ASCII_DECODER = Ascii.newDecoder(StandardCharsets.UTF_8); + + @Override + public Predicate clone() throws CloneNotSupportedException { + return (Predicate)super.clone(); + } + + @Override + public final String toString() { + StringBuilder out = new StringBuilder(); + appendTo(out); + return out.toString(); + } + + protected abstract void appendTo(StringBuilder out); + + protected static void appendQuotedTo(String str, StringBuilder out) { + String encoded = asciiEncode(str); + if (requiresQuote(encoded)) { + out.append(QUOTE_CHAR).append(encoded).append(QUOTE_CHAR); + } else { + out.append(str); + } + } + + private static boolean requiresQuote(String str) { + for (int i = 0, len = str.length(); i < len; i = str.offsetByCodePoints(i, 1)) { + int c = str.codePointAt(i); + if (c == Ascii.ESCAPE_CHAR || !Character.isLetterOrDigit(c)) { + return true; + } + } + return false; + } + + public static String asciiEncode(String str) { + return ASCII_ENCODER.encode(str); + } + + public static String asciiDecode(String str) { + return ASCII_DECODER.decode(str); + } + + public static Predicate fromBinary(byte[] buf) { + return BinaryFormat.decode(buf); + } + + public static Predicate fromString(String str) { + ANTLRStringStream input = new ANTLRStringStream(str); + PredicateLexer lexer = new PredicateLexer(input); + CommonTokenStream tokens = new CommonTokenStream(lexer); + PredicateParser parser = new PredicateParser(tokens); + try { + return parser.predicate(); + } catch (RecognitionException e) { + throw new IllegalArgumentException(e); + } + } + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateHash.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateHash.java new file mode 100644 index 00000000000..8c0c9ee590e --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateHash.java @@ -0,0 +1,111 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + + +import com.yahoo.text.Utf8; + +/** + * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + * This hash function must match the corresponding C++ hash function in 'ConvertClass', + * currently located at 'rise_platform/src/interface/cpp/api/ConvertClass.h' + */ +public class PredicateHash { + @SuppressWarnings("fallthrough") + public static long hash64(String s) { + byte[] bytes = Utf8.toBytes(s); + long a=0L, b=0L; + long c=0x9e3779b97f4a7c13L; + int len = bytes.length; + int offset = 0; + while (len >= 24) { + c += ((0xffL & (long)bytes[offset + 23]) << 56) + + ((0xffL & (long)bytes[offset + 22]) << 48) + + ((0xffL & (long)bytes[offset + 21]) << 40) + + ((0xffL & (long)bytes[offset + 20]) << 32) + + ((0xffL & (long)bytes[offset + 19]) << 24) + + ((0xffL & (long)bytes[offset + 18]) << 16) + + ((0xffL & (long)bytes[offset + 17]) << 8) + + ((0xffL & (long)bytes[offset + 16])); + + b += ((0xffL & (long)bytes[offset + 15]) << 56) + + ((0xffL & (long)bytes[offset + 14]) << 48) + + ((0xffL & (long)bytes[offset + 13]) << 40) + + ((0xffL & (long)bytes[offset + 12]) << 32) + + ((0xffL & (long)bytes[offset + 11]) << 24) + + ((0xffL & (long)bytes[offset + 10]) << 16) + + ((0xffL & (long)bytes[offset + 9]) << 8) + + ((0xffL & (long)bytes[offset + 8])); + + a += ((0xffL & (long)bytes[offset + 7]) << 56) + + ((0xffL & (long)bytes[offset + 6]) << 48) + + ((0xffL & (long)bytes[offset + 5]) << 40) + + ((0xffL & (long)bytes[offset + 4]) << 32) + + ((0xffL & (long)bytes[offset + 3]) << 24) + + ((0xffL & (long)bytes[offset + 2]) << 16) + + ((0xffL & (long)bytes[offset + 1]) << 8) + + ((0xffL & (long)bytes[offset + 0])); + + // Mix. This arithmetic must match the mix below. + a -= b; a -= c; a ^= (c>>>43); + b -= c; b -= a; b ^= (a<<9); + c -= a; c -= b; c ^= (b>>>8); + a -= b; a -= c; a ^= (c>>>38); + b -= c; b -= a; b ^= (a<<23); + c -= a; c -= b; c ^= (b>>>5); + a -= b; a -= c; a ^= (c>>>35); + b -= c; b -= a; b ^= (a<<49); + c -= a; c -= b; c ^= (b>>>11); + a -= b; a -= c; a ^= (c>>>12); + b -= c; b -= a; b ^= (a<<18); + c -= a; c -= b; c ^= (b>>>22); + // End mix. + + offset += 24; + len -= 24; + } + + c += bytes.length; + switch (len) { + case 23: c+= (0xffL & (long)bytes[offset + 22]) << 56; + case 22: c+= (0xffL & (long)bytes[offset + 21]) << 48; + case 21: c+= (0xffL & (long)bytes[offset + 20]) << 40; + case 20: c+= (0xffL & (long)bytes[offset + 19]) << 32; + case 19: c+= (0xffL & (long)bytes[offset + 18]) << 24; + case 18: c+= (0xffL & (long)bytes[offset + 17]) << 16; + case 17: c+= (0xffL & (long)bytes[offset + 16]) << 8; + // The first byte of c is reserved for the length + case 16: b+= (0xffL & (long)bytes[offset + 15]) << 56; + case 15: b+= (0xffL & (long)bytes[offset + 14]) << 48; + case 14: b+= (0xffL & (long)bytes[offset + 13]) << 40; + case 13: b+= (0xffL & (long)bytes[offset + 12]) << 32; + case 12: b+= (0xffL & (long)bytes[offset + 11]) << 24; + case 11: b+= (0xffL & (long)bytes[offset + 10]) << 16; + case 10: b+= (0xffL & (long)bytes[offset + 9]) << 8; + case 9: b+= (0xffL & (long)bytes[offset + 8]); + case 8: a+= (0xffL & (long)bytes[offset + 7]) << 56; + case 7: a+= (0xffL & (long)bytes[offset + 6]) << 48; + case 6: a+= (0xffL & (long)bytes[offset + 5]) << 40; + case 5: a+= (0xffL & (long)bytes[offset + 4]) << 32; + case 4: a+= (0xffL & (long)bytes[offset + 3]) << 24; + case 3: a+= (0xffL & (long)bytes[offset + 2]) << 16; + case 2: a+= (0xffL & (long)bytes[offset + 1]) << 8; + case 1: a+= (0xffL & (long)bytes[offset + 0]); + } + // Mix. This arithmetic must match the mix above. + a -= b; a -= c; a ^= (c>>>43); + b -= c; b -= a; b ^= (a<<9); + c -= a; c -= b; c ^= (b>>>8); + a -= b; a -= c; a ^= (c>>>38); + b -= c; b -= a; b ^= (a<<23); + c -= a; c -= b; c ^= (b>>>5); + a -= b; a -= c; a ^= (c>>>35); + b -= c; b -= a; b ^= (a<<49); + c -= a; c -= b; c ^= (b>>>11); + a -= b; a -= c; a ^= (c>>>12); + b -= c; b -= a; b ^= (a<<18); + c -= a; c -= b; c ^= (b>>>22); + // End mix. + + return c; + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateOperator.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateOperator.java new file mode 100644 index 00000000000..0c0af37a791 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateOperator.java @@ -0,0 +1,12 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import java.util.List; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +abstract public class PredicateOperator extends Predicate { + + public abstract List<Predicate> getOperands(); +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateValue.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateValue.java new file mode 100644 index 00000000000..f34a8f4b268 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateValue.java @@ -0,0 +1,9 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +abstract class PredicateValue extends Predicate { + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/Predicates.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Predicates.java new file mode 100644 index 00000000000..7362eb5ba6d --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Predicates.java @@ -0,0 +1,69 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class Predicates { + + public static Conjunction and(Predicate... operands) { + return new Conjunction(operands); + } + + public static Disjunction or(Predicate... operands) { + return new Disjunction(operands); + } + + public static Negation not(Predicate operand) { + return new Negation(operand); + } + + public static BooleanPredicate value(boolean value) { + return new BooleanPredicate(value); + } + + public static FeatureBuilder feature(String key) { + return new FeatureBuilder(key); + } + + public static class FeatureBuilder { + + private final String key; + + public FeatureBuilder(String key) { + this.key = key; + } + + public FeatureRange lessThan(long toExclusive) { + return new FeatureRange(key, null, toExclusive - 1); + } + + public FeatureRange lessThanOrEqualTo(long toInclusive) { + return new FeatureRange(key, null, toInclusive); + } + + public FeatureRange greaterThan(long fromExclusive) { + return new FeatureRange(key, fromExclusive + 1, null); + } + + public FeatureRange greaterThanOrEqualTo(long fromInclusive) { + return new FeatureRange(key, fromInclusive, null); + } + + public FeatureRange inRange(long fromInclusive, long toInclusive) { + return new FeatureRange(key, fromInclusive, toInclusive); + } + + public Negation notInRange(long fromInclusive, long toInclusive) { + return new Negation(new FeatureRange(key, fromInclusive, toInclusive)); + } + + public FeatureSet inSet(String... values) { + return new FeatureSet(key, values); + } + + public Negation notInSet(String... values) { + return new Negation(new FeatureSet(key, values)); + } + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/RangeEdgePartition.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/RangeEdgePartition.java new file mode 100644 index 00000000000..0771f0ec08e --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/RangeEdgePartition.java @@ -0,0 +1,86 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +/** + * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + */ +public class RangeEdgePartition extends RangePartition { + private final long value; + private final int lowerBound; + private final int upperBound; + + public RangeEdgePartition(String label, long value, int lower, int upper) { + super(label); + this.value = value; + this.lowerBound = lower; + this.upperBound = upper; + } + + public long getValue() { + return value; + } + + public int getLowerBound() { + return lowerBound; + } + + public int getUpperBound() { + return upperBound; + } + + @Override + public RangeEdgePartition clone() throws CloneNotSupportedException { + return (RangeEdgePartition)super.clone(); + } + + @Override + public int hashCode() { + return super.hashCode() + new Long(value).hashCode() + + new Integer(lowerBound).hashCode() + new Integer(upperBound).hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof RangeEdgePartition)) { + return false; + } + RangeEdgePartition other = (RangeEdgePartition)obj; + return super.equals(other) && + value == other.value && + lowerBound == other.lowerBound && + upperBound == other.upperBound; + } + + @Override + protected void appendTo(StringBuilder out) { + super.appendTo(out); + + out.append("+["); + if (lowerBound > 0) + out.append(lowerBound); + out.append(".."); + if (upperBound >= 0) + out.append(upperBound); + out.append(']'); + } + + public long encodeBounds() { + if (lowerBound > 0) { + if (upperBound >= 0) { + return lowerBound << 16 | (upperBound + 1); + } else { + return lowerBound | 0x80000000L; + } + } else { + if (upperBound >= 0) { + return (upperBound + 1) | 0x40000000; + } else { + return 0x80000000L; // >0 + } + } + } + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/RangePartition.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/RangePartition.java new file mode 100644 index 00000000000..33cdd23c45c --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/RangePartition.java @@ -0,0 +1,67 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +/** + * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + */ +public class RangePartition extends PredicateValue { + + private String label; + + public RangePartition(String label) { + this.label = label; + } + + public RangePartition(String key, long fromInclusive, long toInclusive, boolean isNeg) { + this(makeLabel(key, fromInclusive, toInclusive, isNeg)); + } + + private static String makeLabel(String key, long fromInclusive, long toInclusive, boolean isNeg) { + if (isNeg) { + // special case for toInclusive==long_min: It will print its own hyphen. + return key + "=" + (toInclusive==0x8000000000000000L? "" : "-") + toInclusive + "-" + fromInclusive; + } else { + // special case for toInclusive==long_min: It will print its own hyphen. + return key + "=" + fromInclusive + (toInclusive==0x8000000000000000L? "" : "-") + toInclusive; + } + } + + public String getLabel() { + return label; + } + + @Override + public RangePartition clone() throws CloneNotSupportedException { + return (RangePartition)super.clone(); + } + + @Override + public int hashCode() { + return label.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof RangePartition)) { + return false; + } + return label.equals(((RangePartition)obj).getLabel()); + } + + @Override + protected void appendTo(StringBuilder out) { + int i = label.lastIndexOf('='); + appendQuotedTo(label.substring(0, i), out); + if (out.charAt(out.length() - 1) == '\'') { + out.deleteCharAt(out.length() - 1); + out.append(label.substring(i)); + out.append('\''); + } else { + out.append(label.substring(i)); + } + } + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/SimplePredicates.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/SimplePredicates.java new file mode 100644 index 00000000000..1b339767109 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/SimplePredicates.java @@ -0,0 +1,70 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import java.util.ArrayList; +import java.util.List; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class SimplePredicates { + + public static Predicate newPredicate() { + return new Predicate() { + + @Override + protected void appendTo(StringBuilder out) { + out.append("<anon>"); + } + + }; + } + + public static Predicate newString(String str) { + return new StringNode(str); + } + + public static List<Predicate> newStrings(String... arr) { + List<Predicate> ret = new ArrayList<>(arr.length); + for (String str : arr) { + ret.add(newString(str)); + } + return ret; + } + + private static class StringNode extends Predicate { + + final String str; + + StringNode(String str) { + this.str = str; + } + + @Override + public int hashCode() { + return str.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof StringNode)) { + return false; + } + StringNode rhs = (StringNode)obj; + if (!str.equals(rhs.str)) { + return false; + } + return true; + } + + @Override + protected void appendTo(StringBuilder out) { + out.append(str); + } + + } +} + diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/package-info.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/package-info.java new file mode 100644 index 00000000000..ef3b6954992 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/package-info.java @@ -0,0 +1,8 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +@com.yahoo.osgi.annotation.ExportPackage +@com.yahoo.api.annotations.PublicApi +/* + The predicate package is exported by the document module (OSGi). + Do not remove unless the intention is to modify the public API of document. + */ +package com.yahoo.document.predicate; diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/PredicateQueryParser.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/PredicateQueryParser.java new file mode 100644 index 00000000000..6f5fac54354 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/PredicateQueryParser.java @@ -0,0 +1,132 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate; + +import com.fasterxml.jackson.core.JsonFactory; +import com.fasterxml.jackson.core.JsonParser; +import com.fasterxml.jackson.core.JsonToken; +import org.apache.commons.lang.ArrayUtils; + +import java.io.IOException; +import java.util.Arrays; + +/** + * Parses predicate queries from JSON. + * + * Input JSON is assumed to have the following format: + * { + * "features": [ + * {"k": "key-name", "v":"value", "s":"0xDEADBEEFDEADBEEF"} + * ], + * "rangeFeatures": [ + * {"k": "key-name", "v":42, "s":"0xDEADBEEFDEADBEEF"} + * ] + * } + * + * @author bjorncs + */ +public class PredicateQueryParser { + private final JsonFactory factory = new JsonFactory(); + + @FunctionalInterface + public interface FeatureHandler<V> { + void accept(String key, V value, long subqueryBitmap); + } + + /** + * Parses predicate query from JSON. + * @param json JSON input. + * @param featureHandler The handler is invoked when a feature is parsed. + * @param rangeFeatureHandler The handler is invoked when a range feature is parsed. + * @throws IllegalArgumentException If JSON is invalid. + */ + public void parseJsonQuery( + String json, FeatureHandler<String> featureHandler, FeatureHandler<Long> rangeFeatureHandler) + throws IllegalArgumentException { + + try (JsonParser parser = factory.createParser(json)) { + skipToken(parser, JsonToken.START_OBJECT); + while (parser.nextToken() != JsonToken.END_OBJECT) { + String fieldName = parser.getCurrentName(); + switch (fieldName) { + case "features": + parseFeatures(parser, JsonParser::getText, featureHandler); + break; + case "rangeFeatures": + parseFeatures(parser, JsonParser::getLongValue, rangeFeatureHandler); + break; + default: + throw new IllegalArgumentException("Invalid field name: " + fieldName); + } + } + } catch (IllegalArgumentException e) { + throw e; + } catch (IOException e) { + throw new AssertionError("This should never happen when parsing from a String", e); + } catch (Exception e) { + throw new IllegalArgumentException(String.format("Parsing query from JSON failed: '%s'", json), e); + } + } + + private static <V> void parseFeatures( + JsonParser parser, ValueParser<V> valueParser, FeatureHandler<V> featureHandler) throws IOException { + skipToken(parser, JsonToken.START_ARRAY); + while (parser.nextToken() != JsonToken.END_ARRAY) { + parseFeature(parser, valueParser, featureHandler); + } + } + + private static <V> void parseFeature( + JsonParser parser, ValueParser<V> valueParser, FeatureHandler<V> featureHandler) throws IOException { + String key = null; + V value = null; + long subqueryBitmap = SubqueryBitmap.DEFAULT_VALUE; // Specifying subquery bitmap is optional. + + while (parser.nextToken() != JsonToken.END_OBJECT) { + String fieldName = parser.getCurrentName(); + skipToken(parser, JsonToken.VALUE_STRING, JsonToken.VALUE_NUMBER_INT); + switch (fieldName) { + case "k": + key = parser.getText(); + break; + case "v": + value = valueParser.parse(parser); + break; + case "s": + subqueryBitmap = fromHexString(parser.getText()); + break; + default: + throw new IllegalArgumentException("Invalid field name: " + fieldName); + } + } + if (key == null) { + throw new IllegalArgumentException( + String.format("Feature key is missing! (%s)", parser.getCurrentLocation())); + } + if (value == null) { + throw new IllegalArgumentException( + String.format("Feature value is missing! (%s)", parser.getCurrentLocation())); + } + featureHandler.accept(key, value, subqueryBitmap); + } + + private static void skipToken(JsonParser parser, JsonToken... expected) throws IOException { + JsonToken actual = parser.nextToken(); + if (!ArrayUtils.contains(expected, actual)) { + throw new IllegalArgumentException( + String.format("Expected a token in %s, got %s (%s).", + Arrays.toString(expected), actual, parser.getTokenLocation())); + } + } + + private static long fromHexString(String subqueryBitmap) { + if (!subqueryBitmap.startsWith("0x")) { + throw new IllegalArgumentException("Not a valid subquery bitmap ('0x' prefix missing): " + subqueryBitmap); + } + return Long.parseUnsignedLong(subqueryBitmap.substring(2), 16); + } + + @FunctionalInterface + private interface ValueParser<V> { + V parse(JsonParser parser) throws IOException; + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/SubqueryBitmap.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/SubqueryBitmap.java new file mode 100644 index 00000000000..84b342f930a --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/SubqueryBitmap.java @@ -0,0 +1,21 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate; + +/** + * Constants related to the subquery bitmap in predicate/boolean search. + * @author bjorncs + */ +public interface SubqueryBitmap { + + /** + * A feature annotated with the following bitmap will be added to all (64) subqueries. + */ + long ALL_SUBQUERIES = 0xFFFF_FFFF_FFFF_FFFFl; + + /** + * Default subquery bitmap. + */ + long DEFAULT_VALUE = ALL_SUBQUERIES; + + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/AndOrSimplifier.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/AndOrSimplifier.java new file mode 100644 index 00000000000..b281f98a94a --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/AndOrSimplifier.java @@ -0,0 +1,70 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import com.yahoo.document.predicate.Conjunction; +import com.yahoo.document.predicate.Disjunction; +import com.yahoo.document.predicate.Negation; +import com.yahoo.document.predicate.Predicate; + +import java.util.ArrayList; +import java.util.List; + +/** + * Simplifies a predicate by: + * - Combining child-AND/OR nodes with direct parents of the same type + * - Pushing negations down to leaf nodes by using De Morgan's law. + * + * @author magnarn + * @author bjorncs + */ +public class AndOrSimplifier implements PredicateProcessor { + + public Predicate simplifySubTree(Predicate predicate, boolean negated) { + if (predicate == null) { + return null; + } + if (predicate instanceof Negation) { + return simplifySubTree(((Negation) predicate).getOperand(), !negated); + } else if (predicate instanceof Conjunction) { + List<Predicate> in = ((Conjunction)predicate).getOperands(); + List<Predicate> out = new ArrayList<>(in.size()); + for (Predicate operand : in) { + operand = simplifySubTree(operand, negated); + if (operand instanceof Conjunction) { + out.addAll(((Conjunction)operand).getOperands()); + } else { + out.add(operand); + } + } + if (negated) { + return new Disjunction(out); + } + ((Conjunction)predicate).setOperands(out); + } else if (predicate instanceof Disjunction) { + List<Predicate> in = ((Disjunction)predicate).getOperands(); + List<Predicate> out = new ArrayList<>(in.size()); + for (Predicate operand : in) { + operand = simplifySubTree(operand, negated); + if (operand instanceof Disjunction) { + out.addAll(((Disjunction)operand).getOperands()); + } else { + out.add(operand); + } + } + if (negated) { + return new Conjunction(out); + } + ((Disjunction)predicate).setOperands(out); + } else { + if (negated) { + return new Negation(predicate); + } + } + return predicate; + } + + @Override + public Predicate process(Predicate predicate, PredicateOptions options) { + return simplifySubTree(predicate, false); + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/BooleanSimplifier.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/BooleanSimplifier.java new file mode 100644 index 00000000000..fd1fed8ae15 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/BooleanSimplifier.java @@ -0,0 +1,93 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import com.yahoo.document.predicate.BooleanPredicate; +import com.yahoo.document.predicate.Conjunction; +import com.yahoo.document.predicate.Disjunction; +import com.yahoo.document.predicate.Negation; +import com.yahoo.document.predicate.Predicate; +import com.yahoo.document.predicate.PredicateOperator; + +import java.util.ArrayList; +import java.util.List; + +/** + * Simplifies a predicate by collapsing TRUE/FALSE-children into their parents. + * E.g. if an AND node has a FALSE child, the entire node is replaced by FALSE. + * Replaces single-child AND/OR-nodes with the child. + * + * @author magnarn + * @author bjorncs + */ +public class BooleanSimplifier implements PredicateProcessor { + + public Predicate simplifySubTree(Predicate predicate) { + if (predicate == null) { + return null; + } + if (predicate instanceof Conjunction) { + List<Predicate> in = ((PredicateOperator)predicate).getOperands(); + List<Predicate> out = new ArrayList<>(in.size()); + for (Predicate operand : in) { + operand = simplifySubTree(operand); + if (isFalse(operand)) { + return new BooleanPredicate(false); + } else if (!isTrue(operand)) { + out.add(operand); + } + } + if (out.size() == 1) { + return out.get(0); + } else if (out.size() == 0) { + return new BooleanPredicate(true); + } + ((Conjunction)predicate).setOperands(out); + } else if (predicate instanceof Disjunction) { + List<Predicate> in = ((PredicateOperator)predicate).getOperands(); + List<Predicate> out = new ArrayList<>(in.size()); + for (Predicate operand : in) { + operand = simplifySubTree(operand); + if (isTrue(operand)) { + return new BooleanPredicate(true); + } else if (!isFalse(operand)) { + out.add(operand); + } + } + if (out.size() == 1) { + return out.get(0); + } else if (out.size() == 0) { + return new BooleanPredicate(false); + } + ((Disjunction)predicate).setOperands(out); + } else if (predicate instanceof Negation) { + Predicate operand = ((Negation)predicate).getOperand(); + operand = simplifySubTree(operand); + if (isTrue(operand)) { + return new BooleanPredicate(false); + } else if (isFalse(operand)) { + return new BooleanPredicate(true); + } + ((Negation) predicate).setOperand(operand); + } + return predicate; + } + + private boolean isFalse(Predicate predicate) { + if (predicate instanceof BooleanPredicate) { + return !((BooleanPredicate)predicate).getValue(); + } + return false; + } + + private boolean isTrue(Predicate predicate) { + if (predicate instanceof BooleanPredicate) { + return ((BooleanPredicate)predicate).getValue(); + } + return false; + } + + @Override + public Predicate process(Predicate predicate, PredicateOptions options) { + return simplifySubTree(predicate); + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/ComplexNodeTransformer.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/ComplexNodeTransformer.java new file mode 100644 index 00000000000..4ff5d37f842 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/ComplexNodeTransformer.java @@ -0,0 +1,159 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import com.yahoo.document.predicate.FeatureRange; +import com.yahoo.document.predicate.Predicate; +import com.yahoo.document.predicate.PredicateOperator; +import com.yahoo.document.predicate.RangeEdgePartition; +import com.yahoo.document.predicate.RangePartition; + +import static java.lang.Math.abs; + +/** + * Partitions all the feature ranges according to the arity and bounds + * set in the PredicateOptions, and updates the ranges with a set of + * partitions and edge partitions. + * This is required to be able to store a range in the PredicateIndex. + * + * @author magnarn + * @author bjorncs + */ +public class ComplexNodeTransformer implements PredicateProcessor { + + public void processPredicate(Predicate predicate, PredicateOptions options) { + if (predicate instanceof PredicateOperator) { + for (Predicate p : ((PredicateOperator) predicate).getOperands()) { + processPredicate(p, options); + } + } else if (predicate instanceof FeatureRange) { + processFeatureRange((FeatureRange) predicate, options); + } + } + + private void processFeatureRange(FeatureRange range, PredicateOptions options) { + range.clearPartitions(); + int arity = options.getArity(); + RangePruner rangePruner = new RangePruner(range, options, arity); + long from = rangePruner.getFrom(); + long to = rangePruner.getTo(); + + if (from < 0) { + if (to < 0) { + // Special case for to==-1. -X-0 means the same as -X-1, but is more efficient. + partitionRange(range, (to == -1 ? 0 : -to), -from, arity, true); + } else { + partitionRange(range, 0, -from, arity, true); + partitionRange(range, 0, to, arity, false); + } + } else { + partitionRange(range, from, to, arity, false); + } + } + + private void partitionRange(FeatureRange range, long from, long to, int arity, boolean isNeg) { + int fromRemainder = abs((int) (from % arity)); // from is only negative when using LLONG_MIN. + // operate on exclusive upper bound. + int toRemainder = ((int) ((to - arity + 1) % arity) + arity) % arity; // avoid overflow of (to + 1) + long fromVal = from - fromRemainder; + long toVal = to - toRemainder; // use inclusive upper bound here to avoid overflow problems. + long fromValDividedByArity = abs(fromVal / arity); + if (fromVal - 1 == toVal) { // (toVal + 1) might cause overflow + addEdgePartition(range, fromVal, fromRemainder, toRemainder - 1, isNeg); + return; + } else { + if (fromRemainder != 0) { + addEdgePartition(range, fromVal, fromRemainder, -1, isNeg); + fromValDividedByArity += 1; + } + if (toRemainder != 0) { + addEdgePartition(range, toVal + 1, -1, toRemainder - 1, isNeg); + } + } + makePartitions(range, fromValDividedByArity, abs((toVal - (arity - 1)) / arity) + 1, arity, arity, isNeg); + } + + private void addEdgePartition(FeatureRange range, long value, int from, int to, boolean isNeg) { + String label; + if (value == 0x8000000000000000L) // special case long_min. + label = range.getKey() + "=-9223372036854775808"; + else + label = range.getKey() + (isNeg ? "=-" : "=") + Long.toString(value); + range.addPartition(new RangeEdgePartition(label, value, from, to)); + } + + private void makePartitions(FeatureRange range, long fromVal, long toVal, long stepSize, int arity, boolean isNeg) { + int fromRemainder = (int) (fromVal % arity); + int toRemainder = (int) (toVal % arity); + long nextFromVal = fromVal - fromRemainder; + long nextToVal = toVal - toRemainder; + if (nextFromVal == nextToVal) { + addPartitions(range, nextFromVal, stepSize, fromRemainder, toRemainder, isNeg); + } else { + if (fromRemainder > 0) { + addPartitions(range, nextFromVal, stepSize, fromRemainder, arity, isNeg); + fromVal = nextFromVal + arity; + } + addPartitions(range, nextToVal, stepSize, 0, toRemainder, isNeg); + makePartitions(range, fromVal / arity, toVal / arity, stepSize * arity, arity, isNeg); + } + } + + private void addPartitions(FeatureRange range, long part, long partSize, int first, int last, boolean isNeg) { + for (int i = first; i < last; ++i) { + range.addPartition(new RangePartition( + range.getKey(), (part + i) * partSize, (part + i + 1) * partSize - 1, isNeg)); + } + } + + @Override + public Predicate process(Predicate predicate, PredicateOptions options) { + processPredicate(predicate, options); + return predicate; + } + + /** + * Prunes ranges that lie partially or completely outside the configured upper/lower bounds. + */ + private static class RangePruner { + private long from; + private long to; + + public RangePruner(FeatureRange range, PredicateOptions options, int arity) { + from = range.getFromInclusive() != null ? range.getFromInclusive() : options.getAdjustedLowerBound(); + to = range.getToInclusive() != null ? range.getToInclusive() : options.getAdjustedUpperBound(); + + if (from > options.getUpperBound()) { // Range completely beyond bounds + long upperRangeStart = Long.MAX_VALUE - (Long.MAX_VALUE % arity) - arity; + if (options.getUpperBound() < upperRangeStart) { + from = upperRangeStart; + to = upperRangeStart + arity - 1; + } else { + to = from; + } + } else if (to < options.getLowerBound()) { // Range completely before bounds + long lowerRangeEnd = Long.MIN_VALUE + (arity - (Long.MIN_VALUE % arity)); + if (options.getLowerBound() > lowerRangeEnd) { + from = lowerRangeEnd - arity + 1; + to = lowerRangeEnd; + } else { + from = to; + } + } else { // Modify if range overlaps bounds + if (from < options.getLowerBound()) { + from = options.getAdjustedLowerBound(); + } + if (to > options.getUpperBound()) { + to = options.getAdjustedUpperBound(); + } + } + } + + public long getFrom() { + return from; + } + + public long getTo() { + return to; + } + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/NotNodeReorderer.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/NotNodeReorderer.java new file mode 100644 index 00000000000..bd7339581f4 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/NotNodeReorderer.java @@ -0,0 +1,67 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import com.yahoo.document.predicate.Conjunction; +import com.yahoo.document.predicate.Disjunction; +import com.yahoo.document.predicate.Negation; +import com.yahoo.document.predicate.Predicate; + +import java.util.ArrayList; +import java.util.List; + +/** + * Reorders not nodes to improve the efficiency of the z-star posting list compression. + * It puts negative children first in AND-nodes, and last in OR-nodes. + * + * @author magnarn + * @author bjorncs + */ +public class NotNodeReorderer implements PredicateProcessor { + /** + * @return true if the predicate ends in a negation. + */ + public boolean processSubTree(Predicate predicate) { + if (predicate == null) { + return false; + } + if (predicate instanceof Negation) { + // All negations are for leaf-nodes after AndOrSimplifier has run. + return true; + } else if (predicate instanceof Conjunction) { + List<Predicate> in = ((Conjunction)predicate).getOperands(); + List<Predicate> out = new ArrayList<>(in.size()); + List<Predicate> positiveChildren = new ArrayList<>(in.size()); + for (Predicate operand : in) { + if (processSubTree(operand)) { + out.add(operand); + } else { + positiveChildren.add(operand); + } + } + out.addAll(positiveChildren); + ((Conjunction)predicate).setOperands(out); + return positiveChildren.isEmpty(); + } else if (predicate instanceof Disjunction) { + List<Predicate> in = ((Disjunction)predicate).getOperands(); + List<Predicate> out = new ArrayList<>(in.size()); + List<Predicate> negativeChildren = new ArrayList<>(in.size()); + for (Predicate operand : in) { + if (processSubTree(operand)) { + negativeChildren.add(operand); + } else { + out.add(operand); + } + } + out.addAll(negativeChildren); + ((Disjunction)predicate).setOperands(out); + return !negativeChildren.isEmpty(); + } + return false; + } + + @Override + public Predicate process(Predicate predicate, PredicateOptions options) { + processSubTree(predicate); + return predicate; + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/OrSimplifier.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/OrSimplifier.java new file mode 100644 index 00000000000..768534b0068 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/OrSimplifier.java @@ -0,0 +1,71 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import com.yahoo.document.predicate.Conjunction; +import com.yahoo.document.predicate.Disjunction; +import com.yahoo.document.predicate.FeatureSet; +import com.yahoo.document.predicate.Negation; +import com.yahoo.document.predicate.Predicate; + +import java.util.List; +import java.util.Optional; + +import static java.util.stream.Collectors.groupingBy; +import static java.util.stream.Collectors.reducing; +import static java.util.stream.Collectors.toList; + +/** + * Simplifies Disjunction nodes where all children are of type FeatureSet. All FeatureSet that share the same key + * are merged into a single FeatureSet. The Disjunction is removed if all children merges into a single feature set. + * @author bjorncs + */ +public class OrSimplifier implements PredicateProcessor { + + @Override + public Predicate process(Predicate predicate, PredicateOptions options) { + return simplifyTree(predicate); + } + + public Predicate simplifyTree(Predicate predicate) { + if (predicate instanceof Disjunction) { + Disjunction disjunction = (Disjunction) predicate; + List<Predicate> newChildren = + disjunction.getOperands().stream().map(this::simplifyTree).collect(toList()); + return compressFeatureSets(newChildren); + } else if (predicate instanceof Negation) { + Negation negation = (Negation) predicate; + negation.setOperand(simplifyTree(negation.getOperand())); + return negation; + } else if (predicate instanceof Conjunction) { + Conjunction conjunction = (Conjunction) predicate; + List<Predicate> newChildren = + conjunction.getOperands().stream().map(this::simplifyTree).collect(toList()); + conjunction.setOperands(newChildren); + return conjunction; + } else { + return predicate; + } + } + + // Groups and merges the feature sets based on key. + private static Predicate compressFeatureSets(List<Predicate> children) { + List<Predicate> newChildren = children.stream().filter(p -> !(p instanceof FeatureSet)).collect(toList()); + children.stream() + .filter(FeatureSet.class::isInstance) + .map(FeatureSet.class::cast) + .collect(groupingBy(FeatureSet::getKey, + reducing((f1, f2) -> { + f1.addValues(f2.getValues()); + return f1; + }))) + .values() + .stream() + .map(Optional::get) + .forEach(newChildren::add); + if (newChildren.size() == 1) { + return newChildren.get(0); + } else { + return new Disjunction(newChildren); + } + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/PredicateOptions.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/PredicateOptions.java new file mode 100644 index 00000000000..134d52dd3ab --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/PredicateOptions.java @@ -0,0 +1,87 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import java.util.OptionalLong; + +/** + * This class contains the configured options for predicate indexes. + * The adjusted bounds are extended to the nearest power of the arity (-1) + * and are used to generate more efficient indexes. + * + * @author magnarn + * @author bjorncs + */ +public class PredicateOptions { + public static final long DEFAULT_LOWER_BOUND = 0x8000000000000000L; + public static final long DEFAULT_UPPER_BOUND = 0x7fffffffffffffffL; + + private final int arity; + private final long lowerBound; + private final long upperBound; + private OptionalLong adjustedLowerBound; + private OptionalLong adjustedUpperBound; + + public PredicateOptions(int arity, Long lowerBound, Long upperBound) { + this.arity = arity; + this.lowerBound = lowerBound == null? DEFAULT_LOWER_BOUND : lowerBound; + this.upperBound = upperBound == null? DEFAULT_UPPER_BOUND : upperBound; + this.adjustedLowerBound = OptionalLong.empty(); + this.adjustedUpperBound = OptionalLong.empty(); + } + + public PredicateOptions(int arity) { + this(arity, DEFAULT_LOWER_BOUND, DEFAULT_UPPER_BOUND); + } + + public int getArity() { + return arity; + } + + public long getLowerBound() { + return lowerBound; + } + + public long getUpperBound() { + return upperBound; + } + + public long getAdjustedLowerBound() { + if (!adjustedLowerBound.isPresent()) { + if (lowerBound == DEFAULT_LOWER_BOUND) { + adjustedLowerBound = OptionalLong.of(lowerBound); + } else if (lowerBound > 0) { + adjustedLowerBound = OptionalLong.of(0L); + } else { + adjustedLowerBound = OptionalLong.of(-adjustBound(arity, -lowerBound)); + } + } + return adjustedLowerBound.getAsLong(); + } + + public long getAdjustedUpperBound() { + if (!adjustedUpperBound.isPresent()) { + if (upperBound == DEFAULT_UPPER_BOUND) { + adjustedUpperBound = OptionalLong.of(DEFAULT_UPPER_BOUND); + } else if (upperBound < 0) { + adjustedUpperBound = OptionalLong.of(-1L); // 0 belongs to the positive range. + } else { + adjustedUpperBound = OptionalLong.of(adjustBound(arity, upperBound)); + } + } + return adjustedUpperBound.getAsLong(); + } + + private static long adjustBound(int arity, long bound) { + long adjusted = arity; + long value = bound; + long max = Long.MAX_VALUE / arity; + while ((value/=arity) > 0) { + if (adjusted > max) { + return bound; + } + adjusted *= arity; + } + return adjusted - 1; + } +} + diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/PredicateProcessor.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/PredicateProcessor.java new file mode 100644 index 00000000000..f6559bb4044 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/PredicateProcessor.java @@ -0,0 +1,24 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import com.yahoo.document.predicate.Predicate; + +/** + * A predicate processor takes a predicate, processes it and returns the result. + * Predicate optimisers typically implement this interface. + * Note that the interface does not give any guarantees if the processor will + * modify the predicate in-place or return a new instance. + * + * @author bjorncs + */ +@FunctionalInterface +public interface PredicateProcessor { + + /** + * Processes a predicate. + * + * @return the processed predicate. + */ + Predicate process(Predicate predicate, PredicateOptions options); + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/package-info.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/package-info.java new file mode 100644 index 00000000000..77d8143d137 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/optimization/package-info.java @@ -0,0 +1,4 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +@com.yahoo.osgi.annotation.ExportPackage + +package com.yahoo.search.predicate.optimization; diff --git a/predicate-search-core/src/main/java/com/yahoo/search/predicate/package-info.java b/predicate-search-core/src/main/java/com/yahoo/search/predicate/package-info.java new file mode 100644 index 00000000000..8f2d929efcd --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/search/predicate/package-info.java @@ -0,0 +1,4 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +@com.yahoo.osgi.annotation.ExportPackage + +package com.yahoo.search.predicate; diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/BinaryFormatTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/BinaryFormatTest.java new file mode 100644 index 00000000000..44477423fdb --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/BinaryFormatTest.java @@ -0,0 +1,124 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import com.yahoo.slime.Inspector; +import com.yahoo.slime.Slime; +import org.junit.Test; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class BinaryFormatTest { + + @Test + public void requireThatEncodeNullThrows() { + try { + BinaryFormat.encode(null); + fail(); + } catch (NullPointerException e) { + assertEquals("predicate", e.getMessage()); + } + } + + @Test + public void requireThatDecodeNullThrows() { + try { + BinaryFormat.decode(null); + fail(); + } catch (NullPointerException e) { + assertEquals("buf", e.getMessage()); + } + } + + @Test + public void requireThatDecodeEmptyThrows() { + try { + BinaryFormat.decode(new byte[0]); + fail(); + } catch (UnsupportedOperationException e) { + assertEquals("0", e.getMessage()); + } + } + + @Test + public void requireThatConjunctionCanBeSerialized() { + assertSerialize(new Conjunction(new FeatureSet("foo", "bar"), new FeatureSet("baz", "cox"))); + } + + @Test + public void requireThatDisjunctionCanBeSerialized() { + assertSerialize(new Disjunction(new FeatureSet("foo", "bar"), new FeatureSet("baz", "cox"))); + } + + @Test + public void requireThatFeatureRangeCanBeSerialized() { + assertSerialize(new FeatureRange("foo", null, null)); + assertSerialize(new FeatureRange("foo", null, 9L)); + assertSerialize(new FeatureRange("foo", 6L, null)); + assertSerialize(new FeatureRange("foo", 6L, 9L)); + } + + @Test + public void requireThatPartitionedFeatureRangeCanBeSerialized() { + FeatureRange expected = new FeatureRange("foo", 8L, 20L); + FeatureRange f = new FeatureRange("foo", 8L, 20L); + f.addPartition(new RangeEdgePartition("foo=0", 0, 8, -1)); + f.addPartition(new RangeEdgePartition("foo=20", 20, 0, 0)); + f.addPartition(new RangePartition("foo", 10, 19, false)); + assertSerializesTo(expected, f); + Slime slime = com.yahoo.slime.BinaryFormat.decode(BinaryFormat.encode(f)); + assertEquals(BinaryFormat.TYPE_FEATURE_RANGE, slime.get().field(BinaryFormat.NODE_TYPE).asLong()); + Inspector in1 = slime.get().field(BinaryFormat.HASHED_PARTITIONS); + assertEquals(1, in1.entries()); + assertEquals(0xf2b6d1cc6322cb99L, in1.entry(0).asLong()); + Inspector in2 = slime.get().field(BinaryFormat.HASHED_EDGE_PARTITIONS); + assertEquals(2, in2.entries()); + Inspector obj1 = in2.entry(0); + assertEquals(0xb2b301e26efffdc2L, obj1.field(BinaryFormat.HASH).asLong()); + assertEquals(0, obj1.field(BinaryFormat.VALUE).asLong()); + assertEquals(0x80000008L, obj1.field(BinaryFormat.PAYLOAD).asLong()); + Inspector obj2 = in2.entry(1); + assertEquals(0x22acb2ed72523c36L, obj2.field(BinaryFormat.HASH).asLong()); + assertEquals(20, obj2.field(BinaryFormat.VALUE).asLong()); + assertEquals(0x40000001L, obj2.field(BinaryFormat.PAYLOAD).asLong()); + } + + @Test + public void requireThatFeatureSetCanBeSerialized() { + assertSerialize(new FeatureSet("foo")); + assertSerialize(new FeatureSet("foo", "bar")); + assertSerialize(new FeatureSet("foo", "bar", "baz")); + } + + @Test + public void requireThatNegationCanBeSerialized() { + assertSerialize(new Negation(new FeatureSet("foo", "bar"))); + } + + @Test + public void requireThatBooleanCanBeSerialized() { + assertSerialize(new BooleanPredicate(true)); + assertSerialize(new BooleanPredicate(false)); + } + + @Test + public void requireThatUnknownNodeThrows() { + try { + BinaryFormat.encode(SimplePredicates.newString("foo")); + fail(); + } catch (UnsupportedOperationException e) { + + } + } + + private static void assertSerializesTo(Predicate expected, Predicate predicate) { + assertEquals(expected, BinaryFormat.decode(BinaryFormat.encode(predicate))); + } + + private static void assertSerialize(Predicate predicate) { + assertSerializesTo(predicate, predicate); + } +} diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/BooleanPredicateTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/BooleanPredicateTest.java new file mode 100644 index 00000000000..7268b358889 --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/BooleanPredicateTest.java @@ -0,0 +1,47 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import org.junit.Test; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertNotSame; +import static org.junit.Assert.assertTrue; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class BooleanPredicateTest { + + @Test + public void requireThatFalseIsAValue() { + assertTrue(PredicateValue.class.isAssignableFrom(BooleanPredicate.class)); + } + + @Test + public void requireThatCloneIsImplemented() throws CloneNotSupportedException { + BooleanPredicate node1 = new BooleanPredicate(true); + BooleanPredicate node2 = node1.clone(); + assertEquals(node1, node2); + assertNotSame(node1, node2); + } + + @Test + public void requireThatHashCodeIsImplemented() { + assertEquals(new BooleanPredicate(true).hashCode(), new BooleanPredicate(true).hashCode()); + assertEquals(new BooleanPredicate(false).hashCode(), new BooleanPredicate(false).hashCode()); + } + + @Test + public void requireThatEqualsIsImplemented() { + BooleanPredicate lhs = new BooleanPredicate(true); + assertTrue(lhs.equals(lhs)); + assertFalse(lhs.equals(new Object())); + + BooleanPredicate rhs = new BooleanPredicate(false); + assertFalse(lhs.equals(rhs)); + rhs.setValue(true); + assertTrue(lhs.equals(rhs)); + } + +} diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/ConjunctionTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/ConjunctionTest.java new file mode 100644 index 00000000000..6e12a00ba4d --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/ConjunctionTest.java @@ -0,0 +1,113 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import org.junit.Test; + +import java.util.Arrays; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertNotSame; +import static org.junit.Assert.assertTrue; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class ConjunctionTest { + + @Test + public void requireThatConjunctionIsAnOperator() { + assertTrue(PredicateOperator.class.isAssignableFrom(Conjunction.class)); + } + + @Test + public void requireThatAccessorsWork() { + Conjunction node = new Conjunction(); + Predicate a = SimplePredicates.newString("a"); + node.addOperand(a); + assertEquals(Arrays.asList(a), node.getOperands()); + Predicate b = SimplePredicates.newString("b"); + node.addOperand(b); + assertEquals(Arrays.asList(a, b), node.getOperands()); + Predicate c = SimplePredicates.newString("c"); + Predicate d = SimplePredicates.newString("d"); + node.addOperands(Arrays.asList(c, d)); + assertEquals(Arrays.asList(a, b, c, d), node.getOperands()); + Predicate e = SimplePredicates.newString("e"); + Predicate f = SimplePredicates.newString("f"); + node.setOperands(Arrays.asList(e, f)); + assertEquals(Arrays.asList(e, f), node.getOperands()); + } + + @Test + public void requireThatConstructorsWork() { + Predicate foo = SimplePredicates.newString("foo"); + Predicate bar = SimplePredicates.newString("bar"); + Conjunction node = new Conjunction(foo, bar); + assertEquals(Arrays.asList(foo, bar), node.getOperands()); + + node = new Conjunction(Arrays.asList(foo, bar)); + assertEquals(Arrays.asList(foo, bar), node.getOperands()); + } + + @Test + public void requireThatCloneIsImplemented() throws CloneNotSupportedException { + Conjunction node1 = new Conjunction(SimplePredicates.newString("a"), SimplePredicates.newString("b")); + Conjunction node2 = node1.clone(); + assertEquals(node1, node2); + assertNotSame(node1, node2); + assertNotSame(node1.getOperands(), node2.getOperands()); + } + + @Test + public void requireThatHashCodeIsImplemented() { + assertEquals(new Conjunction().hashCode(), new Conjunction().hashCode()); + } + + @Test + public void requireThatEqualsIsImplemented() { + Conjunction lhs = new Conjunction(SimplePredicates.newString("foo"), + SimplePredicates.newString("bar")); + assertTrue(lhs.equals(lhs)); + assertFalse(lhs.equals(new Object())); + + Conjunction rhs = new Conjunction(); + assertFalse(lhs.equals(rhs)); + rhs.addOperand(SimplePredicates.newString("foo")); + assertFalse(lhs.equals(rhs)); + rhs.addOperand(SimplePredicates.newString("bar")); + assertTrue(lhs.equals(rhs)); + } + + @Test + public void requireThatNodeDelimiterIsAND() { + assertEquals("", newConjunction().toString()); + assertEquals("foo", newConjunction("foo").toString()); + assertEquals("foo and bar", newConjunction("foo", "bar").toString()); + assertEquals("foo and bar and baz", newConjunction("foo", "bar", "baz").toString()); + } + + @Test + public void requireThatSimpleConjunctionsArePrettyPrinted() { + assertEquals("foo and bar", + new Conjunction(SimplePredicates.newString("foo"), + SimplePredicates.newString("bar")).toString()); + } + + @Test + public void requireThatComplexConjunctionsArePrintedAsGroup() { + assertEquals("foo and bar and baz", + new Conjunction(SimplePredicates.newString("foo"), + new Conjunction(SimplePredicates.newString("bar"), + SimplePredicates.newString("baz"))).toString()); + assertEquals("foo and (bar or baz)", + new Conjunction(SimplePredicates.newString("foo"), + new Disjunction(SimplePredicates.newString("bar"), + SimplePredicates.newString("baz"))).toString()); + } + + private static Conjunction newConjunction(String... operands) { + return new Conjunction(SimplePredicates.newStrings(operands)); + } + +} diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/DisjunctionTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/DisjunctionTest.java new file mode 100644 index 00000000000..99dc46c4f5f --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/DisjunctionTest.java @@ -0,0 +1,113 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import org.junit.Test; + +import java.util.Arrays; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertNotSame; +import static org.junit.Assert.assertTrue; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class DisjunctionTest { + + @Test + public void requireThatDisjunctionIsAnOperator() { + assertTrue(PredicateOperator.class.isAssignableFrom(Disjunction.class)); + } + + @Test + public void requireThatAccessorsWork() { + Disjunction node = new Disjunction(); + Predicate a = SimplePredicates.newString("a"); + node.addOperand(a); + assertEquals(Arrays.asList(a), node.getOperands()); + Predicate b = SimplePredicates.newString("b"); + node.addOperand(b); + assertEquals(Arrays.asList(a, b), node.getOperands()); + Predicate c = SimplePredicates.newString("c"); + Predicate d = SimplePredicates.newString("d"); + node.addOperands(Arrays.asList(c, d)); + assertEquals(Arrays.asList(a, b, c, d), node.getOperands()); + Predicate e = SimplePredicates.newString("e"); + Predicate f = SimplePredicates.newString("f"); + node.setOperands(Arrays.asList(e, f)); + assertEquals(Arrays.asList(e, f), node.getOperands()); + } + + @Test + public void requireThatConstructorsWork() { + Predicate foo = SimplePredicates.newString("foo"); + Predicate bar = SimplePredicates.newString("bar"); + Disjunction node = new Disjunction(foo, bar); + assertEquals(Arrays.asList(foo, bar), node.getOperands()); + + node = new Disjunction(Arrays.asList(foo, bar)); + assertEquals(Arrays.asList(foo, bar), node.getOperands()); + } + + @Test + public void requireThatCloneIsImplemented() throws CloneNotSupportedException { + Disjunction node1 = new Disjunction(SimplePredicates.newString("a"), SimplePredicates.newString("b")); + Disjunction node2 = node1.clone(); + assertEquals(node1, node2); + assertNotSame(node1, node2); + assertNotSame(node1.getOperands(), node2.getOperands()); + } + + @Test + public void requireThatHashCodeIsImplemented() { + assertEquals(new Disjunction().hashCode(), new Disjunction().hashCode()); + } + + @Test + public void requireThatEqualsIsImplemented() { + Disjunction lhs = new Disjunction(SimplePredicates.newString("foo"), + SimplePredicates.newString("bar")); + assertTrue(lhs.equals(lhs)); + assertFalse(lhs.equals(new Object())); + + Disjunction rhs = new Disjunction(); + assertFalse(lhs.equals(rhs)); + rhs.addOperand(SimplePredicates.newString("foo")); + assertFalse(lhs.equals(rhs)); + rhs.addOperand(SimplePredicates.newString("bar")); + assertTrue(lhs.equals(rhs)); + } + + @Test + public void requireThatNodeDelimiterIsOR() { + assertEquals("", newDisjunction().toString()); + assertEquals("foo", newDisjunction("foo").toString()); + assertEquals("foo or bar", newDisjunction("foo", "bar").toString()); + assertEquals("foo or bar or baz", newDisjunction("foo", "bar", "baz").toString()); + } + + @Test + public void requireThatSimpleDisjunctionsArePrettyPrinted() { + assertEquals("foo or bar", + new Disjunction(SimplePredicates.newString("foo"), + SimplePredicates.newString("bar")).toString()); + } + + @Test + public void requireThatComplexDisjunctionsArePrintedAsGroup() { + assertEquals("foo or bar or baz", + new Disjunction(SimplePredicates.newString("foo"), + new Disjunction(SimplePredicates.newString("bar"), + SimplePredicates.newString("baz"))).toString()); + assertEquals("foo or (bar and baz)", + new Disjunction(SimplePredicates.newString("foo"), + new Conjunction(SimplePredicates.newString("bar"), + SimplePredicates.newString("baz"))).toString()); + } + + private static Disjunction newDisjunction(String... operands) { + return new Disjunction(SimplePredicates.newStrings(operands)); + } + +} diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/FeatureConjunctionTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/FeatureConjunctionTest.java new file mode 100644 index 00000000000..e98400e86fa --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/FeatureConjunctionTest.java @@ -0,0 +1,52 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import org.junit.Test; + +import java.util.Arrays; +import java.util.Collections; + +import static com.yahoo.document.predicate.Predicates.feature; +import static com.yahoo.document.predicate.Predicates.not; + +/** + * @author bjorncs + */ +public class FeatureConjunctionTest { + + @Test + public void require_that_featureconjunction_with_valid_operands_can_be_constructed() { + new FeatureConjunction(Arrays.asList( + not(feature("a").inSet("1")), + feature("b").inSet("1"))); + } + + @Test(expected = IllegalArgumentException.class) + public void require_that_constructor_throws_exception_if_all_operands_are_not_featuresets() { + new FeatureConjunction(Arrays.asList( + not(feature("a").inSet("1")), + feature("b").inRange(1, 2))); + } + + @Test(expected = IllegalArgumentException.class) + public void require_that_constructor_throws_exception_if_single_operand() { + new FeatureConjunction(Arrays.asList(feature("a").inSet("1"))); + } + + @Test(expected = IllegalArgumentException.class) + public void require_that_constructor_throws_exception_if_no_operands() { + new FeatureConjunction(Collections.emptyList()); + } + + @Test(expected = IllegalArgumentException.class) + public void require_that_contructor_throws_exception_if_featuresets_contain_multiple_values() { + new FeatureConjunction(Arrays.asList(feature("a").inSet("1"), feature("b").inSet("2", "3"))); + } + + @Test(expected = IllegalArgumentException.class) + public void require_that_constructor_throws_exception_if_featureset_keys_are_not_unique() { + new FeatureConjunction(Arrays.asList( + not(feature("a").inSet("1")), + feature("a").inSet("2"))); + } +} diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/FeatureRangeTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/FeatureRangeTest.java new file mode 100644 index 00000000000..efcc0e5b64a --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/FeatureRangeTest.java @@ -0,0 +1,263 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import org.junit.Test; + +import java.util.Arrays; + +import static org.junit.Assert.*; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class FeatureRangeTest { + + @Test + public void requireThatFeatureRangeIsAValue() { + assertTrue(PredicateValue.class.isAssignableFrom(FeatureRange.class)); + } + + @Test + public void requireThatAccessorsWork() { + FeatureRange node = new FeatureRange("foo"); + assertEquals("foo", node.getKey()); + node.setKey("bar"); + assertEquals("bar", node.getKey()); + + node.setFromInclusive(69L); + assertEquals(69, node.getFromInclusive().intValue()); + node.setFromInclusive(null); + assertNull(node.getFromInclusive()); + + node.setToInclusive(69L); + assertEquals(69, node.getToInclusive().intValue()); + node.setToInclusive(null); + assertNull(node.getToInclusive()); + } + + @Test + public void requireThatConstructorsWork() { + FeatureRange node = new FeatureRange("foo"); + assertEquals("foo", node.getKey()); + assertNull(node.getFromInclusive()); + assertNull(node.getToInclusive()); + + node = new FeatureRange("foo", null, null); + assertEquals("foo", node.getKey()); + assertNull(node.getFromInclusive()); + assertNull(node.getToInclusive()); + + node = new FeatureRange("foo", 69L, null); + assertEquals("foo", node.getKey()); + assertEquals(69, node.getFromInclusive().intValue()); + assertNull(node.getToInclusive()); + + node = new FeatureRange("foo", null, 69L); + assertEquals("foo", node.getKey()); + assertNull(node.getFromInclusive()); + assertEquals(69, node.getToInclusive().intValue()); + + node = new FeatureRange("foo", 6L, 9L); + assertEquals("foo", node.getKey()); + assertEquals(6, node.getFromInclusive().intValue()); + assertEquals(9, node.getToInclusive().intValue()); + } + + @Test + public void requireThatCloneIsImplemented() throws CloneNotSupportedException { + FeatureRange node1 = new FeatureRange("foo", 6L, 9L); + FeatureRange node2 = node1.clone(); + assertEquals(node1, node2); + assertNotSame(node1, node2); + } + + @Test + public void requireThatHashCodeIsImplemented() { + assertEquals(new FeatureRange("key").hashCode(), new FeatureRange("key").hashCode()); + } + + @Test + public void requireThatEqualsIsImplemented() { + FeatureRange lhs = new FeatureRange("foo", 6L, 9L); + assertTrue(lhs.equals(lhs)); + assertFalse(lhs.equals(new Object())); + + FeatureRange rhs = new FeatureRange("bar"); + assertFalse(lhs.equals(rhs)); + rhs.setKey("foo"); + assertFalse(lhs.equals(rhs)); + rhs.setFromInclusive(6L); + assertFalse(lhs.equals(rhs)); + rhs.setToInclusive(9L); + assertTrue(lhs.equals(rhs)); + rhs.addPartition(new RangePartition("foo")); + assertFalse(lhs.equals(rhs)); + lhs.addPartition(new RangePartition("foo")); + assertTrue(lhs.equals(rhs)); + rhs.addPartition(new RangeEdgePartition("foo", 10, 0, 2)); + assertFalse(lhs.equals(rhs)); + lhs.addPartition(new RangeEdgePartition("foo", 10, 0, 2)); + assertTrue(lhs.equals(rhs)); + } + + @Test + public void requireThatFeatureKeyIsMandatoryInConstructor() { + try { + new FeatureRange(null); + fail(); + } catch (NullPointerException e) { + assertEquals("key", e.getMessage()); + } + } + + @Test + public void requireThatFeatureKeyIsMandatoryInSetter() { + FeatureRange node = new FeatureRange("foo"); + try { + node.setKey(null); + fail(); + } catch (NullPointerException e) { + assertEquals("key", e.getMessage()); + } + assertEquals("foo", node.getKey()); + } + + @Test + public void requireThatRangeCanBeSingleValue() { + FeatureRange node = new FeatureRange("key", 6L, 6L); + assertEquals(6, node.getFromInclusive().intValue()); + assertEquals(6, node.getToInclusive().intValue()); + node.setToInclusive(9L); + node.setFromInclusive(9L); + assertEquals(9, node.getFromInclusive().intValue()); + assertEquals(9, node.getToInclusive().intValue()); + } + + @Test + public void requireThatFromCanNotBeConstructedGreaterThanTo() { + try { + new FeatureRange("key", 9L, 6L); + fail(); + } catch (IllegalArgumentException e) { + assertEquals("Expected 'to' greater than or equal to 9, got 6.", e.getMessage()); + } + } + + @Test + public void requireThatFromCanNotBeSetGreaterThanTo() { + FeatureRange node = new FeatureRange("key", null, 6L); + try { + node.setFromInclusive(9L); + fail(); + } catch (IllegalArgumentException e) { + assertEquals("Expected 'from' less than or equal to 6, got 9.", e.getMessage()); + } + assertNull(node.getFromInclusive()); + + node = new FeatureRange("key", 6L, 9L); + try { + node.setFromInclusive(69L); + fail(); + } catch (IllegalArgumentException e) { + assertEquals("Expected 'from' less than or equal to 9, got 69.", e.getMessage()); + } + assertEquals(6, node.getFromInclusive().intValue()); + } + + @Test + public void requireThatToCanNotBeSetLessThanFrom() { + FeatureRange node = new FeatureRange("key", 9L, null); + try { + node.setToInclusive(6L); + fail(); + } catch (IllegalArgumentException e) { + assertEquals("Expected 'to' greater than or equal to 9, got 6.", e.getMessage()); + } + assertNull(node.getToInclusive()); + + node = new FeatureRange("key", 6L, 9L); + try { + node.setToInclusive(1L); + fail(); + } catch (IllegalArgumentException e) { + assertEquals("Expected 'to' greater than or equal to 6, got 1.", e.getMessage()); + } + assertEquals(9, node.getToInclusive().intValue()); + } + + @Test + public void requireThatKeyIsEscapedInToString() { + assertEquals("foo in [6..9]", + new FeatureRange("foo", 6L, 9L).toString()); + assertEquals("'\\foo' in [6..9]", + new FeatureRange("\foo", 6L, 9L).toString()); + assertEquals("'\\x27foo\\x27' in [6..9]", + new FeatureRange("'foo'", 6L, 9L).toString()); + } + + @Test + public void requireThatToStringIncludesLimits() { + assertEquals("foo in [6..9]", new FeatureRange("foo", 6L, 9L).toString()); + } + + @Test + public void requireThatToStringAllowsNullLimits() { + assertEquals("foo in [..]", new FeatureRange("foo").toString()); + } + + @Test + public void requireThatToStringAllowsNullFromLimit() { + assertEquals("foo in [..69]", new FeatureRange("foo", null, 69L).toString()); + } + + @Test + public void requireThatToStringAllowsNullToLimit() { + assertEquals("foo in [69..]", new FeatureRange("foo", 69L, null).toString()); + } + + @Test + public void requireThatSimpleStringsArePrettyPrinted() { + assertEquals("foo in [6..9]", + new FeatureRange("foo", 6L, 9L).toString()); + } + + @Test + public void requireThatComplexStringsAreEscaped() { + assertEquals("'\\foo' in [6..9]", + new FeatureRange("\foo", 6L, 9L).toString()); + } + + @Test + public void requireThatRangePartitionsCanBeAdded() { + FeatureRange range = new FeatureRange("foo", 10L, 22L); + range.addPartition(new RangePartition("foo=10-19")); + range.addPartition(new RangePartition("foo", 0, 0x8000000000000000L, true)); + range.addPartition(new RangeEdgePartition("foo=20", 20, 0, 2)); + assertEquals("foo in [10..22 (foo=20+[..2],foo=10-19,foo=-9223372036854775808-0)]", range.toString()); + } + + @Test + public void requireThatRangePartitionsCanBeCleared() { + FeatureRange range = new FeatureRange("foo", 10L, 22L); + range.addPartition(new RangePartition("foo=10-19")); + range.addPartition(new RangeEdgePartition("foo=20", 20, 0, 2)); + assertEquals("foo in [10..22 (foo=20+[..2],foo=10-19)]", range.toString()); + range.clearPartitions(); + assertEquals("foo in [10..22]", range.toString()); + } + + @Test + public void requireThatFeatureRangeCanBeBuiltFromMixedInNode() { + assertEquals(new FeatureRange("foo", 10L, 19L), + FeatureRange.buildFromMixedIn("foo", Arrays.asList("foo=10-19"), 10)); + assertEquals(new FeatureRange("foo", -19L, -10L), + FeatureRange.buildFromMixedIn("foo", Arrays.asList("foo=-10-19"), 10)); + assertEquals(new FeatureRange("foo", 10L, 19L), + FeatureRange.buildFromMixedIn("foo", Arrays.asList("foo=10,10,9"), 10)); + assertEquals(new FeatureRange("foo", 10L, 19L), + FeatureRange.buildFromMixedIn("foo", Arrays.asList("foo=10,10,1073741833"), 10)); + assertEquals(new FeatureRange("foo", 10L, 19L), + FeatureRange.buildFromMixedIn("foo", Arrays.asList("foo=10,10,2147483648"), 10)); + } + +} diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/FeatureSetTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/FeatureSetTest.java new file mode 100644 index 00000000000..7bc9d5f2c04 --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/FeatureSetTest.java @@ -0,0 +1,180 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import org.junit.Test; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collection; +import java.util.Collections; +import java.util.List; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertNotNull; +import static org.junit.Assert.assertNotSame; +import static org.junit.Assert.assertTrue; +import static org.junit.Assert.fail; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class FeatureSetTest { + + @Test + public void requireThatFeatureSetIsAValue() { + assertTrue(PredicateValue.class.isAssignableFrom(FeatureSet.class)); + } + + @Test + public void requireThatAccessorsWork() { + FeatureSet node = new FeatureSet("key", "valueA", "valueB"); + assertEquals("key", node.getKey()); + assertValues(Arrays.asList("valueA", "valueB"), node); + node.addValue("valueC"); + assertValues(Arrays.asList("valueA", "valueB", "valueC"), node); + node.addValues(Arrays.asList("valueD", "valueE")); + assertValues(Arrays.asList("valueA", "valueB", "valueC", "valueD", "valueE"), node); + node.setValues(Arrays.asList("valueF", "valueG")); + assertValues(Arrays.asList("valueF", "valueG"), node); + } + + @Test + public void requireThatValueSetIsMutable() { + FeatureSet node = new FeatureSet("key"); + node.getValues().add("valueA"); + assertValues(Arrays.asList("valueA"), node); + + node = new FeatureSet("key", "valueA"); + node.getValues().add("valueB"); + assertValues(Arrays.asList("valueA", "valueB"), node); + } + + @Test + public void requireThatConstructorsWork() { + FeatureSet node = new FeatureSet("key", "valueA", "valueB"); + assertEquals("key", node.getKey()); + assertValues(Arrays.asList("valueA", "valueB"), node); + + node = new FeatureSet("key", Arrays.asList("valueA", "valueB")); + assertEquals("key", node.getKey()); + assertValues(Arrays.asList("valueA", "valueB"), node); + } + + @Test + public void requireThatCloneIsImplemented() throws CloneNotSupportedException { + FeatureSet node1 = new FeatureSet("key", "valueA", "valueB"); + FeatureSet node2 = node1.clone(); + assertEquals(node1, node2); + assertNotSame(node1, node2); + assertNotSame(node1.getValues(), node2.getValues()); + } + + @Test + public void requireThatHashCodeIsImplemented() { + assertEquals(new FeatureSet("key").hashCode(), new FeatureSet("key").hashCode()); + } + + @Test + public void requireThatEqualsIsImplemented() { + FeatureSet lhs = new FeatureSet("keyA", "valueA", "valueB"); + assertTrue(lhs.equals(lhs)); + assertFalse(lhs.equals(new Object())); + + FeatureSet rhs = new FeatureSet("keyB"); + assertFalse(lhs.equals(rhs)); + rhs.setKey("keyA"); + assertFalse(lhs.equals(rhs)); + rhs.addValue("valueA"); + assertFalse(lhs.equals(rhs)); + rhs.addValue("valueB"); + assertTrue(lhs.equals(rhs)); + } + + @Test + public void requireThatkeyIsMandatoryInConstructor() { + try { + new FeatureSet(null); + fail(); + } catch (NullPointerException e) { + assertEquals("key", e.getMessage()); + } + try { + new FeatureSet(null, Collections.<String>emptyList()); + fail(); + } catch (NullPointerException e) { + assertEquals("key", e.getMessage()); + } + } + + @Test + public void requireThatkeyIsMandatoryInSetter() { + FeatureSet node = new FeatureSet("foo"); + try { + node.setKey(null); + fail(); + } catch (NullPointerException e) { + assertEquals("key", e.getMessage()); + } + assertEquals("foo", node.getKey()); + } + + @Test + public void requireThatValueIsMandatoryInSetter() { + FeatureSet node = new FeatureSet("foo", "bar"); + try { + node.addValue(null); + fail(); + } catch (NullPointerException e) { + assertEquals("value", e.getMessage()); + } + assertValues(Arrays.asList("bar"), node); + } + + @Test + public void requireThatKeyIsEscapedInToString() { + assertEquals("foo in [val]", + new FeatureSet("foo", "val").toString()); + assertEquals("'\\foo' in [val]", + new FeatureSet("\foo", "val").toString()); + assertEquals("'\\x27foo\\x27' in [val]", + new FeatureSet("'foo'", "val").toString()); + } + + @Test + public void requireThatValuesAreEscapedInToString() { + assertEquals("key in [bar, foo]", + new FeatureSet("key", "foo", "bar").toString()); + assertEquals("key in ['\\foo', 'ba\\r']", + new FeatureSet("key", "\foo", "ba\r").toString()); + assertEquals("key in ['\\x27bar\\x27', '\\x27foo\\x27']", + new FeatureSet("key", "'foo'", "'bar'").toString()); + } + + @Test + public void requireThatSimpleStringsArePrettyPrinted() { + assertEquals("foo in [bar]", + new FeatureSet("foo", "bar").toString()); + } + + @Test + public void requireThatComplexStringsAreEscaped() { + assertEquals("'\\foo' in ['ba\\r']", + new FeatureSet("\foo", "ba\r").toString()); + } + + @Test + public void requireThatNegatedFeatureSetsArePrettyPrinted() { + assertEquals("country not in [no, se]", + new Negation(new FeatureSet("country", "no", "se")).toString()); + } + + private static void assertValues(Collection<String> expected, FeatureSet actual) { + List<String> tmp = new ArrayList<>(expected); + for (String value : actual.getValues()) { + assertNotNull(value, tmp.remove(value)); + } + assertTrue(tmp.toString(), tmp.isEmpty()); + } + +} diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/NegationTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/NegationTest.java new file mode 100644 index 00000000000..95666342152 --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/NegationTest.java @@ -0,0 +1,89 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import org.junit.Test; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertNotSame; +import static org.junit.Assert.assertSame; +import static org.junit.Assert.assertTrue; +import static org.junit.Assert.fail; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class NegationTest { + + @Test + public void requireThatNegationIsAnOperator() { + assertTrue(PredicateOperator.class.isAssignableFrom(Negation.class)); + } + + @Test + public void requireThatAccessorsWork() { + Predicate foo = SimplePredicates.newString("foo"); + Negation node = new Negation(foo); + assertSame(foo, node.getOperand()); + + Predicate bar = SimplePredicates.newString("bar"); + node.setOperand(bar); + assertSame(bar, node.getOperand()); + } + + @Test + public void requireThatCloneIsImplemented() throws CloneNotSupportedException { + Negation node1 = new Negation(SimplePredicates.newString("a")); + Negation node2 = node1.clone(); + assertEquals(node1, node2); + assertNotSame(node1, node2); + assertNotSame(node1.getOperand(), node2.getOperand()); + } + + @Test + public void requireThatHashCodeIsImplemented() { + Predicate predicate = SimplePredicates.newPredicate(); + assertEquals(new Negation(predicate).hashCode(), new Negation(predicate).hashCode()); + } + + @Test + public void requireThatEqualsIsImplemented() { + Negation lhs = new Negation(SimplePredicates.newString("foo")); + assertTrue(lhs.equals(lhs)); + assertFalse(lhs.equals(new Object())); + + Negation rhs = new Negation(SimplePredicates.newString("bar")); + assertFalse(lhs.equals(rhs)); + rhs.setOperand(SimplePredicates.newString("foo")); + assertTrue(lhs.equals(rhs)); + } + + @Test + public void requireThatChildIsMandatoryInConstructor() { + try { + new Negation(null); + fail(); + } catch (NullPointerException e) { + assertEquals("operand", e.getMessage()); + } + } + + @Test + public void requireThatChildIsMandatoryInSetter() { + Predicate operand = SimplePredicates.newPredicate(); + Negation negation = new Negation(operand); + try { + negation.setOperand(null); + fail(); + } catch (NullPointerException e) { + assertEquals("operand", e.getMessage()); + } + assertSame(operand, negation.getOperand()); + } + + @Test + public void requireThatChildIsIncludedInToString() { + assertEquals("not (foo)", new Negation(SimplePredicates.newString("foo")).toString()); + } + +} diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateHashTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateHashTest.java new file mode 100644 index 00000000000..759bfe9f48f --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateHashTest.java @@ -0,0 +1,102 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import org.junit.Test; + +import static org.junit.Assert.assertEquals; + +/** + * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + */ +public class PredicateHashTest{ + @Test + public void requireThatShortStringsGetsHashes() { + assertHashesTo(0x82af3d1de65ec252L, "abcdefg"); + assertHashesTo(0xdc50d922fb0e91d6L, "雅虎"); + assertHashesTo(0x709bd6ff1a84dc14L, "country=日本"); + assertHashesTo(0x28e8de732ab0e809L, "foo"); + + assertHashesTo(0x8db63936938575bfL, ""); + assertHashesTo(0x1d48fd74d88633acL, "a"); + assertHashesTo(0xd30019bef51f4a75L, "ab"); + assertHashesTo(0x9cb12e2bfea87243L, "abc"); + assertHashesTo(0x207e64432ec23f4bL, "abcd"); + assertHashesTo(0xbb1277971caf7a56L, "abcde"); + assertHashesTo(0xfde595baae539176L, "abcdef"); + assertHashesTo(0x82af3d1de65ec252L, "abcdefg"); + assertHashesTo(0x1cac1cd5db905a5fL, "abcdefgh"); + assertHashesTo(0x1ce1c26a201525deL, "abcdefghi"); + assertHashesTo(0x2237a417a20c1025L, "abcdefghij"); + assertHashesTo(0xd98f47421abc3754L, "abcdefghijk"); + assertHashesTo(0xb974917101764d3aL, "abcdefghijkl"); + assertHashesTo(0xde3b7ffe3e6dd61fL, "abcdefghijklm"); + assertHashesTo(0x31d95fa68634f482L, "abcdefghijklmn"); + assertHashesTo(0xde99d87fdbeca8faL, "abcdefghijklmn1"); + assertHashesTo(0x0afc8571f275c392L, "abcdefghijklmn12"); + assertHashesTo(0xbd00379443b0606cL, "abcdefghijklmn123"); + assertHashesTo(0x855c704c68e095c5L, "abcdefghijklmn1234"); + assertHashesTo(0xe9233cb6e4fad097L, "abcdefghijklmn12345"); + assertHashesTo(0x1103ca46bd6e8d2fL, "abcdefghijklmn123456"); + assertHashesTo(0x0c7097be717354d1L, "abcdefghijklmn1234567"); + assertHashesTo(0x3e75293210127583L, "abcdefghijklmn12345678"); + assertHashesTo(0xa66286e1294d8197L, "abcdefghijklmn123456789"); + assertHashesTo(0x79fac97d13f4cc84L, "abcdefghijklmn1234567890"); + } + + @Test + public void requireThatLongStringsGetsHashes() { + assertHashesTo(0x79fac97d13f4cc84L, "abcdefghijklmn1234567890"); + assertHashesTo(0xd7af1798f1d5de44L, "abcdefghijklmn1234567890a"); + assertHashesTo(0x5a259ad887478cccL, "abcdefghijklmn1234567890ab"); + assertHashesTo(0x4e8d95bab8d64191L, "abcdefghijklmn1234567890abc"); + assertHashesTo(0xf63b94d31db2fe1aL, "abcdefghijklmn1234567890abcd"); + assertHashesTo(0x47a1977d65709aceL, "abcdefghijklmn1234567890abcde"); + assertHashesTo(0x52e1fb6d6aff3aeeL, "abcdefghijklmn1234567890abcdef"); + assertHashesTo(0xc16de639b6e69ad3L, "abcdefghijklmn1234567890abcdefg"); + assertHashesTo(0x87c22dd1e285dd6fL, "abcdefghijklmn1234567890abcdefgh"); + assertHashesTo(0x775a3542d88b4972L, "abcdefghijklmn1234567890abcdefghi"); + assertHashesTo(0x7b0c82116edf338bL, "abcdefghijklmn1234567890abcdefghij"); + assertHashesTo(0x0fe73b58f6b23cb6L, "abcdefghijklmn1234567890abcdefghijk"); + assertHashesTo(0x27ab8d02387e64e0L, "abcdefghijklmn1234567890abcdefghijkl"); + assertHashesTo(0xdd161af20b41be04L, "abcdefghijklmn1234567890abcdefghijklm"); + assertHashesTo(0x67739554f61fffcbL, "abcdefghijklmn1234567890abcdefghijklmn"); + assertHashesTo(0xa765cc6be247dfb2L, "abcdefghijklmn1234567890abcdefghijklmn1"); + assertHashesTo(0x9e201896cc600501L, "abcdefghijklmn1234567890abcdefghijklmn12"); + assertHashesTo(0xfc5077792bfed491L, "abcdefghijklmn1234567890abcdefghijklmn123"); + assertHashesTo(0x96a7acb73fd13601L, "abcdefghijklmn1234567890abcdefghijklmn1234"); + assertHashesTo(0x45de4237e48a0ba8L, "abcdefghijklmn1234567890abcdefghijklmn12345"); + assertHashesTo(0x3b65da96300e107eL, "abcdefghijklmn1234567890abcdefghijklmn123456"); + assertHashesTo(0xbd95c3591ee587bdL, "abcdefghijklmn1234567890abcdefghijklmn1234567"); + assertHashesTo(0x2688cb2d10e8629bL, "abcdefghijklmn1234567890abcdefghijklmn12345678"); + assertHashesTo(0xcd383d98f9483ef0L, "abcdefghijklmn1234567890abcdefghijklmn123456789"); + assertHashesTo(0x220e374268970e84L, "abcdefghijklmn1234567890abcdefghijklmn1234567890"); + assertHashesTo(0xd50ef002ed96bf0bL, "abcdefghijklmn1234567890abcdefghijklmn1234567890a"); + assertHashesTo(0x5ec9b42099bb25c6L, "abcdefghijklmn1234567890abcdefghijklmn1234567890ab"); + assertHashesTo(0x05c603997a19dbceL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abc"); + assertHashesTo(0xcee3fce2a3e38762L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcd"); + assertHashesTo(0xc0d9791b19897f0aL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcde"); + assertHashesTo(0xde98d0f8250ec703L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdef"); + assertHashesTo(0xa7688d5834fa7d2aL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefg"); + assertHashesTo(0xad514e8250667cdeL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefgh"); + assertHashesTo(0xf562662deca536c3L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghi"); + assertHashesTo(0x9d1b8d2463cde877L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghij"); + assertHashesTo(0x24840f21eeb30861L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijk"); + assertHashesTo(0x40af2a3f14d31fdaL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijkl"); + assertHashesTo(0x3514ad5e964b5c73L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklm"); + assertHashesTo(0x7bd6243490571844L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn"); + assertHashesTo(0x273de93a3bddd9e8L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn1"); + assertHashesTo(0x18e6850c3e2f85beL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn12"); + assertHashesTo(0x044968ddc534d822L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn123"); + assertHashesTo(0x7430d9d503fe624dL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn1234"); + assertHashesTo(0xf0bb1e5239c1d88cL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn12345"); + assertHashesTo(0x2ee1ab348b7deaa0L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn123456"); + assertHashesTo(0x18b6da5df76680dfL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn1234567"); + assertHashesTo(0x06c95ee4ddc93743L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn12345678"); + assertHashesTo(0x6406e477d8ca608dL, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn123456789"); + assertHashesTo(0x203397a04178d470L, "abcdefghijklmn1234567890abcdefghijklmn1234567890abcdefghijklmn1234567890"); + } + + private void assertHashesTo(long hash, String key) { + assertEquals(hash, PredicateHash.hash64(key)); + } +} diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateOperatorTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateOperatorTest.java new file mode 100644 index 00000000000..b6de0bf3514 --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateOperatorTest.java @@ -0,0 +1,17 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import org.junit.Test; + +import static org.junit.Assert.assertTrue; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class PredicateOperatorTest { + + @Test + public void requireThatOperatorIsAPredicate() { + assertTrue(Predicate.class.isAssignableFrom(PredicateOperator.class)); + } +} diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateParserTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateParserTest.java new file mode 100644 index 00000000000..ee161c20feb --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateParserTest.java @@ -0,0 +1,155 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import org.junit.Test; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; +import static org.junit.Assert.fail; + +/** + * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + */ + +public class PredicateParserTest { + + @Test + public void requireThatParseErrorThrowsException() { + try { + Predicate.fromString("a in b"); + fail("Expected an exception"); + } catch (IllegalArgumentException e) { + assertEquals("line 1:5 no viable alternative at input 'b'", e.getMessage()); + } + } + + @Test + public void requireThatLexerErrorThrowsException() { + try { + Predicate.fromString("a-b in [b]"); + fail("Expected an exception"); + } catch (IllegalArgumentException e) { + assertEquals("line 1:2 no viable alternative at character 'b'", e.getMessage()); + } + } + + @Test + public void requireThatSingleValueLeafNodesParse() { + assertParsesTo("a in [b]", "a in [b]"); + assertParsesTo("0 in [1]", "0 in [1]"); + assertParsesTo("in in [in]", "in in [in]"); + assertParsesTo("and in [or]", "and in [or]"); + assertParsesTo("not in [not]", "not in [not]"); + assertParsesTo("'-234' in ['+200']", "'-234' in ['+200']"); + assertParsesTo("string in ['!@#$%^&*()[]']", "'string' in ['!@#$%^&*()[]']"); + assertParsesTo("a in [b]", "a in [b]"); + assertParsesTo("string in ['foo\\\\_\"\\t\\n\\f\\rbar']", + "string in ['foo\\\\_\\x22\\t\\n\\f\\rbar']"); + assertParsesTo("'\\xC3\\xB8' in [b]", "'ø' in [b]"); + assertParsesTo("'\\xEF\\xBF\\xBD' in [b]", "'\\xf8' in [b]"); + assertParsesTo("'\\xEF\\xBF\\xBD' in [b]", "'\\xef\\xbf\\xbd' in ['b']"); + assertParsesTo("'\\xE4\\xB8\\x9C\\xE8\\xA5\\xBF' in ['\\xE8\\x87\\xAA\\xE8\\xA1\\x8C\\xE8\\xBD\\xA6']", + "'东西' in ['自行车']"); + assertParsesTo("true in [false]", "true in [false]"); + } + + @Test + public void requireThatMultiValueLeafNodesParse() { + assertParsesTo("a in [b]", "a in [b]"); + assertParsesTo("0 in [1]", "0 in [1]"); + assertParsesTo("in in [and, in]", "in in [in, and]"); + assertParsesTo("a in [b, c, d, e, f]", "'a' in ['b', 'c', 'd', 'e', 'f']"); + } + + @Test + public void requireThatBothSingleAndDoubleQuotesWork() { + assertParsesTo("a in [b]", "'a' in ['b']"); + assertParsesTo("a in [b]", "\"a\" in [\"b\"]"); + assertParsesTo("'a\\x27' in [b]", "'a\\'' in ['b']"); + assertParsesTo("'a\"' in [b]", "\"a\\\"\" in [\"b\"]"); + } + + @Test + public void requireThatRangeLeafNodesParse() { + assertParsesTo("a in [0..100]", "a in [0..100]"); + assertParsesTo("0 in [..100]", "0 in [..100]"); + assertParsesTo("0 in [0..]", "0 in [0..]"); + assertParsesTo("0 in [..]", "0 in [..]"); + assertParsesTo("a in [-100..100]", "a in [-100..+100]"); + assertParsesTo("a in [-9223372036854775808..9223372036854775807]", + "a in [-9223372036854775808..+9223372036854775807]"); + } + + @Test + public void requireThatRangePartitionsAreIgnored() { + assertParsesTo("a in [0..100]", "a in [0..100 (a=0-99,a=100+[..0])]"); + assertParsesTo("a in [-100..0]", "a in [-100..0 (a=-0-99,a=-100+[..0])]"); + assertParsesTo("a in [-9223372036854775808..0]", "a in [-9223372036854775808..0 (a=-0-9223372036854775808)]"); + assertParsesTo("a in [2..8]", "a in [2..8 (a=0+[2..8])]"); + assertParsesTo("a in [0..8]", "a in [0..8 (a=0+[..8])]"); + assertParsesTo("a in [2..9]", "a in [2..9 (a=0+[2..])]"); + } + + @Test + public void requireThatNotInSetWorks() { + assertParsesTo("a not in [b]", "a not in [b]"); + } + + @Test + public void requireThatConjunctionWorks() { + assertParsesTo("a in [b] and c in [d]", "a in [b] and c in [d]"); + assertParsesTo("a in [b] and c in [d] and e in [f]", "a in [b] and c in [d] and e in [f]"); + } + + @Test + public void requireThatDisjunctionWorks() { + assertParsesTo("a in [b] or c in [d]", "a in [b] or c in [d]"); + assertParsesTo("a in [b] or c in [d] or e in [f]", "a in [b] or c in [d] or e in [f]"); + } + + @Test + public void requireThatParenthesesWorks() { + assertParsesTo("a in [b] or c in [d]", + "(a in [b]) or (c in [d])"); + assertParsesTo("a in [b] or c in [d] or e in [f]", + "(((a in [b]) or c in [d]) or e in [f])"); + assertParsesTo("(a in [b] and c in [d]) or e in [f]", + "a in [b] and c in [d] or e in [f]"); + assertParsesTo("a in [b] and (c in [d] or e in [f])", + "a in [b] and (c in [d] or e in [f])"); + assertParsesTo("a in [b] and (c in [d] or e in [f]) and g in [h]", + "a in [b] and (c in [d] or e in [f]) and g in [h]"); + } + + @Test + public void requireThatNotOutsideParenthesesWorks() { + assertParsesTo("a not in [b]", "not (a in [b])"); + } + + @Test + public void requireThatConjunctionsCanGetMoreThanTwoChildren() { + Predicate p = Predicate.fromString("a in [b] and c in [d] and e in [f] and g in [h]"); + assertTrue(p instanceof Conjunction); + assertEquals(4, ((Conjunction)p).getOperands().size()); + } + + @Test + public void requireThatDisjunctionsCanGetMoreThanTwoChildren() { + Predicate p = Predicate.fromString("a in [b] or c in [d] or e in [f] or g in [h]"); + assertTrue(p instanceof Disjunction); + assertEquals(4, ((Disjunction)p).getOperands().size()); + } + + @Test + public void requireThatBooleanCanBeParsed() { + assertParsesTo("true", "true"); + assertParsesTo("false", "false"); + assertParsesTo("true or false", "true or false"); + assertParsesTo("false and true", "false and true"); + } + + private static void assertParsesTo(String expected, String predicate_str) { + assertEquals(expected, // TODO: Predicate.fromString(expected) + Predicate.fromString(predicate_str).toString()); + } +} diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateTest.java new file mode 100644 index 00000000000..621378f394b --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateTest.java @@ -0,0 +1,110 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import org.junit.Test; + +import static com.yahoo.document.predicate.Predicates.and; +import static com.yahoo.document.predicate.Predicates.feature; +import static com.yahoo.document.predicate.Predicates.not; +import static com.yahoo.document.predicate.Predicates.or; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class PredicateTest { + + @Test + public void requireThatPredicateIsCloneable() { + assertTrue(Cloneable.class.isAssignableFrom(Predicate.class)); + } + + @Test + public void requireThatANDConstructsAConjunction() { + Predicate foo = SimplePredicates.newString("foo"); + Predicate bar = SimplePredicates.newString("bar"); + Predicate predicate = and(foo, bar); + assertEquals(Conjunction.class, predicate.getClass()); + assertEquals(new Conjunction(foo, bar), predicate); + } + + @Test + public void requireThatORConstructsADisjunction() { + Predicate foo = SimplePredicates.newString("foo"); + Predicate bar = SimplePredicates.newString("bar"); + Predicate predicate = or(foo, bar); + assertEquals(Disjunction.class, predicate.getClass()); + assertEquals(new Disjunction(foo, bar), predicate); + } + + @Test + public void requireThatNOTConstructsANegation() { + Predicate foo = SimplePredicates.newString("foo"); + Predicate predicate = not(foo); + assertEquals(Negation.class, predicate.getClass()); + assertEquals(new Negation(foo), predicate); + } + + @Test + public void requireThatFeatureBuilderCanConstructFeatureRange() { + assertEquals(new FeatureRange("key", 6L, 9L), + feature("key").inRange(6, 9)); + assertEquals(new Negation(new FeatureRange("key", 6L, 9L)), + feature("key").notInRange(6, 9)); + assertEquals(new FeatureRange("key", 7L, null), + feature("key").greaterThan(6)); + assertEquals(new FeatureRange("key", 6L, null), + feature("key").greaterThanOrEqualTo(6)); + assertEquals(new FeatureRange("key", null, 5L), + feature("key").lessThan(6)); + assertEquals(new FeatureRange("key", null, 9L), + feature("key").lessThanOrEqualTo(9)); + } + + @Test + public void requireThatFeatureBuilderCanConstructFeatureSet() { + assertEquals(new FeatureSet("key", "valueA", "valueB"), + feature("key").inSet("valueA", "valueB")); + assertEquals(new Negation(new FeatureSet("key", "valueA", "valueB")), + feature("key").notInSet("valueA", "valueB")); + } + + @Test + public void requireThatPredicatesCanBeConstructedUsingConstructors() { + assertEquals("country in [no, se] and age in [20..30]", + new Conjunction(new FeatureSet("country", "no", "se"), + new FeatureRange("age", 20L, 30L)).toString()); + assertEquals("country not in [no, se] or age in [20..] or height in [..160]", + new Disjunction(new Negation(new FeatureSet("country", "no", "se")), + new FeatureRange("age", 20L, null), + new FeatureRange("height", null, 160L)).toString()); + } + + @Test + public void requireThatPredicatesCanBeBuiltUsingChainedMethodCalls() { + assertEquals("country not in [no, se] or age in [20..] or height in [..160]", + new Disjunction() + .addOperand(new Negation(new FeatureSet("country").addValue("no").addValue("se"))) + .addOperand(new FeatureRange("age").setFromInclusive(20L)) + .addOperand(new FeatureRange("height").setToInclusive(160L)) + .toString()); + } + + @Test + public void requireThatPredicatesCanBeBuiltUsingSeparateMethodCalls() { + Conjunction conjunction = new Conjunction(); + FeatureSet countrySet = new FeatureSet("country"); + countrySet.addValue("no"); + countrySet.addValue("se"); + conjunction.addOperand(countrySet); + FeatureRange ageRange = new FeatureRange("age"); + ageRange.setFromInclusive(20L); + conjunction.addOperand(ageRange); + FeatureRange heightRange = new FeatureRange("height"); + heightRange.setToInclusive(160L); + conjunction.addOperand(heightRange); + assertEquals("country in [no, se] and age in [20..] and height in [..160]", + conjunction.toString()); + } +} diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateValueTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateValueTest.java new file mode 100644 index 00000000000..810e9a8717c --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicateValueTest.java @@ -0,0 +1,17 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import org.junit.Test; + +import static org.junit.Assert.assertTrue; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class PredicateValueTest { + + @Test + public void requireThatValueIsAPredicate() { + assertTrue(Predicate.class.isAssignableFrom(PredicateValue.class)); + } +} diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicatesTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicatesTest.java new file mode 100644 index 00000000000..22832eedeff --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/PredicatesTest.java @@ -0,0 +1,38 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import org.junit.Test; + +import static com.yahoo.document.predicate.Predicates.and; +import static com.yahoo.document.predicate.Predicates.feature; +import static com.yahoo.document.predicate.Predicates.not; +import static com.yahoo.document.predicate.Predicates.or; +import static com.yahoo.document.predicate.Predicates.value; +import static org.junit.Assert.assertEquals; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class PredicatesTest { + + @Test + public void requireThatApiIsUsable() { + assertEquals( + new Disjunction( + new Conjunction(new FeatureSet("country", "de", "no"), + new Negation(new FeatureSet("gender", "female")), + new FeatureRange("age", 6L, 9L)), + new Conjunction(new Negation(new FeatureSet("country", "se")), + new FeatureSet("gender", "female"), + new FeatureRange("age", 69L, null))), + or(and(feature("country").inSet("de", "no"), + feature("gender").notInSet("female"), + feature("age").inRange(6, 9)), + and(not(feature("country").inSet("se")), + feature("gender").inSet("female"), + feature("age").greaterThanOrEqualTo(69)))); + + assertEquals(new BooleanPredicate(true), value(true)); + assertEquals(new BooleanPredicate(false), value(false)); + } +} diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/RangeEdgePartitionTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/RangeEdgePartitionTest.java new file mode 100644 index 00000000000..d9f6714d8c8 --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/RangeEdgePartitionTest.java @@ -0,0 +1,62 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import org.junit.Test; + +import static org.junit.Assert.*; +import static org.junit.Assert.assertEquals; + +/** + * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + */ +public class RangeEdgePartitionTest { + + @Test + public void requireThatRangeEdgePartitionIsAValue() { + assertTrue(PredicateValue.class.isAssignableFrom(RangeEdgePartition.class)); + } + + @Test + public void requireThatConstructorsWork() { + RangeEdgePartition part = new RangeEdgePartition("foo=10", 10, 0, -1); + assertEquals("foo=10", part.getLabel()); + assertEquals(0, part.getLowerBound()); + assertEquals(-1, part.getUpperBound()); + } + + @Test + public void requireThatCloneIsImplemented() throws CloneNotSupportedException { + RangeEdgePartition node1 = new RangeEdgePartition("foo=10", 10, 0, 0); + RangeEdgePartition node2 = node1.clone(); + assertEquals(node1, node2); + assertNotSame(node1, node2); + } + + @Test + public void requireThatHashCodeIsImplemented() { + assertEquals(new RangeEdgePartition("foo=-10", 10, 2, 3).hashCode(), + new RangeEdgePartition("foo=-10", 10, 2, 3).hashCode()); + } + + @Test + public void requireThatEqualsIsImplemented() { + RangeEdgePartition lhs = new RangeEdgePartition("foo=10", 10, 5, 10); + assertTrue(lhs.equals(lhs)); + assertFalse(lhs.equals(new Object())); + + RangeEdgePartition rhs = new RangeEdgePartition("foo=20", 20, 0, 0); + assertFalse(lhs.equals(rhs)); + rhs = new RangeEdgePartition("foo=10", 10, 5, 10); + assertTrue(lhs.equals(rhs)); + assertFalse(lhs.equals(new RangeEdgePartition("foo=10", 10, 5, 11))); + assertFalse(lhs.equals(new RangeEdgePartition("foo=10", 10, 6, 10))); + assertFalse(lhs.equals(new RangeEdgePartition("foo=10", 11, 5, 10))); + assertFalse(lhs.equals(new RangeEdgePartition("foo=11", 10, 5, 10))); + } + + @Test + public void requireThatKeyIsEscapedInToString() { + assertEquals("foo=10+[2..3]", new RangeEdgePartition("foo=10", 10, 2, 3).toString()); + assertEquals("'\\foo=10'+[2..3]", new RangeEdgePartition("\foo=10", 10, 2, 3).toString()); + assertEquals("'\\x27foo\\x27=10'+[2..3]", new RangeEdgePartition("'foo'=10", 10, 2, 3).toString()); + }} diff --git a/predicate-search-core/src/test/java/com/yahoo/document/predicate/RangePartitionTest.java b/predicate-search-core/src/test/java/com/yahoo/document/predicate/RangePartitionTest.java new file mode 100644 index 00000000000..b9d2c865e9b --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/document/predicate/RangePartitionTest.java @@ -0,0 +1,60 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import org.junit.Test; + +import static org.junit.Assert.*; +import static org.junit.Assert.assertEquals; + +/** + * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + */ +public class RangePartitionTest { + + @Test + public void requireThatRangePartitionIsAValue() { + assertTrue(PredicateValue.class.isAssignableFrom(RangePartition.class)); + } + + @Test + public void requireThatConstructorsWork() { + RangePartition part = new RangePartition("foo=10-19"); + assertEquals("foo=10-19", part.getLabel()); + part = new RangePartition("foo", 10, 19, false); + assertEquals("foo=10-19", part.getLabel()); + part = new RangePartition("foo", 10, 19, true); + assertEquals("foo=-19-10", part.getLabel()); + } + + @Test + public void requireThatCloneIsImplemented() throws CloneNotSupportedException { + RangePartition node1 = new RangePartition("foo=300-399"); + RangePartition node2 = node1.clone(); + assertEquals(node1, node2); + assertNotSame(node1, node2); + } + + @Test + public void requireThatHashCodeIsImplemented() { + assertEquals(new RangePartition("foo=0-9").hashCode(), new RangePartition("foo=0-9").hashCode()); + } + + @Test + public void requireThatEqualsIsImplemented() { + RangePartition lhs = new RangePartition("foo=10-19"); + assertTrue(lhs.equals(lhs)); + assertFalse(lhs.equals(new Object())); + + RangePartition rhs = new RangePartition("bar=1000-1999"); + assertFalse(lhs.equals(rhs)); + rhs = new RangePartition("foo=10-19"); + assertTrue(lhs.equals(rhs)); + } + + @Test + public void requireThatKeyIsEscapedInToString() { + assertEquals("foo=10-19", new RangePartition("foo=10-19").toString()); + assertEquals("'\\foo=10-19'", new RangePartition("\foo=10-19").toString()); + assertEquals("'\\x27foo\\x27=10-19'", new RangePartition("'foo'=10-19").toString()); + } +} diff --git a/predicate-search-core/src/test/java/com/yahoo/search/predicate/PredicateQueryParserTest.java b/predicate-search-core/src/test/java/com/yahoo/search/predicate/PredicateQueryParserTest.java new file mode 100644 index 00000000000..dcee3a0c55d --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/search/predicate/PredicateQueryParserTest.java @@ -0,0 +1,43 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate; + +import org.junit.Test; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.List; + +import static org.hamcrest.CoreMatchers.is; +import static org.junit.Assert.assertThat; + +/** + * @author bjorncs + */ +public class PredicateQueryParserTest { + + @Test + public void require_that_json_is_correctly_parsed() { + String json = + "{" + + " \"features\":[" + + " {\"k\":\"k1\",\"v\":\"value1\",\"s\":\"0x1\"}," + + " {\"k\":\"k2\",\"v\":\"value2\",\"s\":\"0x3\"}" + + " ],\"rangeFeatures\":[" + + " {\"k\":\"range1\",\"v\":123456789123,\"s\":\"0xffff\"}," + + " {\"k\":\"range2\",\"v\":0,\"s\":\"0xffffffffffffffff\"}" + + " ]" + + "}"; + + PredicateQueryParser parser = new PredicateQueryParser(); + List<String> result = new ArrayList<>(); + parser.parseJsonQuery( + json, + (k, v, s) -> result.add(String.format("%s:%s:%#x", k, v, s)), + (k, v, s) -> result.add(String.format("%s:%d:%#x", k, v, s))); + + assertThat(result, is(Arrays.asList( + "k1:value1:0x1", "k2:value2:0x3", + "range1:123456789123:0xffff", "range2:0:0xffffffffffffffff"))); + } + +} diff --git a/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/AndOrSimplifierTest.java b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/AndOrSimplifierTest.java new file mode 100644 index 00000000000..4ec6c496e73 --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/AndOrSimplifierTest.java @@ -0,0 +1,134 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import com.yahoo.document.predicate.Predicate; +import org.junit.Test; + +import static com.yahoo.document.predicate.Predicates.and; +import static com.yahoo.document.predicate.Predicates.feature; +import static com.yahoo.document.predicate.Predicates.not; +import static com.yahoo.document.predicate.Predicates.or; +import static org.junit.Assert.assertEquals; + +/** + * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + */ +public class AndOrSimplifierTest { + + @Test + public void requireThatNestedConjunctionsAreCollapsed() { + assertSimplified(and(feature("a").inSet("b"), + feature("c").inSet("d")), + and(and(feature("a").inSet("b"), + feature("c").inSet("d")))); + } + + @Test + public void requireThatNestedConjuctionsAreCollapsedInPlace() { + assertSimplified(and(feature("a").inSet("b"), + feature("c").inSet("d"), + feature("e").inSet("f")), + and(feature("a").inSet("b"), + and(feature("c").inSet("d")), + feature("e").inSet("f"))); + } + + @Test + public void requireThatDeeplyNestedConjunctionsAreCollapsed() { + assertSimplified(and(feature("a").inSet("b"), + feature("c").inSet("d"), + feature("e").inSet("f"), + feature("g").inSet("h"), + feature("i").inSet("j")), + and(feature("a").inSet("b"), + and(feature("c").inSet("d")), + feature("e").inSet("f"), + and(and(feature("g").inSet("h"), + feature("i").inSet("j"))))); + } + + @Test + public void requireThatNestedDisjunctionsAreCollapsed() { + assertSimplified(or(feature("a").inSet("b"), + feature("c").inSet("d")), + or(or(feature("a").inSet("b"), + feature("c").inSet("d")))); + } + + @Test + public void requireThatNestedDisjuctionsAreCollapsedInPlace() { + assertSimplified(or(feature("a").inSet("b"), + feature("c").inSet("d"), + feature("e").inSet("f")), + or(feature("a").inSet("b"), + or(feature("c").inSet("d")), + feature("e").inSet("f"))); + } + + @Test + public void requireThatDeeplyNestedDisjunctionsAreCollapsed() { + assertSimplified(or(feature("a").inSet("b"), + feature("c").inSet("d"), + feature("e").inSet("f"), + feature("g").inSet("h"), + feature("i").inSet("j")), + or(feature("a").inSet("b"), + or(feature("c").inSet("d")), + feature("e").inSet("f"), + or(or(feature("g").inSet("h"), + feature("i").inSet("j"))))); + } + + @Test + public void requireThatConjunctionsAndDisjunctionsAreNotCollapsed() { + assertSimplified(and(or(feature("a").inSet("b"), + feature("c").inSet("d"))), + and(or(feature("a").inSet("b"), + feature("c").inSet("d")))); + } + + @Test + public void requireThatNotOrIsTranslatedToAndNot() { + assertSimplified( + and(feature("a").notInSet("b"), feature("c").inSet("d")), + not(or(feature("a").inSet("b"), feature("c").notInSet("d")))); + } + + @Test + public void requireThatNotAndIsTranslatedToOrNot() { + assertSimplified( + or(feature("a").notInSet("b"), feature("c").inSet("d")), + not(and(feature("a").inSet("b"), feature("c").notInSet("d")))); + } + + @Test + public void requireThatTreeWithoutNotIsNotAffected() { + assertSimplified( + and(feature("a").inSet("b"), feature("c").notInSet("d")), + and(feature("a").inSet("b"), feature("c").notInSet("d"))); + assertSimplified( + or(feature("a").inSet("b"), feature("c").notInSet("d")), + or(feature("a").inSet("b"), feature("c").notInSet("d"))); + assertSimplified(feature("a").inSet("b"), feature("a").inSet("b")); + } + + @Test + public void requireThatNotOfNotIsRemoved() { + assertSimplified(feature("a").inSet("b"), not(not(feature("a").inSet("b")))); + assertSimplified(feature("a").inSet("b"), not(feature("a").notInSet("b"))); + assertSimplified(feature("a").notInSet("b"), not(not(feature("a").notInSet("b")))); + } + + @Test + public void requireThatNotBeneathAndIsTranslated() { + assertSimplified( + and(feature("a").notInSet("b"), feature("c").inSet("d"), feature("b").inSet("c")), + and(not(or(feature("a").inSet("b"), feature("c").notInSet("d"))), feature("b").inSet("c"))); + } + + private static void assertSimplified(Predicate expected, Predicate input) { + AndOrSimplifier simplifier = new AndOrSimplifier(); + Predicate actual = simplifier.process(input, new PredicateOptions(10)); + assertEquals(expected, actual); + } +} diff --git a/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/BooleanSimplifierTest.java b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/BooleanSimplifierTest.java new file mode 100644 index 00000000000..37d2352df57 --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/BooleanSimplifierTest.java @@ -0,0 +1,60 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import com.yahoo.document.predicate.Predicate; +import org.junit.Test; + +import static com.yahoo.document.predicate.Predicates.*; +import static org.junit.Assert.assertEquals; + +/** + * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + */ +public class BooleanSimplifierTest { + + @Test + public void requireThatOrOfTrueIsTrue() { + assertSimplifiedTo(value(true), or(feature("a").inSet("b"), value(true))); + } + + @Test + public void requireThatFalseChildrenOfOrAreRemoved() { + assertSimplifiedTo(feature("a").inSet("b"), or(feature("a").inSet("b"), value(false))); + } + + @Test + public void requireThatAndOfFalseIsFalse() { + assertSimplifiedTo(value(false), and(feature("a").inSet("b"), value(false))); + } + + @Test + public void requireThatTrueChildrenOfAndAreRemoved() { + assertSimplifiedTo(feature("a").inSet("b"), and(feature("a").inSet("b"), value(true))); + } + + @Test + public void requireThatSingleChildAndOrAreRemoved() { + assertSimplifiedTo(feature("a").inSet("b"), and(or(and(feature("a").inSet("b"))))); + } + + @Test + public void requireThatValueChildrenOfNotAreInverted() { + assertSimplifiedTo(value(true), not(value(false))); + assertSimplifiedTo(value(false), not(value(true))); + assertSimplifiedTo(value(true), not(not(not(value(false))))); + assertSimplifiedTo(value(true), not(not(not(and(feature("a").inSet("b"), value(false)))))); + } + + @Test + public void requireThatComplexExpressionIsSimplified() { + assertSimplifiedTo( + Predicate.fromString("'pub_entity' not in [301951]"), + Predicate.fromString("true and true and true and true and true and 'pub_entity' not in [301951] and ((true and true and true and true) or (true and true and true and true) or (true and true and true and true and 'pub_entity' in [86271]))")); + } + + private void assertSimplifiedTo(Predicate expected, Predicate input) { + BooleanSimplifier simplifier = new BooleanSimplifier(); + Predicate actual = simplifier.process(input, new PredicateOptions(10)); + assertEquals(expected, actual); + } +} diff --git a/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/ComplexNodeTransformerTest.java b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/ComplexNodeTransformerTest.java new file mode 100644 index 00000000000..45cdabfb4f2 --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/ComplexNodeTransformerTest.java @@ -0,0 +1,604 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import com.yahoo.document.predicate.FeatureRange; +import com.yahoo.document.predicate.Predicate; +import com.yahoo.document.predicate.RangePartition; +import org.junit.Test; + +import static org.junit.Assert.assertEquals; + +/** + * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + */ +public class ComplexNodeTransformerTest { + + private long lowerBound = 0x8000000000000000L; + private long upperBound = 0x7fffffffffffffffL; + + private void testConvert(String predicate, String expected) { + int defaultArity = 10; + testConvert(predicate, expected, defaultArity); + } + + private void testConvert(String predicate, String expected, int arity) { + Predicate p = Predicate.fromString(predicate); + ComplexNodeTransformer transformer = new ComplexNodeTransformer(); + Predicate converted = transformer.process(p, new PredicateOptions(arity, lowerBound, upperBound)); + assertEquals(expected, converted.toString()); + } + + @Test + public void requireThatSingleValueRangesAreConverted() { + testConvert("foo in [0..0]", "foo in [0..0 (foo=0+[..0])]"); + testConvert("foo in [5..5]", "foo in [5..5 (foo=0+[5..5])]"); + testConvert("foo in [9..9]", "foo in [9..9 (foo=0+[9..])]"); + testConvert("foo in [10..10]", "foo in [10..10 (foo=10+[..0])]"); + testConvert("foo in [-5..-5]", "foo in [-5..-5 (foo=-0+[5..5])]"); + testConvert("foo in [-9..-9]", "foo in [-9..-9 (foo=-0+[9..])]"); + testConvert("foo in [-10..-10]", "foo in [-10..-10 (foo=-10+[..0])]"); + } + + @Test + public void requireThatVeryShortRangesAreConverted() { + testConvert("foo in [10..17]", "foo in [10..17 (foo=10+[..7])]"); + testConvert("foo in [12..19]", "foo in [12..19 (foo=10+[2..])]"); + testConvert("foo in [11..18]", "foo in [11..18 (foo=10+[1..8])]"); + testConvert("foo in [7..13]", "foo in [7..13 (foo=0+[7..],foo=10+[..3])]"); + testConvert("foo in [-17..-10]", "foo in [-17..-10 (foo=-10+[..7])]"); + testConvert("foo in [-19..-12]", "foo in [-19..-12 (foo=-10+[2..])]"); + testConvert("foo in [-18..-11]", "foo in [-18..-11 (foo=-10+[1..8])]"); + testConvert("foo in [-13..-7]", "foo in [-13..-7 (foo=-0+[7..],foo=-10+[..3])]"); + testConvert("foo in [-5..4]", "foo in [-5..4 (foo=-0+[..5],foo=0+[..4])]"); + } + + @Test + public void requireThatShortRangeIsConverted() { + testConvert("foo in [9..19]", "foo in [9..19 (foo=0+[9..],foo=10-19)]"); + testConvert("foo in [10..19]", "foo in [10..19 (foo=10-19)]"); + testConvert("foo in [10..20]", "foo in [10..20 (foo=20+[..0],foo=10-19)]"); + testConvert("foo in [12..21]", "foo in [12..21 (foo=10+[2..],foo=20+[..1])]"); + testConvert("foo in [-19..-9]", "foo in [-19..-9 (foo=-0+[9..],foo=-19-10)]"); + testConvert("foo in [-19..-10]", "foo in [-19..-10 (foo=-19-10)]"); + testConvert("foo in [-20..-10]", "foo in [-20..-10 (foo=-20+[..0],foo=-19-10)]"); + testConvert("foo in [-21..-12]", "foo in [-21..-12 (foo=-10+[2..],foo=-20+[..1])]"); + testConvert("foo in [-9..9]", "foo in [-9..9 (foo=-9-0,foo=0-9)]"); + testConvert("foo in [-10..10]", "foo in [-10..10 (foo=-10+[..0],foo=10+[..0],foo=-9-0,foo=0-9)]"); + } + + @Test + public void requireThatMediumRangeIsConverted() { + testConvert("foo in [10..39]", "foo in [10..39 (foo=10-19,foo=20-29,foo=30-39)]"); + testConvert("foo in [10..38]", "foo in [10..38 (foo=30+[..8],foo=10-19,foo=20-29)]"); + testConvert("foo in [18..39]", "foo in [18..39 (foo=10+[8..],foo=20-29,foo=30-39)]"); + testConvert("foo in [8..38]", "foo in [8..38 (foo=0+[8..],foo=30+[..8],foo=10-19,foo=20-29)]"); + testConvert("foo in [-39..-10]", "foo in [-39..-10 (foo=-19-10,foo=-29-20,foo=-39-30)]"); + testConvert("foo in [-38..-10]", "foo in [-38..-10 (foo=-30+[..8],foo=-19-10,foo=-29-20)]"); + testConvert("foo in [-39..-18]", "foo in [-39..-18 (foo=-10+[8..],foo=-29-20,foo=-39-30)]"); + testConvert("foo in [-38..-8]", "foo in [-38..-8 (foo=-0+[8..],foo=-30+[..8],foo=-19-10,foo=-29-20)]"); + testConvert("foo in [-19..19]", "foo in [-19..19 (foo=-9-0,foo=-19-10,foo=0-9,foo=10-19)]"); + } + + @Test + public void requireThatLargeRangeIsConverted() { + testConvert("foo in [10..199]", "foo in [10..199 (foo=10-19,foo=20-29,foo=30-39,foo=40-49,foo=50-59,foo=60-69,foo=70-79,foo=80-89,foo=90-99,foo=100-199)]"); + testConvert("foo in [8..207]", "foo in [8..207 (foo=0+[8..],foo=200+[..7],foo=10-19,foo=20-29,foo=30-39,foo=40-49,foo=50-59,foo=60-69,foo=70-79,foo=80-89,foo=90-99,foo=100-199)]"); + testConvert("foo in [999..2001]", "foo in [999..2001 (foo=990+[9..],foo=2000+[..1],foo=1000-1999)]"); + testConvert("foo in [999..2009]", "foo in [999..2009 (foo=990+[9..],foo=2000-2009,foo=1000-1999)]"); + testConvert("foo in [999..2099]", "foo in [999..2099 (foo=990+[9..],foo=2000-2099,foo=1000-1999)]"); + testConvert("foo in [999..2999]", "foo in [999..2999 (foo=990+[9..],foo=1000-1999,foo=2000-2999)]"); + testConvert("foo in [-199..-10]", "foo in [-199..-10 (foo=-19-10,foo=-29-20,foo=-39-30,foo=-49-40,foo=-59-50,foo=-69-60,foo=-79-70,foo=-89-80,foo=-99-90,foo=-199-100)]"); + testConvert("foo in [-207..-8]", "foo in [-207..-8 (foo=-0+[8..],foo=-200+[..7],foo=-19-10,foo=-29-20,foo=-39-30,foo=-49-40,foo=-59-50,foo=-69-60,foo=-79-70,foo=-89-80,foo=-99-90,foo=-199-100)]"); + testConvert("foo in [-2001..-999]", "foo in [-2001..-999 (foo=-990+[9..],foo=-2000+[..1],foo=-1999-1000)]"); + testConvert("foo in [-999..999]", "foo in [-999..999 (foo=-999-0,foo=0-999)]"); + } + + @Test + public void requireThatLongMaxIsConverted() { + testConvert("foo in [0..9223372036854775807]", + "foo in [0..9223372036854775807 (" + + "foo=9223372036854775800+[..7]," + + "foo=9223372036854775000-9223372036854775099," + + "foo=9223372036854775100-9223372036854775199," + + "foo=9223372036854775200-9223372036854775299," + + "foo=9223372036854775300-9223372036854775399," + + "foo=9223372036854775400-9223372036854775499," + + "foo=9223372036854775500-9223372036854775599," + + "foo=9223372036854775600-9223372036854775699," + + "foo=9223372036854775700-9223372036854775799," + + "foo=9223372036854770000-9223372036854770999," + + "foo=9223372036854771000-9223372036854771999," + + "foo=9223372036854772000-9223372036854772999," + + "foo=9223372036854773000-9223372036854773999," + + "foo=9223372036854774000-9223372036854774999," + + "foo=9223372036854700000-9223372036854709999," + + "foo=9223372036854710000-9223372036854719999," + + "foo=9223372036854720000-9223372036854729999," + + "foo=9223372036854730000-9223372036854739999," + + "foo=9223372036854740000-9223372036854749999," + + "foo=9223372036854750000-9223372036854759999," + + "foo=9223372036854760000-9223372036854769999," + + "foo=9223372036854000000-9223372036854099999," + + "foo=9223372036854100000-9223372036854199999," + + "foo=9223372036854200000-9223372036854299999," + + "foo=9223372036854300000-9223372036854399999," + + "foo=9223372036854400000-9223372036854499999," + + "foo=9223372036854500000-9223372036854599999," + + "foo=9223372036854600000-9223372036854699999," + + "foo=9223372036850000000-9223372036850999999," + + "foo=9223372036851000000-9223372036851999999," + + "foo=9223372036852000000-9223372036852999999," + + "foo=9223372036853000000-9223372036853999999," + + "foo=9223372036800000000-9223372036809999999," + + "foo=9223372036810000000-9223372036819999999," + + "foo=9223372036820000000-9223372036829999999," + + "foo=9223372036830000000-9223372036839999999," + + "foo=9223372036840000000-9223372036849999999," + + "foo=9223372036000000000-9223372036099999999," + + "foo=9223372036100000000-9223372036199999999," + + "foo=9223372036200000000-9223372036299999999," + + "foo=9223372036300000000-9223372036399999999," + + "foo=9223372036400000000-9223372036499999999," + + "foo=9223372036500000000-9223372036599999999," + + "foo=9223372036600000000-9223372036699999999," + + "foo=9223372036700000000-9223372036799999999," + + "foo=9223372030000000000-9223372030999999999," + + "foo=9223372031000000000-9223372031999999999," + + "foo=9223372032000000000-9223372032999999999," + + "foo=9223372033000000000-9223372033999999999," + + "foo=9223372034000000000-9223372034999999999," + + "foo=9223372035000000000-9223372035999999999," + + "foo=9223372000000000000-9223372009999999999," + + "foo=9223372010000000000-9223372019999999999," + + "foo=9223372020000000000-9223372029999999999," + + "foo=9223370000000000000-9223370999999999999," + + "foo=9223371000000000000-9223371999999999999," + + "foo=9223300000000000000-9223309999999999999," + + "foo=9223310000000000000-9223319999999999999," + + "foo=9223320000000000000-9223329999999999999," + + "foo=9223330000000000000-9223339999999999999," + + "foo=9223340000000000000-9223349999999999999," + + "foo=9223350000000000000-9223359999999999999," + + "foo=9223360000000000000-9223369999999999999," + + "foo=9223000000000000000-9223099999999999999," + + "foo=9223100000000000000-9223199999999999999," + + "foo=9223200000000000000-9223299999999999999," + + "foo=9220000000000000000-9220999999999999999," + + "foo=9221000000000000000-9221999999999999999," + + "foo=9222000000000000000-9222999999999999999," + + "foo=9200000000000000000-9209999999999999999," + + "foo=9210000000000000000-9219999999999999999," + + "foo=9000000000000000000-9099999999999999999," + + "foo=9100000000000000000-9199999999999999999," + + "foo=0-999999999999999999," + + "foo=1000000000000000000-1999999999999999999," + + "foo=2000000000000000000-2999999999999999999," + + "foo=3000000000000000000-3999999999999999999," + + "foo=4000000000000000000-4999999999999999999," + + "foo=5000000000000000000-5999999999999999999," + + "foo=6000000000000000000-6999999999999999999," + + "foo=7000000000000000000-7999999999999999999," + + "foo=8000000000000000000-8999999999999999999)]"); + + testConvert("foo in [9223372036854775807..9223372036854775807]", "foo in [9223372036854775807..9223372036854775807 (foo=9223372036854775800+[7..7])]"); + } + + @Test + public void requireThatLongMinIsConverted() { + testConvert("foo in [-9223372036854775808..-1]", + "foo in [-9223372036854775808..-1 (" + + "foo=-9223372036854775800+[..8]," + + "foo=-9223372036854775099-9223372036854775000," + + "foo=-9223372036854775199-9223372036854775100," + + "foo=-9223372036854775299-9223372036854775200," + + "foo=-9223372036854775399-9223372036854775300," + + "foo=-9223372036854775499-9223372036854775400," + + "foo=-9223372036854775599-9223372036854775500," + + "foo=-9223372036854775699-9223372036854775600," + + "foo=-9223372036854775799-9223372036854775700," + + "foo=-9223372036854770999-9223372036854770000," + + "foo=-9223372036854771999-9223372036854771000," + + "foo=-9223372036854772999-9223372036854772000," + + "foo=-9223372036854773999-9223372036854773000," + + "foo=-9223372036854774999-9223372036854774000," + + "foo=-9223372036854709999-9223372036854700000," + + "foo=-9223372036854719999-9223372036854710000," + + "foo=-9223372036854729999-9223372036854720000," + + "foo=-9223372036854739999-9223372036854730000," + + "foo=-9223372036854749999-9223372036854740000," + + "foo=-9223372036854759999-9223372036854750000," + + "foo=-9223372036854769999-9223372036854760000," + + "foo=-9223372036854099999-9223372036854000000," + + "foo=-9223372036854199999-9223372036854100000," + + "foo=-9223372036854299999-9223372036854200000," + + "foo=-9223372036854399999-9223372036854300000," + + "foo=-9223372036854499999-9223372036854400000," + + "foo=-9223372036854599999-9223372036854500000," + + "foo=-9223372036854699999-9223372036854600000," + + "foo=-9223372036850999999-9223372036850000000," + + "foo=-9223372036851999999-9223372036851000000," + + "foo=-9223372036852999999-9223372036852000000," + + "foo=-9223372036853999999-9223372036853000000," + + "foo=-9223372036809999999-9223372036800000000," + + "foo=-9223372036819999999-9223372036810000000," + + "foo=-9223372036829999999-9223372036820000000," + + "foo=-9223372036839999999-9223372036830000000," + + "foo=-9223372036849999999-9223372036840000000," + + "foo=-9223372036099999999-9223372036000000000," + + "foo=-9223372036199999999-9223372036100000000," + + "foo=-9223372036299999999-9223372036200000000," + + "foo=-9223372036399999999-9223372036300000000," + + "foo=-9223372036499999999-9223372036400000000," + + "foo=-9223372036599999999-9223372036500000000," + + "foo=-9223372036699999999-9223372036600000000," + + "foo=-9223372036799999999-9223372036700000000," + + "foo=-9223372030999999999-9223372030000000000," + + "foo=-9223372031999999999-9223372031000000000," + + "foo=-9223372032999999999-9223372032000000000," + + "foo=-9223372033999999999-9223372033000000000," + + "foo=-9223372034999999999-9223372034000000000," + + "foo=-9223372035999999999-9223372035000000000," + + "foo=-9223372009999999999-9223372000000000000," + + "foo=-9223372019999999999-9223372010000000000," + + "foo=-9223372029999999999-9223372020000000000," + + "foo=-9223370999999999999-9223370000000000000," + + "foo=-9223371999999999999-9223371000000000000," + + "foo=-9223309999999999999-9223300000000000000," + + "foo=-9223319999999999999-9223310000000000000," + + "foo=-9223329999999999999-9223320000000000000," + + "foo=-9223339999999999999-9223330000000000000," + + "foo=-9223349999999999999-9223340000000000000," + + "foo=-9223359999999999999-9223350000000000000," + + "foo=-9223369999999999999-9223360000000000000," + + "foo=-9223099999999999999-9223000000000000000," + + "foo=-9223199999999999999-9223100000000000000," + + "foo=-9223299999999999999-9223200000000000000," + + "foo=-9220999999999999999-9220000000000000000," + + "foo=-9221999999999999999-9221000000000000000," + + "foo=-9222999999999999999-9222000000000000000," + + "foo=-9209999999999999999-9200000000000000000," + + "foo=-9219999999999999999-9210000000000000000," + + "foo=-9099999999999999999-9000000000000000000," + + "foo=-9199999999999999999-9100000000000000000," + + "foo=-999999999999999999-0," + + "foo=-1999999999999999999-1000000000000000000," + + "foo=-2999999999999999999-2000000000000000000," + + "foo=-3999999999999999999-3000000000000000000," + + "foo=-4999999999999999999-4000000000000000000," + + "foo=-5999999999999999999-5000000000000000000," + + "foo=-6999999999999999999-6000000000000000000," + + "foo=-7999999999999999999-7000000000000000000," + + "foo=-8999999999999999999-8000000000000000000)]"); + testConvert("foo in [-9223372036854775808..-9223372036854775808]", "foo in [-9223372036854775808..-9223372036854775808 (foo=-9223372036854775800+[8..8])]"); + } + + @Test + public void requireThatLowAritiesWork() { + testConvert("foo in [10..39]", "foo in [10..39 (foo=10-11,foo=12-15,foo=32-39,foo=16-31)]", 2); + testConvert("foo in [2..32]", "foo in [2..32 (foo=32+[..0],foo=2-3,foo=4-7,foo=8-15,foo=16-31)]", 2); + testConvert("foo in [-31..63]", "foo in [-31..63 (foo=-31-0,foo=0-63)]", 2); + testConvert("foo in [0..9223372036854775807]", "foo in [0..9223372036854775807 (foo=0-9223372036854775807)]", 2); + testConvert("foo in [9223372036854775807..9223372036854775807]", "foo in [9223372036854775807..9223372036854775807 (foo=9223372036854775806+[1..])]", 2); + testConvert("foo in [-9223372036854775808..-1]", "foo in [-9223372036854775808..-1 (foo=-9223372036854775808+[..0],foo=-9223372036854775807-0)]", 2); + testConvert("foo in [-9223372036854775808..-9223372036854775808]", "foo in [-9223372036854775808..-9223372036854775808 (foo=-9223372036854775808+[..0])]", 2); + testConvert("foo in [-9223372036854775808..9223372036854775807]", "foo in [-9223372036854775808..9223372036854775807 (foo=-9223372036854775808+[..0],foo=-9223372036854775807-0,foo=0-9223372036854775807)]", 2); + + testConvert("foo in [9223372036854775807..9223372036854775807]", "foo in [9223372036854775807..9223372036854775807 (foo=9223372036854775806+[1..1])]", 3); + testConvert("foo in [-9223372036854775808..-9223372036854775808]", "foo in [-9223372036854775808..-9223372036854775808 (foo=-9223372036854775806+[2..])]", 3); + testConvert("foo in [-9223372036854775808..-1]", + "foo in [-9223372036854775808..-1 (" + + "foo=-9223372036854775808-9223372036854775782," + + "foo=-9223372036854775700-9223372036854775620," + + "foo=-9223372036854775781-9223372036854775701," + + "foo=-9223372036854775376-9223372036854775134," + + "foo=-9223372036854775619-9223372036854775377," + + "foo=-9223372036854775133-9223372036854774405," + + "foo=-9223372036854774404-9223372036854767844," + + "foo=-9223372036854708794-9223372036854649746," + + "foo=-9223372036854767843-9223372036854708795," + + "foo=-9223372036854472598-9223372036854295452," + + "foo=-9223372036854649745-9223372036854472599," + + "foo=-9223372036854295451-9223372036853764011," + + "foo=-9223372036852169687-9223372036850575365," + + "foo=-9223372036853764010-9223372036852169688," + + "foo=-9223372036850575364-9223372036807528644," + + "foo=-9223372036420108154-9223372036032687666," + + "foo=-9223372036807528643-9223372036420108155," + + "foo=-9223372036032687665-9223372032545903265," + + "foo=-9223372022085550061-9223372011625196859," + + "foo=-9223372032545903264-9223372022085550062," + + "foo=-9223372011625196858-9223371980244137250," + + "foo=-9223371980244137249-9223371132955527807," + + "foo=-9223368591089699477-9223366049223871149," + + "foo=-9223371132955527806-9223368591089699478," + + "foo=-9223358423626386161-9223350798028901175," + + "foo=-9223366049223871148-9223358423626386162," + + "foo=-9223327921236446213-9223305044443991253," + + "foo=-9223350798028901174-9223327921236446214," + + "foo=-9223305044443991252-9223099153311896604," + + "foo=-9223099153311896603-9222481479915612657," + + "foo=-9222481479915612656-9205804298215946088," + + "foo=-9205804298215946087-9155772753116946381," + + "foo=-9155772753116946380-9005678117819947260," + + "foo=-8555394211928949896-8105110306037952534," + + "foo=-9005678117819947259-8555394211928949897," + + "foo=-4052555153018976266-0," + + "foo=-8105110306037952533-4052555153018976267)]", 3); + } + + @Test + public void requireThatHighAritiesWork() { + testConvert("foo in [10..39]", "foo in [10..39 (foo=0+[10..39])]", 1000); + testConvert("foo in [9000..11000]", "foo in [9000..11000 (foo=0+[9000..],foo=10000+[..1000])]", 10000); + testConvert("foo in [10..39]", "foo in [10..39 (foo=0+[10..39])]", 16384); + testConvert("foo in [10..32768]", "foo in [10..32768 (foo=0+[10..],foo=32768+[..0],foo=16384-32767)]", 16384); + + testConvert("foo in [9223372036854775807..9223372036854775807]", "foo in [9223372036854775807..9223372036854775807 (foo=9223372036854759424+[16383..])]", 16384); + testConvert("foo in [-9223372036854775808..-9223372036854775808]", "foo in [-9223372036854775808..-9223372036854775808 (foo=-9223372036854775808+[..0])]", 16384); + } + + @Test + public void requireThatOpenRangesWork() { + testConvert("foo in [-7..]", "foo in [-7.. (foo=-7-0,foo=0-9223372036854775807)]", 2); + testConvert("foo in [..7]", "foo in [..7 (foo=-9223372036854775808+[..0],foo=-9223372036854775807-0,foo=0-7)]", 2); + } + + @Test + public void requireThatUpperAndLowerBoundsWork() { + lowerBound = -999; + upperBound = 999; + testConvert("foo in [-9..]", "foo in [-9.. (foo=-9-0,foo=0-999)]", 10); + testConvert("foo in [..9]", "foo in [..9 (foo=-999-0,foo=0-9)]", 10); + testConvert("foo in [..]", "foo in [.. (foo=-999-0,foo=0-999)]", 10); + } + + @Test + public void requireThatUpperAndLowerBoundsPruneClosedRanges() { + lowerBound = -999; + upperBound = 999; + testConvert("foo in [0..10000]", "foo in [0..10000 (foo=0-999)]", 10); + lowerBound = 888; + testConvert("foo in [0..10000]", "foo in [0..10000 (foo=0-999)]", 10); + lowerBound = 900; + testConvert("foo in [0..10000]", "foo in [0..10000 (foo=0-999)]", 10); + } + + @Test + public void requireThatRangesOutsideBoundsAreSimplifiedToOneImpossibleRange() { + lowerBound = 900; + upperBound = 999; + testConvert("foo in [0..100]", "foo in [0..100 (foo=-9223372036854775799-9223372036854775790)]", 10); + testConvert("foo in [1000..1100]", "foo in [1000..1100 (foo=9223372036854775790-9223372036854775799)]", 10); + lowerBound = -999; + upperBound = -900; + testConvert("foo in [-2000..-1000]", "foo in [-2000..-1000 (foo=-9223372036854775799-9223372036854775790)]", 10); + testConvert("foo in [0..100]", "foo in [0..100 (foo=9223372036854775790-9223372036854775799)]", 10); + lowerBound = -9223372036854775790L; + upperBound = 9223372036854775790L; + testConvert("foo in [9223372036854775791..9223372036854775792]", "foo in [9223372036854775791..9223372036854775792 (foo=9223372036854775790+[1..1])]", 10); + testConvert("foo in [-9223372036854775792..-9223372036854775791]", "foo in [-9223372036854775792..-9223372036854775791 (foo=-9223372036854775790+[1..1])]", 10); + } + + @Test + public void requireThatUpperAndLowerBoundsAreAdjustedWithArity() { + lowerBound = -999; + upperBound = 999; + testConvert("foo in [0..10000]", "foo in [0..10000 (foo=0-999)]", 10); + testConvert("foo in [0..10000]", "foo in [0..10000 (foo=0-1023)]", 2); + testConvert("foo in [-10000..10000]", "foo in [-10000..10000 (foo=-999-0,foo=0-999)]", 10); + testConvert("foo in [-10000..10000]", "foo in [-10000..10000 (foo=-1023-0,foo=0-1023)]", 2); + + upperBound = 1000; + testConvert("foo in [0..10000]", "foo in [0..10000 (foo=0-9999)]", 10); + + lowerBound = 100; + upperBound = 999; + testConvert("foo in [0..10000]", "foo in [0..10000 (foo=0-999)]", 10); + testConvert("foo in [0..10000]", "foo in [0..10000 (foo=0-1023)]", 2); + + lowerBound = -999; + upperBound = -100; + testConvert("foo in [-10000..10000]", "foo in [-10000..10000 (foo=-999-0)]", 10); + testConvert("foo in [-10000..10000]", "foo in [-10000..10000 (foo=-1023-0)]", 2); + + lowerBound = -9223372036854775790L; + upperBound = 9223372036854775790L; + testConvert("foo in [-9223372036854775791..9223372036854775792]", + "foo in [-9223372036854775791..9223372036854775792 (" + + "foo=-9223372036854775790+[..0],foo=9223372036854775790+[..0]," + + "foo=-9223372036854775709-9223372036854775700," + + "foo=-9223372036854775719-9223372036854775710," + + "foo=-9223372036854775729-9223372036854775720," + + "foo=-9223372036854775739-9223372036854775730," + + "foo=-9223372036854775749-9223372036854775740," + + "foo=-9223372036854775759-9223372036854775750," + + "foo=-9223372036854775769-9223372036854775760," + + "foo=-9223372036854775779-9223372036854775770," + + "foo=-9223372036854775789-9223372036854775780," + + "foo=-9223372036854775099-9223372036854775000," + + "foo=-9223372036854775199-9223372036854775100," + + "foo=-9223372036854775299-9223372036854775200," + + "foo=-9223372036854775399-9223372036854775300," + + "foo=-9223372036854775499-9223372036854775400," + + "foo=-9223372036854775599-9223372036854775500," + + "foo=-9223372036854775699-9223372036854775600," + + "foo=-9223372036854770999-9223372036854770000," + + "foo=-9223372036854771999-9223372036854771000," + + "foo=-9223372036854772999-9223372036854772000," + + "foo=-9223372036854773999-9223372036854773000," + + "foo=-9223372036854774999-9223372036854774000," + + "foo=-9223372036854709999-9223372036854700000," + + "foo=-9223372036854719999-9223372036854710000," + + "foo=-9223372036854729999-9223372036854720000," + + "foo=-9223372036854739999-9223372036854730000," + + "foo=-9223372036854749999-9223372036854740000," + + "foo=-9223372036854759999-9223372036854750000," + + "foo=-9223372036854769999-9223372036854760000," + + "foo=-9223372036854099999-9223372036854000000," + + "foo=-9223372036854199999-9223372036854100000," + + "foo=-9223372036854299999-9223372036854200000," + + "foo=-9223372036854399999-9223372036854300000," + + "foo=-9223372036854499999-9223372036854400000," + + "foo=-9223372036854599999-9223372036854500000," + + "foo=-9223372036854699999-9223372036854600000," + + "foo=-9223372036850999999-9223372036850000000," + + "foo=-9223372036851999999-9223372036851000000," + + "foo=-9223372036852999999-9223372036852000000," + + "foo=-9223372036853999999-9223372036853000000," + + "foo=-9223372036809999999-9223372036800000000," + + "foo=-9223372036819999999-9223372036810000000," + + "foo=-9223372036829999999-9223372036820000000," + + "foo=-9223372036839999999-9223372036830000000," + + "foo=-9223372036849999999-9223372036840000000," + + "foo=-9223372036099999999-9223372036000000000," + + "foo=-9223372036199999999-9223372036100000000," + + "foo=-9223372036299999999-9223372036200000000," + + "foo=-9223372036399999999-9223372036300000000," + + "foo=-9223372036499999999-9223372036400000000," + + "foo=-9223372036599999999-9223372036500000000," + + "foo=-9223372036699999999-9223372036600000000," + + "foo=-9223372036799999999-9223372036700000000," + + "foo=-9223372030999999999-9223372030000000000," + + "foo=-9223372031999999999-9223372031000000000," + + "foo=-9223372032999999999-9223372032000000000," + + "foo=-9223372033999999999-9223372033000000000," + + "foo=-9223372034999999999-9223372034000000000," + + "foo=-9223372035999999999-9223372035000000000," + + "foo=-9223372009999999999-9223372000000000000," + + "foo=-9223372019999999999-9223372010000000000," + + "foo=-9223372029999999999-9223372020000000000," + + "foo=-9223370999999999999-9223370000000000000," + + "foo=-9223371999999999999-9223371000000000000," + + "foo=-9223309999999999999-9223300000000000000," + + "foo=-9223319999999999999-9223310000000000000," + + "foo=-9223329999999999999-9223320000000000000," + + "foo=-9223339999999999999-9223330000000000000," + + "foo=-9223349999999999999-9223340000000000000," + + "foo=-9223359999999999999-9223350000000000000," + + "foo=-9223369999999999999-9223360000000000000," + + "foo=-9223099999999999999-9223000000000000000," + + "foo=-9223199999999999999-9223100000000000000," + + "foo=-9223299999999999999-9223200000000000000," + + "foo=-9220999999999999999-9220000000000000000," + + "foo=-9221999999999999999-9221000000000000000," + + "foo=-9222999999999999999-9222000000000000000," + + "foo=-9209999999999999999-9200000000000000000," + + "foo=-9219999999999999999-9210000000000000000," + + "foo=-9099999999999999999-9000000000000000000," + + "foo=-9199999999999999999-9100000000000000000," + + "foo=-999999999999999999-0," + + "foo=-1999999999999999999-1000000000000000000," + + "foo=-2999999999999999999-2000000000000000000," + + "foo=-3999999999999999999-3000000000000000000," + + "foo=-4999999999999999999-4000000000000000000," + + "foo=-5999999999999999999-5000000000000000000," + + "foo=-6999999999999999999-6000000000000000000," + + "foo=-7999999999999999999-7000000000000000000," + + "foo=-8999999999999999999-8000000000000000000," + + "foo=9223372036854775700-9223372036854775709," + + "foo=9223372036854775710-9223372036854775719," + + "foo=9223372036854775720-9223372036854775729," + + "foo=9223372036854775730-9223372036854775739," + + "foo=9223372036854775740-9223372036854775749," + + "foo=9223372036854775750-9223372036854775759," + + "foo=9223372036854775760-9223372036854775769," + + "foo=9223372036854775770-9223372036854775779," + + "foo=9223372036854775780-9223372036854775789," + + "foo=9223372036854775000-9223372036854775099," + + "foo=9223372036854775100-9223372036854775199," + + "foo=9223372036854775200-9223372036854775299," + + "foo=9223372036854775300-9223372036854775399," + + "foo=9223372036854775400-9223372036854775499," + + "foo=9223372036854775500-9223372036854775599," + + "foo=9223372036854775600-9223372036854775699," + + "foo=9223372036854770000-9223372036854770999," + + "foo=9223372036854771000-9223372036854771999," + + "foo=9223372036854772000-9223372036854772999," + + "foo=9223372036854773000-9223372036854773999," + + "foo=9223372036854774000-9223372036854774999," + + "foo=9223372036854700000-9223372036854709999," + + "foo=9223372036854710000-9223372036854719999," + + "foo=9223372036854720000-9223372036854729999," + + "foo=9223372036854730000-9223372036854739999," + + "foo=9223372036854740000-9223372036854749999," + + "foo=9223372036854750000-9223372036854759999," + + "foo=9223372036854760000-9223372036854769999," + + "foo=9223372036854000000-9223372036854099999," + + "foo=9223372036854100000-9223372036854199999," + + "foo=9223372036854200000-9223372036854299999," + + "foo=9223372036854300000-9223372036854399999," + + "foo=9223372036854400000-9223372036854499999," + + "foo=9223372036854500000-9223372036854599999," + + "foo=9223372036854600000-9223372036854699999," + + "foo=9223372036850000000-9223372036850999999," + + "foo=9223372036851000000-9223372036851999999," + + "foo=9223372036852000000-9223372036852999999," + + "foo=9223372036853000000-9223372036853999999," + + "foo=9223372036800000000-9223372036809999999," + + "foo=9223372036810000000-9223372036819999999," + + "foo=9223372036820000000-9223372036829999999," + + "foo=9223372036830000000-9223372036839999999," + + "foo=9223372036840000000-9223372036849999999," + + "foo=9223372036000000000-9223372036099999999," + + "foo=9223372036100000000-9223372036199999999," + + "foo=9223372036200000000-9223372036299999999," + + "foo=9223372036300000000-9223372036399999999," + + "foo=9223372036400000000-9223372036499999999," + + "foo=9223372036500000000-9223372036599999999," + + "foo=9223372036600000000-9223372036699999999," + + "foo=9223372036700000000-9223372036799999999," + + "foo=9223372030000000000-9223372030999999999," + + "foo=9223372031000000000-9223372031999999999," + + "foo=9223372032000000000-9223372032999999999," + + "foo=9223372033000000000-9223372033999999999," + + "foo=9223372034000000000-9223372034999999999," + + "foo=9223372035000000000-9223372035999999999," + + "foo=9223372000000000000-9223372009999999999," + + "foo=9223372010000000000-9223372019999999999," + + "foo=9223372020000000000-9223372029999999999," + + "foo=9223370000000000000-9223370999999999999," + + "foo=9223371000000000000-9223371999999999999," + + "foo=9223300000000000000-9223309999999999999," + + "foo=9223310000000000000-9223319999999999999," + + "foo=9223320000000000000-9223329999999999999," + + "foo=9223330000000000000-9223339999999999999," + + "foo=9223340000000000000-9223349999999999999," + + "foo=9223350000000000000-9223359999999999999," + + "foo=9223360000000000000-9223369999999999999," + + "foo=9223000000000000000-9223099999999999999," + + "foo=9223100000000000000-9223199999999999999," + + "foo=9223200000000000000-9223299999999999999," + + "foo=9220000000000000000-9220999999999999999," + + "foo=9221000000000000000-9221999999999999999," + + "foo=9222000000000000000-9222999999999999999," + + "foo=9200000000000000000-9209999999999999999," + + "foo=9210000000000000000-9219999999999999999," + + "foo=9000000000000000000-9099999999999999999," + + "foo=9100000000000000000-9199999999999999999," + + "foo=0-999999999999999999," + + "foo=1000000000000000000-1999999999999999999," + + "foo=2000000000000000000-2999999999999999999," + + "foo=3000000000000000000-3999999999999999999," + + "foo=4000000000000000000-4999999999999999999," + + "foo=5000000000000000000-5999999999999999999," + + "foo=6000000000000000000-6999999999999999999," + + "foo=7000000000000000000-7999999999999999999," + + "foo=8000000000000000000-8999999999999999999)]"); + + lowerBound = -922337203685477579L; + upperBound = 922337203685477579L; + testConvert("foo in [-9223372036854775791..9223372036854775792]", + "foo in [-9223372036854775791..9223372036854775792 (foo=-999999999999999999-0,foo=0-999999999999999999)]"); + } + + @Test + public void requireThatExistingPartitionsAreCleared() { + testConvert("foo in [10..19]", "foo in [10..19 (foo=10-19)]"); + Predicate p = Predicate.fromString("foo in [10..19]"); + ((FeatureRange)p).addPartition(new RangePartition("foo", 10000L, 20000L, false)); + ComplexNodeTransformer tranformer = new ComplexNodeTransformer(); + Predicate converted = tranformer.process(p, new PredicateOptions(10, lowerBound, upperBound)); + assertEquals("foo in [10..19 (foo=10-19)]", converted.toString()); + + } +} diff --git a/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/NotNodeReordererTest.java b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/NotNodeReordererTest.java new file mode 100644 index 00000000000..de61c3e04c6 --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/NotNodeReordererTest.java @@ -0,0 +1,55 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import com.yahoo.document.predicate.Predicate; +import org.junit.Test; + +import static com.yahoo.document.predicate.Predicates.and; +import static com.yahoo.document.predicate.Predicates.feature; +import static com.yahoo.document.predicate.Predicates.or; +import static org.junit.Assert.assertEquals; + +/** + * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + */ +public class NotNodeReordererTest { + @Test + public void requireThatNotChildrenAreMovedAwayFromLastAndChild() { + checkReorder( + and(feature("a").inSet("b"), feature("c").notInSet("d")), + and(feature("c").notInSet("d"), feature("a").inSet("b"))); + + checkReorder( + and(feature("a").inSet("b"), feature("c").notInSet("d"), feature("e").notInSet("f")), + and(feature("c").notInSet("d"), feature("e").notInSet("f"), feature("a").inSet("b"))); + } + + @Test + public void requireThatNotChildrenAreMovedToLastOrChild() { + checkReorder( + or(feature("c").notInSet("d"), feature("a").inSet("b")), + or(feature("a").inSet("b"), feature("c").notInSet("d"))); + + checkReorder( + or(feature("c").notInSet("d"), feature("e").notInSet("f"), feature("a").inSet("b")), + or(feature("a").inSet("b"), feature("c").notInSet("d"), feature("e").notInSet("f"))); + } + + @Test + public void requireThatComplexReorderingWork() { + checkReorder(and(feature("g").inSet("h"), + or(and(feature("a").notInSet("b"), + feature("c").notInSet("d")), + feature("e").inSet("f"))), + and(or(feature("e").inSet("f"), + and(feature("a").notInSet("b"), + feature("c").notInSet("d"))), + feature("g").inSet("h"))); + } + + private static void checkReorder(Predicate input, Predicate expected) { + NotNodeReorderer reorderer = new NotNodeReorderer(); + Predicate actual = reorderer.process(input, new PredicateOptions(10)); + assertEquals(expected, actual); + } +} diff --git a/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/OrSimplifierTest.java b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/OrSimplifierTest.java new file mode 100644 index 00000000000..6db02c5be57 --- /dev/null +++ b/predicate-search-core/src/test/java/com/yahoo/search/predicate/optimization/OrSimplifierTest.java @@ -0,0 +1,98 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.search.predicate.optimization; + +import com.yahoo.document.predicate.Predicate; +import org.junit.Test; + +import static com.yahoo.document.predicate.Predicates.and; +import static com.yahoo.document.predicate.Predicates.feature; +import static com.yahoo.document.predicate.Predicates.not; +import static com.yahoo.document.predicate.Predicates.or; +import static org.junit.Assert.assertEquals; + +public class OrSimplifierTest { + + @Test + public void require_that_or_with_feature_sets_of_same_key_is_simplified_to_single_feature_set() { + Predicate p = + or( + feature("key1").inSet("value1", "value4"), + feature("key1").inSet("value2", "value3"), + feature("key1").inSet("value1", "value4")); + Predicate expected = feature("key1").inSet("value1", "value2", "value3", "value4"); + assertConvertedPredicateEquals(expected, p); + } + + @Test + public void require_that_or_with_feature_sets_of_different_keys_is_simplified() { + Predicate p = + or( + feature("key1").inSet("value1", "value3"), + feature("key1").inSet("value2"), + feature("key2").inSet("value1"), + feature("key2").inSet("value2", "value3")); + Predicate expected = + or( + feature("key1").inSet("value1", "value2", "value3"), + feature("key2").inSet("value1", "value2", "value3")); + assertConvertedPredicateEquals(expected, p); + } + + @Test + public void require_that_conversion_is_recursive_and_cascades() { + Predicate p = + or( + feature("key1").inSet("value1", "value4"), + feature("key1").inSet("value2", "value3"), + or( + feature("key1").inSet("value1"), + feature("key1").inSet("value4"))); + Predicate expected = feature("key1").inSet("value1", "value2", "value3", "value4"); + assertConvertedPredicateEquals(expected, p); + } + + @Test + public void require_that_or_below_and_is_converted() { + Predicate p = + and( + or( + feature("key1").inSet("value1"), + feature("key1").inSet("value2")), + feature("key2").inSet("value2")); + Predicate expected = + and( + feature("key1").inSet("value1", "value2"), + feature("key2").inSet("value2")); + assertConvertedPredicateEquals(expected, p); + } + + @Test + public void require_that_or_below_not_is_converted() { + Predicate p = + not( + or( + feature("key1").inSet("value1"), + feature("key1").inSet("value2"))); + Predicate expected = not(feature("key1").inSet("value1", "value2")); + assertConvertedPredicateEquals(expected, p); + } + + @Test + public void require_that_non_feature_set_nodes_are_left_untouched() { + Predicate p = + or( + feature("key1").inSet("value1"), + feature("key1").inSet("value2"), + not(feature("key1").inSet("value3"))); + Predicate expected = + or( + not(feature("key1").inSet("value3")), + feature("key1").inSet("value1", "value2")); + assertConvertedPredicateEquals(expected, p); + } + + private static void assertConvertedPredicateEquals(Predicate expected, Predicate predicate) { + OrSimplifier simplifier = new OrSimplifier(); + assertEquals(expected, simplifier.simplifyTree(predicate)); + } +} |