LCOV - code coverage report
Current view: top level - matcher - matcher.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 954b5873a738 Lines: 217 248 87.5 %
Date: 2019-06-30 05:20:33 Functions: 9 9 100.0 %
Branches: 263 415 63.4 %

           Branch data     Line data    Source code
       1                 :            : /** @file matcher.cc
       2                 :            :  * @brief Matcher class
       3                 :            :  */
       4                 :            : /* Copyright (C) 2006,2008,2009,2010,2011,2017,2018,2019 Olly Betts
       5                 :            :  *
       6                 :            :  * This program is free software; you can redistribute it and/or modify
       7                 :            :  * it under the terms of the GNU General Public License as published by
       8                 :            :  * the Free Software Foundation; either version 2 of the License, or
       9                 :            :  * (at your option) any later version.
      10                 :            :  *
      11                 :            :  * This program is distributed in the hope that it will be useful,
      12                 :            :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      13                 :            :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14                 :            :  * GNU General Public License for more details.
      15                 :            :  *
      16                 :            :  * You should have received a copy of the GNU General Public License
      17                 :            :  * along with this program; if not, write to the Free Software
      18                 :            :  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
      19                 :            :  */
      20                 :            : 
      21                 :            : #include <config.h>
      22                 :            : 
      23                 :            : #include "matcher.h"
      24                 :            : 
      25                 :            : #include "api/enquireinternal.h"
      26                 :            : #include "api/msetinternal.h"
      27                 :            : #include "api/rsetinternal.h"
      28                 :            : #include "backends/multi/multi_database.h"
      29                 :            : #include "deciderpostlist.h"
      30                 :            : #include "localsubmatch.h"
      31                 :            : #include "msetcmp.h"
      32                 :            : #include "omassert.h"
      33                 :            : #include "postlisttree.h"
      34                 :            : #include "protomset.h"
      35                 :            : #include "spymaster.h"
      36                 :            : #include "valuestreamdocument.h"
      37                 :            : #include "weight/weightinternal.h"
      38                 :            : 
      39                 :            : #include <xapian/version.h> // For XAPIAN_HAS_REMOTE_BACKEND
      40                 :            : 
      41                 :            : #ifdef XAPIAN_HAS_REMOTE_BACKEND
      42                 :            : # include "backends/remote/remote-database.h"
      43                 :            : # include "remotesubmatch.h"
      44                 :            : #endif
      45                 :            : 
      46                 :            : #include <algorithm>
      47                 :            : #include <cerrno>
      48                 :            : #include <cfloat> // For DBL_EPSILON.
      49                 :            : #include <vector>
      50                 :            : 
      51                 :            : #ifdef HAVE_POLL_H
      52                 :            : # include <poll.h>
      53                 :            : #else
      54                 :            : # include "safesysselect.h"
      55                 :            : #endif
      56                 :            : 
      57                 :            : using namespace std;
      58                 :            : using Xapian::Internal::opt_intrusive_ptr;
      59                 :            : 
      60                 :            : static constexpr auto DOCID = Xapian::Enquire::Internal::DOCID;
      61                 :            : static constexpr auto REL = Xapian::Enquire::Internal::REL;
      62                 :            : static constexpr auto REL_VAL = Xapian::Enquire::Internal::REL_VAL;
      63                 :            : static constexpr auto VAL = Xapian::Enquire::Internal::VAL;
      64                 :            : static constexpr auto VAL_REL = Xapian::Enquire::Internal::VAL_REL;
      65                 :            : 
      66                 :            : #ifdef XAPIAN_HAS_REMOTE_BACKEND
      67                 :            : [[noreturn]]
      68                 :          4 : static void unimplemented(const char* msg)
      69                 :            : {
      70 [ +  - ][ +  - ]:          4 :     throw Xapian::UnimplementedError(msg);
                 [ +  - ]
      71                 :            : }
      72                 :            : 
      73                 :            : template<typename Action>
      74                 :            : inline void
      75                 :     160758 : Matcher::for_all_remotes(Action action)
      76                 :            : {
      77                 :            : #ifdef HAVE_POLL
      78                 :     160758 :     size_t n_remotes = remotes.size();
      79   [ +  +  +  + ]:     160758 :     if (n_remotes <= 1) {
      80                 :            :         // We only need to use poll() when there are at least 2 remote
      81                 :            :         // databases we need to wait for.
      82 [ +  - ][ +  + ]:     160710 :         if (n_remotes == 1) {
      83                 :            :             // Just execute action and block if it's not ready.
      84 [ +  - ][ +  - ]:      10614 :             action(remotes[0].get());
      85                 :            :         }
      86                 :     160758 :         return;
      87                 :            :     }
      88                 :            : 
      89 [ +  - ][ +  - ]:         48 :     unique_ptr<struct pollfd[]> fds(new struct pollfd[n_remotes]);
         [ +  - ][ +  - ]
      90 [ +  + ][ +  + ]:        148 :     for (size_t i = 0; i != n_remotes; ++i) {
      91                 :        100 :         fds[i].fd = remotes[i]->get_read_fd();
      92                 :        100 :         fds[i].events = POLLIN;
      93                 :        100 :         fds[i].revents = 0;
      94                 :            :     }
      95 [ -  + ][ -  + ]:         48 :     do {
      96 [ +  - ][ +  - ]:         48 :         int r = poll(fds.get(), n_remotes, -1);
      97 [ -  + ][ -  + ]:         48 :         if (r <= 0) {
      98                 :            :             // We shouldn't get a timeout, but if we do retry.
      99 [ #  # ][ #  # ]:          0 :             if (r == 0 || errno == EINTR || errno == EAGAIN) {
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
     100                 :          0 :                 continue;
     101                 :            :             }
     102 [ #  # ][ #  # ]:          0 :             throw Xapian::NetworkError("poll() failed waiting for remotes",
         [ #  # ][ #  # ]
     103                 :          0 :                                        errno);
     104                 :            :         }
     105                 :         48 :         size_t i = 0;
     106 [ +  - ][ +  - ]:         78 :         while (i != n_remotes) {
     107 [ +  + ][ +  + ]:         78 :             if (fds[i].revents) {
     108 [ +  - ][ +  - ]:         52 :                 action(remotes[i].get());
     109                 :            :                 // Swap such that entries we still need to handle are first.
     110                 :         52 :                 swap(remotes[i], remotes[--n_remotes]);
     111                 :         52 :                 fds[i] = fds[n_remotes];
     112                 :            :                 // r is number of ready fds.
     113 [ +  + ][ +  + ]:         52 :                 if (--r == 0) break;
     114                 :            :             } else {
     115                 :         26 :                 ++i;
     116                 :            :             }
     117                 :            :         }
     118                 :            :     } while (n_remotes > 1);
     119                 :            : 
     120                 :            :     // If there's only one remote left just execute action and block if it's
     121                 :            :     // not ready.
     122 [ +  - ][ +  - ]:         48 :     if (n_remotes == 1) {
     123 [ +  - ][ +  - ]:         48 :         action(remotes[0].get());
     124                 :         48 :     }
     125                 :            : #else
     126                 :            : #ifndef __WIN32__
     127                 :            :     size_t n_remotes = first_oversize;
     128                 :            :     fd_set fds;
     129                 :            :     while (n_remotes > 1) {
     130                 :            :         int nfds = 0;
     131                 :            :         FD_ZERO(&fds);
     132                 :            :         for (size_t i = 0; i != n_remotes; ++i) {
     133                 :            :             int fd = remotes[i]->get_read_fd();
     134                 :            :             FD_SET(fd, &fds);
     135                 :            :             if (fd >= nfds) nfds = fd + 1;
     136                 :            :         }
     137                 :            : 
     138                 :            :         int r = select(nfds, &fds, NULL, NULL, NULL);
     139                 :            :         if (r <= 0) {
     140                 :            :             int eno = socket_errno();
     141                 :            :             // We shouldn't get a timeout, but if we do retry.
     142                 :            :             if (r == 0 || eno == EINTR || eno == EAGAIN) {
     143                 :            :                 continue;
     144                 :            :             }
     145                 :            :             throw Xapian::NetworkError("select() failed waiting for remotes",
     146                 :            :                                        eno);
     147                 :            :         }
     148                 :            :         size_t i = 0;
     149                 :            :         while (i != n_remotes) {
     150                 :            :             int fd = remotes[i]->get_read_fd();
     151                 :            :             if (FD_ISSET(fd, &fds)) {
     152                 :            :                 action(remotes[i].get());
     153                 :            :                 // Swap such that entries we still need to handle are first.
     154                 :            :                 swap(remotes[i], remotes[--n_remotes]);
     155                 :            :                 // r is number of ready fds.
     156                 :            :                 if (--r == 0) break;
     157                 :            :             } else {
     158                 :            :                 ++i;
     159                 :            :             }
     160                 :            :         }
     161                 :            :     }
     162                 :            : 
     163                 :            :     // If there's only one remote left just execute action and block if it's
     164                 :            :     // not ready.
     165                 :            :     if (n_remotes == 1) {
     166                 :            :         action(remotes[0].get());
     167                 :            :     }
     168                 :            : #endif
     169                 :            : 
     170                 :            :     // Handle any remotes with fd >= FD_SETSIZE
     171                 :            :     for (size_t i = first_oversize; i != remotes.size(); ++i) {
     172                 :            :         action(remotes[i].get());
     173                 :            :     }
     174                 :            : #endif
     175                 :            : }
     176                 :            : #endif
     177                 :            : 
     178                 :     160739 : Matcher::Matcher(const Xapian::Database& db_,
     179                 :            :                  bool full_db_has_positions_,
     180                 :            :                  const Xapian::Query& query_,
     181                 :            :                  Xapian::termcount query_length,
     182                 :            :                  const Xapian::RSet* rset,
     183                 :            :                  Xapian::Weight::Internal& stats,
     184                 :            :                  const Xapian::Weight& wtscheme,
     185                 :            :                  bool have_sorter,
     186                 :            :                  bool have_mdecider,
     187                 :            :                  Xapian::valueno collapse_key,
     188                 :            :                  Xapian::doccount collapse_max,
     189                 :            :                  int percent_threshold,
     190                 :            :                  double weight_threshold,
     191                 :            :                  Xapian::Enquire::docid_order order,
     192                 :            :                  Xapian::valueno sort_key,
     193                 :            :                  Xapian::Enquire::Internal::sort_setting sort_by,
     194                 :            :                  bool sort_val_reverse,
     195                 :            :                  double time_limit,
     196                 :            :                  const vector<opt_intrusive_ptr<Xapian::MatchSpy>>& matchspies)
     197         [ +  - ]:     160750 :     : db(db_), query(query_), full_db_has_positions(full_db_has_positions_)
     198                 :            : {
     199                 :            :     // An empty query should get handled higher up.
     200                 :            :     Assert(!query.empty());
     201                 :            : 
     202         [ +  - ]:     160739 :     Xapian::doccount n_shards = db.internal->size();
     203                 :     160739 :     vector<Xapian::RSet> subrsets;
     204 [ +  + ][ +  + ]:     160739 :     if (rset && rset->internal.get()) {
                 [ +  + ]
     205         [ +  - ]:         75 :         rset->internal->shard(n_shards, subrsets);
     206                 :            :     } else {
     207         [ +  - ]:     160664 :         subrsets.resize(n_shards);
     208                 :            :     }
     209                 :            : 
     210         [ +  + ]:     350029 :     for (size_t i = 0; i != n_shards; ++i) {
     211                 :     189300 :         const Xapian::Database::Internal *subdb = db.internal.get();
     212         [ +  + ]:     189300 :         if (n_shards > 1) {
     213                 :      57108 :             auto multidb = static_cast<const MultiDatabase*>(subdb);
     214         [ +  - ]:      57108 :             subdb = multidb->shards[i];
     215                 :            :         }
     216                 :            :         Assert(subdb);
     217                 :            : #ifdef XAPIAN_HAS_REMOTE_BACKEND
     218 [ +  - ][ +  + ]:     189300 :         if (subdb->get_backend_info(NULL) == BACKEND_REMOTE) {
     219                 :      10668 :             auto as_rem = static_cast<const RemoteDatabase*>(subdb);
     220         [ +  + ]:      10668 :             if (have_sorter) {
     221                 :            :                 unimplemented("Xapian::KeyMaker not supported by the remote "
     222                 :          2 :                               "backend");
     223                 :            :             }
     224         [ +  + ]:      10666 :             if (have_mdecider) {
     225                 :            :                 unimplemented("Xapian::MatchDecider not supported by the "
     226                 :          2 :                               "remote backend");
     227                 :            :             }
     228                 :            :             as_rem->set_query(query, query_length,
     229                 :            :                               collapse_key, collapse_max,
     230                 :            :                               order, sort_key, sort_by, sort_val_reverse,
     231                 :            :                               time_limit,
     232                 :            :                               n_shards == 1 ? percent_threshold : 0,
     233                 :            :                               weight_threshold,
     234                 :            :                               wtscheme,
     235                 :      10664 :                               subrsets[i], matchspies,
     236 [ +  + ][ +  + ]:      10664 :                               full_db_has_positions);
     237 [ +  - ][ +  - ]:      10658 :             remotes.emplace_back(new RemoteSubMatch(as_rem, i));
     238                 :      10658 :             continue;
     239                 :            :         }
     240                 :            : #else
     241                 :            :         // Avoid unused parameter warnings.
     242                 :            :         (void)have_sorter;
     243                 :            :         (void)have_mdecider;
     244                 :            :         (void)collapse_key;
     245                 :            :         (void)collapse_max;
     246                 :            :         (void)percent_threshold;
     247                 :            :         (void)weight_threshold;
     248                 :            :         (void)order;
     249                 :            :         (void)sort_key;
     250                 :            :         (void)sort_by;
     251                 :            :         (void)sort_val_reverse;
     252                 :            :         (void)time_limit;
     253                 :            :         (void)matchspies;
     254                 :            : #endif /* XAPIAN_HAS_REMOTE_BACKEND */
     255         [ +  + ]:     178632 :         if (locals.size() != i)
     256         [ +  - ]:          4 :             locals.resize(i);
     257                 :            :         locals.emplace_back(new LocalSubMatch(subdb, query, query_length,
     258                 :            :                                               wtscheme,
     259                 :            :                                               i,
     260 [ +  - ][ +  - ]:     178632 :                                               full_db_has_positions));
                 [ +  - ]
     261         [ +  - ]:     178632 :         subdb->readahead_for_query(query);
     262                 :            :     }
     263                 :            : 
     264 [ +  + ][ +  + ]:     160729 :     if (!locals.empty() && locals.size() != n_shards)
                 [ +  + ]
     265         [ +  - ]:          2 :         locals.resize(n_shards);
     266                 :            : 
     267                 :            : #ifdef XAPIAN_HAS_REMOTE_BACKEND
     268                 :            : # ifndef HAVE_POLL
     269                 :            : #  ifndef __WIN32__
     270                 :            :     {
     271                 :            :         // Unfortunately select() can't monitor fds >= FD_SETSIZE, so swap those to
     272                 :            :         // the end here and then handle those last letting them just block if not
     273                 :            :         // ready.
     274                 :            :         first_oversize = remotes.size();
     275                 :            :         size_t i = 0;
     276                 :            :         while (i != first_oversize) {
     277                 :            :             int fd = remotes[i]->get_read_fd();
     278                 :            :             if (fd >= FD_SETSIZE) {
     279                 :            :                 swap(remotes[i], remotes[--first_oversize]);
     280                 :            :             } else {
     281                 :            :                 ++i;
     282                 :            :             }
     283                 :            :         }
     284                 :            :     }
     285                 :            : #  else
     286                 :            :     // We can only use select() on sockets under __WIN32__ and with the remote
     287                 :            :     // prog backend the fds aren't sockets so just avoid using select() for
     288                 :            :     // now.
     289                 :            :     //
     290                 :            :     // FIXME: perhaps we should use WaitForMultipleObjects(), but that seems a
     291                 :            :     // bit tricky to hook up as it probably needs an async ReadFile() to be
     292                 :            :     // active.
     293                 :            :     first_oversize = 0;
     294                 :            : #  endif
     295                 :            : # endif
     296                 :            : #endif
     297                 :            : 
     298         [ +  - ]:     160729 :     stats.set_query(query);
     299                 :            : 
     300                 :            :     /* To improve overall performance in the case of searches over a mix of
     301                 :            :      * local and remote shards we set the queries for remote shards above,
     302                 :            :      * then prepare local shards here, then finish preparing remote shards
     303                 :            :      * below.
     304                 :            :      */
     305                 :            : 
     306         [ +  + ]:     160729 :     if (!locals.empty()) {
     307                 :            :         // Prepare local matches.
     308         [ +  + ]:     328740 :         for (size_t i = 0; i != n_shards; ++i) {
     309                 :     178638 :             auto submatch = locals[i].get();
     310         [ +  + ]:     178638 :             if (submatch) {
     311         [ +  + ]:     178632 :                 submatch->prepare_match(subrsets[i], stats);
     312                 :            :             }
     313                 :            :         }
     314                 :            :     }
     315                 :            : 
     316                 :            : #ifdef XAPIAN_HAS_REMOTE_BACKEND
     317                 :            :     for_all_remotes(
     318                 :      10658 :         [&](RemoteSubMatch* submatch) {
     319                 :      10658 :             submatch->prepare_match(stats);
     320         [ +  - ]:     160728 :         });
     321                 :            : #endif
     322                 :            : 
     323         [ +  - ]:     160739 :     stats.set_bounds_from_db(db);
     324                 :     160728 : }
     325                 :            : 
     326                 :            : Xapian::MSet
     327                 :     150102 : Matcher::get_local_mset(Xapian::doccount first,
     328                 :            :                         Xapian::doccount maxitems,
     329                 :            :                         Xapian::doccount check_at_least,
     330                 :            :                         const Xapian::Weight& wtscheme,
     331                 :            :                         const Xapian::MatchDecider* mdecider,
     332                 :            :                         const Xapian::KeyMaker* sorter,
     333                 :            :                         Xapian::valueno collapse_key,
     334                 :            :                         Xapian::doccount collapse_max,
     335                 :            :                         int percent_threshold,
     336                 :            :                         double percent_threshold_factor,
     337                 :            :                         double weight_threshold,
     338                 :            :                         Xapian::Enquire::docid_order order,
     339                 :            :                         Xapian::valueno sort_key,
     340                 :            :                         Xapian::Enquire::Internal::sort_setting sort_by,
     341                 :            :                         bool sort_val_reverse,
     342                 :            :                         double time_limit,
     343                 :            :                         const vector<opt_ptr_spy>& matchspies)
     344                 :            : {
     345                 :            :     Assert(!locals.empty());
     346                 :            : 
     347         [ +  - ]:     150102 :     ValueStreamDocument vsdoc(db);
     348                 :     150102 :     ++vsdoc._refs;
     349         [ +  - ]:     300204 :     Xapian::Document doc(&vsdoc);
     350                 :            : 
     351                 :     300204 :     vector<PostList*> postlists;
     352         [ +  - ]:     150102 :     postlists.reserve(locals.size());
     353                 :     300204 :     PostListTree pltree(vsdoc, db, wtscheme);
     354                 :     150102 :     Xapian::termcount total_subqs = 0;
     355                 :     150102 :     bool all_null = true;
     356         [ +  + ]:     328679 :     for (size_t i = 0; i != locals.size(); ++i) {
     357         [ +  + ]:     178629 :         if (!locals[i].get()) {
     358         [ +  - ]:          6 :             postlists.push_back(NULL);
     359                 :          6 :             continue;
     360                 :            :         }
     361                 :            :         // Pick the highest total subqueries answer amongst the subdatabases,
     362                 :            :         // as the query to postlist conversion doesn't recurse into positional
     363                 :            :         // queries for shards that don't have positional data when at least one
     364                 :            :         // other shard does.
     365                 :     178623 :         Xapian::termcount total_subqs_i = 0;
     366         [ +  + ]:     178623 :         PostList* pl = locals[i]->get_postlist(&pltree, &total_subqs_i);
     367         [ +  - ]:     178571 :         total_subqs = max(total_subqs, total_subqs_i);
     368         [ +  + ]:     178571 :         if (pl != NULL) {
     369                 :     178360 :             all_null = false;
     370         [ +  + ]:     178360 :             if (mdecider) {
     371 [ +  - ][ +  - ]:        118 :                 pl = new DeciderPostList(pl, mdecider, &vsdoc, &pltree);
     372                 :            :             }
     373                 :            :         }
     374         [ +  - ]:     178571 :         postlists.push_back(pl);
     375                 :            :     }
     376                 :            :     Assert(!postlists.empty());
     377                 :            : 
     378         [ +  + ]:     150050 :     if (all_null) {
     379                 :        127 :         vector<Result> dummy;
     380                 :            :         return Xapian::MSet(new Xapian::MSet::Internal(first, 0, 0, 0, 0, 0, 0,
     381                 :            :                                                        0.0, 0.0,
     382 [ +  - ][ +  - ]:        127 :                                                        std::move(dummy), 0));
                 [ +  - ]
     383                 :            :     }
     384                 :            : 
     385                 :     149923 :     Xapian::doccount n_shards = postlists.size();
     386         [ +  - ]:     149923 :     pltree.set_postlists(&postlists[0], n_shards);
     387                 :            : 
     388                 :            :     // The highest weight a document could get in this match.
     389         [ +  - ]:     149923 :     const double max_possible = pltree.recalc_maxweight();
     390                 :            : 
     391         [ +  + ]:     149923 :     if (max_possible == 0.0) {
     392                 :            :         // All the weights are zero.
     393         [ +  + ]:      10905 :         if (sort_by == REL) {
     394                 :            :             // We're only sorting by DOCID.
     395                 :      10886 :             sort_by = DOCID;
     396 [ +  - ][ -  + ]:         19 :         } else if (sort_by == REL_VAL || sort_by == VAL_REL) {
     397                 :            :             // Normalise REL_VAL and VAL_REL to VAL, to avoid needlessly
     398                 :            :             // fetching and comparing weights.
     399                 :          0 :             sort_by = VAL;
     400                 :            :         }
     401                 :            :         // All percentages will be 100% so turn off any percentage cut-off.
     402                 :      10905 :         percent_threshold = 0;
     403                 :      10905 :         percent_threshold_factor = 0.0;
     404                 :            :     }
     405                 :            : 
     406         [ +  - ]:     149923 :     Xapian::doccount matches_lower_bound = pltree.get_termfreq_min();
     407         [ +  - ]:     149923 :     Xapian::doccount matches_estimated = pltree.get_termfreq_est();
     408         [ +  - ]:     149923 :     Xapian::doccount matches_upper_bound = pltree.get_termfreq_max();
     409                 :            : 
     410                 :            :     // Check if any results have been asked for (might just be wanting
     411                 :            :     // maxweight).
     412         [ +  + ]:     149923 :     if (check_at_least == 0) {
     413                 :        343 :         Xapian::doccount uncollapsed_lower_bound = matches_lower_bound;
     414         [ +  + ]:        343 :         if (collapse_max) {
     415                 :            :             // Lower bound must be set to no more than collapse_max, since it's
     416                 :            :             // possible that all matching documents have the same collapse_key
     417                 :            :             // value and so are collapsed together.
     418         [ +  - ]:         42 :             if (matches_lower_bound > collapse_max)
     419                 :         42 :                 matches_lower_bound = collapse_max;
     420                 :            :         }
     421                 :            : 
     422                 :        343 :         vector<Result> dummy;
     423                 :            :         return Xapian::MSet(new Xapian::MSet::Internal(first,
     424                 :            :                                                        matches_upper_bound,
     425                 :            :                                                        matches_lower_bound,
     426                 :            :                                                        matches_estimated,
     427                 :            :                                                        matches_upper_bound,
     428                 :            :                                                        uncollapsed_lower_bound,
     429                 :            :                                                        matches_estimated,
     430                 :            :                                                        max_possible,
     431                 :            :                                                        0.0,
     432                 :            :                                                        std::move(dummy),
     433 [ +  - ][ +  - ]:        343 :                                                        0));
                 [ +  - ]
     434                 :            :     }
     435                 :            : 
     436                 :     149580 :     SpyMaster spymaster(&matchspies);
     437                 :            : 
     438                 :     149580 :     bool sort_forward = (order != Xapian::Enquire::DESCENDING);
     439         [ +  - ]:     149580 :     auto mcmp = get_msetcmp_function(sort_by, sort_forward, sort_val_reverse);
     440                 :            : 
     441                 :            :     // Can we stop once the ProtoMSet is full?
     442         [ +  + ]:     149243 :     bool stop_once_full = (sort_forward &&
     443 [ +  + ][ +  + ]:     298823 :                            n_shards == 1 &&
     444                 :     149580 :                            sort_by == DOCID);
     445                 :            : 
     446                 :            :     ProtoMSet proto_mset(first, maxitems, check_at_least,
     447                 :            :                          mcmp, sort_by, total_subqs,
     448                 :            :                          pltree,
     449                 :            :                          collapse_key, collapse_max,
     450                 :            :                          percent_threshold, percent_threshold_factor,
     451                 :            :                          max_possible,
     452                 :            :                          stop_once_full,
     453         [ +  - ]:     299160 :                          time_limit);
     454                 :     149580 :     proto_mset.set_new_min_weight(weight_threshold);
     455                 :            : 
     456                 :            :     while (true) {
     457                 :   47819231 :         double min_weight = proto_mset.get_min_weight();
     458 [ +  - ][ +  + ]:   47819231 :         if (!pltree.next(min_weight)) {
     459                 :     149465 :             break;
     460                 :            :         }
     461                 :            : 
     462                 :            :         // The weight calculation can be expensive enough that it's worth being
     463                 :            :         // lazy and only calculating it once we know we need to.  If sort_by
     464                 :            :         // is DOCID then all weights are zero.
     465                 :   47669766 :         double weight = 0.0;
     466                 :   47669766 :         bool calculated_weight = (sort_by == DOCID);
     467         [ +  + ]:   47669766 :         if (!calculated_weight) {
     468 [ +  + ][ -  + ]:   47463575 :             if (sort_by != VAL || min_weight > 0.0) {
     469         [ +  - ]:   47451688 :                 weight = pltree.get_weight();
     470         [ +  + ]:   47451688 :                 if (weight < min_weight) {
     471                 :   47669651 :                     continue;
     472                 :            :                 }
     473                 :   34146673 :                 calculated_weight = true;
     474                 :            :             }
     475                 :            :         }
     476                 :            : 
     477         [ +  - ]:   34352864 :         Xapian::docid did = pltree.get_docid();
     478                 :   34352864 :         vsdoc.set_document(did);
     479         [ +  - ]:   34352864 :         Result new_item(weight, did);
     480                 :            : 
     481 [ +  + ][ +  + ]:   34352864 :         if (sort_by != DOCID && sort_by != REL) {
     482         [ +  + ]:      27419 :             if (sorter) {
     483 [ +  - ][ +  - ]:        540 :                 new_item.set_sort_key((*sorter)(doc));
     484                 :            :             } else {
     485 [ +  - ][ +  - ]:      26879 :                 new_item.set_sort_key(vsdoc.get_value(sort_key));
     486                 :            :             }
     487                 :            : 
     488 [ +  - ][ +  + ]:      27419 :             if (proto_mset.early_reject(new_item, calculated_weight, spymaster,
     489                 :      27419 :                                         doc))
     490                 :       3791 :                 continue;
     491                 :            :         }
     492                 :            : 
     493                 :            :         // Apply any MatchSpy objects.
     494         [ +  + ]:   34349073 :         if (spymaster) {
     495         [ +  + ]:        460 :             if (!calculated_weight) {
     496         [ +  - ]:         88 :                 weight = pltree.get_weight();
     497                 :         88 :                 new_item.set_weight(weight);
     498                 :         88 :                 calculated_weight = true;
     499                 :            :             }
     500         [ +  - ]:        460 :             spymaster(doc, weight);
     501                 :            :         }
     502                 :            : 
     503         [ +  + ]:   34349073 :         if (!calculated_weight) {
     504         [ +  - ]:      10252 :             weight = pltree.get_weight();
     505                 :      10252 :             new_item.set_weight(weight);
     506                 :            :         }
     507                 :            : 
     508 [ +  - ][ +  + ]:   34349073 :         if (!proto_mset.process(std::move(new_item), vsdoc))
     509      [ +  +  + ]:   34352864 :             break;
     510                 :   34348958 :     }
     511                 :            : 
     512                 :            :     return proto_mset.finalise(mdecider,
     513                 :            :                                matches_lower_bound,
     514                 :            :                                matches_estimated,
     515         [ +  - ]:     299682 :                                matches_upper_bound);
     516                 :            : }
     517                 :            : 
     518                 :            : Xapian::MSet
     519                 :     160728 : Matcher::get_mset(Xapian::doccount first,
     520                 :            :                   Xapian::doccount maxitems,
     521                 :            :                   Xapian::doccount check_at_least,
     522                 :            :                   Xapian::Weight::Internal& stats,
     523                 :            :                   const Xapian::Weight& wtscheme,
     524                 :            :                   const Xapian::MatchDecider* mdecider,
     525                 :            :                   const Xapian::KeyMaker* sorter,
     526                 :            :                   Xapian::valueno collapse_key,
     527                 :            :                   Xapian::doccount collapse_max,
     528                 :            :                   int percent_threshold,
     529                 :            :                   double weight_threshold,
     530                 :            :                   Xapian::Enquire::docid_order order,
     531                 :            :                   Xapian::valueno sort_key,
     532                 :            :                   Xapian::Enquire::Internal::sort_setting sort_by,
     533                 :            :                   bool sort_val_reverse,
     534                 :            :                   double time_limit,
     535                 :            :                   const vector<opt_intrusive_ptr<Xapian::MatchSpy>>& matchspies)
     536                 :            : {
     537                 :            :     AssertRel(check_at_least, >=, first + maxitems);
     538                 :            : 
     539                 :            :     Assert(!query.empty());
     540                 :            : 
     541                 :            : #ifdef XAPIAN_HAS_REMOTE_BACKEND
     542 [ +  + ][ +  + ]:     160728 :     if (locals.empty() && remotes.size() == 1) {
                 [ +  + ]
     543                 :            :         // Short cut for a single remote database.
     544                 :            :         Assert(remotes[0].get());
     545         [ +  - ]:      10602 :         remotes[0]->start_match(first, maxitems, check_at_least, stats);
     546         [ +  + ]:      10602 :         return remotes[0]->get_mset(matchspies);
     547                 :            :     }
     548                 :            : #endif
     549                 :            : 
     550                 :            :     // Factor to multiply maximum weight seen by to get the minimum weight we
     551                 :            :     // need to consider.
     552                 :     150126 :     double percent_threshold_factor = percent_threshold / 100.0;
     553                 :            :     // Corresponding correction to that in api/mset.cc to account for excess
     554                 :            :     // precision on x86.
     555                 :     150126 :     percent_threshold_factor -= DBL_EPSILON;
     556                 :            : 
     557                 :            : #ifdef XAPIAN_HAS_REMOTE_BACKEND
     558         [ +  + ]:     150182 :     for (auto&& submatch : remotes) {
     559                 :            :         // We need to fetch the first "first" results too, as merging may push
     560                 :            :         // those down into the part of the merged MSet we care about.
     561         [ +  - ]:         56 :         if (submatch.get())
     562         [ +  - ]:         56 :             submatch->start_match(0, first + maxitems, check_at_least, stats);
     563                 :            :     }
     564                 :            : #endif
     565                 :            : 
     566         [ +  - ]:     150126 :     Xapian::MSet local_mset;
     567         [ +  + ]:     150126 :     if (!locals.empty()) {
     568         [ +  + ]:     328739 :         for (auto&& submatch : locals) {
     569         [ +  + ]:     178637 :             if (submatch.get())
     570                 :     178631 :                 submatch->start_match(stats);
     571                 :            :         }
     572                 :            : 
     573                 :            : #ifdef XAPIAN_HAS_REMOTE_BACKEND
     574         [ +  + ]:     150102 :         double ptf_to_use = remotes.empty() ? percent_threshold_factor : 0;
     575                 :            : #else
     576                 :            :         double ptf_to_use = percent_threshold_factor;
     577                 :            : #endif
     578         [ +  + ]:     300152 :         local_mset = get_local_mset(first, maxitems, check_at_least,
     579                 :            :                                     wtscheme, mdecider,
     580                 :            :                                     sorter, collapse_key, collapse_max,
     581                 :            :                                     percent_threshold, ptf_to_use,
     582                 :            :                                     weight_threshold, order, sort_key, sort_by,
     583         [ +  - ]:     150050 :                                     sort_val_reverse, time_limit, matchspies);
     584                 :            :     }
     585                 :            : 
     586                 :            : #ifdef XAPIAN_HAS_REMOTE_BACKEND
     587         [ +  + ]:     150074 :     if (remotes.empty()) {
     588                 :            :         // Another easy case - only local databases.
     589         [ +  - ]:     150044 :         return local_mset;
     590                 :            :     }
     591                 :            : 
     592                 :            :     // We need to merge MSet objects.  We only need the number of remote shards
     593                 :            :     // + 1 if there are any local shards, so reserving n_shards may be more
     594                 :            :     // than we need.
     595                 :         60 :     vector<pair<Xapian::MSet, Xapian::doccount>> msets;
     596         [ +  - ]:         60 :     Xapian::MSet merged_mset;
     597         [ +  + ]:         30 :     if (!locals.empty()) {
     598 [ +  - ][ +  - ]:          6 :         if (!local_mset.empty())
     599 [ +  - ][ +  - ]:          6 :             msets.push_back({local_mset, 0});
     600         [ +  - ]:          6 :         merged_mset.internal->merge_stats(local_mset.internal.get());
     601                 :            :     }
     602                 :            : 
     603                 :            :     for_all_remotes(
     604                 :         56 :         [&](RemoteSubMatch* submatch) {
     605         [ +  - ]:         56 :             Xapian::MSet remote_mset = submatch->get_mset(matchspies);
     606         [ +  - ]:         56 :             merged_mset.internal->merge_stats(remote_mset.internal.get());
     607 [ +  - ][ +  + ]:         56 :             if (remote_mset.empty()) {
     608                 :         64 :                 return;
     609                 :            :             }
     610                 :         48 :             remote_mset.internal->unshard_docids(submatch->get_shard(),
     611   [ +  -  +  - ]:         96 :                                                  db.internal->size());
     612 [ +  - ][ +  - ]:         56 :             msets.push_back({remote_mset, 0});
                 [ +  + ]
     613         [ +  - ]:         86 :         });
     614                 :            : 
     615         [ +  + ]:         30 :     if (merged_mset.internal->max_possible == 0.0) {
     616                 :            :         // All the weights are zero.
     617         [ +  + ]:          8 :         if (sort_by == REL) {
     618                 :            :             // We're only sorting by DOCID.
     619                 :          6 :             sort_by = DOCID;
     620 [ +  - ][ -  + ]:          2 :         } else if (sort_by == REL_VAL || sort_by == VAL_REL) {
     621                 :            :             // Normalise REL_VAL and VAL_REL to VAL, to avoid needlessly
     622                 :            :             // fetching and comparing weights.
     623                 :          0 :             sort_by = VAL;
     624                 :            :         }
     625                 :            :         // All percentages will be 100% so turn off any percentage cut-off.
     626                 :          8 :         percent_threshold = 0;
     627                 :          8 :         percent_threshold_factor = 0.0;
     628                 :            :     }
     629                 :            : 
     630                 :         30 :     bool sort_forward = (order != Xapian::Enquire::DESCENDING);
     631         [ +  - ]:         30 :     auto mcmp = get_msetcmp_function(sort_by, sort_forward, sort_val_reverse);
     632                 :            :     auto heap_cmp =
     633                 :            :         [&](const pair<Xapian::MSet, Xapian::doccount>& a,
     634                 :         84 :             const pair<Xapian::MSet, Xapian::doccount>& b) {
     635                 :         84 :             return mcmp(b.first.internal->items[b.second],
     636                 :         84 :                         a.first.internal->items[a.second]);
     637                 :         84 :         };
     638                 :            : 
     639         [ +  - ]:         30 :     Heap::make(msets.begin(), msets.end(), heap_cmp);
     640                 :            : 
     641                 :         30 :     double min_weight = 0.0;
     642         [ -  + ]:         30 :     if (percent_threshold) {
     643                 :          0 :         min_weight = percent_threshold_factor * 100.0 /
     644                 :          0 :                      merged_mset.internal->percent_scale_factor;
     645                 :            :     }
     646                 :            : 
     647         [ +  - ]:         60 :     CollapserLite collapser(collapse_max);
     648                 :         30 :     merged_mset.internal->first = first;
     649 [ +  + ][ +  - ]:        158 :     while (!msets.empty() && merged_mset.size() != maxitems) {
         [ +  - ][ +  + ]
     650                 :        128 :         auto& front = msets.front();
     651                 :        128 :         auto& result = front.first.internal->items[front.second];
     652         [ -  + ]:        128 :         if (percent_threshold) {
     653         [ #  # ]:          0 :             if (result.get_weight() < min_weight) {
     654                 :          0 :                 break;
     655                 :            :             }
     656                 :            :         }
     657         [ -  + ]:        128 :         if (collapser) {
     658 [ #  # ][ #  # ]:          0 :             if (!collapser.add(result.get_collapse_key()))
     659                 :          0 :                 continue;
     660                 :            :         }
     661         [ -  + ]:        128 :         if (first) {
     662                 :          0 :             --first;
     663                 :            :         } else {
     664         [ +  - ]:        128 :             merged_mset.internal->items.push_back(std::move(result));
     665                 :            :         }
     666                 :        128 :         auto n = msets.front().second + 1;
     667 [ +  - ][ +  + ]:        128 :         if (n == msets.front().first.size()) {
     668         [ +  - ]:         54 :             Heap::pop(msets.begin(), msets.end(), heap_cmp);
     669         [ +  - ]:         54 :             msets.resize(msets.size() - 1);
     670                 :            :         } else {
     671                 :         74 :             msets.front().second = n;
     672         [ +  - ]:         74 :             Heap::replace(msets.begin(), msets.end(), heap_cmp);
     673                 :            :         }
     674                 :            :     }
     675                 :            : 
     676         [ -  + ]:         30 :     if (collapser) {
     677         [ #  # ]:          0 :         collapser.finalise(merged_mset.internal->items, percent_threshold);
     678                 :            : 
     679                 :          0 :         auto mseti = merged_mset.internal;
     680                 :          0 :         mseti->matches_lower_bound = collapser.get_matches_lower_bound();
     681                 :            : 
     682                 :          0 :         double unique_rate = 1.0;
     683                 :            : 
     684                 :          0 :         Xapian::doccount docs_considered = collapser.get_docs_considered();
     685                 :          0 :         Xapian::doccount dups_ignored = collapser.get_dups_ignored();
     686         [ #  # ]:          0 :         if (docs_considered > 0) {
     687                 :            :             // Scale the estimate by the rate at which we've been finding
     688                 :            :             // unique documents.
     689                 :          0 :             double unique = double(docs_considered - dups_ignored);
     690                 :          0 :             unique_rate = unique / double(docs_considered);
     691                 :            :         }
     692                 :            : 
     693                 :            :         // We can safely reduce the upper bound by the number of duplicates
     694                 :            :         // we've ignored.
     695                 :          0 :         mseti->matches_upper_bound -= collapser.get_dups_ignored();
     696                 :            : 
     697                 :          0 :         double estimate_scale = unique_rate;
     698                 :            : 
     699         [ #  # ]:          0 :         if (estimate_scale != 1.0) {
     700                 :          0 :             auto matches_estimated = mseti->matches_estimated;
     701                 :          0 :             mseti->matches_estimated =
     702                 :          0 :                 Xapian::doccount(matches_estimated * estimate_scale + 0.5);
     703                 :            :         }
     704                 :            : 
     705                 :            :         // Clamp the estimate the range given by the bounds.
     706                 :            :         AssertRel(mseti->matches_lower_bound, <=, mseti->matches_upper_bound);
     707                 :          0 :         mseti->matches_estimated = STD_CLAMP(mseti->matches_estimated,
     708                 :          0 :                                              mseti->matches_lower_bound,
     709         [ #  # ]:          0 :                                              mseti->matches_upper_bound);
     710                 :            :     }
     711                 :            : 
     712         [ +  - ]:     160738 :     return merged_mset;
     713                 :            : #else
     714                 :            :     return local_mset;
     715                 :            : #endif
     716                 :            : }

Generated by: LCOV version 1.11