///|
/// Types that can enumerate "smaller" variants of a given value for
/// the classical QuickCheck shrinker. Each call to `shrink(x)` returns
/// an `Iter[Self]` of candidates strictly simpler than `x`; the driver
/// walks these candidates after a failure, keeping the first one that
/// still falsifies the property.
///
/// The return type is `Iter[Self]` rather than `Array[Self]` so large
/// or recursive shrink spaces stay lazy. The default body (`= _`)
/// means "no shrinks" — a conservative starting point for types where
/// shrinking isn't meaningful.
///
/// ```mbt check
/// test {
///   // `Int` has a built-in Shrink instance that walks toward 0.
///   let candidates : Array[Int] = Shrink::shrink(100).collect()
///   assert_true(candidates.contains(0))
///   assert_true(candidates.length() > 0)
///   // `Bool` shrinks `true` to `false`, and `false` has no shrinks.
///   assert_eq(Shrink::shrink(true).collect(), [false])
///   assert_eq(Shrink::shrink(false).collect(), [])
/// }
/// ```
pub(open) trait Shrink {
  shrink(Self) -> Iter[Self] = _
}

///|
impl Shrink with shrink(_a) {
  Iter::empty()
}

///|
pub impl Shrink for Int with shrink(x) {
  @utils.apply_while_list(x, z => z / 2, z => (x - z).abs() < x.abs())
  .map(i => x - i)
  .iter()
  .concat(Iter::singleton(0))
  .filter(u => u != x)
}

///|
test "shrink int" {
  json_inspect(Shrink::shrink(100), content=[99, 97, 94, 88, 75, 50, 0])
  json_inspect(Shrink::shrink(0), content=[])
}

///|
pub impl Shrink for Int64 with shrink(x) {
  @utils.apply_while_list(x, z => z / 2, z => (x - z).abs() < x.abs())
  .map(i => x - i)
  .iter()
  .concat(Iter::singleton(0))
  .filter(u => u != x)
}

///|
test "shrink int64" {
  json_inspect(Shrink::shrink(10000L), content=[
    "9999", "9998", "9996", "9991", "9981", "9961", "9922", "9844", "9688", "9375",
    "8750", "7500", "5000", "0",
  ])
}

///|
pub impl Shrink for UInt with shrink(x) {
  @utils.apply_while_list(x, z => z / 2, z => z > 0)
  .map(i => x - i)
  .iter()
  .concat(Iter::singleton(0))
  .filter(u => u != x)
}

///|
test "shrink uint" {
  json_inspect(Shrink::shrink(37000U), content=[
    36999, 36998, 36996, 36991, 36982, 36964, 36928, 36856, 36711, 36422, 35844,
    34688, 32375, 27750, 18500, 0,
  ])
}

///|
pub impl Shrink for UInt64 with shrink(x) {
  @utils.apply_while_list(x, z => z / 2, z => z > 0)
  .map(i => x - i)
  .iter()
  .concat(Iter::singleton(0))
  .filter(u => u != x)
}

///|
test "shrink uint64" {
  json_inspect(Shrink::shrink((42000 : UInt64)), content=[
    "41999", "41998", "41995", "41990", "41980", "41959", "41918", "41836", "41672",
    "41344", "40688", "39375", "36750", "31500", "21000", "0",
  ])
}

///|
pub impl Shrink for Bool with shrink(b) {
  if !b {
    Iter::empty()
  } else {
    Iter::singleton(false)
  }
}

///|
test "shrink boolean" {
  json_inspect(Shrink::shrink(true), content=[false])
  json_inspect(Shrink::shrink(false), content=[])
}

///|
pub impl Shrink for Char with shrink(c) {
  let ci = c.to_int()
  if ci == 0 {
    return Iter::empty()
  } else {
    let (cl, ch) = (Int::unsafe_to_char(ci - 1), Int::unsafe_to_char(ci + 1))
    [cl, ch, 'a', 'A', '1', '\n', '\t', '\b', '\\', '\'', '\r', ' '].iter()
  }
}

///|
test "shrink char" {
  json_inspect(Shrink::shrink('测'), content=[
    "浊", "浌", "a", "A", "1", "\n", "\t", "\b", "\\", "'", "\r", " ",
  ])
}

