icing/index/main/main-index.h

// Copyright (C) 2019 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#ifndef ICING_INDEX_MAIN_MAIN_INDEX_H_
#define ICING_INDEX_MAIN_MAIN_INDEX_H_

#include <memory>

#include "icing/text_classifier/lib3/utils/base/status.h"
#include "icing/text_classifier/lib3/utils/base/statusor.h"
#include "icing/file/filesystem.h"
#include "icing/index/lite/term-id-hit-pair.h"
#include "icing/index/main/flash-index-storage.h"
#include "icing/index/main/posting-list-accessor.h"
#include "icing/index/term-id-codec.h"
#include "icing/index/term-metadata.h"
#include "icing/legacy/index/icing-dynamic-trie.h"
#include "icing/legacy/index/icing-filesystem.h"
#include "icing/proto/storage.pb.h"
#include "icing/store/namespace-id.h"
#include "icing/util/status-macros.h"

namespace icing {
namespace lib {

class MainIndex {
 public:
  // RETURNS:
  //  - valid instance of MainIndex, on success.
  //  - INTERNAL error if unable to create the lexicon or flash storage.
  static libtextclassifier3::StatusOr<std::unique_ptr<MainIndex>> Create(
      const std::string& index_directory, const Filesystem* filesystem,
      const IcingFilesystem* icing_filesystem);

  // Get a PostingListAccessor that holds the posting list chain for 'term'.
  //
  // RETURNS:
  //  - On success, a valid PostingListAccessor
  //  - NOT_FOUND if term is not present in the main index.
  libtextclassifier3::StatusOr<std::unique_ptr<PostingListAccessor>>
  GetAccessorForExactTerm(const std::string& term);

  // Get a PostingListAccessor for 'prefix'.
  //
  // RETURNS:
  //  - On success, a result containing a valid PostingListAccessor.
  //  - NOT_FOUND if neither 'prefix' nor any terms for which 'prefix' is a
  //    prefix are present in the main index.
  struct GetPrefixAccessorResult {
    // A PostingListAccessor that holds the posting list chain for the term
    // that best represents 'prefix' in the main index.
    std::unique_ptr<PostingListAccessor> accessor;
    // True if the returned posting list chain is for 'prefix' or false if the
    // returned posting list chain is for a term for which 'prefix' is a prefix.
    bool exact;
  };
  libtextclassifier3::StatusOr<GetPrefixAccessorResult>
  GetAccessorForPrefixTerm(const std::string& prefix);

  // Finds terms with the given prefix in the given namespaces. If
  // 'namespace_ids' is empty, returns results from all the namespaces. The
  // input prefix must be normalized, otherwise inaccurate results may be
  // returned. Results are not sorted specifically and are in lexigraphical
  // order. Number of results are no more than 'num_to_return'.
  //
  // The hit count returned with each TermMetadata is an approximation based of
  // posting list size.
  //
  // Returns:
  //   A list of TermMetadata on success
  //   INTERNAL_ERROR if failed to access term data.
  libtextclassifier3::StatusOr<std::vector<TermMetadata>> FindTermsByPrefix(
      const std::string& prefix, const std::vector<NamespaceId>& namespace_ids,
      int num_to_return);

  struct LexiconMergeOutputs {
    // Maps from main_lexicon tvi for new branching point to the main_lexicon
    // tvi for posting list whose hits must be backfilled.
    std::unordered_map<uint32_t, uint32_t> backfill_map;

    // Maps from lexicon tvis to main_lexicon tvis.
    std::unordered_map<uint32_t, uint32_t> other_tvi_to_main_tvi;

    // Maps from main lexicon tvi to the block index. Tvis with no entry do not
    // have an allocated posting list.
    std::unordered_map<uint32_t, int> main_tvi_to_block_index;

    // Maps from the lexicon tvi to the beginning position in
    // prefix_tvis_buf and the length.
    std::unordered_map<uint32_t, std::pair<int, int>>
        other_tvi_to_prefix_main_tvis;

    // Stores tvis that are mapped to by other_tvi_to_prefix_tvis.
    std::vector<uint32_t> prefix_tvis_buf;
  };

