Construct a key from varied headers

8 files changed, 805 insertions, 2 deletions

diff --git a/bootstrap.conf b/bootstrap.conf
index 9c3997c..da85715 100644
--- a/bootstrap.conf
+++ b/bootstrap.conf
@@ -47,6 +47,7 @@ stdbool
 stdint
 stdio
 strdup
+strstr
 sys_stat
 time
 tmpfile
diff --git a/doc/disfluid.texi b/doc/disfluid.texi
index b3b8e06..7b6b30a 100644
--- a/doc/disfluid.texi
+++ b/doc/disfluid.texi
@@ -7,7 +7,7 @@
 @settitle Demanding Interoperability to Strengthen the Free (Libre) Web: Introducing Disfluid
 @c %**end of header
 
-@set UPDATED 13 March 2023
+@set UPDATED 19 March 2023
 @set UPDATED-MONTH March 2023
 @include version_number.texi
 
@@ -59,6 +59,7 @@ The software is available at
 @menu
 * Decentralized Authentication on the Web:: What is Disfluid?
 * Running disfluid::
+* The Disfluid Cache::
 @end menu
 
 @c *********************************************************************
@@ -106,4 +107,92 @@ Disfluid is packaged for the GNOME desktop as the Experiences
 application. Experiences provides a main menu on the top right of the
 screen.
 
+@node The Disfluid Cache
+@chapter The Disfluid Cache
+
+@cindex cache
+@cindex cache entry
+Disfluid caches frequently-used data, to avoid overloading the
+network. Each response and associated request are considered for cache
+storage. They constitute a @dfn{cache entry}.
+
+@cindex cache key
+Each cache entry file stores some metadata, a @dfn{cache key}, the
+response, and response body. To query the cache for an entry, the
+@dfn{primary key} combines the HTTP method and effective URI. When the
+response varies depending on a combination of headers, the values of
+the relevant request headers are also considered as a @dfn{secondary
+key}.
+
+For instance, suppose that the following HTTP 1.1 request made over
+https:
+@example
+GET /example HTTP/1.1
+Host: example.com
+Accept: text/plain
+Foo: bar
+Foo: other,thing
+If-None-Match: W/"hello", "world"
+If-None-Match: W/"hi :)"
+
+@end example
+
+has the following HTTP 1.1 response:
+
+@example
+HTTP/1.1 200 Hi
+Content-Type: text/plain
+ETag: W/\"hello\"
+Vary: accept, foo
+Vary: accept
+
+Hi :)
+@end example
+
+Then the @dfn{cache key} is composed as:
+
+@example
+GET https://example.com/example
+text/plain
+bar,other,thing
+text/plain
+@end example
+
+The first line of the cache key is the primary key. When querying the
+cache, you should know the value. There may be different responses
+that share the same primary key. You then have to examine the stored
+response, and compose the list of varied header values, in order, to
+narrow down the list of possible stored responses. Notice that you
+must respect the order and multiplicity of all varied headers, and you
+must aggregate all the values for duplicated request headers.
+
+If the response has a Vary header for a request header that is not set
+in the request, then the cache key has an empty corresponding line.
+
+@deftypefun int disfluid_compute_cache_key (const char *@var{request_scheme}, const char *@var{request_header}, const char *@var{response_header}, size_t @var{max_key}, char *@var{key})
+Write the cache key to @var{key}, up to @var{max_key}. The result is
+NUL-terminated.
+
+Return:
+
+@table @strong
+@item 0
+on success;
+@item -1
+if the key cannot be computed due to an HTTP/1.1 error in the arguments;
+@item -2
+if the allocated @var{key} is too small to contain the whole key plus
+a final NUL character.
+@end table
+
+@var{request_scheme}, @var{request_header}, @var{response_header} and
+@var{key} must be non-overlapping.
+@end deftypefun
+
+@cindex cache entry metadata
+Disfluid also store some metadata in the cache entry: the request and
+response dates, according to the client, a boolean flag to mark an
+entry as invalidated, and the HTTP scheme that was used (HTTP or
+HTTPS).
+
 @bye
