uuuidv7

defmodule UUIDv7 do
  @moduledoc """
  UUIDv7 for Elixir.

  Used for generating version 7 UUIDs using submicrosecond precision.
  Normally the default precision is 1 millisecond, this causes issues
  when generating UUIDs in bulk because we can generate multiple UUIDs
  in the same millisecond. This module allows you to generate UUIDs with
  submicrosecond precision.

    UUIDv7.generate()
    "018e90d8-06e8-7f9f-bfd7-6730ba98a51b"

    UUIDv7.bingenerate()
    <<1, 142, 144, 216, 6, 232, 127, 159, 191, 215, 103, 48, 186, 152, 165, 27>>

  """
  if Code.ensure_loaded?(Ecto.Type) do
    use Ecto.Type

    @impl true
    def autogenerate(), do: generate()
    @impl true
    def type(), do: :uuid
    @impl true
    defdelegate cast(term), to: Ecto.UUID
    @impl true
    defdelegate dump(term), to: Ecto.UUID
    @impl true
    def load(<<_::128>> = raw_uuid), do: {:ok, encode(raw_uuid)}
  end

  @typedoc """
  A hex-encoded UUID string.
  """
  @type t :: <<_::288>>

  @typedoc """
  A raw binary representation of a UUID.
  """
  @type raw :: <<_::128>>

  @version 7
  @variant 2

  @doc """
  Generates a version 7 UUID using submilliseconds for increased clock
  precision.

  ## Example

    iex> [UUIDv7.generate(), UUIDv7.generate()]
    iex> |> Enum.map(& String.byte_slice(&1, 0, 11))
    iex> |> Enum.reduce(fn second, first -> second == first end)
    true

  """
  @spec generate() :: t
  def generate, do: bingenerate() |> encode()

  @doc """
  Generates a version 7 UUID in the binary format.

  ## Example

    iex> [UUIDv7.bingenerate(), UUIDv7.bingenerate()]
    iex> |> Enum.map(& :binary.part(&1, 0, 5))
    iex> |> Enum.reduce(fn second, first -> second == first end)
    true

  """
  def bingenerate do
    {milliseconds, scaled_nanos} = get_time()

    <<rand::62, _::2>> = :crypto.strong_rand_bytes(8)

    <<milliseconds::big-unsigned-48, @version::4, scaled_nanos::12, @variant::2, rand::62>>
  end

  @doc """
  Bulk-generates `n` raw UUIDv7 binaries.

  Each millisecond can hold up to 4096 strictly-ordered UUIDs (the
  capacity of the 12-bit sub-millisecond field). For `n <= 4096` the
  whole batch shares a single millisecond. For larger batches, full
  chunks of 4096 are generated at consecutive milliseconds and the
  remainder (if any) lands in the next millisecond — so the batch keeps
  monotonically-increasing timestamps without ever colliding inside a
  single ms.

  Within each millisecond the 12-bit sub-millisecond field is
  partitioned into `n` equal slots (`step = div(4096, n)`); each UUID's
  value is `step * i + jitter`, where the jitter is a crypto-strong
  offset within `[0, step)`. This guarantees strict in-batch ordering
  while keeping positions inside each slot randomized.

  Both `rand_b` (62 bits) and the jitter (12 bits) are sliced from the
  same `:crypto.strong_rand_bytes/1` call — 10 bytes per UUID, no extra
  PRNG overhead.

  Note: when `n > 4096`, this function burns `div(n - 1, 4096)` future
  milliseconds. Subsequent `bingenerate/0` calls landing in those same
  milliseconds still won't collide (62 random bits per UUID), but
  conceptually the batch reaches ahead of the wall clock.

  ## Examples

      iex> uuids = UUIDv7.bingenerate_many(4)
      iex> length(uuids)
      4
      iex> uuids == Enum.sort(uuids)
      true

      iex> uuids = UUIDv7.bingenerate_many(10_000)
      iex> length(uuids)
      10_000
      iex> uuids == Enum.sort(uuids)
      true
  """
  @spec bingenerate_many(pos_integer()) :: [raw]
  def bingenerate_many(n) when is_integer(n) and n >= 1 and n <= 4096 do
    {ms, _} = get_time()
    bingenerate_ms_chunk(ms, n)
  end

  def bingenerate_many(n) when is_integer(n) and n > 4096 do
    {start_ms, _} = get_time()
    chunked(n, start_ms, [])
  end

  defp chunked(n, ms, acc) when n <= 4096 do
    :lists.append(:lists.reverse([bingenerate_ms_chunk(ms, n) | acc]))
  end

  defp chunked(n, ms, acc) do
    chunked(n - 4096, ms + 1, [bingenerate_ms_chunk(ms, 4096) | acc])
  end

  defp bingenerate_ms_chunk(ms, n) do
    step = div(4096, n)
    rand_bytes = :crypto.strong_rand_bytes(n * 10)
    build_many(ms, step, 0, n, rand_bytes, [])
  end

  defp build_many(_ms, _step, n, n, _rand, acc), do: :lists.reverse(acc)

  defp build_many(ms, step, i, n, <<rand::62, jitter::12, _::6, rest::binary>>, acc) do
    scaled_nanos = step * i + rem(jitter, step)
    uuid = <<ms::big-unsigned-48, @version::4, scaled_nanos::12, @variant::2, rand::62>>
    build_many(ms, step, i + 1, n, rest, [uuid | acc])
  end

  @doc """
  String-encoded counterpart of `bingenerate_many/1`.

  ## Example

      iex> uuids = UUIDv7.generate_many(8)
      iex> length(uuids)
      8
      iex> uuids == Enum.sort(uuids)
      true
  """
  @spec generate_many(pos_integer()) :: [t]
  def generate_many(n), do: n |> bingenerate_many() |> Enum.map(&encode/1)

  @doc """
  Generates a random version 7 UUID for a specific DateTime.

  Similar to `generate/0`, but uses the provided DateTime for the timestamp
  instead of the current time. The sub-millisecond precision and random bits
  are still randomly generated.

  Useful for:
  - Generating backdated UUIDs for testing
  - Creating UUIDs for historical data
  - Partitioning data by time ranges

  ## Example

      iex> {:ok, dt, _} = DateTime.from_iso8601("2024-01-01T00:00:00.000Z")
      iex> uuid = UUIDv7.generate_from_datetime(dt)
      iex> UUIDv7.extract_timestamp(uuid) == DateTime.to_unix(dt, :millisecond)
      true

  """
  @spec generate_from_datetime(DateTime.t()) :: t
  def generate_from_datetime(%DateTime{} = datetime) do
    bingenerate_from_datetime(datetime) |> encode()
  end

  @doc """
  Generates a random version 7 UUID in binary format for a specific DateTime.

  Binary version of `generate_from_datetime/1`.

  ## Example

      iex> {:ok, dt, _} = DateTime.from_iso8601("2024-01-01T00:00:00.000Z")
      iex> uuid = UUIDv7.bingenerate_from_datetime(dt)
      iex> is_binary(uuid) and byte_size(uuid) == 16
      true

  """
  @spec bingenerate_from_datetime(DateTime.t()) :: raw
  def bingenerate_from_datetime(%DateTime{} = datetime) do
    milliseconds = DateTime.to_unix(datetime, :millisecond)

    # Generate random sub-millisecond precision (0-4095)
    <<scaled_nanos::12, _::4>> = :crypto.strong_rand_bytes(2)

    # Generate random bits
    <<rand::62, _::2>> = :crypto.strong_rand_bytes(8)

    <<milliseconds::big-unsigned-48, @version::4, scaled_nanos::12, @variant::2, rand::62>>
  end

  # This maps the microsecond range to 4096 values
  # that fits in 12 bits
  @scale 1_000_000 / 4096
  @nanoseconds_per_millisecond 1_000_000
  @doc """
  returns the current time in milliseconds and scaled nanoseconds
  """
  def get_time do
    timestamp = System.system_time(:nanosecond)
    milliseconds = div(timestamp, @nanoseconds_per_millisecond)
    remaining_nanos = rem(timestamp, @nanoseconds_per_millisecond)
    {milliseconds, scale_nanoseconds(remaining_nanos)}
  end

  @doc """
  scales the remaining nanoseconds to fit in 12 bits

  ## Example

      iex> UUIDv7.scale_nanoseconds(0)
      0
      iex> UUIDv7.scale_nanoseconds(500000)
      2048
      iex> UUIDv7.scale_nanoseconds(999999)
      0xFFF

  """
  def scale_nanoseconds(nanos) do
    trunc(nanos / @scale)
  end

  @doc """
  Extract the millisecond timestamp from the UUID.

  ## Example

      iex> UUIDv7.extract_timestamp("018ecb40-c457-73e6-a400-000398daddd9")
      1712807003223

  """
  @spec extract_timestamp(t | raw | UUID.t()) :: integer
  def extract_timestamp(%UUID{bytes: bytes}), do: extract_timestamp(bytes)

  def extract_timestamp(
        <<timestamp_ms::big-unsigned-48, @version::4, _rand_a::12, _variant::2, _::62>>
      ) do
    timestamp_ms
  end

  def extract_timestamp(<<_::288>> = uuid) do
    decode(uuid) |> extract_timestamp()
  end

  @doc """
  Encode a raw UUID to the string representation.

  ## Example

      iex> UUIDv7.encode(<<1, 142, 144, 216, 6, 232, 127, 159, 191, 215, 103, 48, 186, 152, 165, 27>>)
      "018e90d8-06e8-7f9f-bfd7-6730ba98a51b"

  """
  @spec encode(raw) :: t
  def encode(
        <<a1::4, a2::4, a3::4, a4::4, a5::4, a6::4, a7::4, a8::4, b1::4, b2::4, b3::4, b4::4,
          c1::4, c2::4, c3::4, c4::4, d1::4, d2::4, d3::4, d4::4, e1::4, e2::4, e3::4, e4::4,
          e5::4, e6::4, e7::4, e8::4, e9::4, e10::4, e11::4, e12::4>>
      ) do
    <<e(a1), e(a2), e(a3), e(a4), e(a5), e(a6), e(a7), e(a8), ?-, e(b1), e(b2), e(b3), e(b4), ?-,
      e(c1), e(c2), e(c3), e(c4), ?-, e(d1), e(d2), e(d3), e(d4), ?-, e(e1), e(e2), e(e3), e(e4),
      e(e5), e(e6), e(e7), e(e8), e(e9), e(e10), e(e11), e(e12)>>
  end

  @compile {:inline, e: 1}

  defp e(0), do: ?0
  defp e(1), do: ?1
  defp e(2), do: ?2
  defp e(3), do: ?3
  defp e(4), do: ?4
  defp e(5), do: ?5
  defp e(6), do: ?6
  defp e(7), do: ?7
  defp e(8), do: ?8
  defp e(9), do: ?9
  defp e(10), do: ?a
  defp e(11), do: ?b
  defp e(12), do: ?c
  defp e(13), do: ?d
  defp e(14), do: ?e
  defp e(15), do: ?f

  @doc """
  Decode a string representation of a UUID to the raw binary version.

  ## Example

      iex> UUIDv7.decode("018e90d8-06e8-7f9f-bfd7-6730ba98a51b")
      <<1, 142, 144, 216, 6, 232, 127, 159, 191, 215, 103, 48, 186, 152, 165, 27>>

  """
  @spec decode(t) :: raw | :error
  def decode(
        <<a1, a2, a3, a4, a5, a6, a7, a8, ?-, b1, b2, b3, b4, ?-, c1, c2, c3, c4, ?-, d1, d2, d3,
          d4, ?-, e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11, e12>>
      ) do
    <<d(a1)::4, d(a2)::4, d(a3)::4, d(a4)::4, d(a5)::4, d(a6)::4, d(a7)::4, d(a8)::4, d(b1)::4,
      d(b2)::4, d(b3)::4, d(b4)::4, d(c1)::4, d(c2)::4, d(c3)::4, d(c4)::4, d(d1)::4, d(d2)::4,
      d(d3)::4, d(d4)::4, d(e1)::4, d(e2)::4, d(e3)::4, d(e4)::4, d(e5)::4, d(e6)::4, d(e7)::4,
      d(e8)::4, d(e9)::4, d(e10)::4, d(e11)::4, d(e12)::4>>
  catch
    :error -> :error
  end

  def decode(_), do: :error

  @compile {:inline, d: 1}

  defp d(?0), do: 0
  defp d(?1), do: 1
  defp d(?2), do: 2
  defp d(?3), do: 3
  defp d(?4), do: 4
  defp d(?5), do: 5
  defp d(?6), do: 6
  defp d(?7), do: 7
  defp d(?8), do: 8
  defp d(?9), do: 9
  defp d(?A), do: 10
  defp d(?B), do: 11
  defp d(?C), do: 12
  defp d(?D), do: 13
  defp d(?E), do: 14
  defp d(?F), do: 15
  defp d(?a), do: 10
  defp d(?b), do: 11
  defp d(?c), do: 12
  defp d(?d), do: 13
  defp d(?e), do: 14
  defp d(?f), do: 15
  defp d(_), do: throw(:error)

  @doc """
  Generates the minimum UUID v7 for a given `Date` or `DateTime`.

  Creates a UUID with the timestamp from the given moment and all random
  bits set to zero — the smallest possible UUID for that millisecond.
  For a `Date`, midnight UTC of that day is used.

  Used for half-closed time ranges in database partitioning:
  - Range `[T1, T2)`: `WHERE uuid >= min_uuid(T1) AND uuid < min_uuid(T2)`
  - Ranges are continuous with no gaps or overlaps

  ## Examples

      iex> {:ok, dt, _} = DateTime.from_iso8601("2024-01-01T00:00:00.000Z")
      iex> uuid = UUIDv7.min_uuid(dt)
      iex> String.ends_with?(uuid, "7000-8000-000000000000")
      true

      iex> UUIDv7.min_uuid(~D[2024-01-01])
      "018cc251-f400-7000-8000-000000000000"
  """
  @spec min_uuid(Date.t() | DateTime.t()) :: t
  def min_uuid(%Date{} = date) do
    date
    |> DateTime.new!(~T[00:00:00.000], "Etc/UTC")
    |> min_uuid()
  end

  def min_uuid(%DateTime{} = datetime) do
    milliseconds = DateTime.to_unix(datetime, :millisecond)

    <<milliseconds::big-unsigned-48, @version::4, 0::12, @variant::2, 0::62>>
    |> encode()
  end

  @doc """
  Extracts a `DateTime` (UTC, millisecond precision) from a UUIDv7.

  Accepts the hex string form, the raw 16-byte binary, or a `%UUID{}`
  struct.

  ## Example

      iex> UUIDv7.to_datetime("018ecb40-c457-73e6-a400-000398daddd9")
      ~U[2024-04-11 03:43:23.223Z]
  """
  @spec to_datetime(t | raw | UUID.t()) :: DateTime.t()
  def to_datetime(uuid) do
    uuid
    |> extract_timestamp()
    |> DateTime.from_unix!(:millisecond)
  end

  @doc """
  Extracts a `Date` (UTC) from a UUIDv7.

  Accepts the hex string form, the raw 16-byte binary, or a `%UUID{}`
  struct.

  ## Example

      iex> UUIDv7.to_date("018ecb40-c457-73e6-a400-000398daddd9")
      ~D[2024-04-11]
  """
  @spec to_date(t | raw | UUID.t()) :: Date.t()
  def to_date(uuid) do
    uuid
    |> to_datetime()
    |> DateTime.to_date()
  end
end