  // Merge the lexicon into the main lexicon and populate the data
  // structures necessary to translate lite tvis to main tvis, track backfilling
  // and expanding lite terms to prefix terms.
  //
  // RETURNS:
  //   - OK on success
  //   - INTERNAL on IO error while writing to the main lexicon.
  libtextclassifier3::StatusOr<LexiconMergeOutputs> MergeLexicon(
      const IcingDynamicTrie& other_lexicon) {
    // Backfill branch points need to be added first so that the backfill_map
    // can be correctly populated.
    ICING_ASSIGN_OR_RETURN(LexiconMergeOutputs outputs,
                           AddBackfillBranchPoints(other_lexicon));
    ICING_ASSIGN_OR_RETURN(outputs,
                           AddTerms(other_lexicon, std::move(outputs)));
    // Non-backfill branch points need to be added last so that the mapping of
    // newly added terms to prefix terms can be correctly populated (prefix
    // terms might be branch points between two new terms or between a
    // pre-existing term and a new term).
    ICING_ASSIGN_OR_RETURN(outputs,
                           AddBranchPoints(other_lexicon, std::move(outputs)));
    return outputs;
  }

  // Add hits to the main index and backfill from existing posting lists to new
  // backfill branch points.
  //
  // The backfill_map maps from main_lexicon tvi for a newly added branching
  // point to the main_lexicon tvi for the posting list whose hits must be
  // backfilled. backfill_map should be populated as part of LexiconMergeOutputs
  // in MergeLexicon and be blindly passed to this function.
  //
  // RETURNS:
  //  - OK on success
  //  - INVALID_ARGUMENT if one of the elements in the lite index has a term_id
  //  exceeds the max TermId, is not valid or is not less than pre-existing hits
  //  in the main index.
  //  - INTERNAL_ERROR if unable to mmap necessary IndexBlocks
  //  - RESOURCE_EXHAUSTED error if unable to grow the index
  libtextclassifier3::Status AddHits(
      const TermIdCodec& term_id_codec,
      std::unordered_map<uint32_t, uint32_t>&& backfill_map,
      std::vector<TermIdHitPair>&& hits, DocumentId last_added_document_id);

  libtextclassifier3::Status PersistToDisk() {
    if (main_lexicon_->Sync() && flash_index_storage_->PersistToDisk()) {
      return libtextclassifier3::Status::OK;
    }
    return absl_ports::InternalError("Unable to sync lite index components.");
  }

  DocumentId last_added_document_id() const {
    return flash_index_storage_->get_last_indexed_docid();
  }

  libtextclassifier3::Status Reset() {
    ICING_RETURN_IF_ERROR(flash_index_storage_->Reset());
    main_lexicon_->Clear();
    return libtextclassifier3::Status::OK;
  }

  void Warm() { main_lexicon_->Warm(); }

  // Returns:
  //  - elements size of lexicon and index, on success
  //  - INTERNAL on IO error
  libtextclassifier3::StatusOr<int64_t> GetElementsSize() const;

  // Takes the provided storage_info, populates the fields related to the main
  // index and returns that storage_info.
  //
  // If an IO error occurs while trying to calculate the value for a field, then
  // that field will be set to -1.
  IndexStorageInfoProto GetStorageInfo(
      IndexStorageInfoProto storage_info) const;

  // Returns debug information for the main index in out.
  // verbosity <= 0, simplest debug information - just the lexicon
  // verbosity > 0, more detailed debug information including raw postings
  //                lists.
  void GetDebugInfo(int verbosity, std::string* out) const;

 private:
  libtextclassifier3::Status Init(const std::string& index_directory,
                                  const Filesystem* filesystem,
                                  const IcingFilesystem* icing_filesystem);

  // Helpers for merging the lexicon
  // Add all 'backfill' branch points. Backfill branch points are prefix
  // branch points that are a prefix of terms that existed in the lexicon
  // to the merge.
  //
  // For example, if the main lexicon only contains "foot" and is then merged
  // with a lite lexicon containing only "fool", then a backfill branch point
  // for "foo" will be added to contain prefix hits from both the pre-existing
  // posting list for "foot" and the new posting list for "fool".
  //
  // Populates LexiconMergeOutputs.backfill_map
  //
  // RETURNS:
  //   - OK on success
  //   - INTERNAL on IO error while writing to the main lexicon.
  libtextclassifier3::StatusOr<LexiconMergeOutputs> AddBackfillBranchPoints(
      const IcingDynamicTrie& other_lexicon);

