# Copyright, 2018, by Samuel G. D. Williams. <http://www.codeotaku.com>
# Copyrigh, 2013, by Ilya Grigorik.
# 
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
# 
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
# THE SOFTWARE.

require_relative 'huffman'

module Protocol
	# Implementation of header compression for HTTP 2.0 (HPACK) format adapted
	# to efficiently represent HTTP headers in the context of HTTP 2.0.
	#
	# - http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-10
	module HPACK
		# Header representation as defined by the spec.
		HEADER_REPRESENTATION = {
			indexed: {prefix: 7, pattern: 0x80},
			incremental: {prefix: 6, pattern: 0x40},
			no_index: {prefix: 4, pattern: 0x00},
			never_indexed: {prefix: 4, pattern: 0x10},
			change_table_size: {prefix: 5, pattern: 0x20},
		}
		
		# To decompress header blocks, a decoder only needs to maintain a
		# dynamic table as a decoding context.
		# No other state information is needed.
		class Context
			# @private
			# Static table
			# - http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-10#appendix-A
			STATIC_TABLE = [
				[':authority',                  ''],
				[':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',              ''],
				['accept-encoding',             'gzip, deflate'],
				['accept-language',             ''],
				['accept-ranges',               ''],
				['accept',                      ''],
				['access-control-allow-origin', ''],
				['age',                         ''],
				['allow',                       ''],
				['authorization',               ''],
				['cache-control',               ''],
				['content-disposition',         ''],
				['content-encoding',            ''],
				['content-language',            ''],
				['content-length',              ''],
				['content-location',            ''],
				['content-range',               ''],
				['content-type',                ''],
				['cookie',                      ''],
				['date',                        ''],
				['etag',                        ''],
				['expect',                      ''],
				['expires',                     ''],
				['from',                        ''],
				['host',                        ''],
				['if-match',                    ''],
				['if-modified-since',           ''],
				['if-none-match',               ''],
				['if-range',                    ''],
				['if-unmodified-since',         ''],
				['last-modified',               ''],
				['link',                        ''],
				['location',                    ''],
				['max-forwards',                ''],
				['proxy-authenticate',          ''],
				['proxy-authorization',         ''],
				['range',                       ''],
				['referer',                     ''],
				['refresh',                     ''],
				['retry-after',                 ''],
				['server',                      ''],
				['set-cookie',                  ''],
				['strict-transport-security',   ''],
				['transfer-encoding',           ''],
				['user-agent',                  ''],
				['vary',                        ''],
				['via',                         ''],
				['www-authenticate',            ''],
			].each {|pair| pair.each(&:freeze).freeze}.freeze
			
			# Initializes compression context with appropriate client/server defaults and maximum size of the dynamic table.
			#
			# @param table [Array] Table of header key-value pairs.
			# @option huffman [Symbol] One of `:always`, `:never`, `:shorter`. Controls use of compression.
			# @option index [Symbol] One of `:all`, `:static`, `:never`. Controls use of static/dynamic tables.
			# @option table_size [Integer] The current maximum dynamic table size.
			def initialize(table = nil, huffman: :shorter, index: :all, table_size: 4096)
				@huffman = huffman
				@index = index
				
				@table_size = table_size
				
				@table = (table&.dup) || []
			end
			
			def initialize_copy(other)
				super
				
				# This is the only mutable state:
				@table = @table.dup
			end
			
			# Current table of header key-value pairs.
			attr :table
			
			attr :huffman
			attr :index
			
			attr :table_size
			
			# Finds an entry in current dynamic table by index.
			# Note that index is zero-based in this module.
			#
			# If the index is greater than the last index in the static table,
			# an entry in the dynamic table is dereferenced.
			#
			# If the index is greater than the last header index, an error is raised.
			#
			# @param index [Integer] zero-based index in the dynamic table.
			# @return [Array] +[key, value]+
			def dereference(index)
				# NOTE: index is zero-based in this module.
				value = STATIC_TABLE[index] || @table[index - STATIC_TABLE.size]
				
				raise CompressionError, "Index #{index} too large" unless value
				
				return value
			end

			# Header Block Processing
			# - http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-10#section-4.1
			#
			# @param command [Hash] {type:, name:, value:, index:}
			# @return [Array] +[name, value]+ header field that is added to the decoded header list
			def decode(command)
				emit = nil

				case command[:type]
				when :change_table_size
					self.table_size = command[:value]

				when :indexed
					# Indexed Representation
					# An _indexed representation_ entails the following actions:
					# o  The header field corresponding to the referenced entry in either
					# the static table or dynamic table is added to the decoded header
					# list.
					idx = command[:name]

					k, v = dereference(idx)
					emit = [k, v]

				when :incremental, :no_index, :never_indexed
					# A _literal representation_ that is _not added_ to the dynamic table
					# entails the following action:
					# o  The header field is added to the decoded header list.

					# A _literal representation_ that is _added_ to the dynamic table
					# entails the following actions:
					# o  The header field is added to the decoded header list.
					# o  The header field is inserted at the beginning of the dynamic table.

					if command[:name].is_a? Integer
						k, v = dereference(command[:name])

						command = command.dup
						command[:index] ||= command[:name]
						command[:value] ||= v
						command[:name] = k
					end

					emit = [command[:name], command[:value]]

					add_to_table(emit) if command[:type] == :incremental

				else
					raise CompressionError, "Invalid type: #{command[:type]}"
				end

				return emit
			end

			# Plan header compression according to +@index+
			#  :never   Do not use dynamic table or static table reference at all.
			#  :static  Use static table only.
			#  :all     Use all of them.
			#
			# @param headers [Array] +[[name, value], ...]+
			# @return [Array] array of commands
			def encode(headers)
				commands = []
				
				# Literals commands are marked with :no_index when index is not used
				no_index = [:static, :never].include?(@index)
				
				headers.each do |field, value|
					command = add_command(field, value)
					command[:type] = :no_index if no_index && command[:type] == :incremental
					commands << command
					
					decode(command)
				end
				
				return commands
			end

			# Emits command for a header.
			# Prefer static table over dynamic table.
			# Prefer exact match over name-only match.
			#
			# +@index+ controls whether to use the dynamic table,
			# static table, or both.
			#  :never   Do not use dynamic table or static table reference at all.
			#  :static  Use static table only.
			#  :all     Use all of them.
			#
			# @param header [Array] +[name, value]+
			# @return [Hash] command
			def add_command(*header)
				exact = nil
				name_only = nil

				if [:all, :static].include?(@index)
					STATIC_TABLE.each_index do |i|
						if STATIC_TABLE[i] == header
							exact ||= i
							break
						elsif STATIC_TABLE[i].first == header.first
							name_only ||= i
						end
					end
				end
				if [:all].include?(@index) && !exact
					@table.each_index do |i|
						if @table[i] == header
							exact ||= i + STATIC_TABLE.size
							break
						elsif @table[i].first == header.first
							name_only ||= i + STATIC_TABLE.size
						end
					end
				end

				if exact
					{name: exact, type: :indexed}
				elsif name_only
					{name: name_only, value: header.last, type: :incremental}
				else
					{name: header.first, value: header.last, type: :incremental}
				end
			end

			# Alter dynamic table size.
			#  When the size is reduced, some headers might be evicted.
			def table_size= size
				@table_size = size
				size_check(nil)
			end

			# Returns current table size in octets
			# @return [Integer]
			def current_table_size
				@table.inject(0) {|r, (k, v)| r + k.bytesize + v.bytesize + 32}
			end

			private

			# Add a name-value pair to the dynamic table.
			# Older entries might have been evicted so that
			# the new entry fits in the dynamic table.
			#
			# @param command [Array] +[name, value]+
			def add_to_table(command)
				return unless size_check(command)
				@table.unshift(command)
			end

			# To keep the dynamic table size lower than or equal to @table_size,
			# remove one or more entries at the end of the dynamic table.
			#
			# @param command [Hash]
			# @return [Boolean] whether +command+ fits in the dynamic table.
			def size_check(command)
				cursize = current_table_size
				cmdsize = command.nil? ? 0 : command[0].bytesize + command[1].bytesize + 32

				while cursize + cmdsize > @table_size
					break if @table.empty?

					e = @table.pop
					cursize -= e[0].bytesize + e[1].bytesize + 32
				end

				cmdsize <= @table_size
			end
		end
	end
end