firebase_pushid.nim

# Fancy ID generator that creates 20-character string identifiers with the following properties:
#
# 1. They're based on timestamp so that they sort *after* any existing ids.
# 2. They contain 72-bits of random data after the timestamp so that IDs won't collide with other clients' IDs.
# 3. They sort *lexicographically* (so the timestamp is converted to characters that will sort properly).
# 4. They're monotonically increasing.  Even if you generate more than one in the same timestamp, the
#    latter ones will sort after the former ones.  We do this by using the previous random bits
#    but "incrementing" them by 1 (only in the case of a timestamp collision).
#
# Based on https://www.firebase.com/blog/2015-02-11-firebase-unique-identifiers.html
# Nim version by H. Raaf / GitHub: OderWat

import times, math

# Modeled after base64 web-safe chars, but ordered by ASCII.
const PUSH_CHARS = "-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz"

# Timestamp of last push, used to prevent local collisions if you push twice in one ms.
var lastPushTime = 0

# We generate 72-bits of randomness which get turned into 12 characters and appended to the
# timestamp to prevent collisions with other clients.  We store the last characters we
# generated because in the event of a collision, we'll use those same characters except
# "incremented" by one.
var lastRandChars: array[12, int8]

proc generatePushID: array[21, char] =
    var now = int(getTime().toSeconds())
    let duplicateTime = now == lastPushTime
    lastPushTime = now

    for i in countdown(7, 0):
        result[i] = PUSH_CHARS[now mod 64]
        now = now div 64

    assert now == 0 # We should have converted the entire timestamp.

    if not duplicateTime:
        for c in lastRandChars.mitems:
            c = int8(random(64))
    else:
        # If the timestamp hasn't changed since last push,
        # use the same random number, except incremented by 1.
        var i = lastRandChars.high
        while i >= 0 and lastRandChars[i] == 63:
            lastRandChars[i] = 0
            dec i

        inc lastRandChars[i]

    for i, o in lastRandChars:
        result[8+i] = PUSH_CHARS[o]

when isMainModule:
    randomize() # Needed for pseudo-random numbers

    echo generatePushID()
    echo generatePushID()
    echo generatePushID()

    for i in 1..1_000_000:
        discard generatePushID()

    echo generatePushID()