Add support for UUID generation

12 files changed, 1261 insertions, 19 deletions

diff --git a/libbutl/buildfile b/libbutl/buildfile
index d64f630..073ed14 100644
--- a/libbutl/buildfile
+++ b/libbutl/buildfile
@@ -13,8 +13,8 @@ if ($force_std_modules == true)
   cxx.poptions += -D__cpp_lib_modules
 }
 
-lib{butl}: {mxx hxx ixx txx cxx}{** -win32-utility -version} {hxx}{version} \
-  $int_libs
+lib{butl}: {mxx hxx ixx txx cxx}{** -uuid-* +uuid-io -win32-utility -version} \
+           {hxx}{version} $int_libs
 
 windows = ($cxx.target.class == 'windows')
 
@@ -22,12 +22,38 @@ windows = ($cxx.target.class == 'windows')
 #
 lib{butl}: {hxx cxx}{win32-utility}: include = $windows
 
-# The C-files are included into sha256.cxx (sha256c.c) and timestamp.cxx
-# (strptime.c timelocal.h timelocal.c), so treat them as files to exclude from
+# Our C-files are included into sha256.cxx (sha256c.c) and timestamp.cxx
+# (strptime.c timelocal.h timelocal.c), so treat them as files exclude from
 # the compilation.
 #
 lib{butl}: file{*.c *.h}
 
+# Platform-specific UUID implementations.
+#
+lib{butl}: cxx{uuid-linux}:   include = ($cxx.target.class  == 'linux')
+lib{butl}: cxx{uuid-macos}:   include = ($cxx.target.class  == 'macos')
+lib{butl}: cxx{uuid-windows}: include = $windows
+lib{butl}: cxx{uuid-freebsd}: include = ($cxx.target.system == 'freebsd')
+
+if ($cxx.target.class == 'linux')
+  cxx.libs += -ldl
+elif ($cxx.target.class == 'macos')
+  cxx.libs += -framework CoreFoundation
+elif ($windows)
+  cxx.libs += ($cxx.target.system == 'mingw32' ? -lrpcrt4 : rpcrt4.lib)
+
+# Additional system libraries.
+#
+if $windows
+  cxx.libs += ($cxx.target.system == 'mingw32' ? -limagehlp : imagehlp.lib)
+else
+  cxx.libs += -lpthread
+
+#@@ MOD VC bogus warning if module and dll-exported function called within DLL.
+#
+if ($cxx.features.modules && $cxx.class == 'msvc')
+  cxx.loptions += /ignore:4217
+
 # Include the generated version header into the distribution (so that we don't
 # pick up an installed one) and don't remove it when cleaning in src (so that
 # clean results in a state identical to distributed).
@@ -54,21 +80,6 @@ lib{butl}: cxx.export.poptions = "-I$out_root" "-I$src_root"
 liba{butl}: cxx.export.poptions += -DLIBBUTL_STATIC
 libs{butl}: cxx.export.poptions += -DLIBBUTL_SHARED
 
-if $windows
-{
-  if ($cxx.target.system == 'mingw32')
-    cxx.libs += -limagehlp
-  else
-    cxx.libs += imagehlp.lib
-}
-else
-  cxx.libs += -lpthread
-
-#@@ MOD VC bogus warning if module and dll-exported function called within DLL.
-#
-if ($cxx.features.modules && $cxx.class == 'msvc')
-  cxx.loptions += /ignore:4217
-
 # Install into the libbutl/ subdirectory of, say, /usr/include/ recreating
 # subdirectories.
 #
