once

defmodule Once do
  @format_docs """
  - `:url64` a url64-encoded string of 11 characters, for example `"AAjhfZyAAAE"`
  - `:hex` a hex-encoded string of 16 characters, for example `"e010831058218a39"`
  - `:raw` a bitstring of 64 bits, for example `<<0, 8, 225, 125, 156, 128, 0, 2>>`
  - `:signed` a signed 64-bits integer, like `-12345`, between -(2^63) and 2^63-1
  - `:unsigned` an unsigned 64-bits integer, like `67890`, between 0 and 2^64-1
  - `:hex32` an extended-hex string of 13 characters, for example "0786vs3p0000a"
  """
  @options_docs """
  - `:no_noncense` name of the NoNoncense instance used to generate new IDs (default `Once`)
  - `:ex_format` what an ID looks like in Elixir, one of `t:format/0` (default `:url64`). Be sure to read [the caveats](`m:Once#module-elixir-format-caveats`).
  - `:db_format` what an ID looks like in your database, one of `t:format/0` (default `:signed`)
  - `:nonce_type` how the nonce is generated, one of `t:nonce_type/0` (default `:counter`)
  """

  @moduledoc """
  Once is an Ecto type for locally unique 64-bits IDs generated by multiple Elixir nodes. Locally unique IDs make it easier to keep things separated, simplify caching and simplify inserting related things (because you don't have to wait for the database to return the ID). A Once can be generated in multiple ways:

  - counter (default): really fast to generate, predictable, works well with b-tree indexes
  - [encrypted](#module-encrypted-ids): unique and unpredictable, like a UUIDv4 but shorter
  - sortable: time-sortable like a [Snowflake ID](https://en.wikipedia.org/wiki/Snowflake_ID)

  For prefixed IDs like `"usr_AV7m9gAAAAU"`, see `Once.Prefixed`.

  > #### Read the migration guide {: .warning}
  >
  > If you're upgrading from v0.x.x and you use encrypted IDs, please read the [Migration Guide](MIGRATION.md) carefully - there are breaking changes that require attention to preserve uniqueness guarantees.

  A Once can look however you want, and can be stored in multiple ways as well. By default, in Elixir it's a url64-encoded 11-char string, and in the database it's a signed bigint. By using the `:ex_format` and `:db_format` options, you can choose both the Elixir and storage format out of `t:format/0`. You can pick any combination and use `to_format/3` to transform them as you wish!

  Because a Once fits into an SQL bigint, they use little space and keep indexes small and fast. Because of their [structure](https://hexdocs.pm/no_noncense/NoNoncense.html#module-nonce-types) they have counter-like data locality, which helps your indexes perform well, [unlike UUIDv4s](https://www.cybertec-postgresql.com/en/unexpected-downsides-of-uuid-keys-in-postgresql/). If you don't care about that and want unpredictable IDs, you can use encrypted IDs that seem random and are still unique.

  The actual values are generated by `NoNoncense`, which performs incredibly well, hitting rates of tens of millions of nonces per second, and it also helps you to safeguard the uniqueness guarantees.

  The library has only `Ecto` and its sibling `NoNoncense` as dependencies.

  ## Usage

  To get going, you need to set up a `NoNoncense` instance to generate the base unique values. Follow [its documentation](https://hexdocs.pm/no_noncense) to do so. `Once` expects an instance with its own module name by default, like so:

      # application.ex (read the NoNoncense docs!)
      machine_id = NoNoncense.MachineId.id!(opts)
      NoNoncense.init(name: Once, machine_id: machine_id)

  In your `Ecto` schemas, you can then use the type:

      schema "things" do
        field :id, Once
      end

  And that's it!

  ## Options

  The Ecto type takes a few optional parameters:

  #{@options_docs}

  ## Data formats

  There's a drawback to having different data formats for Elixir and SQL: it makes it harder to compare the two. The following are all the same ID:

      -1
      <<255, 255, 255, 255, 255, 255, 255, 255>>
      "__________8"
      18_446_744_073_709_551_615
      "ffffffffffffffff"

  If you use the defaults `:url64` as the Elixir format and `:signed` in your database, you could see `"AAAAAACYloA"` in Elixir and `10_000_000` in your database. The reasoning behind these defaults is that the encoded format is readable, short, and JSON safe by default, while the signed format means you can use a standard bigint column type.

  The negative integers will not cause problems with Postgres and MySQL, they both happily swallow them. Also, negative integers will only start to appear after ~70 years of usage. However, be careful if you wish to [sort by ID](#module-sorting-by-id).

  If you don't like the formats, it's really easy to change them! The Elixir format especially, which can be changed at any time.

  The supported formats are:

  #{@format_docs}

  ### Elixir format caveats

  Some caveats apply to the `:ex_format` options.

  > #### Don't use raw integers with JS clients {: .warning}
  >
  > Encode `:signed` and `:unsigned` as strings.

  While JSON does not impose a precision limit on numbers, JavaScript can't deal with >= 2^53 numbers. That means the first 11 nonce bits can't be used, so the first 11 timestamp bits can't be used, which leaves 33 timestamp bits, which will run out after exactly 24 days, so let's say immediately. If you want to use integers, convert them to strings.

  > #### `ex_format: :signed` and `:unsigned` disable encoded binary parsing {: .info}
  >
  > If you use an integer format as `:ex_format`, casting and dumping hex-encoded, url64-encoded, hex32-encoded and raw formats will be disabled. On the other hand, parsing numeric strings ("123") will be supported.

  That's because we can't disambiguate some binaries that are valid hex, hex32, url64 and raw binaries and also valid numeric strings. An example is "12345678901", which is either integer 12_345_678_901 or url64-encoded `<<215, 109, 248, 231, 174, 252, 247, 77>>` (a.k.a. quite a different number).

  By treating all incoming binaries as either a valid numeric string or invalid when using an integer Elixir format, this ambiguity is resolved at the cost of some flexibility. Note that `to_format/3` only supports numeric strings with option `:parse_int`.

  > #### `ex_format: :hex`, `:hex32`, `:url64` and `:raw` disable numeric string parsing {: .info}
  >
  > If you use hex-encoded, hex32-encoded, url64-encoded or raw binary as `:ex_format`, parsing numeric strings will be disabled. On the other hand, parsing those binary formats is enabled.

  ### Sorting by ID

  The various formats have different sorting behaviors for the same underlying value, which becomes especially problematic with values equivalent to negative integers. Here are the same set of values in ascending sort order for each format:

      # unsigned ints (0, 1, signed-max, unsigned-max)
      [0, 1, 9223372036854775807, 18446744073709551615]

      # raw (binary comparison, same order as unsigned)
      [<<0::64>>, <<1::64>>, <<127, 255, 255, 255, 255, 255, 255, 255>>, <<255, 255, 255, 255, 255, 255, 255, 255>>]

      # hex (lexicographic string comparison, same order as unsigned)
      ["0000000000000000", "0000000000000001", "8000000000000000", "ffffffffffffffff"]

      # hex32 (lexicographic string comparison, same order as unsigned)
      ["0000000000000", "0000000000002", "FVVVVVVVVVVVU", "VVVVVVVVVVVVU"]

      # url64 (lexicographic but with different alphabet ordering, resulting in [0, 1, *unsigned-max*, signed-max])
      ["AAAAAAAAAAA", "AAAAAAAAAAE", "__________8", "f_________8"]

      # signed ints (natural signed integer order where unsigned-max is equivalent to signed-min)
      [-9223372036854775808, 0, 1, 9223372036854775807]

  If you want to rely on Once IDs for chronological sorting (especially with sortable nonces), choose formats that preserve unsigned integer ordering. This means using `:unsigned`, `:raw`, `:hex` or `hex32`.

  Avoid `:url64` for sorting; its alphabet wasn't designed with lexicographic ordering in mind, making it unsuitable. Signed integers only preserve the order in their positive range.

  #### Database considerations
  - PostgreSQL: Uses signed bigint with no native unsigned type. An "ORDER BY id" query will produce unexpected results when Once IDs become negative (~70 years after epoch). Consider using `:raw` format (stored as bytea) for correct sorting throughout the full range, combined with `:unsigned` or `:hex` format in your application. Since PG's raw bytes will often be rendered as hex, using hex in Elixir will simplify value comparison.
  - MySQL: Supports unsigned bigint, so `:unsigned` format works perfectly for sorting.

  ## On local uniqueness

  By locally unique, we mean unique within your domain or application. UUIDs are globally unique across domains, servers and applications. A Once is not, because 64 bits is not enough to achieve that. It is enough for local uniqueness however: you can generate 8 million IDs per second on 512 machines in parallel for 140 years straight before you run out of bits, by which time your great-grandchildren will deal with the problem. Even higher burst rates are possible and you can use separate `NoNoncense` instanses for every table if you wish.

  ## Encrypted IDs

  By default, IDs are generated using a machine init timestamp, machine ID and counter (although they should be considered to be opague). This means they leak a little information and are somewhat predictable. If that is unacceptable, you can use encrypted IDs. Note that encrypted IDs will cost you the data locality, decrease index performance a little and are slightly slower to generate. In order to use encrypted IDs:
  - Set [option](#module-options) `nonce_type: :encrypted`
  - initialize `NoNoncense` with option `base_key: <some 32-byte secret binary>`
  - (optional) change the encryption algorithm using option `:cipher64` from the default `:blowfish` to `:speck` (you will need optional dependency SpeckEx) or `:des3` (not recommended, it is the 0.x default but it is relatively slow)

  To learn more about nonce encryption and the available ciphers, be sure to take a look at the [NoNoncense docs](https://hexdocs.pm/no_noncense/NoNoncense.html#module-nonce-encryption).
  """
  require Logger
  use Ecto.ParameterizedType
  import Once.Shared

  @typedoc """
  Formats in which a `Once` can be rendered.
  They are all equivalent and can be transformed to one another.

  #{@format_docs}
  """
  @type format :: :url64 | :raw | :signed | :unsigned | :hex | :hex32

  @typedoc """
  The way in which the underlying 64-bits nonce is generated.

  See `NoNoncense` for details.
  """
  @type nonce_type :: :counter | :encrypted | :sortable

  @typedoc """
  Options to initialize `Once`.

  #{@options_docs}
  """
  @type init_opt ::
          {:no_noncense, module()}
          | {:ex_format, format()}
          | {:db_format, format()}
          | {:nonce_type, nonce_type()}

  @default_opts %{
    no_noncense: __MODULE__,
    ex_format: :url64,
    db_format: :signed,
    nonce_type: :counter
  }

  @int_formats [:signed, :unsigned]
  @encoded_formats [:url64, :hex, :hex32]
  @formats [:raw] ++ @int_formats ++ @encoded_formats

  #######################
  # Type implementation #
  #######################

  @impl true
  def type(%{db_format: :raw}), do: :binary
  def type(%{db_format: format}) when format in @encoded_formats, do: :string
  def type(%{db_format: format}) when format in @int_formats, do: :integer

  @impl true
  @spec init([init_opt()]) :: map()
  def init(opts \\ []) do
    opts = Enum.into(opts, @default_opts)

    if not is_atom(opts.no_noncense) do
      raise ArgumentError, "option :no_noncense is invalid: #{inspect(opts.no_noncense)}"
    end

    if opts.ex_format not in @formats do
      raise ArgumentError, "option :ex_format is invalid: #{inspect(opts.ex_format)}"
    end

    if opts.db_format not in @formats do
      raise ArgumentError, "option :db_format is invalid: #{inspect(opts.db_format)}"
    end

    if opts.nonce_type not in [:counter, :encrypted, :sortable] do
      raise ArgumentError, "option :nonce_type is invalid: #{inspect(opts.nonce_type)}"
    end

    if is_map_key(opts, :encrypt?) do
      raise ArgumentError, "option :encrypt? is deprecated"
    end

    if is_map_key(opts, :get_key) do
      raise ArgumentError, "option :get_key is deprecated"
    end

    opts
  end

  @impl true
  def cast(nil, _), do: {:ok, nil}

  def cast(value, %{ex_format: ex_format}) when ex_format in @int_formats and is_binary(value) do
    case parse_int(value) do
      :error = error -> error
      int -> convert_int(int, ex_format)
    end
  end

  def cast(value, params), do: to_format(value, params.ex_format)

  @impl true
  def load(nil, _, _), do: {:ok, nil}
  def load(value, _, params), do: to_format(value, params.ex_format)

  @impl true
  def dump(nil, _, _), do: {:ok, nil}

  def dump(value, _, params) when params.ex_format in @int_formats and is_binary(value) do
    case parse_int(value) do
      :error = error -> error
      int -> maybe_convert(:int, int, params.db_format)
    end
  end

  def dump(value, _, params), do: to_format(value, params.db_format)

  @impl true
  def autogenerate(params = %{nonce_type: nonce_type}) do
    case nonce_type do
      :counter -> NoNoncense.nonce(params.no_noncense, 64)
      :sortable -> NoNoncense.sortable_nonce(params.no_noncense, 64)
      :encrypted -> NoNoncense.encrypted_nonce(params.no_noncense, 64)
    end
    |> from_raw(params.ex_format)
  end

  #####################
  # Mapping functions #
  #####################

  @to_format_opts_docs """
  - `:parse_int` parse numeric strings like `"123"`. Will give unexpected results with all-int hex/url64 inputs.
  """

  @doc false
  def to_format_opts_docs, do: @to_format_opts_docs

  @typedoc """
  Options for `to_format/3`

  #{@to_format_opts_docs}
  """
  @type to_format_opt :: {:parse_int, boolean()}

  @doc """
  Transform the different forms that a `Once` can take to one another.
  The formats can be found in `t:format/0`.

  ## Options

  #{@to_format_opts_docs}

  ## Examples

      iex> Once.to_format("4BCDEFghijk", :raw)
      {:ok, <<224, 16, 131, 16, 88, 33, 138, 57>>}
      iex> Once.to_format(<<224, 16, 131, 16, 88, 33, 138, 57>>, :signed)
      {:ok, -2301195303365014983}
      iex> Once.to_format(-2301195303365014983, :unsigned)
      {:ok, 16145548770344536633}
      iex> Once.to_format(16145548770344536633, :hex)
      {:ok, "e010831058218a39"}
      iex> Once.to_format("e010831058218a39", :hex32)
      {:ok, "s088642o4653i"}
      iex> Once.to_format("s088642o4653i", :url64)
      {:ok, "4BCDEFghijk"}

      iex> Once.to_format(-1, :url64)
      {:ok, "__________8"}
      iex> Once.to_format("__________8", :raw)
      {:ok, <<255, 255, 255, 255, 255, 255, 255, 255>>}
      iex> Once.to_format(<<255, 255, 255, 255, 255, 255, 255, 255>>, :unsigned)
      {:ok, 18446744073709551615}
      iex> Once.to_format(18446744073709551615, :hex)
      {:ok, "ffffffffffffffff"}
      iex> Once.to_format("ffffffffffffffff", :hex32)
      {:ok, "vvvvvvvvvvvvu"}
      iex> Once.to_format("ffffffffffffffff", :signed)
      {:ok, -1}

      iex> Once.to_format(Integer.pow(2, 64), :unsigned)
      :error

      # numeric strings are supported using `:parse_int`
      iex> Once.to_format("-2301195303365014983", :unsigned, parse_int: true)
      {:ok, 16145548770344536633}
      iex> Once.to_format("16145548770344536633", :hex, parse_int: true)
      {:ok, "e010831058218a39"}
  """
  @spec to_format(binary() | integer(), format(), [to_format_opt()]) ::
          {:ok, binary() | integer()} | :error
  def to_format(value, format, opts \\ []) do
    value = maybe_parse_int(value, opts[:parse_int])
    format_in = identify_format(value)
    maybe_convert(format_in, value, format)
  end

  @doc """
  Same as `to_format/3` but raises on error.

      iex> -200
      ...> |> Once.to_format!(:url64)
      ...> |> Once.to_format!(:raw)
      ...> |> Once.to_format!(:hex32)
      ...> |> Once.to_format!(:unsigned)
      ...> |> Once.to_format!(:hex)
      ...> |> Once.to_format!(:signed)
      -200

      iex> Once.to_format!(Integer.pow(2, 64), :unsigned)
      ** (ArgumentError) value could not be parsed: 18446744073709551616
  """
  @spec to_format!(binary() | integer(), format(), [to_format_opt()]) :: binary() | integer()
  def to_format!(value, format, opts \\ []) do
    to_format(value, format, opts) |> do_to_format!(value)
  end

  ###########
  # Private #
  ###########

  @compile {:inline, identify_format: 1, to_raw: 2}

  @bigint_size Integer.pow(2, 64)
  @signed_min -Integer.pow(2, 63)
  @signed_max Integer.pow(2, 63) - 1
  @unsigned_min 0
  @unsigned_max @bigint_size - 1

  # convert a signed to unsigned int and back
  defp convert_int(int, format)
  defp convert_int(int, _) when int < @signed_min, do: :error
  defp convert_int(int, _) when int > @unsigned_max, do: :error

  defp convert_int(int, :signed) when int > @signed_max, do: {:ok, int - @bigint_size}
  defp convert_int(int, :unsigned) when int < @unsigned_min, do: {:ok, int + @bigint_size}

  defp convert_int(int, _), do: {:ok, int}

  # identify the value's format, where ints are grouped together for convert_int/2 to deal with
  defp identify_format(value)
  defp identify_format(<<_::88>>), do: :url64
  defp identify_format(<<_::64>>), do: :raw
  defp identify_format(<<_::128>>), do: :hex
  defp identify_format(<<_::104>>), do: :hex32
  defp identify_format(int) when is_integer(int), do: :int
  defp identify_format(_), do: :error

  # convert (or verify) a value from one format to another
  defp maybe_convert(format_in, value, format_out)
  defp maybe_convert(:raw, value, :raw), do: {:ok, value}

  defp maybe_convert(:url64, value, :url64) do
    if valid64?(value), do: {:ok, value}, else: :error
  end

  defp maybe_convert(:hex, value, :hex) do
    if valid16?(value), do: {:ok, value}, else: :error
  end

  defp maybe_convert(:hex32, value, :hex32) do
    if valid32?(value), do: {:ok, value}, else: :error
  end

  defp maybe_convert(:int, value, int_format) when int_format in @int_formats,
    do: convert_int(value, int_format)

  defp maybe_convert(format_in, value, format_out) do
    value
    |> to_raw(format_in)
    |> case do
      {:ok, raw} -> {:ok, from_raw(raw, format_out)}
      _ -> :error
    end
  end

  # convert a value to raw format
  defp to_raw(value, from_format)
  defp to_raw(value, :raw), do: {:ok, value}
  defp to_raw(value, :url64), do: decode64(value)
  defp to_raw(value, :hex), do: decode16(value)
  defp to_raw(value, :hex32), do: decode32(value)

  defp to_raw(value, :int) do
    case convert_int(value, :signed) do
      {:ok, int} -> {:ok, <<int::signed-64>>}
      _ -> :error
    end
  end

  defp to_raw(_, :error), do: :error

  defp from_raw(raw, to_format)
  defp from_raw(raw, :raw), do: raw
  defp from_raw(raw, :url64), do: encode64(raw)
  defp from_raw(raw, :hex), do: encode16(raw)
  defp from_raw(raw, :hex32), do: encode32(raw)
  defp from_raw(<<int::signed-64>>, :signed), do: int
  defp from_raw(<<int::unsigned-64>>, :unsigned), do: int

  defp maybe_parse_int(value, true) when is_binary(value), do: parse_int(value)
  defp maybe_parse_int(value, _), do: value

  defp parse_int(value) do
    try do
      String.to_integer(value)
    rescue
      _ -> :error
    end
  end
end