lucene-java-3.4.0/lucene/src/java/org/apache/lucene/search/BooleanQuery.java

   1 package org.apache.lucene.search;
   2
   3 /**
   4  * Licensed to the Apache Software Foundation (ASF) under one or more
   5  * contributor license agreements.  See the NOTICE file distributed with
   6  * this work for additional information regarding copyright ownership.
   7  * The ASF licenses this file to You under the Apache License, Version 2.0
   8  * (the "License"); you may not use this file except in compliance with
   9  * the License.  You may obtain a copy of the License at
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 import org.apache.lucene.index.IndexReader;
  21 import org.apache.lucene.index.Term;
  22 import org.apache.lucene.util.ToStringUtils;
  23 import org.apache.lucene.search.BooleanClause.Occur;
  24
  25 import java.io.IOException;
  26 import java.util.*;
  27
  28 /** A Query that matches documents matching boolean combinations of other
  29   * queries, e.g. {@link TermQuery}s, {@link PhraseQuery}s or other
  30   * BooleanQuerys.
  31   */
  32 public class BooleanQuery extends Query implements Iterable<BooleanClause> {
  33
  34   private static int maxClauseCount = 1024;
  35
  36   /** Thrown when an attempt is made to add more than {@link
  37    * #getMaxClauseCount()} clauses. This typically happens if
  38    * a PrefixQuery, FuzzyQuery, WildcardQuery, or TermRangeQuery
  39    * is expanded to many terms during search.
  40    */
  41   public static class TooManyClauses extends RuntimeException {
  42     public TooManyClauses() {
  43       super("maxClauseCount is set to " + maxClauseCount);
  44     }
  45   }
  46
  47   /** Return the maximum number of clauses permitted, 1024 by default.
  48    * Attempts to add more than the permitted number of clauses cause {@link
  49    * TooManyClauses} to be thrown.
  50    * @see #setMaxClauseCount(int)
  51    */
  52   public static int getMaxClauseCount() { return maxClauseCount; }
  53
  54   /**
  55    * Set the maximum number of clauses permitted per BooleanQuery.
  56    * Default value is 1024.
  57    */
  58   public static void setMaxClauseCount(int maxClauseCount) {
  59     if (maxClauseCount < 1)
  60       throw new IllegalArgumentException("maxClauseCount must be >= 1");
  61     BooleanQuery.maxClauseCount = maxClauseCount;
  62   }
  63
  64   private ArrayList<BooleanClause> clauses = new ArrayList<BooleanClause>();
  65   private final boolean disableCoord;
  66
  67   /** Constructs an empty boolean query. */
  68   public BooleanQuery() {
  69     disableCoord = false;
  70   }
  71
  72   /** Constructs an empty boolean query.
  73    *
  74    * {@link Similarity#coord(int,int)} may be disabled in scoring, as
  75    * appropriate. For example, this score factor does not make sense for most
  76    * automatically generated queries, like {@link WildcardQuery} and {@link
  77    * FuzzyQuery}.
  78    *
  79    * @param disableCoord disables {@link Similarity#coord(int,int)} in scoring.
  80    */
  81   public BooleanQuery(boolean disableCoord) {
  82     this.disableCoord = disableCoord;
  83   }
  84
  85   /** Returns true iff {@link Similarity#coord(int,int)} is disabled in
  86    * scoring for this query instance.
  87    * @see #BooleanQuery(boolean)
  88    */
  89   public boolean isCoordDisabled() { return disableCoord; }
  90
  91   /**
  92    * Specifies a minimum number of the optional BooleanClauses
  93    * which must be satisfied.
  94    *
  95    * <p>
  96    * By default no optional clauses are necessary for a match
  97    * (unless there are no required clauses).  If this method is used,
  98    * then the specified number of clauses is required.
  99    * </p>
 100    * <p>
 101    * Use of this method is totally independent of specifying that
 102    * any specific clauses are required (or prohibited).  This number will
 103    * only be compared against the number of matching optional clauses.
 104    * </p>
 105    *
 106    * @param min the number of optional clauses that must match
 107    */
 108   public void setMinimumNumberShouldMatch(int min) {
 109     this.minNrShouldMatch = min;
 110   }
 111   protected int minNrShouldMatch = 0;
 112
 113   /**
 114    * Gets the minimum number of the optional BooleanClauses
 115    * which must be satisfied.
 116    */
 117   public int getMinimumNumberShouldMatch() {
 118     return minNrShouldMatch;
 119   }
 120
 121   /** Adds a clause to a boolean query.
 122    *
 123    * @throws TooManyClauses if the new number of clauses exceeds the maximum clause number
 124    * @see #getMaxClauseCount()
 125    */
 126   public void add(Query query, BooleanClause.Occur occur) {
 127     add(new BooleanClause(query, occur));
 128   }
 129
 130   /** Adds a clause to a boolean query.
 131    * @throws TooManyClauses if the new number of clauses exceeds the maximum clause number
 132    * @see #getMaxClauseCount()
 133    */
 134   public void add(BooleanClause clause) {
 135     if (clauses.size() >= maxClauseCount)
 136       throw new TooManyClauses();
 137
 138     clauses.add(clause);
 139   }
 140
 141   /** Returns the set of clauses in this query. */
 142   public BooleanClause[] getClauses() {
 143     return clauses.toArray(new BooleanClause[clauses.size()]);
 144   }
 145
 146   /** Returns the list of clauses in this query. */
 147   public List<BooleanClause> clauses() { return clauses; }
 148
 149   /** Returns an iterator on the clauses in this query. It implements the {@link Iterable} interface to
 150    * make it possible to do:
 151    * <pre>for (BooleanClause clause : booleanQuery) {}</pre>
 152    */
 153   public final Iterator<BooleanClause> iterator() { return clauses().iterator(); }
 154
 155   /**
 156    * Expert: the Weight for BooleanQuery, used to
 157    * normalize, score and explain these queries.
 158    *
 159    * <p>NOTE: this API and implementation is subject to
 160    * change suddenly in the next release.</p>
 161    */
 162   protected class BooleanWeight extends Weight {
 163     /** The Similarity implementation. */
 164     protected Similarity similarity;
 165     protected ArrayList<Weight> weights;
 166     protected int maxCoord;  // num optional + num required
 167     private final boolean disableCoord;
 168
 169     public BooleanWeight(Searcher searcher, boolean disableCoord)
 170       throws IOException {
 171       this.similarity = getSimilarity(searcher);
 172       this.disableCoord = disableCoord;
 173       weights = new ArrayList<Weight>(clauses.size());
 174       for (int i = 0 ; i < clauses.size(); i++) {
 175         BooleanClause c = clauses.get(i);
 176         weights.add(c.getQuery().createWeight(searcher));
 177         if (!c.isProhibited()) maxCoord++;
 178       }
 179     }
 180
 181     @Override
 182     public Query getQuery() { return BooleanQuery.this; }
 183
 184     @Override
 185     public float getValue() { return getBoost(); }
 186
 187     @Override
 188     public float sumOfSquaredWeights() throws IOException {
 189       float sum = 0.0f;
 190       for (int i = 0 ; i < weights.size(); i++) {
 191         // call sumOfSquaredWeights for all clauses in case of side effects
 192         float s = weights.get(i).sumOfSquaredWeights();         // sum sub weights
 193         if (!clauses.get(i).isProhibited())
 194           // only add to sum for non-prohibited clauses
 195           sum += s;
 196       }
 197
 198       sum *= getBoost() * getBoost();             // boost each sub-weight
 199
 200       return sum ;
 201     }
 202
 203
 204     @Override
 205     public void normalize(float norm) {
 206       norm *= getBoost();                         // incorporate boost
 207       for (Weight w : weights) {
 208         // normalize all clauses, (even if prohibited in case of side affects)
 209         w.normalize(norm);
 210       }
 211     }
 212
 213     @Override
 214     public Explanation explain(IndexReader reader, int doc)
 215       throws IOException {
 216       final int minShouldMatch =
 217         BooleanQuery.this.getMinimumNumberShouldMatch();
 218       ComplexExplanation sumExpl = new ComplexExplanation();
 219       sumExpl.setDescription("sum of:");
 220       int coord = 0;
 221       float sum = 0.0f;
 222       boolean fail = false;
 223       int shouldMatchCount = 0;
 224       Iterator<BooleanClause> cIter = clauses.iterator();
 225       for (Iterator<Weight> wIter = weights.iterator(); wIter.hasNext();) {
 226         Weight w = wIter.next();
 227         BooleanClause c = cIter.next();
 228         if (w.scorer(reader, true, true) == null) {
 229           if (c.isRequired()) {
 230             fail = true;
 231             Explanation r = new Explanation(0.0f, "no match on required clause (" + c.getQuery().toString() + ")");
 232             sumExpl.addDetail(r);
 233           }
 234           continue;
 235         }
 236         Explanation e = w.explain(reader, doc);
 237         if (e.isMatch()) {
 238           if (!c.isProhibited()) {
 239             sumExpl.addDetail(e);
 240             sum += e.getValue();
 241             coord++;
 242           } else {
 243             Explanation r =
 244               new Explanation(0.0f, "match on prohibited clause (" + c.getQuery().toString() + ")");
 245             r.addDetail(e);
 246             sumExpl.addDetail(r);
 247             fail = true;
 248           }
 249           if (c.getOccur() == Occur.SHOULD)
 250             shouldMatchCount++;
 251         } else if (c.isRequired()) {
 252           Explanation r = new Explanation(0.0f, "no match on required clause (" + c.getQuery().toString() + ")");
 253           r.addDetail(e);
 254           sumExpl.addDetail(r);
 255           fail = true;
 256         }
 257       }
 258       if (fail) {
 259         sumExpl.setMatch(Boolean.FALSE);
 260         sumExpl.setValue(0.0f);
 261         sumExpl.setDescription
 262           ("Failure to meet condition(s) of required/prohibited clause(s)");
 263         return sumExpl;
 264       } else if (shouldMatchCount < minShouldMatch) {
 265         sumExpl.setMatch(Boolean.FALSE);
 266         sumExpl.setValue(0.0f);
 267         sumExpl.setDescription("Failure to match minimum number "+
 268                                "of optional clauses: " + minShouldMatch);
 269         return sumExpl;
 270       }
 271
 272       sumExpl.setMatch(0 < coord ? Boolean.TRUE : Boolean.FALSE);
 273       sumExpl.setValue(sum);
 274
 275       final float coordFactor = disableCoord ? 1.0f : similarity.coord(coord, maxCoord);
 276       if (coordFactor == 1.0f) {
 277         return sumExpl;                             // eliminate wrapper
 278       } else {
 279         ComplexExplanation result = new ComplexExplanation(sumExpl.isMatch(),
 280                                                            sum*coordFactor,
 281                                                            "product of:");
 282         result.addDetail(sumExpl);
 283         result.addDetail(new Explanation(coordFactor,
 284                                          "coord("+coord+"/"+maxCoord+")"));
 285         return result;
 286       }
 287     }
 288
 289     @Override
 290     public Scorer scorer(IndexReader reader, boolean scoreDocsInOrder, boolean topScorer)
 291         throws IOException {
 292       List<Scorer> required = new ArrayList<Scorer>();
 293       List<Scorer> prohibited = new ArrayList<Scorer>();
 294       List<Scorer> optional = new ArrayList<Scorer>();
 295       Iterator<BooleanClause> cIter = clauses.iterator();
 296       for (Weight w  : weights) {
 297         BooleanClause c =  cIter.next();
 298         Scorer subScorer = w.scorer(reader, true, false);
 299         if (subScorer == null) {
 300           if (c.isRequired()) {
 301             return null;
 302           }
 303         } else if (c.isRequired()) {
 304           required.add(subScorer);
 305         } else if (c.isProhibited()) {
 306           prohibited.add(subScorer);
 307         } else {
 308           optional.add(subScorer);
 309         }
 310       }
 311
 312       // Check if we can return a BooleanScorer
 313       if (!scoreDocsInOrder && topScorer && required.size() == 0 && prohibited.size() < 32) {
 314         return new BooleanScorer(this, disableCoord, similarity, minNrShouldMatch, optional, prohibited, maxCoord);
 315       }
 316
 317       if (required.size() == 0 && optional.size() == 0) {
 318         // no required and optional clauses.
 319         return null;
 320       } else if (optional.size() < minNrShouldMatch) {
 321         // either >1 req scorer, or there are 0 req scorers and at least 1
 322         // optional scorer. Therefore if there are not enough optional scorers
 323         // no documents will be matched by the query
 324         return null;
 325       }
 326
 327       // Return a BooleanScorer2
 328       return new BooleanScorer2(this, disableCoord, similarity, minNrShouldMatch, required, prohibited, optional, maxCoord);
 329     }
 330
 331     @Override
 332     public boolean scoresDocsOutOfOrder() {
 333       int numProhibited = 0;
 334       for (BooleanClause c : clauses) {
 335         if (c.isRequired()) {
 336           return false; // BS2 (in-order) will be used by scorer()
 337         } else if (c.isProhibited()) {
 338           ++numProhibited;
 339         }
 340       }
 341
 342       if (numProhibited > 32) { // cannot use BS
 343         return false;
 344       }
 345
 346       // scorer() will return an out-of-order scorer if requested.
 347       return true;
 348     }
 349
 350   }
 351
 352   @Override
 353   public Weight createWeight(Searcher searcher) throws IOException {
 354     return new BooleanWeight(searcher, disableCoord);
 355   }
 356
 357   @Override
 358   public Query rewrite(IndexReader reader) throws IOException {
 359     if (minNrShouldMatch == 0 && clauses.size() == 1) {                    // optimize 1-clause queries
 360       BooleanClause c = clauses.get(0);
 361       if (!c.isProhibited()) {                    // just return clause
 362
 363         Query query = c.getQuery().rewrite(reader);    // rewrite first
 364
 365         if (getBoost() != 1.0f) {                 // incorporate boost
 366           if (query == c.getQuery())                   // if rewrite was no-op
 367             query = (Query)query.clone();         // then clone before boost
 368           query.setBoost(getBoost() * query.getBoost());
 369         }
 370
 371         return query;
 372       }
 373     }
 374
 375     BooleanQuery clone = null;                    // recursively rewrite
 376     for (int i = 0 ; i < clauses.size(); i++) {
 377       BooleanClause c = clauses.get(i);
 378       Query query = c.getQuery().rewrite(reader);
 379       if (query != c.getQuery()) {                     // clause rewrote: must clone
 380         if (clone == null)
 381           clone = (BooleanQuery)this.clone();
 382         clone.clauses.set(i, new BooleanClause(query, c.getOccur()));
 383       }
 384     }
 385     if (clone != null) {
 386       return clone;                               // some clauses rewrote
 387     } else
 388       return this;                                // no clauses rewrote
 389   }
 390
 391   // inherit javadoc
 392   @Override
 393   public void extractTerms(Set<Term> terms) {
 394       for (BooleanClause clause : clauses) {
 395           clause.getQuery().extractTerms(terms);
 396         }
 397   }
 398
 399   @Override @SuppressWarnings("unchecked")
 400   public Object clone() {
 401     BooleanQuery clone = (BooleanQuery)super.clone();
 402     clone.clauses = (ArrayList<BooleanClause>) this.clauses.clone();
 403     return clone;
 404   }
 405
 406   /** Prints a user-readable version of this query. */
 407   @Override
 408   public String toString(String field) {
 409     StringBuilder buffer = new StringBuilder();
 410     boolean needParens=(getBoost() != 1.0) || (getMinimumNumberShouldMatch()>0) ;
 411     if (needParens) {
 412       buffer.append("(");
 413     }
 414
 415     for (int i = 0 ; i < clauses.size(); i++) {
 416       BooleanClause c = clauses.get(i);
 417       if (c.isProhibited())
 418         buffer.append("-");
 419       else if (c.isRequired())
 420         buffer.append("+");
 421
 422       Query subQuery = c.getQuery();
 423       if (subQuery != null) {
 424         if (subQuery instanceof BooleanQuery) {   // wrap sub-bools in parens
 425           buffer.append("(");
 426           buffer.append(subQuery.toString(field));
 427           buffer.append(")");
 428         } else {
 429           buffer.append(subQuery.toString(field));
 430         }
 431       } else {
 432         buffer.append("null");
 433       }
 434
 435       if (i != clauses.size()-1)
 436         buffer.append(" ");
 437     }
 438
 439     if (needParens) {
 440       buffer.append(")");
 441     }
 442
 443     if (getMinimumNumberShouldMatch()>0) {
 444       buffer.append('~');
 445       buffer.append(getMinimumNumberShouldMatch());
 446     }
 447
 448     if (getBoost() != 1.0f)
 449     {
 450       buffer.append(ToStringUtils.boost(getBoost()));
 451     }
 452
 453     return buffer.toString();
 454   }
 455
 456   /** Returns true iff <code>o</code> is equal to this. */
 457   @Override
 458   public boolean equals(Object o) {
 459     if (!(o instanceof BooleanQuery))
 460       return false;
 461     BooleanQuery other = (BooleanQuery)o;
 462     return (this.getBoost() == other.getBoost())
 463         && this.clauses.equals(other.clauses)
 464         && this.getMinimumNumberShouldMatch() == other.getMinimumNumberShouldMatch()
 465         && this.disableCoord == other.disableCoord;
 466   }
 467
 468   /** Returns a hash code value for this object.*/
 469   @Override
 470   public int hashCode() {
 471     return Float.floatToIntBits(getBoost()) ^ clauses.hashCode()
 472       + getMinimumNumberShouldMatch() + (disableCoord ? 17:0);
 473   }
 474
 475 }