///|
pub impl Shrink for Double

///|
pub impl Shrink for Float

///|
pub impl Shrink for String

///|
pub impl Shrink for Bytes

///|
pub impl[T : Shrink] Shrink for T? with shrink(x) {
  match x {
    None => Iter::empty()
    Some(v) =>
      Shrink::shrink(v).map(v1 => Some(v1)).concat(Iter::singleton(None))
  }
}

///|

///|
pub impl Shrink for Unit

///|
test "shrink option" {
  json_inspect(Shrink::shrink((None : Unit?)), content=[])
  json_inspect(Shrink::shrink(Some(1000)), content=[
    [999],
    [997],
    [993],
    [985],
    [969],
    [938],
    [875],
    [750],
    [500],
    [0],
    null,
  ])
}

///|
pub impl[T : Shrink, E : Shrink] Shrink for Result[T, E] with shrink(x) {
  match x {
    Ok(v) => Shrink::shrink(v).map(v1 => Ok(v1))
    Err(e) => Shrink::shrink(e).map(e1 => Err(e1))
  }
}

///|
test "shrink result" {
  let b : Result[Bool, Int] = Err(100)
  let x : Result[Bool, Int] = Ok(true)
  json_inspect(Shrink::shrink(b), content=[
    { "Err": 99 },
    { "Err": 97 },
    { "Err": 94 },
    { "Err": 88 },
    { "Err": 75 },
    { "Err": 50 },
    { "Err": 0 },
  ])
  json_inspect(Shrink::shrink(x), content=[{ "Ok": false }])
}

///|
pub impl[A : Shrink, B : Shrink] Shrink for (A, B) with shrink(x) {
  let (a, b) = x
  Shrink::shrink(a)
  .map(a1 => (a1, b))
  .concat(Shrink::shrink(b).map(b1 => (a, b1)))
}

///|
test "shrink tuple" {
  let x = (120, true)
  json_inspect(Shrink::shrink(x), content=[
    [119, true],
    [117, true],
    [113, true],
    [105, true],
    [90, true],
    [60, true],
    [0, true],
    [120, false],
  ])
}

///|
pub impl[A : Shrink, B : Shrink, C : Shrink] Shrink for (A, B, C) with shrink(x) {
  let (a, b, c) = x
  Shrink::shrink((a, (b, c))).map(y => {
    let (a1, (b1, c1)) = y
    (a1, b1, c1)
  })
}

///|
pub impl[A : Shrink, B : Shrink, C : Shrink, D : Shrink] Shrink for (A, B, C, D) with shrink(
  x,
) {
  let (a, b, c, d) = x
  Shrink::shrink((a, (b, c, d))).map(y => {
    let (a1, (b1, c1, d1)) = y
    (a1, b1, c1, d1)
  })
}

///|
pub impl[A : Shrink, B : Shrink, C : Shrink, D : Shrink, E : Shrink] Shrink for (
  A,
  B,
  C,
  D,
  E,
) with shrink(x) {
  let (a, b, c, d, e) = x
  Shrink::shrink((a, (b, c, d, e))).map(y => {
    let (a1, (b1, c1, d1, e1)) = y
    (a1, b1, c1, d1, e1)
  })
}

///|
pub impl[A : Shrink, B : Shrink, C : Shrink, D : Shrink, E : Shrink, F : Shrink] Shrink for (
  A,
  B,
  C,
  D,
  E,
  F,
) with shrink(x) {
  let (a, b, c, d, e, f) = x
  Shrink::shrink((a, (b, c, d, e, f))).map(y => {
    let (a1, (b1, c1, d1, e1, f1)) = y
    (a1, b1, c1, d1, e1, f1)
  })
}

///|
fn[X] shrink_remove_one_array(xs : Array[X]) -> Iter[Array[X]] {
  let l = xs.length() - 1
  Array::makei(l + 1, i => i)
  .iter()
  .flat_map(i => {
    let nv = xs.copy()
    nv.remove(i) |> ignore
    Iter::singleton(nv)
  })
}

