path: root/src/libdisfluid/disfluid-cache-entry-key.h

#ifndef DISFLUID_DISFLUID_CACHE_ENTRY_KEY_INCLUDED
# define DISFLUID_DISFLUID_CACHE_ENTRY_KEY_INCLUDED

MAYBE_UNUSED static int
compute_cache_key (const char *restrict request_scheme,
		   const char *restrict request_header,
		   const char *restrict response_header,
		   size_t max_memory, char *restrict memory);
# include <assert.h>

# include "disfluid-init.h"

static inline int
cache_entry_key_push (const char *str, size_t length, size_t *max_memory,
		      char *restrict *memory)
{
  if (length >= *max_memory)
    {
      return -2;
    }
  memcpy (*memory, str, length);
  (*memory)[length] = '\0';
  *max_memory -= length;
  *memory += length;
  return 0;
}

static inline int
cache_entry_key_find_method (const char *request_header, const char **method,
			     const char **after_method, size_t *method_length)
{
  /* The method is found at the start of the request header. It is a
     succession of ASCII upper-case letters. */
  *method = request_header;
  *method_length = 0;
  while (request_header[*method_length] >= 'A'
	 && request_header[*method_length] <= 'Z')
    {
      *method_length += 1;
    }
  *after_method = NULL;
  if (request_header[*method_length] == ' ' && *method_length > 0)
    {
      *after_method = request_header + *method_length + 1;
      return 0;
    }
  return -1;
}

static inline int
cache_entry_key_next_line (const char **txt)
{
  /* Advance *txt until after the next \r\n. */
  static const char *eol = "\r\n";
  const char *next_eol = strstr (*txt, eol);
  if (next_eol == NULL)
    {
      return -1;
    }
  *txt = next_eol + strlen (eol);
  return 0;
}

static inline int
cache_entry_key_parse_header (const char **header_line,
			      const char **header_name,
			      size_t *header_name_length,
			      const char **header_value,
			      size_t *header_value_length)
{
  static const char *separator = ":";
  static const char *line_separator = "\r\n";
  *header_name = *header_line;
  *header_name_length = 0;
  *header_value = *header_line;
  *header_value_length = 0;
  const char *colon = strstr (*header_line, separator);
  const char *next_eol = strstr (*header_line, line_separator);
  if (colon == NULL
      || next_eol == NULL
      || ((next_eol - *header_line) < (colon - *header_line)))
    {
      /* the newline happens before the colon, or there isn’t a
         newline or a colon. */
      return -1;
    }
  *header_name_length = colon - *header_line;
  *header_value = colon + strlen (separator);
  while (**header_value == ' ')
    {
      (*header_value) += 1;
    }
  *header_value_length = next_eol - *header_value;
  /* Advance to the next line. */
  *header_line = next_eol + strlen (line_separator);
  return 0;
}

static inline int
cache_entry_key_find_header (const char **header_line,
			     const char *header_name,
			     size_t header_name_length,
			     const char **header_value,
			     size_t *header_value_length)
{
  /* Return +1 if the header is not found, 0 if the header is found
     and so *header_value / *header_value_length are set, -1 if the
     header is not HTTP. */
  const char *next_header_name = NULL;
  size_t next_header_name_length;
  int error = 0;
  while (true)
    {
      if (strncmp (*header_line, "\r\n", strlen ("\r\n")) == 0)
	{
	  /* End of header. */
	  return +1;
	}
      error =
	cache_entry_key_parse_header (header_line, &next_header_name,
				      &next_header_name_length, header_value,
				      header_value_length);
      if (error != 0)
	{
	  return error;
	}
      size_t prefix_length = 0;
      if (next_header_name_length == header_name_length)
	{
	  for (prefix_length = 0; prefix_length < header_name_length;
	       prefix_length++)
	    {
	      char c = next_header_name[prefix_length];
	      char expected = header_name[prefix_length];
	      if (c >= 'A' && c <= 'Z')
		{
		  c += ('a' - 'A');
		}
	      if (expected >= 'A' && expected <= 'Z')
		{
		  expected += ('a' - 'A');
		}
	      if (c != expected)
		{
		  /* This is not the header that we are looking for. */
		  break;
		}
	    }
	  if (prefix_length == header_name_length)
	    {
	      return 0;
	    }
	}
    }
}

