#pragma once

#include <array>

#include <cstdint>

#include <list>

#include <memory>

#include <string>

#include <type_traits>

#include "envoy/common/optref.h"

#include "envoy/config/core/v3/base.pb.h"

#include "envoy/http/header_map.h"

#include "source/common/common/compiled_string_map.h"

#include "source/common/common/non_copyable.h"

#include "source/common/common/utility.h"

#include "source/common/http/headers.h"

namespace Envoy {

namespace Http {

/**

 * These are definitions of all of the inline header access functions described inside header_map.h

 */

#define DEFINE_INLINE_HEADER_FUNCS(name)                                                           \

public:                                                                                            \

#define DEFINE_INLINE_HEADER_STRING_FUNCS(name)                                                    \

  DEFINE_INLINE_HEADER_FUNCS(name)                                                                 \

#define DEFINE_INLINE_HEADER_NUMERIC_FUNCS(name)                                                   \

  DEFINE_INLINE_HEADER_FUNCS(name)                                                                 \

/**

 * Implementation of Http::HeaderMap. This is heavily optimized for performance. Roughly, when

 * headers are added to the map by string, we do a trie lookup to see if it's one of the O(1)

 * headers. If it is, we store a reference to it that can be accessed later directly via direct

 * method access. Most high performance paths use O(1) direct method access. In general, we try to

 * copy as little as possible and allocate as little as possible in any of the paths.

 */

class HeaderMapImpl : NonCopyable {

public:

  HeaderMapImpl(const uint32_t max_headers_kb = UINT32_MAX,

                const uint32_t max_headers_count = UINT32_MAX)

  // The following "constructors" call virtual functions during construction and must use the

  // static factory pattern.

  static void copyFrom(HeaderMap& lhs, const HeaderMap& rhs);

  // The value_type of iterator must be pair, and the first value of them must be LowerCaseString.

  // If not, it won't be compiled successfully.

  // Performs a manual byte size count for test verification.

  void verifyByteSizeInternalForTest() const;

  // Note: This class does not actually implement Http::HeaderMap to avoid virtual inheritance in

  // the derived classes. Instead, it is used as a mix-in class for TypedHeaderMapImpl below. This

  // both avoid virtual inheritance and allows the concrete final header maps to use a variable

  // length member at the end.

  bool operator==(const HeaderMap& rhs) const;

  bool operator!=(const HeaderMap& rhs) const;

  void addViaMove(HeaderString&& key, HeaderString&& value);

  void addReference(const LowerCaseString& key, absl::string_view value);

  void addReferenceKey(const LowerCaseString& key, uint64_t value);

  void addReferenceKey(const LowerCaseString& key, absl::string_view value);

  void addCopy(const LowerCaseString& key, uint64_t value);

  void addCopy(const LowerCaseString& key, absl::string_view value);

  void appendCopy(const LowerCaseString& key, absl::string_view value);

  void setReference(const LowerCaseString& key, absl::string_view value);

  void setReferenceKey(const LowerCaseString& key, absl::string_view value);

  void setCopy(const LowerCaseString& key, absl::string_view value);

  uint64_t byteSize() const;

  HeaderMap::GetResult get(const LowerCaseString& key) const;

  void iterate(HeaderMap::ConstIterateCb cb) const;

  void iterateReverse(HeaderMap::ConstIterateCb cb) const;

  void clear();

  size_t remove(const LowerCaseString& key);

  size_t removeIf(const HeaderMap::HeaderMatchPredicate& predicate);

  size_t removePrefix(const LowerCaseString& key);

  void dumpState(std::ostream& os, int indent_level = 0) const;

protected:

  struct HeaderEntryImpl : public HeaderEntry, NonCopyable {

    HeaderEntryImpl(const LowerCaseString& key);

    HeaderEntryImpl(const LowerCaseString& key, HeaderString&& value);

    HeaderEntryImpl(HeaderString&& key, HeaderString&& value);

    // HeaderEntry

    void value(absl::string_view value) override;

    void value(uint64_t value) override;

    void value(const HeaderEntry& header) override;

    HeaderString key_;

    HeaderString value_;

    std::list<HeaderEntryImpl>::iterator entry_;

  };

  using HeaderNode = std::list<HeaderEntryImpl>::iterator;

  /**

   * This is the static lookup table that is used to determine whether a header is one of the O(1)

   * headers. This uses a trie for lookup time at most equal to the size of the incoming string.

   */

  struct StaticLookupResponse {

    HeaderEntryImpl** entry_;

    const LowerCaseString* key_;

  };

