git.squeep.com Git - akkoma/blob - lib/pleroma/flake_id.ex

   1 # Pleroma: A lightweight social networking server
   2 # Copyright © 2017-2019 Pleroma Authors <https://pleroma.social/>
   3 # SPDX-License-Identifier: AGPL-3.0-only
   4
   5 defmodule Pleroma.FlakeId do
   6   @moduledoc """
   7   Flake is a decentralized, k-ordered id generation service.
   8
   9   Adapted from:
  10
  11   * [flaky](https://github.com/nirvana/flaky), released under the terms of the Truly Free License,
  12   * [Flake](https://github.com/boundary/flake), Copyright 2012, Boundary, Apache License, Version 2.0
  13   """
  14
  15   @type t :: binary
  16
  17   @behaviour Ecto.Type
  18   use GenServer
  19   require Logger
  20   alias __MODULE__
  21   import Kernel, except: [to_string: 1]
  22
  23   defstruct node: nil, time: 0, sq: 0
  24
  25   @doc "Converts a binary Flake to a String"
  26   def to_string(<<0::integer-size(64), id::integer-size(64)>>) do
  27     Kernel.to_string(id)
  28   end
  29
  30   def to_string(<<_::integer-size(64), _::integer-size(48), _::integer-size(16)>> = flake) do
  31     encode_base62(flake)
  32   end
  33
  34   def to_string(s), do: s
  35
  36   def from_string(int) when is_integer(int) do
  37     from_string(Kernel.to_string(int))
  38   end
  39
  40   for i <- [-1, 0] do
  41     def from_string(unquote(i)), do: <<0::integer-size(128)>>
  42     def from_string(unquote(Kernel.to_string(i))), do: <<0::integer-size(128)>>
  43   end
  44
  45   def from_string(<<_::integer-size(128)>> = flake), do: flake
  46
  47   def from_string(string) when is_binary(string) and byte_size(string) < 18 do
  48     case Integer.parse(string) do
  49       {id, ""} -> <<0::integer-size(64), id::integer-size(64)>>
  50       _ -> nil
  51     end
  52   end
  53
  54   def from_string(string) do
  55     string |> decode_base62 |> from_integer
  56   end
  57
  58   def to_integer(<<integer::integer-size(128)>>), do: integer
  59
  60   def from_integer(integer) do
  61     <<_time::integer-size(64), _node::integer-size(48), _seq::integer-size(16)>> =
  62       <<integer::integer-size(128)>>
  63   end
  64
  65   @doc "Generates a Flake"
  66   @spec get :: binary
  67   def get, do: to_string(:gen_server.call(:flake, :get))
  68
  69   # checks that ID is is valid FlakeID
  70   #
  71   @spec is_flake_id?(String.t()) :: boolean
  72   def is_flake_id?(id), do: is_flake_id?(String.to_charlist(id), true)
  73   defp is_flake_id?([c | cs], true) when c >= ?0 and c <= ?9, do: is_flake_id?(cs, true)
  74   defp is_flake_id?([c | cs], true) when c >= ?A and c <= ?Z, do: is_flake_id?(cs, true)
  75   defp is_flake_id?([c | cs], true) when c >= ?a and c <= ?z, do: is_flake_id?(cs, true)
  76   defp is_flake_id?([], true), do: true
  77   defp is_flake_id?(_, _), do: false
  78
  79   # -- Ecto.Type API
  80   @impl Ecto.Type
  81   def type, do: :uuid
  82
  83   @impl Ecto.Type
  84   def cast(value) do
  85     {:ok, FlakeId.to_string(value)}
  86   end
  87
  88   @impl Ecto.Type
  89   def load(value) do
  90     {:ok, FlakeId.to_string(value)}
  91   end
  92
  93   @impl Ecto.Type
  94   def dump(value) do
  95     {:ok, FlakeId.from_string(value)}
  96   end
  97
  98   def autogenerate, do: get()
  99
 100   # -- GenServer API
 101   def start_link do
 102     :gen_server.start_link({:local, :flake}, __MODULE__, [], [])
 103   end
 104
 105   @impl GenServer
 106   def init([]) do
 107     {:ok, %FlakeId{node: worker_id(), time: time()}}
 108   end
 109
 110   @impl GenServer
 111   def handle_call(:get, _from, state) do
 112     {flake, new_state} = get(time(), state)
 113     {:reply, flake, new_state}
 114   end
 115
 116   # Matches when the calling time is the same as the state time. Incr. sq
 117   defp get(time, %FlakeId{time: time, node: node, sq: seq}) do
 118     new_state = %FlakeId{time: time, node: node, sq: seq + 1}
 119     {gen_flake(new_state), new_state}
 120   end
 121
 122   # Matches when the times are different, reset sq
 123   defp get(newtime, %FlakeId{time: time, node: node}) when newtime > time do
 124     new_state = %FlakeId{time: newtime, node: node, sq: 0}
 125     {gen_flake(new_state), new_state}
 126   end
 127
 128   # Error when clock is running backwards
 129   defp get(newtime, %FlakeId{time: time}) when newtime < time do
 130     {:error, :clock_running_backwards}
 131   end
 132
 133   defp gen_flake(%FlakeId{time: time, node: node, sq: seq}) do
 134     <<time::integer-size(64), node::integer-size(48), seq::integer-size(16)>>
 135   end
 136
 137   defp nthchar_base62(n) when n <= 9, do: ?0 + n
 138   defp nthchar_base62(n) when n <= 35, do: ?A + n - 10
 139   defp nthchar_base62(n), do: ?a + n - 36
 140
 141   defp encode_base62(<<integer::integer-size(128)>>) do
 142     integer
 143     |> encode_base62([])
 144     |> List.to_string()
 145   end
 146
 147   defp encode_base62(int, acc) when int < 0, do: encode_base62(-int, acc)
 148   defp encode_base62(int, []) when int == 0, do: '0'
 149   defp encode_base62(int, acc) when int == 0, do: acc
 150
 151   defp encode_base62(int, acc) do
 152     r = rem(int, 62)
 153     id = div(int, 62)
 154     acc = [nthchar_base62(r) | acc]
 155     encode_base62(id, acc)
 156   end
 157
 158   defp decode_base62(s) do
 159     decode_base62(String.to_charlist(s), 0)
 160   end
 161
 162   defp decode_base62([c | cs], acc) when c >= ?0 and c <= ?9,
 163     do: decode_base62(cs, 62 * acc + (c - ?0))
 164
 165   defp decode_base62([c | cs], acc) when c >= ?A and c <= ?Z,
 166     do: decode_base62(cs, 62 * acc + (c - ?A + 10))
 167
 168   defp decode_base62([c | cs], acc) when c >= ?a and c <= ?z,
 169     do: decode_base62(cs, 62 * acc + (c - ?a + 36))
 170
 171   defp decode_base62([], acc), do: acc
 172
 173   defp time do
 174     {mega_seconds, seconds, micro_seconds} = :erlang.timestamp()
 175     1_000_000_000 * mega_seconds + seconds * 1000 + :erlang.trunc(micro_seconds / 1000)
 176   end
 177
 178   defp worker_id do
 179     <<worker::integer-size(48)>> = :crypto.strong_rand_bytes(6)
 180     worker
 181   end
 182 end