///|
/// Shrink sorted array, requires the Array[T] to be sorted.
pub fn[T : Shrink + Compare] shrink_sorted_array(
  xs : Array[T],
  lo~ : T,
  hi~ : T,
) -> Iter[Array[T]] {
  let shrink_one_val = (nv : Array[T]) => {
    let l = nv.length() - 1
    Array::makei(l + 1, i => i)
    .iter()
    .flat_map(i => {
      let lo = if i == 0 { lo } else { nv[i - 1] }
      let hi = if i == l { hi } else { nv[i + 1] }
      Shrink::shrink(nv[i]).flat_map(x => {
        if lo <= x && x <= hi && x != nv[i] {
          let nv1 = nv.copy()
          nv1[i] = x
          Iter::singleton(nv1)
        } else {
          Iter::empty()
        }
      })
    })
  }
  shrink_remove_one_array(xs).concat(shrink_one_val(xs))
}

///|
/// Shrink sorted list, requires the List[T] to be sorted.
pub fn[T : Shrink + Compare] shrink_sorted_list(
  xs : List[T],
  lo~ : T,
  hi~ : T,
) -> Iter[List[T]] {
  shrink_sorted_array(xs.to_array(), lo~, hi~).map(a => @list.from_array(a))
}

///|
/// Shrink distinct array, requires all elements of the Array[X] to be distinct.
pub fn[X : Shrink + Eq] shrink_distinct_array(xs : Array[X]) -> Iter[Array[X]] {
  fn no_duplicate_at(arr : Array[X], i : Int, x : X) -> Bool {
    for j in 0.. i)
    .iter()
    .flat_map(i => {
      X::shrink(xs[i]).flat_map(x => {
        if x != xs[i] && no_duplicate_at(xs, i, x) {
          let nv = xs.copy()
          nv[i] = x
          Iter::singleton(nv)
        } else {
          Iter::empty()
        }
      })
    })
  shrink_remove_one_array(xs).concat(shrink_one_val)
}

///|
/// Shrink sorted distinct array, requires the Array[T] to be sorted and distinct.
pub fn[T : Shrink + Compare] shrink_sorted_distinct_array(
  xs : Array[T],
  lo~ : T,
  hi~ : T,
) -> Iter[Array[T]] {
  let shrink_one_val = (nv : Array[T]) => {
    let l = nv.length() - 1
    Array::makei(l + 1, i => i)
    .iter()
    .flat_map(i => {
      let lower_ok = x => if i == 0 { lo <= x } else { nv[i - 1] < x }
      let upper_ok = x => if i == l { x <= hi } else { x < nv[i + 1] }
      T::shrink(nv[i]).flat_map(x => {
        if lower_ok(x) && upper_ok(x) && x != nv[i] {
          let nv1 = nv.copy()
          nv1[i] = x
          Iter::singleton(nv1)
        } else {
          Iter::empty()
        }
      })
    })
  }
  shrink_remove_one_array(xs).concat(shrink_one_val(xs))
}

///|
test "shrink 6-tuple" {
  let x = (20, 'A', 30U, true, true, true)
  json_inspect(Shrink::shrink(x), content=[
    [19, "A", 30, true, true, true],
    [18, "A", 30, true, true, true],
    [15, "A", 30, true, true, true],
    [10, "A", 30, true, true, true],
    [0, "A", 30, true, true, true],
    [20, "@", 30, true, true, true],
    [20, "B", 30, true, true, true],
    [20, "a", 30, true, true, true],
    [20, "A", 30, true, true, true],
    [20, "1", 30, true, true, true],
    [20, "\n", 30, true, true, true],
    [20, "\t", 30, true, true, true],
    [20, "\b", 30, true, true, true],
    [20, "\\", 30, true, true, true],
    [20, "'", 30, true, true, true],
    [20, "\r", 30, true, true, true],
    [20, " ", 30, true, true, true],
    [20, "A", 29, true, true, true],
    [20, "A", 27, true, true, true],
    [20, "A", 23, true, true, true],
    [20, "A", 15, true, true, true],
    [20, "A", 0, true, true, true],
    [20, "A", 30, false, true, true],
    [20, "A", 30, true, false, true],
    [20, "A", 30, true, true, false],
  ])
}