diff --git a/include/Makefile.am b/include/Makefile.am
index 044edf6..ef55c6b 100644
--- a/include/Makefile.am
+++ b/include/Makefile.am
@@ -2,4 +2,5 @@ include_HEADERS += %D%/disfluid.h
 
 pkgincludedir = $(includedir)/disfluid
 
-dist_pkginclude_HEADERS = %D%/disfluid/cache_entry.h
+dist_pkginclude_HEADERS = \
+  %D%/disfluid/cache_entry.h
diff --git a/include/disfluid.h b/include/disfluid.h
index b117ab7..e6a17db 100644
--- a/include/disfluid.h
+++ b/include/disfluid.h
@@ -144,6 +144,12 @@ extern "C"
   LIBDISFLUID_CONST LIBDISFLUID_API const char
     *disfluid_translation_credits (void);
 
+  LIBDISFLUID_API extern int
+    disfluid_compute_cache_key (const char *request_scheme,
+				const char *request_header,
+				const char *response_header,
+				size_t max_key, char *key);
+
 # ifdef __cplusplus
 }
 # endif				/* __cplusplus */
diff --git a/src/libdisfluid/Makefile.am b/src/libdisfluid/Makefile.am
index aec9db5..1af0acc 100644
--- a/src/libdisfluid/Makefile.am
+++ b/src/libdisfluid/Makefile.am
@@ -3,6 +3,7 @@ lib_LTLIBRARIES += %D%/libdisfluid.la
 %C%_libdisfluid_la_SOURCES = \
   %D%/disfluid-authors.h \
   %D%/disfluid-cache-entry.h \
+  %D%/disfluid-cache-entry-key.h \
   %D%/disfluid-init.h \
   %D%/disfluid-tests.h \
   %D%/disfluid-version.h \
diff --git a/src/libdisfluid/disfluid-cache-entry-key.h b/src/libdisfluid/disfluid-cache-entry-key.h
new file mode 100644
index 0000000..9c2d3ba
--- /dev/null
+++ b/src/libdisfluid/disfluid-cache-entry-key.h
@@ -0,0 +1,473 @@
+#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 */
diff --git a/src/libdisfluid/disfluid-tests.h b/src/libdisfluid/disfluid-tests.h
index 21f4f43..e81d66f 100644
--- a/src/libdisfluid/disfluid-tests.h
+++ b/src/libdisfluid/disfluid-tests.h
@@ -10,6 +10,7 @@ static inline char *run_tests (size_t *n_tests, size_t *n_errors);
 # include "disfluid-init.h"
 # include "disfluid-version.h"
 # include "disfluid-cache-entry.h"
+# include "disfluid-cache-entry-key.h"
 
 # define BYTES * 1
 
@@ -416,6 +417,217 @@ START_TEST (test_normalize_timespec)
 END_TEST
 /* *INDENT-ON* */
 
