ulid 0.1.0.0 → 0.2.0.0

raw patch · 9 files changed

+248/−84 lines, 9 filesdep +deepseqdep +format-numbersdep +hashabledep ~basePVP ok

version bump matches the API change (PVP)

Dependencies added: deepseq, format-numbers, hashable, text

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• README.md +21/−0
• app/Main.hs +35/−34
• bench/Main.hs +24/−0
• src/Data/Binary/Roll.hs +28/−0
• src/Data/ULID.hs +79/−3
• src/Data/ULID/Crockford.hs +3/−2
• src/Data/ULID/Random.hs +19/−23
• src/Data/ULID/TimeStamp.hs +18/−4
• ulid.cabal +21/−18

@@ -72,3 +72,24 @@             Right (rnd, g2) -> ULID t rnd   -- use g2, etc, to continue generating secure ULIDs     print ulid3 ````++++## Test Suite++```+stack test+```++## Performance++```+stack bench+```++```+Running 1 benchmarks...+Benchmark ulid-bench: RUNNING...+217,868 op/s generate+Benchmark ulid-bench: FINISH+```

@@ -1,34 +1,35 @@-module Main where--import           Data.ULID---- These imports only needed for cryptographically secure ULID-import qualified Crypto.Random       as CR-import qualified Data.ULID.Random    as UR-import qualified Data.ULID.TimeStamp as TS--main :: IO ()-main = do-     -- Derive a ULID using the current time and default random number generator-    ulid1 <- getULID-    print ulid1--    -- Derive a ULID using a specified time and default random number generator-    ulid2 <- getULIDTime 1469918176.385 -- POSIX Time, specified to the millisecond-    print ulid2---    -- Below only for crypographically secure ULID example--    -- This default instantiation may not be sufficiently secure, see the docs -    -- https://hackage.haskell.org/package/crypto-api-0.13.2/docs/Crypto-Random.html-    g <- (CR.newGenIO :: IO CR.SystemRandom)--    -- Generate time stamp from current time-    t <- TS.getULIDTimeStamp--    let ulid3 = case UR.mkCryptoULIDRandom g of-            Left err        -> error $ show err-            Right (rnd, g2) -> ULID t rnd   -- use g2, etc, to continue generating secure ULIDs-    print ulid3-+module Main where
+
+import           Data.ULID
+
+-- These imports only needed for cryptographically secure ULID
+import qualified Crypto.Random       as CR
+import qualified Data.ULID.Random    as UR
+import qualified Data.ULID.TimeStamp as TS
+
+main :: IO ()
+main = do
+     -- Derive a ULID using the current time and default random number generator
+    ulid1 <- getULID
+    print ulid1
+
+    -- Derive a ULID using a specified time and default random number generator
+    ulid2 <- getULIDTime 1469918176.385 -- POSIX Time, specified to the millisecond
+    print ulid2
+
+
+    -- Below only for crypographically secure ULID example
+
+    -- This default instantiation may not be sufficiently secure, see the docs
+    -- https://hackage.haskell.org/package/crypto-api-0.13.2/docs/Crypto-Random.html
+    g <- (CR.newGenIO :: IO CR.SystemRandom)
+
+    -- Generate time stamp from current time
+    t <- TS.getULIDTimeStamp
+
+    let ulid3 = case UR.mkCryptoULIDRandom g of
+            Left err        -> error $ show err
+            Right (rnd, g2) -> ULID t rnd   -- use g2, etc, to continue generating secure ULIDs
+    print ulid3
+
+

@@ -0,0 +1,24 @@+module Main where
+
+import           Data.ULID
+
+import           Control.DeepSeq
+import           Control.Monad            (replicateM)
+import qualified Data.Text                as T
+import qualified Data.Text.Format.Numbers as FN
+import qualified Data.Time.Clock.POSIX    as PX
+
+formatTN = T.unpack . (FN.prettyI (Just ','))
+
+main :: IO ()
+main = do
+    -- Run many iterations of getULID
+    let ops = 100000
+    begin <- PX.getPOSIXTime
+    ulids <- replicateM ops (getULID >>= return.force)
+    end <- PX.getPOSIXTime
+    let elapsed = end - begin
+    let opsPerSec = (fromIntegral ops) / (realToFrac elapsed) :: Double
+    putStr $ formatTN (round opsPerSec)
+    putStrLn " op/s generate"
+