  // Add all terms from the lexicon.
  //
  // Populates LexiconMergeOutputs.other_tvi_to_main_tvi
  //
  // RETURNS:
  //   - OK on success
  //   - INTERNAL on IO error while writing to the main lexicon.
  libtextclassifier3::StatusOr<LexiconMergeOutputs> AddTerms(
      const IcingDynamicTrie& other_lexicon, LexiconMergeOutputs&& outputs);

  // Add all branch points for terms added from the lexicon.
  // For example, if the main lexicon is empty and is then merged with a
  // lexicon containing only "foot" and "fool", then a branch point for "foo"
  // will be added to contain prefix hits from both "foot" and "fool".
  //
  // Populates LexiconMergeOutputs.other_tvi_to_prefix_main_tvis and
  // LexiconMergeOutputs.prefix_tvis_buf;
  //
  // RETURNS:
  //   - OK on success
  //   - INTERNAL on IO error while writing to the main lexicon.
  libtextclassifier3::StatusOr<LexiconMergeOutputs> AddBranchPoints(
      const IcingDynamicTrie& other_lexicon, LexiconMergeOutputs&& outputs);

  // Copies all properties from old_tvi in the other lexicon to the new_tvi in
  // the main lexicon.
  // Returns true on success, false if an IO error is encountered.
  bool CopyProperties(const IcingDynamicTrie::PropertyReadersAll& prop_reader,
                      const IcingDynamicTrie& other_lexicon, uint32_t other_tvi,
                      uint32_t new_main_tvi);

  // Add all hits between [hit_elements, hit_elements + len) to main_index,
  // updating the entry in the main lexicon at trie_value_index to point to the
  // resulting posting list. Hits are sorted in descending document id order, so
  // they should be to posting lists in reverse (starting at hit_elements
  // + len - 1) and working backwards. Therefore, hit_elements must be in sorted
  // order.
  //
  // trie_value_index may point to a valid posting list id if there is a
  // pre-existing posting list to append to.
  //
  // If backfill_posting_list_id is valid, then the hits from the posting list
  // identified by backfill_posting_list_id should be added to the new posting
  // list before the hits in hit_elements.
  //
  // RETURNS:
  //  - OK on success
  //  - INVALID_ARGUMENT if posting_list_id stored at trie_value_index is valid
  //  but points out of bounds in the IndexBlock referred to by
  //  id.block_index(), if one of the hits from [hit_elements,hit_elements+len)
  //  is not valid, or if one of the hits from [hit_elements,hit_elements+len)
  //  is not less than the previously added hits.
  //  - INTERNAL_ERROR if posting_list_id stored at trie_value_index is valid
  //  but points to an invalid block index or if unable to mmap the IndexBlock.
  //  - RESOURCE_EXHAUSTED error if unable to grow the index to allocate a new
  //  posting list.
  libtextclassifier3::Status AddHitsForTerm(
      uint32_t tvi, PostingListIdentifier backfill_posting_list_id,
      const TermIdHitPair* hit_elements, size_t len);

  // Adds all prefix hits or hits from prefix sections present on the posting
  // list identified by backfill_posting_list_id to hit_accum.
  //
  // RETURNS:
  //  - OK, on success
  //  - INVALID_ARGUMENT if backfill_posting_list_id points out of bounds in the
  //  IndexBlock referred to by id.block_index()
  //  - INTERNAL_ERROR if unable to mmap the block identified by
  //  backfill_posting_list_id or if the posting list identified by
  //  backfill_posting_list_id has been corrupted.
  //  - RESOURCE_EXHAUSTED error if unable to grow the index to allocate a new
  //  posting list.
  libtextclassifier3::Status AddPrefixBackfillHits(
      PostingListIdentifier backfill_posting_list_id,
      PostingListAccessor* hit_accum);

  std::unique_ptr<FlashIndexStorage> flash_index_storage_;
  std::unique_ptr<IcingDynamicTrie> main_lexicon_;
};

}  // namespace lib
}  // namespace icing

#endif  // ICING_INDEX_MAIN_MAIN_INDEX_H_