///|
pub impl[T : Shrink] Shrink for List[T] with shrink(xs) {
  let n = xs.length()
  fn shr_sub_terms(lst : List[T]) {
    match lst {
      Empty => Iter::empty()
      More(x, tail=xs) =>
        T::shrink(x)
        .map(x_ => xs.add(x_))
        .concat(shr_sub_terms(xs).map(xs_ => xs_.add(x)))
    }
  }

  @utils.apply_while_list(n, x => x / 2, x => x > 0)
  .map(k => @utils.removes_list(k, n, xs))
  .flatten()
  .iter()
  .concat(shr_sub_terms(xs))
}

///|
/// Shrink non-empty list without producing the empty list.
///
/// ```mbt check
/// test {
///   let xs : @list.List[Int] = @list.from_array([5])
///   // Default list shrink would produce [], which is filtered out here.
///   assert_true(shrink_non_empty_list(xs).all(ys => !ys.is_empty()))
/// }
/// ```
pub fn[T : Shrink] shrink_non_empty_list(xs : List[T]) -> Iter[List[T]] {
  Shrink::shrink(xs).filter(ys => !ys.is_empty())
}

///|
test "shrink int list" {
  let il : List[Int] = @list.from_array([1, 2, 3, 4, 5, 6])
  let s = Shrink::shrink(il)
  json_inspect(s, content=[
    [2, 3, 4, 5, 6],
    [1, 3, 4, 5, 6],
    [1, 2, 4, 5, 6],
    [1, 2, 3, 5, 6],
    [1, 2, 3, 4, 6],
    [4, 5, 6],
    [0, 2, 3, 4, 5, 6],
    [1, 1, 3, 4, 5, 6],
    [1, 0, 3, 4, 5, 6],
    [1, 2, 2, 4, 5, 6],
    [1, 2, 0, 4, 5, 6],
    [1, 2, 3, 3, 5, 6],
    [1, 2, 3, 2, 5, 6],
    [1, 2, 3, 0, 5, 6],
    [1, 2, 3, 4, 4, 6],
    [1, 2, 3, 4, 3, 6],
    [1, 2, 3, 4, 0, 6],
    [1, 2, 3, 4, 5, 5],
    [1, 2, 3, 4, 5, 3],
    [1, 2, 3, 4, 5, 0],
  ])
}

///|
test "shrink non-empty list" {
  let il : List[Int] = @list.from_array([1])
  json_inspect(shrink_non_empty_list(il), content=[[0]])
}

///|
pub impl[X : Shrink] Shrink for Array[X] with shrink(xs) {
  let view = xs[:]
  let n = view.length()
  fn shr_sub_terms(arr : ArrayView[X]) {
    match arr {
      [] => Iter::empty()
      [x, .. xs] =>
        X::shrink(x)
        .map(x_ => [x_, ..xs])
        .concat(shr_sub_terms(xs).map(xs_ => [x, ..xs_]))
    }
  }

  @utils.apply_while_array(n, x => x / 2, x => x > 0)
  .map(k => @utils.removes_array(k, n, xs))
  .flatten()
  .iter()
  .concat(shr_sub_terms(view))
}

///|
/// Shrink non-empty array without producing the empty array.
///
/// ```mbt check
/// test {
///   assert_true(shrink_non_empty_array([1, 2, 3]).all(ys => ys.length() > 0))
/// }
/// ```
pub fn[X : Shrink] shrink_non_empty_array(xs : Array[X]) -> Iter[Array[X]] {
  Shrink::shrink(xs).filter(ys => ys.length() > 0)
}