+/* *INDENT-OFF* */
+START_TEST (test_cache_key_no_host)
+/* *INDENT-ON* */
+
+{
+  static const char *request = "\
+GET /example HTTP/1.1\r\n\
+If-None-Match: W/\"hello\", \"world\"\r\n\
+If-None-Match: W/\"hi :)\"\r\n\
+\r\n";
+  static const char *response = "\
+HTTP/1.1 200 Hi\r\n\
+Content-Type: text/plain\r\n\
+\r\n\
+Hi :)";
+  char memory[512];
+  int error =
+    compute_cache_key ("https", request, response, sizeof (memory), memory);
+  ck_assert_int_eq (error, -1);
+}
+/* *INDENT-OFF* */
+END_TEST
+/* *INDENT-ON* */
+
+/* *INDENT-OFF* */
+START_TEST (test_cache_key_invalid_request_line)
+/* *INDENT-ON* */
+
+{
+  static const char *request = "\
+GET /example HTTP/1.1\r\n\
+Hello\r\n\
+Host: example.com\r\n\
+If-None-Match: W/\"hello\", \"world\"\r\n\
+If-None-Match: W/\"hi :)\"\r\n\
+\r\n";
+  static const char *response = "\
+HTTP/1.1 200 Hi\r\n\
+Content-Type: text/plain\r\n\
+\r\n\
+Hi :)";
+  char memory[512];
+  int error =
+    compute_cache_key ("https", request, response, sizeof (memory), memory);
+  ck_assert_int_eq (error, -1);
+}
+/* *INDENT-OFF* */
+END_TEST
+/* *INDENT-ON* */
+
+/* *INDENT-OFF* */
+START_TEST (test_cache_key_invalid_response_line)
+/* *INDENT-ON* */
+
+{
+  static const char *request = "\
+GET /example HTTP/1.1\r\n\
+Host: example.com\r\n\
+If-None-Match: W/\"hello\", \"world\"\r\n\
+If-None-Match: W/\"hi :)\"\r\n\
+\r\n";
+  static const char *response = "\
+HTTP/1.1 200 Hi\r\n\
+Content-Type: text/plain\r\n\
+This line is not HTTP/1.1.\r\n\
+\r\n\
+Hi :)";
+  char memory[512];
+  int error =
+    compute_cache_key ("https", request, response, sizeof (memory), memory);
+  ck_assert_int_eq (error, -1);
+}
+/* *INDENT-OFF* */
+END_TEST
+/* *INDENT-ON* */
+
+/* *INDENT-OFF* */
+START_TEST (test_simple_cache_key)
+/* *INDENT-ON* */
+
+{
+  static const char *request = "\
+GET /example HTTP/1.1\r\n\
+Host: example.com\r\n\
+If-None-Match: W/\"hello\", \"world\"\r\n\
+If-None-Match: W/\"hi :)\"\r\n\
+\r\n";
+  static const char *response = "\
+HTTP/1.1 200 Hi\r\n\
+Content-Type: text/plain\r\n\
+\r\n\
+Hi :)";
+  char memory[512];
+  int error = compute_cache_key ("https", request, response, 0, memory);
+  ck_assert_int_eq (error, -2);
+  error =
+    compute_cache_key ("https", request, response, sizeof (memory), memory);
+  ck_assert_int_eq (error, 0);
+  ck_assert_str_eq (memory, "GET https://example.com/example\r\n");
+}
+/* *INDENT-OFF* */
+END_TEST
+/* *INDENT-ON* */
+
+/* *INDENT-OFF* */
+START_TEST (test_simply_varied_cache_key)
+/* *INDENT-ON* */
+
+{
+  static const char *request = "\
+GET /example HTTP/1.1\r\n\
+Host: example.com\r\n\
+Accept: text/plain\r\n\
+Foo: bar\r\n\
+Foo: other, thing\r\n\
+If-None-Match: W/\"hello\", \"world\"\r\n\
+If-None-Match: W/\"hi :)\"\r\n\
+\r\n";
+  static const char *response = "\
+HTTP/1.1 200 Hi\r\n\
+Content-Type: text/plain\r\n\
+ETag: W/\"hello\"\r\n\
+Vary: accept, foo\r\n\
+\r\n\
+Hi :)";
+  char memory[512];
+  int error = compute_cache_key ("https", request, response, 0, memory);
+  ck_assert_int_eq (error, -2);
+  error =
+    compute_cache_key ("https", request, response, sizeof (memory), memory);
+  ck_assert_int_eq (error, 0);
+  ck_assert_str_eq (memory, "\
+GET https://example.com/example\r\n\
+text/plain\r\n\
+bar,other, thing\r\n");
+  /* FIXME: "other, thing" is not touched so the space is
+     kept. Should disfluid try and parse comma-separated lists? Also
+     see test_multiply_varied_cache_key for another occurence of the
+     same problem. */
+}
+/* *INDENT-OFF* */
+END_TEST
+/* *INDENT-ON* */
+
+/* *INDENT-OFF* */
+START_TEST (test_multiply_varied_cache_key)
+/* *INDENT-ON* */
+
+{
+  static const char *request = "\
+GET /example HTTP/1.1\r\n\
+Host: example.com\r\n\
+Accept: text/plain\r\n\
+Foo: bar\r\n\
+Foo: other, thing\r\n\
+If-None-Match: W/\"hello\", \"world\"\r\n\
+If-None-Match: W/\"hi :)\"\r\n\
+\r\n";
+  static const char *response = "\
+HTTP/1.1 200 Hi\r\n\
+Content-Type: text/plain\r\n\
+ETag: W/\"hello\"\r\n\
+Vary: accept, foo\r\n\
+Vary: accept\r\n\
+\r\n\
+Hi :)";
+  char memory[512];
+  int error = compute_cache_key ("https", request, response, 0, memory);
+  ck_assert_int_eq (error, -2);
+  error =
+    compute_cache_key ("https", request, response, sizeof (memory), memory);
+  ck_assert_int_eq (error, 0);
+  ck_assert_str_eq (memory, "\
+GET https://example.com/example\r\n\
+text/plain\r\n\
+bar,other, thing\r\n\
+text/plain\r\n");
+  /* FIXME: see the test_simply_varied_cache_key test. */
+}
+/* *INDENT-OFF* */
+END_TEST
+/* *INDENT-ON* */
+
+/* *INDENT-OFF* */
+START_TEST (test_partial_cache_key)
+/* *INDENT-ON* */
+
+{
+  static const char *request = "\
+GET /example HTTP/1.1\r\n\
+Host: example.com\r\n\
+Accept: text/plain\r\n\
+\r\n";
+  static const char *response = "\
+HTTP/1.1 200 Hi\r\n\
+Content-Type: text/plain\r\n\
+Vary: a\r\n\
+\r\n\
+Hi :)";
+  char memory[512];
+  int error =
+    compute_cache_key ("https", request, response, sizeof (memory), memory);
+  ck_assert_int_eq (error, 0);
+  ck_assert_str_eq (memory, "\
+GET https://example.com/example\r\n\
+\r\n");				/* Notice how the "a" header is not present in the request, so
+				   the value is just empty. */
+}
+/* *INDENT-OFF* */
+END_TEST
+/* *INDENT-ON* */
 
 static inline char *
 tests_read_whole_file (int file)
