LCOV - code coverage report
Current view: top level - matcher - orpostlist.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core c2b6f1024d3a Lines: 203 232 87.5 %
Date: 2019-05-16 09:13:18 Functions: 17 18 94.4 %
Branches: 148 202 73.3 %

           Branch data     Line data    Source code
       1                 :            : /** @file orpostlist.cc
       2                 :            :  * @brief PostList class implementing Query::OP_OR
       3                 :            :  */
       4                 :            : /* Copyright 2017 Olly Betts
       5                 :            :  *
       6                 :            :  * This program is free software; you can redistribute it and/or
       7                 :            :  * modify it under the terms of the GNU General Public License as
       8                 :            :  * published by the Free Software Foundation; either version 2 of the
       9                 :            :  * License, or (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 "orpostlist.h"
      24                 :            : 
      25                 :            : #include "andmaybepostlist.h"
      26                 :            : #include "min_non_zero.h"
      27                 :            : #include "multiandpostlist.h"
      28                 :            : #include "postlisttree.h"
      29                 :            : 
      30                 :            : #include <algorithm>
      31                 :            : 
      32                 :            : using namespace std;
      33                 :            : 
      34                 :            : PostList*
      35                 :         81 : OrPostList::decay_to_and(Xapian::docid did,
      36                 :            :                          double w_min,
      37                 :            :                          bool* valid_ptr)
      38                 :            : {
      39         [ +  - ]:         81 :     l = new MultiAndPostList(l, r, l_max, r_max, pltree, db_size);
      40                 :         81 :     r = NULL;
      41                 :            :     PostList* result;
      42         [ -  + ]:         81 :     if (valid_ptr) {
      43                 :          0 :         result = l->check(did, w_min, *valid_ptr);
      44                 :            :     } else {
      45                 :         81 :         result = l->skip_to(did, w_min);
      46                 :            :     }
      47         [ +  - ]:         81 :     if (!result) {
      48                 :         81 :         result = l;
      49                 :         81 :         l = NULL;
      50                 :            :     }
      51                 :         81 :     pltree->force_recalc();
      52                 :         81 :     return result;
      53                 :            : }
      54                 :            : 
      55                 :            : PostList*
      56                 :        117 : OrPostList::decay_to_andmaybe(PostList* left,
      57                 :            :                               PostList* right,
      58                 :            :                               Xapian::docid did,
      59                 :            :                               double w_min,
      60                 :            :                               bool* valid_ptr)
      61                 :            : {
      62         [ +  + ]:        117 :     if (l != left) swap(l_max, r_max);
      63                 :        117 :     l = new AndMaybePostList(left, right, l_max, r_max, pltree, db_size);
      64                 :        117 :     r = NULL;
      65                 :            :     PostList* result;
      66         [ -  + ]:        117 :     if (valid_ptr) {
      67                 :          0 :         result = l->check(did, w_min, *valid_ptr);
      68                 :            :     } else {
      69                 :        117 :         result = l->skip_to(did, w_min);
      70                 :            :     }
      71         [ +  + ]:        117 :     if (!result) {
      72                 :         93 :         result = l;
      73                 :         93 :         l = NULL;
      74                 :            :     }
      75                 :        117 :     pltree->force_recalc();
      76                 :        117 :     return result;
      77                 :            : }
      78                 :            : 
      79                 :            : Xapian::doccount
      80                 :     142530 : OrPostList::get_termfreq_min() const
      81                 :            : {
      82         [ +  - ]:     142530 :     return max(l->get_termfreq_min(), r->get_termfreq_min());
      83                 :            : }
      84                 :            : 
      85                 :            : Xapian::docid
      86                 :   63278386 : OrPostList::get_docid() const
      87                 :            : {
      88                 :            :     // Handle l_did or r_did being zero correctly (which means the last call on
      89                 :            :     // that side was a check() which came back !valid).
      90                 :   63278386 :     return min_non_zero(l_did, r_did);
      91                 :            : }
      92                 :            : 
      93                 :            : double
      94                 :   35347519 : OrPostList::get_weight(Xapian::termcount doclen,
      95                 :            :                        Xapian::termcount unique_terms) const
      96                 :            : {
      97 [ +  + ][ +  + ]:   35347519 :     if (r_did == 0 || l_did < r_did)
      98                 :   35109252 :         return l->get_weight(doclen, unique_terms);
      99 [ +  - ][ +  + ]:     238267 :     if (l_did == 0 || l_did > r_did)
     100                 :       1051 :         return r->get_weight(doclen, unique_terms);
     101                 :     237216 :     return l->get_weight(doclen, unique_terms) +
     102                 :     237216 :            r->get_weight(doclen, unique_terms);
     103                 :            : }
     104                 :            : 
     105                 :            : double
     106                 :     164043 : OrPostList::recalc_maxweight()
     107                 :            : {
     108                 :     164043 :     l_max = l->recalc_maxweight();
     109                 :     164043 :     r_max = r->recalc_maxweight();
     110                 :     164043 :     return l_max + r_max;
     111                 :            : }
     112                 :            : 
     113                 :            : PostList*
     114                 :   35491066 : OrPostList::next(double w_min)
     115                 :            : {
     116         [ +  + ]:   35491066 :     if (w_min > l_max) {
     117         [ +  + ]:        166 :         if (w_min > r_max) {
     118                 :            :             // Work out the smallest docid which the AND could match at.
     119                 :            :             Xapian::docid did;
     120 [ +  + ][ -  + ]:         81 :             if (l_did == r_did || r_did == 0) {
     121                 :         79 :                 did = l_did + 1;
     122         [ -  + ]:          2 :             } else if (l_did == 0) {
     123                 :          0 :                 did = r_did + 1;
     124                 :            :             } else {
     125                 :            :                 // The OR last matched at min(l_did, r_did), so the AND could
     126                 :            :                 // match at the max().
     127                 :          2 :                 did = max(l_did, r_did);
     128                 :            :             }
     129                 :         81 :             return decay_to_and(did, w_min);
     130                 :            :         }
     131                 :            :         // Work out the smallest docid which r AND_MAYBE l could match at.
     132                 :            :         Xapian::docid did;
     133         [ +  + ]:         85 :         if (r_did == 0) {
     134                 :          8 :             did = l_did + 1;
     135         [ +  + ]:         77 :         } else if (l_did - 1 >= r_did - 1) {
     136                 :         75 :             did = r_did + 1;
     137                 :            :         } else {
     138                 :            :             // l_did and r_did both non zero and l_did < r_did.
     139                 :          2 :             did = r_did;
     140                 :            :         }
     141                 :         85 :         return decay_to_andmaybe(r, l, did, w_min);
     142                 :            :     }
     143         [ +  + ]:   35490900 :     if (w_min > r_max) {
     144                 :            :         // Work out the smallest docid which l AND_MAYBE r could match at.
     145                 :            :         Xapian::docid did;
     146         [ +  + ]:         16 :         if (l_did == 0) {
     147                 :          9 :             did = r_did + 1;
     148         [ +  - ]:          7 :         } else if (r_did - 1 >= l_did - 1) {
     149                 :          7 :             did = l_did + 1;
     150                 :            :         } else {
     151                 :            :             // l_did and r_did both non zero and r_did < l_did.
     152                 :          0 :             did = l_did;
     153                 :            :         }
     154                 :         16 :         return decay_to_andmaybe(l, r, did, w_min);
     155                 :            :     }
     156                 :            : 
     157                 :            :     // We always advance_l if l_did is 0, and similarly for advance_r.
     158                 :   35490884 :     bool advance_l = (l_did <= r_did);
     159                 :   35490884 :     bool advance_r = (l_did >= r_did);
     160                 :            : 
     161         [ +  + ]:   35490884 :     if (advance_l) {
     162                 :   35489515 :         PostList* result = l->next(w_min - r_max);
     163         [ +  + ]:   35489515 :         if (result) {
     164         [ +  - ]:       1057 :             delete l;
     165                 :   35489515 :             l = result;
     166                 :            :         }
     167                 :            :     }
     168                 :            : 
     169         [ +  + ]:   35490884 :     if (advance_r) {
     170                 :     380728 :         PostList* result = r->next(w_min - l_max);
     171         [ +  + ]:     380728 :         if (result) {
     172         [ +  - ]:       1329 :             delete r;
     173                 :     380728 :             r = result;
     174                 :            :         }
     175                 :            :     }
     176                 :            : 
     177         [ +  + ]:   35490884 :     if (advance_l) {
     178         [ +  + ]:   35489515 :         if (l->at_end()) {
     179                 :       2872 :             PostList* result = r;
     180                 :       2872 :             r = NULL;
     181                 :       2872 :             pltree->force_recalc();
     182                 :   35489515 :             return result;
     183                 :            :         }
     184                 :            :     }
     185                 :            : 
     186         [ +  + ]:   35488012 :     if (advance_r) {
     187         [ +  + ]:     378069 :         if (r->at_end()) {
     188                 :     139276 :             PostList* result = l;
     189                 :     139276 :             l = NULL;
     190                 :     139276 :             pltree->force_recalc();
     191                 :     378069 :             return result;
     192                 :            :         }
     193                 :            :     }
     194                 :            : 
     195         [ +  + ]:   35348736 :     if (advance_l) {
     196                 :   35347778 :         l_did = l->get_docid();
     197                 :            :     }
     198                 :            : 
     199         [ +  + ]:   35348736 :     if (advance_r) {
     200                 :     238793 :         r_did = r->get_docid();
     201                 :            :     }
     202                 :            : 
     203                 :   35348736 :     return NULL;
     204                 :            : }
     205                 :            : 
     206                 :            : PostList*
     207                 :       1163 : OrPostList::skip_to(Xapian::docid did, double w_min)
     208                 :            : {
     209                 :            :     // We always advance_l if l_did is 0, and similarly for advance_r.
     210                 :       1163 :     bool advance_l = (did > l_did);
     211                 :       1163 :     bool advance_r = (did > r_did);
     212 [ +  + ][ -  + ]:       1163 :     if (!advance_l && !advance_r)
     213                 :          0 :         return NULL;
     214                 :            : 
     215         [ +  + ]:       1163 :     if (w_min > l_max) {
     216         [ -  + ]:         16 :         if (w_min > r_max)
     217                 :          0 :             return decay_to_and(did, w_min);
     218                 :         16 :         return decay_to_andmaybe(r, l, did, w_min);
     219                 :            :     }
     220         [ -  + ]:       1147 :     if (w_min > r_max) {
     221                 :          0 :         return decay_to_andmaybe(l, r, did, w_min);
     222                 :            :     }
     223                 :            : 
     224         [ +  + ]:       1147 :     if (advance_l) {
     225                 :       1005 :         PostList* result = l->skip_to(did, w_min - r_max);
     226         [ +  + ]:       1005 :         if (result) {
     227         [ +  - ]:         60 :             delete l;
     228                 :       1005 :             l = result;
     229                 :            :         }
     230                 :            :     }
     231                 :            : 
     232         [ +  + ]:       1147 :     if (advance_r) {
     233                 :        543 :         PostList* result = r->skip_to(did, w_min - l_max);
     234         [ +  + ]:        543 :         if (result) {
     235         [ +  - ]:          4 :             delete r;
     236                 :        543 :             r = result;
     237                 :            :         }
     238                 :            :     }
     239                 :            : 
     240         [ +  + ]:       1147 :     if (advance_l) {
     241         [ +  + ]:       1005 :         if (l->at_end()) {
     242                 :         38 :             PostList* result = r;
     243                 :         38 :             r = NULL;
     244                 :         38 :             pltree->force_recalc();
     245                 :       1005 :             return result;
     246                 :            :         }
     247                 :            :     }
     248                 :            : 
     249         [ +  + ]:       1109 :     if (advance_r) {
     250         [ +  + ]:        507 :         if (r->at_end()) {
     251                 :         88 :             PostList* result = l;
     252                 :         88 :             l = NULL;
     253                 :         88 :             pltree->force_recalc();
     254                 :        507 :             return result;
     255                 :            :         }
     256                 :            :     }
     257                 :            : 
     258         [ +  + ]:       1021 :     if (advance_l) {
     259                 :        914 :         l_did = l->get_docid();
     260                 :            :     }
     261                 :            : 
     262         [ +  + ]:       1021 :     if (advance_r) {
     263                 :        419 :         r_did = r->get_docid();
     264                 :            :     }
     265                 :            : 
     266                 :       1021 :     return NULL;
     267                 :            : }
     268                 :            : 
     269                 :            : PostList*
     270                 :         75 : OrPostList::check(Xapian::docid did, double w_min, bool& valid)
     271                 :            : {
     272                 :         75 :     bool advance_l = (did > l_did);
     273                 :         75 :     bool advance_r = (did > r_did);
     274 [ +  + ][ +  + ]:         75 :     if (!advance_l && !advance_r) {
     275                 :            :         // A call to check() which steps back isn't valid, so if we get here
     276                 :            :         // then did should be equal to at least one of l_did or r_did.
     277                 :            :         Assert(did == l_did || did == r_did);
     278                 :         10 :         valid = true;
     279                 :         10 :         return NULL;
     280                 :            :     }
     281                 :            : 
     282         [ -  + ]:         65 :     if (w_min > l_max) {
     283                 :          0 :         valid = true;
     284         [ #  # ]:          0 :         if (w_min > r_max)
     285                 :          0 :             return decay_to_and(did, w_min, &valid);
     286                 :          0 :         return decay_to_andmaybe(r, l, did, w_min, &valid);
     287                 :            :     }
     288         [ -  + ]:         65 :     if (w_min > r_max) {
     289                 :          0 :         valid = true;
     290                 :          0 :         return decay_to_andmaybe(l, r, did, w_min, &valid);
     291                 :            :     }
     292                 :            : 
     293         [ +  + ]:         65 :     if (advance_l) {
     294                 :            :         bool l_valid;
     295         [ +  - ]:         56 :         PostList* result = l->check(did, w_min - r_max, l_valid);
     296         [ -  + ]:         56 :         if (result) {
     297                 :            :             Assert(l_valid);
     298         [ #  # ]:          0 :             delete l;
     299                 :          0 :             l = result;
     300         [ +  + ]:         56 :         } else if (!l_valid) {
     301                 :          7 :             l_did = 0;
     302                 :         56 :             advance_l = false;
     303                 :            :         }
     304                 :            :     }
     305                 :            : 
     306         [ +  + ]:         65 :     if (advance_r) {
     307                 :            :         bool r_valid;
     308         [ +  - ]:         55 :         PostList* result = r->check(did, w_min - l_max, r_valid);
     309         [ -  + ]:         55 :         if (result) {
     310                 :            :             Assert(r_valid);
     311         [ #  # ]:          0 :             delete r;
     312                 :          0 :             r = result;
     313         [ +  + ]:         55 :         } else if (!r_valid) {
     314                 :          8 :             r_did = 0;
     315                 :         55 :             advance_r = false;
     316                 :            :         }
     317                 :            :     }
     318                 :            : 
     319         [ +  + ]:         65 :     if (advance_l) {
     320         [ -  + ]:         49 :         if (l->at_end()) {
     321                 :          0 :             PostList* result = r;
     322                 :          0 :             r = NULL;
     323                 :          0 :             pltree->force_recalc();
     324                 :          0 :             valid = true;
     325                 :         49 :             return result;
     326                 :            :         }
     327                 :            :     }
     328                 :            : 
     329         [ +  + ]:         65 :     if (advance_r) {
     330         [ +  + ]:         47 :         if (r->at_end()) {
     331                 :          3 :             PostList* result = l;
     332                 :          3 :             l = NULL;
     333                 :          3 :             pltree->force_recalc();
     334                 :          3 :             valid = true;
     335                 :         47 :             return result;
     336                 :            :         }
     337                 :            :     }
     338                 :            : 
     339         [ +  + ]:         62 :     if (advance_l) {
     340                 :         46 :         l_did = l->get_docid();
     341                 :            :     }
     342                 :            : 
     343         [ +  + ]:         62 :     if (advance_r) {
     344                 :         44 :         r_did = r->get_docid();
     345                 :            :     }
     346                 :            : 
     347 [ +  + ][ +  - ]:         62 :     valid = (l_did == did || r_did == did) || (l_did != 0 && r_did != 0);
         [ +  + ][ +  + ]
     348                 :            : 
     349                 :         75 :     return NULL;
     350                 :            : }
     351                 :            : 
     352                 :            : Xapian::doccount
     353                 :     142783 : OrPostList::get_termfreq_max() const
     354                 :            : {
     355                 :     142783 :     auto l_tf_max = l->get_termfreq_max();
     356                 :     142783 :     auto r_tf_max = r->get_termfreq_max();
     357                 :     142783 :     auto tf_max = l_tf_max + r_tf_max;
     358                 :            :     // If the sum is greater than the number of documents (or would have been
     359                 :            :     // except it overflowed) then we can potentially match all documents.
     360 [ +  + ][ -  + ]:     142783 :     if (tf_max > db_size || tf_max < l_tf_max)
     361                 :       1141 :         tf_max = db_size;
     362                 :     142783 :     return tf_max;
     363                 :            : }
     364                 :            : 
     365                 :            : template<typename T>
     366                 :            : static void
     367                 :     143047 : estimate_or_assuming_indep(double a, double b, double n, T& res)
     368                 :            : {
     369         [ +  + ]:     143047 :     if (rare(n == 0.0)) {
     370                 :         20 :         res = 0;
     371                 :            :     } else {
     372                 :     143027 :         res = static_cast<T>(a + b - (a * b / n) + 0.5);
     373                 :            :     }
     374                 :     143047 : }
     375                 :            : 
     376                 :            : Xapian::doccount
     377                 :     142935 : OrPostList::get_termfreq_est() const
     378                 :            : {
     379         [ +  - ]:     142935 :     auto l_tf_est = l->get_termfreq_est();
     380         [ +  - ]:     142935 :     auto r_tf_est = r->get_termfreq_est();
     381                 :            :     Xapian::doccount tf_est;
     382                 :     142935 :     estimate_or_assuming_indep(l_tf_est, r_tf_est, db_size, tf_est);
     383                 :     142935 :     return tf_est;
     384                 :            : }
     385                 :            : 
     386                 :            : TermFreqs
     387                 :         56 : OrPostList::get_termfreq_est_using_stats(
     388                 :            :         const Xapian::Weight::Internal& stats) const
     389                 :            : {
     390         [ +  - ]:         56 :     const TermFreqs& l_freqs = l->get_termfreq_est_using_stats(stats);
     391         [ +  - ]:         56 :     const TermFreqs& r_freqs = r->get_termfreq_est_using_stats(stats);
     392                 :            : 
     393                 :            :     // Our caller should have ensured this.
     394                 :            :     Assert(stats.collection_size);
     395                 :            :     Xapian::doccount freqest;
     396                 :            :     estimate_or_assuming_indep(l_freqs.termfreq,
     397                 :            :                                r_freqs.termfreq,
     398                 :            :                                stats.collection_size,
     399                 :         56 :                                freqest);
     400                 :            : 
     401                 :         56 :     Xapian::doccount relfreqest = 0;
     402         [ -  + ]:         56 :     if (stats.rset_size != 0) {
     403                 :            :         estimate_or_assuming_indep(l_freqs.reltermfreq,
     404                 :            :                                    r_freqs.reltermfreq,
     405                 :            :                                    stats.rset_size,
     406                 :          0 :                                    relfreqest);
     407                 :            :     }
     408                 :            : 
     409                 :         56 :     Xapian::termcount collfreqest = 0;
     410         [ +  - ]:         56 :     if (stats.total_term_count != 0) {
     411                 :            :         estimate_or_assuming_indep(l_freqs.collfreq,
     412                 :            :                                    r_freqs.collfreq,
     413                 :            :                                    stats.total_term_count,
     414                 :         56 :                                    collfreqest);
     415                 :            :     }
     416                 :            : 
     417                 :         56 :     return TermFreqs(freqest, relfreqest, collfreqest);
     418                 :            : }
     419                 :            : 
     420                 :            : bool
     421                 :   35350133 : OrPostList::at_end() const
     422                 :            : {
     423                 :            :     // We never need to return true here - if one child reaches at_end(), we
     424                 :            :     // prune to leave the other, and if both children reach at_end() together,
     425                 :            :     // we prune to leave one of them which will then indicate at_end() for us.
     426                 :   35350133 :     return false;
     427                 :            : }
     428                 :            : 
     429                 :            : std::string
     430                 :          0 : OrPostList::get_description() const
     431                 :            : {
     432         [ #  # ]:          0 :     string desc = "OrPostList(";
     433 [ #  # ][ #  # ]:          0 :     desc += l->get_description();
     434         [ #  # ]:          0 :     desc += ", ";
     435 [ #  # ][ #  # ]:          0 :     desc += r->get_description();
     436         [ #  # ]:          0 :     desc += ')';
     437                 :          0 :     return desc;
     438                 :            : }
     439                 :            : 
     440                 :            : Xapian::termcount
     441                 :       1751 : OrPostList::get_wdf() const
     442                 :            : {
     443 [ +  - ][ +  + ]:       1751 :     if (r_did == 0 || l_did < r_did)
     444                 :       1029 :         return l->get_wdf();
     445 [ +  - ][ +  + ]:        722 :     if (l_did == 0 || l_did > r_did)
     446                 :        458 :         return r->get_wdf();
     447                 :        264 :     return l->get_wdf() + r->get_wdf();
     448                 :            : }
     449                 :            : 
     450                 :            : Xapian::termcount
     451                 :     856136 : OrPostList::count_matching_subqs() const
     452                 :            : {
     453 [ +  + ][ +  + ]:     856136 :     if (r_did == 0 || l_did < r_did)
     454                 :     622210 :         return l->count_matching_subqs();
     455 [ +  - ][ +  + ]:     233926 :     if (l_did == 0 || l_did > r_did)
     456                 :        522 :         return r->count_matching_subqs();
     457                 :     233404 :     return l->count_matching_subqs() + r->count_matching_subqs();
     458                 :            : }
     459                 :            : 
     460                 :            : void
     461                 :        328 : OrPostList::gather_position_lists(OrPositionList* orposlist)
     462                 :            : {
     463         [ +  + ]:        328 :     if (l_did - 1 <= r_did - 1)
     464                 :        248 :         l->gather_position_lists(orposlist);
     465         [ +  + ]:        328 :     if (l_did - 1 >= r_did - 1)
     466                 :        220 :         r->gather_position_lists(orposlist);
     467                 :        328 : }

Generated by: LCOV version 1.11