LCOV - code coverage report
Current view: top level - api - queryinternal.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 954b5873a738 Lines: 1004 1139 88.1 %
Date: 2019-06-30 05:20:33 Functions: 156 169 92.3 %
Branches: 855 1692 50.5 %

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

Generated by: LCOV version 1.11