@@ -0,0 +1,28 @@+module Data.Binary.Roll where
+
+import           Data.Binary
+import           Data.Bits
+import           Data.List   (foldl', unfoldr)
+
+
+-- | unroll and produce an exact number of bytes (left-pad with 0 bytes)
+unroll :: Int -> Integer -> [Word8]
+unroll bytes val = replicate (bytes - length xs) 0 ++ xs
+    where xs = unroll' val
+
+-- source: http://hackage.haskell.org/package/binary-0.8.5.1/docs/src/Data-Binary-Class.html#line-311
+--
+-- Fold and unfold an Integer to and from a list of its bytes
+--
+-- MOST SIGNIFICANT BYTE FIRST please (this is a change from the default Data.Binary impl)
+
+unroll' :: Integer -> [Word8]
+unroll' = reverse . unfoldr step
+  where
+    step 0 = Nothing
+    step i = Just (fromIntegral i, i `shiftR` 8)
+
+roll :: [Word8] -> Integer
+roll = foldl' unstep 0
+  where
+    unstep a b = a `shiftL` 8 .|. fromIntegral b

@@ -1,19 +1,61 @@+{- |
+Module      : Data.ULID
+Copyright   : (c) 2017 Steve Kollmansberger
+
+License     : BSD-style
+
+Maintainer  : steve@kolls.net
+Stability   : experimental
+Portability : portable
+
+This library implements the Universally Unique Lexicographically Sortable Identifier, as described at <https://github.com/alizain/ulid>.
+
+UUID can be suboptimal for many uses-cases because:
+
+* It isn't the most character efficient way of encoding 128 bits of randomness
+* UUID v1/v2 is impractical in many environments, as it requires access to a unique, stable MAC address
+* UUID v3/v5 requires a unique seed and produces randomly distributed IDs, which can cause fragmentation in many data structures
+* UUID v4 provides no other information than randomness which can cause fragmentation in many data structures
+
+Instead, herein is proposed ULID:
+
+* 128-bit compatibility with UUID
+* 1.21e+24 unique ULIDs per millisecond
+* Lexicographically sortable!
+* Canonically encoded as a 26 character string, as opposed to the 36 character UUID
+* Uses Crockford's base32 for better efficiency and readability (5 bits per character)
+* Case insensitive
+* No special characters (URL safe)
+
+-}
+{-# LANGUAGE DeriveDataTypeable #-}
 module Data.ULID (
     ULID(..),
     getULIDTime,
-    getULID
+    getULID,
+    ulidToInteger,
+    ulidFromInteger
 ) where
 
+import           Control.DeepSeq
+import           Data.Binary
+import qualified Data.ByteString.Lazy  as LBS
+import           Data.Data
+import           Data.Hashable
+import           Data.Monoid           ((<>))
 import           Data.Time.Clock.POSIX
+import           System.IO.Unsafe
+import qualified System.Random         as R
 
+import           Data.Binary.Roll
 import           Data.ULID.Random
 import           Data.ULID.TimeStamp
 
-data ULID = ULID {    
+data ULID = ULID {
     timeStamp :: !ULIDTimeStamp,
     random    :: !ULIDRandom
     }
-    deriving (Eq)
+    deriving (Eq, Typeable, Data)
 
 -- | Derive a ULID using a specified time and default random number generator
 getULIDTime :: POSIXTime    -- ^ The specified UNIX time (seconds) to millisecond precision, e.g. 1469918176.385
@@ -30,6 +72,16 @@     r <- getULIDRandom
     return $ ULID t r
 
+-- | Convert a ULID to its corresponding (at most) 128-bit Integer. Integer equivalents retain sortable trait (same sort order).
+-- This could be useful for storing in a database using a smaller field than storing the Show'n string, but still human-readable unlike the Binary version.
+ulidToInteger :: ULID -> Integer
+ulidToInteger = roll.(LBS.unpack).encode
+
+-- | Convert a ULID from its corresponding 128-bit Integer.
+ulidFromInteger :: Integer -- ^ The ULID's Integer equivalent, as generated by toInteger
+    -> ULID
+ulidFromInteger = decode.(LBS.pack).(unroll 16) -- 16 bytes = 128 bit
+
 instance Ord ULID where
     compare (ULID ts1 _) (ULID ts2 _) = compare ts1 ts2
 
@@ -41,3 +93,27 @@         (ts, str2) <- reads str
         (rn, str3) <- reads str2
         return (ULID ts rn, str3)
+
+instance Binary ULID where
+    put (ULID ts bytes) = put ts <> put bytes
+    get = do
+        ts <- get
+        bytes <- get
+        return $ ULID ts bytes
+
+-- Because of the strictness annotations, this shouldn't be needed and shouldn't do anything
+-- I tested and confirmed this in the benchmark, but since I did the work to put it here
+-- It's no harm to leave it in
+instance NFData ULID where
+    rnf (ULID ts bytes) = rnf ts `seq` (rnf bytes `seq` ())
+
+instance R.Random ULID where
+    randomR _ = R.random -- ignore range
+    random g = unsafePerformIO $ do
+        t <- getULIDTimeStamp
+        let (r, g') = mkULIDRandom g
+        return (ULID t r, g')
+    randomIO = getULID
+
+instance Hashable ULID where
+    hashWithSalt salt ulid = hashWithSalt salt (encode ulid)

@@ -4,8 +4,9 @@ import           Text.Read
 
 -- source: https://stackoverflow.com/a/29153602
-leftpad m xs = replicate (m - length ys) '0' ++ ys
-    where ys = take m xs
+-- I removed the safety for m > length because that should never happen
+-- and if it does, I want it to crash!
+leftpad m xs = replicate (m - length xs) '0' ++ xs
 
 encode :: Int -> Integer -> String
 encode width = (leftpad width).(CR.encode)

@@ -1,3 +1,4 @@+{-# LANGUAGE DeriveDataTypeable #-}
 module Data.ULID.Random (
     ULIDRandom,
     mkCryptoULIDRandom,
@@ -5,11 +6,13 @@     getULIDRandom
 ) where
 
+import           Control.DeepSeq
+import           Control.Monad
 import           Crypto.Random
 import           Data.Binary
-import           Data.Bits
+import           Data.Binary.Roll
 import qualified Data.ByteString     as BS
-import           Data.List           (foldl', unfoldr)
+import           Data.Data
 import           Data.Word
 import           System.Random
 
@@ -18,13 +21,15 @@ 
 
 newtype ULIDRandom = ULIDRandom BS.ByteString
-    deriving (Eq)
+    deriving (Eq, Typeable, Data)
 
--- | Generate a ULID Random based on a cryptographically secure random number generator. 
+numBytes = 10 -- 80 bits
+
+-- | Generate a ULID Random based on a cryptographically secure random number generator.
 -- | see: https://hackage.haskell.org/package/crypto-api-0.13.2/docs/Crypto-Random.html
 mkCryptoULIDRandom :: CryptoRandomGen g => g -> Either GenError (ULIDRandom, g)
 mkCryptoULIDRandom g = do
-    (b, g2) <- genBytes 10 g
+    (b, g2) <- genBytes numBytes g
     return (ULIDRandom b, g2)
 
 -- | Generate a ULID Random based on a standard random number generator.
@@ -32,31 +37,22 @@ mkULIDRandom :: RandomGen g => g -> (ULIDRandom, g)
 mkULIDRandom g = let
     (g1, g2) = split g
-    genbytes = (BS.pack) . take 10 . randoms
+    genbytes = (BS.pack) . take numBytes . randoms
     in (ULIDRandom $ genbytes g, g2)
 
 -- | Generate a ULID Random based on the global random number generator.
 getULIDRandom :: IO ULIDRandom
 getULIDRandom = fst <$> mkULIDRandom <$> newStdGen -- Note: the call to newStdGen splits the generator, so this is safe to call multiple times
 
-
--- source: http://hackage.haskell.org/package/binary-0.8.5.1/docs/src/Data-Binary-Class.html#line-311
---
--- Fold and unfold an Integer to and from a list of its bytes
---
-unroll :: Integer -> [Word8]
-unroll = unfoldr step
-  where
-    step 0 = Nothing
-    step i = Just (fromIntegral i, i `shiftR` 8)
-
-roll :: [Word8] -> Integer
-roll = foldl' unstep 0 . reverse
-  where
-    unstep a b = a `shiftL` 8 .|. fromIntegral b
-
 instance Show ULIDRandom where
     show (ULIDRandom r) =  (CR.encode) 16.roll.(BS.unpack) $ r
 
 instance Read ULIDRandom where
-    readsPrec _ = map (\(c,r)->(ULIDRandom $ (BS.pack) $ unroll c, r)) . (CR.decode) 16
+    readsPrec _ = map (\(c,r)->(ULIDRandom $ (BS.pack) $ unroll numBytes c, r)) . (CR.decode) 16
+
+instance Binary ULIDRandom where
+    put (ULIDRandom r) = mapM_ put (BS.unpack $ r)
+    get = ULIDRandom <$> (BS.pack) <$> replicateM numBytes get
+
+instance NFData ULIDRandom where
+    rnf (ULIDRandom r) = rnf r

@@ -1,17 +1,25 @@+{-# LANGUAGE DeriveDataTypeable #-}
 module Data.ULID.TimeStamp (
     ULIDTimeStamp,
     mkULIDTimeStamp,
     getULIDTimeStamp
 ) where
 
+import           Control.DeepSeq
+import           Control.Monad
+import           Data.Binary
+import           Data.Binary.Roll
+import           Data.Data
 import           Data.Time.Clock
 import           Data.Time.Clock.POSIX
 
-import           Data.ULID.Crockford
+import qualified Data.ULID.Crockford   as CR
 
+numBytes = 6 -- 48 bits
+
 -- UNIX time in milliseconds
 newtype ULIDTimeStamp = ULIDTimeStamp Integer
-    deriving (Eq, Ord)
+    deriving (Eq, Ord, Typeable, Data)
 
 -- | Generate a ULID Timestamp based on a specified time
 mkULIDTimeStamp :: POSIXTime -- ^ The specified UNIX time (seconds) to millisecond precision, e.g. 1469918176.385
@@ -23,8 +31,14 @@ getULIDTimeStamp = mkULIDTimeStamp <$> getPOSIXTime
 
 instance Show ULIDTimeStamp where
-    show (ULIDTimeStamp i) = encode 10 i
+    show (ULIDTimeStamp i) = CR.encode 10 i
 
 instance Read ULIDTimeStamp where
-    readsPrec _ = map (\(c,r)->(ULIDTimeStamp c, r)) . decode 10
+    readsPrec _ = map (\(c,r)->(ULIDTimeStamp c, r)) . (CR.decode) 10
 
+instance Binary ULIDTimeStamp where
+    put (ULIDTimeStamp i) = mapM_ put (unroll numBytes i)
+    get = ULIDTimeStamp <$> roll <$> replicateM numBytes get
+
+instance NFData ULIDTimeStamp where
+    rnf (ULIDTimeStamp i) = rnf i

@@ -1,23 +1,8 @@ name:                ulid-version:             0.1.0.0+version:             0.2.0.0 synopsis:            Implementation of ULID, lexicographically sortable unique identifiers-description:         Implementation of alizain's ULID identifier (https://github.com/alizain/ulid ).--                     UUID can be suboptimal for many uses-cases because:--                     It isn't the most character efficient way of encoding 128 bits of randomness-                     UUID v1/v2 is impractical in many environments, as it requires access to a unique, stable MAC address-                     UUID v3/v5 requires a unique seed and produces randomly distributed IDs, which can cause fragmentation in many data structures-                     UUID v4 provides no other information than randomness which can cause fragmentation in many data structures-                     Instead, herein is proposed ULID:--                     128-bit compatibility with UUID-                     1.21e+24 unique ULIDs per millisecond-                     Lexicographically sortable!-                     Canonically encoded as a 26 character string, as opposed to the 36 character UUID+description:         Implementation of alizain's ULID identifier. Canonically encoded as a 26 character string, as opposed to the 36 character UUID.                       Uses Crockford's base32 for better efficiency and readability (5 bits per character)-                     Case insensitive-                     No special characters (URL safe) homepage:            https://github.com/steven777400/ulid license:             BSD3 license-file:        LICENSE@@ -35,6 +20,7 @@                     ,  Data.ULID.Crockford                     ,  Data.ULID.Random                     ,  Data.ULID.TimeStamp+  other-modules:       Data.Binary.Roll                     build-depends:       base >= 4.7 && < 5                     ,  crockford                     ,  time@@ -42,6 +28,8 @@                     ,  random                     ,  bytestring                     ,  binary+                    ,  deepseq+                    ,  hashable   default-language:    Haskell2010  executable ulid-exe@@ -50,7 +38,7 @@   ghc-options:         -threaded -rtsopts -with-rtsopts=-N   build-depends:       base                      , ulid-                     , crypto-api+                     , crypto-api                        default-language:    Haskell2010  test-suite ulid-test@@ -60,8 +48,23 @@   build-depends:       base                      , hspec                      , ulid+                     , bytestring+                     , binary+                     , random+                     , hashable   ghc-options:         -threaded -rtsopts -with-rtsopts=-N   default-language:    Haskell2010++benchmark ulid-bench+    type:                exitcode-stdio-1.0+    hs-source-dirs:      bench+    main-is:             Main.hs+    build-depends:       base+                      ,  ulid                     +                      ,  time+                      ,  text+                      ,  format-numbers+                      ,  deepseq  source-repository head   type:     git