LCOV - code coverage report
Current view: top level - api - matchspy.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core fcfb185a9dd5 Lines: 141 167 84.4 %
Date: 2019-04-18 16:33:14 Functions: 39 51 76.5 %
Branches: 98 218 45.0 %

           Branch data     Line data    Source code
       1                 :            : /** @file matchspy.cc
       2                 :            :  * @brief MatchSpy implementation.
       3                 :            :  */
       4                 :            : /* Copyright (C) 2007,2008,2009,2010,2011,2012,2013,2014,2015,2018 Olly Betts
       5                 :            :  * Copyright (C) 2007,2009 Lemur Consulting Ltd
       6                 :            :  * Copyright (C) 2010 Richard Boulton
       7                 :            :  *
       8                 :            :  * This program is free software; you can redistribute it and/or modify
       9                 :            :  * it under the terms of the GNU General Public License as published by
      10                 :            :  * the Free Software Foundation; either version 2 of the License, or
      11                 :            :  * (at your option) any later version.
      12                 :            :  *
      13                 :            :  * This program is distributed in the hope that it will be useful,
      14                 :            :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      15                 :            :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      16                 :            :  * GNU General Public License for more details.
      17                 :            :  *
      18                 :            :  * You should have received a copy of the GNU General Public License
      19                 :            :  * along with this program; if not, write to the Free Software
      20                 :            :  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
      21                 :            :  */
      22                 :            : 
      23                 :            : #include <config.h>
      24                 :            : #include <xapian/matchspy.h>
      25                 :            : 
      26                 :            : #include <xapian/document.h>
      27                 :            : #include <xapian/error.h>
      28                 :            : #include <xapian/queryparser.h>
      29                 :            : #include <xapian/registry.h>
      30                 :            : 
      31                 :            : #include <map>
      32                 :            : #include <memory>
      33                 :            : #include <string>
      34                 :            : #include <vector>
      35                 :            : 
      36                 :            : #include "debuglog.h"
      37                 :            : #include "heap.h"
      38                 :            : #include "omassert.h"
      39                 :            : #include "net/length.h"
      40                 :            : #include "stringutils.h"
      41                 :            : #include "str.h"
      42                 :            : #include "termlist.h"
      43                 :            : 
      44                 :            : #include <cfloat>
      45                 :            : #include <cmath>
      46                 :            : 
      47                 :            : using namespace std;
      48                 :            : using namespace Xapian;
      49                 :            : using Xapian::Internal::intrusive_ptr;
      50                 :            : 
      51         [ -  + ]:       3044 : MatchSpy::~MatchSpy() {}
      52                 :            : 
      53                 :            : MatchSpy *
      54                 :          1 : MatchSpy::clone() const {
      55 [ +  - ][ +  - ]:          1 :     throw UnimplementedError("MatchSpy not suitable for use with remote searches - clone() method unimplemented");
                 [ +  - ]
      56                 :            : }
      57                 :            : 
      58                 :            : string
      59                 :          1 : MatchSpy::name() const {
      60 [ +  - ][ +  - ]:          1 :     throw UnimplementedError("MatchSpy not suitable for use with remote searches - name() method unimplemented");
                 [ +  - ]
      61                 :            : }
      62                 :            : 
      63                 :            : string
      64                 :          1 : MatchSpy::serialise() const {
      65 [ +  - ][ +  - ]:          1 :     throw UnimplementedError("MatchSpy not suitable for use with remote searches - serialise() method unimplemented");
                 [ +  - ]
      66                 :            : }
      67                 :            : 
      68                 :            : MatchSpy *
      69                 :          1 : MatchSpy::unserialise(const string &, const Registry &) const {
      70 [ +  - ][ +  - ]:          1 :     throw UnimplementedError("MatchSpy not suitable for use with remote searches - unserialise() method unimplemented");
                 [ +  - ]
      71                 :            : }
      72                 :            : 
      73                 :            : string
      74                 :          1 : MatchSpy::serialise_results() const {
      75 [ +  - ][ +  - ]:          1 :     throw UnimplementedError("MatchSpy not suitable for use with remote searches - serialise_results() method unimplemented");
                 [ +  - ]
      76                 :            : }
      77                 :            : 
      78                 :            : void
      79                 :          1 : MatchSpy::merge_results(const string &) {
      80 [ +  - ][ +  - ]:          1 :     throw UnimplementedError("MatchSpy not suitable for use with remote searches - merge_results() method unimplemented");
                 [ +  - ]
      81                 :            : }
      82                 :            : 
      83                 :            : string
      84                 :          1 : MatchSpy::get_description() const {
      85         [ +  - ]:          1 :     return "Xapian::MatchSpy()";
      86                 :            : }
      87                 :            : 
      88                 :            : [[noreturn]]
      89                 :          0 : static void unsupported_method() {
      90 [ #  # ][ #  # ]:          0 :     throw Xapian::InvalidOperationError("Method not supported for this type of termlist");
                 [ #  # ]
      91                 :            : }
      92                 :            : 
      93                 :            : /// A termlist iterator over the contents of a ValueCountMatchSpy
      94         [ -  + ]:         92 : class ValueCountTermList : public TermList {
      95                 :            :   private:
      96                 :            :     map<string, Xapian::doccount>::const_iterator it;
      97                 :            :     bool started;
      98                 :            :     intrusive_ptr<Xapian::ValueCountMatchSpy::Internal> spy;
      99                 :            :   public:
     100                 :            : 
     101                 :         23 :     explicit ValueCountTermList(ValueCountMatchSpy::Internal * spy_)
     102                 :         23 :         : spy(spy_)
     103                 :            :     {
     104                 :         23 :         it = spy->values.begin();
     105                 :         23 :         started = false;
     106                 :         23 :     }
     107                 :            : 
     108                 :         85 :     string get_termname() const {
     109                 :            :         Assert(started);
     110                 :            :         Assert(!at_end());
     111                 :         85 :         return it->first;
     112                 :            :     }
     113                 :            : 
     114                 :         85 :     Xapian::doccount get_termfreq() const {
     115                 :            :         Assert(started);
     116                 :            :         Assert(!at_end());
     117                 :         85 :         return it->second;
     118                 :            :     }
     119                 :            : 
     120                 :        108 :     TermList * next() {
     121         [ +  + ]:        108 :         if (!started) {
     122                 :         23 :             started = true;
     123                 :            :         } else {
     124                 :            :             Assert(!at_end());
     125                 :         85 :             ++it;
     126                 :            :         }
     127                 :        108 :         return NULL;
     128                 :            :     }
     129                 :            : 
     130                 :          0 :     TermList * skip_to(const string & term) {
     131 [ #  # ][ #  # ]:          0 :         while (it != spy->values.end() && it->first < term) {
         [ #  # ][ #  # ]
         [ #  # ][ #  #  
             #  #  #  # ]
     132                 :          0 :             ++it;
     133                 :            :         }
     134                 :          0 :         started = true;
     135                 :          0 :         return NULL;
     136                 :            :     }
     137                 :            : 
     138                 :        108 :     bool at_end() const {
     139                 :            :         Assert(started);
     140                 :        108 :         return it == spy->values.end();
     141                 :            :     }
     142                 :            : 
     143                 :          0 :     Xapian::termcount get_approx_size() const { unsupported_method(); return 0; }
     144                 :          0 :     Xapian::termcount get_wdf() const { unsupported_method(); return 0; }
     145                 :          0 :     PositionList* positionlist_begin() const {
     146                 :          0 :         unsupported_method();
     147                 :            :         return NULL;
     148                 :            :     }
     149                 :          0 :     Xapian::termcount positionlist_count() const { unsupported_method(); return 0; }
     150                 :            : };
     151                 :            : 
     152                 :            : /** A string with a corresponding frequency.
     153                 :            :  */
     154                 :      15756 : class StringAndFrequency {
     155                 :            :     std::string str;
     156                 :            :     Xapian::doccount frequency;
     157                 :            :   public:
     158                 :            :     /// Construct a StringAndFrequency object.
     159                 :       1836 :     StringAndFrequency(const std::string & str_, Xapian::doccount frequency_)
     160                 :       1836 :             : str(str_), frequency(frequency_) {}
     161                 :            : 
     162                 :            :     /// Return the string.
     163                 :       8340 :     std::string get_string() const { return str; }
     164                 :            : 
     165                 :            :     /// Return the frequency.
     166                 :      26916 :     Xapian::doccount get_frequency() const { return frequency; }
     167                 :            : };
     168                 :            : 
     169                 :            : /** Compare two StringAndFrequency objects.
     170                 :            :  *
     171                 :            :  *  The comparison is firstly by frequency (higher is better), then by string
     172                 :            :  *  (earlier lexicographic sort is better).
     173                 :            :  */
     174                 :            : class StringAndFreqCmpByFreq {
     175                 :            :   public:
     176                 :            :     /// Default constructor
     177                 :        228 :     StringAndFreqCmpByFreq() {}
     178                 :            : 
     179                 :            :     /// Return true if a has a higher frequency than b.
     180                 :            :     /// If equal, compare by the str, to provide a stable sort order.
     181                 :       3582 :     bool operator()(const StringAndFrequency &a,
     182                 :            :                     const StringAndFrequency &b) const {
     183         [ +  + ]:       3582 :         if (a.get_frequency() > b.get_frequency()) return true;
     184         [ +  + ]:       2688 :         if (a.get_frequency() < b.get_frequency()) return false;
     185 [ +  - ][ +  - ]:       3582 :         return a.get_string() < b.get_string();
     186                 :            :     }
     187                 :            : };
     188                 :            : 
     189                 :            : /// A termlist iterator over a vector of StringAndFrequency objects.
     190         [ -  + ]:       1368 : class StringAndFreqTermList : public TermList {
     191                 :            :   private:
     192                 :            :     vector<StringAndFrequency>::const_iterator it;
     193                 :            :     bool started;
     194                 :            :   public:
     195                 :            :     vector<StringAndFrequency> values;
     196                 :            : 
     197                 :            :     /** init should be called after the values have been set, but before
     198                 :            :      *  iteration begins.
     199                 :            :      */
     200                 :        228 :     void init() {
     201                 :        228 :         it = values.begin();
     202                 :        228 :         started = false;
     203                 :        228 :     }
     204                 :            : 
     205                 :        918 :     string get_termname() const {
     206                 :            :         Assert(started);
     207                 :            :         Assert(!at_end());
     208                 :        918 :         return it->get_string();
     209                 :            :     }
     210                 :            : 
     211                 :        918 :     Xapian::doccount get_termfreq() const {
     212                 :            :         Assert(started);
     213                 :            :         Assert(!at_end());
     214                 :        918 :         return it->get_frequency();
     215                 :            :     }
     216                 :            : 
     217                 :       1146 :     TermList * next() {
     218         [ +  + ]:       1146 :         if (!started) {
     219                 :        228 :             started = true;
     220                 :            :         } else {
     221                 :            :             Assert(!at_end());
     222                 :        918 :             ++it;
     223                 :            :         }
     224                 :       1146 :         return NULL;
     225                 :            :     }
     226                 :            : 
     227                 :          0 :     TermList * skip_to(const string & term) {
     228 [ #  # ][ #  # ]:          0 :         while (it != values.end() && it->get_string() < term) {
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
           [ #  #  #  #  
                   #  # ]
     229                 :          0 :             ++it;
     230                 :            :         }
     231                 :          0 :         started = true;
     232                 :          0 :         return NULL;
     233                 :            :     }
     234                 :            : 
     235                 :       1146 :     bool at_end() const {
     236                 :            :         Assert(started);
     237                 :       1146 :         return it == values.end();
     238                 :            :     }
     239                 :            : 
     240                 :          0 :     Xapian::termcount get_approx_size() const { unsupported_method(); return 0; }
     241                 :          0 :     Xapian::termcount get_wdf() const { unsupported_method(); return 0; }
     242                 :          0 :     PositionList* positionlist_begin() const {
     243                 :          0 :         unsupported_method();
     244                 :            :         return NULL;
     245                 :            :     }
     246                 :          0 :     Xapian::termcount positionlist_count() const { unsupported_method(); return 0; }
     247                 :            : };
     248                 :            : 
     249                 :            : /** Get the most frequent items from a map from string to frequency.
     250                 :            :  *
     251                 :            :  *  This takes input such as that in ValueCountMatchSpy::Internal::values and
     252                 :            :  *  returns a vector of the most frequent items in the input.
     253                 :            :  *
     254                 :            :  *  @param result A vector which will be filled with the most frequent
     255                 :            :  *                items, in descending order of frequency.  Items with
     256                 :            :  *                the same frequency will be sorted in ascending
     257                 :            :  *                alphabetical order.
     258                 :            :  *
     259                 :            :  *  @param items The map from string to frequency, from which the most
     260                 :            :  *               frequent items will be selected.
     261                 :            :  *
     262                 :            :  *  @param maxitems The maximum number of items to return (non-zero).
     263                 :            :  */
     264                 :            : static void
     265                 :        228 : get_most_frequent_items(vector<StringAndFrequency> & result,
     266                 :            :                         const map<string, doccount> & items,
     267                 :            :                         size_t maxitems)
     268                 :            : {
     269                 :            :     Assert(maxitems != 0);
     270                 :        228 :     result.clear();
     271         [ +  - ]:        228 :     result.reserve(maxitems);
     272                 :        228 :     StringAndFreqCmpByFreq cmpfn;
     273                 :        228 :     bool is_heap = false;
     274                 :            : 
     275         [ +  + ]:       4128 :     for (map<string, doccount>::const_iterator i = items.begin();
     276                 :       2064 :          i != items.end(); ++i) {
     277         [ +  + ]:       1836 :         if (result.size() < maxitems) {
     278         [ +  - ]:       1434 :             result.emplace_back(i->first, i->second);
     279                 :       1764 :             continue;
     280                 :            :         }
     281                 :            : 
     282                 :            :         // We have the desired number of items, so it's one-in one-out from
     283                 :            :         // now on.
     284                 :            :         Assert(result.size() == maxitems);
     285         [ +  + ]:        402 :         if (!is_heap) {
     286         [ +  - ]:         96 :             Heap::make(result.begin(), result.end(), cmpfn);
     287                 :         96 :             is_heap = true;
     288                 :            :         }
     289                 :            : 
     290         [ +  - ]:        402 :         StringAndFrequency new_item(i->first, i->second);
     291 [ +  - ][ +  + ]:        402 :         if (!cmpfn(new_item, result[0])) {
     292                 :            :             // The candidate is worse than the worst of the current top N.
     293                 :        330 :             continue;
     294                 :            :         }
     295                 :            : 
     296         [ +  - ]:         72 :         result[0] = std::move(new_item);
     297 [ +  - ][ +  + ]:        402 :         Heap::replace(result.begin(), result.end(), cmpfn);
     298                 :         72 :     }
     299                 :            : 
     300         [ +  + ]:        228 :     if (is_heap) {
     301         [ +  - ]:         96 :         Heap::sort(result.begin(), result.end(), cmpfn);
     302                 :            :     } else {
     303         [ +  - ]:        132 :         sort(result.begin(), result.end(), cmpfn);
     304                 :            :     }
     305                 :        228 : }
     306                 :            : 
     307                 :            : void
     308                 :        759 : ValueCountMatchSpy::operator()(const Document &doc, double) {
     309                 :            :     Assert(internal.get());
     310                 :        759 :     ++(internal->total);
     311         [ +  - ]:        759 :     string val(doc.get_value(internal->slot));
     312 [ +  - ][ +  - ]:        759 :     if (!val.empty()) ++(internal->values[val]);
     313                 :        759 : }
     314                 :            : 
     315                 :            : TermIterator
     316                 :         23 : ValueCountMatchSpy::values_begin() const
     317                 :            : {
     318                 :            :     Assert(internal.get());
     319         [ +  - ]:         23 :     return Xapian::TermIterator(new ValueCountTermList(internal.get()));
     320                 :            : }
     321                 :            : 
     322                 :            : TermIterator
     323                 :        246 : ValueCountMatchSpy::top_values_begin(size_t maxvalues) const
     324                 :            : {
     325                 :            :     Assert(internal.get());
     326                 :        246 :     unique_ptr<StringAndFreqTermList> termlist(nullptr);
     327         [ +  + ]:        246 :     if (usual(maxvalues > 0)) {
     328         [ +  - ]:        228 :         termlist.reset(new StringAndFreqTermList);
     329         [ +  - ]:        228 :         get_most_frequent_items(termlist->values, internal->values, maxvalues);
     330                 :        228 :         termlist->init();
     331                 :            :     }
     332         [ +  - ]:        246 :     return Xapian::TermIterator(termlist.release());
     333                 :            : }
     334                 :            : 
     335                 :            : MatchSpy *
     336                 :          0 : ValueCountMatchSpy::clone() const {
     337                 :            :     Assert(internal.get());
     338         [ #  # ]:          0 :     return new ValueCountMatchSpy(internal->slot);
     339                 :            : }
     340                 :            : 
     341                 :            : string
     342                 :       1443 : ValueCountMatchSpy::name() const {
     343         [ +  - ]:       1443 :     return "Xapian::ValueCountMatchSpy";
     344                 :            : }
     345                 :            : 
     346                 :            : string
     347                 :          4 : ValueCountMatchSpy::serialise() const {
     348                 :            :     Assert(internal.get());
     349                 :          4 :     string result;
     350 [ +  - ][ +  - ]:          4 :     result += encode_length(internal->slot);
     351                 :          4 :     return result;
     352                 :            : }
     353                 :            : 
     354                 :            : MatchSpy *
     355                 :          4 : ValueCountMatchSpy::unserialise(const string & s, const Registry &) const
     356                 :            : {
     357                 :          4 :     const char * p = s.data();
     358                 :          4 :     const char * end = p + s.size();
     359                 :            : 
     360                 :            :     valueno new_slot;
     361         [ +  - ]:          4 :     decode_length(&p, end, new_slot);
     362         [ -  + ]:          4 :     if (p != end) {
     363 [ #  # ][ #  # ]:          0 :         throw NetworkError("Junk at end of serialised ValueCountMatchSpy");
                 [ #  # ]
     364                 :            :     }
     365                 :            : 
     366 [ +  - ][ +  - ]:          4 :     return new ValueCountMatchSpy(new_slot);
     367                 :            : }
     368                 :            : 
     369                 :            : string
     370                 :          4 : ValueCountMatchSpy::serialise_results() const {
     371                 :            :     LOGCALL(REMOTE, string, "ValueCountMatchSpy::serialise_results", NO_ARGS);
     372                 :            :     Assert(internal.get());
     373                 :          4 :     string result;
     374 [ +  - ][ +  - ]:          4 :     result += encode_length(internal->total);
     375 [ +  - ][ +  - ]:          4 :     result += encode_length(internal->values.size());
     376         [ +  + ]:         24 :     for (map<string, doccount>::const_iterator i = internal->values.begin();
     377                 :         12 :          i != internal->values.end(); ++i) {
     378 [ +  - ][ +  - ]:          8 :         result += encode_length(i->first.size());
     379         [ +  - ]:          8 :         result += i->first;
     380 [ +  - ][ +  - ]:          8 :         result += encode_length(i->second);
     381                 :            :     }
     382                 :          4 :     RETURN(result);
     383                 :            : }
     384                 :            : 
     385                 :            : void
     386                 :          4 : ValueCountMatchSpy::merge_results(const string & s) {
     387                 :            :     LOGCALL_VOID(REMOTE, "ValueCountMatchSpy::merge_results", s);
     388                 :            :     Assert(internal.get());
     389                 :          4 :     const char * p = s.data();
     390                 :          4 :     const char * end = p + s.size();
     391                 :            : 
     392                 :            :     Xapian::doccount n;
     393         [ +  - ]:          4 :     decode_length(&p, end, n);
     394                 :          4 :     internal->total += n;
     395                 :            : 
     396                 :            :     map<string, doccount>::size_type items;
     397         [ +  - ]:          4 :     decode_length(&p, end, items);
     398         [ +  + ]:          8 :     while (p != end) {
     399         [ +  + ]:         12 :         while (items != 0) {
     400                 :            :             size_t vallen;
     401         [ +  - ]:          8 :             decode_length_and_check(&p, end, vallen);
     402         [ +  - ]:          8 :             string val(p, vallen);
     403                 :          8 :             p += vallen;
     404                 :            :             doccount freq;
     405         [ +  - ]:          8 :             decode_length(&p, end, freq);
     406         [ +  - ]:          8 :             internal->values[val] += freq;
     407                 :          8 :             --items;
     408                 :          8 :         }
     409                 :            :     }
     410                 :          4 : }
     411                 :            : 
     412                 :            : string
     413                 :          1 : ValueCountMatchSpy::get_description() const {
     414         [ +  - ]:          1 :     string d = "ValueCountMatchSpy(";
     415         [ +  - ]:          1 :     if (internal.get()) {
     416 [ +  - ][ +  - ]:          1 :         d += str(internal->total);
     417         [ +  - ]:          1 :         d += " docs seen, looking in ";
     418 [ +  - ][ +  - ]:          1 :         d += str(internal->values.size());
     419         [ +  - ]:          1 :         d += " slots)";
     420                 :            :     } else {
     421         [ #  # ]:          0 :         d += ")";
     422                 :            :     }
     423                 :          1 :     return d;
     424                 :            : }

Generated by: LCOV version 1.11