diff --git a/libbutl/uuid-freebsd.cxx b/libbutl/uuid-freebsd.cxx
new file mode 100644
index 0000000..184799d
--- /dev/null
+++ b/libbutl/uuid-freebsd.cxx
@@ -0,0 +1,90 @@
+// file      : libbutl/uuid-freebsd.cxx -*- C++ -*-
+// copyright : Copyright (c) 2014-2018 Code Synthesis Ltd
+// license   : MIT; see accompanying LICENSE file
+
+#ifndef BUILD2_BOOTSTRAP
+
+#include <libbutl/uuid.hxx>
+
+#include <sys/uuid.h>
+
+#include <errno.h>
+
+#include <cassert>
+#include <cstring>      // memcpy()
+#include <system_error>
+
+using namespace std;
+
+namespace butl
+{
+  void
+  uuid_throw_weak (); // uuid.cxx
+
+  uuid uuid_system_generator::
+  generate (bool strong)
+  {
+    // While FreeBSD shares the uuid_*() (<uuid.h>, uuid(3)) API with other
+    // BSDs, its documentation is quite light on the kind of UUID we get and
+    // with what guarantees. The implementation of uuid_create() simply calls
+    // the uuidgen() system call (<sys/uuid.h>, uuidgen(2)) which has some
+    // details.
+    //
+    // Specifically (and as of FreeBSD 11.2), we get a version 1 (MAC/time-
+    // based) UUID and it seems there is provision for getting the time in a
+    // collision-safe:
+    //
+    // "According to the algorithm of generating time-based UUIDs, this will
+    //  also force a new random clock sequence, thereby increasing the
+    //  likelihood for the identifier to be unique."
+    //
+    // So we will assume a MAC/time-based UUID is strong. We also assume a
+    // random UUID is strong as well in case in the future this will becomes
+    // the default (as seems to be the trend); presumably, FreeBSD folks are
+    // smart enough not to start return random UUIDs without a good source of
+    // randomness, at least not by default.
+    //
+    struct ::uuid d;
+
+    if (uuidgen (&d, 1) != 0)
+      throw system_error (errno, system_category ());
+
+    uuid r;
+
+    // This is effectively just memcpy() but let's reference the member names
+    // in case anything changes on either side.
+    //
+    r.time_low = d.time_low;
+    r.time_mid = d.time_mid;
+    r.time_hiv = d.time_hi_and_version;
+    r.clock_seq_hir = d.clock_seq_hi_and_reserved;
+    r.clock_seq_low = d.clock_seq_low;
+    memcpy (r.node, d.node, 6);
+
+    assert (r.variant () == uuid_variant::dce); // Sanity check.
+
+    if (strong)
+    {
+      switch (r.version ())
+      {
+      case uuid_version::time:
+      case uuid_version::random: break;
+      default:                   uuid_throw_weak ();
+      }
+    }
+
+    return r;
+  }
+
+  void uuid_system_generator::
+  initialize ()
+  {
+  }
+
+  void uuid_system_generator::
+  terminate ()
+  {
+  }
+}
+
+#endif // BUILD2_BOOTSTRAP
diff --git a/libbutl/uuid-io.cxx b/libbutl/uuid-io.cxx
new file mode 100644
index 0000000..7eed134
--- /dev/null
+++ b/libbutl/uuid-io.cxx
@@ -0,0 +1,43 @@
+// file      : libbutl/uuid-io.cxx -*- C++ -*-
+// copyright : Copyright (c) 2014-2018 Code Synthesis Ltd
+// license   : MIT; see accompanying LICENSE file
+
+#include <libbutl/uuid-io.hxx>
+
+#include <ostream>
+#include <istream>
+#include <stdexcept> // invalid_argument
+
+using namespace std;
+
+namespace butl
+{
+  ostream&
+  operator<< (ostream& os, const uuid& u)
+  {
+    return os << u.c_string ().data ();
+  }
+
+  istream&
+  operator>> (istream& is, uuid& u)
+  {
+    u = uuid ();
+
+    char s[37];
+    if (is.read (s, 36))
+    {
+      s[36] ='\0';
+
+      try
+      {
+        u = uuid (s);
+      }
+      catch (const invalid_argument&)
+      {
+        is.setstate (istream::failbit);
+      }
+    }
+
+    return is;
+  }
+}
diff --git a/libbutl/uuid-io.hxx b/libbutl/uuid-io.hxx
new file mode 100644
index 0000000..57de9f3
--- /dev/null
+++ b/libbutl/uuid-io.hxx
@@ -0,0 +1,23 @@
+// file      : libbutl/uuid-io.hxx -*- C++ -*-
+// copyright : Copyright (c) 2014-2018 Code Synthesis Ltd
+// license   : MIT; see accompanying LICENSE file
+
+#pragma once
+
+#include <iosfwd>
+
+#include <libbutl/uuid.hxx>
+#include <libbutl/export.hxx>
+
+namespace butl
+{
+  // Insert lower case string representation.
+  //
+  LIBBUTL_SYMEXPORT std::ostream&
+  operator<< (std::ostream&, const uuid&);
+
+  // Extract string representation (lower or upper case).
+  //
+  LIBBUTL_SYMEXPORT std::istream&
+  operator>> (std::istream&, uuid&);
+}
diff --git a/libbutl/uuid-linux.cxx b/libbutl/uuid-linux.cxx
new file mode 100644
index 0000000..7396910
--- /dev/null
+++ b/libbutl/uuid-linux.cxx
@@ -0,0 +1,145 @@
+// file      : libbutl/uuid-linux.cxx -*- C++ -*-
+// copyright : Copyright (c) 2014-2018 Code Synthesis Ltd
+// license   : MIT; see accompanying LICENSE file
+
+#ifndef BUILD2_BOOTSTRAP
+
+#include <libbutl/uuid.hxx>
+
+#include <errno.h>
+#include <dlfcn.h>
+
+#include <mutex>
+#include <cassert>
+#include <utility>      // move()
+#include <system_error>
+
+using namespace std;
+
+namespace butl
+{
+  // While we can safely assume libuuid.so.1 is present on every Linux machine
+  // (it is part of the essential util-linux package since version 2.15.1),
+  // the development files (uuid.h, .so/.a symlinks) are a different story.
+  // So for maximum portability we will use dlopen()/dlsym() to "link" to this
+  // library without any development files.
+  //
+  // It appears that not all execution paths in uuid_generate() are thread-
+  // safe (see Ubuntu bug #1005878). So for now the calls are serialized but
+  // maybe this could be optimized (e.g., if we can be sure a thread-safe path
+  // will be taken). Note also that we may still end up in trouble if someone
+  // else in the process calls libuuid directly.
+  //
+  // Note also that the Linux kernel has support for generatin random UUIDs
+  // which is exposed to userspace via /proc/sys/kernel/random/uuid. This
+  // could be another implementation option (though it's not clear since which
+  // version it is available, seem at least from the 2.6 days).
+  //
+  using lock = unique_lock<mutex>;
+
+  static mutex uuid_mutex;
+
+  // <uuid.h>
+  //
+  using uuid_t = unsigned char[16];
+
+  static void (*uuid_generate)           (uuid_t);
+  static int  (*uuid_generate_time_safe) (uuid_t);
+
+  static void* libuuid;
+
+  // Use a union to cleanly cast dlsym() result (void*) to a function pointer.
+  //
+  template <typename F>
+  static inline F
+  function_cast (void* p)
+  {
+    union { void* p; F f; } r;
+    r.p = p;
+    return r.f;
+  };
+
+  static inline void
+  dlfail (string what)
+  {
+    what += ": ";
+    what += dlerror ();
+    throw system_error (ENOSYS, system_category (), move (what));
+  };
+
+  void uuid_system_generator::
+  initialize ()
+  {
+    assert (libuuid == nullptr);
+
+    libuuid = dlopen ("libuuid.so.1", RTLD_LAZY | RTLD_GLOBAL);
+
+    if (libuuid == nullptr)
+      dlfail ("unable to load libuuid.so.1");
+
+    uuid_generate =
+      function_cast<decltype(uuid_generate)> (
+        dlsym (libuuid, "uuid_generate"));
+
+    if (uuid_generate == nullptr)
+      dlfail ("unable to lookup uuid_generate() in libuuid.so.1");
+
+    uuid_generate_time_safe =
+      function_cast<decltype(uuid_generate_time_safe)> (
+        dlsym (libuuid, "uuid_generate_time_safe"));
+
+    // Delay the failure until/if we need this function (it was only added in
+    // 2011 so may not be available on older systems).
+    //
+    //if (uuid_generate_time_safe == nullptr)
+    //  dlfail ("unable to lookup uuid_generate_time_safe() in libuuid.so.1");
+  }
+
+  void uuid_system_generator::
+  terminate ()
+  {
+    assert (libuuid != nullptr);
+
+    if (dlclose (libuuid) != 0)
+      dlfail ("unable to unload libuuid.so.1");
+
+    libuuid = nullptr;
+  }
+
+  void
+  uuid_throw_weak (); // uuid.cxx
+
+  uuid uuid_system_generator::
+  generate (bool strong)
+  {
+    lock l (uuid_mutex);
+
+    if (libuuid == nullptr)
+      initialize ();
+
+    uuid_t d;
+    uuid_generate (d);
+
+    uuid r (d);
+    assert (r.variant () == uuid_variant::dce); // Sanity check.
+
+    // According to the uuid_generate() documentation (and confirmed by the
+    // implementation) it generates a random uuid if high-quality randomness
+    // is available and a MAC/time-based one otherwise (in other words, it
+    // should never generate a pseudo-random UUID).
+    //
+    if (strong && r.version () != uuid_version::random)
+    {
+      if (uuid_generate_time_safe == nullptr ||
+          uuid_generate_time_safe (d) == -1)
+        uuid_throw_weak ();
+
+      r.assign (d);
+      assert (r.variant () == uuid_variant::dce);
+    }
+
+    return r;
+  }
+}
+
+#endif // BUILD2_BOOTSTRAP
diff --git a/libbutl/uuid-macos.cxx b/libbutl/uuid-macos.cxx
new file mode 100644
index 0000000..1003501
--- /dev/null
+++ b/libbutl/uuid-macos.cxx
@@ -0,0 +1,81 @@
+// file      : libbutl/uuid-macos.cxx -*- C++ -*-
+// copyright : Copyright (c) 2014-2018 Code Synthesis Ltd
+// license   : MIT; see accompanying LICENSE file
+
+#ifndef BUILD2_BOOTSTRAP
+
+#include <libbutl/uuid.hxx>
+
+#include <CoreFoundation/CFUUID.h>
+
+#include <cassert>
+#include <cstring>   // memcpy()
+
+using namespace std;
+
+namespace butl
+{
+  void
+  uuid_throw_weak (); // uuid.cxx
+
+  uuid uuid_system_generator::
+  generate (bool strong)
+  {
+    // The common way to generate a UUID on Mac OS is with the CFUUIDCreate()
+    // function from the CoreFoundation framework. Interestingly, if we look
+    // at the implementation (yes, the CF source code is available), we will
+    // see that it uses the <uuid/uuid.h> API which looks like a customized
+    // implementation from e2fsprogs that itself is a precursor to libuuid
+    // from util-linux.
+    //
+    // More specifically (and at least as of CF version 1153.18), it calls
+    // uuid_generate_random() unless the CFUUIDVersionNumber environment
+    // variable is set to 1, in which case it calls uuid_generate_time(). It
+    // also appears to serialize these calls so the implementation should be
+    // thread-safe (see the Linux implementation for background; this is also
+    // the reason why we don't want to use the low-level API directly even if
+    // we provide our own synchronization: if other code in the process calls
+    // CFUUIDCreate() then we will end up with a race).
+    //
+    // In theory the use of uuid_generate_random() is bad news since it will
+    // produce weak pseudo-random UUIDs if no high-quality randomness is
+    // available (unlike uuid_generate() which will only produce strong random
+    // UUIDs falling back to the MAC/time-based ones; see uuid_generate(3) for
+    // details).
+    //
+    // In practice (and at least as of Mac OS libc version 1244.30), however,
+    // uuid_generate_random() uses arc4random(3) which reportedly produces
+    // high-quality randomness (and uuid_generate() simply always calls it).
+    //
+    CFUUIDRef h (CFUUIDCreate (NULL));
+    CFUUIDBytes d (CFUUIDGetUUIDBytes (h));
+    CFRelease (h);
+
+    uint8_t a[16];
+    memcpy (a, &d, 16); // CFUUIDBytes is POD.
+
+    uuid r (a);
+    assert (r.variant () == uuid_variant::dce); // Sanity check.
+
+    // If this is a MAC/time-based UUID, then it's possible the time was not
+    // obtained in a collision-safe manner (looking at the implementation this
+    // seems to be the case; see the Linux implementation for background).
+    //
+    if (strong && r.version () != uuid_version::random)
+      uuid_throw_weak ();
+
+    return r;
+  }
+
+  void uuid_system_generator::
+  initialize ()
+  {
+  }
+
+  void uuid_system_generator::
+  terminate ()
+  {
+  }
+}
+
+#endif // BUILD2_BOOTSTRAP
diff --git a/libbutl/uuid-windows.cxx b/libbutl/uuid-windows.cxx
new file mode 100644
index 0000000..825505b
--- /dev/null
+++ b/libbutl/uuid-windows.cxx
@@ -0,0 +1,131 @@
+// file      : libbutl/uuid-windows.cxx -*- C++ -*-
+// copyright : Copyright (c) 2014-2018 Code Synthesis Ltd
+// license   : MIT; see accompanying LICENSE file
+
+#ifndef BUILD2_BOOTSTRAP
+
+#include <libbutl/uuid.hxx>
+
+#include <rpc.h>   // UuidCreate*()
+#include <errno.h>
+
+#include <cassert>
+#include <system_error>
+
+using namespace std;
+
+namespace butl
+{
+  void uuid::
+  assign (const _GUID& g)
+  {
+    time_low  = g.Data1;
+    time_mid  = g.Data2;
+    time_hiv  = g.Data3;
+    clock_seq_hir = g.Data4[0];
+    clock_seq_low = g.Data4[1];
+    memcpy (node, &g.Data4[2], 6);
+  }
+
+  template<>
+  LIBBUTL_SYMEXPORT _GUID uuid::
+  guid<_GUID> () const
+  {
+    _GUID r;
+    r.Data1 = time_low;
+    r.Data2 = time_mid;
+    r.Data3 = time_hiv;
+    r.Data4[0] = clock_seq_hir;
+    r.Data4[1] = clock_seq_low;
+    memcpy (&r.Data4[2], node, 6);
+    return r;
+  }
+
+  void
+  uuid_throw_weak (); // uuid.cxx
+
+  uuid uuid_system_generator::
+  generate (bool strong)
+  {
+    // The common way to generate a UUID on Windows is with the CoCreateGuid()
+    // function which, according to the documentation, calls UuidCreate().
+    // There is some talk of it somehow generating stronger UUIDs but it is
+    // probably bogus (it most likely simply returns an error if UuidCreate()
+    // returns a "weak" UUID).
+    //
+    // UuidCreate(), on the other hand, has various interesting return codes
+    // as well as the UuidCreateSequential() variant which always generates a
+    // MAC/time-based UUID (according to the documentation, since Windows 2000
+    // UuidCreate() always generates a random UUID). So let's use that.
+    //
+    // While the documentation doesn't explicitly state this, presumably
+    // UuidCreate() uses a "decent" source of randomness. See this post for
+    // some background:
+    //
+    // https://stackoverflow.com/questions/35366368/does-uuidcreate-use-a-csprng
+    //
+    // So we assume a random UUID returned by UuidCreate() is strong. What to
+    // do if it's not is a tricky question (is it even possible?): we can call
+    // UuidCreateSequential() to generate a MAC/time-based UUID but it's
+    // possible the time was not obtained in a collision-safe manner (see the
+    // Linux implementation for background). However, the documentation
+    // suggests that it is safe ("... guaranteed to be unique among all UUIDs
+    // generated on the computer"). And so we assume it is.
+    //
+    auto rpcfail = [strong] (RPC_STATUS s)
+    {
+      if (s != RPC_S_UUID_LOCAL_ONLY)
+      {
+        char m [DCE_C_ERROR_STRING_LEN];
+
+        throw system_error (
+          ENOSYS,
+          system_category (),
+          (DceErrorInqTextA (s, reinterpret_cast<RPC_CSTR> (m)) == RPC_S_OK
+           ? m
+           : "unknown RPC error"));
+      }
+      else if (strong)
+        uuid_throw_weak ();
+    };
+
+    UUID d;
+    RPC_STATUS s (UuidCreate (&d));
+
+    if (s != RPC_S_OK)
+      rpcfail (s);
+
+    uuid r (d);
+    assert (r.variant () == uuid_variant::dce); // Sanity check.
+
+    if (strong && r.version () != uuid_version::random)
+    {
+      s = UuidCreateSequential (&d);
+
+      if (s != RPC_S_OK)
+        rpcfail (s);
+
+      r.assign (d);
+
+      // UuidCreateSequential() on Wine returns the Microsoft variant.
+      //
+      if (r.variant () != uuid_variant::dce ||
+          r.version () != uuid_version::time)
+        rpcfail (RPC_S_UUID_LOCAL_ONLY);
+    }
+
+    return r;
+  }
+
+  void uuid_system_generator::
+  initialize ()
+  {
+  }
+
+  void uuid_system_generator::
+  terminate ()
+  {
+  }
+}
+
+#endif // BUILD2_BOOTSTRAP
diff --git a/libbutl/uuid.cxx b/libbutl/uuid.cxx
new file mode 100644
index 0000000..ab42ad8
--- /dev/null
+++ b/libbutl/uuid.cxx
@@ -0,0 +1,88 @@
+// file      : libbutl/uuid.cxx -*- C++ -*-
+// copyright : Copyright (c) 2014-2018 Code Synthesis Ltd
+// license   : MIT; see accompanying LICENSE file
+
+#include <libbutl/uuid.hxx>
+
+#include <errno.h> // ENOTSUP
+
+#include <cstdio>       // sprintf() scanf()
+#include <cstring>      // strlen()
+#include <stdexcept>
+#include <system_error>
+
+using namespace std;
+
+namespace butl
+{
+  array<char, 37> uuid::
+  c_string (bool upper) const
+  {
+    array<char, 37> r;
+
+    sprintf (r.data (),
+             (upper
+              ? "%08X-%04X-%04X-%02X%02X-%02X%02X%02X%02X%02X%02X"
+              : "%08x-%04x-%04x-%02x%02x-%02x%02x%02x%02x%02x%02x"),
+             time_low,
+             time_mid,
+             time_hiv,
+             clock_seq_hir,
+             clock_seq_low,
+             node[0], node[1], node[2], node[3], node[4], node[5]);
+
+    return r;
+  }
+
+  void uuid::
+  assign (const char* s)
+  {
+    if (s != nullptr && strlen (s) == 36 && s[8] == '-')
+    {
+      if (sscanf (s,
+                  "%8x-%4hx-%4hx-%2hhx%2hhx-%2hhx%2hhx%2hhx%2hhx%2hhx%2hhx",
+                  &time_low,
+                  &time_mid,
+                  &time_hiv,
+                  &clock_seq_hir,
+                  &clock_seq_low,
+                  &node[0], &node[1], &node[2],
+                  &node[3], &node[4], &node[5]) == 11)
+        return;
+    }
+
+    throw invalid_argument ("invalid UUID string representation");
+  }
+
+  uuid_system_generator uuid::system_generator;
+
+  // Utility function used by platform-specified uuid-*.cxx implementations.
+  //
+  void
+  uuid_throw_weak ()
+  {
+    throw system_error (ENOTSUP,
+                        generic_category (),
+                        "strong UUID uniqueness cannot be guaranteed");
+  }
+
+#ifdef BUILD2_BOOTSTRAP
+  uuid uuid_system_generator::
+  generate (bool)
+  {
+    throw system_error (ENOTSUP,
+                        generic_category (),
+                        "no UUID generation support during bootstrap");
+  }
+
+  void uuid_system_generator::
+  initialize ()
+  {
+  }
+
+  void uuid_system_generator::
+  terminate ()
+  {
+  }
+#endif // BUILD2_BOOTSTRAP
+}
diff --git a/libbutl/uuid.hxx b/libbutl/uuid.hxx
new file mode 100644
index 0000000..92397f6
--- /dev/null
+++ b/libbutl/uuid.hxx
@@ -0,0 +1,234 @@
+// file      : libbutl/uuid.hxx -*- C++ -*-
+// copyright : Copyright (c) 2014-2018 Code Synthesis Ltd
+// license   : MIT; see accompanying LICENSE file
+
+#pragma once
+
+#include <array>
+#include <string>
+#include <cstdint>
+#include <functional> // hash
+
+#include <libbutl/export.hxx>
+#include <libbutl/version.hxx>
+
+#ifdef _WIN32
+struct _GUID; // GUID and UUID.
+#endif
+
+namespace butl
+{
+  // Universally-unique identifier (UUID), RFC4122:
+  //
+  // https://tools.ietf.org/html/rfc4122
+
+  // The UUID variant (type). Nil UUID is DCE.
+  //
+  enum class uuid_variant
+  {
+    ncs,       // NCS backward compatibility.
+    dce,       // DCE 1.1/RFC4122.
+    microsoft, // Microsoft backward compatibility.
+    other      // Currently reserved for possible future definition.
+  };
+
+  // The DCE UUID version (sub-type). Nil UUID is random.
+  //
+  enum class uuid_version
+  {
+    time     = 1, // Time-based.
+    security = 2, // DCE Security with embedded POSIX UIDs.
+    md5      = 3, // Name-based with MD5 hashing.
+    random   = 4, // Randomly or pseudo-randomly generated.
+    sha1     = 5  // Name-based with SHA1 hashing.
+  };
+
+  class LIBBUTL_SYMEXPORT uuid_system_generator;
+
+  struct LIBBUTL_SYMEXPORT uuid
+  {
+    // Normally not accessed directly (see RFC4122 Section 4.1.2).
+    //
+    std::uint32_t  time_low;
+    std::uint16_t  time_mid;
+    std::uint16_t  time_hiv;      // hi_and_version
+    std::uint8_t   clock_seq_hir; // hi_and_reserved
+    std::uint8_t   clock_seq_low;
+    std::uint8_t   node[6];
+
+    // System UUID generator. See the uuid_generator interface for details.
+    //
+    // Note: system generator cannot be called during static initialization.
+    //
+    static uuid_system_generator system_generator;
+
+    static uuid
+    generate (bool strong = true);
+
+    // Create a nil UUID (all members are 0).
+    //
+    uuid ();
+
+    bool
+    nil () const;
+
+    explicit operator bool () const;
+
+    // Create a UUID from a 16-octet binary representation with the sizes and
+    // order of the fields as defined in RFC4122 Section 4.1.2 and with each
+    // field encoded with the most significant byte first (also known as
+    // big-endian or network byte order).
+    //
+    using binary_type = std::array<std::uint8_t, 16>;
+
+    explicit
+    uuid (const binary_type&);
+
+    void
+    assign (const binary_type&);
+
+    binary_type
+    binary () const noexcept;
+
+    // Note that this constructor is compatible with libuuid's uuid_t type.
+    //
+    explicit
+    uuid (const std::uint8_t (&)[16]);
+
+    void
+    assign (const std::uint8_t (&)[16]);
+
+#ifdef _WIN32
+    // Create a UUID from Win32 GUID.
+    //
+    uuid (const _GUID&);
+
+    void
+    assign (const _GUID&);
+
+    template <typename G = _GUID>
+    G
+    guid () const;
+#endif
+
+    // Create a UUID from a 36-character string representation in the
+    //
+    //   xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx
+    //
+    // form which can be in lower or upper case. Throw std::invalid_argument
+    // if the representation is invalid.
+    //
+    // The returned string representation is by default in lower case.
+    //
+    explicit
+    uuid (const std::string&);
+
+    explicit
+    uuid (const char*);
+
+    void
+    assign (const std::string&);
+
+    void
+    assign (const char*);
+
+    std::string
+    string (bool upper = false) const;
+
+    std::array<char, 37>
+    c_string (bool upper = false) const;
+
+    // UUID variant (type) and version (sub-type).
+    //
+    using variant_type = uuid_variant;
+    using version_type = uuid_version;
+
+    variant_type
+    variant () const;
+
+    version_type
+    version () const;
+
+    // UUID comparison.
+    //
+    int
+    compare (const uuid&) const;
+
+    // Swapping and moving. On move we make the moved-from instance nil.
+    //
+    void
+    swap (uuid&);
+
+    uuid (uuid&&);
+    uuid (const uuid&) = default;
+
+    uuid& operator= (uuid&&);
+    uuid& operator= (const uuid&) = default;
+  };
+
+  bool operator== (const uuid&, const uuid&);
+  bool operator!= (const uuid&, const uuid&);
+  bool operator<  (const uuid&, const uuid&);
+  bool operator>  (const uuid&, const uuid&);
+  bool operator<= (const uuid&, const uuid&);
+  bool operator>= (const uuid&, const uuid&);
+
+  // For iostream operators see uuid-io.hxx.
+
+  // UUID generator interface.
+  //
+  class LIBBUTL_SYMEXPORT uuid_generator
+  {
+  public:
+    virtual
+    ~uuid_generator () = default;
+
+    // Generate a UUID. If strong is true (default), generate a strongly-
+    // unique UUID. Throw std::runtime_error to report errors, including if
+    // strong uniqueness cannot be guaranteed.
+    //
+    // A weak UUID is not guaranteed to be unique, neither universialy nor
+    // locally (that is, on the machine it has been generated).
+    //
+    virtual uuid
+    generate (bool strong = true) = 0;
+  };
+
+  // System UUID generator.
+  //
+  class LIBBUTL_SYMEXPORT uuid_system_generator: public uuid_generator
+  {
+  public:
+    // Throw std::system_error with the generic category and ENOTSUP error
+    // code if strong uniqueness cannot be guaranteed.
+    //
+    virtual uuid
+    generate (bool strong = true) override;
+
+    // Optional explicit initialization and termination. Note that it is not
+    // thread-safe and must only be performed once (normally from main())
+    // before/after any calls to generate(), respectively. Both functions may
+    // throw std::runtime_error to report errors.
+    //
+    static void
+    initialize ();
+
+    static void
+    terminate ();
+  };
+}
+
+namespace std
+{
+  template <>
+  struct hash<butl::uuid>
+  {
+    using argument_type = butl::uuid;
+    using result_type = size_t;
+
+    size_t
+    operator() (const butl::uuid&) const noexcept;
+  };
+}
+
+#include <libbutl/uuid.ixx>
diff --git a/libbutl/uuid.ixx b/libbutl/uuid.ixx
new file mode 100644
index 0000000..0208221
--- /dev/null
+++ b/libbutl/uuid.ixx
@@ -0,0 +1,291 @@
+// file      : libbutl/uuid.ixx -*- C++ -*-
+// copyright : Copyright (c) 2014-2018 Code Synthesis Ltd
+// license   : MIT; see accompanying LICENSE file
+
+#include <cstring> // mem*()
+#include <utility> // swap()
+
+namespace butl
+{
+  // NOTE: the order of definitions is important to MinGW GCC (DLL linkage).
+
+  inline uuid::
+  uuid ()
+      : time_low  (0), time_mid  (0), time_hiv  (0),
+        clock_seq_hir (0), clock_seq_low (0),
+        node {0, 0, 0, 0, 0, 0}
+  {
+  }
+
+  inline bool uuid::
+  nil () const
+  {
+    return
+      time_low  == 0 &&
+      time_mid  == 0 &&
+      time_hiv  == 0 &&
+      clock_seq_hir == 0 &&
+      clock_seq_low == 0 &&
+      node[0] == 0 && node[1] == 0 && node[2] == 0 &&
+      node[3] == 0 && node[4] == 0 && node[5] == 0;
+  }
+
+  inline uuid::
+  operator bool () const
+  {
+    return !nil ();
+  }
+
+  inline void uuid::
+  swap (uuid& u)
+  {
+    std::swap (time_low, u.time_low);
+    std::swap (time_mid, u.time_mid);
+    std::swap (time_hiv, u.time_hiv);
+    std::swap (clock_seq_hir, u.clock_seq_hir);
+    std::swap (clock_seq_low, u.clock_seq_low);
+    std::swap (node, u.node);
+  }
+
+  inline uuid::
+  uuid (uuid&& u)
+      : uuid () // nil
+  {
+    swap (u);
+  }
+
+  inline uuid& uuid::
+  operator= (uuid&& u)
+  {
+    if (this != &u)
+    {
+      uuid n; // nil
+      swap (n);
+      swap (u);
+    }
+    return *this;
+  }
+
+  inline void
+  uuid_assign_impl (uuid& r, const std::uint8_t* p)
+  {
+    {
+      std::uint32_t t;
+
+      t = *p++;
+      t = (t << 8) | *p++;
+      t = (t << 8) | *p++;
+      t = (t << 8) | *p++;
+      r.time_low = t;
+    }
+
+    std::uint16_t t;
+
+    t = *p++;
+    t = (t << 8) | *p++;
+    r.time_mid = t;
+
+    t = *p++;
+    t = (t << 8) | *p++;
+    r.time_hiv = t;
+
+    r.clock_seq_hir = *p++;
+    r.clock_seq_low = *p++;
+
+    std::memcpy (r.node, p, 6);
+  }
+
+  inline void uuid::
+  assign (const binary_type& d)
+  {
+    uuid_assign_impl (*this, d.data ());
+  }
+
+  inline uuid::
+  uuid (const binary_type& d)
+  {
+    assign (d);
+  }
+
+  inline uuid::binary_type uuid::
+  binary () const noexcept
+  {
+    using u8 = std::uint8_t;
+
+    binary_type r;
+    std::uint32_t t;
+
+    t = time_low;
+    r[3] = static_cast<u8> (t); t >>= 8;
+    r[2] = static_cast<u8> (t); t >>= 8;
+    r[1] = static_cast<u8> (t); t >>= 8;
+    r[0] = static_cast<u8> (t);
+
+    t = time_mid;
+    r[5] = static_cast<u8> (t); t >>= 8;
+    r[4] = static_cast<u8> (t);
+
+    t = time_hiv;
+    r[7] = static_cast<u8> (t); t >>= 8;
+    r[6] = static_cast<u8> (t);
+
+    r[9] = clock_seq_low;
+    r[8] = clock_seq_hir;
+
+    std::memcpy(r.data () + 10, node, 6);
+
+    return r;
+  }
+
+  inline void uuid::
+  assign (const std::uint8_t (&d)[16])
+  {
+    uuid_assign_impl (*this, d);
+  }
+
+  inline uuid::
+  uuid (const std::uint8_t (&d)[16])
+  {
+    assign (d);
+  }
+
+#ifdef _WIN32
+  inline uuid::
+  uuid (const _GUID& g)
+  {
+    assign (g);
+  }
+#endif
+
+  inline void uuid::
+  assign (const std::string& s)
+  {
+    assign (s.c_str ());
+  }
+
+  inline uuid::
+  uuid (const std::string& s)
+  {
+    assign (s);
+  }
+
+  inline uuid::
+  uuid (const char* s)
+  {
+    assign (s);
+  }
+
+  inline std::string uuid::
+  string (bool upper) const
+  {
+    return c_string (upper).data ();
+  }
+
+  inline uuid::variant_type uuid::
+  variant () const
+  {
+    return nil ()
+      ? variant_type::dce
+      : ((clock_seq_hir & 0x80) == 0 ? variant_type::ncs :
+         (clock_seq_hir & 0x40) == 0 ? variant_type::dce :
+         (clock_seq_hir & 0x20) == 0 ? variant_type::microsoft :
+         /*                         */ variant_type::other);
+  }
+
+  inline uuid::version_type uuid::
+  version () const
+  {
+    return nil ()
+      ? version_type::random
+      : static_cast<version_type> ((time_hiv >> 12) & 0x0f);
+  }
+
+  inline int uuid::
+  compare (const uuid& y) const
+  {
+    int r;
+    auto neq = [&r] (auto a, auto b) -> bool
+    {
+      return (r = (a == b ? 0 : (a < b  ? -1 : 1))) != 0;
+    };
+
+    return (neq (time_low, y.time_low) ? r :
+            neq (time_mid, y.time_mid) ? r :
+            neq (time_hiv, y.time_hiv) ? r :
+            neq (clock_seq_hir, y.clock_seq_hir) ? r :
+            neq (clock_seq_low, y.clock_seq_low) ? r :
+            std::memcmp (node, y.node, 6));
+  }
+
+  inline bool
+  operator== (const uuid& x, const uuid& y)
+  {
+    return x.compare (y) == 0;
+  }
+
+  inline bool
+  operator!= (const uuid& x, const uuid& y)
+  {
+    return x.compare (y) != 0;
+  }
+
+  inline bool
+  operator< (const uuid& x, const uuid& y)
+  {
+    return x.compare (y) < 0;
+  }
+
+  inline bool
+  operator> (const uuid& x, const uuid& y)
+  {
+    return x.compare (y) > 0;
+  }
+
+  inline bool
+  operator<= (const uuid& x, const uuid& y)
+  {
+    return x.compare (y) <= 0;
+  }
+
+  inline bool
+  operator>= (const uuid& x, const uuid& y)
+  {
+    return x.compare (y) >= 0;
+  }
+
+  inline uuid uuid::
+  generate (bool strong)
+  {
+    return system_generator.generate (strong);
+  }
+}
+
+namespace std
+{
+  inline size_t hash<butl::uuid>::
+  operator() (const butl::uuid& u) const noexcept
+  {
+    // To make sure hashes for the same UUID are the same on the same-width
+    // platforms we FNV-hash the portable binary prepresentation.
+    //
+    // Let's keep the implementation inline hoping the compiler will unroll
+    // the loop for us.
+    //
+    array<uint8_t, 16> d (u.binary ());
+
+    size_t h (static_cast<size_t> (2166136261UL));
+    for (uint8_t b: d)
+    {
+      h ^= b;
+
+      // We are using the C-style cast to suppress VC warnings for 32-bit
+      // targets (the value is compiled but not used).
+      //
+      h *= sizeof (size_t) == 4
+        ? static_cast<size_t> (16777619UL)
+        : (size_t) 1099511628211ULL;
+    }
+
+    return h;
+  }
+}
diff --git a/tests/uuid/buildfile b/tests/uuid/buildfile
new file mode 100644
index 0000000..101c41b
--- /dev/null
+++ b/tests/uuid/buildfile
@@ -0,0 +1,8 @@
+# file      : tests/uuid/buildfile
+# copyright : Copyright (c) 2014-2018 Code Synthesis Ltd
+# license   : MIT; see accompanying LICENSE file
+
+import libs = libbutl%lib{butl}
+libs += $stdmod_lib
+
+exe{driver}: {hxx cxx}{*} $libs
diff --git a/tests/uuid/driver.cxx b/tests/uuid/driver.cxx
new file mode 100644
index 0000000..f4ee640
--- /dev/null
+++ b/tests/uuid/driver.cxx
@@ -0,0 +1,97 @@
+// file      : tests/uuid/driver.cxx -*- C++ -*-
+// copyright : Copyright (c) 2014-2018 Code Synthesis Ltd
+// license   : MIT; see accompanying LICENSE file
+
+#ifdef _WIN32
+#  include <rpc.h> // GUID
+#endif
+
+#include <cassert>
+#include <sstream>
+#include <iostream>
+
+#include <libbutl/uuid.hxx>
+#include <libbutl/uuid-io.hxx>
+
+using namespace std;
+using namespace butl;
+
+int main ()
+{
+  // Nil.
+  //
+  uuid un;
+  assert (un.nil () && !un);
+
+  // System generator.
+  //
+  uuid u1 (uuid::generate ());
+  uuid u2 (uuid::generate ());
+
+  assert (u1 && u2);
+  assert (u1 != u2);
+
+  // Binary.
+  //
+  assert (uuid (u1.binary ()) == u1);
+
+  // GUID.
+  //
+#ifdef _WIN32
+  assert (uuid (u1.guid ()) == u1);
+#endif
+
+  // String.
+  //
+  assert (uuid (u1.string ())                == u1);
+  assert (uuid (u2.c_string (false).data ()) == u2);
+
+  try {uuid ("123");                                  assert (false);} catch (const invalid_argument&) {}
+  try {uuid ("2cfX28ff-1a9a-451d-b953-1bb4622e810f"); assert (false);} catch (const invalid_argument&) {}
+
+  // Variant and version.
+  //
+  uuid ur ("2cf228ff-1a9a-451d-b953-1bb4622e810f");
+  uuid ut ("027bf5e8-a471-11e8-aa3f-1f0a5c55c825");
+
+  assert (ur.variant () == uuid_variant::dce &&
+          ur.version () == uuid_version::random);
+
+  assert (ut.variant () == uuid_variant::dce &&
+          ut.version () == uuid_version::time);
+
+  // Comparion.
+  //
+  assert (u1 != u2 && u1 == u1 && ur > ut);
+
+  // Input/output.
+  //
+  {
+    stringstream ss;
+    uuid u;
+    assert (ss << u1 && ss >> u && u == u1);
+  }
+
+  // Swap and move.
+  //
+  {
+    uuid un, uc (u1);
+    uc.swap (un);
+    assert (uc.nil () && un == u1);
+  }
+
+  {
+    uuid uc (u1), um (move (uc));
+    assert (uc.nil () && um == u1);
+  }
+
+  {
+    uuid uc (u1), um (u2);
+    um = move (uc);
+    assert (uc.nil () && um == u1);
+  }
+
+  // Hash.
+  //
+  assert (hash<uuid> () (ur) != hash<uuid> () (ut));
+}