// TID -- Timestamp Identifier. The record key most records use, and the
// revision number on every repository commit.
//
// https://atproto.com/specs/tid
// Ported from @atproto/syntax packages/syntax/src/tid.ts, and from
// @atproto/common-web's tid.ts for the generator.
//
// A TID is a 64-bit integer in a base-32 alphabet chosen so that LEXICOGRAPHIC
// ORDER IS CHRONOLOGICAL ORDER. That is the entire point of the format, and it
// is why `Tid` compares as its string: sorting record keys sorts records by
// creation time, with no parsing and no clock.
//
//   bit  63     : always zero, which is why the first character is limited to
//                 the low half of the alphabet
//   bits 62..10 : microseconds since the Unix epoch (53 bits -- the range a
//                 JavaScript number can hold exactly, which is why it is 53)
//   bits  9..0  : a "clock identifier", chosen once at random per process, so
//                 two writers who share a microsecond still produce different
//                 keys
//
// The legacy dashed spelling (`3jzf-cij-pj2z-2a`) is NOT accepted. The
// reference implementation's own interop corpus lists it as invalid, and
// silently accepting it would let a dashed key reach a server that rejects it.

///|
const TID_LENGTH : Int = 13

///|
/// Base 32, "sortable" ordering: the digits are in ASCII order, so comparing
/// two encoded values as strings compares the values.
const S32_ALPHABET : String = "234567abcdefghijklmnopqrstuvwxyz"

///|
/// The encoding of zero, and therefore the left-padding character.
const S32_ZERO : Char = '2'

///|
/// A syntactically valid TID.
///
/// `Compare` is derived from the string, which is correct precisely because of
/// the sortable alphabet -- see the note above before changing it.
pub struct Tid(String) derive(Eq, Compare, Debug)

///|
pub impl Show for Tid with fn output(self, logger) {
  logger.write_string(self.0)
}

///|
pub fn Tid::to_string(self : Self) -> String {
  self.0
}

///|
pub fn Tid::unchecked(tid : String) -> Tid {
  Tid(tid)
}

///|
pub fn Tid::is_valid(tid : String) -> Bool {
  try {
    Tid::parse(tid) |> ignore
    true
  } catch {
    _ => false
  }
}

///|
pub fn Tid::parse(tid : String) -> Tid raise SyntaxError {
  fn bad(reason : String) -> SyntaxError {
    SyntaxError(kind=Tid, input=tid, reason~)
  }

  guard tid.length() == TID_LENGTH else {
    raise bad("TID must be \{TID_LENGTH} characters")
  }
  // The first character carries the always-zero high bit, so it is restricted
  // to the first sixteen digits of the alphabet: `zzzz...` and `kjzf...` are
  // rejected here and nowhere else.
  guard s32_digit(tid[0]) is Some(first) && first < 16 else {
    raise bad("TID syntax not valid (regex)")
  }
  for i = 1; i < TID_LENGTH; i = i + 1 {
    guard s32_digit(tid[i]) is Some(_) else {
      raise bad("TID syntax not valid (regex)")
    }
  }
  Tid(tid)
}

///|
/// Microseconds since the Unix epoch.
pub fn Tid::timestamp(self : Self) -> Int64 {
  s32_decode(self.0, 0, 11)
}

///|
/// The writer's random per-process identifier. Carries no meaning beyond
/// breaking ties between two TIDs minted in the same microsecond.
pub fn Tid::clock_id(self : Self) -> Int {
  s32_decode(self.0, 11, 13).to_int()
}

///|
/// Builds a TID from an explicit time. The clock is an argument rather than a
/// call to `now()` so that this package needs no platform clock and stays
/// buildable on every backend -- the same reason `@ratectl` in the sibling
/// slack library takes `now : Int64`.
///
/// `micros` is truncated to 53 bits and `clock_id` to 10, which is what makes
/// this total: there is no input for which it produces an invalid TID.
pub fn Tid::from_time(micros : Int64, clock_id : Int) -> Tid {
  let t = micros & 0x001FFFFFFFFFFFFFL
  let c = clock_id.to_int64() & 0x3FFL
  Tid(s32_encode(t, 11) + s32_encode(c, 2))
}

///|
/// Mints TIDs that increase even when the clock does not.
///
/// Two calls in the same microsecond -- or across a clock that has gone
/// backwards -- must not produce the same key or a decreasing one, because a
/// repository's records are ordered by it. So the ticker keeps the last value
/// it issued and steps past it, which costs a microsecond of drift and buys
/// monotonicity.
pub struct Ticker {
  clock_id : Int
  mut last : Int64
}

///|
/// `clock_id` should be random per process; this package will not draw it,
/// because a random number needs a source and a source needs a platform.
pub fn Ticker::new(clock_id : Int) -> Ticker {
  { clock_id, last: 0L }
}

///|
pub fn Ticker::next(self : Self, now_micros : Int64) -> Tid {
  let t = if now_micros > self.last { now_micros } else { self.last + 1L }
  self.last = t
  Tid::from_time(t, self.clock_id)
}

///|
/// The alphabet as characters, for encoding. Derived from the string above so
/// the two cannot drift.
let s32_digits : Array[Char] = S32_ALPHABET.iter().collect()

///|
/// The digit value of a base-32 character, or `None` if it is not one.
///
/// Computed from the two contiguous ASCII ranges rather than by searching the
/// alphabet, which also makes the sortability visible: `2`-`7` are ASCII 0x32
/// to 0x37 and `a`-`z` are 0x61 to 0x7A, both ascending and in that order, so
/// ASCII order over these characters IS digit order.
fn s32_digit(unit : UInt16) -> Int? {
  let i = unit.to_int()
  if i >= '2'.to_int() && i <= '7'.to_int() {
    Some(i - '2'.to_int())
  } else if i >= 'a'.to_int() && i <= 'z'.to_int() {
    Some(i - 'a'.to_int() + 6)
  } else {
    None
  }
}

///|
/// Big-endian, left-padded to `width` digits with the alphabet's zero.
fn s32_encode(value : Int64, width : Int) -> String {
  let digits = Array::make(width, S32_ZERO)
  let mut v = value
  for i = width - 1; i >= 0; i = i - 1 {
    digits[i] = s32_digits[(v % 32L).to_int()]
    v = v / 32L
  }
  String::from_array(digits)
}

///|
/// Decodes `s[start:end]`. Only ever called on a string `parse` has already
/// checked, so an unknown digit cannot occur and contributes zero.
fn s32_decode(s : String, start : Int, end : Int) -> Int64 {
  let mut acc = 0L
  for i = start; i < end; i = i + 1 {
    let d = match s32_digit(s[i]) {
      Some(d) => d
      None => 0
    }
    acc = acc * 32L + d.to_int64()
  }
  acc
}