// CID -- a Content Identifier, the content hash half of every strong ref, and
// the name of every blob.
//
// https://github.com/multiformats/cid
//
// This parses a CID and reads its header; it does not COMPUTE one. Computing
// requires DAG-CBOR encoding and SHA-256, which this library deliberately does
// not carry -- see "Not included" in the README. Parsing needs neither, and
// skipping it would make `Cid` a rubber stamp over any string at all, on the 56
// Lexicon fields that declare `format: cid`.
//
// Two spellings exist in the wild and both must be read:
//
//   CIDv1, `b` + base32 -- everything atproto writes. The `b` is a multibase
//       prefix; the decoded bytes are four varints (version, codec, hash
//       function, digest length) followed by the digest.
//   CIDv0, a bare base58btc `Qm...` -- IPFS's original format, dag-pb and
//       SHA-256 by definition, with no version or codec bytes to read. Legacy,
//       but it appears in old records.
//
// Base58 is not decoded. A CIDv0 is always exactly 46 characters and always
// means the same three things, so checking the alphabet and the length
// establishes as much as decoding would.

///|
/// Multicodec content types, the ones atproto uses.
pub(all) enum CidCodec {
  /// `0x55`. Blobs: the bytes are the content, uninterpreted.
  Raw
  /// `0x71`. Records and commits: the bytes are DAG-CBOR.
  DagCbor
  /// `0x70`. CIDv0 only.
  DagPb
  /// Anything else, kept so an unrecognised codec round-trips rather than
  /// failing to parse.
  Other(Int)
} derive(Eq, Debug)

///|
pub fn CidCodec::code(self : Self) -> Int {
  match self {
    Raw => 0x55
    DagCbor => 0x71
    DagPb => 0x70
    Other(code) => code
  }
}

///|
fn CidCodec::of_code(code : Int) -> CidCodec {
  match code {
    0x55 => Raw
    0x71 => DagCbor
    0x70 => DagPb
    _ => Other(code)
  }
}

///|
/// A parsed CID, holding the string it came from.
///
/// As everywhere else in this package the original bytes are what
/// re-serializes, which for a CID matters twice over: it is a content hash, so
/// a re-encoding that differs is a reference to nothing.
pub struct Cid {
  text : String
  version : Int
  codec : CidCodec
  /// The multihash function code. `0x12` is SHA-256, which is all atproto uses.
  hash_code : Int
  hash_length : Int
} derive(Eq, Debug)

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

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

///|
pub fn Cid::version(self : Self) -> Int {
  self.version
}

///|
pub fn Cid::codec(self : Self) -> CidCodec {
  self.codec
}

///|
pub fn Cid::hash_code(self : Self) -> Int {
  self.hash_code
}

///|
/// Trusts the caller. The header fields are reported as a CIDv1 SHA-256
/// DAG-CBOR CID, which is what atproto writes -- so do not read them off a
/// value you built this way.
pub fn Cid::unchecked(text : String) -> Cid {
  { text, version: 1, codec: DagCbor, hash_code: 0x12, hash_length: 32 }
}

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

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

  guard text.length() > 0 else { raise bad("CID can not be empty") }
  if text.has_prefix("Qm") {
    // CIDv0: base58btc, no multibase prefix, dag-pb and SHA-256 by definition.
    guard text.length() == 46 else { raise bad("CIDv0 must be 46 characters") }
    guard all_chars(text, is_base58btc_char) else {
      raise bad("Disallowed characters in CIDv0 (base58btc)")
    }
    return { text, version: 0, codec: DagPb, hash_code: 0x12, hash_length: 32 }
  }
  guard text.has_prefix("b") else {
    raise bad("CID must be base32 (\"b\" prefix) or a CIDv0 (\"Qm\" prefix)")
  }
  guard decode_base32(text[1:].to_owned()) is Some(bytes) else {
    raise bad("Disallowed characters in CID (base32)")
  }
  let cursor = { bytes, index: 0 }
  guard read_varint(cursor) is Some(version) else {
    raise bad("CID is truncated")
  }
  guard version == 1 else {
    raise bad("CID version must be 1 (got \{version})")
  }
  guard read_varint(cursor) is Some(codec) else {
    raise bad("CID is truncated")
  }
  guard read_varint(cursor) is Some(hash_code) else {
    raise bad("CID is truncated")
  }
  guard read_varint(cursor) is Some(hash_length) else {
    raise bad("CID is truncated")
  }
  // The digest length is declared, so a CID that lies about it is malformed
  // rather than merely unusual -- and this is the check that rejects a random
  // base32 string that happened to decode.
  guard cursor.bytes.length() - cursor.index == hash_length else {
    raise bad("CID digest length does not match its multihash header")
  }
  { text, version, codec: CidCodec::of_code(codec), hash_code, hash_length }
}

///|
/// RFC 4648 base32, lower case, no padding -- multibase `b`, whose alphabet is
/// `abcdefghijklmnopqrstuvwxyz234567`. Computed from the two contiguous ASCII
/// ranges rather than searched, as in `s32_digit`.
fn base32_digit(unit : UInt16) -> Int? {
  let i = unit.to_int()
  if i >= 'a'.to_int() && i <= 'z'.to_int() {
    Some(i - 'a'.to_int())
  } else if i >= '2'.to_int() && i <= '7'.to_int() {
    Some(i - '2'.to_int() + 26)
  } else {
    None
  }
}

///|
fn decode_base32(text : String) -> Array[Int]? {
  let out = []
  let mut buffer = 0
  let mut bits = 0
  for i = 0; i < text.length(); i = i + 1 {
    guard base32_digit(text[i]) is Some(digit) else { return None }
    buffer = buffer * 32 + digit
    bits = bits + 5
    if bits >= 8 {
      bits = bits - 8
      out.push((buffer >> bits) & 0xFF)
      buffer = buffer & ((1 << bits) - 1)
    }
  }
  Some(out)
}

///|
priv struct Cursor {
  bytes : Array[Int]
  mut index : Int
}

///|
/// An unsigned LEB128 varint, as multiformats uses. Bounded at five bytes,
/// which is more than any multicodec in use needs and keeps the result inside
/// an `Int`.
fn read_varint(cursor : Cursor) -> Int? {
  let mut result = 0
  let mut shift = 0
  while cursor.index < cursor.bytes.length() {
    let byte = cursor.bytes[cursor.index]
    cursor.index = cursor.index + 1
    result = result | ((byte & 0x7F) << shift)
    if (byte & 0x80) == 0 {
      return Some(result)
    }
    shift = shift + 7
    if shift > 28 {
      return None
    }
  }
  None
}

///|
/// Bitcoin's base58 alphabet: no `0`, `O`, `I` or `l`.
fn is_base58btc_char(c : Char) -> Bool {
  is_ascii_alnum(c) && c != '0' && c != 'O' && c != 'I' && c != 'l'
}