@@ -468,6 +680,15 @@ run_tests (size_t *n_tests, size_t *n_errors)
   tcase_add_test (cache_entry, test_load_and_shrink);
   tcase_add_test (cache_entry, test_write_cache_entry);
   suite_add_tcase (suite, cache_entry);
+  TCase *cache_key = tcase_create (_("disfluid cache key"));
+  tcase_add_test (cache_key, test_cache_key_no_host);
+  tcase_add_test (cache_key, test_cache_key_invalid_request_line);
+  tcase_add_test (cache_key, test_cache_key_invalid_response_line);
+  tcase_add_test (cache_key, test_simple_cache_key);
+  tcase_add_test (cache_key, test_simply_varied_cache_key);
+  tcase_add_test (cache_key, test_multiply_varied_cache_key);
+  tcase_add_test (cache_key, test_partial_cache_key);
+  suite_add_tcase (suite, cache_key);
   SRunner *runner = srunner_create (suite);
   char log_file_name[] = "/tmp/disfluid-unit-tests-XXXXXX";
   int log_file = mkstemp (log_file_name);
diff --git a/src/libdisfluid/main.c b/src/libdisfluid/main.c
index a898079..76edb68 100644
--- a/src/libdisfluid/main.c
+++ b/src/libdisfluid/main.c
@@ -22,6 +22,7 @@
 
 #include "disfluid-authors.h"
 #include "disfluid-cache-entry.h"
+#include "disfluid-cache-entry-key.h"
 #include "disfluid-tests.h"
 #include "disfluid-version.h"
 
@@ -256,3 +257,13 @@ disfluid_cache_entry_fwrite (const struct disfluid_cache_entry *entry,
 {
   return cache_entry_fwrite (entry, f);
 }
+
+int
+disfluid_compute_cache_key (const char *request_scheme,
+			    const char *request_header,
+			    const char *response_header,
+			    size_t max_key, char *key)
+{
+  return compute_cache_key (request_scheme, request_header, response_header,
+			    max_key, key);
+}