///|
test "shrink array" {
  let ar = [1, 2, 3, 4, 5, 6]
  let s = Shrink::shrink(ar)
  json_inspect(s, content=[
    [2, 3, 4, 5, 6],
    [1, 3, 4, 5, 6],
    [1, 2, 4, 5, 6],
    [1, 2, 3, 5, 6],
    [1, 2, 3, 4, 6],
    [4, 5, 6],
    [0, 2, 3, 4, 5, 6],
    [1, 1, 3, 4, 5, 6],
    [1, 0, 3, 4, 5, 6],
    [1, 2, 2, 4, 5, 6],
    [1, 2, 0, 4, 5, 6],
    [1, 2, 3, 3, 5, 6],
    [1, 2, 3, 2, 5, 6],
    [1, 2, 3, 0, 5, 6],
    [1, 2, 3, 4, 4, 6],
    [1, 2, 3, 4, 3, 6],
    [1, 2, 3, 4, 0, 6],
    [1, 2, 3, 4, 5, 5],
    [1, 2, 3, 4, 5, 3],
    [1, 2, 3, 4, 5, 0],
  ])
}

///|
test "shrink non-empty array" {
  json_inspect(shrink_non_empty_array([1]), content=[[0]])
}

///|
pub impl[X : Shrink] Shrink for Iter[X] with shrink(xs) {
  let arr = xs.to_array()
  let its : Array[_] = Array::makei(arr.length(), x => {
    X::shrink(arr[x])
    .map(y => {
      let cp = arr.copy()
      cp[x] = y
      cp.iter()
    })
    .to_array()
  }).flatten()
  let rms : Array[Iter[X]] = arr.mapi((i, _) => {
    let a = arr.copy()
    a.remove(i) |> ignore
    a.iter()
  })
  rms.iter().concat(its.iter())
}

///|
test "shrink iter" {
  let it = [1, 2, 3, 4, 5, 6].iter()
  json_inspect(Shrink::shrink(it), content=[
    [2, 3, 4, 5, 6],
    [1, 3, 4, 5, 6],
    [1, 2, 4, 5, 6],
    [1, 2, 3, 5, 6],
    [1, 2, 3, 4, 6],
    [1, 2, 3, 4, 5],
    [0, 2, 3, 4, 5, 6],
    [1, 1, 3, 4, 5, 6],
    [1, 0, 3, 4, 5, 6],
    [1, 2, 2, 4, 5, 6],
    [1, 2, 0, 4, 5, 6],
    [1, 2, 3, 3, 5, 6],
    [1, 2, 3, 2, 5, 6],
    [1, 2, 3, 0, 5, 6],
    [1, 2, 3, 4, 4, 6],
    [1, 2, 3, 4, 3, 6],
    [1, 2, 3, 4, 0, 6],
    [1, 2, 3, 4, 5, 5],
    [1, 2, 3, 4, 5, 3],
    [1, 2, 3, 4, 5, 0],
  ])
}

///|
test "shrink sorted array" {
  let ar = [1, 3, 5, 7, 9]
  let s = shrink_sorted_array(ar, lo=0, hi=10)
  let content = s.to_array()
  json_inspect(content, content=[
    [3, 5, 7, 9],
    [1, 5, 7, 9],
    [1, 3, 7, 9],
    [1, 3, 5, 9],
    [1, 3, 5, 7],
    [0, 3, 5, 7, 9],
    [1, 2, 5, 7, 9],
    [1, 3, 4, 7, 9],
    [1, 3, 3, 7, 9],
    [1, 3, 5, 6, 9],
    [1, 3, 5, 7, 8],
    [1, 3, 5, 7, 7],
  ])
}

///|
test "shrink distinct array" {
  let s = shrink_distinct_array([1, 3, 5])
  json_inspect(s, content=[
    [3, 5],
    [1, 5],
    [1, 3],
    [0, 3, 5],
    [1, 2, 5],
    [1, 0, 5],
    [1, 3, 4],
    [1, 3, 0],
  ])
}

///|
test "shrink sorted distinct array" {
  let s = shrink_sorted_distinct_array([1, 3, 5], lo=0, hi=9)
  json_inspect(s, content=[
    [3, 5],
    [1, 5],
    [1, 3],
    [0, 3, 5],
    [1, 2, 5],
    [1, 3, 4],
  ])
}

///|
test "shrink sorted list" {
  let xs : List[Int] = @list.from_array([1, 3, 5])
  json_inspect(shrink_sorted_list(xs, lo=0, hi=9), content=[
    [3, 5],
    [1, 5],
    [1, 3],
    [0, 3, 5],
    [1, 2, 5],
    [1, 3, 4],
    [1, 3, 3],
  ])
}