///|
/// The functions on values of Annex A.3: equality, membership, elements,
/// iteration, subscripting and the dictionary builders.
///
/// Equality is PARTIAL, and the order in which elements are compared is
/// therefore observable: `eq` short-circuits at the first pair that decides
/// the answer, so an undefined comparison later in a sequence does not make
/// the whole comparison undefined. `[1, "a"] == [1, 3]` is stuck and
/// `[1, "a"] == [2, 3]` is False, and the difference is deliberate.
///
/// Every function that can be undefined returns a `Bool?` or an `Outcome`;
/// `None` and `Stuck` mean "no rule", not "false".
pub fn eq(a : Value, b : Value) -> Bool? {
  match (a, b) {
    // `None` compares with anything.
    (None, None) => Some(true)
    (None, _) | (_, None) => Some(false)
    (Bool(x), Bool(y)) => Some(x == y)
    (Int(x), Int(y)) => Some(x == y)
    (Float(x), Float(y)) =>
      // `nan` against `nan` has no rule; the `==` OPERATOR has one, which is
      // why `nan == nan` is False and `[nan] == [nan]` is stuck.
      if x.is_nan() && y.is_nan() {
        Option::None
      } else {
        Some(x == y)
      }
    // An integer and a float compare numerically and exactly, as they do in
    // Python and as the pattern checker's subsumption already assumes.
    (Int(x), Float(y)) => int_float_eq(x, y)
    (Float(x), Int(y)) => int_float_eq(y, x)
    (Str(x), Str(y)) => Some(x == y)
    (List(xs), List(ys)) | (Tuple(xs), Tuple(ys)) => eq_elems(xs, ys)
    (Dict(x), Dict(y)) => {
      if x.length() != y.length() {
        return Some(false)
      }
      // Compared in the entry order of the LEFT operand.
      let left : Array[Value] = []
      let right : Array[Value] = []
      for e in x {
        match lookup(y, e.0) {
          Option::None => return Some(false)
          Some(v) => {
            left.push(e.1)
            right.push(v)
          }
        }
      }
      eq_elems(left, right)
    }
    (Obj(ca, ra), Obj(cb, rb)) => {
      if ca.name != cb.name {
        return Some(false)
      }
      let left : Array[Value] = []
      let right : Array[Value] = []
      for x in ca.fields() {
        match (ra.get(x), rb.get(x)) {
          (Some(u), Some(v)) => {
            left.push(u)
            right.push(v)
          }
          _ => return Option::None
        }
      }
      eq_elems(left, right)
    }
    _ => Option::None
  }
}

///|
fn int_float_eq(n : BigInt, d : Double) -> Bool? {
  if d.is_nan() {
    // A number against `nan`: different values, so False. Only `nan` against
    // `nan` has no rule.
    return Some(false)
  }
  match exact_integer(d) {
    Some(m) => Some(m == n)
    Option::None => Some(false)
  }
}

///|
/// The integer a double exactly equals, or `None` when it is not one.
///
/// Read off the bit pattern rather than through decimal text, so it is exact
/// at every magnitude: a double is `mantissa * 2^exponent`, and when it is
/// integral the shift below loses nothing.
pub fn exact_integer(d : Double) -> BigInt? {
  if d.is_nan() || d.is_inf() || d != d.floor() {
    return Option::None
  }
  let bits = d.reinterpret_as_uint64()
  let negative = bits >> 63 != 0UL
  let exponent = ((bits >> 52) & 0x7FFUL).to_int()
  let fraction = bits & 0xFFFFFFFFFFFFFUL
  let (mantissa, shift) = if exponent == 0 {
    (fraction, -1074)
  } else {
    (fraction | (1UL << 52), exponent - 1075)
  }
  let mut n = BigInt::from_uint64(mantissa)
  if shift > 0 {
    n = n << shift
  } else if shift < 0 {
    n = n >> -shift
  }
  Some(if negative { -n } else { n })
}

///|
fn lookup(entries : Array[(String, Value)], key : String) -> Value? {
  for e in entries {
    if e.0 == key {
      return Some(e.1)
    }
  }
  Option::None
}

///|
/// Elementwise equality, stopping at the first pair that decides it.
pub fn eq_elems(xs : Array[Value], ys : Array[Value]) -> Bool? {
  if xs.length() != ys.length() {
    return Some(false)
  }
  for i in 0.. return Some(false)
      Some(true) => ()
      Option::None => return Option::None
    }
  }
  Some(true)
}

///|
/// Whether `needle` is in `haystack`: an element of a list or tuple, a key of
/// a dictionary, a substring of a string.
pub fn contains(haystack : Value, needle : Value) -> Bool? {
  match haystack {
    List(xs) | Tuple(xs) => contains_elems(xs, needle)
    Dict(entries) =>
      match needle {
        Str(w) => Some(lookup(entries, w) is Some(_))
        _ => Option::None
      }
    Str(w) =>
      match needle {
        Str(sub) => Some(w.contains(sub))
        _ => Option::None
      }
    _ => Option::None
  }
}

///|
pub fn contains_elems(xs : Array[Value], needle : Value) -> Bool? {
  for x in xs {
    match eq(needle, x) {
      Some(true) => return Some(true)
      Some(false) => ()
      Option::None => return Option::None
    }
  }
  Some(false)
}

///|
/// The elements of a list, a tuple or a string. A string's elements are its
/// CODE POINTS, which is what Python iterates.
pub fn elems(v : Value) -> Array[Value]? {
  match v {
    List(xs) | Tuple(xs) => Some(xs)
    Str(s) => Some(s.to_array().map(fn(c) { Value::Str(c.to_string()) }))
    _ => Option::None
  }
}

