LCOV - code coverage report
Current view: top level - api - queryinternal.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core c2b6f1024d3a Lines: 1022 1146 89.2 %
Date: 2019-05-16 09:13:18 Functions: 156 169 92.3 %
Branches: 870 1718 50.6 %

           Branch data     Line data    Source code
       1                 :            : /** @file queryinternal.cc
       2                 :            :  * @brief Xapian::Query internals
       3                 :            :  */
       4                 :            : /* Copyright (C) 2007,2008,2009,2010,2011,2012,2013,2014,2015,2016,2017,2018,2019 Olly Betts
       5                 :            :  * Copyright (C) 2008,2009 Lemur Consulting Ltd
       6                 :            :  *
       7                 :            :  * This program is free software; you can redistribute it and/or
       8                 :            :  * modify it under the terms of the GNU General Public License as
       9                 :            :  * published by the Free Software Foundation; either version 2 of the
      10                 :            :  * License, or (at your option) any later version.
      11                 :            :  *
      12                 :            :  * This program is distributed in the hope that it will be useful,
      13                 :            :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      14                 :            :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      15                 :            :  * GNU General Public License for more details.
      16                 :            :  *
      17                 :            :  * You should have received a copy of the GNU General Public License
      18                 :            :  * along with this program; if not, write to the Free Software
      19                 :            :  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
      20                 :            :  */
      21                 :            : 
      22                 :            : #include <config.h>
      23                 :            : 
      24                 :            : #include "queryinternal.h"
      25                 :            : 
      26                 :            : #include "xapian/error.h"
      27                 :            : #include "xapian/postingsource.h"
      28                 :            : #include "xapian/query.h"
      29                 :            : #include "xapian/unicode.h"
      30                 :            : 
      31                 :            : #include "api/editdistance.h"
      32                 :            : #include "heap.h"
      33                 :            : #include "leafpostlist.h"
      34                 :            : #include "matcher/andmaybepostlist.h"
      35                 :            : #include "matcher/andnotpostlist.h"
      36                 :            : #include "matcher/boolorpostlist.h"
      37                 :            : #include "matcher/exactphrasepostlist.h"
      38                 :            : #include "matcher/externalpostlist.h"
      39                 :            : #include "matcher/maxpostlist.h"
      40                 :            : #include "matcher/multiandpostlist.h"
      41                 :            : #include "matcher/multixorpostlist.h"
      42                 :            : #include "matcher/nearpostlist.h"
      43                 :            : #include "matcher/orpospostlist.h"
      44                 :            : #include "matcher/orpostlist.h"
      45                 :            : #include "matcher/phrasepostlist.h"
      46                 :            : #include "matcher/queryoptimiser.h"
      47                 :            : #include "matcher/valuerangepostlist.h"
      48                 :            : #include "matcher/valuegepostlist.h"
      49                 :            : #include "net/length.h"
      50                 :            : #include "serialise-double.h"
      51                 :            : #include "stringutils.h"
      52                 :            : #include "termlist.h"
      53                 :            : 
      54                 :            : #include "debuglog.h"
      55                 :            : #include "omassert.h"
      56                 :            : #include "str.h"
      57                 :            : #include "stringutils.h"
      58                 :            : #include "unicode/description_append.h"
      59                 :            : 
      60                 :            : #include <algorithm>
      61                 :            : #include <functional>
      62                 :            : #include <list>
      63                 :            : #include <memory>
      64                 :            : #include <string>
      65                 :            : #include <unordered_set>
      66                 :            : #include <vector>
      67                 :            : 
      68                 :            : using namespace std;
      69                 :            : 
      70                 :            : static constexpr unsigned MAX_UTF_8_CHARACTER_LENGTH = 4;
      71                 :            : 
      72                 :            : template<class CLASS> struct delete_ptr {
      73                 :            :     void operator()(CLASS *p) const { delete p; }
      74                 :            : };
      75                 :            : 
      76                 :            : using Xapian::Internal::AndContext;
      77                 :            : using Xapian::Internal::OrContext;
      78                 :            : using Xapian::Internal::BoolOrContext;
      79                 :            : using Xapian::Internal::XorContext;
      80                 :            : 
      81                 :            : namespace Xapian {
      82                 :            : 
      83                 :            : namespace Internal {
      84                 :            : 
      85                 :            : struct PostListAndTermFreq {
      86                 :            :     PostList* pl;
      87                 :            :     Xapian::doccount tf = 0;
      88                 :            : 
      89                 :          0 :     PostListAndTermFreq() : pl(nullptr) {}
      90                 :            : 
      91                 :            :     explicit
      92                 :     285384 :     PostListAndTermFreq(PostList* pl_) : pl(pl_) {}
      93                 :            : };
      94                 :            : 
      95                 :            : /** Class providing an operator which sorts postlists to select max or terms.
      96                 :            :  *  This returns true if a has a (strictly) greater termweight than b.
      97                 :            :  *
      98                 :            :  *  Using this comparator will tend to result in multiple calls to
      99                 :            :  *  recalc_maxweight() for each of the subqueries (we use it with nth_element
     100                 :            :  *  which should be O(n)) - perhaps it'd be better to call recalc_maxweight()
     101                 :            :  *  once and then sort on that.
     102                 :            :  */
     103                 :            : struct CmpMaxOrTerms {
     104                 :            :     /** Return true if and only if a has a strictly greater termweight than b. */
     105                 :      11528 :     bool operator()(const PostListAndTermFreq& elt_a,
     106                 :            :                     const PostListAndTermFreq& elt_b) {
     107                 :      11528 :         PostList* a = elt_a.pl;
     108                 :      11528 :         PostList* b = elt_b.pl;
     109                 :            : #if (defined(__i386__) && !defined(__SSE_MATH__)) || \
     110                 :            :     defined(__mc68000__) || defined(__mc68010__) || \
     111                 :            :     defined(__mc68020__) || defined(__mc68030__)
     112                 :            :         // On some architectures, most common of which is x86, floating point
     113                 :            :         // values are calculated and stored in registers with excess precision.
     114                 :            :         // If the two recalc_maxweight() calls below return identical values in a
     115                 :            :         // register, the excess precision may be dropped for one of them but
     116                 :            :         // not the other (e.g. because the compiler saves the first calculated
     117                 :            :         // weight to memory while calculating the second, then reloads it to
     118                 :            :         // compare).  This leads to both a > b and b > a being true, which
     119                 :            :         // violates the antisymmetry property of the strict weak ordering
     120                 :            :         // required by nth_element().  This can have serious consequences (e.g.
     121                 :            :         // segfaults).
     122                 :            :         //
     123                 :            :         // Note that m68k only has excess precision in earlier models - 68040
     124                 :            :         // and later are OK:
     125                 :            :         // https://gcc.gnu.org/ml/gcc-patches/2008-11/msg00105.html
     126                 :            :         //
     127                 :            :         // To avoid this, we store each result in a volatile double prior to
     128                 :            :         // comparing them.  This means that the result of this test should
     129                 :            :         // match that on other architectures with the same double format (which
     130                 :            :         // is desirable), and actually has less overhead than rounding both
     131                 :            :         // results to float (which is another approach which works).
     132                 :            :         volatile double a_max_wt = a->recalc_maxweight();
     133                 :            :         volatile double b_max_wt = b->recalc_maxweight();
     134                 :            :         return a_max_wt > b_max_wt;
     135                 :            : #else
     136                 :      11528 :         return a->recalc_maxweight() > b->recalc_maxweight();
     137                 :            : #endif
     138                 :            :     }
     139                 :            : };
     140                 :            : 
     141                 :            : /// Comparison functor which orders by descending termfreq.
     142                 :            : struct ComparePostListTermFreqAscending {
     143                 :            :     /// Order PostListAndTermFreq by descending tf.
     144                 :     161340 :     bool operator()(const PostListAndTermFreq& a,
     145                 :            :                     const PostListAndTermFreq& b) const {
     146                 :     161340 :         return a.tf > b.tf;
     147                 :            :     }
     148                 :            : 
     149                 :            :     /// Order PostList* by descending get_termfreq_est().
     150                 :        648 :     bool operator()(const PostList* a,
     151                 :            :                     const PostList* b) const {
     152                 :        648 :         return a->get_termfreq_est() > b->get_termfreq_est();
     153                 :            :     }
     154                 :            : };
     155                 :            : 
     156                 :            : template<typename T>
     157                 :            : class Context {
     158                 :            :     /** Helper for initialisation when T = PostList*.
     159                 :            :      *
     160                 :            :      *  No initialisation is needed for this case.
     161                 :            :      */
     162                 :         30 :     void init_tf_(vector<PostList*>&) { }
     163                 :            : 
     164                 :            :     /** Helper for initialisation when T = PostListAndTermFreq. */
     165                 :     140217 :     void init_tf_(vector<PostListAndTermFreq>&) {
     166 [ +  - ][ -  + ]:     280434 :         if (pls.empty() || pls.front().tf != 0) return;
                 [ -  + ]
     167         [ +  + ]:     423137 :         for (auto&& elt : pls) {
     168         [ +  - ]:     282920 :             elt.tf = elt.pl->get_termfreq_est();
     169                 :            :         }
     170                 :            :     }
     171                 :            : 
     172                 :            :   protected:
     173                 :            :     QueryOptimiser* qopt;
     174                 :            : 
     175                 :            :     vector<T> pls;
     176                 :            : 
     177                 :            :     /** Helper for initialisation.
     178                 :            :      *
     179                 :            :      *  Use with BoolOrContext and OrContext.
     180                 :            :      */
     181                 :     280494 :     void init_tf() { init_tf_(pls); }
     182                 :            : 
     183                 :            :     /** Helper for dereferencing when T = PostList*. */
     184                 :        948 :     PostList* as_postlist(PostList* pl) { return pl; }
     185                 :            : 
     186                 :            :     /** Helper for dereferencing when T = PostListAndTermFreq. */
     187                 :       4480 :     PostList* as_postlist(const PostListAndTermFreq& x) { return x.pl; }
     188                 :            : 
     189                 :            :   public:
     190                 :     285418 :     Context(QueryOptimiser* qopt_, size_t reserve) : qopt(qopt_) {
     191   [ +  -  +  - ]:     142709 :         pls.reserve(reserve);
     192                 :     142709 :     }
     193                 :            : 
     194                 :     142709 :     ~Context() {
     195                 :     142709 :         shrink(0);
     196                 :     142709 :     }
     197                 :            : 
     198                 :     288290 :     void add_postlist(PostList * pl) {
     199 [ +  + ][ +  + ]:     288290 :         if (pl)
     200                 :     288267 :             pls.emplace_back(pl);
     201                 :     288290 :     }
     202                 :            : 
     203                 :        316 :     bool empty() const {
     204                 :        316 :         return pls.empty();
     205                 :            :     }
     206                 :            : 
     207                 :     281196 :     size_t size() const {
     208                 :     281196 :         return pls.size();
     209                 :            :     }
     210                 :            : 
     211                 :     142963 :     void shrink(size_t new_size) {
     212                 :            :         AssertRel(new_size, <=, pls.size());
     213 [ +  + ][ +  + ]:     142963 :         if (new_size >= pls.size())
     214                 :     142669 :             return;
     215                 :            : 
     216                 :        294 :         const PostList * hint_pl = qopt->get_hint_postlist();
     217 [ +  + ][ +  + ]:       3008 :         for (auto&& i = pls.begin() + new_size; i != pls.end(); ++i) {
     218                 :       2714 :             const PostList * pl = as_postlist(*i);
     219 [ +  + ][ +  - ]:       2714 :             if (rare(pl == hint_pl && hint_pl)) {
           [ +  +  +  + ]
         [ +  - ][ +  + ]
     220                 :            :                 // We were about to delete qopt's hint - instead tell qopt to
     221                 :            :                 // take ownership.
     222                 :        168 :                 qopt->take_hint_ownership();
     223                 :        168 :                 hint_pl = NULL;
     224                 :            :             } else {
     225 [ +  - ][ +  - ]:       2546 :                 delete pl;
     226                 :            :             }
     227                 :            :         }
     228                 :        294 :         pls.resize(new_size);
     229                 :            :     }
     230                 :            : 
     231                 :            :     /** Expand a wildcard query.
     232                 :            :      *
     233                 :            :      *  Used with BoolOrContext and OrContext.
     234                 :            :      */
     235                 :            :     void expand_wildcard(const QueryWildcard* query, double factor);
     236                 :            : 
     237                 :            :     /** Expand an edit distance query.
     238                 :            :      *
     239                 :            :      *  Used with BoolOrContext and OrContext.
     240                 :            :      */
     241                 :            :     void expand_edit_distance(const QueryEditDistance* query, double factor);
     242                 :            : };
     243                 :            : 
     244                 :            : template<typename T>
     245                 :            : inline void
     246                 :        235 : Context<T>::expand_wildcard(const QueryWildcard* query,
     247                 :            :                             double factor)
     248                 :            : {
     249 [ #  # ][ #  # ]:        235 :     unique_ptr<TermList> t(qopt->db.open_allterms(query->get_fixed_prefix()));
         [ +  - ][ +  - ]
     250 [ #  # ][ +  - ]:        235 :     bool skip_ucase = query->get_fixed_prefix().empty();
     251                 :        235 :     auto max_type = query->get_max_type();
     252                 :        235 :     Xapian::termcount expansions_left = query->get_max_expansion();
     253                 :            :     // If there's no expansion limit, set expansions_left to the maximum
     254                 :            :     // value Xapian::termcount can hold.
     255   [ #  #  +  + ]:        235 :     if (expansions_left == 0)
     256                 :        126 :         --expansions_left;
     257                 :        924 :     while (true) {
     258 [ #  # ][ +  - ]:       1128 :         t->next();
     259                 :            : done_skip_to:
     260 [ #  # ][ #  # ]:       1132 :         if (t->at_end())
         [ +  - ][ +  + ]
     261                 :        198 :             break;
     262                 :            : 
     263 [ #  # ][ +  - ]:        934 :         const string & term = t->get_termname();
     264 [ #  # ][ #  # ]:        934 :         if (skip_ucase && term[0] >= 'A') {
         [ #  # ][ +  + ]
         [ +  - ][ +  + ]
     265                 :            :             // If there's a leading wildcard then skip terms that start
     266                 :            :             // with A-Z, as we don't want the expansion to include prefixed
     267                 :            :             // terms.
     268                 :            :             //
     269                 :            :             // This assumes things about the structure of terms which the
     270                 :            :             // Query class otherwise doesn't need to care about, but it
     271                 :            :             // seems hard to avoid here.
     272                 :         16 :             skip_ucase = false;
     273 [ #  # ][ +  + ]:         16 :             if (term[0] <= 'Z') {
     274                 :            :                 static_assert('Z' + 1 == '[', "'Z' + 1 == '['");
     275 [ #  # ][ #  # ]:          4 :                 t->skip_to("[");
         [ +  - ][ +  - ]
     276                 :          4 :                 goto done_skip_to;
     277                 :            :             }
     278                 :            :         }
     279                 :            : 
     280 [ #  # ][ #  # ]:        930 :         if (!query->test_prefix_known(term)) continue;
         [ +  - ][ +  + ]
     281                 :            : 
     282 [ #  # ][ +  + ]:        862 :         if (max_type < Xapian::Query::WILDCARD_LIMIT_MOST_FREQUENT) {
     283 [ #  # ][ +  + ]:        610 :             if (expansions_left-- == 0) {
     284 [ #  # ][ +  + ]:         37 :                 if (max_type == Xapian::Query::WILDCARD_LIMIT_FIRST)
     285                 :          6 :                     break;
     286 [ #  # ][ +  - ]:         31 :                 string msg("Wildcard ");
     287 [ #  # ][ #  # ]:         31 :                 msg += query->get_pattern();
         [ +  - ][ +  - ]
     288   [ #  #  +  - ]:         31 :                 if (query->get_just_flags() == 0)
     289 [ #  # ][ +  - ]:         31 :                     msg += '*';
     290 [ #  # ][ +  - ]:         31 :                 msg += " expands to more than ";
     291 [ #  # ][ #  # ]:         31 :                 msg += str(query->get_max_expansion());
         [ +  - ][ +  - ]
     292   [ #  #  +  - ]:         31 :                 msg += " terms";
     293 [ #  # ][ #  # ]:        610 :                 throw Xapian::WildcardError(msg);
         [ +  - ][ +  - ]
     294                 :            :             }
     295                 :            :         }
     296                 :            : 
     297 [ #  # ][ #  # ]:        903 :         add_postlist(qopt->open_lazy_post_list(term, 1, factor));
           [ #  #  #  # ]
         [ +  - ][ +  - ]
           [ +  +  +  + ]
     298                 :            :     }
     299                 :            : 
     300 [ #  # ][ +  + ]:        204 :     if (max_type == Xapian::Query::WILDCARD_LIMIT_MOST_FREQUENT) {
     301                 :            :         // FIXME: open_lazy_post_list() results in the term getting registered
     302                 :            :         // for stats, so we still incur an avoidable cost from the full
     303                 :            :         // expansion size of the wildcard, which is most likely to be visible
     304                 :            :         // with the remote backend.  Perhaps we should split creating the lazy
     305                 :            :         // postlist from registering the term for stats.
     306                 :         24 :         auto set_size = query->get_max_expansion();
     307   [ #  #  +  - ]:         24 :         if (size() > set_size) {
     308 [ #  # ][ +  - ]:         24 :             init_tf();
     309                 :         24 :             auto begin = pls.begin();
     310   [ #  #  +  - ]:         24 :             nth_element(begin, begin + set_size - 1, pls.end(),
     311                 :         24 :                         ComparePostListTermFreqAscending());
     312 [ #  # ][ +  - ]:         24 :             shrink(set_size);
     313                 :            :         }
     314                 :        235 :     }
     315                 :        204 : }
     316                 :            : 
     317                 :            : template<typename T>
     318                 :            : inline void
     319                 :        133 : Context<T>::expand_edit_distance(const QueryEditDistance* query,
     320                 :            :                                  double factor)
     321                 :            : {
     322 [ #  # ][ #  # ]:        133 :     string pfx(query->get_pattern(), 0, query->get_fixed_prefix_len());
         [ +  - ][ +  - ]
     323 [ #  # ][ +  - ]:        266 :     unique_ptr<TermList> t(qopt->db.open_allterms(pfx));
     324                 :        133 :     bool skip_ucase = pfx.empty();
     325                 :        133 :     auto max_type = query->get_max_type();
     326                 :        133 :     Xapian::termcount expansions_left = query->get_max_expansion();
     327                 :            :     // If there's no expansion limit, set expansions_left to the maximum
     328                 :            :     // value Xapian::termcount can hold.
     329   [ #  #  +  + ]:        133 :     if (expansions_left == 0)
     330                 :         52 :         --expansions_left;
     331                 :       4153 :     while (true) {
     332 [ #  # ][ +  - ]:       4265 :         t->next();
     333                 :            : done_skip_to:
     334 [ #  # ][ #  # ]:       4271 :         if (t->at_end())
         [ +  - ][ +  + ]
     335                 :        106 :             break;
     336                 :            : 
     337 [ #  # ][ +  - ]:       4165 :         const string& term = t->get_termname();
     338 [ #  # ][ -  + ]:       4165 :         if (!startswith(term, pfx))
     339                 :          0 :             break;
     340 [ #  # ][ #  # ]:       4165 :         if (skip_ucase && term[0] >= 'A') {
         [ #  # ][ +  + ]
         [ +  - ][ +  + ]
     341                 :            :             // Skip terms that start with A-Z, as we don't want the expansion
     342                 :            :             // to include prefixed terms.
     343                 :            :             //
     344                 :            :             // This assumes things about the structure of terms which the
     345                 :            :             // Query class otherwise doesn't need to care about, but it
     346                 :            :             // seems hard to avoid here.
     347                 :        114 :             skip_ucase = false;
     348 [ #  # ][ +  + ]:        114 :             if (term[0] <= 'Z') {
     349                 :            :                 static_assert('Z' + 1 == '[', "'Z' + 1 == '['");
     350 [ #  # ][ #  # ]:          6 :                 t->skip_to("[");
         [ +  - ][ +  - ]
     351                 :          6 :                 goto done_skip_to;
     352                 :            :             }
     353                 :            :         }
     354                 :            : 
     355 [ #  # ][ #  # ]:       4159 :         if (!query->test(term)) continue;
         [ +  - ][ +  + ]
     356                 :            : 
     357 [ #  # ][ +  + ]:        426 :         if (max_type < Xapian::Query::WILDCARD_LIMIT_MOST_FREQUENT) {
     358 [ #  # ][ +  + ]:        408 :             if (expansions_left-- == 0) {
     359 [ #  # ][ +  + ]:         27 :                 if (max_type == Xapian::Query::WILDCARD_LIMIT_FIRST)
     360                 :          6 :                     break;
     361 [ #  # ][ +  - ]:         21 :                 string msg("Edit distance ");
     362 [ #  # ][ #  # ]:         21 :                 msg += query->get_pattern();
         [ +  - ][ +  - ]
     363   [ #  #  +  - ]:         21 :                 msg += '~';
     364 [ #  # ][ #  # ]:         21 :                 msg += str(query->get_threshold());
         [ +  - ][ +  - ]
     365   [ #  #  +  - ]:         21 :                 msg += " expands to more than ";
     366 [ #  # ][ #  # ]:         21 :                 msg += str(query->get_max_expansion());
         [ +  - ][ +  - ]
     367   [ #  #  +  - ]:         21 :                 msg += " terms";
     368 [ #  # ][ #  # ]:        408 :                 throw Xapian::WildcardError(msg);
         [ +  - ][ +  - ]
     369                 :            :             }
     370                 :            :         }
     371                 :            : 
     372 [ #  # ][ #  # ]:       4144 :         add_postlist(qopt->open_lazy_post_list(term, 1, factor));
           [ #  #  #  # ]
         [ +  - ][ +  - ]
           [ +  +  +  + ]
     373                 :            :     }
     374                 :            : 
     375 [ #  # ][ +  + ]:        112 :     if (max_type == Xapian::Query::WILDCARD_LIMIT_MOST_FREQUENT) {
     376                 :            :         // FIXME: open_lazy_post_list() results in the term getting registered
     377                 :            :         // for stats, so we still incur an avoidable cost from the full
     378                 :            :         // expansion size of the wildcard, which is most likely to be visible
     379                 :            :         // with the remote backend.  Perhaps we should split creating the lazy
     380                 :            :         // postlist from registering the term for stats.
     381                 :          6 :         auto set_size = query->get_max_expansion();
     382   [ #  #  +  - ]:          6 :         if (size() > set_size) {
     383 [ #  # ][ +  - ]:          6 :             init_tf();
     384                 :          6 :             auto begin = pls.begin();
     385   [ #  #  +  - ]:          6 :             nth_element(begin, begin + set_size - 1, pls.end(),
     386                 :          6 :                         ComparePostListTermFreqAscending());
     387 [ #  # ][ +  - ]:          6 :             shrink(set_size);
     388                 :            :         }
     389                 :        133 :     }
     390                 :        112 : }
     391                 :            : 
     392                 :       2056 : class BoolOrContext : public Context<PostList*> {
     393                 :            :   public:
     394                 :       1028 :     BoolOrContext(QueryOptimiser* qopt_, size_t reserve)
     395                 :       1028 :         : Context(qopt_, reserve) { }
     396                 :            : 
     397                 :            :     PostList * postlist();
     398                 :            : };
     399                 :            : 
     400                 :            : PostList *
     401                 :        891 : BoolOrContext::postlist()
     402                 :            : {
     403                 :            :     PostList* pl;
     404      [ +  +  + ]:        891 :     switch (pls.size()) {
     405                 :            :         case 0:
     406                 :          1 :             pl = NULL;
     407                 :          1 :             break;
     408                 :            :         case 1:
     409                 :         77 :             pl = pls[0];
     410                 :         77 :             break;
     411                 :            :         default:
     412 [ +  - ][ +  - ]:        813 :             pl = new BoolOrPostList(pls.begin(), pls.end(), qopt->db_size);
     413                 :            :     }
     414                 :            : 
     415                 :            :     // Empty pls so our destructor doesn't delete them all!
     416                 :        891 :     pls.clear();
     417                 :        891 :     return pl;
     418                 :            : }
     419                 :            : 
     420                 :     280882 : class OrContext : public Context<PostListAndTermFreq> {
     421                 :            :   public:
     422                 :     140441 :     OrContext(QueryOptimiser* qopt_, size_t reserve)
     423                 :     140441 :         : Context(qopt_, reserve) { }
     424                 :            : 
     425                 :            :     /// Select the best set_size postlists from the last out_of added.
     426                 :            :     void select_elite_set(size_t set_size, size_t out_of);
     427                 :            : 
     428                 :            :     PostList * postlist();
     429                 :            :     PostList * postlist_max();
     430                 :            : };
     431                 :            : 
     432                 :            : void
     433                 :        208 : OrContext::select_elite_set(size_t set_size, size_t out_of)
     434                 :            : {
     435                 :        208 :     auto begin = pls.begin() + pls.size() - out_of;
     436         [ +  - ]:        208 :     nth_element(begin, begin + set_size - 1, pls.end(), CmpMaxOrTerms());
     437         [ +  - ]:        208 :     shrink(pls.size() - out_of + set_size);
     438                 :        208 : }
     439                 :            : 
     440                 :            : PostList *
     441                 :     140433 : OrContext::postlist()
     442                 :            : {
     443      [ -  +  + ]:     140433 :     switch (pls.size()) {
     444                 :            :         case 0:
     445                 :          0 :             return NULL;
     446                 :            :         case 1: {
     447                 :        224 :             PostList* pl = pls[0].pl;
     448                 :        224 :             pls.clear();
     449                 :        224 :             return pl;
     450                 :            :         }
     451                 :            :     }
     452                 :            : 
     453                 :            :     // Make postlists into a heap so that the postlist with the greatest term
     454                 :            :     // frequency is at the top of the heap.
     455                 :     140209 :     init_tf();
     456         [ +  - ]:     140209 :     Heap::make(pls.begin(), pls.end(), ComparePostListTermFreqAscending());
     457                 :            : 
     458                 :            :     // Now build a tree of binary OrPostList objects.
     459                 :            :     //
     460                 :            :     // The algorithm used to build the tree is like that used to build an
     461                 :            :     // optimal Huffman coding tree.  If we called next() repeatedly, this
     462                 :            :     // arrangement would minimise the number of method calls.  Generally we
     463                 :            :     // don't actually do that, but this arrangement is still likely to be a
     464                 :            :     // good one, and it does minimise the work in the worst case.
     465                 :            :     while (true) {
     466                 :            :         // We build the tree such that at each branch:
     467                 :            :         //
     468                 :            :         //   l.get_termfreq_est() >= r.get_termfreq_est()
     469                 :            :         //
     470                 :            :         // We do this so that the OrPostList class can be optimised assuming
     471                 :            :         // that this is the case.
     472                 :     142695 :         PostList * r = pls.front().pl;
     473                 :     142695 :         auto tf = pls.front().tf;
     474         [ +  - ]:     142695 :         Heap::pop(pls.begin(), pls.end(), ComparePostListTermFreqAscending());
     475                 :     142695 :         pls.pop_back();
     476                 :            :         PostList * pl;
     477                 :     142695 :         pl = new OrPostList(pls.front().pl, r, qopt->matcher, qopt->db_size);
     478                 :            : 
     479         [ +  + ]:     142695 :         if (pls.size() == 1) {
     480                 :     140209 :             pls.clear();
     481                 :     140209 :             return pl;
     482                 :            :         }
     483                 :            : 
     484                 :       2486 :         pls[0].pl = pl;
     485                 :       2486 :         pls[0].tf += tf;
     486                 :            :         Heap::replace(pls.begin(), pls.end(),
     487         [ +  - ]:       2486 :                       ComparePostListTermFreqAscending());
     488                 :     142919 :     }
     489                 :            : }
     490                 :            : 
     491                 :            : PostList *
     492                 :          8 : OrContext::postlist_max()
     493                 :            : {
     494      [ -  -  + ]:          8 :     switch (pls.size()) {
     495                 :            :         case 0:
     496                 :          0 :             return NULL;
     497                 :            :         case 1: {
     498                 :          0 :             PostList* pl = pls[0].pl;
     499                 :          0 :             pls.clear();
     500                 :          0 :             return pl;
     501                 :            :         }
     502                 :            :     }
     503                 :            : 
     504                 :            :     // Sort the postlists so that the postlist with the greatest term frequency
     505                 :            :     // is first.
     506                 :          8 :     init_tf();
     507         [ +  - ]:          8 :     sort(pls.begin(), pls.end(), ComparePostListTermFreqAscending());
     508                 :            : 
     509                 :            :     PostList * pl;
     510 [ +  - ][ +  - ]:          8 :     pl = new MaxPostList(pls.begin(), pls.end(), qopt->matcher, qopt->db_size);
     511                 :            : 
     512                 :          8 :     pls.clear();
     513                 :          8 :     return pl;
     514                 :            : }
     515                 :            : 
     516                 :        224 : class XorContext : public Context<PostList*> {
     517                 :            :   public:
     518                 :        112 :     XorContext(QueryOptimiser* qopt_, size_t reserve)
     519                 :        112 :         : Context(qopt_, reserve) { }
     520                 :            : 
     521                 :            :     PostList * postlist();
     522                 :            : };
     523                 :            : 
     524                 :            : PostList *
     525                 :        112 : XorContext::postlist()
     526                 :            : {
     527         [ -  + ]:        112 :     if (pls.empty())
     528                 :          0 :         return NULL;
     529                 :            : 
     530                 :        112 :     Xapian::doccount db_size = qopt->db_size;
     531                 :            :     PostList * pl;
     532 [ +  - ][ +  - ]:        112 :     pl = new MultiXorPostList(pls.begin(), pls.end(), qopt->matcher, db_size);
     533                 :            : 
     534                 :            :     // Empty pls so our destructor doesn't delete them all!
     535                 :        112 :     pls.clear();
     536                 :        112 :     return pl;
     537                 :            : }
     538                 :            : 
     539                 :       2256 : class AndContext : public Context<PostList*> {
     540                 :            :     class PosFilter {
     541                 :            :         Xapian::Query::op op_;
     542                 :            : 
     543                 :            :         /// Start and end indices for the PostLists this positional filter uses.
     544                 :            :         size_t begin, end;
     545                 :            : 
     546                 :            :         Xapian::termcount window;
     547                 :            : 
     548                 :            :       public:
     549                 :        688 :         PosFilter(Xapian::Query::op op__, size_t begin_, size_t end_,
     550                 :            :                   Xapian::termcount window_)
     551                 :        688 :             : op_(op__), begin(begin_), end(end_), window(window_) { }
     552                 :            : 
     553                 :            :         PostList * postlist(PostList* pl,
     554                 :            :                             const vector<PostList*>& pls,
     555                 :            :                             PostListTree* pltree) const;
     556                 :            :     };
     557                 :            : 
     558                 :            :     list<PosFilter> pos_filters;
     559                 :            : 
     560                 :            :   public:
     561                 :       1128 :     AndContext(QueryOptimiser* qopt_, size_t reserve)
     562                 :       1128 :         : Context(qopt_, reserve) { }
     563                 :            : 
     564                 :       2712 :     bool add_postlist(PostList* pl) {
     565         [ -  + ]:       2712 :         if (!pl) {
     566                 :          0 :             shrink(0);
     567                 :          0 :             return false;
     568                 :            :         }
     569                 :       2712 :         pls.emplace_back(pl);
     570                 :       2712 :         return true;
     571                 :            :     }
     572                 :            : 
     573                 :            :     void add_pos_filter(Query::op op_,
     574                 :            :                         size_t n_subqs,
     575                 :            :                         Xapian::termcount window);
     576                 :            : 
     577                 :            :     PostList * postlist();
     578                 :            : };
     579                 :            : 
     580                 :            : PostList *
     581                 :        688 : AndContext::PosFilter::postlist(PostList* pl,
     582                 :            :                                 const vector<PostList*>& pls,
     583                 :            :                                 PostListTree* pltree) const
     584                 :            : try {
     585                 :        688 :     vector<PostList *>::const_iterator terms_begin = pls.begin() + begin;
     586                 :        688 :     vector<PostList *>::const_iterator terms_end = pls.begin() + end;
     587                 :            : 
     588         [ +  + ]:        688 :     if (op_ == Xapian::Query::OP_NEAR) {
     589 [ +  - ][ +  - ]:        214 :         pl = new NearPostList(pl, window, terms_begin, terms_end, pltree);
     590         [ +  + ]:        474 :     } else if (window == end - begin) {
     591                 :            :         AssertEq(op_, Xapian::Query::OP_PHRASE);
     592 [ +  - ][ +  - ]:        326 :         pl = new ExactPhrasePostList(pl, terms_begin, terms_end, pltree);
     593                 :            :     } else {
     594                 :            :         AssertEq(op_, Xapian::Query::OP_PHRASE);
     595 [ +  - ][ +  - ]:        148 :         pl = new PhrasePostList(pl, window, terms_begin, terms_end, pltree);
     596                 :            :     }
     597                 :        688 :     return pl;
     598                 :          0 : } catch (...) {
     599         [ #  # ]:          0 :     delete pl;
     600                 :          0 :     throw;
     601                 :            : }
     602                 :            : 
     603                 :            : void
     604                 :        688 : AndContext::add_pos_filter(Query::op op_,
     605                 :            :                            size_t n_subqs,
     606                 :            :                            Xapian::termcount window)
     607                 :            : {
     608                 :            :     Assert(n_subqs > 1);
     609                 :        688 :     size_t end = pls.size();
     610                 :        688 :     size_t begin = end - n_subqs;
     611         [ +  - ]:        688 :     pos_filters.push_back(PosFilter(op_, begin, end, window));
     612                 :        688 : }
     613                 :            : 
     614                 :            : PostList *
     615                 :       1128 : AndContext::postlist()
     616                 :            : {
     617         [ +  + ]:       1128 :     if (pls.empty()) {
     618                 :         16 :         return NULL;
     619                 :            :     }
     620                 :            : 
     621                 :       2224 :     unique_ptr<PostList> pl(new MultiAndPostList(pls.begin(), pls.end(),
     622 [ +  - ][ +  - ]:       1112 :                                                  qopt->matcher, qopt->db_size));
     623                 :            : 
     624                 :            :     // Sort the positional filters to try to apply them in an efficient order.
     625                 :            :     // FIXME: We need to figure out what that is!  Try applying lowest cf/tf
     626                 :            :     // first?
     627                 :            : 
     628                 :            :     // Apply any positional filters.
     629                 :       1112 :     list<PosFilter>::const_iterator i;
     630         [ +  + ]:       1800 :     for (i = pos_filters.begin(); i != pos_filters.end(); ++i) {
     631                 :        688 :         const PosFilter & filter = *i;
     632         [ +  - ]:        688 :         pl.reset(filter.postlist(pl.release(), pls, qopt->matcher));
     633                 :            :     }
     634                 :            : 
     635                 :            :     // Empty pls so our destructor doesn't delete them all!
     636                 :       1112 :     pls.clear();
     637                 :       1128 :     return pl.release();
     638                 :            : }
     639                 :            : 
     640                 :            : }
     641                 :            : 
     642         [ -  + ]:    2668128 : Query::Internal::~Internal() { }
     643                 :            : 
     644                 :            : size_t
     645                 :        776 : Query::Internal::get_num_subqueries() const XAPIAN_NOEXCEPT
     646                 :            : {
     647                 :        776 :     return 0;
     648                 :            : }
     649                 :            : 
     650                 :            : const Query
     651                 :          0 : Query::Internal::get_subquery(size_t) const
     652                 :            : {
     653 [ #  # ][ #  # ]:          0 :     throw Xapian::InvalidArgumentError("get_subquery() not meaningful for this Query object");
                 [ #  # ]
     654                 :            : }
     655                 :            : 
     656                 :            : Xapian::termcount
     657                 :          0 : Query::Internal::get_wqf() const
     658                 :            : {
     659 [ #  # ][ #  # ]:          0 :     throw Xapian::InvalidArgumentError("get_wqf() not meaningful for this Query object");
                 [ #  # ]
     660                 :            : }
     661                 :            : 
     662                 :            : Xapian::termpos
     663                 :          0 : Query::Internal::get_pos() const
     664                 :            : {
     665 [ #  # ][ #  # ]:          0 :     throw Xapian::InvalidArgumentError("get_pos() not meaningful for this Query object");
                 [ #  # ]
     666                 :            : }
     667                 :            : 
     668                 :            : void
     669                 :      24124 : Query::Internal::gather_terms(void *) const
     670                 :            : {
     671                 :      24124 : }
     672                 :            : 
     673                 :            : Xapian::termcount
     674                 :      10906 : Query::Internal::get_length() const XAPIAN_NOEXCEPT
     675                 :            : {
     676                 :      10906 :     return 0;
     677                 :            : }
     678                 :            : 
     679                 :            : Query::Internal *
     680                 :      13519 : Query::Internal::unserialise(const char ** p, const char * end,
     681                 :            :                              const Registry & reg)
     682                 :            : {
     683         [ +  + ]:      13519 :     if (*p == end)
     684                 :          1 :         return NULL;
     685                 :      13518 :     unsigned char ch = *(*p)++;
     686   [ +  +  +  +  :      13518 :     switch (ch >> 5) {
                      - ]
     687                 :            :         case 4: case 5: case 6: case 7: {
     688                 :            :             // Multi-way branch
     689                 :            :             //
     690                 :            :             // 1ccccnnn where:
     691                 :            :             //   nnn -> n_subqs (0 means encoded value follows)
     692                 :            :             //   cccc -> code (which OP_XXX)
     693                 :        840 :             size_t n_subqs = ch & 0x07;
     694         [ +  + ]:        840 :             if (n_subqs == 0) {
     695         [ +  - ]:         46 :                 decode_length(p, end, n_subqs);
     696                 :         46 :                 n_subqs += 8;
     697                 :            :             }
     698                 :        840 :             unsigned char code = (ch >> 3) & 0x0f;
     699                 :        840 :             Xapian::termcount parameter = 0;
     700         [ +  + ]:        840 :             if (code >= 13)
     701         [ +  - ]:        231 :                 decode_length(p, end, parameter);
     702                 :            :             Xapian::Internal::QueryBranch * result;
     703   [ +  +  +  +  :        840 :             switch (code) {
          +  +  +  +  +  
                +  +  - ]
     704                 :            :                 case 0: // OP_AND
     705 [ +  - ][ +  - ]:         58 :                     result = new Xapian::Internal::QueryAnd(n_subqs);
     706                 :         58 :                     break;
     707                 :            :                 case 1: // OP_OR
     708 [ +  - ][ +  - ]:        371 :                     result = new Xapian::Internal::QueryOr(n_subqs);
     709                 :        371 :                     break;
     710                 :            :                 case 2: // OP_AND_NOT
     711 [ +  - ][ +  - ]:         34 :                     result = new Xapian::Internal::QueryAndNot(n_subqs);
     712                 :         34 :                     break;
     713                 :            :                 case 3: // OP_XOR
     714 [ +  - ][ +  - ]:         26 :                     result = new Xapian::Internal::QueryXor(n_subqs);
     715                 :         26 :                     break;
     716                 :            :                 case 4: // OP_AND_MAYBE
     717 [ +  - ][ +  - ]:         16 :                     result = new Xapian::Internal::QueryAndMaybe(n_subqs);
     718                 :         16 :                     break;
     719                 :            :                 case 5: // OP_FILTER
     720 [ +  - ][ +  - ]:         10 :                     result = new Xapian::Internal::QueryFilter(n_subqs);
     721                 :         10 :                     break;
     722                 :            :                 case 6: // OP_SYNONYM
     723 [ +  - ][ +  - ]:         92 :                     result = new Xapian::Internal::QuerySynonym(n_subqs);
     724                 :         92 :                     break;
     725                 :            :                 case 7: // OP_MAX
     726 [ +  - ][ +  - ]:          2 :                     result = new Xapian::Internal::QueryMax(n_subqs);
     727                 :          2 :                     break;
     728                 :            :                 case 13: // OP_ELITE_SET
     729                 :            :                     result = new Xapian::Internal::QueryEliteSet(n_subqs,
     730 [ +  - ][ +  - ]:         56 :                                                                  parameter);
     731                 :         56 :                     break;
     732                 :            :                 case 14: // OP_NEAR
     733                 :            :                     result = new Xapian::Internal::QueryNear(n_subqs,
     734 [ +  - ][ +  - ]:         58 :                                                              parameter);
     735                 :         58 :                     break;
     736                 :            :                 case 15: // OP_PHRASE
     737                 :            :                     result = new Xapian::Internal::QueryPhrase(n_subqs,
     738 [ +  - ][ +  - ]:        117 :                                                                parameter);
     739                 :        117 :                     break;
     740                 :            :                 default:
     741                 :            :                     // 8 to 12 are currently unused.
     742 [ #  # ][ #  # ]:          0 :                     throw SerialisationError("Unknown multi-way branch Query operator");
                 [ #  # ]
     743                 :            :             }
     744         [ +  + ]:       2929 :             do {
     745 [ +  - ][ +  - ]:       2929 :                 result->add_subquery(Xapian::Query(unserialise(p, end, reg)));
                 [ +  - ]
     746                 :            :             } while (--n_subqs);
     747         [ +  - ]:        840 :             result->done();
     748                 :        840 :             return result;
     749                 :            :         }
     750                 :            :         case 2: case 3: { // Term
     751                 :            :             // Term
     752                 :            :             //
     753                 :            :             // 01ccLLLL where:
     754                 :            :             //   LLLL -> length (0 means encoded value follows)
     755                 :            :             //   cc -> code:
     756                 :            :             //     0: wqf = 0; pos = 0
     757                 :            :             //     1: wqf = 1; pos = 0
     758                 :            :             //     2: wqf = 1; pos -> encoded value follows
     759                 :            :             //     3: wqf -> encoded value follows; pos -> encoded value follows
     760                 :       8360 :             size_t len = ch & 0x0f;
     761         [ -  + ]:       8360 :             if (len == 0) {
     762         [ #  # ]:          0 :                 decode_length(p, end, len);
     763                 :          0 :                 len += 16;
     764                 :            :             }
     765         [ -  + ]:       8360 :             if (size_t(end - *p) < len)
     766 [ #  # ][ #  # ]:          0 :                 throw SerialisationError("Not enough data");
                 [ #  # ]
     767         [ +  - ]:       8360 :             string term(*p, len);
     768                 :       8360 :             *p += len;
     769                 :            : 
     770                 :       8360 :             int code = ((ch >> 4) & 0x03);
     771                 :            : 
     772                 :       8360 :             Xapian::termcount wqf = static_cast<Xapian::termcount>(code > 0);
     773         [ +  + ]:       8360 :             if (code == 3)
     774         [ +  - ]:          6 :                 decode_length(p, end, wqf);
     775                 :            : 
     776                 :       8360 :             Xapian::termpos pos = 0;
     777         [ +  + ]:       8360 :             if (code >= 2)
     778         [ +  - ]:        449 :                 decode_length(p, end, pos);
     779                 :            : 
     780 [ +  - ][ +  - ]:       8360 :             return new Xapian::Internal::QueryTerm(term, wqf, pos);
     781                 :            :         }
     782                 :            :         case 1: {
     783                 :            :             // OP_VALUE_RANGE or OP_VALUE_GE or OP_VALUE_LE
     784                 :            :             //
     785                 :            :             // 001tssss where:
     786                 :            :             //   ssss -> slot number (15 means encoded value follows)
     787                 :            :             //   t -> op:
     788                 :            :             //     0: OP_VALUE_RANGE (or OP_VALUE_LE if begin empty)
     789                 :            :             //     1: OP_VALUE_GE
     790                 :       3996 :             Xapian::valueno slot = ch & 15;
     791         [ -  + ]:       3996 :             if (slot == 15) {
     792         [ #  # ]:          0 :                 decode_length(p, end, slot);
     793                 :          0 :                 slot += 15;
     794                 :            :             }
     795                 :            :             size_t len;
     796         [ +  - ]:       3996 :             decode_length_and_check(p, end, len);
     797         [ +  - ]:       3996 :             string begin(*p, len);
     798                 :       3996 :             *p += len;
     799         [ +  + ]:       3996 :             if (ch & 0x10) {
     800                 :            :                 // OP_VALUE_GE
     801 [ +  - ][ +  - ]:         26 :                 return new Xapian::Internal::QueryValueGE(slot, begin);
     802                 :            :             }
     803                 :            : 
     804                 :            :             // OP_VALUE_RANGE
     805         [ +  - ]:       3970 :             decode_length_and_check(p, end, len);
     806         [ +  - ]:       7940 :             string end_(*p, len);
     807                 :       3970 :             *p += len;
     808         [ +  + ]:       3970 :             if (begin.empty()) // FIXME: is this right?
     809 [ +  - ][ +  - ]:         50 :                 return new Xapian::Internal::QueryValueLE(slot, end_);
     810 [ +  - ][ +  - ]:       7916 :             return new Xapian::Internal::QueryValueRange(slot, begin, end_);
     811                 :            :         }
     812                 :            :         case 0: {
     813                 :            :             // Other operators
     814                 :            :             //
     815                 :            :             //   000ttttt where:
     816                 :            :             //     ttttt -> encodes which OP_XXX
     817   [ -  +  +  +  :        322 :             switch (ch & 0x1f) {
             +  -  +  - ]
     818                 :            :                 case 0x00: // OP_INVALID
     819         [ #  # ]:          0 :                     return new Xapian::Internal::QueryInvalid();
     820                 :            :                 case 0x0a: { // Edit distance
     821         [ -  + ]:         40 :                     if (*p == end)
     822 [ #  # ][ #  # ]:          0 :                         throw SerialisationError("not enough data");
                 [ #  # ]
     823                 :            :                     Xapian::termcount max_expansion;
     824         [ +  - ]:         40 :                     decode_length(p, end, max_expansion);
     825         [ -  + ]:         40 :                     if (end - *p < 2)
     826 [ #  # ][ #  # ]:          0 :                         throw SerialisationError("not enough data");
                 [ #  # ]
     827                 :         40 :                     int flags = static_cast<unsigned char>(*(*p)++);
     828                 :         40 :                     op combiner = static_cast<op>(*(*p)++);
     829                 :            :                     unsigned edit_distance;
     830         [ +  - ]:         40 :                     decode_length(p, end, edit_distance);
     831                 :            :                     size_t fixed_prefix_len;
     832         [ +  - ]:         40 :                     decode_length(p, end, fixed_prefix_len);
     833                 :            :                     size_t len;
     834         [ +  - ]:         40 :                     decode_length_and_check(p, end, len);
     835         [ +  - ]:         40 :                     string pattern(*p, len);
     836                 :         40 :                     *p += len;
     837                 :            :                     using Xapian::Internal::QueryEditDistance;
     838                 :            :                     return new QueryEditDistance(pattern,
     839                 :            :                                                  max_expansion,
     840                 :            :                                                  flags,
     841                 :            :                                                  combiner,
     842                 :            :                                                  edit_distance,
     843 [ +  - ][ +  - ]:         40 :                                                  fixed_prefix_len);
     844                 :            :                 }
     845                 :            :                 case 0x0b: { // Wildcard
     846         [ -  + ]:         68 :                     if (*p == end)
     847 [ #  # ][ #  # ]:          0 :                         throw SerialisationError("not enough data");
                 [ #  # ]
     848                 :            :                     Xapian::termcount max_expansion;
     849         [ +  - ]:         68 :                     decode_length(p, end, max_expansion);
     850         [ -  + ]:         68 :                     if (end - *p < 2)
     851 [ #  # ][ #  # ]:          0 :                         throw SerialisationError("not enough data");
                 [ #  # ]
     852                 :         68 :                     int flags = static_cast<unsigned char>(*(*p)++);
     853                 :         68 :                     op combiner = static_cast<op>(*(*p)++);
     854                 :            :                     size_t len;
     855         [ +  - ]:         68 :                     decode_length_and_check(p, end, len);
     856         [ +  - ]:         68 :                     string pattern(*p, len);
     857                 :         68 :                     *p += len;
     858                 :            :                     return new Xapian::Internal::QueryWildcard(pattern,
     859                 :            :                                                                max_expansion,
     860                 :            :                                                                flags,
     861 [ +  - ][ +  - ]:         68 :                                                                combiner);
     862                 :            :                 }
     863                 :            :                 case 0x0c: { // PostingSource
     864                 :            :                     size_t len;
     865         [ +  - ]:         43 :                     decode_length_and_check(p, end, len);
     866         [ +  - ]:         43 :                     string name(*p, len);
     867                 :         43 :                     *p += len;
     868                 :            : 
     869         [ +  - ]:         43 :                     const PostingSource * reg_source = reg.get_posting_source(name);
     870         [ +  + ]:         43 :                     if (!reg_source) {
     871         [ +  - ]:          2 :                         string m = "PostingSource ";
     872         [ +  - ]:          2 :                         m += name;
     873         [ +  - ]:          2 :                         m += " not registered";
     874 [ +  - ][ +  - ]:          2 :                         throw SerialisationError(m);
     875                 :            :                     }
     876                 :            : 
     877         [ +  - ]:         41 :                     decode_length_and_check(p, end, len);
     878                 :            :                     PostingSource * source =
     879                 :            :                         reg_source->unserialise_with_registry(string(*p, len),
     880 [ +  - ][ +  - ]:         41 :                                                               reg);
     881                 :         41 :                     *p += len;
     882 [ +  - ][ +  - ]:         43 :                     return new Xapian::Internal::QueryPostingSource(source->release());
     883                 :            :                 }
     884                 :            :                 case 0x0d: {
     885                 :            :                     using Xapian::Internal::QueryScaleWeight;
     886         [ +  - ]:        161 :                     double scale_factor = unserialise_double(p, end);
     887                 :            :                     return new QueryScaleWeight(scale_factor,
     888 [ +  - ][ +  - ]:        161 :                                                 Query(unserialise(p, end, reg)));
         [ +  - ][ +  - ]
     889                 :            :                 }
     890                 :            :                 case 0x0e: {
     891                 :            :                     Xapian::termcount wqf;
     892                 :            :                     Xapian::termpos pos;
     893         [ #  # ]:          0 :                     decode_length(p, end, wqf);
     894         [ #  # ]:          0 :                     decode_length(p, end, pos);
     895 [ #  # ][ #  # ]:          0 :                     return new Xapian::Internal::QueryTerm(string(), wqf, pos);
                 [ #  # ]
     896                 :            :                 }
     897                 :            :                 case 0x0f:
     898 [ +  - ][ +  - ]:         10 :                     return new Xapian::Internal::QueryTerm();
     899                 :            :                 default: // Others currently unused.
     900                 :          0 :                     break;
     901                 :            :             }
     902                 :          0 :             break;
     903                 :            :         }
     904                 :            :     }
     905         [ #  # ]:          0 :     string msg = "Unknown Query serialisation: ";
     906 [ #  # ][ #  # ]:          0 :     msg += str(ch);
     907 [ #  # ][ #  # ]:      13517 :     throw SerialisationError(msg);
     908                 :            : }
     909                 :            : 
     910                 :            : bool
     911                 :       1020 : Query::Internal::postlist_sub_and_like(AndContext& ctx,
     912                 :            :                                        QueryOptimiser * qopt,
     913                 :            :                                        double factor) const
     914                 :            : {
     915                 :       1020 :     return ctx.add_postlist(postlist(qopt, factor));
     916                 :            : }
     917                 :            : 
     918                 :            : void
     919                 :     285396 : Query::Internal::postlist_sub_or_like(OrContext& ctx,
     920                 :            :                                       QueryOptimiser * qopt,
     921                 :            :                                       double factor) const
     922                 :            : {
     923                 :     285396 :     ctx.add_postlist(postlist(qopt, factor));
     924                 :     285396 : }
     925                 :            : 
     926                 :            : void
     927                 :       1358 : Query::Internal::postlist_sub_bool_or_like(BoolOrContext& ctx,
     928                 :            :                                            QueryOptimiser * qopt) const
     929                 :            : {
     930                 :       1358 :     ctx.add_postlist(postlist(qopt, 0.0));
     931                 :       1358 : }
     932                 :            : 
     933                 :            : void
     934                 :        312 : Query::Internal::postlist_sub_xor(XorContext& ctx,
     935                 :            :                                   QueryOptimiser * qopt,
     936                 :            :                                   double factor) const
     937                 :            : {
     938                 :        312 :     ctx.add_postlist(postlist(qopt, factor));
     939                 :        312 : }
     940                 :            : 
     941                 :            : namespace Internal {
     942                 :            : 
     943                 :            : Query::op
     944                 :      27026 : QueryTerm::get_type() const XAPIAN_NOEXCEPT
     945                 :            : {
     946         [ +  + ]:      27026 :     return term.empty() ? Query::LEAF_MATCH_ALL : Query::LEAF_TERM;
     947                 :            : }
     948                 :            : 
     949                 :            : string
     950                 :       6520 : QueryTerm::get_description() const
     951                 :            : {
     952                 :       6520 :     string desc;
     953         [ +  + ]:       6520 :     if (term.empty()) {
     954         [ +  - ]:         26 :         desc = "<alldocuments>";
     955                 :            :     } else {
     956         [ +  - ]:       6494 :         description_append(desc, term);
     957                 :            :     }
     958         [ -  + ]:       6520 :     if (wqf != 1) {
     959         [ #  # ]:          0 :         desc += '#';
     960 [ #  # ][ #  # ]:          0 :         desc += str(wqf);
     961                 :            :     }
     962         [ +  + ]:       6520 :     if (pos) {
     963         [ +  - ]:       4891 :         desc += '@';
     964 [ +  - ][ +  - ]:       4891 :         desc += str(pos);
     965                 :            :     }
     966                 :       6520 :     return desc;
     967                 :            : }
     968                 :            : 
     969                 :        667 : QueryPostingSource::QueryPostingSource(PostingSource * source_)
     970                 :        671 :     : source(source_)
     971                 :            : {
     972         [ +  + ]:        667 :     if (!source_)
     973 [ +  - ][ +  - ]:          4 :         throw Xapian::InvalidArgumentError("source parameter can't be NULL");
                 [ +  - ]
     974         [ +  + ]:        663 :     if (source->_refs == 0) {
     975                 :            :         // source_ isn't reference counted, so try to clone it.  If clone()
     976                 :            :         // isn't implemented, just use the object provided and it's the
     977                 :            :         // caller's responsibility to ensure it stays valid while in use.
     978         [ +  - ]:        621 :         PostingSource * cloned_source = source->clone();
     979 [ +  + ][ +  - ]:        621 :         if (cloned_source) source = cloned_source->release();
     980                 :            :     }
     981                 :        663 : }
     982                 :            : 
     983                 :            : Query::op
     984                 :         27 : QueryPostingSource::get_type() const XAPIAN_NOEXCEPT
     985                 :            : {
     986                 :         27 :     return Query::LEAF_POSTING_SOURCE;
     987                 :            : }
     988                 :            : 
     989                 :            : string
     990                 :         21 : QueryPostingSource::get_description() const
     991                 :            : {
     992         [ +  - ]:         21 :     string desc = "PostingSource(";
     993 [ +  - ][ +  - ]:         21 :     desc += source->get_description();
     994         [ +  - ]:         21 :     desc += ')';
     995                 :         21 :     return desc;
     996                 :            : }
     997                 :            : 
     998                 :       1023 : QueryScaleWeight::QueryScaleWeight(double factor, const Query & subquery_)
     999         [ +  - ]:       1247 :     : scale_factor(factor), subquery(subquery_)
    1000                 :            : {
    1001         [ +  + ]:       1023 :     if (rare(scale_factor < 0.0))
    1002 [ +  - ][ +  - ]:        224 :         throw Xapian::InvalidArgumentError("OP_SCALE_WEIGHT requires factor >= 0");
                 [ +  - ]
    1003                 :        799 : }
    1004                 :            : 
    1005                 :            : Query::op
    1006                 :         11 : QueryScaleWeight::get_type() const XAPIAN_NOEXCEPT
    1007                 :            : {
    1008                 :         11 :     return Query::OP_SCALE_WEIGHT;
    1009                 :            : }
    1010                 :            : 
    1011                 :            : size_t
    1012                 :          2 : QueryScaleWeight::get_num_subqueries() const XAPIAN_NOEXCEPT
    1013                 :            : {
    1014                 :          2 :     return 1;
    1015                 :            : }
    1016                 :            : 
    1017                 :            : const Query
    1018                 :          5 : QueryScaleWeight::get_subquery(size_t) const
    1019                 :            : {
    1020                 :          5 :     return subquery;
    1021                 :            : }
    1022                 :            : 
    1023                 :            : string
    1024                 :        348 : QueryScaleWeight::get_description() const
    1025                 :            : {
    1026                 :            :     Assert(subquery.internal.get());
    1027                 :        348 :     string desc = str(scale_factor);
    1028         [ +  - ]:        348 :     desc += " * ";
    1029 [ +  - ][ +  - ]:        348 :     desc += subquery.internal->get_description();
    1030                 :        348 :     return desc;
    1031                 :            : }
    1032                 :            : 
    1033                 :            : PostList*
    1034                 :     312613 : QueryTerm::postlist(QueryOptimiser * qopt, double factor) const
    1035                 :            : {
    1036                 :            :     LOGCALL(QUERY, PostList*, "QueryTerm::postlist", qopt | factor);
    1037         [ +  + ]:     312613 :     if (factor != 0.0)
    1038                 :     310791 :         qopt->inc_total_subqs();
    1039                 :     312613 :     RETURN(qopt->open_post_list(term, wqf, factor));
    1040                 :            : }
    1041                 :            : 
    1042                 :            : PostList*
    1043                 :        664 : QueryPostingSource::postlist(QueryOptimiser * qopt, double factor) const
    1044                 :            : {
    1045                 :            :     LOGCALL(QUERY, PostList*, "QueryPostingSource::postlist", qopt | factor);
    1046                 :            :     Assert(source.get());
    1047         [ +  + ]:        664 :     if (factor != 0.0)
    1048                 :        640 :         qopt->inc_total_subqs();
    1049                 :            :     // Casting away const on the Database::Internal here is OK, as we wrap
    1050                 :            :     // them in a const Xapian::Database so non-const methods can't actually
    1051                 :            :     // be called on the Database::Internal object.
    1052                 :            :     const Xapian::Database wrappeddb(
    1053         [ +  - ]:        664 :             const_cast<Xapian::Database::Internal*>(&(qopt->db)));
    1054 [ +  - ][ +  - ]:        664 :     RETURN(new ExternalPostList(wrappeddb, source.get(), factor, qopt->matcher));
    1055                 :            : }
    1056                 :            : 
    1057                 :            : PostList*
    1058                 :        654 : QueryScaleWeight::postlist(QueryOptimiser * qopt, double factor) const
    1059                 :            : {
    1060                 :            :     LOGCALL(QUERY, PostList*, "QueryScaleWeight::postlist", qopt | factor);
    1061                 :        654 :     RETURN(subquery.internal->postlist(qopt, factor * scale_factor));
    1062                 :            : }
    1063                 :            : 
    1064                 :            : void
    1065                 :     524313 : QueryTerm::gather_terms(void * void_terms) const
    1066                 :            : {
    1067                 :            :     // Skip Xapian::Query::MatchAll (aka Xapian::Query("")).
    1068         [ +  + ]:     524313 :     if (!term.empty()) {
    1069                 :            :         vector<pair<Xapian::termpos, string>> &terms =
    1070                 :     524181 :             *static_cast<vector<pair<Xapian::termpos, string>>*>(void_terms);
    1071         [ +  - ]:     524181 :         terms.push_back(make_pair(pos, term));
    1072                 :            :     }
    1073                 :     524313 : }
    1074                 :            : 
    1075                 :            : PostList*
    1076                 :      11974 : QueryValueRange::postlist(QueryOptimiser *qopt, double factor) const
    1077                 :            : {
    1078                 :            :     LOGCALL(QUERY, PostList*, "QueryValueRange::postlist", qopt | factor);
    1079         [ +  - ]:      11974 :     if (factor != 0.0)
    1080                 :      11974 :         qopt->inc_total_subqs();
    1081                 :      11974 :     const Xapian::Database::Internal & db = qopt->db;
    1082                 :      11974 :     const string & lb = db.get_value_lower_bound(slot);
    1083         [ +  + ]:      11974 :     if (lb.empty()) {
    1084                 :            :         // This should only happen if there are no values in this slot (which
    1085                 :            :         // could be because the backend just doesn't support values at all).
    1086                 :            :         // If there were values in the slot, the backend should have a
    1087                 :            :         // non-empty lower bound, even if it isn't a tight one.
    1088                 :            :         AssertEq(db.get_value_freq(slot), 0);
    1089                 :          4 :         RETURN(NULL);
    1090                 :            :     }
    1091 [ +  - ][ +  + ]:      11970 :     if (end < lb) {
    1092                 :         23 :         RETURN(NULL);
    1093                 :            :     }
    1094         [ +  - ]:      23894 :     const string & ub = db.get_value_upper_bound(slot);
    1095 [ +  - ][ +  + ]:      11947 :     if (begin > ub) {
    1096                 :         25 :         RETURN(NULL);
    1097                 :            :     }
    1098 [ +  - ][ +  + ]:      11922 :     if (end >= ub) {
    1099                 :            :         // If begin <= lb too, then the range check isn't needed, but we do
    1100                 :            :         // still need to consider which documents have a value set in this
    1101                 :            :         // slot.  If this value is set for all documents, we can replace it
    1102                 :            :         // with the MatchAll postlist, which is especially efficient if
    1103                 :            :         // there are no gaps in the docids.
    1104 [ +  - ][ +  + ]:        554 :         if (begin <= lb && db.get_value_freq(slot) == db.get_doccount()) {
         [ +  - ][ +  - ]
         [ +  + ][ +  + ]
    1105 [ +  - ][ +  - ]:         25 :             RETURN(db.open_post_list(string()));
    1106                 :            :         }
    1107 [ +  - ][ +  - ]:        529 :         RETURN(new ValueGePostList(&db, slot, begin));
    1108                 :            :     }
    1109 [ +  - ][ +  - ]:      23342 :     RETURN(new ValueRangePostList(&db, slot, begin, end));
    1110                 :            : }
    1111                 :            : 
    1112                 :            : void
    1113                 :       3920 : QueryValueRange::serialise(string & result) const
    1114                 :            : {
    1115         [ +  - ]:       3920 :     if (slot < 15) {
    1116                 :       3920 :         result += static_cast<char>(0x20 | slot);
    1117                 :            :     } else {
    1118                 :          0 :         result += static_cast<char>(0x20 | 15);
    1119         [ #  # ]:          0 :         result += encode_length(slot - 15);
    1120                 :            :     }
    1121         [ +  - ]:       3920 :     result += encode_length(begin.size());
    1122                 :       3920 :     result += begin;
    1123         [ +  - ]:       3920 :     result += encode_length(end.size());
    1124                 :       3920 :     result += end;
    1125                 :       3920 : }
    1126                 :            : 
    1127                 :            : Query::op
    1128                 :      19005 : QueryValueRange::get_type() const XAPIAN_NOEXCEPT
    1129                 :            : {
    1130                 :      19005 :     return Query::OP_VALUE_RANGE;
    1131                 :            : }
    1132                 :            : 
    1133                 :            : string
    1134                 :         55 : QueryValueRange::get_description() const
    1135                 :            : {
    1136         [ +  - ]:         55 :     string desc = "VALUE_RANGE ";
    1137 [ +  - ][ +  - ]:         55 :     desc += str(slot);
    1138         [ +  - ]:         55 :     desc += ' ';
    1139         [ +  - ]:         55 :     description_append(desc, begin);
    1140         [ +  - ]:         55 :     desc += ' ';
    1141         [ +  - ]:         55 :     description_append(desc, end);
    1142                 :         55 :     return desc;
    1143                 :            : }
    1144                 :            : 
    1145                 :            : PostList*
    1146                 :        198 : QueryValueLE::postlist(QueryOptimiser *qopt, double factor) const
    1147                 :            : {
    1148                 :            :     LOGCALL(QUERY, PostList*, "QueryValueLE::postlist", qopt | factor);
    1149         [ +  - ]:        198 :     if (factor != 0.0)
    1150                 :        198 :         qopt->inc_total_subqs();
    1151                 :        198 :     const Xapian::Database::Internal & db = qopt->db;
    1152                 :        198 :     const string & lb = db.get_value_lower_bound(slot);
    1153         [ +  + ]:        198 :     if (lb.empty()) {
    1154                 :            :         // This should only happen if there are no values in this slot (which
    1155                 :            :         // could be because the backend just doesn't support values at all).
    1156                 :            :         // If there were values in the slot, the backend should have a
    1157                 :            :         // non-empty lower bound, even if it isn't a tight one.
    1158                 :            :         AssertEq(db.get_value_freq(slot), 0);
    1159                 :          1 :         RETURN(NULL);
    1160                 :            :     }
    1161 [ +  - ][ +  + ]:        197 :     if (limit < lb) {
    1162                 :         18 :         RETURN(NULL);
    1163                 :            :     }
    1164 [ +  - ][ +  - ]:        179 :     if (limit >= db.get_value_upper_bound(slot)) {
                 [ +  + ]
    1165                 :            :         // The range check isn't needed, but we do still need to consider
    1166                 :            :         // which documents have a value set in this slot.  If this value is
    1167                 :            :         // set for all documents, we can replace it with the MatchAll
    1168                 :            :         // postlist, which is especially efficient if there are no gaps in
    1169                 :            :         // the docids.
    1170 [ +  - ][ +  - ]:         21 :         if (db.get_value_freq(slot) == db.get_doccount()) {
                 [ +  - ]
    1171 [ +  - ][ +  - ]:         21 :             RETURN(db.open_post_list(string()));
    1172                 :            :         }
    1173                 :            :     }
    1174 [ +  - ][ +  - ]:        198 :     RETURN(new ValueRangePostList(&db, slot, string(), limit));
                 [ +  - ]
    1175                 :            : }
    1176                 :            : 
    1177                 :            : void
    1178                 :         50 : QueryValueLE::serialise(string & result) const
    1179                 :            : {
    1180                 :            :     // Encode as a range with an empty start (which only takes a single byte to
    1181                 :            :     // encode).
    1182         [ +  - ]:         50 :     if (slot < 15) {
    1183                 :         50 :         result += static_cast<char>(0x20 | slot);
    1184                 :            :     } else {
    1185                 :          0 :         result += static_cast<char>(0x20 | 15);
    1186         [ #  # ]:          0 :         result += encode_length(slot - 15);
    1187                 :            :     }
    1188         [ +  - ]:         50 :     result += encode_length(0);
    1189         [ +  - ]:         50 :     result += encode_length(limit.size());
    1190                 :         50 :     result += limit;
    1191                 :         50 : }
    1192                 :            : 
    1193                 :            : Query::op
    1194                 :         10 : QueryValueLE::get_type() const XAPIAN_NOEXCEPT
    1195                 :            : {
    1196                 :         10 :     return Query::OP_VALUE_LE;
    1197                 :            : }
    1198                 :            : 
    1199                 :            : string
    1200                 :          5 : QueryValueLE::get_description() const
    1201                 :            : {
    1202         [ +  - ]:          5 :     string desc = "VALUE_LE ";
    1203 [ +  - ][ +  - ]:          5 :     desc += str(slot);
    1204         [ +  - ]:          5 :     desc += ' ';
    1205         [ +  - ]:          5 :     description_append(desc, limit);
    1206                 :          5 :     return desc;
    1207                 :            : }
    1208                 :            : 
    1209                 :            : PostList*
    1210                 :        104 : QueryValueGE::postlist(QueryOptimiser *qopt, double factor) const
    1211                 :            : {
    1212                 :            :     LOGCALL(QUERY, PostList*, "QueryValueGE::postlist", qopt | factor);
    1213         [ +  - ]:        104 :     if (factor != 0.0)
    1214                 :        104 :         qopt->inc_total_subqs();
    1215                 :        104 :     const Xapian::Database::Internal & db = qopt->db;
    1216                 :        104 :     const string & lb = db.get_value_lower_bound(slot);
    1217         [ -  + ]:        104 :     if (lb.empty()) {
    1218                 :            :         // This should only happen if there are no values in this slot (which
    1219                 :            :         // could be because the backend just doesn't support values at all).
    1220                 :            :         // If there were values in the slot, the backend should have a
    1221                 :            :         // non-empty lower bound, even if it isn't a tight one.
    1222                 :            :         AssertEq(db.get_value_freq(slot), 0);
    1223                 :          0 :         RETURN(NULL);
    1224                 :            :     }
    1225 [ +  - ][ +  - ]:        104 :     if (limit > db.get_value_upper_bound(slot)) {
                 [ +  + ]
    1226                 :          8 :         RETURN(NULL);
    1227                 :            :     }
    1228 [ +  - ][ +  + ]:         96 :     if (limit < lb) {
    1229                 :            :         // The range check isn't needed, but we do still need to consider
    1230                 :            :         // which documents have a value set in this slot.  If this value is
    1231                 :            :         // set for all documents, we can replace it with the MatchAll
    1232                 :            :         // postlist, which is especially efficient if there are no gaps in
    1233                 :            :         // the docids.
    1234 [ +  - ][ +  - ]:          1 :         if (db.get_value_freq(slot) == db.get_doccount()) {
                 [ +  - ]
    1235 [ +  - ][ +  - ]:          1 :             RETURN(db.open_post_list(string()));
    1236                 :            :         }
    1237                 :            :     }
    1238 [ +  - ][ +  - ]:        104 :     RETURN(new ValueGePostList(&db, slot, limit));
    1239                 :            : }
    1240                 :            : 
    1241                 :            : void
    1242                 :         26 : QueryValueGE::serialise(string & result) const
    1243                 :            : {
    1244         [ +  - ]:         26 :     if (slot < 15) {
    1245                 :         26 :         result += static_cast<char>(0x20 | 0x10 | slot);
    1246                 :            :     } else {
    1247                 :          0 :         result += static_cast<char>(0x20 | 0x10 | 15);
    1248         [ #  # ]:          0 :         result += encode_length(slot - 15);
    1249                 :            :     }
    1250         [ +  - ]:         26 :     result += encode_length(limit.size());
    1251                 :         26 :     result += limit;
    1252                 :         26 : }
    1253                 :            : 
    1254                 :            : Query::op
    1255                 :          9 : QueryValueGE::get_type() const XAPIAN_NOEXCEPT
    1256                 :            : {
    1257                 :          9 :     return Query::OP_VALUE_GE;
    1258                 :            : }
    1259                 :            : 
    1260                 :            : string
    1261                 :          5 : QueryValueGE::get_description() const
    1262                 :            : {
    1263         [ +  - ]:          5 :     string desc = "VALUE_GE ";
    1264 [ +  - ][ +  - ]:          5 :     desc += str(slot);
    1265         [ +  - ]:          5 :     desc += ' ';
    1266         [ +  - ]:          5 :     description_append(desc, limit);
    1267                 :          5 :     return desc;
    1268                 :            : }
    1269                 :            : 
    1270                 :       1336 : QueryWildcard::QueryWildcard(const std::string &pattern_,
    1271                 :            :                              Xapian::termcount max_expansion_,
    1272                 :            :                              int flags_,
    1273                 :            :                              Query::op combiner_)
    1274                 :            :     : pattern(pattern_),
    1275                 :            :       max_expansion(max_expansion_),
    1276                 :            :       flags(flags_),
    1277 [ +  - ][ +  - ]:       1336 :       combiner(combiner_)
                 [ +  - ]
    1278                 :            : {
    1279         [ +  + ]:       1336 :     if ((flags & ~Query::WILDCARD_LIMIT_MASK_) == 0) {
    1280                 :       1252 :         head = min_len = pattern.size();
    1281                 :       1252 :         max_len = numeric_limits<decltype(max_len)>::max();
    1282         [ +  - ]:       1252 :         prefix = pattern;
    1283                 :       1336 :         return;
    1284                 :            :     }
    1285                 :            : 
    1286                 :         84 :     size_t i = 0;
    1287         [ +  + ]:        187 :     while (i != pattern.size()) {
    1288                 :            :         // Check for characters with special meaning.
    1289         [ +  - ]:        180 :         switch (pattern[i]) {
              [ +  +  + ]
    1290                 :            :             case '*':
    1291         [ +  + ]:         55 :                 if (flags & Query::WILDCARD_PATTERN_MULTI)
    1292                 :         48 :                     goto found_special;
    1293                 :          7 :                 break;
    1294                 :            :             case '?':
    1295         [ +  + ]:         36 :                 if (flags & Query::WILDCARD_PATTERN_SINGLE)
    1296                 :         29 :                     goto found_special;
    1297                 :          7 :                 break;
    1298                 :            :         }
    1299 [ +  - ][ +  - ]:        103 :         prefix += pattern[i];
    1300                 :        103 :         ++i;
    1301                 :        103 :         head = i;
    1302                 :            :     }
    1303                 :            : found_special:
    1304                 :            : 
    1305                 :         84 :     min_len = max_len = prefix.size();
    1306                 :            : 
    1307                 :         84 :     tail = i;
    1308                 :         84 :     bool had_qm = false, had_star = false;
    1309         [ +  + ]:        314 :     while (i != pattern.size()) {
    1310         [ +  - ]:        230 :         switch (pattern[i]) {
              [ +  +  + ]
    1311                 :            :             default:
    1312                 :            : default_case:
    1313 [ +  - ][ +  - ]:        127 :                 suffix += pattern[i];
    1314                 :        127 :                 ++min_len;
    1315                 :        127 :                 ++max_len;
    1316                 :        127 :                 break;
    1317                 :            : 
    1318                 :            :             case '*':
    1319         [ -  + ]:         59 :                 if (!(flags & Query::WILDCARD_PATTERN_MULTI))
    1320                 :          0 :                     goto default_case;
    1321                 :            :                 // Matches zero or more characters.
    1322                 :         59 :                 had_star = true;
    1323                 :         59 :                 tail = i + 1;
    1324         [ +  + ]:         59 :                 if (!suffix.empty()) {
    1325                 :          9 :                     check_pattern = true;
    1326         [ +  - ]:          9 :                     suffix.clear();
    1327                 :            :                 }
    1328                 :         59 :                 break;
    1329                 :            : 
    1330                 :            :             case '?':
    1331         [ -  + ]:         44 :                 if (!(flags & Query::WILDCARD_PATTERN_SINGLE))
    1332                 :          0 :                     goto default_case;
    1333                 :            :                 // Matches exactly one character.
    1334                 :         44 :                 tail = i + 1;
    1335         [ +  + ]:         44 :                 if (!suffix.empty()) {
    1336                 :          2 :                     check_pattern = true;
    1337         [ +  - ]:          2 :                     suffix.clear();
    1338                 :            :                 }
    1339                 :            :                 // `?` matches one Unicode character, which is 1-4 bytes in
    1340                 :            :                 // UTF-8, so we have to actually check the pattern if there's
    1341                 :            :                 // more than one `?` in it.
    1342         [ +  + ]:         44 :                 if (had_qm) {
    1343                 :         13 :                     check_pattern = true;
    1344                 :            :                 }
    1345                 :         44 :                 had_qm = true;
    1346                 :         44 :                 ++min_len;
    1347                 :         44 :                 max_len += MAX_UTF_8_CHARACTER_LENGTH;
    1348                 :         44 :                 break;
    1349                 :            :         }
    1350                 :            : 
    1351                 :        230 :         ++i;
    1352                 :            :     }
    1353                 :            : 
    1354         [ +  + ]:         84 :     if (had_star) {
    1355                 :         52 :         max_len = numeric_limits<decltype(max_len)>::max();
    1356                 :            :     } else {
    1357                 :            :         // If the pattern only contains `?` wildcards we'll need to check it
    1358                 :            :         // since `?` matches one Unicode character, which is 1-4 bytes in
    1359                 :            :         // UTF-8.  FIXME: We can avoid this if there's only one `?` wildcard
    1360                 :            :         // and the candidate is min_len bytes long.
    1361                 :         32 :         check_pattern = true;
    1362                 :            :     }
    1363                 :            : }
    1364                 :            : 
    1365                 :            : bool
    1366                 :        222 : QueryWildcard::test_wildcard_(const string& candidate, size_t o, size_t p,
    1367                 :            :                               size_t i) const
    1368                 :            : {
    1369                 :            :     // FIXME: Optimisation potential here.  We could compile the pattern to a
    1370                 :            :     // regex, or other tricks like calculating the min length needed after each
    1371                 :            :     // position that we test with this method - e.g. for foo*bar*x*baz there
    1372                 :            :     // must be at least 7 bytes after a position or there's no point testing if
    1373                 :            :     // "bar" matches there.
    1374         [ +  + ]:        384 :     for ( ; i != tail; ++i) {
    1375 [ +  + ][ +  + ]:        342 :         if ((flags & Query::WILDCARD_PATTERN_MULTI) && pattern[i] == '*') {
                 [ +  + ]
    1376         [ +  + ]:         35 :             if (++i == tail) {
    1377                 :            :                 // '*' at end of variable part is easy!
    1378                 :         10 :                 return true;
    1379                 :            :             }
    1380         [ +  + ]:        155 :             for (size_t test_o = o; test_o <= p; ++test_o) {
    1381         [ +  + ]:        140 :                 if (test_wildcard_(candidate, test_o, p, i))
    1382                 :         10 :                     return true;
    1383                 :            :             }
    1384                 :         15 :             return false;
    1385                 :            :         }
    1386         [ +  + ]:        307 :         if (o == p) return false;
    1387 [ +  + ][ +  - ]:        277 :         if ((flags & Query::WILDCARD_PATTERN_SINGLE) && pattern[i] == '?') {
                 [ +  + ]
    1388                 :         57 :             unsigned char b = candidate[o];
    1389         [ +  + ]:         57 :             if (b < 0xc0) {
    1390                 :         27 :                 ++o;
    1391                 :         27 :                 continue;
    1392                 :            :             }
    1393                 :            :             unsigned seqlen;
    1394         [ +  + ]:         30 :             if (b < 0xe0) {
    1395                 :         10 :                 seqlen = 2;
    1396         [ +  + ]:         20 :             } else if (b < 0xf0) {
    1397                 :         10 :                 seqlen = 3;
    1398                 :            :             } else {
    1399                 :         10 :                 seqlen = 4;
    1400                 :            :             }
    1401         [ -  + ]:         30 :             if (rare(p - o < seqlen)) return false;
    1402                 :         30 :             o += seqlen;
    1403                 :         30 :             continue;
    1404                 :            :         }
    1405                 :            : 
    1406         [ +  + ]:        220 :         if (pattern[i] != candidate[o]) return false;
    1407                 :        105 :         ++o;
    1408                 :            :     }
    1409                 :         42 :     return (o == p);
    1410                 :            : }
    1411                 :            : 
    1412                 :            : bool
    1413                 :        969 : QueryWildcard::test_prefix_known(const string& candidate) const
    1414                 :            : {
    1415         [ +  + ]:        969 :     if (candidate.size() < min_len) return false;
    1416         [ -  + ]:        954 :     if (candidate.size() > max_len) return false;
    1417         [ +  + ]:        954 :     if (!endswith(candidate, suffix)) return false;
    1418                 :            : 
    1419         [ +  + ]:        939 :     if (!check_pattern) return true;
    1420                 :            : 
    1421                 :            :     return test_wildcard_(candidate, prefix.size(),
    1422                 :         82 :                           candidate.size() - suffix.size(),
    1423                 :         82 :                           head);
    1424                 :            : }
    1425                 :            : 
    1426                 :            : PostList*
    1427                 :        235 : QueryWildcard::postlist(QueryOptimiser * qopt, double factor) const
    1428                 :            : {
    1429                 :            :     LOGCALL(QUERY, PostList*, "QueryWildcard::postlist", qopt | factor);
    1430                 :        235 :     Query::op op = combiner;
    1431 [ +  + ][ +  - ]:        235 :     if (factor == 0.0 || op == Query::OP_SYNONYM) {
    1432         [ +  + ]:        235 :         if (factor == 0.0) {
    1433                 :            :             // If we have a factor of 0, we don't care about the weights, so
    1434                 :            :             // we're just like a normal OR query.
    1435                 :         24 :             op = Query::OP_OR;
    1436                 :            :         }
    1437                 :            : 
    1438                 :        235 :         bool old_in_synonym = qopt->in_synonym;
    1439         [ +  + ]:        235 :         if (!old_in_synonym) {
    1440                 :        219 :             qopt->in_synonym = (op == Query::OP_SYNONYM);
    1441                 :            :         }
    1442                 :            : 
    1443         [ +  - ]:        235 :         BoolOrContext ctx(qopt, 0);
    1444         [ +  + ]:        235 :         ctx.expand_wildcard(this, 0.0);
    1445                 :            : 
    1446         [ +  + ]:        204 :         if (op == Query::OP_SYNONYM) {
    1447                 :        180 :             qopt->inc_total_subqs();
    1448                 :            :         }
    1449                 :            : 
    1450                 :        204 :         qopt->in_synonym = old_in_synonym;
    1451                 :            : 
    1452         [ +  + ]:        204 :         if (ctx.empty())
    1453                 :         54 :             RETURN(NULL);
    1454                 :            : 
    1455         [ +  - ]:        150 :         PostList * pl = ctx.postlist();
    1456         [ +  + ]:        150 :         if (op != Query::OP_SYNONYM)
    1457                 :         15 :             RETURN(pl);
    1458                 :            : 
    1459                 :            :         // We build an OP_OR tree for OP_SYNONYM and then wrap it in a
    1460                 :            :         // SynonymPostList, which supplies the weights.
    1461                 :            :         //
    1462                 :            :         // We know the subqueries from a wildcard expansion are wdf-disjoint
    1463                 :            :         // (i.e. each wdf from the document contributes at most itself to the
    1464                 :            :         // wdf of the subquery).
    1465         [ +  - ]:        235 :         RETURN(qopt->make_synonym_postlist(pl, factor, true));
    1466                 :            :     }
    1467                 :            : 
    1468         [ #  # ]:          0 :     OrContext ctx(qopt, 0);
    1469         [ #  # ]:          0 :     ctx.expand_wildcard(this, factor);
    1470                 :            : 
    1471                 :          0 :     qopt->set_total_subqs(qopt->get_total_subqs() + ctx.size());
    1472                 :            : 
    1473         [ #  # ]:          0 :     if (ctx.empty())
    1474                 :          0 :         RETURN(NULL);
    1475                 :            : 
    1476         [ #  # ]:          0 :     if (op == Query::OP_MAX)
    1477         [ #  # ]:          0 :         RETURN(ctx.postlist_max());
    1478                 :            : 
    1479         [ #  # ]:        204 :     RETURN(ctx.postlist());
    1480                 :            : }
    1481                 :            : 
    1482                 :            : termcount
    1483                 :        211 : QueryWildcard::get_length() const XAPIAN_NOEXCEPT
    1484                 :            : {
    1485                 :            :     // We currently assume wqf is 1 for calculating the synonym's weight
    1486                 :            :     // since conceptually the synonym is one "virtual" term.  If we were
    1487                 :            :     // to combine multiple occurrences of the same synonym expansion into
    1488                 :            :     // a single instance with wqf set, we would want to track the wqf.
    1489                 :        211 :     return 1;
    1490                 :            : }
    1491                 :            : 
    1492                 :            : void
    1493                 :         68 : QueryWildcard::serialise(string & result) const
    1494                 :            : {
    1495                 :         68 :     result += static_cast<char>(0x0b);
    1496         [ +  - ]:         68 :     result += encode_length(max_expansion);
    1497                 :         68 :     result += static_cast<unsigned char>(flags);
    1498                 :         68 :     result += static_cast<unsigned char>(combiner);
    1499         [ +  - ]:         68 :     result += encode_length(pattern.size());
    1500                 :         68 :     result += pattern;
    1501                 :         68 : }
    1502                 :            : 
    1503                 :            : Query::op
    1504                 :        685 : QueryWildcard::get_type() const XAPIAN_NOEXCEPT
    1505                 :            : {
    1506                 :        685 :     return Query::OP_WILDCARD;
    1507                 :            : }
    1508                 :            : 
    1509                 :            : string
    1510                 :        547 : QueryWildcard::get_description() const
    1511                 :            : {
    1512         [ +  - ]:        547 :     string desc = "WILDCARD ";
    1513   [ +  -  +  - ]:        547 :     switch (combiner) {
    1514                 :            :         case Query::OP_SYNONYM:
    1515         [ +  - ]:        507 :             desc += "SYNONYM ";
    1516                 :        507 :             break;
    1517                 :            :         case Query::OP_MAX:
    1518         [ #  # ]:          0 :             desc += "MAX ";
    1519                 :          0 :             break;
    1520                 :            :         case Query::OP_OR:
    1521         [ +  - ]:         40 :             desc += "OR ";
    1522                 :         40 :             break;
    1523                 :            :         default:
    1524         [ #  # ]:          0 :             desc += "BAD ";
    1525                 :          0 :             break;
    1526                 :            :     }
    1527         [ +  - ]:        547 :     description_append(desc, pattern);
    1528                 :        547 :     return desc;
    1529                 :            : }
    1530                 :            : 
    1531                 :            : int
    1532                 :       4159 : QueryEditDistance::test(const string& candidate) const
    1533                 :            : {
    1534                 :       4159 :     int threshold = get_threshold();
    1535                 :       4159 :     int edist = edcalc(candidate, threshold);
    1536         [ +  + ]:       4159 :     return edist <= threshold ? edist + 1 : 0;
    1537                 :            : }
    1538                 :            : 
    1539                 :            : PostList*
    1540                 :        133 : QueryEditDistance::postlist(QueryOptimiser * qopt, double factor) const
    1541                 :            : {
    1542                 :            :     LOGCALL(QUERY, PostList*, "QueryEditDistance::postlist", qopt | factor);
    1543                 :        133 :     Query::op op = combiner;
    1544 [ +  + ][ +  - ]:        133 :     if (factor == 0.0 || op == Query::OP_SYNONYM) {
    1545         [ +  + ]:        133 :         if (factor == 0.0) {
    1546                 :            :             // If we have a factor of 0, we don't care about the weights, so
    1547                 :            :             // we're just like a normal OR query.
    1548                 :          8 :             op = Query::OP_OR;
    1549                 :            :         }
    1550                 :            : 
    1551                 :        133 :         bool old_in_synonym = qopt->in_synonym;
    1552         [ +  + ]:        133 :         if (!old_in_synonym) {
    1553                 :        125 :             qopt->in_synonym = (op == Query::OP_SYNONYM);
    1554                 :            :         }
    1555                 :            : 
    1556         [ +  - ]:        133 :         BoolOrContext ctx(qopt, 0);
    1557         [ +  + ]:        133 :         ctx.expand_edit_distance(this, 0.0);
    1558                 :            : 
    1559         [ +  + ]:        112 :         if (op == Query::OP_SYNONYM) {
    1560                 :        104 :             qopt->inc_total_subqs();
    1561                 :            :         }
    1562                 :            : 
    1563                 :        112 :         qopt->in_synonym = old_in_synonym;
    1564                 :            : 
    1565         [ +  + ]:        112 :         if (ctx.empty())
    1566                 :         31 :             RETURN(NULL);
    1567                 :            : 
    1568         [ +  - ]:         81 :         PostList * pl = ctx.postlist();
    1569         [ +  + ]:         81 :         if (op != Query::OP_SYNONYM)
    1570                 :          6 :             RETURN(pl);
    1571                 :            : 
    1572                 :            :         // We build an OP_OR tree for OP_SYNONYM and then wrap it in a
    1573                 :            :         // SynonymPostList, which supplies the weights.
    1574                 :            :         //
    1575                 :            :         // We know the subqueries from an edit distance expansion are
    1576                 :            :         // wdf-disjoint (i.e. each wdf from the document contributes at most
    1577                 :            :         // itself to the wdf of the subquery).
    1578         [ +  - ]:        133 :         RETURN(qopt->make_synonym_postlist(pl, factor, true));
    1579                 :            :     }
    1580                 :            : 
    1581         [ #  # ]:          0 :     OrContext ctx(qopt, 0);
    1582         [ #  # ]:          0 :     ctx.expand_edit_distance(this, factor);
    1583                 :            : 
    1584                 :          0 :     qopt->set_total_subqs(qopt->get_total_subqs() + ctx.size());
    1585                 :            : 
    1586         [ #  # ]:          0 :     if (ctx.empty())
    1587                 :          0 :         RETURN(NULL);
    1588                 :            : 
    1589         [ #  # ]:          0 :     if (op == Query::OP_MAX)
    1590         [ #  # ]:          0 :         RETURN(ctx.postlist_max());
    1591                 :            : 
    1592         [ #  # ]:        112 :     RETURN(ctx.postlist());
    1593                 :            : }
    1594                 :            : 
    1595                 :            : termcount
    1596                 :        118 : QueryEditDistance::get_length() const XAPIAN_NOEXCEPT
    1597                 :            : {
    1598                 :            :     // We currently assume wqf is 1 for calculating the synonym's weight
    1599                 :            :     // since conceptually the synonym is one "virtual" term.  If we were
    1600                 :            :     // to combine multiple occurrences of the same synonym expansion into
    1601                 :            :     // a single instance with wqf set, we would want to track the wqf.
    1602                 :        118 :     return 1;
    1603                 :            : }
    1604                 :            : 
    1605                 :            : void
    1606                 :         40 : QueryEditDistance::serialise(string & result) const
    1607                 :            : {
    1608                 :         40 :     result += static_cast<char>(0x0a);
    1609         [ +  - ]:         40 :     result += encode_length(max_expansion);
    1610                 :         40 :     result += static_cast<unsigned char>(flags);
    1611                 :         40 :     result += static_cast<unsigned char>(combiner);
    1612         [ +  - ]:         40 :     result += encode_length(edit_distance);
    1613         [ +  - ]:         40 :     result += encode_length(fixed_prefix_len);
    1614         [ +  - ]:         40 :     result += encode_length(pattern.size());
    1615                 :         40 :     result += pattern;
    1616                 :         40 : }
    1617                 :            : 
    1618                 :            : Query::op
    1619                 :        119 : QueryEditDistance::get_type() const XAPIAN_NOEXCEPT
    1620                 :            : {
    1621                 :        119 :     return Query::OP_EDIT_DISTANCE;
    1622                 :            : }
    1623                 :            : 
    1624                 :            : string
    1625                 :         75 : QueryEditDistance::get_description() const
    1626                 :            : {
    1627         [ +  - ]:         75 :     string desc = "EDIT_DISTANCE ";
    1628   [ +  -  -  - ]:         75 :     switch (combiner) {
    1629                 :            :         case Query::OP_SYNONYM:
    1630         [ +  - ]:         75 :             desc += "SYNONYM ";
    1631                 :         75 :             break;
    1632                 :            :         case Query::OP_MAX:
    1633         [ #  # ]:          0 :             desc += "MAX ";
    1634                 :          0 :             break;
    1635                 :            :         case Query::OP_OR:
    1636         [ #  # ]:          0 :             desc += "OR ";
    1637                 :          0 :             break;
    1638                 :            :         default:
    1639         [ #  # ]:          0 :             desc += "BAD ";
    1640                 :          0 :             break;
    1641                 :            :     }
    1642         [ +  - ]:         75 :     description_append(desc, pattern);
    1643         [ +  - ]:         75 :     desc += '~';
    1644 [ +  - ][ +  - ]:         75 :     desc += str(edit_distance);
    1645         [ +  + ]:         75 :     if (fixed_prefix_len) {
    1646         [ +  - ]:          5 :         desc += " fixed_prefix_len=";
    1647 [ +  - ][ +  - ]:          5 :         desc += str(fixed_prefix_len);
    1648                 :            :     }
    1649                 :         75 :     return desc;
    1650                 :            : }
    1651                 :            : 
    1652                 :            : Xapian::termcount
    1653                 :       3384 : QueryBranch::get_length() const XAPIAN_NOEXCEPT
    1654                 :            : {
    1655                 :            :     // Sum results from all subqueries.
    1656                 :       3384 :     Xapian::termcount result = 0;
    1657                 :       3384 :     QueryVector::const_iterator i;
    1658         [ +  + ]:      14532 :     for (i = subqueries.begin(); i != subqueries.end(); ++i) {
    1659                 :            :         // MatchNothing subqueries should have been removed by done(), but we
    1660                 :            :         // can't use Assert in a XAPIAN_NOEXCEPT function.  But we'll get a
    1661                 :            :         // segfault anyway.
    1662                 :      11148 :         result += (*i).internal->get_length();
    1663                 :            :     }
    1664                 :       3384 :     return result;
    1665                 :            : }
    1666                 :            : 
    1667                 :            : #define MULTIWAY(X) static_cast<unsigned char>(0x80 | (X) << 3)
    1668                 :            : #define MISC(X) static_cast<unsigned char>(X)
    1669                 :            : void
    1670                 :        842 : QueryBranch::serialise_(string & result, Xapian::termcount parameter) const
    1671                 :            : {
    1672                 :            :     static const unsigned char first_byte[] = {
    1673                 :            :         MULTIWAY(0),    // OP_AND
    1674                 :            :         MULTIWAY(1),    // OP_OR
    1675                 :            :         MULTIWAY(2),    // OP_AND_NOT
    1676                 :            :         MULTIWAY(3),    // OP_XOR
    1677                 :            :         MULTIWAY(4),    // OP_AND_MAYBE
    1678                 :            :         MULTIWAY(5),    // OP_FILTER
    1679                 :            :         MULTIWAY(14),   // OP_NEAR
    1680                 :            :         MULTIWAY(15),   // OP_PHRASE
    1681                 :            :         0,              // OP_VALUE_RANGE
    1682                 :            :         MISC(3),        // OP_SCALE_WEIGHT
    1683                 :            :         MULTIWAY(13),   // OP_ELITE_SET
    1684                 :            :         0,              // OP_VALUE_GE
    1685                 :            :         0,              // OP_VALUE_LE
    1686                 :            :         MULTIWAY(6),    // OP_SYNONYM
    1687                 :            :         MULTIWAY(7)     // OP_MAX
    1688                 :            :     };
    1689         [ +  - ]:        842 :     Xapian::Query::op op_ = get_op();
    1690                 :            :     AssertRel(size_t(op_),<,sizeof(first_byte));
    1691                 :        842 :     unsigned char ch = first_byte[op_];
    1692         [ +  - ]:        842 :     if (ch & 0x80) {
    1693                 :            :         // Multi-way operator.
    1694 [ +  - ][ +  + ]:        842 :         if (subqueries.size() < 8)
    1695         [ +  - ]:        796 :             ch |= subqueries.size();
    1696         [ +  - ]:        842 :         result += ch;
    1697 [ +  - ][ +  + ]:        842 :         if (subqueries.size() >= 8)
    1698 [ +  - ][ +  - ]:         46 :             result += encode_length(subqueries.size() - 8);
                 [ +  - ]
    1699         [ +  + ]:        842 :         if (ch >= MULTIWAY(13))
    1700 [ +  - ][ +  - ]:        231 :             result += encode_length(parameter);
    1701                 :            :     } else {
    1702         [ #  # ]:          0 :         result += ch;
    1703                 :            :     }
    1704                 :            : 
    1705                 :        842 :     QueryVector::const_iterator i;
    1706 [ +  - ][ +  - ]:       3773 :     for (i = subqueries.begin(); i != subqueries.end(); ++i) {
         [ +  - ][ +  + ]
    1707                 :            :         // MatchNothing subqueries should have been removed by done().
    1708                 :            :         Assert((*i).internal.get());
    1709 [ +  - ][ +  + ]:       2933 :         (*i).internal->serialise(result);
    1710                 :            :     }
    1711                 :            : 
    1712                 :            :     // For OP_NEAR, OP_PHRASE, and OP_ELITE_SET, the window/set size gets
    1713                 :            :     // appended next by an overloaded serialise() method in the subclass.
    1714                 :        840 : }
    1715                 :            : 
    1716                 :            : void
    1717                 :        611 : QueryBranch::serialise(string & result) const
    1718                 :            : {
    1719                 :        611 :     QueryBranch::serialise_(result);
    1720                 :        609 : }
    1721                 :            : 
    1722                 :            : void
    1723                 :         58 : QueryNear::serialise(string & result) const
    1724                 :            : {
    1725                 :            :     // FIXME: window - subqueries.size() ?
    1726                 :         58 :     QueryBranch::serialise_(result, window);
    1727                 :         58 : }
    1728                 :            : 
    1729                 :            : void
    1730                 :        117 : QueryPhrase::serialise(string & result) const
    1731                 :            : {
    1732                 :            :     // FIXME: window - subqueries.size() ?
    1733                 :        117 :     QueryBranch::serialise_(result, window);
    1734                 :        117 : }
    1735                 :            : 
    1736                 :            : void
    1737                 :         56 : QueryEliteSet::serialise(string & result) const
    1738                 :            : {
    1739                 :            :     // FIXME: set_size - subqueries.size() ?
    1740                 :         56 :     QueryBranch::serialise_(result, set_size);
    1741                 :         56 : }
    1742                 :            : 
    1743                 :            : void
    1744                 :     237973 : QueryBranch::gather_terms(void * void_terms) const
    1745                 :            : {
    1746                 :            :     // Gather results from all subqueries.
    1747                 :     237973 :     QueryVector::const_iterator i;
    1748 [ +  - ][ +  - ]:     723091 :     for (i = subqueries.begin(); i != subqueries.end(); ++i) {
         [ +  - ][ +  + ]
    1749                 :            :         // MatchNothing subqueries should have been removed by done().
    1750                 :            :         Assert((*i).internal.get());
    1751 [ +  - ][ +  - ]:     485118 :         (*i).internal->gather_terms(void_terms);
    1752                 :            :     }
    1753                 :     237973 : }
    1754                 :            : 
    1755                 :            : void
    1756                 :        660 : QueryBranch::do_bool_or_like(BoolOrContext& ctx, QueryOptimiser* qopt) const
    1757                 :            : {
    1758                 :            :     LOGCALL_VOID(MATCH, "QueryBranch::do_bool_or_like", ctx | qopt);
    1759                 :            : 
    1760                 :            :     // FIXME: we could optimise by merging OP_ELITE_SET and OP_OR like we do
    1761                 :            :     // for AND-like operations.
    1762                 :            : 
    1763                 :            :     // OP_SYNONYM with a single subquery is only simplified by
    1764                 :            :     // QuerySynonym::done() if the single subquery is a term or MatchAll.
    1765                 :            :     Assert(subqueries.size() >= 2 || get_op() == Query::OP_SYNONYM);
    1766                 :            : 
    1767 [ +  - ][ +  - ]:       2018 :     for (auto q : subqueries) {
         [ +  - ][ +  - ]
                 [ +  + ]
    1768                 :            :         // MatchNothing subqueries should have been removed by done().
    1769                 :            :         Assert(q.internal.get());
    1770         [ +  - ]:       1358 :         q.internal->postlist_sub_bool_or_like(ctx, qopt);
    1771                 :       1358 :     }
    1772                 :        660 : }
    1773                 :            : 
    1774                 :            : void
    1775                 :     140583 : QueryBranch::do_or_like(OrContext& ctx, QueryOptimiser * qopt, double factor,
    1776                 :            :                         Xapian::termcount elite_set_size, size_t first) const
    1777                 :            : {
    1778                 :            :     LOGCALL_VOID(MATCH, "QueryBranch::do_or_like", ctx | qopt | factor | elite_set_size);
    1779                 :            : 
    1780                 :            :     // FIXME: we could optimise by merging OP_ELITE_SET and OP_OR like we do
    1781                 :            :     // for AND-like operations.
    1782                 :            : 
    1783                 :            :     // OP_SYNONYM with a single subquery is only simplified by
    1784                 :            :     // QuerySynonym::done() if the single subquery is a term or MatchAll.
    1785                 :            :     Assert(subqueries.size() >= 2 || get_op() == Query::OP_SYNONYM);
    1786                 :            : 
    1787                 :     140583 :     size_t size_before = ctx.size();
    1788                 :     140583 :     QueryVector::const_iterator q;
    1789 [ +  - ][ +  - ]:     426121 :     for (q = subqueries.begin() + first; q != subqueries.end(); ++q) {
         [ +  - ][ +  - ]
                 [ +  + ]
    1790                 :            :         // MatchNothing subqueries should have been removed by done().
    1791                 :            :         Assert((*q).internal.get());
    1792 [ +  - ][ +  - ]:     285538 :         (*q).internal->postlist_sub_or_like(ctx, qopt, factor);
    1793                 :            :     }
    1794                 :            : 
    1795                 :     140583 :     size_t out_of = ctx.size() - size_before;
    1796 [ +  + ][ +  + ]:     140583 :     if (elite_set_size && elite_set_size < out_of) {
    1797         [ +  - ]:        208 :         ctx.select_elite_set(elite_set_size, out_of);
    1798                 :            :         // FIXME: This isn't quite right as we flatten ORs under the ELITE_SET
    1799                 :            :         // and then pick from amongst all the subqueries.  Consider:
    1800                 :            :         //
    1801                 :            :         // Query subqs[] = {q1 | q2, q3 | q4};
    1802                 :            :         // Query q(OP_ELITE_SET, begin(subqs), end(subqs), 1);
    1803                 :            :         //
    1804                 :            :         // Here q should be either q1 | q2 or q3 | q4, but actually it'll be
    1805                 :            :         // just one of q1 or q2 or q3 or q4 (assuming those aren't themselves
    1806                 :            :         // OP_OR or OP_OR-like queries).
    1807                 :            :     }
    1808                 :     140583 : }
    1809                 :            : 
    1810                 :            : PostList *
    1811                 :        660 : QueryBranch::do_synonym(QueryOptimiser * qopt, double factor) const
    1812                 :            : {
    1813                 :            :     LOGCALL(MATCH, PostList *, "QueryBranch::do_synonym", qopt | factor);
    1814 [ +  - ][ +  - ]:        660 :     BoolOrContext ctx(qopt, subqueries.size());
    1815         [ +  + ]:        660 :     if (factor == 0.0) {
    1816                 :            :         // If we have a factor of 0, we don't care about the weights, so
    1817                 :            :         // we're just like a normal OR query.
    1818         [ +  - ]:         48 :         do_bool_or_like(ctx, qopt);
    1819         [ +  - ]:         48 :         return ctx.postlist();
    1820                 :            :     }
    1821                 :            : 
    1822                 :        612 :     bool old_in_synonym = qopt->in_synonym;
    1823                 :            :     Assert(!old_in_synonym);
    1824                 :        612 :     qopt->in_synonym = true;
    1825         [ +  - ]:        612 :     do_bool_or_like(ctx, qopt);
    1826         [ +  - ]:        612 :     PostList * pl = ctx.postlist();
    1827         [ +  + ]:        612 :     if (!pl) return NULL;
    1828                 :        611 :     qopt->in_synonym = old_in_synonym;
    1829                 :            : 
    1830                 :        611 :     bool wdf_disjoint = false;
    1831                 :            :     Assert(!subqueries.empty());
    1832         [ +  - ]:        611 :     auto type = subqueries.front().get_type();
    1833         [ +  + ]:        611 :     if (type == Query::OP_WILDCARD) {
    1834                 :            :         // Detect common easy case where all subqueries are OP_WILDCARD whose
    1835                 :            :         // constant prefixes form a prefix-free set.
    1836                 :          7 :         wdf_disjoint = true;
    1837                 :          7 :         vector<string> prefixes;
    1838 [ +  - ][ +  - ]:         21 :         for (auto&& q : subqueries) {
         [ +  - ][ +  - ]
                 [ +  + ]
    1839         [ -  + ]:         14 :             if (q.get_type() != Query::OP_WILDCARD) {
    1840                 :          0 :                 wdf_disjoint = false;
    1841                 :          0 :                 break;
    1842                 :            :             }
    1843                 :         14 :             auto qw = static_cast<const QueryWildcard*>(q.internal.get());
    1844 [ +  - ][ +  - ]:         14 :             prefixes.push_back(qw->get_fixed_prefix());
                 [ +  - ]
    1845                 :         14 :         }
    1846                 :            : 
    1847         [ +  - ]:          7 :         if (wdf_disjoint) {
    1848         [ +  - ]:          7 :             sort(prefixes.begin(), prefixes.end());
    1849                 :          7 :             const string* prev = nullptr;
    1850         [ +  + ]:         21 :             for (const auto& i : prefixes) {
    1851         [ +  + ]:         14 :                 if (prev) {
    1852         [ -  + ]:          7 :                     if (startswith(i, *prev)) {
    1853                 :          0 :                         wdf_disjoint = false;
    1854                 :          0 :                         break;
    1855                 :            :                     }
    1856                 :            :                 }
    1857                 :         14 :                 prev = &i;
    1858                 :            :             }
    1859                 :          7 :         }
    1860         [ +  + ]:        604 :     } else if (type == Query::LEAF_TERM) {
    1861                 :            :         // Detect common easy case where all subqueries are terms, none of
    1862                 :            :         // which are the same.
    1863                 :        568 :         wdf_disjoint = true;
    1864         [ +  - ]:        568 :         unordered_set<string> terms;
    1865 [ +  - ][ +  - ]:       1598 :         for (auto&& q : subqueries) {
         [ +  - ][ +  - ]
                 [ +  + ]
    1866         [ +  + ]:       1174 :             if (q.get_type() != Query::LEAF_TERM) {
    1867                 :        144 :                 wdf_disjoint = false;
    1868                 :        144 :                 break;
    1869                 :            :             }
    1870                 :       1030 :             auto qt = static_cast<const QueryTerm*>(q.internal.get());
    1871 [ +  - ][ -  + ]:       1030 :             if (!terms.insert(qt->get_term()).second) {
    1872                 :          0 :                 wdf_disjoint = false;
    1873         [ +  + ]:       1174 :                 break;
    1874                 :            :             }
    1875                 :       1598 :         }
    1876                 :            :     }
    1877                 :            : 
    1878                 :            :     // We currently assume wqf is 1 for calculating the synonym's weight
    1879                 :            :     // since conceptually the synonym is one "virtual" term.  If we were
    1880                 :            :     // to combine multiple occurrences of the same synonym expansion into
    1881                 :            :     // a single instance with wqf set, we would want to track the wqf.
    1882                 :            : 
    1883                 :            :     // We build an OP_OR tree for OP_SYNONYM and then wrap it in a
    1884                 :            :     // SynonymPostList, which supplies the weights.
    1885         [ +  - ]:        660 :     RETURN(qopt->make_synonym_postlist(pl, factor, wdf_disjoint));
    1886                 :            : }
    1887                 :            : 
    1888                 :            : PostList *
    1889                 :          8 : QueryBranch::do_max(QueryOptimiser * qopt, double factor) const
    1890                 :            : {
    1891                 :            :     LOGCALL(MATCH, PostList *, "QueryBranch::do_max", qopt | factor);
    1892 [ +  - ][ +  - ]:          8 :     OrContext ctx(qopt, subqueries.size());
    1893         [ +  - ]:          8 :     do_or_like(ctx, qopt, factor);
    1894         [ -  + ]:          8 :     if (factor == 0.0) {
    1895                 :            :         // If we have a factor of 0, we don't care about the weights, so
    1896                 :            :         // we're just like a normal OR query.
    1897         [ #  # ]:          0 :         RETURN(ctx.postlist());
    1898                 :            :     }
    1899                 :            : 
    1900                 :            :     // We currently assume wqf is 1 for calculating the OP_MAX's weight
    1901                 :            :     // since conceptually the OP_MAX is one "virtual" term.  If we were
    1902                 :            :     // to combine multiple occurrences of the same OP_MAX expansion into
    1903                 :            :     // a single instance with wqf set, we would want to track the wqf.
    1904         [ +  - ]:          8 :     RETURN(ctx.postlist_max());
    1905                 :            : }
    1906                 :            : 
    1907                 :            : Xapian::Query::op
    1908                 :       2091 : QueryBranch::get_type() const XAPIAN_NOEXCEPT
    1909                 :            : {
    1910                 :       2091 :     return get_op();
    1911                 :            : }
    1912                 :            : 
    1913                 :            : size_t
    1914                 :        349 : QueryBranch::get_num_subqueries() const XAPIAN_NOEXCEPT
    1915                 :            : {
    1916                 :        349 :     return subqueries.size();
    1917                 :            : }
    1918                 :            : 
    1919                 :            : const Query
    1920                 :        848 : QueryBranch::get_subquery(size_t n) const
    1921                 :            : {
    1922                 :        848 :     return subqueries[n];
    1923                 :            : }
    1924                 :            : 
    1925                 :            : const string
    1926                 :       2965 : QueryBranch::get_description_helper(const char * op,
    1927                 :            :                                     Xapian::termcount parameter) const
    1928                 :            : {
    1929         [ +  - ]:       2965 :     string desc = "(";
    1930                 :       2965 :     QueryVector::const_iterator i;
    1931 [ +  - ][ +  - ]:      10726 :     for (i = subqueries.begin(); i != subqueries.end(); ++i) {
         [ +  - ][ +  + ]
    1932         [ +  + ]:       7761 :         if (desc.size() > 1) {
    1933         [ +  - ]:       4796 :             desc += op;
    1934         [ +  + ]:       4796 :             if (parameter) {
    1935 [ +  - ][ +  - ]:        843 :                 desc += str(parameter);
    1936         [ +  - ]:        843 :                 desc += ' ';
    1937                 :            :             }
    1938                 :            :         }
    1939                 :            :         Assert((*i).internal.get());
    1940                 :            :         // MatchNothing subqueries should have been removed by done(), and we
    1941                 :            :         // shouldn't get called before done() is, since that happens at the
    1942                 :            :         // end of the Xapian::Query constructor.
    1943 [ +  - ][ +  - ]:       7761 :         desc += (*i).internal->get_description();
                 [ +  - ]
    1944                 :            :     }
    1945         [ +  - ]:       2965 :     desc += ')';
    1946                 :       2965 :     return desc;
    1947                 :            : }
    1948                 :            : 
    1949                 :            : Query::Internal *
    1950                 :       1174 : QueryWindowed::done()
    1951                 :            : {
    1952                 :            :     // If window size not specified, default it.
    1953         [ +  + ]:       1174 :     if (window == 0)
    1954                 :        215 :         window = subqueries.size();
    1955                 :       1174 :     return QueryAndLike::done();
    1956                 :            : }
    1957                 :            : 
    1958                 :            : void
    1959                 :       1142 : QueryScaleWeight::gather_terms(void * void_terms) const
    1960                 :            : {
    1961                 :       1142 :     subquery.internal->gather_terms(void_terms);
    1962                 :       1142 : }
    1963                 :            : 
    1964                 :       8374 : void QueryTerm::serialise(string & result) const
    1965                 :            : {
    1966                 :       8374 :     size_t len = term.size();
    1967         [ +  + ]:       8374 :     if (len == 0) {
    1968 [ +  - ][ +  - ]:         10 :         if (wqf == 1 && pos == 0) {
    1969                 :            :             // Query::MatchAll
    1970                 :         10 :             result += '\x0f';
    1971                 :            :         } else {
    1972                 :            :             // Weird mutant versions of MatchAll
    1973                 :          0 :             result += '\x0e';
    1974         [ #  # ]:          0 :             result += encode_length(wqf);
    1975         [ #  # ]:         10 :             result += encode_length(pos);
    1976                 :            :         }
    1977         [ +  + ]:       8364 :     } else if (wqf == 1) {
    1978         [ +  + ]:       8358 :         if (pos == 0) {
    1979                 :            :             // Single occurrence free-text term without position set.
    1980         [ -  + ]:       7915 :             if (len >= 16) {
    1981                 :          0 :                 result += static_cast<char>(0x40 | 0x10);
    1982         [ #  # ]:          0 :                 result += encode_length(term.size() - 16);
    1983                 :            :             } else {
    1984                 :       7915 :                 result += static_cast<char>(0x40 | 0x10 | len);
    1985                 :            :             }
    1986                 :       7915 :             result += term;
    1987                 :            :         } else {
    1988                 :            :             // Single occurrence free-text term with position set.
    1989         [ -  + ]:        443 :             if (len >= 16) {
    1990                 :          0 :                 result += static_cast<char>(0x40 | 0x20);
    1991         [ #  # ]:          0 :                 result += encode_length(term.size() - 16);
    1992                 :            :             } else {
    1993                 :        443 :                 result += static_cast<char>(0x40 | 0x20 | len);
    1994                 :            :             }
    1995                 :        443 :             result += term;
    1996         [ +  - ]:       8358 :             result += encode_length(pos);
    1997                 :            :         }
    1998 [ -  + ][ #  # ]:          6 :     } else if (wqf > 1 || pos > 0) {
    1999                 :            :         // General case.
    2000         [ -  + ]:          6 :         if (len >= 16) {
    2001                 :          0 :             result += static_cast<char>(0x40 | 0x30);
    2002         [ #  # ]:          0 :             result += encode_length(term.size() - 16);
    2003         [ +  - ]:          6 :         } else if (len) {
    2004                 :          6 :             result += static_cast<char>(0x40 | 0x30 | len);
    2005                 :            :         }
    2006                 :          6 :         result += term;
    2007         [ +  - ]:          6 :         result += encode_length(wqf);
    2008         [ +  - ]:          6 :         result += encode_length(pos);
    2009                 :            :     } else {
    2010                 :            :         // Typical boolean term.
    2011                 :            :         AssertEq(wqf, 0);
    2012                 :            :         AssertEq(pos, 0);
    2013         [ #  # ]:          0 :         if (len >= 16) {
    2014                 :          0 :             result += static_cast<char>(0x40);
    2015         [ #  # ]:          0 :             result += encode_length(term.size() - 16);
    2016                 :            :         } else {
    2017                 :          0 :             result += static_cast<char>(0x40 | len);
    2018                 :            :         }
    2019                 :          0 :         result += term;
    2020                 :            :     }
    2021                 :       8374 : }
    2022                 :            : 
    2023                 :         45 : void QueryPostingSource::serialise(string & result) const
    2024                 :            : {
    2025                 :         45 :     result += static_cast<char>(0x0c);
    2026                 :            : 
    2027                 :         45 :     const string & n = source->name();
    2028 [ +  - ][ +  - ]:         45 :     result += encode_length(n.size());
    2029         [ +  - ]:         45 :     result += n;
    2030                 :            : 
    2031         [ +  + ]:         86 :     const string & s = source->serialise();
    2032 [ +  - ][ +  - ]:         41 :     result += encode_length(s.size());
    2033         [ +  - ]:         86 :     result += s;
    2034                 :         41 : }
    2035                 :            : 
    2036                 :        161 : void QueryScaleWeight::serialise(string & result) const
    2037                 :            : {
    2038                 :            :     Assert(subquery.internal.get());
    2039                 :        161 :     const string & s = serialise_double(scale_factor);
    2040         [ +  - ]:        161 :     result += '\x0d';
    2041         [ +  - ]:        161 :     result += s;
    2042         [ +  - ]:        161 :     subquery.internal->serialise(result);
    2043                 :        161 : }
    2044                 :            : 
    2045                 :            : struct is_matchnothing {
    2046                 :            :     bool operator()(const Xapian::Query & q) const {
    2047                 :            :         return q.internal.get() == NULL;
    2048                 :            :     }
    2049                 :            : };
    2050                 :            : 
    2051                 :            : void
    2052                 :       4075 : QueryAndLike::add_subquery(const Xapian::Query & subquery)
    2053                 :            : {
    2054                 :            :     // If the AndLike is already MatchNothing, do nothing.
    2055 [ +  - ][ +  + ]:       4075 :     if (subqueries.size() == 1 && subqueries[0].internal.get() == NULL)
         [ +  - ][ +  + ]
                 [ +  + ]
           [ +  +  #  # ]
    2056                 :       4075 :         return;
    2057                 :            :     // If we're adding MatchNothing, discard any previous subqueries.
    2058         [ +  + ]:       4071 :     if (subquery.internal.get() == NULL)
    2059                 :         54 :         subqueries.clear();
    2060                 :       4071 :     subqueries.push_back(subquery);
    2061                 :            : }
    2062                 :            : 
    2063                 :            : Query::Internal *
    2064                 :       1700 : QueryAndLike::done()
    2065                 :            : {
    2066                 :            :     // Empty AndLike gives MatchNothing.
    2067         [ -  + ]:       1700 :     if (subqueries.empty())
    2068                 :          0 :         return NULL;
    2069                 :            :     // We handle any subquery being MatchNothing in add_subquery() by leaving
    2070                 :            :     // a single MatchNothing subquery, and so this check results in AndLike
    2071                 :            :     // giving MatchNothing.
    2072         [ +  + ]:       1700 :     if (subqueries.size() == 1)
    2073                 :        132 :         return subqueries[0].internal.get();
    2074                 :       1568 :     return this;
    2075                 :            : }
    2076                 :            : 
    2077                 :            : PostList*
    2078                 :       1128 : QueryAndLike::postlist(QueryOptimiser * qopt, double factor) const
    2079                 :            : {
    2080                 :            :     LOGCALL(QUERY, PostList*, "QueryAndLike::postlist", qopt | factor);
    2081 [ +  - ][ +  - ]:       1128 :     AndContext ctx(qopt, subqueries.size());
    2082         [ +  - ]:       1128 :     (void)postlist_sub_and_like(ctx, qopt, factor);
    2083         [ +  - ]:       1128 :     RETURN(ctx.postlist());
    2084                 :            : }
    2085                 :            : 
    2086                 :            : bool
    2087                 :        432 : QueryAndLike::postlist_sub_and_like(AndContext& ctx, QueryOptimiser * qopt, double factor) const
    2088                 :            : {
    2089                 :        432 :     QueryVector::const_iterator i;
    2090 [ +  - ][ +  - ]:       1456 :     for (i = subqueries.begin(); i != subqueries.end(); ++i) {
         [ +  - ][ +  + ]
    2091                 :            :         // MatchNothing subqueries should have been removed by done().
    2092                 :            :         Assert((*i).internal.get());
    2093 [ +  - ][ +  - ]:       1028 :         if (!(*i).internal->postlist_sub_and_like(ctx, qopt, factor))
                 [ +  + ]
    2094                 :          4 :             return false;
    2095                 :            :     }
    2096                 :        432 :     return true;
    2097                 :            : }
    2098                 :            : 
    2099                 :            : void
    2100                 :    1296138 : QueryOrLike::add_subquery(const Xapian::Query & subquery)
    2101                 :            : {
    2102                 :            :     // Drop any subqueries which are MatchNothing.
    2103         [ +  + ]:    1296138 :     if (subquery.internal.get() != NULL)
    2104                 :    1296065 :         subqueries.push_back(subquery);
    2105                 :    1296138 : }
    2106                 :            : 
    2107                 :            : Query::Internal *
    2108                 :     568683 : QueryOrLike::done()
    2109                 :            : {
    2110                 :            :     // An empty OrLike gives MatchNothing.  Note that add_subquery() drops any
    2111                 :            :     // subqueries which are MatchNothing.
    2112         [ +  + ]:     568683 :     if (subqueries.empty())
    2113                 :         20 :         return NULL;
    2114         [ +  + ]:     568663 :     if (subqueries.size() == 1)
    2115                 :      10494 :         return subqueries[0].internal.get();
    2116                 :     558169 :     return this;
    2117                 :            : }
    2118                 :            : 
    2119                 :            : void
    2120                 :        447 : QueryAndNot::add_subquery(const Xapian::Query & subquery)
    2121                 :            : {
    2122         [ +  + ]:        447 :     if (!subqueries.empty()) {
    2123                 :            :         // We're adding the 2nd or subsequent subquery, so this subquery is
    2124                 :            :         // negated.
    2125         [ +  + ]:        222 :         if (subqueries[0].internal.get() == NULL) {
    2126                 :            :             // The left side is already MatchNothing so drop any right side.
    2127                 :            :             //
    2128                 :            :             // MatchNothing AND_NOT X == MatchNothing
    2129                 :          2 :             return;
    2130                 :            :         }
    2131         [ +  + ]:        220 :         if (subquery.internal.get() == NULL) {
    2132                 :            :             // Drop MatchNothing on the right of AndNot.
    2133                 :            :             //
    2134                 :            :             // X AND_NOT MatchNothing == X
    2135                 :          1 :             return;
    2136                 :            :         }
    2137         [ +  + ]:        219 :         if (subquery.get_type() == subquery.OP_SCALE_WEIGHT) {
    2138                 :            :             // Strip OP_SCALE_WEIGHT wrapping from queries on the right of
    2139                 :            :             // AndNot as no weight is taken from them.
    2140         [ +  - ]:          3 :             subqueries.push_back(subquery.get_subquery(0));
    2141                 :            :             // The Query constructor for OP_SCALE_WEIGHT constructor should
    2142                 :            :             // eliminate OP_SCALE_WEIGHT applied to MatchNothing.
    2143                 :            :             Assert(subquery.get_subquery(0).internal.get() != NULL);
    2144                 :          3 :             return;
    2145                 :            :         }
    2146                 :            :     }
    2147                 :        447 :     subqueries.push_back(subquery);
    2148                 :            : }
    2149                 :            : 
    2150                 :            : Query::Internal *
    2151                 :        225 : QueryAndNot::done()
    2152                 :            : {
    2153                 :            :     // Any MatchNothing right subqueries get discarded by add_subquery() - if
    2154                 :            :     // that leaves just the left subquery, return that.
    2155                 :            :     //
    2156                 :            :     // If left subquery is MatchNothing, then add_subquery() discards all right
    2157                 :            :     // subqueries, so this check also gives MatchNothing for this case.
    2158         [ +  + ]:        225 :     if (subqueries.size() == 1)
    2159                 :          6 :         return subqueries[0].internal.get();
    2160                 :        219 :     return this;
    2161                 :            : }
    2162                 :            : 
    2163                 :            : void
    2164                 :        257 : QueryAndMaybe::add_subquery(const Xapian::Query & subquery)
    2165                 :            : {
    2166                 :            :     // If the left side of AndMaybe is already MatchNothing, do nothing.
    2167 [ +  - ][ +  + ]:        257 :     if (subqueries.size() == 1 && subqueries[0].internal.get() == NULL)
         [ +  - ][ +  + ]
                 [ +  + ]
           [ +  +  #  # ]
    2168                 :        257 :         return;
    2169                 :            :     // Drop any 2nd or subsequent subqueries which are MatchNothing.
    2170 [ +  + ][ +  + ]:        255 :     if (subquery.internal.get() != NULL || subqueries.empty())
                 [ +  + ]
    2171                 :        254 :         subqueries.push_back(subquery);
    2172                 :            : }
    2173                 :            : 
    2174                 :            : Query::Internal *
    2175                 :        130 : QueryAndMaybe::done()
    2176                 :            : {
    2177                 :            :     // Any MatchNothing right subqueries get discarded by add_subquery() - if
    2178                 :            :     // that leaves just the left subquery, return that.
    2179                 :            :     //
    2180                 :            :     // If left subquery is MatchNothing, then add_subquery() discards all right
    2181                 :            :     // subqueries, so this check also gives MatchNothing for this case.
    2182         [ +  + ]:        130 :     if (subqueries.size() == 1)
    2183                 :          6 :         return subqueries[0].internal.get();
    2184                 :        124 :     return this;
    2185                 :            : }
    2186                 :            : 
    2187                 :            : PostList*
    2188                 :     140029 : QueryOr::postlist(QueryOptimiser * qopt, double factor) const
    2189                 :            : {
    2190                 :            :     LOGCALL(QUERY, PostList*, "QueryOr::postlist", qopt | factor);
    2191 [ +  - ][ +  - ]:     140029 :     OrContext ctx(qopt, subqueries.size());
    2192         [ +  - ]:     140029 :     do_or_like(ctx, qopt, factor);
    2193         [ +  - ]:     140029 :     RETURN(ctx.postlist());
    2194                 :            : }
    2195                 :            : 
    2196                 :            : void
    2197                 :        142 : QueryOr::postlist_sub_or_like(OrContext& ctx, QueryOptimiser * qopt, double factor) const
    2198                 :            : {
    2199                 :        142 :     do_or_like(ctx, qopt, factor);
    2200                 :        142 : }
    2201                 :            : 
    2202                 :            : PostList*
    2203                 :        136 : QueryAndNot::postlist(QueryOptimiser * qopt, double factor) const
    2204                 :            : {
    2205                 :            :     LOGCALL(QUERY, PostList*, "QueryAndNot::postlist", qopt | factor);
    2206                 :            :     // FIXME: Combine and-like side with and-like stuff above.
    2207 [ +  - ][ +  - ]:        136 :     unique_ptr<PostList> l(subqueries[0].internal->postlist(qopt, factor));
    2208         [ -  + ]:        136 :     if (!l.get()) {
    2209                 :          0 :         RETURN(NULL);
    2210                 :            :     }
    2211 [ +  - ][ +  - ]:        272 :     OrContext ctx(qopt, subqueries.size() - 1);
    2212         [ +  - ]:        136 :     do_or_like(ctx, qopt, 0.0, 0, 1);
    2213         [ +  - ]:        272 :     unique_ptr<PostList> r(ctx.postlist());
    2214         [ -  + ]:        136 :     if (!r.get()) {
    2215                 :          0 :         RETURN(l.release());
    2216                 :            :     }
    2217         [ +  - ]:        136 :     RETURN(new AndNotPostList(l.release(), r.release(),
    2218                 :        136 :                               qopt->matcher, qopt->db_size));
    2219                 :            : }
    2220                 :            : 
    2221                 :            : PostList*
    2222                 :        112 : QueryXor::postlist(QueryOptimiser * qopt, double factor) const
    2223                 :            : {
    2224                 :            :     LOGCALL(QUERY, PostList*, "QueryXor::postlist", qopt | factor);
    2225 [ +  - ][ +  - ]:        112 :     XorContext ctx(qopt, subqueries.size());
    2226         [ +  - ]:        112 :     postlist_sub_xor(ctx, qopt, factor);
    2227         [ +  - ]:        112 :     RETURN(ctx.postlist());
    2228                 :            : }
    2229                 :            : 
    2230                 :            : void
    2231                 :        112 : QueryXor::postlist_sub_xor(XorContext& ctx, QueryOptimiser * qopt, double factor) const
    2232                 :            : {
    2233                 :        112 :     QueryVector::const_iterator i;
    2234 [ +  - ][ +  - ]:        424 :     for (i = subqueries.begin(); i != subqueries.end(); ++i) {
         [ +  - ][ +  + ]
    2235                 :            :         // MatchNothing subqueries should have been removed by done().
    2236                 :            :         Assert((*i).internal.get());
    2237 [ +  - ][ +  - ]:        312 :         (*i).internal->postlist_sub_xor(ctx, qopt, factor);
    2238                 :            :     }
    2239                 :        112 : }
    2240                 :            : 
    2241                 :            : PostList*
    2242                 :         68 : QueryAndMaybe::postlist(QueryOptimiser * qopt, double factor) const
    2243                 :            : {
    2244                 :            :     LOGCALL(QUERY, PostList*, "QueryAndMaybe::postlist", qopt | factor);
    2245                 :            :     // FIXME: Combine and-like side with and-like stuff above.
    2246 [ +  - ][ +  - ]:         68 :     unique_ptr<PostList> l(subqueries[0].internal->postlist(qopt, factor));
    2247         [ +  + ]:         68 :     if (!l.get()) {
    2248                 :          8 :         RETURN(NULL);
    2249                 :            :     }
    2250         [ +  + ]:         60 :     if (factor == 0.0) {
    2251                 :            :         // An unweighted OP_AND_MAYBE can be replaced with its left branch.
    2252                 :         16 :         RETURN(l.release());
    2253                 :            :     }
    2254 [ +  - ][ +  - ]:         88 :     OrContext ctx(qopt, subqueries.size() - 1);
    2255         [ +  - ]:         44 :     do_or_like(ctx, qopt, factor, 0, 1);
    2256         [ +  - ]:         88 :     unique_ptr<PostList> r(ctx.postlist());
    2257         [ -  + ]:         44 :     if (!r.get()) {
    2258                 :          0 :         RETURN(l.release());
    2259                 :            :     }
    2260         [ +  - ]:         44 :     RETURN(new AndMaybePostList(l.release(), r.release(),
    2261                 :         68 :                                 qopt->matcher, qopt->db_size));
    2262                 :            : }
    2263                 :            : 
    2264                 :            : PostList*
    2265                 :         50 : QueryFilter::postlist(QueryOptimiser * qopt, double factor) const
    2266                 :            : {
    2267                 :            :     LOGCALL(QUERY, PostList*, "QueryFilter::postlist", qopt | factor);
    2268                 :            :     // FIXME: Combine and-like stuff, like QueryOptimiser.
    2269                 :            :     AssertEq(subqueries.size(), 2);
    2270                 :            :     PostList * pls[2];
    2271 [ +  - ][ +  - ]:         50 :     unique_ptr<PostList> l(subqueries[0].internal->postlist(qopt, factor));
    2272         [ -  + ]:         50 :     if (!l.get()) RETURN(NULL);
    2273 [ +  - ][ +  - ]:         50 :     pls[1] = subqueries[1].internal->postlist(qopt, 0.0);
    2274         [ -  + ]:         50 :     if (!pls[1]) RETURN(NULL);
    2275                 :         50 :     pls[0] = l.release();
    2276 [ +  - ][ +  - ]:         50 :     RETURN(new MultiAndPostList(pls, pls + 2, qopt->matcher, qopt->db_size));
    2277                 :            : }
    2278                 :            : 
    2279                 :            : bool
    2280                 :          0 : QueryFilter::postlist_sub_and_like(AndContext& ctx, QueryOptimiser * qopt, double factor) const
    2281                 :            : {
    2282                 :          0 :     QueryVector::const_iterator i;
    2283 [ #  # ][ #  # ]:          0 :     for (i = subqueries.begin(); i != subqueries.end(); ++i) {
         [ #  # ][ #  # ]
    2284                 :            :         // MatchNothing subqueries should have been removed by done().
    2285                 :            :         Assert((*i).internal.get());
    2286 [ #  # ][ #  # ]:          0 :         if (!(*i).internal->postlist_sub_and_like(ctx, qopt, factor))
                 [ #  # ]
    2287                 :          0 :             return false;
    2288                 :            :         // Second and subsequent subqueries are unweighted.
    2289                 :          0 :         factor = 0.0;
    2290                 :            :     }
    2291                 :          0 :     return true;
    2292                 :            : }
    2293                 :            : 
    2294                 :            : bool
    2295                 :        748 : QueryWindowed::postlist_windowed(Query::op op, AndContext& ctx, QueryOptimiser * qopt, double factor) const
    2296                 :            : {
    2297         [ +  + ]:        748 :     if (!qopt->full_db_has_positions) {
    2298                 :            :         // No positional data anywhere, so just handle as AND.
    2299         [ +  - ]:         44 :         return QueryAndLike::postlist_sub_and_like(ctx, qopt, factor);
    2300                 :            :     }
    2301                 :            : 
    2302 [ +  - ][ +  + ]:        704 :     if (!qopt->db.has_positions()) {
    2303                 :            :         // No positions in this subdatabase so this matches nothing, which
    2304                 :            :         // means the whole andcontext matches nothing.
    2305                 :            :         //
    2306                 :            :         // Bailing out here means we don't recurse deeper and that means we
    2307                 :            :         // don't call QueryOptimiser::inc_total_subqs() for leaf postlists in
    2308                 :            :         // the phrase, but at least one shard will count them, and the matcher
    2309                 :            :         // takes the highest answer (since 1.4.6).
    2310         [ +  - ]:         16 :         ctx.shrink(0);
    2311                 :         16 :         return false;
    2312                 :            :     }
    2313                 :            : 
    2314                 :        688 :     bool old_need_positions = qopt->need_positions;
    2315                 :        688 :     qopt->need_positions = true;
    2316                 :            : 
    2317                 :        688 :     bool result = true;
    2318                 :        688 :     QueryVector::const_iterator i;
    2319 [ +  - ][ +  - ]:       2380 :     for (i = subqueries.begin(); i != subqueries.end(); ++i) {
         [ +  - ][ +  + ]
    2320                 :            :         // MatchNothing subqueries should have been removed by done().
    2321                 :            :         Assert((*i).internal.get());
    2322         [ +  - ]:       1692 :         bool is_term = ((*i).internal->get_type() == Query::LEAF_TERM);
    2323 [ +  - ][ +  - ]:       1692 :         PostList* pl = (*i).internal->postlist(qopt, factor);
    2324 [ +  - ][ +  + ]:       1692 :         if (pl && !is_term)
    2325         [ +  - ]:        128 :             pl = new OrPosPostList(pl);
    2326         [ +  - ]:       1692 :         result = ctx.add_postlist(pl);
    2327         [ -  + ]:       1692 :         if (!result) {
    2328         [ #  # ]:          0 :             if (factor == 0.0) break;
    2329                 :            :             // If we don't complete the iteration, the subquery count may be
    2330                 :            :             // wrong, and weighting information may not be filled in.
    2331 [ #  # ][ #  # ]:          0 :             while (i != subqueries.end()) {
                 [ #  # ]
    2332                 :            :                 // MatchNothing subqueries should have been removed by done().
    2333                 :            :                 // FIXME: Can we handle this more gracefully?
    2334                 :            :                 Assert((*i).internal.get());
    2335 [ #  # ][ #  # ]:          0 :                 delete (*i).internal->postlist(qopt, factor);
                 [ #  # ]
    2336                 :          0 :                 ++i;
    2337                 :            :             }
    2338                 :          0 :             break;
    2339                 :            :         }
    2340                 :            :     }
    2341         [ +  - ]:        688 :     if (result) {
    2342                 :            :         // Record the positional filter to apply higher up the tree.
    2343 [ +  - ][ +  - ]:        688 :         ctx.add_pos_filter(op, subqueries.size(), window);
    2344                 :            :     }
    2345                 :            : 
    2346                 :        688 :     qopt->need_positions = old_need_positions;
    2347                 :        748 :     return result;
    2348                 :            : }
    2349                 :            : 
    2350                 :            : bool
    2351                 :        512 : QueryPhrase::postlist_sub_and_like(AndContext & ctx, QueryOptimiser * qopt, double factor) const
    2352                 :            : {
    2353                 :        512 :     constexpr auto OP_PHRASE = Query::OP_PHRASE;
    2354                 :        512 :     return QueryWindowed::postlist_windowed(OP_PHRASE, ctx, qopt, factor);
    2355                 :            : }
    2356                 :            : 
    2357                 :            : bool
    2358                 :        236 : QueryNear::postlist_sub_and_like(AndContext & ctx, QueryOptimiser * qopt, double factor) const
    2359                 :            : {
    2360                 :        236 :     constexpr auto OP_NEAR = Query::OP_NEAR;
    2361                 :        236 :     return QueryWindowed::postlist_windowed(OP_NEAR, ctx, qopt, factor);
    2362                 :            : }
    2363                 :            : 
    2364                 :            : PostList*
    2365                 :        224 : QueryEliteSet::postlist(QueryOptimiser * qopt, double factor) const
    2366                 :            : {
    2367                 :            :     LOGCALL(QUERY, PostList*, "QueryEliteSet::postlist", qopt | factor);
    2368 [ +  - ][ +  - ]:        224 :     OrContext ctx(qopt, subqueries.size());
    2369         [ +  - ]:        224 :     do_or_like(ctx, qopt, factor, set_size);
    2370         [ +  - ]:        224 :     RETURN(ctx.postlist());
    2371                 :            : }
    2372                 :            : 
    2373                 :            : void
    2374                 :          0 : QueryEliteSet::postlist_sub_or_like(OrContext& ctx, QueryOptimiser * qopt, double factor) const
    2375                 :            : {
    2376                 :          0 :     do_or_like(ctx, qopt, factor, set_size);
    2377                 :          0 : }
    2378                 :            : 
    2379                 :            : PostList*
    2380                 :        660 : QuerySynonym::postlist(QueryOptimiser * qopt, double factor) const
    2381                 :            : {
    2382                 :            :     LOGCALL(QUERY, PostList*, "QuerySynonym::postlist", qopt | factor);
    2383                 :            :     // Save and restore total_subqs so we only add one for the whole
    2384                 :            :     // OP_SYNONYM subquery (or none if we're not weighted).
    2385                 :        660 :     Xapian::termcount save_total_subqs = qopt->get_total_subqs();
    2386         [ +  + ]:        660 :     if (factor != 0.0)
    2387                 :        612 :         ++save_total_subqs;
    2388                 :        660 :     PostList * pl = do_synonym(qopt, factor);
    2389                 :        660 :     qopt->set_total_subqs(save_total_subqs);
    2390                 :        660 :     RETURN(pl);
    2391                 :            : }
    2392                 :            : 
    2393                 :            : Query::Internal *
    2394                 :      52058 : QuerySynonym::done()
    2395                 :            : {
    2396                 :            :     // An empty Synonym gives MatchNothing.  Note that add_subquery() drops any
    2397                 :            :     // subqueries which are MatchNothing.
    2398         [ +  + ]:      52058 :     if (subqueries.empty())
    2399                 :          1 :         return NULL;
    2400         [ +  + ]:      52057 :     if (subqueries.size() == 1) {
    2401                 :      20906 :         Query::op sub_type = subqueries[0].get_type();
    2402                 :            :         // Synonym of a single subquery should only be simplified if that
    2403                 :            :         // subquery is a term (or MatchAll), or if it's also OP_SYNONYM.  Note
    2404                 :            :         // that MatchNothing subqueries are dropped, so we'd never get here
    2405                 :            :         // with a single MatchNothing subquery.
    2406 [ +  + ][ +  + ]:      20906 :         if (sub_type == Query::LEAF_TERM || sub_type == Query::LEAF_MATCH_ALL ||
                 [ -  + ]
    2407                 :            :             sub_type == Query::OP_SYNONYM) {
    2408                 :      20249 :             return subqueries[0].internal.get();
    2409                 :            :         }
    2410         [ +  + ]:        657 :         if (sub_type == Query::OP_WILDCARD) {
    2411                 :        554 :             auto q = static_cast<QueryWildcard*>(subqueries[0].internal.get());
    2412                 :            :             // SYNONYM over WILDCARD X -> WILDCARD SYNONYM for any combiner X.
    2413                 :        554 :             return q->change_combiner(Query::OP_SYNONYM);
    2414                 :            :         }
    2415         [ +  - ]:        103 :         if (sub_type == Query::OP_EDIT_DISTANCE) {
    2416                 :            :             auto q =
    2417                 :        103 :                 static_cast<QueryEditDistance*>(subqueries[0].internal.get());
    2418                 :            :             // SYNONYM over EDIT_DISTANCE X -> EDIT_DISTANCE SYNONYM for any
    2419                 :            :             // combiner X.
    2420                 :        103 :             return q->change_combiner(Query::OP_SYNONYM);
    2421                 :            :         }
    2422                 :            :     }
    2423                 :      31151 :     return this;
    2424                 :            : }
    2425                 :            : 
    2426                 :            : PostList*
    2427                 :          8 : QueryMax::postlist(QueryOptimiser * qopt, double factor) const
    2428                 :            : {
    2429                 :            :     LOGCALL(QUERY, PostList*, "QueryMax::postlist", qopt | factor);
    2430                 :            :     // Save and restore total_subqs so we only add one for the whole
    2431                 :            :     // OP_MAX subquery (or none if we're not weighted).
    2432                 :          8 :     Xapian::termcount save_total_subqs = qopt->get_total_subqs();
    2433         [ +  - ]:          8 :     if (factor != 0.0)
    2434                 :          8 :         ++save_total_subqs;
    2435                 :          8 :     PostList * pl = do_max(qopt, factor);
    2436                 :          8 :     qopt->set_total_subqs(save_total_subqs);
    2437                 :          8 :     RETURN(pl);
    2438                 :            : }
    2439                 :            : 
    2440                 :            : Xapian::Query::op
    2441                 :        172 : QueryAnd::get_op() const
    2442                 :            : {
    2443                 :        172 :     return Xapian::Query::OP_AND;
    2444                 :            : }
    2445                 :            : 
    2446                 :            : Xapian::Query::op
    2447                 :       1873 : QueryOr::get_op() const
    2448                 :            : {
    2449                 :       1873 :     return Xapian::Query::OP_OR;
    2450                 :            : }
    2451                 :            : 
    2452                 :            : Xapian::Query::op
    2453                 :         95 : QueryAndNot::get_op() const
    2454                 :            : {
    2455                 :         95 :     return Xapian::Query::OP_AND_NOT;
    2456                 :            : }
    2457                 :            : 
    2458                 :            : Xapian::Query::op
    2459                 :         44 : QueryXor::get_op() const
    2460                 :            : {
    2461                 :         44 :     return Xapian::Query::OP_XOR;
    2462                 :            : }
    2463                 :            : 
    2464                 :            : Xapian::Query::op
    2465                 :         32 : QueryAndMaybe::get_op() const
    2466                 :            : {
    2467                 :         32 :     return Xapian::Query::OP_AND_MAYBE;
    2468                 :            : }
    2469                 :            : 
    2470                 :            : Xapian::Query::op
    2471                 :         14 : QueryFilter::get_op() const
    2472                 :            : {
    2473                 :         14 :     return Xapian::Query::OP_FILTER;
    2474                 :            : }
    2475                 :            : 
    2476                 :            : Xapian::Query::op
    2477                 :         69 : QueryNear::get_op() const
    2478                 :            : {
    2479                 :         69 :     return Xapian::Query::OP_NEAR;
    2480                 :            : }
    2481                 :            : 
    2482                 :            : Xapian::Query::op
    2483                 :        268 : QueryPhrase::get_op() const
    2484                 :            : {
    2485                 :        268 :     return Xapian::Query::OP_PHRASE;
    2486                 :            : }
    2487                 :            : 
    2488                 :            : Xapian::Query::op
    2489                 :        217 : QueryEliteSet::get_op() const
    2490                 :            : {
    2491                 :        217 :     return Xapian::Query::OP_ELITE_SET;
    2492                 :            : }
    2493                 :            : 
    2494                 :            : Xapian::Query::op
    2495                 :        147 : QuerySynonym::get_op() const
    2496                 :            : {
    2497                 :        147 :     return Xapian::Query::OP_SYNONYM;
    2498                 :            : }
    2499                 :            : 
    2500                 :            : Xapian::Query::op
    2501                 :          2 : QueryMax::get_op() const
    2502                 :            : {
    2503                 :          2 :     return Xapian::Query::OP_MAX;
    2504                 :            : }
    2505                 :            : 
    2506                 :            : string
    2507                 :        197 : QueryAnd::get_description() const
    2508                 :            : {
    2509                 :        197 :     return get_description_helper(" AND ");
    2510                 :            : }
    2511                 :            : 
    2512                 :            : string
    2513                 :       1462 : QueryOr::get_description() const
    2514                 :            : {
    2515                 :       1462 :     return get_description_helper(" OR ");
    2516                 :            : }
    2517                 :            : 
    2518                 :            : string
    2519                 :        128 : QueryAndNot::get_description() const
    2520                 :            : {
    2521                 :        128 :     return get_description_helper(" AND_NOT ");
    2522                 :            : }
    2523                 :            : 
    2524                 :            : string
    2525                 :         44 : QueryXor::get_description() const
    2526                 :            : {
    2527                 :         44 :     return get_description_helper(" XOR ");
    2528                 :            : }
    2529                 :            : 
    2530                 :            : string
    2531                 :        103 : QueryAndMaybe::get_description() const
    2532                 :            : {
    2533                 :        103 :     return get_description_helper(" AND_MAYBE ");
    2534                 :            : }
    2535                 :            : 
    2536                 :            : string
    2537                 :         30 : QueryFilter::get_description() const
    2538                 :            : {
    2539                 :         30 :     return get_description_helper(" FILTER ");
    2540                 :            : }
    2541                 :            : 
    2542                 :            : string
    2543                 :         20 : QueryNear::get_description() const
    2544                 :            : {
    2545                 :         20 :     return get_description_helper(" NEAR ", window);
    2546                 :            : }
    2547                 :            : 
    2548                 :            : string
    2549                 :        431 : QueryPhrase::get_description() const
    2550                 :            : {
    2551                 :        431 :     return get_description_helper(" PHRASE ", window);
    2552                 :            : }
    2553                 :            : 
    2554                 :            : string
    2555                 :          1 : QueryEliteSet::get_description() const
    2556                 :            : {
    2557                 :          1 :     return get_description_helper(" ELITE_SET ", set_size);
    2558                 :            : }
    2559                 :            : 
    2560                 :            : string
    2561                 :        549 : QuerySynonym::get_description() const
    2562                 :            : {
    2563         [ -  + ]:        549 :     if (subqueries.size() == 1) {
    2564         [ #  # ]:          0 :         string d = "(SYNONYM ";
    2565 [ #  # ][ #  # ]:          0 :         d += subqueries[0].internal->get_description();
                 [ #  # ]
    2566         [ #  # ]:          0 :         d += ")";
    2567                 :          0 :         return d;
    2568                 :            :     }
    2569                 :        549 :     return get_description_helper(" SYNONYM ");
    2570                 :            : }
    2571                 :            : 
    2572                 :            : string
    2573                 :          0 : QueryMax::get_description() const
    2574                 :            : {
    2575                 :          0 :     return get_description_helper(" MAX ");
    2576                 :            : }
    2577                 :            : 
    2578                 :            : Xapian::Query::op
    2579                 :         96 : QueryInvalid::get_type() const XAPIAN_NOEXCEPT
    2580                 :            : {
    2581                 :         96 :     return Xapian::Query::OP_INVALID;
    2582                 :            : }
    2583                 :            : 
    2584                 :            : PostList*
    2585                 :          0 : QueryInvalid::postlist(QueryOptimiser *, double) const
    2586                 :            : {
    2587 [ #  # ][ #  # ]:          0 :     throw Xapian::InvalidOperationError("Query is invalid");
                 [ #  # ]
    2588                 :            : }
    2589                 :            : 
    2590                 :            : void
    2591                 :          0 : QueryInvalid::serialise(std::string & result) const
    2592                 :            : {
    2593                 :          0 :     result += static_cast<char>(0x00);
    2594                 :          0 : }
    2595                 :            : 
    2596                 :            : string
    2597                 :          0 : QueryInvalid::get_description() const
    2598                 :            : {
    2599         [ #  # ]:          0 :     return "<INVALID>";
    2600                 :            : }
    2601                 :            : 
    2602                 :            : }
    2603                 :            : }

Generated by: LCOV version 1.11