static inline int
cache_entry_key_find_host (const char *request_header,
			   const char **host, size_t *host_length)
{
  int error = 0;
  /* Discard the first line of the request header. */
  if (error == 0)
    {
      error = cache_entry_key_next_line (&request_header);
    }
  if (error == 0)
    {
      error =
	cache_entry_key_find_header (&request_header, "host", strlen ("host"),
				     host, host_length);
    }
  if (error == 1)
    {
      /* Host not found. Not valid in HTTP/1.1. */
      error = -1;
    }
  return error;
}

static inline int
cache_entry_key_find_all_header_values (const char *headers,
					const char *header_name,
					size_t header_name_length,
					int (*iter) (void *, const char *,
						     size_t), void *context)
{
  int error = 0;
  while (error == 0)
    {
      const char *value;
      size_t value_length;
      error =
	cache_entry_key_find_header (&headers, header_name,
				     header_name_length, &value,
				     &value_length);
      if (error == 1)
	{
	  /* Done. */
	  return 0;
	}
      if (error == 0)
	{
	  error = iter (context, value, value_length);
	}
    }
  return error;
}

struct cache_entry_key_copy_context
{
  /* Paste all values of a specified header, separated by commas. */
  size_t max_memory;
  char *memory;
  bool needs_separator;
};

static inline int
cache_entry_key_copy_cb (void *ptr, const char *value, size_t value_length)
{
  struct cache_entry_key_copy_context *context = ptr;
  int error = 0;
  if (context->needs_separator)
    {
      error =
	cache_entry_key_push (",", strlen (","), &(context->max_memory),
			      &(context->memory));
    }
  if (error == 0)
    {
      error =
	cache_entry_key_push (value, value_length, &(context->max_memory),
			      &(context->memory));
    }
  context->needs_separator = true;
  return error;
}

static inline int
cache_entry_key_paste_header_values (const char *headers,
				     const char *header_name,
				     size_t header_name_length,
				     size_t *max_memory, char **memory)
{
  struct cache_entry_key_copy_context context = {
    .max_memory = *max_memory,
    .memory = *memory,
    .needs_separator = false
  };
  int error = cache_entry_key_find_all_header_values (headers, header_name,
						      header_name_length,
						      cache_entry_key_copy_cb,
						      &context);
  *max_memory = context.max_memory;
  *memory = context.memory;
  return error;
}

struct cache_entry_key_multiple_iterator
{
  int (*iter) (void *, const char *, size_t);
  void *context;
};

static inline void
cache_entry_key_next_atom (const char **restrict line,
			   size_t *restrict line_length,
			   const char **restrict atom,
			   size_t *restrict atom_length)
{
  /* An atom starts after the optional whitespace, and ends at the end
     of the line or at the first comma, whichever comes first. */
  while (*line_length > 0 && **line == ' ')
    {
      *line_length -= 1;
      *line += 1;
    }
  *atom = *line;
  for (*atom_length = 0;
       (*atom_length < *line_length
	&& (*line)[*atom_length] != ','); (*atom_length)++)
    ;
  assert (*atom_length == *line_length || (*line)[*atom_length] == ',');
  *line += *atom_length;
  *line_length -= *atom_length;
  if (*line_length > 0)
    {
      *line += 1;		/* also consume the comma. */
      *line_length -= 1;
    }
}

static inline int
cache_entry_key_iter_multiple (void *context, const char *value,
			       size_t value_length)
{
  struct cache_entry_key_multiple_iterator *it = context;
  const char *next_atom = NULL;
  size_t next_atom_length = 0;
  int error = 0;
  while (error == 0 && value_length > 0)
    {
      cache_entry_key_next_atom (&value, &value_length, &next_atom,
				 &next_atom_length);
      error = it->iter (it->context, next_atom, next_atom_length);
    }
  return error;
}

static inline int
cache_entry_key_find_all_varying_headers (const char *response_headers,
					  int (*iter) (void *, const char *,
						       size_t), void *context)
{
  struct cache_entry_key_multiple_iterator it = {
    .iter = iter,
    .context = context
  };
  return cache_entry_key_find_all_header_values (response_headers, "vary",
						 strlen ("vary"),
						 cache_entry_key_iter_multiple,
						 &it);
}

