[glib] gresourcefile: simplify path canonicalization

[Christian Hergert <chergert src gnome org>]

commit 38ffcd298c2613a8934b46ee363f61c1e0cb50c3
Author: Christian Hergert <chergert redhat com>
Date:   Mon Nov 13 21:42:20 2017 -0800

    gresourcefile: simplify path canonicalization
    
    Previously, the path canonicalization for resources had liberal use of
    strlen() and memmove() while walking through the path. This patch avoids
    any secondary strlen() and removes all use of memmove().
    
    A single allocation is created up front as we should only ever need one
    additional byte more than then length of the incoming path string.
    
    To keep the implementation readable, the mechanics are kept in external
    functions. memrchr() was not used due to its lack of portability.
    
    This is faster in every test case I've tested. Paths that contain
    relative ../ have the most speedup.
    
    https://bugzilla.gnome.org/show_bug.cgi?id=790310

 gio/gresourcefile.c   |  131 +++++++++++++++++++++++++++++--------------------
 gio/tests/resources.c |   44 ++++++++++++++++
 2 files changed, 121 insertions(+), 54 deletions(-)
---
diff --git a/gio/gresourcefile.c b/gio/gresourcefile.c
index 739c6e2..429e9ef 100644
--- a/gio/gresourcefile.c
+++ b/gio/gresourcefile.c
@@ -138,69 +138,92 @@ g_resource_file_init (GResourceFile *resource)
 {
 }
 
-static char *
-canonicalize_filename (const char *filename)
+static inline gchar *
+scan_backwards (const gchar *begin,
+                const gchar *end,
+                gchar        c)
 {
-  char *canon, *start, *p, *q;
+  while (end >= begin)
+    {
+      if (*end == c)
+        return (gchar *)end;
+      end--;
+    }
 
-  /* Skip multiple inital slashes */
-  while (filename[0] == '/' && filename[1] == '/')
-    filename++;
+  return NULL;
+}
 
-  if (*filename != '/')
-    canon = g_strconcat ("/", filename, NULL);
-  else
-    canon = g_strdup (filename);
+static inline void
+pop_to_previous_part (const gchar  *begin,
+                      gchar       **out)
+{
+  if (*out > begin)
+    *out = scan_backwards (begin, *out - 1, '/');
+}
+
+/*
+ * canonicalize_filename:
+ * @in: the path to be canonicalized
+ *
+ * The path @in may contain non-canonical path pieces such as "../"
+ * or duplicated "/". This will resolve those into a form that only
+ * contains a single / at a time and resolves all "../". The resulting
+ * path must also start with a /.
+ *
+ * Returns: the canonical form of the path
+ */
+static char *
+canonicalize_filename (const char *in)
+{
+  gchar *bptr;
+  char *out;
 
-  start = canon + 1;
+  bptr = out = g_malloc (strlen (in) + 2);
+  *out = '/';
 
-  p = start;
-  while (*p != 0)
+  while (*in != 0)
     {
-      if (p[0] == '.' && (p[1] == 0 || p[1] == '/'))
-       {
-         memmove (p, p+1, strlen (p+1)+1);
-       }
-      else if (p[0] == '.' && p[1] == '.' && (p[2] == 0 || p[2] == '/'))
-       {
-         q = p + 2;
-         /* Skip previous separator */
-         p = p - 2;
-         if (p < start)
-           p = start;
-         while (p > start && *p != '/')
-           p--;
-         if (*p == '/')
-           *p++ = '/';
-         memmove (p, q, strlen (q)+1);
-       }
-      else
-       {
-         /* Skip until next separator */
-         while (*p != 0 && *p != '/')
-           p++;
+      g_assert (*out == '/');
 
-         if (*p != 0)
-           {
-             /* Canonicalize one separator */
-             *p++ = '/';
-           }
-       }
+      /* move past slashes */
+      while (*in == '/')
+        in++;
+
+      /* Handle ./ ../ .\0 ..\0 */
+      if (*in == '.')
+        {
+          /* If this is ../ or ..\0 move up */
+          if (in[1] == '.' && (in[2] == '/' || in[2] == 0))
+            {
+              pop_to_previous_part (bptr, &out);
+              in += 2;
+              continue;
+            }
+
+          /* If this is ./ skip past it */
+          if (in[1] == '/' || in[1] == 0)
+            {
+              in += 1;
+              continue;
+            }
+        }
 
-      /* Remove additional separators */
-      q = p;
-      while (*q && *q == '/')
-       q++;
+      /* Scan to the next path piece */
+      while (*in != 0 && *in != '/')
+        *(++out) = *(in++);
 
-      if (p != q)
-       memmove (p, q, strlen (q)+1);
+      /* Add trailing /, compress the rest on the next go round. */
+      if (*in == '/')
+        *(++out) = *(in++);
     }
 
-  /* Remove trailing slashes */
-  if (p > start && *(p-1) == '/')
-    *(p-1) = 0;
+  /* Trim trailing / from path */
+  if (out > bptr && *out == '/')
+    *out = 0;
+  else
+    *(++out) = 0;
 
-  return canon;
+  return bptr;
 }
 
 static GFile *
diff --git a/gio/tests/resources.c b/gio/tests/resources.c
index 22ce7c6..81922d3 100644
--- a/gio/tests/resources.c
+++ b/gio/tests/resources.c
@@ -156,6 +156,49 @@ test_resource_file (void)
 }
 
 static void
+test_resource_file_path (void)
+{
+  static const struct {
+    const gchar *input;
+    const gchar *expected;
+  } test_uris[] = {
+    { "resource://", "resource:///" },
+    { "resource:///", "resource:///" },
+    { "resource://////", "resource:///" },
+    { "resource:///../../../", "resource:///" },
+    { "resource:///../../..", "resource:///" },
+    { "resource://abc", "resource:///abc" },
+    { "resource:///abc/", "resource:///abc" },
+    { "resource:/a/b/../c/", "resource:///a/c" },
+    { "resource://../a/b/../c/../", "resource:///a" },
+    { "resource://a/b/cc//bb//a///", "resource:///a/b/cc/bb/a" },
+    { "resource://././././", "resource:///" },
+    { "resource://././././../", "resource:///" },
+    { "resource://a/b/c/d.png", "resource:///a/b/c/d.png" },
+    { "resource://a/b/c/..png", "resource:///a/b/c/..png" },
+    { "resource://a/b/c/./png", "resource:///a/b/c/png" },
+  };
+  guint i;
+
+  for (i = 0; i < G_N_ELEMENTS (test_uris); i++)
+    {
+      GFile *file;
+      gchar *uri;
+
+      file = g_file_new_for_uri (test_uris[i].input);
+      g_assert (file != NULL);
+
+      uri = g_file_get_uri (file);
+      g_assert (uri != NULL);
+
+      g_assert_cmpstr (uri, ==, test_uris[i].expected);
+
+      g_object_unref (file);
+      g_free (uri);
+    }
+}
+
+static void
 test_resource_data (void)
 {
   GResource *resource;
@@ -673,6 +716,7 @@ main (int   argc,
   _g_test2_register_resource ();
 
   g_test_add_func ("/resource/file", test_resource_file);
+  g_test_add_func ("/resource/file-path", test_resource_file_path);
   g_test_add_func ("/resource/data", test_resource_data);
   g_test_add_func ("/resource/data_unaligned", test_resource_data_unaligned);
   g_test_add_func ("/resource/registered", test_resource_registered);