LCOV - code coverage report
Current view: top level - backends/honey - honey_postlist.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 4ba52dacf4fb Lines: 146 172 84.9 %
Date: 2019-05-20 14:58:19 Functions: 18 19 94.7 %
Branches: 97 212 45.8 %

           Branch data     Line data    Source code
       1                 :            : /** @file honey_postlist.cc
       2                 :            :  * @brief PostList in a honey database.
       3                 :            :  */
       4                 :            : /* Copyright (C) 2017,2018 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 "honey_postlist.h"
      24                 :            : 
      25                 :            : #include "honey_cursor.h"
      26                 :            : #include "honey_database.h"
      27                 :            : #include "honey_positionlist.h"
      28                 :            : #include "honey_postlist_encodings.h"
      29                 :            : #include "pack.h"
      30                 :            : 
      31                 :            : #include <string>
      32                 :            : 
      33                 :            : using namespace Honey;
      34                 :            : using namespace std;
      35                 :            : 
      36                 :            : bool
      37                 :         10 : HoneyPostList::update_reader()
      38                 :            : {
      39                 :         10 :     Xapian::docid chunk_last = docid_from_key(term, cursor->current_key);
      40         [ +  + ]:         10 :     if (!chunk_last) return false;
      41                 :            : 
      42                 :          9 :     cursor->read_tag();
      43                 :          9 :     const string& tag = cursor->current_tag;
      44                 :          9 :     reader.assign(tag.data(), tag.size(), chunk_last);
      45                 :          5 :     return true;
      46                 :            : }
      47                 :            : 
      48                 :            : // Return T with just its top bit set (for unsigned T).
      49                 :            : #define TOP_BIT_SET(T) ((static_cast<T>(-1) >> 1) + 1)
      50                 :            : 
      51                 :      51169 : HoneyPostList::HoneyPostList(const HoneyDatabase* db_,
      52                 :            :                              const string& term_,
      53                 :            :                              HoneyCursor* cursor_)
      54                 :      51169 :     : LeafPostList(term_), cursor(cursor_), db(db_)
      55                 :            : {
      56         [ +  + ]:      51169 :     if (!cursor) {
      57                 :            :         // Term not present in db.
      58                 :        195 :         reader.init();
      59                 :        195 :         last_did = 0;
      60                 :      51169 :         return;
      61                 :            :     }
      62                 :            : 
      63         [ +  - ]:      50974 :     cursor->read_tag();
      64                 :      50974 :     const string& chunk = cursor->current_tag;
      65                 :            : 
      66                 :      50974 :     const char* p = chunk.data();
      67                 :      50974 :     const char* pend = p + chunk.size();
      68                 :            :     // FIXME: Make use of [first,last] ranges to calculate better estimates and
      69                 :            :     // potentially to spot subqueries that can't match anything.
      70                 :            :     Xapian::doccount tf;
      71                 :            :     Xapian::termcount cf;
      72                 :            :     Xapian::docid first_did;
      73                 :            :     Xapian::termcount first_wdf;
      74                 :            :     Xapian::docid chunk_last;
      75                 :            :     Xapian::termcount wdf_max;
      76         [ -  + ]:      50974 :     if (!decode_initial_chunk_header(&p, pend, tf, cf,
      77                 :            :                                      first_did, last_did,
      78         [ +  - ]:      50974 :                                      chunk_last, first_wdf, wdf_max))
      79 [ #  # ][ #  # ]:          0 :         throw Xapian::DatabaseCorruptError("Postlist initial chunk header");
                 [ #  # ]
      80                 :            : 
      81                 :      50974 :     Xapian::termcount cf_info = cf;
      82         [ +  - ]:      50974 :     if (cf == 0) {
      83                 :            :         // wdf must always be zero.
      84         [ +  + ]:      50974 :     } else if (tf <= 2) {
      85                 :            :         // No further postlist data stored.
      86         [ +  + ]:      26425 :     } else if (cf == tf - 1 + first_wdf) {
      87                 :            :         // wdf must be 1 for second and subsequent entries.
      88                 :        378 :         cf_info = 1 | TOP_BIT_SET(decltype(cf_info));
      89                 :            :     } else {
      90                 :      26047 :         cf_info = 1;
      91                 :            :         // If wdf_max can only be zero if cf == 0 (and
      92                 :            :         // decode_initial_chunk_header() should ensure this).
      93                 :            :         Assert(wdf_max != 0);
      94                 :      26047 :         Xapian::termcount remaining_cf_for_flat_wdf = (tf - 1) * wdf_max;
      95                 :            :         // Check this matches and that it isn't a false match due
      96                 :            :         // to overflow of the multiplication above.
      97 [ -  + ][ #  # ]:      26047 :         if (cf - first_wdf == remaining_cf_for_flat_wdf &&
      98                 :          0 :             usual(remaining_cf_for_flat_wdf / wdf_max == tf - 1)) {
      99                 :            :             // Set cl_info to the flat wdf value with the top bit set to
     100                 :            :             // signify that this is a flat wdf value.
     101                 :          0 :             cf_info = wdf_max;
     102                 :            :             // It shouldn't be possible for the top bit to already be set since
     103                 :            :             // tf > 2 so cf must be at least 2 * remaining_cf_for_flat_wdf.
     104                 :            :             Assert((cf_info & TOP_BIT_SET(decltype(cf_info))) == 0);
     105                 :          0 :             cf_info |= TOP_BIT_SET(decltype(cf_info));
     106                 :            :         }
     107                 :            :     }
     108                 :            : 
     109                 :      50974 :     reader.init(tf, cf_info);
     110                 :      50974 :     reader.assign(p, pend - p, first_did, last_did, first_wdf);
     111                 :            : }
     112                 :            : 
     113                 :     153309 : HoneyPostList::~HoneyPostList()
     114                 :            : {
     115         [ +  + ]:      51169 :     delete cursor;
     116         [ -  + ]:     102140 : }
     117                 :            : 
     118                 :            : Xapian::doccount
     119                 :     198748 : HoneyPostList::get_termfreq() const
     120                 :            : {
     121                 :     198748 :     return reader.get_termfreq();
     122                 :            : }
     123                 :            : 
     124                 :            : LeafPostList*
     125                 :      24256 : HoneyPostList::open_nearby_postlist(const string& term_,
     126                 :            :                                     bool need_read_pos) const
     127                 :            : {
     128                 :            :     Assert(!term_.empty());
     129         [ +  + ]:      24256 :     if (!cursor) return NULL;
     130                 :            :     // FIXME: Once Honey supports writing, we need to return NULL here if the
     131                 :            :     // DB is writable and has uncommitted modifications.
     132                 :            : 
     133 [ +  - ][ +  - ]:      24182 :     unique_ptr<HoneyCursor> new_cursor(new HoneyCursor(*cursor));
     134 [ +  - ][ +  - ]:      24182 :     if (!new_cursor->find_exact(Honey::make_postingchunk_key(term_))) {
                 [ +  + ]
     135                 :            :         // FIXME: Return NULL here and handle that in Query::Internal
     136                 :            :         // postlist() methods as we build the PostList tree.
     137                 :            :         // We also need to distinguish this case from "open_nearby_postlist()
     138                 :            :         // not supported" though.
     139                 :            :         // return NULL;
     140                 :            :         //
     141                 :            :         // No need to consider need_read_pos for an empty posting list.
     142 [ +  - ][ +  - ]:         84 :         return new HoneyPostList(db, term_, NULL);
     143                 :            :     }
     144                 :            : 
     145         [ +  + ]:      24098 :     if (need_read_pos)
     146 [ +  - ][ +  - ]:        120 :         return new HoneyPosPostList(db, term_, new_cursor.release());
     147 [ +  - ][ +  - ]:      24256 :     return new HoneyPostList(db, term_, new_cursor.release());
     148                 :            : }
     149                 :            : 
     150                 :            : Xapian::docid
     151                 :   10317535 : HoneyPostList::get_docid() const
     152                 :            : {
     153                 :   10317535 :     return reader.get_docid();
     154                 :            : }
     155                 :            : 
     156                 :            : Xapian::termcount
     157                 :    9529427 : HoneyPostList::get_wdf() const
     158                 :            : {
     159                 :    9529427 :     return reader.get_wdf();
     160                 :            : }
     161                 :            : 
     162                 :            : bool
     163                 :    9604372 : HoneyPostList::at_end() const
     164                 :            : {
     165                 :    9604372 :     return cursor == NULL;
     166                 :            : }
     167                 :            : 
     168                 :            : PositionList*
     169                 :        232 : HoneyPostList::open_position_list() const
     170                 :            : {
     171         [ +  - ]:        232 :     return new HoneyPositionList(db->position_table, get_docid(), term);
     172                 :            : }
     173                 :            : 
     174                 :            : PostList*
     175                 :    9579260 : HoneyPostList::next(double)
     176                 :            : {
     177         [ +  + ]:    9579260 :     if (!started) {
     178                 :      50563 :         started = true;
     179                 :      50563 :         return NULL;
     180                 :            :     }
     181                 :            : 
     182                 :            :     Assert(!reader.at_end());
     183                 :            : 
     184         [ +  + ]:    9528697 :     if (reader.next())
     185                 :    9478332 :         return NULL;
     186                 :            : 
     187         [ +  + ]:      50365 :     if (reader.get_docid() >= last_did) {
     188                 :            :         // We've reached the end.
     189         [ +  - ]:      50355 :         delete cursor;
     190                 :      50355 :         cursor = NULL;
     191                 :      50355 :         return NULL;
     192                 :            :     }
     193                 :            : 
     194         [ -  + ]:         10 :     if (rare(!cursor->next()))
     195                 :            :         throw Xapian::DatabaseCorruptError("Hit end of table looking for "
     196 [ #  # ][ #  # ]:          0 :                                            "postlist chunk");
                 [ #  # ]
     197                 :            : 
     198         [ +  + ]:         10 :     if (rare(!update_reader()))
     199 [ +  - ][ +  - ]:          1 :         throw Xapian::DatabaseCorruptError("Missing postlist chunk");
                 [ +  - ]
     200                 :            : 
     201                 :    9579255 :     return NULL;
     202                 :            : }
     203                 :            : 
     204                 :            : PostList*
     205                 :       1056 : HoneyPostList::skip_to(Xapian::docid did, double)
     206                 :            : {
     207         [ +  + ]:       1056 :     if (!started) {
     208                 :        158 :         started = true;
     209                 :            :     }
     210                 :            : 
     211         [ +  + ]:       1056 :     if (rare(!cursor)) {
     212                 :            :         // No-op if already at_end.
     213                 :          2 :         return NULL;
     214                 :            :     }
     215                 :            : 
     216                 :            :     Assert(!reader.at_end());
     217                 :            : 
     218         [ +  + ]:       1054 :     if (reader.skip_to(did))
     219                 :        994 :         return NULL;
     220                 :            : 
     221         [ +  - ]:         60 :     if (did > last_did) {
     222                 :            :         // We've reached the end.
     223         [ +  - ]:         60 :         delete cursor;
     224                 :         60 :         cursor = NULL;
     225                 :         60 :         return NULL;
     226                 :            :     }
     227                 :            : 
     228                 :            :     // At this point we know that skip_to() must succeed since last_did
     229                 :            :     // satisfies the requirements.
     230                 :            : 
     231                 :            :     // find_entry_ge() returns true for an exact match, which isn't interesting
     232                 :            :     // here.
     233         [ #  # ]:          0 :     (void)cursor->find_entry_ge(make_postingchunk_key(term, did));
     234                 :            : 
     235         [ #  # ]:          0 :     if (rare(cursor->after_end()))
     236                 :            :         throw Xapian::DatabaseCorruptError("Hit end of table looking for "
     237 [ #  # ][ #  # ]:          0 :                                            "postlist chunk");
                 [ #  # ]
     238                 :            : 
     239         [ #  # ]:          0 :     if (rare(!update_reader()))
     240 [ #  # ][ #  # ]:          0 :         throw Xapian::DatabaseCorruptError("Missing postlist chunk");
                 [ #  # ]
     241                 :            : 
     242         [ #  # ]:          0 :     if (rare(!reader.skip_to(did)))
     243                 :            :         throw Xapian::DatabaseCorruptError("Postlist chunk doesn't contain "
     244 [ #  # ][ #  # ]:          0 :                                            "its last entry");
                 [ #  # ]
     245                 :            : 
     246                 :       1056 :     return NULL;
     247                 :            : }
     248                 :            : 
     249                 :            : string
     250                 :          3 : HoneyPostList::get_description() const
     251                 :            : {
     252         [ +  - ]:          3 :     string desc = "HoneyPostList(";
     253         [ +  - ]:          3 :     desc += term;
     254         [ +  - ]:          3 :     desc += ')';
     255                 :          3 :     return desc;
     256                 :            : }
     257                 :            : 
     258                 :        198 : HoneyPosPostList::HoneyPosPostList(const HoneyDatabase* db_,
     259                 :            :                                    const std::string& term_,
     260                 :            :                                    HoneyCursor* cursor_)
     261                 :            :     : HoneyPostList(db_, term_, cursor_),
     262         [ +  - ]:        198 :       position_list(db_->position_table) {}
     263                 :            : 
     264                 :            : PositionList*
     265                 :        619 : HoneyPosPostList::read_position_list()
     266                 :            : {
     267                 :        619 :     position_list.read_data(HoneyPostList::get_docid(), term);
     268                 :            :     // FIXME: Consider returning NULL if there's no positional data - callers
     269                 :            :     // need fixing up, but this may be a rare case and the costs of checking
     270                 :            :     // for NULL may outweigh any gains.  Need to profile.
     271                 :        619 :     return &position_list;
     272                 :            : }
     273                 :            : 
     274                 :            : string
     275                 :          0 : HoneyPosPostList::get_description() const
     276                 :            : {
     277         [ #  # ]:          0 :     string desc = "HoneyPosPostList(";
     278         [ #  # ]:          0 :     desc += term;
     279         [ #  # ]:          0 :     desc += ')';
     280                 :          0 :     return desc;
     281                 :            : }
     282                 :            : 
     283                 :            : namespace Honey {
     284                 :            : 
     285                 :            : void
     286                 :          9 : PostingChunkReader::assign(const char * p_, size_t len,
     287                 :            :                            Xapian::docid chunk_last)
     288                 :            : {
     289                 :          9 :     const char* pend = p_ + len;
     290 [ +  - ][ +  + ]:         18 :     if (collfreq_info ?
     291                 :          9 :         !decode_delta_chunk_header(&p_, pend, chunk_last, did, wdf) :
     292                 :          0 :         !decode_delta_chunk_header_no_wdf(&p_, pend, chunk_last, did)) {
     293 [ +  - ][ +  - ]:          4 :         throw Xapian::DatabaseCorruptError("Postlist delta chunk header");
                 [ +  - ]
     294                 :            :     }
     295                 :          5 :     p = p_;
     296                 :          5 :     end = pend;
     297                 :          5 :     last_did = chunk_last;
     298                 :          5 : }
     299                 :            : 
     300                 :            : void
     301                 :      50974 : PostingChunkReader::assign(const char * p_, size_t len, Xapian::docid did_,
     302                 :            :                            Xapian::docid last_did_in_chunk,
     303                 :            :                            Xapian::termcount wdf_)
     304                 :            : {
     305                 :      50974 :     p = p_;
     306                 :      50974 :     end = p_ + len;
     307                 :      50974 :     did = did_;
     308                 :      50974 :     last_did = last_did_in_chunk;
     309                 :      50974 :     wdf = wdf_;
     310                 :      50974 : }
     311                 :            : 
     312                 :            : bool
     313                 :    9528697 : PostingChunkReader::next()
     314                 :            : {
     315         [ +  + ]:    9528697 :     if (p == end) {
     316 [ +  + ][ +  + ]:      73730 :         if (termfreq == 2 && did != last_did) {
     317                 :      23365 :             did = last_did;
     318                 :      23365 :             wdf = collfreq_info - wdf;
     319                 :      23365 :             return true;
     320                 :            :         }
     321                 :      50365 :         p = NULL;
     322                 :      50365 :         return false;
     323                 :            :     }
     324                 :            : 
     325                 :            :     // The "constant wdf apart from maybe the first entry" case.
     326         [ +  + ]:    9454967 :     if (collfreq_info & TOP_BIT_SET(decltype(collfreq_info))) {
     327                 :        179 :         wdf = collfreq_info &~ TOP_BIT_SET(decltype(collfreq_info));
     328                 :        179 :         collfreq_info = 0;
     329                 :            :     }
     330                 :            : 
     331                 :            :     Xapian::docid delta;
     332         [ -  + ]:    9454967 :     if (!unpack_uint(&p, end, &delta)) {
     333 [ #  # ][ #  # ]:          0 :         throw Xapian::DatabaseCorruptError("postlist docid delta");
                 [ #  # ]
     334                 :            :     }
     335                 :    9454967 :     did += delta + 1;
     336         [ +  + ]:    9454967 :     if (collfreq_info) {
     337         [ -  + ]:    9453817 :         if (!unpack_uint(&p, end, &wdf)) {
     338 [ #  # ][ #  # ]:          0 :             throw Xapian::DatabaseCorruptError("postlist wdf");
                 [ #  # ]
     339                 :            :         }
     340                 :            :     }
     341                 :            : 
     342                 :    9528697 :     return true;
     343                 :            : }
     344                 :            : 
     345                 :            : bool
     346                 :       1054 : PostingChunkReader::skip_to(Xapian::docid target)
     347                 :            : {
     348         [ -  + ]:       1054 :     if (p == NULL)
     349                 :          0 :         return false;
     350                 :            : 
     351         [ +  + ]:       1054 :     if (target <= did)
     352                 :        140 :         return true;
     353                 :            : 
     354         [ +  + ]:        914 :     if (target > last_did) {
     355                 :         60 :         p = NULL;
     356                 :         60 :         return false;
     357                 :            :     }
     358                 :            : 
     359         [ +  + ]:        854 :     if (p == end) {
     360                 :            :         // Given the checks above, this must be the termfreq == 2 case with the
     361                 :            :         // current position being on the first entry, and so skip_to() must
     362                 :            :         // move to last_did.
     363                 :            :         AssertEq(termfreq, 2);
     364                 :         15 :         did = last_did;
     365                 :         15 :         wdf = collfreq_info - wdf;
     366                 :         15 :         return true;
     367                 :            :     }
     368                 :            : 
     369                 :            :     // The "constant wdf apart from maybe the first entry" case.
     370         [ +  + ]:        839 :     if (collfreq_info & TOP_BIT_SET(decltype(collfreq_info))) {
     371                 :         38 :         wdf = collfreq_info &~ TOP_BIT_SET(decltype(collfreq_info));
     372                 :         38 :         collfreq_info = 0;
     373                 :            :     }
     374                 :            : 
     375         [ +  + ]:        839 :     if (target == last_did) {
     376         [ +  + ]:         52 :         if (collfreq_info) {
     377         [ -  + ]:         26 :             if (!unpack_uint_backwards(&end, p, &wdf))
     378 [ #  # ][ #  # ]:          0 :                 throw Xapian::DatabaseCorruptError("postlist final wdf");
                 [ #  # ]
     379                 :            :         }
     380                 :         52 :         did = last_did;
     381                 :         52 :         p = end;
     382                 :         52 :         return true;
     383                 :            :     }
     384                 :            : 
     385         [ +  + ]:       1946 :     do {
     386         [ -  + ]:       1946 :         if (rare(p == end)) {
     387                 :            :             // FIXME: Shouldn't happen unless last_did was wrong.
     388                 :          0 :             p = NULL;
     389                 :          0 :             return false;
     390                 :            :         }
     391                 :            : 
     392                 :            :         Xapian::docid delta;
     393         [ -  + ]:       1946 :         if (!unpack_uint(&p, end, &delta)) {
     394 [ #  # ][ #  # ]:          0 :             throw Xapian::DatabaseCorruptError("postlist docid delta");
                 [ #  # ]
     395                 :            :         }
     396                 :       1946 :         did += delta + 1;
     397         [ +  + ]:       1946 :         if (collfreq_info) {
     398         [ -  + ]:       1768 :             if (!unpack_uint(&p, end, &wdf)) {
     399 [ #  # ][ #  # ]:          0 :                 throw Xapian::DatabaseCorruptError("postlist wdf");
                 [ #  # ]
     400                 :            :             }
     401                 :            :         }
     402                 :       1946 :     } while (target > did);
     403                 :            : 
     404                 :       1054 :     return true;
     405                 :            : }
     406                 :            : 
     407                 :            : }

Generated by: LCOV version 1.11