struct cache_entry_key_vary_iterator_context
{
  /* The goal of the iterator is to construct the key. */
  const char *request_headers;
  size_t max_memory;
  char *memory;
};

static inline int
cache_entry_key_vary_iterator_cb (void *ptr, const char *next_varying_header,
				  size_t next_varying_header_length)
{
  struct cache_entry_key_vary_iterator_context *context = ptr;
  int error = 0;
  /* Push the value of each header in the request that matches
     next_varying_header, with a comma separator. After that, push
     \r\n. */
  error =
    cache_entry_key_paste_header_values (context->request_headers,
					 next_varying_header,
					 next_varying_header_length,
					 &(context->max_memory),
					 &(context->memory));
  if (error == 0)
    {
      error =
	cache_entry_key_push ("\r\n", strlen ("\r\n"), &(context->max_memory),
			      &(context->memory));
    }
  return error;
}

static int
compute_cache_key (const char *restrict request_scheme,
		   const char *restrict request_header,
		   const char *restrict response_header,
		   size_t max_memory, char *restrict memory)
{
  ensure_init ();
  /* A cache entry key is a string, of the form:
     METHOD FULL-URI\r\n
     VALUE FOR 1ST VARYING HEADER, COMBINED WITH COMMAS\r\n
     VALUE FOR 2ND VARYING HEADER, …\r\n
     \0
   */
  /* Return: 0 on success, -1 if there is an error in request or
     response header, -2 if there is not enough memory. */
  /* If the response header has multiple Vary: header, then the list
     of varying headers is the accumulated list, in response header
     order, and in-field order, with multiplicity. */
  /* If a varying header is present multiple times in the request,
     then its value in the key is the comma-separated list of all
     occurences. in the request, in the order of appearance. */
  int error = 0;
  /* First, push the method and space. */
  const char *method;
  const char *after_method;
  size_t method_length;
  if (error == 0)
    {
      error =
	cache_entry_key_find_method (request_header, &method, &after_method,
				     &method_length);
    }
  if (error == 0)
    {
      error =
	cache_entry_key_push (method, method_length, &max_memory, &memory);
    }
  if (error == 0)
    {
      error = cache_entry_key_push (" ", strlen (" "), &max_memory, &memory);
    }
  /* Push the URI scheme and :// */
  if (error == 0)
    {
      error =
	cache_entry_key_push (request_scheme, strlen (request_scheme),
			      &max_memory, &memory);
    }
  if (error == 0)
    {
      error =
	cache_entry_key_push ("://", strlen ("://"), &max_memory, &memory);
    }
  /* Find the host and push it. */
  const char *host;
  size_t host_length;
  if (error == 0)
    {
      error = cache_entry_key_find_host (after_method, &host, &host_length);
    }
  if (error == 0)
    {
      error = cache_entry_key_push (host, host_length, &max_memory, &memory);
    }
  /* Find the URI and push it. */
  if (error == 0)
    {
      const char *space_before_version = strstr (after_method, " ");
      if (space_before_version == NULL)
	{
	  error = -1;
	}
      else
	{
	  error =
	    cache_entry_key_push (after_method,
				  space_before_version - after_method,
				  &max_memory, &memory);
	}
    }
  if (error == 0)
    {
      error =
	cache_entry_key_push ("\r\n", strlen ("\r\n"), &max_memory, &memory);
    }
  /* Iterate over all varying cache headers (there might be many Vary:
     header lines in the response). */
  const char *request_headers = after_method;
  const char *response_headers = response_header;
  if (error == 0)
    {
      error = cache_entry_key_next_line (&request_headers);
    }
  if (error == 0)
    {
      error = cache_entry_key_next_line (&response_headers);
    }
  /* So request_headers is the first line of headers, and
     response_headers too. */
  if (error == 0)
    {
      struct cache_entry_key_vary_iterator_context context = {
	.request_headers = request_headers,
	.max_memory = max_memory,
	.memory = memory
      };
      error =
	cache_entry_key_find_all_varying_headers (response_headers,
						  cache_entry_key_vary_iterator_cb,
						  &context);
      max_memory = context.max_memory;
      memory = context.memory;
    }
  return error;
}

#endif /* DISFLUID_DISFLUID_CACHE_ENTRY_KEY_INCLUDED */