  /**

   * Base class for a static lookup table that converts a string key into an O(1) header.

   */

  template <class Interface>

  struct StaticLookupTable

      : public CompiledStringMap<std::function<StaticLookupResponse(HeaderMapImpl&)>> {

    StaticLookupTable();

      // The size of the lookup table is finalized when the singleton lookup table is created. This

      // allows for late binding of custom headers as well as envoy header prefix changes. This

      // does mean that once the first header map is created of this type, no further changes are

      // possible.

      // TODO(mattklein123): If we decide to keep this implementation, it is conceivable that header

      // maps could be created by an API factory that is owned by the listener/HCM, thus making

      // O(1) header delivery over xDS possible.

    static absl::optional<StaticLookupResponse> lookup(HeaderMapImpl& header_map,

    // This is the size of the number of callbacks; in the case of Requests,

    // this is one smaller than the number of entries in the lookup table,

    // because of legacy `host` mapping to the same thing as `:authority`.

    size_t size_;

  };

  /**

   * List of HeaderEntryImpl that keeps the pseudo headers (key starting with ':') in the front

   * of the list (as required by nghttp2) and otherwise maintains insertion order.

   * When the list size is greater or equal to 3, all headers are added to a map, to allow fast

   * access given a header key. Once the map is initialized, it will be used even

   * if the number of headers decreases below the threshold.

   *

   * Note: the internal iterators held in fields make this unsafe to copy and move, since the

   * reference to end() is not preserved across a move (see Notes in

   * https://en.cppreference.com/w/cpp/container/list/list). The NonCopyable will suppress both copy

   * and move constructors/assignment.

   * TODO(htuch): Maybe we want this to movable one day; for now, our header map moves happen on

   * HeaderMapPtr, so the performance impact should not be evident.

   */

  class HeaderList : NonCopyable {

  public:

    using HeaderNodeVector = absl::InlinedVector<HeaderNode, 1>;

    using HeaderLazyMap = absl::flat_hash_map<absl::string_view, HeaderNodeVector>;

        // Lazy map is used, iterate over its elements and remove those that satisfy the predicate

        // from the map and from the list.

          // The following call to std::remove_if removes the elements that satisfy the

          // UnaryPredicate and shifts the vector elements, but does not resize the vector.

          // The call to erase that follows erases the unneeded cells (from remove_pos to the

          // end) and modifies the vector's size.

                  // Remove the element from the list.

          // If all elements were removed from the map entry, erase it.

        // The lazy map isn't used, iterate over the list elements and remove elements that satisfy

        // the predicate.

    /*

     * Creates and populates a map if the number of headers is at least 3.

     *

     * @return if a map was created.

     */

    bool maybeMakeMap();

    /*

     * Removes a given key and its values from the HeaderList.

     *

     * @return the number of bytes that were removed.

     */

    size_t remove(absl::string_view key);

  private:

    std::list<HeaderEntryImpl> headers_;

    HeaderNode pseudo_headers_end_;

    HeaderLazyMap lazy_map_;

  };

  void insertByKey(HeaderString&& key, HeaderString&& value);

  static uint64_t appendToHeader(HeaderString& header, absl::string_view data,

                                 absl::string_view delimiter = ",");

  HeaderEntryImpl& maybeCreateInline(HeaderEntryImpl** entry, const LowerCaseString& key);

  HeaderEntryImpl& maybeCreateInline(HeaderEntryImpl** entry, const LowerCaseString& key,

                                     HeaderString&& value);

  HeaderMap::NonConstGetResult getExisting(absl::string_view key);

  size_t removeExisting(absl::string_view key);

  size_t removeInline(HeaderEntryImpl** entry);

  void updateSize(uint64_t from_size, uint64_t to_size);

  void addSize(uint64_t size);

  void subtractSize(uint64_t size);

  virtual absl::optional<StaticLookupResponse> staticLookup(absl::string_view) PURE;

  virtual void clearInline() PURE;

  virtual HeaderEntryImpl** inlineHeaders() PURE;

  HeaderList headers_;

  // TODO(mattklein123): The formatter does not currently get copied when a header map gets

  // copied. This may be problematic in certain cases like request shadowing. This is omitted

  // on purpose until someone asks for it, at which point a clone() method can be created to

  // avoid using extra space/processing for a shared_ptr.

  StatefulHeaderKeyFormatterPtr formatter_;

  // This holds the internal byte size of the HeaderMap.

  uint64_t cached_byte_size_ = 0;

  // This holds the max size of the headers in kilobyte in the HeaderMap.

  const uint32_t max_headers_kb_ = UINT32_MAX;

  // This holds the max count of the headers in the HeaderMap.

  const uint32_t max_headers_count_ = UINT32_MAX;

  // For benchmarking to access non-public methods to test staticLookup.

  friend class StaticLookupBenchmarker;

};

/**

 * Typed derived classes for all header map types. This class implements the actual typed

 * interface and for the majority of methods just passes through to the HeaderMapImpl mix-in. Per

 * above, this avoids virtual inheritance.

 */

template <class Interface> class TypedHeaderMapImpl : public HeaderMapImpl, public Interface {

public:

  TypedHeaderMapImpl(const uint32_t max_headers_kb = UINT32_MAX,

                     const uint32_t max_headers_count = UINT32_MAX)

  // Implementation of Http::HeaderMap that passes through to HeaderMapImpl.

  // Generic custom header functions for each fully typed interface. To avoid accidental issues,

  // the Handle type is different for each interface, which is why these functions live here vs.

  // inside HeaderMapImpl.

  using Handle = CustomInlineHeaderRegistry::Handle<Interface::header_map_type>;

protected:

  virtual const HeaderEntryImpl* const* constInlineHeaders() const PURE;

};

#define DEFINE_HEADER_HANDLE(name)                                                                 \

