text: // Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
  
  #pragma once
  
  #include "field_spec.h"
  #include "unpackinfo.h"
  #include "executeinfo.h"
  #include "global_filter.h"
  #include "multisearch.h"
  #include <vespa/searchlib/common/bitvector.h>
  
  namespace vespalib { class ObjectVisitor; }
  namespace vespalib::slime {
      struct Cursor;
      struct Inserter;
  }
  namespace search { class MatchingElementsFields; }
  namespace search::attribute { class ISearchContext; }
  namespace search::fef {
      class TermFieldMatchDataArray;
      class MatchData;
  }
  
  namespace search::queryeval {
  
  class SearchIterator;
  class ExecuteInfo;
  class MatchingElementsSearch;
  
  /**
   * A Blueprint is an intermediate representation of a search. More
   * concretely, it is a tree of search iterator factories annotated
   * with meta-data about the fields to be searched, how match
   * information is to be exposed to the ranking framework and estimates
   * for the number of results that will be produced. Intermediate
   * operations are implemented by extending the blueprint::Intermediate
   * template class. Leaf operations are implemented by extending the
   * blueprint::Leaf template class.
   **/
  class Blueprint
  {
  public:
      typedef std::unique_ptr<Blueprint> UP;
      typedef std::unique_ptr<SearchIterator> SearchIteratorUP;
  
      struct HitEstimate {
          uint32_t estHits;
          bool     empty;
  
          HitEstimate() : estHits(0), empty(true) {}
          HitEstimate(uint32_t estHits_, bool empty_)
              : estHits(estHits_), empty(empty_) {}
  
          bool operator < (const HitEstimate &other) const {
              if (empty == other.empty) {
                  return (estHits < other.estHits);
              } else {
                  return empty;
              }
          }
      };
  
      class State
      {
      private:
          FieldSpecBaseList _fields;
          HitEstimate       _estimate;
          uint32_t          _cost_tier;
          uint32_t          _tree_size;
          bool              _allow_termwise_eval;
          bool              _want_global_filter;
  
      public:
          static constexpr uint32_t COST_TIER_NORMAL = 1;
          static constexpr uint32_t COST_TIER_EXPENSIVE = 2;
          static constexpr uint32_t COST_TIER_MAX = 999;
  
          State(const FieldSpecBaseList &fields_in);
          State(const State &rhs) = delete;
          State(State &&rhs) = default;
          State &operator=(const State &rhs) = delete;
          State &operator=(State &&rhs) = default;
          ~State();
  
          bool isTermLike() const { return !_fields.empty(); }
          const FieldSpecBaseList &fields() const { return _fields; }
  
          size_t numFields() const { return _fields.size(); }
          const FieldSpecBase &field(size_t idx) const { return _fields[idx]; }
          const FieldSpecBase *lookupField(uint32_t fieldId) const {
              for (const FieldSpecBase & field : _fields) {
                  if (field.getFieldId() == fieldId) {
                      return &field;
                  }
              }
              return nullptr;
          }
  
          void estimate(HitEstimate est) { _estimate = est; }
          HitEstimate estimate() const { return _estimate; }
          double hit_ratio(uint32_t docid_limit) const {
              uint32_t total_hits = _estimate.estHits;
              uint32_t total_docs = std::max(total_hits, docid_limit);
              return double(total_hits) / double(total_docs);
          }
          void tree_size(uint32_t value) { _tree_size = value; }
          uint32_t tree_size() const { return _tree_size; }
          void allow_termwise_eval(bool value) { _allow_termwise_eval = value; }
          bool allow_termwise_eval() const { return _allow_termwise_eval; }
          void want_global_filter(bool value) { _want_global_filter = value; }
          bool want_global_filter() const { return _want_global_filter; }
          void cost_tier(uint32_t value) { _cost_tier = value; }
          uint32_t cost_tier() const { return _cost_tier; }
      };
  
      // utility that just takes maximum estimate
      static HitEstimate max(const std::vector<HitEstimate> &data);
  
      // utility that just takes minium estimate
      static HitEstimate min(const std::vector<HitEstimate> &data);
  
      // utility to get the greater estimate to sort first, higher tiers last
      struct TieredGreaterEstimate {
          bool operator () (Blueprint * const &a, Blueprint * const &b) const {
              const auto &lhs = a->getState();
              const auto &rhs = b->getState();
              if (lhs.cost_tier() != rhs.cost_tier()) {
                  return (lhs.cost_tier() < rhs.cost_tier());
              }
              return (rhs.estimate() < lhs.estimate());
          }
      };
  
      // utility to get the lesser estimate to sort first, higher tiers last
      struct TieredLessEstimate {
          bool operator () (Blueprint * const &a, const Blueprint * const &b) const {
              const auto &lhs = a->getState();
              const auto &rhs = b->getState();
              if (lhs.cost_tier() != rhs.cost_tier()) {
                  return (lhs.cost_tier() < rhs.cost_tier());
              }
              return (lhs.estimate() < rhs.estimate());
          }
      };
  
  private:
      Blueprint *_parent;
      uint32_t   _sourceId;
      uint32_t   _docid_limit;
      bool       _frozen;
  
  protected:
      virtual void notifyChange() {
          if (_parent != nullptr) {
              _parent->notifyChange();
          }
      }
      void freeze_self() {
          getState();
          _frozen = true;
      }
  
  public:
      class IPredicate {
      public:
          virtual ~IPredicate() {}
          virtual bool check(const Blueprint & bp) const = 0;
      };
  
      // Signal if createFilterSearch should ensure the returned
      // iterator is an upper bound (yielding a hit on at least
      // all matching documents) or a lower bound (never yielding a
      // hit that isn't certain to be a match).
      enum class FilterConstraint { UPPER_BOUND, LOWER_BOUND };
  
      Blueprint();
      Blueprint(const Blueprint &) = delete;
      Blueprint &operator=(const Blueprint &) = delete;
      virtual ~Blueprint();
  
      void setParent(Blueprint *parent) { _parent = parent; }
      Blueprint *getParent() const { return _parent; }
      bool has_parent() const { return (_parent != nullptr); }
  
      Blueprint &setSourceId(uint32_t sourceId) { _sourceId = sourceId; return *this; }
      uint32_t getSourceId() const { return _sourceId; }
  
      virtual void setDocIdLimit(uint32_t limit) { _docid_limit = limit; }
      uint32_t get_docid_limit() const { return _docid_limit; }
  
      static Blueprint::UP optimize(Blueprint::UP bp);
      virtual void optimize(Blueprint* &self) = 0;
      virtual void optimize_self();
      virtual Blueprint::UP get_replacement();
      virtual bool should_optimize_children() const { return true; }
  
      virtual bool supports_termwise_children() const { return false; }
      virtual bool always_needs_unpack() const { return false; }
      virtual void set_global_filter(const GlobalFilter &global_filter);
  
      virtual const State &getState() const = 0;
      const Blueprint &root() const;
  
      double hit_ratio() const { return getState().hit_ratio(_docid_limit); }        
  
      virtual void fetchPostings(const ExecuteInfo &execInfo) = 0;
      virtual void freeze() = 0;
      bool frozen() const { return _frozen; }
  
      virtual SearchIteratorUP createSearch(fef::MatchData &md, bool strict) const = 0;
      virtual SearchIteratorUP createFilterSearch(bool strict, FilterConstraint constraint) const;
      static std::unique_ptr<SearchIterator> create_and_filter(const std::vector<Blueprint *>& children, bool strict, FilterConstraint constraint);
      static std::unique_ptr<SearchIterator> create_or_filter(const std::vector<Blueprint *>& children, bool strict, FilterConstraint constraint);
  
      // for debug dumping
      vespalib::string asString() const;
      vespalib::slime::Cursor & asSlime(const vespalib::slime::Inserter & cursor) const;
      virtual vespalib::string getClassName() const;
      virtual void visitMembers(vespalib::ObjectVisitor &visitor) const;
      virtual bool isEquiv() const { return false; }
      virtual bool isWhiteList() const { return false; }
      virtual bool isIntermediate() const { return false; }
      virtual bool isAnd() const { return false; }
      virtual bool isAndNot() const { return false; }
      virtual bool isOr() const { return false; }
      virtual bool isSourceBlender() const { return false; }
      virtual bool isRank() const { return false; }
      virtual const attribute::ISearchContext *get_attribute_search_context() const { return nullptr; }
  
      // For document summaries with matched-elements-only set.
      virtual std::unique_ptr<MatchingElementsSearch> create_matching_elements_search(const MatchingElementsFields &fields) const;
  };
  
  namespace blueprint {
  
  //-----------------------------------------------------------------------------
  
  class StateCache : public Blueprint
  {
  private:
      mutable bool  _stale;
      mutable State _state;
      void updateState() const;
  
  protected:
      void notifyChange() override final;
      virtual State calculateState() const = 0;
  
  public:
      StateCache() : _stale(true), _state(FieldSpecBaseList()) {}
      const State &getState() const override final {
          if (_stale) {
              updateState();
          }
          return _state;
      }
  };
  
  } // namespace blueprint
  
  //-----------------------------------------------------------------------------
  
  class IntermediateBlueprint : public blueprint::StateCache
  {
  public:
      typedef std::vector<Blueprint*> Children;
  private:
      Children _children;
      HitEstimate calculateEstimate() const;
      uint32_t calculate_cost_tier() const;
      uint32_t calculate_tree_size() const;
      bool infer_allow_termwise_eval() const;
      bool infer_want_global_filter() const;
  
      size_t count_termwise_nodes(const UnpackInfo &unpack) const;
      virtual double computeNextHitRate(const Blueprint & child, double hitRate) const;
  
  protected:
      // returns an empty collection if children have empty or
      // conflicting collections of field specs.
      FieldSpecBaseList mixChildrenFields() const;
  
      State calculateState() const override final;
  
      virtual bool isPositive(size_t index) const { (void) index; return true; }
  
      bool should_do_termwise_eval(const UnpackInfo &unpack, double match_limit) const;
  
      const Children& get_children() const { return _children; }
  
  public:
      typedef std::vector<size_t> IndexList;
      IntermediateBlueprint();
      ~IntermediateBlueprint() override;
  
      void setDocIdLimit(uint32_t limit) override final;
  
      void optimize(Blueprint* &self) override final;
      void set_global_filter(const GlobalFilter &global_filter) override;
  
      IndexList find(const IPredicate & check) const;
      size_t childCnt() const { return _children.size(); }
      const Blueprint &getChild(size_t n) const { return *_children[n]; }
      Blueprint &getChild(size_t n) { return *_children[n]; }
      IntermediateBlueprint & insertChild(size_t n, Blueprint::UP child);
      IntermediateBlueprint &addChild(Blueprint::UP child);
      Blueprint::UP removeChild(size_t n);
      SearchIteratorUP createSearch(fef::MatchData &md, bool strict) const override;
  
      virtual HitEstimate combine(const std::vector<HitEstimate> &data) const = 0;
      virtual FieldSpecBaseList exposeFields() const = 0;
      virtual void sort(std::vector<Blueprint*> &children) const = 0;
      virtual bool inheritStrict(size_t i) const = 0;
      virtual SearchIteratorUP
      createIntermediateSearch(MultiSearch::Children subSearches,
                               bool strict, fef::MatchData &md) const = 0;
  
      void visitMembers(vespalib::ObjectVisitor &visitor) const override;
      void fetchPostings(const ExecuteInfo &execInfo) override;
      void freeze() override final;
  
      UnpackInfo calculateUnpackInfo(const fef::MatchData & md) const;
      bool isIntermediate() const override { return true; }
  };
  
  
  class LeafBlueprint : public Blueprint
  {
  private:
      State _state;
  
  protected:
      void optimize(Blueprint* &self) override final;
      void setEstimate(HitEstimate est);
      void set_cost_tier(uint32_t value);
      void set_allow_termwise_eval(bool value);
      void set_want_global_filter(bool value);
      void set_tree_size(uint32_t value);
  
      LeafBlueprint(const FieldSpecBaseList &fields, bool allow_termwise_eval);
  public:
      ~LeafBlueprint() override;
      const State &getState() const override final { return _state; }
      void setDocIdLimit(uint32_t limit) override final { Blueprint::setDocIdLimit(limit); }
      void fetchPostings(const ExecuteInfo &execInfo) override;
      void freeze() override final;
      SearchIteratorUP createSearch(fef::MatchData &md, bool strict) const override;
  
      virtual SearchIteratorUP createLeafSearch(const fef::TermFieldMatchDataArray &tfmda,
                                                  bool strict) const = 0;
  };
  
  // for leaf nodes representing a single term
  struct SimpleLeafBlueprint : LeafBlueprint {
      SimpleLeafBlueprint(const FieldSpecBase &field) : LeafBlueprint(FieldSpecBaseList().add(field), true) {}
      SimpleLeafBlueprint(const FieldSpecBaseList &fields) : LeafBlueprint(fields, true) {}
  };
  
  // for leaf nodes representing more complex structures like wand/phrase
  struct ComplexLeafBlueprint : LeafBlueprint {
      ComplexLeafBlueprint(const FieldSpecBase &field) : LeafBlueprint(FieldSpecBaseList().add(field), false) {}    
      ComplexLeafBlueprint(const FieldSpecBaseList &fields) : LeafBlueprint(fields, false) {}
  };
  
  //-----------------------------------------------------------------------------
  
  }
  
  void visit(vespalib::ObjectVisitor &self, const vespalib::string &name,
             const search::queryeval::Blueprint &obj);
  void visit(vespalib::ObjectVisitor &self, const vespalib::string &name,
             const search::queryeval::Blueprint *obj);
  
  