search

ak-coram / cl-frugal-uuid

Common Lisp UUID library with zero dependencies
https://github.com/ak-coram/cl-frugal-uuid/blob/main/README.org
MIT License
23 stars 3 forks source link
common-lisp utility-library uuid

readme

+begin_html

Build Status

+end_html

Common Lisp [[https://en.wikipedia.org/wiki/Universally_unique_identifier][UUID]] library with zero dependencies

** Rationale

** Limitations

Please note that by default the implementation dependent built-in CL random number generator is used, which might not be of sufficient quality for your purposes. The use of cryptographic-quality random numbers is strongly recommended in order to reduce the probability of repeated values. Please see the section on randomness in this README for setting up an alternative source of random numbers especially for generating UUID versions 4 and 7.

You can also use the [[https://github.com/ak-coram/cl-frugal-uuid#non-frugal-setup][frugal-uuid/non-frugal]] system to change the defaults and provide support for generating name-based UUIDs (versions 3 and 5). This should only be necessary if you intend to securely generate new UUIDs via this library: for representing existing UUIDs (parsing, comparing and converting values) relying on the frugal-uuid system should be sufficient.

Please also see [[https://github.com/ak-coram/cl-frugal-uuid#Saving-a-Lisp-image][this section]] of the README if you intend on saving your program as a Lisp image.

The following implementations and operating systems are tested via [[https://github.com/ak-coram/cl-frugal-uuid/blob/main/.github/workflows/CI.yml][CI]]:

** Installation

cl-frugal-uuid can be installed via [[https://www.quicklisp.org/][Quicklisp]]:

+begin_src lisp

(ql:quickload :frugal-uuid)

+end_src

The latest version is available from the [[https://ultralisp.org/][Ultralisp]] distribution:

+begin_src lisp

(ql-dist:install-dist "http://dist.ultralisp.org/" :prompt nil) (ql:quickload :frugal-uuid)

+end_src

Alternatively you can also rely on [[https://github.com/ocicl/ocicl][ocicl]].

** Basic usage

+begin_src lisp

;; Generate version 1 UUID (fuuid:make-v1) ; => #<FRUGAL-UUID:UUID 58c3e000-1875-100c-a524-89154ef00c1c>

;; Generate random UUID (fuuid:make-v4) ; => #<FRUGAL-UUID:UUID 3ffc05ba-9c35-4f21-8535-beba03a2495c>

;; Convert random UUID to canonical string representation (fuuid:to-string (fuuid:make-v4)) ; => "2172e412-06a6-4cfb-bbf1-3584aadaed15"

;; Parse UUID from string (fuuid:from-string "0909e4f4-8333-4712-8609-5ae02d735772") ;; => #<FRUGAL-UUID:UUID 0909e4f4-8333-4712-8609-5ae02d735772>

;; Convert UUID to octets (fuuid:to-octets (fuuid:make-v4)) ;; => #(33 194 68 252 59 137 78 19 177 22 25 166 226 241 44 55)

;; Compare two random UUID values (fuuid:uuid= (fuuid:make-v4) (fuuid:make-v4)) ; => NIL

;; Loosely compare UUID with canonical string representation (fuuid:uuid-equal-p (fuuid:from-string "0909e4f4-8333-4712-8609-5ae02d735772") "0909e4f4-8333-4712-8609-5ae02d735772") ; => T

+end_src

** Embedding UUIDs

You can efficiently embed UUID literals in your source using the ~ macro:

+begin_src lisp

(fuuid:~ 1d2f8148-c30c-4f9d-8aae-2ac5807000dc) ;; => #<FRUGAL-UUID:UUID 1d2f8148-c30c-4f9d-8aae-2ac5807000dc>

(multiple-value-list (fuuid:~ 1d2f8148-c30c-4f9d-8aae-2ac5807000dc fa23520b-972c-4f84-b5bf-91f0d7d4f4b4)) ;; => (#<FRUGAL-UUID:UUID 1d2f8148-c30c-4f9d-8aae-2ac5807000dc> ;; #)

;; When called without arguments, the macro generates a random ;; value during expansion (via MAKE-V4): (fuuid:~) ;; => #

+end_src

For writing your own macros, you can rely on the COMPILE-LITERAL function.

** non-frugal setup

+begin_src lisp

(ql:quickload :frugal-uuid/non-frugal)

+end_src

The above system is provided to conveniently setup the following:

frugal-uuid/non-frugal is composed of multiple systems which can also be loaded individually if you only require parts of the above. See [[https://github.com/ak-coram/cl-frugal-uuid/blob/main/frugal-uuid.asd][frugal-uuid.asd]] for details.

** UUID Versions

*** Version 1

Node ID and clock sequence are initialized randomly by default, but you can provide your own values (or even your own function for generating timestamp values) using MAKE-V1-GENERATOR. Currently there's no mechanism included in this library for determining the systems MAC address, but the PARSE-NODE-ID function is included for parsing it once obtained.

The clock sequence is reinitialized on every new clock tick with the highest bit set to zero and a random value for the remaining bits.

To avoid repeated values, it is recommended for multithreaded applications to use a separate generator for each thread. This is automatically done using bordeaux-threads if you use the frugal-uuid/non-frugal system.

Please also see the section on randomness for setting up alternative sources for random numbers.

+begin_src lisp

(bordeaux-threads-2:make-thread (lambda () (format t "~A" (fuuid:make-v1))) :initial-bindings `((fuuid:v1-generator . ,(fuuid:make-v1-generator))))

+end_src

*** Version 2

Generating "DCE security" UUIDs (version 2) is not implemented.

*** Version 3

See section for version 5 below.

*** Version 4

+begin_src lisp

;; Generate random UUID (fuuid:make-v4)

;; Provide 128-bit random number directly and set the bits for version 4 (fuuid:make-v4-from-integer (secure-random:number #xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF))

+end_src

*** Version 5

If you're using the frugal-uuid/non-frugal system, then you can also generate name-based (version 3 or version 5) UUIDs:

+begin_src lisp

(fuuid:make-v3 fuuid:ns-url "https://html5zombo.com/") ;; => #

(let ((cheese-namespace (fuuid:make-v4))) (fuuid:make-v5 cheese-namespace "Orda")) ;; => #

+end_src

*** Version 6

The implementation first generates a version 1 UUID (see above) and reorders the timestamp fields to create a version 6 UUID value. Please note that the slot accessors for the UUID class (TIME-LOW, TIME-MID and TIME-HI-AND-VERSION) are based on RFC 4122 and do not match the timestamp part names used for version 6. Please rely on the following functions instead:

+begin_src lisp

(fuuid:make-v6) ;; => #<FRUGAL-UUID:UUID 1ee2d53a-729c-6929-8c8c-e780ff7b0e6a>

+end_src

*** Version 7

When an accurate system clock is available (see frugal-uuid/non-frugal):

This approach is a combination of methods 2 and 3 from the specification for providing monotonicity.

When no accurate clock is available:

This corresponds to method 2 from the specification for providing monotonicity.

Regarding the monotonic random counter:

+begin_src lisp

(fuuid:make-v7) ;; => #<UUID 0189a085-b115-7e5d-8664-3c5fbe542e4c>

+end_src

*** Version 8

The MAKE-V8 function is provided to create version 8 UUID values from specifying the three custom components:

**** MiNaRa UUID (custom UUID relying on version 8)

The frugal-uuid/non-frugal system provides a custom UUID generation scheme which encodes a nanosecond precision timestamp in a version 8 UUID and randomizes the remaining variable bits. It consists of three components which also make up the name:

The random component may also be used for encoding custom data.

+begin_src lisp

(fuuid:make-minara) ;; => #<FRUGAL-UUID:UUID 01899a63-6540-8d89-b9db-f0fa388bf86e>

(fuuid:minara-components *) ;; => 1690512352576 (41 bits, #x1899A636540) ;; 887271 (20 bits, #xD89E7) ;; 7864781852375150 (53 bits, #x1BF0FA388BF86E)

(fuuid:minara-components (fuuid:make-minara 42)) ;; => 1690514402692 (41 bits, #x1899A82AD84) ;; 507614 (19 bits, #x7BEDE) ;; 42 (6 bits, #x2A, #o52, #b101010)

+end_src

** Timestamps

The Common Lisp standard only provides a function to retrieve the current wall-clock time as a number of whole seconds elapsed since the Common Lisp epoch. In order to make use of the subsecond bits of the timestamp (in UUID versions 1, 6 and 7), the default implementation uses them as a counter which is incremented every time the clock sequence values are exhausted within the same clock tick. If the total number of unique values is exhausted, the counter wraps around and starts at zero again.

Within the frugal-uuid/non-frugal system a more accurate clock is available and the above doesn't apply.

** Randomness

If you have an alternative source of random numbers, you can use it instead of the built-in random number generator. Please consult the documentation of your chosen implementation or library for details on thread-safety if you intend to use this in a multi-threaded program.

*** Ironclad

A setup using [[https://github.com/sharplispers/ironclad#pseudo-random-number-generation][Ironclad PRNG]]:

+begin_src lisp

(ql:quickload :ironclad/prngs)

;; Use the default Ironclad PRNG: (fuuid:initialize-random #'crypto:strong-random)

;; Setup with custom PRNG: (fuuid:initialize-random #'crypto:strong-random (lambda () (ironclad:make-prng :os)))

;; Dynamically bind the generator: (fuuid:with-random-number-generator (ironclad:make-prng :os) (fuuid:make-v4))

+end_src

*** secure-random

Below you'll find and example using the [[https://github.com/avodonosov/secure-random][secure-random]] library which relies on OpenSSL:

+begin_src lisp

;; Load library for generating secure random numbers (ql:quickload :secure-random)

;; Dynamically bind both random number generator & random function: (fuuid:with-random (#'secure-random:number secure-random:generator) (fuuid:make-v4))

+end_src

*** Saving a Lisp image

If you generate UUID values while building your Lisp image, it can include global random state which already has been initialized. This would mean that executing the image multiple times could lead to generating repeated UUID values.

To avoid this, you can clear the global state before saving your image or on image startup (it will be reinitialized on first use):

+begin_src lisp

(setf fuuid:*random-number-generator* nil
      fuuid:*v1-generator* nil
      fuuid:*v7-generator* nil)

+end_src

If you only load the systems in this project this should not be an issue as the global random state is initialized on first use (when generating UUID values of either version 1 or version 4).

Here's an example session illustrating the issue:

+begin_src

$ sbcl

** Running tests

+begin_src lisp

(ql:quickload :frugal-uuid/test)

+end_src

+begin_src lisp

;; Using ASDF: (asdf:test-system :frugal-uuid) ;; Using FiveAM directly: (fiveam:run! :frugal-uuid)

+end_src

** Legal