///|
/// What a generator draws from a value: the KEYS of a dictionary, and
/// otherwise its elements.
pub fn iter(v : Value) -> Array[Value]? {
  match v {
    Dict(entries) => Some(entries.map(fn(e) { Value::Str(e.0) }))
    other => elems(other)
  }
}

///|
/// Subscripting: a dictionary by a string key, a sequence by an integer index
/// counting from the end when negative.
pub fn getitem(v : Value, key : Value) -> Outcome {
  match v {
    Dict(entries) =>
      match key {
        Str(w) =>
          match lookup(entries, w) {
            Some(found) => Val(found)
            Option::None => Aborts(KeyError)
          }
        // A dictionary subscripted by anything but a string is undefined --
        // not a KeyError.
        _ => Stuck("subscripting a dict with " + key.kind_name())
      }
    _ =>
      match elems(v) {
        Option::None => Aborts(TypeError)
        Some(xs) =>
          match key {
            Int(n) => {
              let len = BigInt::from_int(xs.length())
              let i = if n < 0N { n + len } else { n }
              if i < 0N || i >= len {
                Aborts(IndexError)
              } else {
                Val(xs[i.to_int()])
              }
            }
            _ => Aborts(TypeError)
          }
      }
  }
}

///|
/// `update(δ, w, v)`: the entries with `w` bound to `v`, in place if it was
/// already there and appended otherwise.
pub fn update(
  entries : Array[(String, Value)],
  key : String,
  v : Value,
) -> Array[(String, Value)] {
  let out : Array[(String, Value)] = []
  let mut replaced = false
  for e in entries {
    if e.0 == key {
      out.push((key, v))
      replaced = true
    } else {
      out.push(e)
    }
  }
  if !replaced {
    out.push((key, v))
  }
  out
}

///|
/// `entries(δ, δ')`: the left entries extended by the right ones in order.
pub fn entries(
  base : Array[(String, Value)],
  more : Array[(String, Value)],
) -> Array[(String, Value)] {
  let mut out = base
  for e in more {
    out = update(out, e.0, e.1)
  }
  out
}

// ---------------------------------------------------------------------------
// Slicing (#59), which a profile opens

///|
/// A slice's three parts, each absent unless the source wrote it.
///
/// A `Value` and not an `@ast.Slice`, because `lib/value` is where the rule
/// lives and an evaluator should hand it what it evaluated rather than what it
/// parsed. `None` is "the source left it out", which is not the same as `None`
/// the PurePy value: `xs[None:]` is a TypeError in Python and is one here.
pub(all) struct SliceBounds {
  lower : Value?
  upper : Value?
  step : Value?
}

///|
/// `xs[i:j:k]`, by CPython's own rule.
///
/// Slicing is total where indexing is partial: an index past the end is an
/// `IndexError` and a slice past the end is empty, which is why this cannot
/// borrow `getitem`'s arithmetic. The clamping below is `PySlice_AdjustIndices`
/// written out -- a negative bound counts from the end and then clamps, and
/// which end it clamps to depends on the sign of the step.
///
/// `k == 0` is a `ValueError` in Python. PurePy does not model `ValueError`,
/// so it is undefined here rather than pretending to be one of the seven
/// terminations the semantics has.
pub fn getslice(v : Value, bounds : SliceBounds) -> Outcome {
  let xs = match elems(v) {
    Some(xs) => xs
    None =>
      match v {
        Dict(_) => return Stuck("slicing a dict")
        _ => return Aborts(TypeError)
      }
  }
  let step = match bounds.step {
    None | Some(Value::None) => 1
    Some(Int(k)) =>
      if k == 0N {
        return Stuck("a slice with a step of zero")
      } else if k > 1000000000N {
        1000000000
      } else if k < -1000000000N {
        -1000000000
      } else {
        k.to_int()
      }
    Some(_) => return Aborts(TypeError)
  }
  let len = xs.length()
  let bound = fn(b : Value?, if_absent : Int) -> Int? {
    match b {
      None | Some(Value::None) => Some(if_absent)
      Some(Int(n)) => {
        // Clamp before narrowing: an index far outside the sequence is legal
        // in a slice and must not wrap when it stops being a BigInt.
        let big = BigInt::from_int(len)
        let i = if n < 0N { n + big } else { n }
        if i < 0N {
          Some(if step < 0 { -1 } else { 0 })
        } else if i > big {
          Some(if step < 0 { len - 1 } else { len })
        } else {
          Some(i.to_int())
        }
      }
      Some(_) => Option::None
    }
  }
  // Absent bounds run the whole way, in whichever direction the step goes.
  let start = match bound(bounds.lower, if step < 0 { len - 1 } else { 0 }) {
    Some(i) => i
    None => return Aborts(TypeError)
  }
  let stop = match bound(bounds.upper, if step < 0 { -1 } else { len }) {
    Some(i) => i
    None => return Aborts(TypeError)
  }
  let out : Array[Value] = []
  if step > 0 {
    let mut i = start
    while i < stop {
      out.push(xs[i])
      i += step
    }
  } else {
    let mut i = start
    while i > stop {
      out.push(xs[i])
      i += step
    }
  }
  match v {
    // A slice of a string is a string, not a list of one-character strings.
    Str(_) => {
      let sb = StringBuilder()
      for c in out {
        match c {
          Str(t) => sb.write_string(t)
          _ => return Stuck("slicing a str")
        }
      }
      Val(Str(sb.to_string()))
    }
    Tuple(_) => Val(Tuple(out))
    _ => Val(List(out))
  }
}