[PATCH] Universally-unique gensyms

[Mark H Weaver <mhw@netris.org>]

[-- Attachment #1: Type: text/plain, Size: 80 bytes --]

This patch makes our gensyms universally-unique.  Comments welcome.

    Mark



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: [PATCH] Universally-unique gensyms --]
[-- Type: text/x-patch, Size: 3611 bytes --]

From 18616afc6a3d5aca48da2e0819d08d7ff98de214 Mon Sep 17 00:00:00 2001
From: Mark H Weaver <mhw@netris.org>
Date: Tue, 17 Jan 2012 08:15:10 -0500
Subject: [PATCH] Universally-unique gensyms

* libguile/symbols.c (scm_gensym): The gensym counter is now 128 bits,
  initialized to a random number at the beginning of each session.  This
  counter is rendered as a 22 byte suffix of mostly base64 digits.
---
 libguile/symbols.c |   69 +++++++++++++++++++++++++++++++++++++++++++++-------
 1 files changed, 60 insertions(+), 9 deletions(-)

diff --git a/libguile/symbols.c b/libguile/symbols.c
index 59aca00..cf82518 100644
--- a/libguile/symbols.c
+++ b/libguile/symbols.c
@@ -340,7 +340,9 @@ SCM_DEFINE (scm_string_ci_to_symbol, "string-ci->symbol", 1, 0, 0,
 /* The default prefix for `gensym'd symbols.  */
 static SCM default_gensym_prefix;
 
-#define MAX_PREFIX_LENGTH 30
+#define GENSYM_LENGTH      22  /* bytes */
+#define GENSYM_RADIX_BITS  6
+#define GENSYM_RADIX       (1 << (GENSYM_RADIX_BITS))
 
 SCM_DEFINE (scm_gensym, "gensym", 0, 1, 0,
             (SCM prefix),
@@ -351,22 +353,71 @@ SCM_DEFINE (scm_gensym, "gensym", 0, 1, 0,
 	    "resetting the counter.")
 #define FUNC_NAME s_scm_gensym
 {
-  static int gensym_counter = 0;
-  
+  static int initialized = 0;
+  static unsigned char digit_buf[GENSYM_LENGTH];
+  static char base64[GENSYM_RADIX] =
+    "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789$@";
+  static char base4[4] = "_.-~";
+
+  char char_buf[GENSYM_LENGTH];
   SCM suffix, name;
-  int n, n_digits;
-  char buf[SCM_INTBUFLEN];
+  int i;
+
+  if (SCM_UNLIKELY (!initialized))
+    {
+      int res = 0;
+      FILE *f = fopen ("/dev/urandom", "r");
+      if (f)
+        {
+          res = fread(digit_buf, 1, GENSYM_LENGTH, f);
+          fclose (f);
+        }
+      if (res == GENSYM_LENGTH)
+        {
+          for (i = (GENSYM_LENGTH - 1); i >= 0; --i)
+            digit_buf[i] &= (GENSYM_RADIX - 1);
+        }
+      else
+        {
+          /* This is a fallback in case /dev/urandom fails */
+          SCM tm = scm_gettimeofday ();
+          SCM seed = scm_sum (scm_product (scm_car (tm),
+                                           scm_from_int (1000000)),
+                              scm_cdr (tm));
+          SCM random_state = scm_seed_to_random_state (seed);
+          SCM radix = scm_from_int (GENSYM_RADIX);
+          for (i = (GENSYM_LENGTH - 1); i >= 0; --i)
+            digit_buf[i] = scm_to_int (scm_random (radix, random_state));
+        }
+      initialized = 1;
+    }
 
   if (SCM_UNBNDP (prefix))
     prefix = default_gensym_prefix;
 
-  /* mutex in case another thread looks and incs at the exact same moment */
+  /* ENHANCE-ME: make digit_buf thread-local to avoid the mutex */
+
+  /* lock the mutex */
   scm_i_scm_pthread_mutex_lock (&scm_i_misc_mutex);
-  n = gensym_counter++;
+
+  /* increment digit_buf */
+  for (i = (GENSYM_LENGTH - 1); i >= 0; --i)
+    {
+      if (SCM_LIKELY (++(digit_buf[i]) < GENSYM_RADIX))
+        break;
+      else
+        digit_buf[i] = 0;
+    }
+
+  /* convert digit_buf to the base64 char_buf */
+  for (i = (GENSYM_LENGTH - 1); i > 0; --i)
+    char_buf[i] = base64[digit_buf[i]];
+  char_buf[0] = base4[digit_buf[0] & 3];
+
+  /* unlock the mutex */
   scm_i_pthread_mutex_unlock (&scm_i_misc_mutex);
 
-  n_digits = scm_iint2str (n, 10, buf);
-  suffix = scm_from_latin1_stringn (buf, n_digits);
+  suffix = scm_from_latin1_stringn (char_buf, GENSYM_LENGTH);
   name = scm_string_append (scm_list_2 (prefix, suffix));
   return scm_string_to_symbol (name);
 }
-- 
1.7.5.4