LCOV - code coverage report
Current view: top level - expand - esetinternal.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 7822d31adece Lines: 58 79 73.4 %
Date: 2019-05-23 11:15:29 Functions: 10 13 76.9 %
Branches: 49 110 44.5 %

           Branch data     Line data    Source code
       1                 :            : /** @file esetinternal.cc
       2                 :            :  * @brief Xapian::ESet::Internal class
       3                 :            :  */
       4                 :            : /* Copyright (C) 2008,2010,2011,2013,2016,2017,2018 Olly Betts
       5                 :            :  * Copyright (C) 2011 Action Without Borders
       6                 :            :  *
       7                 :            :  * This program is free software; you can redistribute it and/or modify
       8                 :            :  * it under the terms of the GNU General Public License as published by
       9                 :            :  * the Free Software Foundation; either version 2 of the License, or
      10                 :            :  * (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 "esetinternal.h"
      25                 :            : 
      26                 :            : #include "xapian/enquire.h"
      27                 :            : #include "xapian/expanddecider.h"
      28                 :            : #include "backends/databaseinternal.h"
      29                 :            : #include "backends/multi.h"
      30                 :            : #include "debuglog.h"
      31                 :            : #include "api/rsetinternal.h"
      32                 :            : #include "expandweight.h"
      33                 :            : #include "heap.h"
      34                 :            : #include "omassert.h"
      35                 :            : #include "ortermlist.h"
      36                 :            : #include "str.h"
      37                 :            : #include "api/termlist.h"
      38                 :            : #include "termlistmerger.h"
      39                 :            : #include "unicode/description_append.h"
      40                 :            : 
      41                 :            : #include <memory>
      42                 :            : #include <set>
      43                 :            : #include <string>
      44                 :            : #include <vector>
      45                 :            : 
      46                 :            : using namespace std;
      47                 :            : 
      48                 :            : namespace Xapian {
      49                 :            : 
      50                 :            : string
      51                 :          0 : Internal::ExpandTerm::get_description() const
      52                 :            : {
      53         [ #  # ]:          0 :     string desc("ExpandTerm(");
      54 [ #  # ][ #  # ]:          0 :     desc += str(wt);
      55         [ #  # ]:          0 :     desc += ", ";
      56         [ #  # ]:          0 :     description_append(desc, term);
      57         [ #  # ]:          0 :     desc += ')';
      58                 :          0 :     return desc;
      59                 :            : }
      60                 :            : 
      61                 :            : template<class CLASS> struct delete_ptr {
      62         [ #  # ]:          0 :     void operator()(CLASS *p) const { delete p; }
      63                 :            : };
      64                 :            : 
      65                 :            : /** Build a tree of binary TermList objects like QueryOptimiser does for
      66                 :            :  *  OrPostList objects.
      67                 :            :  */
      68                 :            : static TermList *
      69                 :        214 : build_termlist_tree(const Xapian::Database &db, const RSet & rset)
      70                 :            : {
      71                 :            :     Assert(!rset.empty());
      72                 :            : 
      73                 :        214 :     const set<Xapian::docid> & docids = rset.internal->docs;
      74                 :            : 
      75                 :        214 :     vector<TermList*> termlists;
      76         [ +  - ]:        214 :     termlists.reserve(docids.size());
      77                 :            : 
      78                 :            :     try {
      79         [ +  + ]:        558 :         for (Xapian::docid did : docids) {
      80 [ +  - ][ +  - ]:        344 :             termlists.push_back(db.internal->open_term_list_direct(did));
      81                 :            :         }
      82                 :            :         Assert(!termlists.empty());
      83         [ +  - ]:        428 :         return make_termlist_merger(termlists);
      84                 :          0 :     } catch (...) {
      85         [ #  # ]:          0 :         for_each(termlists.begin(), termlists.end(), delete_ptr<TermList>());
      86                 :          0 :         throw;
      87                 :        214 :     }
      88                 :            : }
      89                 :            : 
      90                 :            : void
      91                 :        214 : ESet::Internal::expand(Xapian::termcount max_esize,
      92                 :            :                        const Xapian::Database & db,
      93                 :            :                        const RSet & rset,
      94                 :            :                        const Xapian::ExpandDecider * edecider,
      95                 :            :                        Xapian::Internal::ExpandWeight & eweight,
      96                 :            :                        double min_wt)
      97                 :            : {
      98                 :            :     LOGCALL_VOID(EXPAND, "ESet::Internal::expand", max_esize | db | rset | edecider | eweight);
      99                 :            :     // These two cases are handled by our caller.
     100                 :            :     Assert(max_esize);
     101                 :            :     Assert(!rset.empty());
     102                 :            :     // This method should only be called once for a given ESet::Internal, so
     103                 :            :     // check we're empty.
     104                 :            :     Assert(ebound == 0);
     105                 :            :     Assert(items.empty());
     106                 :            : 
     107         [ +  - ]:        214 :     unique_ptr<TermList> tree(build_termlist_tree(db, rset));
     108                 :            :     Assert(tree.get());
     109                 :            : 
     110                 :        214 :     bool is_heap = false;
     111                 :            :     while (true) {
     112                 :            :         // See if the root needs replacing.
     113         [ +  - ]:       9618 :         TermList * new_root = tree->next();
     114         [ +  + ]:       9618 :         if (new_root) {
     115                 :            :             LOGLINE(EXPAND, "Replacing the root of the termlist tree");
     116                 :        130 :             tree.reset(new_root);
     117                 :            :         }
     118                 :            : 
     119 [ +  - ][ +  + ]:       9618 :         if (tree->at_end()) break;
     120                 :            : 
     121         [ +  - ]:       9404 :         string term = tree->get_termname();
     122                 :            : 
     123                 :            :         // If there's an ExpandDecider, see if it accepts the term.
     124 [ +  + ][ +  - ]:       9404 :         if (edecider && !(*edecider)(term)) continue;
         [ +  + ][ +  + ]
     125                 :            : 
     126                 :       8611 :         ++ebound;
     127                 :            : 
     128                 :            :         /* Set up the ExpandWeight by clearing the existing statistics and
     129                 :            :            collecting statistics for the new term. */
     130         [ +  - ]:       8611 :         eweight.collect_stats(tree.get(), term);
     131                 :            : 
     132         [ +  - ]:       8611 :         double wt = eweight.get_weight();
     133                 :            : 
     134                 :            :         // If the weights are equal, we prefer the lexically smaller term and
     135                 :            :         // since we process terms in ascending order we use "<=" not "<" here.
     136         [ +  + ]:       8611 :         if (wt <= min_wt) continue;
     137                 :            : 
     138         [ +  + ]:       4301 :         if (items.size() < max_esize) {
     139         [ +  - ]:       3648 :             items.emplace_back(wt, term);
     140                 :       3648 :             continue;
     141                 :            :         }
     142                 :            : 
     143                 :            :         // We have the desired number of items, so it's one-in one-out from
     144                 :            :         // now on.
     145                 :            :         Assert(items.size() == max_esize);
     146         [ +  + ]:        653 :         if (rare(!is_heap)) {
     147                 :            :             Heap::make(items.begin(), items.end(),
     148         [ +  - ]:        133 :                        std::less<Xapian::Internal::ExpandTerm>());
     149                 :        133 :             min_wt = items.front().wt;
     150                 :        133 :             is_heap = true;
     151         [ +  + ]:        133 :             if (wt <= min_wt) continue;
     152                 :            :         }
     153                 :            : 
     154 [ +  - ][ +  - ]:        604 :         items.front() = Xapian::Internal::ExpandTerm(wt, term);
     155                 :            :         Heap::replace(items.begin(), items.end(),
     156         [ +  - ]:        604 :                       std::less<Xapian::Internal::ExpandTerm>());
     157         [ +  + ]:       9404 :         min_wt = items.front().wt;
     158                 :       9404 :     }
     159                 :            : 
     160                 :            :     // Now sort the contents of the new ESet.
     161         [ +  + ]:        214 :     if (is_heap) {
     162                 :            :         Heap::sort(items.begin(), items.end(),
     163         [ +  - ]:        133 :                    std::less<Xapian::Internal::ExpandTerm>());
     164                 :            :     } else {
     165         [ +  - ]:         81 :         sort(items.begin(), items.end());
     166                 :        214 :     }
     167                 :        214 : }
     168                 :            : 
     169                 :            : string
     170                 :          0 : ESet::Internal::get_description() const
     171                 :            : {
     172         [ #  # ]:          0 :     string desc("ESet::Internal(ebound=");
     173 [ #  # ][ #  # ]:          0 :     desc += str(ebound);
     174                 :            : 
     175                 :          0 :     vector<Xapian::Internal::ExpandTerm>::const_iterator i;
     176         [ #  # ]:          0 :     for (i = items.begin(); i != items.end(); ++i) {
     177         [ #  # ]:          0 :         desc += ", ";
     178 [ #  # ][ #  # ]:          0 :         desc += i->get_description();
     179                 :            :     }
     180         [ #  # ]:          0 :     desc += ')';
     181                 :            : 
     182                 :          0 :     return desc;
     183                 :            : }
     184                 :            : 
     185                 :        460 : ESet::ESet() : internal(new ESet::Internal) {}
     186                 :            : 
     187                 :            : ESet::ESet(const ESet &) = default;
     188                 :            : 
     189                 :            : ESet&
     190                 :            : ESet::operator=(const ESet &) = default;
     191                 :            : 
     192                 :            : ESet::ESet(ESet &&) = default;
     193                 :            : 
     194                 :            : ESet&
     195                 :            : ESet::operator=(ESet &&) = default;
     196                 :            : 
     197                 :       7564 : ESet::~ESet() { }
     198                 :            : 
     199                 :            : Xapian::doccount
     200                 :        414 : ESet::size() const
     201                 :            : {
     202                 :        414 :     return internal->items.size();
     203                 :            : }
     204                 :            : 
     205                 :            : Xapian::termcount
     206                 :         56 : ESet::get_ebound() const
     207                 :            : {
     208                 :         56 :     return internal->ebound;
     209                 :            : }
     210                 :            : 
     211                 :            : std::string
     212                 :          5 : ESet::get_description() const
     213                 :            : {
     214         [ +  - ]:          5 :     string desc = "ESet(";
     215         [ +  - ]:          5 :     desc += ')';
     216                 :          5 :     return desc;
     217                 :            : }
     218                 :            : 
     219                 :            : 
     220                 :            : std::string
     221                 :       3067 : ESetIterator::operator*() const
     222                 :            : {
     223                 :            :     Assert(off_from_end != 0);
     224                 :            :     AssertRel(off_from_end, <=, eset.internal->items.size());
     225         [ +  - ]:       3067 :     return (eset.internal->items.end() - off_from_end)->get_term();
     226                 :            : }
     227                 :            : 
     228                 :            : double
     229                 :       1067 : ESetIterator::get_weight() const
     230                 :            : {
     231                 :            :     Assert(off_from_end != 0);
     232                 :            :     AssertRel(off_from_end, <=, eset.internal->items.size());
     233                 :       1067 :     return (eset.internal->items.end() - off_from_end)->get_weight();
     234                 :            : }
     235                 :            : 
     236                 :            : std::string
     237                 :          5 : ESetIterator::get_description() const
     238                 :            : {
     239         [ +  - ]:          5 :     string desc = "ESetIterator(";
     240         [ +  - ]:          5 :     if (off_from_end == 0) {
     241         [ +  - ]:          5 :         desc += "end";
     242                 :            :     } else {
     243 [ #  # ][ #  # ]:          0 :         desc += str(eset.internal->items.size() - off_from_end);
     244                 :            :     }
     245         [ +  - ]:          5 :     desc += ')';
     246                 :          5 :     return desc;
     247                 :            : }
     248                 :            : 
     249                 :            : }

Generated by: LCOV version 1.11