refs.c: optimize check_refname_component()

In a repository with many refs, check_refname_component can be a major
contributor to the runtime of some git commands. One such command is

git rev-parse HEAD

Timings for one particular repo, with about 60k refs, almost all
packed, are:

Old: 35 ms
New: 29 ms

Many other commands which read refs are also sped up.

Signed-off-by: David Turner <dturner@twitter.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/refs.c b/refs.c
index 728a76164830368637e95390d95ce3f7c7df659e..637a93d695a51872ad2b04289898421ca906af54 100644 (file)
--- a/refs.c
+++ b/refs.c
@@ -6,8 +6,29 @@
 #include "string-list.h"
 
 /*
 #include "string-list.h"
 
 /*

- * Make sure "ref" is something reasonable to have under ".git/refs/";
- * We do not like it if:
+ * How to handle various characters in refnames:
+ * 0: An acceptable character for refs
+ * 1: End-of-component
+ * 2: ., look for a preceding . to reject .. in refs
+ * 3: {, look for a preceding @ to reject @{ in refs
+ * 4: A bad character: ASCII control characters, "~", "^", ":" or SP
+ */
+static unsigned char refname_disposition[256] = {
+       1, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
+       4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
+       4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 2, 1,
+       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 4,
+       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 4, 0, 4, 0,
+       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 4, 4
+};
+
+/*
+ * Try to read one refname component from the front of refname.
+ * Return the length of the component found, or -1 if the component is
+ * not legal.  It is legal if it is something reasonable to have under
+ * ".git/refs/"; We do not like it if:

  *
  * - any path component of it begins with ".", or
  * - it has double dots "..", or
  *
  * - any path component of it begins with ".", or
  * - it has double dots "..", or


@@ -16,41 +37,31 @@
  * - it ends with ".lock"
  * - it contains a "\" (backslash)
  */
  * - it ends with ".lock"
  * - it contains a "\" (backslash)
  */

-
-/* Return true iff ch is not allowed in reference names. */
-static inline int bad_ref_char(int ch)
-{
-       if (((unsigned) ch) <= ' ' || ch == 0x7f ||
-           ch == '~' || ch == '^' || ch == ':' || ch == '\\')
-               return 1;
-       /* 2.13 Pattern Matching Notation */
-       if (ch == '*' || ch == '?' || ch == '[') /* Unsupported */
-               return 1;
-       return 0;
-}
-
-/*
- * Try to read one refname component from the front of refname.  Return
- * the length of the component found, or -1 if the component is not
- * legal.
- */

 static int check_refname_component(const char *refname, int flags)
 {
        const char *cp;
        char last = '\0';
 
        for (cp = refname; ; cp++) {
 static int check_refname_component(const char *refname, int flags)
 {
        const char *cp;
        char last = '\0';
 
        for (cp = refname; ; cp++) {

-               char ch = *cp;
-               if (ch == '\0' || ch == '/')
+               int ch = *cp & 255;
+               unsigned char disp = refname_disposition[ch];
+               switch (disp) {
+               case 1:
+                       goto out;
+               case 2:
+                       if (last == '.')
+                               return -1; /* Refname contains "..". */
+                       break;
+               case 3:
+                       if (last == '@')
+                               return -1; /* Refname contains "@{". */

                        break;
                        break;

-               if (bad_ref_char(ch))
-                       return -1; /* Illegal character in refname. */
-               if (last == '.' && ch == '.')
-                       return -1; /* Refname contains "..". */
-               if (last == '@' && ch == '{')
-                       return -1; /* Refname contains "@{". */
+               case 4:
+                       return -1;
+               }

                last = ch;
        }
                last = ch;
        }

+out:

        if (cp == refname)
                return 0; /* Component has zero length. */
        if (refname[0] == '.') {
        if (cp == refname)
                return 0; /* Component has zero length. */
        if (refname[0] == '.') {

diff --git a/t/t5511-refspec.sh b/t/t5511-refspec.sh
index c28932216b1dd0893bc3c3a0a643963663ff8e1f..de6db86ccff044b5cc97a7b9236760076a8784d8 100755 (executable)
--- a/t/t5511-refspec.sh
+++ b/t/t5511-refspec.sh
@@ -5,7 +5,6 @@ test_description='refspec parsing'
 . ./test-lib.sh
 
 test_refspec () {
 . ./test-lib.sh
 
 test_refspec () {

-

        kind=$1 refspec=$2 expect=$3
        git config remote.frotz.url "." &&
        git config --remove-section remote.frotz &&
        kind=$1 refspec=$2 expect=$3
        git config remote.frotz.url "." &&
        git config --remove-section remote.frotz &&


@@ -84,4 +83,9 @@ test_refspec push 'refs/heads/*/*/for-linus:refs/remotes/mine/*' invalid
 test_refspec fetch 'refs/heads/*/for-linus:refs/remotes/mine/*'
 test_refspec push 'refs/heads/*/for-linus:refs/remotes/mine/*'
 
 test_refspec fetch 'refs/heads/*/for-linus:refs/remotes/mine/*'
 test_refspec push 'refs/heads/*/for-linus:refs/remotes/mine/*'
 

+good=$(printf '\303\204')
+test_refspec fetch "refs/heads/${good}"
+bad=$(printf '\011tab')
+test_refspec fetch "refs/heads/${bad}"                         invalid
+

 test_done
 test_done