zf

table.ex (8198B)

---

 defmodule HPAX.Table do
   @moduledoc false
 
   defstruct [
     :max_table_size,
     entries: [],
     size: 0,
     length: 0
   ]
 
   @type t() :: %__MODULE__{
           max_table_size: non_neg_integer(),
           entries: [{binary(), binary()}],
           size: non_neg_integer(),
           length: non_neg_integer()
         }
 
   @static_table [
     {":authority", nil},
     {":method", "GET"},
     {":method", "POST"},
     {":path", "/"},
     {":path", "/index.html"},
     {":scheme", "http"},
     {":scheme", "https"},
     {":status", "200"},
     {":status", "204"},
     {":status", "206"},
     {":status", "304"},
     {":status", "400"},
     {":status", "404"},
     {":status", "500"},
     {"accept-charset", nil},
     {"accept-encoding", "gzip, deflate"},
     {"accept-language", nil},
     {"accept-ranges", nil},
     {"accept", nil},
     {"access-control-allow-origin", nil},
     {"age", nil},
     {"allow", nil},
     {"authorization", nil},
     {"cache-control", nil},
     {"content-disposition", nil},
     {"content-encoding", nil},
     {"content-language", nil},
     {"content-length", nil},
     {"content-location", nil},
     {"content-range", nil},
     {"content-type", nil},
     {"cookie", nil},
     {"date", nil},
     {"etag", nil},
     {"expect", nil},
     {"expires", nil},
     {"from", nil},
     {"host", nil},
     {"if-match", nil},
     {"if-modified-since", nil},
     {"if-none-match", nil},
     {"if-range", nil},
     {"if-unmodified-since", nil},
     {"last-modified", nil},
     {"link", nil},
     {"location", nil},
     {"max-forwards", nil},
     {"proxy-authenticate", nil},
     {"proxy-authorization", nil},
     {"range", nil},
     {"referer", nil},
     {"refresh", nil},
     {"retry-after", nil},
     {"server", nil},
     {"set-cookie", nil},
     {"strict-transport-security", nil},
     {"transfer-encoding", nil},
     {"user-agent", nil},
     {"vary", nil},
     {"via", nil},
     {"www-authenticate", nil}
   ]
 
   @static_table_size length(@static_table)
   @dynamic_table_start @static_table_size + 1
 
   @doc """
   Creates a new HPACK table with the given maximum size.
 
   The maximum size is not the maximum number of entries but rather the maximum size as defined in
   http://httpwg.org/specs/rfc7541.html#maximum.table.size.
   """
   @spec new(non_neg_integer()) :: t()
   def new(max_table_size) do
     %__MODULE__{max_table_size: max_table_size}
   end
 
   @doc """
   Adds the given header to the given table.
 
   If the new entry does not fit within the max table size then the oldest entries will be evicted.
 
   Header names should be lowercase when added to the HPACK table
   as per the [HTTP/2 spec](https://http2.github.io/http2-spec/#rfc.section.8.1.2):
 
   > header field names MUST be converted to lowercase prior to their encoding in HTTP/2
 
   """
   @spec add(t(), binary(), binary()) :: t()
   def add(%__MODULE__{} = table, name, value) do
     %{max_table_size: max_table_size, size: size} = table
     entry_size = entry_size(name, value)
 
     cond do
       # An attempt to add an entry larger than the maximum size causes the table to be emptied of
       # all existing entries and results in an empty table.
       entry_size > max_table_size ->
         %{table | entries: [], size: 0, length: 0}
 
       size + entry_size > max_table_size ->
         table
         |> resize(max_table_size - entry_size)
         |> add_header(name, value, entry_size)
 
       true ->
         add_header(table, name, value, entry_size)
     end
   end
 
   defp add_header(%__MODULE__{} = table, name, value, entry_size) do
     %{entries: entries, size: size, length: length} = table
     %{table | entries: [{name, value} | entries], size: size + entry_size, length: length + 1}
   end
 
   @doc """
   Looks up a header by index `index` in the given `table`.
 
   Returns `{:ok, {name, value}}` if a header is found at the given `index`, otherwise returns
   `:error`. `value` can be a binary in case both the header name and value are present in the
   table, or `nil` if only the name is present (this can only happen in the static table).
   """
   @spec lookup_by_index(t(), pos_integer()) :: {:ok, {binary(), binary() | nil}} | :error
   def lookup_by_index(table, index)
 
   # Static table
   for {header, index} <- Enum.with_index(@static_table, 1) do
     def lookup_by_index(%__MODULE__{}, unquote(index)), do: {:ok, unquote(header)}
   end
 
   def lookup_by_index(%__MODULE__{length: 0}, _index) do
     :error
   end
 
   def lookup_by_index(%__MODULE__{entries: entries, length: length}, index)
       when index in @dynamic_table_start..(@dynamic_table_start + length - 1) do
     {:ok, Enum.at(entries, index - @dynamic_table_start)}
   end
 
   def lookup_by_index(%__MODULE__{}, _index) do
     :error
   end
 
   @doc """
   Looks up the index of a header by its name and value.
 
   It returns:
 
     * `{:full, index}` if the full header (name and value) are present in the table at `index`
 
     * `{:name, index}` if `name` is present in the table but with a different value than `value`
 
     * `:not_found` if the header name is not in the table at all
 
   Header names should be lowercase when looked up in the HPACK table
   as per the [HTTP/2 spec](https://http2.github.io/http2-spec/#rfc.section.8.1.2):
 
   > header field names MUST be converted to lowercase prior to their encoding in HTTP/2
 
   """
   @spec lookup_by_header(t(), binary(), binary() | nil) ::
           {:full, pos_integer()} | {:name, pos_integer()} | :not_found
   def lookup_by_header(table, name, value)
 
   def lookup_by_header(%__MODULE__{entries: entries}, name, value) do
     case static_lookup_by_header(name, value) do
       {:full, _index} = result ->
         result
 
       {:name, index} ->
         # Check if we get full match in the dynamic tabble
         case dynamic_lookup_by_header(entries, name, value, @dynamic_table_start, nil) do
           {:full, _index} = result -> result
           _other -> {:name, index}
         end
 
       :not_found ->
         dynamic_lookup_by_header(entries, name, value, @dynamic_table_start, nil)
     end
   end
 
   for {{name, value}, index} when is_binary(value) <- Enum.with_index(@static_table, 1) do
     defp static_lookup_by_header(unquote(name), unquote(value)) do
       {:full, unquote(index)}
     end
   end
 
   static_table_names =
     @static_table
     |> Enum.map(&elem(&1, 0))
     |> Enum.with_index(1)
     |> Enum.uniq_by(&elem(&1, 0))
 
   for {name, index} <- static_table_names do
     defp static_lookup_by_header(unquote(name), _value) do
       {:name, unquote(index)}
     end
   end
 
   defp static_lookup_by_header(_name, _value) do
     :not_found
   end
 
   defp dynamic_lookup_by_header([{name, value} | _rest], name, value, index, _name_index) do
     {:full, index}
   end
 
   defp dynamic_lookup_by_header([{name, _} | rest], name, value, index, _name_index) do
     dynamic_lookup_by_header(rest, name, value, index + 1, index)
   end
 
   defp dynamic_lookup_by_header([_other | rest], name, value, index, name_index) do
     dynamic_lookup_by_header(rest, name, value, index + 1, name_index)
   end
 
   defp dynamic_lookup_by_header([], _name, _value, _index, name_index) do
     if name_index, do: {:name, name_index}, else: :not_found
   end
 
   @doc """
   Resizes the table.
 
   If the existing entries do not fit in the new table size the oldest entries are evicted.
   """
   @spec resize(t(), non_neg_integer()) :: t()
   def resize(%__MODULE__{entries: entries, size: size} = table, new_size) do
     {new_entries_reversed, new_size} = evict_towards_size(Enum.reverse(entries), size, new_size)
 
     %{
       table
       | entries: Enum.reverse(new_entries_reversed),
         size: new_size,
         length: length(new_entries_reversed)
     }
   end
 
   defp evict_towards_size([{name, value} | rest], size, max_target_size) do
     new_size = size - entry_size(name, value)
 
     if new_size <= max_target_size do
       {rest, new_size}
     else
       evict_towards_size(rest, new_size, max_target_size)
     end
   end
 
   defp evict_towards_size([], 0, _max_target_size) do
     {[], 0}
   end
 
   defp entry_size(name, value) do
     byte_size(name) + byte_size(value) + 32
   end
 
   # Made public to be used in tests.
   @doc false
   def __static_table__() do
     @static_table
   end
 end