  Handle name =                                                                                    \

      CustomInlineHeaderRegistry::getInlineHeader<header_map_type>(Headers::get().name).value();

/**

 * Concrete implementation of RequestHeaderMap which allows for variable custom registered inline

 * headers.

 */

class RequestHeaderMapImpl final : public TypedHeaderMapImpl<RequestHeaderMap>,

                                   public InlineStorage {

public:

  static std::unique_ptr<RequestHeaderMapImpl>

  create(const uint32_t max_headers_kb = UINT32_MAX,

  INLINE_REQ_STRING_HEADERS(DEFINE_INLINE_HEADER_STRING_FUNCS)

  INLINE_REQ_NUMERIC_HEADERS(DEFINE_INLINE_HEADER_NUMERIC_FUNCS)

  INLINE_REQ_RESP_STRING_HEADERS(DEFINE_INLINE_HEADER_STRING_FUNCS)

  INLINE_REQ_RESP_NUMERIC_HEADERS(DEFINE_INLINE_HEADER_NUMERIC_FUNCS)

protected:

  // NOTE: Because inline_headers_ is a variable size member, it must be the last member in the

  // most derived class. This forces the definition of the following three functions to also be

  // in the most derived class and thus duplicated. There may be a way to consolidate thus but it's

  // not clear and can be deferred for now.

private:

  struct HeaderHandleValues {

    INLINE_REQ_STRING_HEADERS(DEFINE_HEADER_HANDLE)

    INLINE_REQ_NUMERIC_HEADERS(DEFINE_HEADER_HANDLE)

    INLINE_REQ_RESP_STRING_HEADERS(DEFINE_HEADER_HANDLE)

    INLINE_REQ_RESP_NUMERIC_HEADERS(DEFINE_HEADER_HANDLE)

  };

  using HeaderHandles = ConstSingleton<HeaderHandleValues>;

  RequestHeaderMapImpl(const uint32_t max_headers_kb = UINT32_MAX,

                       const uint32_t max_headers_count = UINT32_MAX)

  HeaderEntryImpl* inline_headers_[];

};

/**

 * Concrete implementation of RequestTrailerMap which allows for variable custom registered inline

 * headers.

 */

class RequestTrailerMapImpl final : public TypedHeaderMapImpl<RequestTrailerMap>,

                                    public InlineStorage {

public:

  static std::unique_ptr<RequestTrailerMapImpl>

  create(const uint32_t max_headers_kb = UINT32_MAX,

protected:

  // See comment in RequestHeaderMapImpl.

private:

  RequestTrailerMapImpl(const uint32_t max_headers_kb = UINT32_MAX,

                        const uint32_t max_headers_count = UINT32_MAX)

  HeaderEntryImpl* inline_headers_[];

};

/**

 * Concrete implementation of ResponseHeaderMap which allows for variable custom registered inline

 * headers.

 */

class ResponseHeaderMapImpl final : public TypedHeaderMapImpl<ResponseHeaderMap>,

                                    public InlineStorage {

public:

  static std::unique_ptr<ResponseHeaderMapImpl>

  create(const uint32_t max_headers_kb = UINT32_MAX,

  INLINE_RESP_STRING_HEADERS(DEFINE_INLINE_HEADER_STRING_FUNCS)

  INLINE_RESP_NUMERIC_HEADERS(DEFINE_INLINE_HEADER_NUMERIC_FUNCS)

  INLINE_REQ_RESP_STRING_HEADERS(DEFINE_INLINE_HEADER_STRING_FUNCS)

  INLINE_REQ_RESP_NUMERIC_HEADERS(DEFINE_INLINE_HEADER_NUMERIC_FUNCS)

  INLINE_RESP_STRING_HEADERS_TRAILERS(DEFINE_INLINE_HEADER_STRING_FUNCS)

  INLINE_RESP_NUMERIC_HEADERS_TRAILERS(DEFINE_INLINE_HEADER_NUMERIC_FUNCS)

protected:

  // See comment in RequestHeaderMapImpl.

private:

  struct HeaderHandleValues {

    INLINE_RESP_STRING_HEADERS(DEFINE_HEADER_HANDLE)

    INLINE_RESP_NUMERIC_HEADERS(DEFINE_HEADER_HANDLE)

    INLINE_REQ_RESP_STRING_HEADERS(DEFINE_HEADER_HANDLE)

    INLINE_REQ_RESP_NUMERIC_HEADERS(DEFINE_HEADER_HANDLE)

    INLINE_RESP_STRING_HEADERS_TRAILERS(DEFINE_HEADER_HANDLE)

    INLINE_RESP_NUMERIC_HEADERS_TRAILERS(DEFINE_HEADER_HANDLE)

  };

  using HeaderHandles = ConstSingleton<HeaderHandleValues>;

  ResponseHeaderMapImpl(const uint32_t max_headers_kb = UINT32_MAX,

                        const uint32_t max_headers_count = UINT32_MAX)

  HeaderEntryImpl* inline_headers_[];

};

/**

 * Concrete implementation of ResponseTrailerMap which allows for variable custom registered

 * inline headers.

 */

class ResponseTrailerMapImpl final : public TypedHeaderMapImpl<ResponseTrailerMap>,

                                     public InlineStorage {

public:

  static std::unique_ptr<ResponseTrailerMapImpl>

  create(const uint32_t max_headers_kb = UINT32_MAX,

  INLINE_RESP_STRING_HEADERS_TRAILERS(DEFINE_INLINE_HEADER_STRING_FUNCS)

  INLINE_RESP_NUMERIC_HEADERS_TRAILERS(DEFINE_INLINE_HEADER_NUMERIC_FUNCS)

protected:

  // See comment in RequestHeaderMapImpl.

private:

  struct HeaderHandleValues {

    INLINE_RESP_STRING_HEADERS_TRAILERS(DEFINE_HEADER_HANDLE)

    INLINE_RESP_NUMERIC_HEADERS_TRAILERS(DEFINE_HEADER_HANDLE)

  };

  using HeaderHandles = ConstSingleton<HeaderHandleValues>;

  ResponseTrailerMapImpl(const uint32_t max_headers_kb = UINT32_MAX,

                         const uint32_t max_headers_count = UINT32_MAX)

  HeaderEntryImpl* inline_headers_[];

};

class TunnelResponseHeadersOrTrailersImpl : public TunnelResponseHeadersOrTrailers {

public:

  ProtobufTypes::MessagePtr serializeAsProto() const override;

};

template <class T>

std::unique_ptr<T>

  // TODO(mattklein123): Use of this function allows copying a request header map into a response

  // header map, etc. which is probably not what we want. Unfortunately, we do this on purpose in

  // a few places when dealing with gRPC headers/trailers conversions so it's not trivial to remove.

  // We should revisit this to figure how to make this a bit safer as a non-intentional conversion

  // may have surprising results with different O(1) headers, implementations, etc.

struct EmptyHeaders {

  RequestHeaderMapPtr request_headers = RequestHeaderMapImpl::create();

  ResponseHeaderMapPtr response_headers = ResponseHeaderMapImpl::create();

  ResponseTrailerMapPtr response_trailers = ResponseTrailerMapImpl::create();

};

using StaticEmptyHeaders = ConstSingleton<EmptyHeaders>;

class HeaderMapImplUtility {

public:

  struct HeaderMapImplInfo {

    // Human readable name for the header map used in info logging.

    std::string name_;

    // The byte size of the header map including both fixed space as well as variable space used

    // by the registered custom headers.

    size_t size_;

    // All registered custom headers for the header map.

    std::vector<std::string> registered_headers_;

  };

  /**

   * Fetch detailed information about each header map implementation for use in logging.

   */

  static std::vector<HeaderMapImplInfo> getAllHeaderMapImplInfo();

};

} // namespace Http

} // namespace Envoy