// Gradient boosting training with histograms, writing XGBoost JSON models.
//
// Each feature is cut into at most `max_bin` bins at observed values; trees
// grow depth-wise on per-node gradient histograms (the smaller child is
// built, its sibling is the parent minus it), and every split learns where
// missing values go. Trained models are ordinary XGBoost JSON documents, so
// XGBoost itself loads them and predicts exactly what moonboost predicts.

///|
/// Training settings, named as in XGBoost.
pub(all) struct TrainParams {
  /// `reg:squarederror`, `binary:logistic`, `multi:softprob` or
  /// `multi:softmax`
  objective : String
  /// number of classes, for the `multi:` objectives
  num_class : Int32
  num_round : Int32
  max_depth : Int32
  /// learning rate
  eta : Double
  /// L2 regularisation on leaf weights
  lambda : Double
  /// minimum loss reduction to make a split (`min_split_loss`)
  gamma : Double
  min_child_weight : Double
  max_bin : Int32
}

///|
/// XGBoost's defaults: squared error, 10 rounds, depth 6, eta 0.3,
/// lambda 1, 256 bins.
pub fn TrainParams::default() -> TrainParams {
  {
    objective: "reg:squarederror",
    num_class: 0,
    num_round: 10,
    max_depth: 6,
    eta: 0.3,
    lambda: 1.0,
    gamma: 0.0,
    min_child_weight: 1.0,
    max_bin: 256,
  }
}

///|
/// Feature values cut into bins. `by_col[f * rows + r]` is one more than
/// the bin of row `r` in feature `f` (`0` missing); a value `v` falls in bin
/// `k` when exactly `k` of the feature's cut points are `<= v`.
priv struct Binned {
  cols : Int32
  // for two-byte training, the histogram slot of row r in feature f at
  // bins[r * cols + f]: `cut_start[f] + 2 * f` when missing, then one per
  // bin (filled by training only when needed)
  mut bins : U16s
  by_col : U16s
  // cut points of feature f are cuts[cut_start[f] .. cut_start[f + 1]]
  cuts : Array[Float]
  cut_start : FixedArray[Int32]
  // whether feature f has a missing value
  missing : FixedArray[Bool]
}

///|
/// Sorts the non-missing values of one column: a radix sort on keys that
/// order like the floats, skipping the byte passes where all keys agree.
fn sorted_column(m : DenseMatrix, f : Int32) -> FixedArray[Float] {
  let rows = m.rows
  let cols = m.cols
  let mut n = 0
  for r in 0..> 31) & 0x7FFFFFFF) ^ 0x80000000
      k += 1
    }
  }
  let count = FixedArray::make(256, 0)
  for pass in 0..<4 {
    let shift = pass * 8
    count.fill(0)
    for i in 0..> shift) & 255
      count.unsafe_set(d, count.unsafe_get(d) + 1)
    }
    if n == 0 || count[(keys[0] >> shift) & 255] == n {
      continue
    }
    let mut sum = 0
    for d in 0..<256 {
      let c = count[d]
      count[d] = sum
      sum += c
    }
    for i in 0..> shift) & 255
      let at = count.unsafe_get(d)
      tmp.unsafe_set(at, key)
      count.unsafe_set(d, at + 1)
    }
    let t = keys
    keys = tmp
    tmp = t
  }
  FixedArray::makei(n, fn(i) {
    let key = keys[i] ^ 0x80000000
    Float::reinterpret_from_int(key ^ ((key >> 31) & 0x7FFFFFFF))
  })
}

///|
/// Rows per call of the loops that pass over all rows. Each loop is its
/// own function, called block by block: WebAssembly engines optimise a
/// function between calls but not while one call runs, so a loop over all
/// rows in a function called once would run unoptimised throughout.
let block : Int32 = 8192

///|
/// Bins of feature f for rows lo..hi into by_col (feature-major, `rows`
/// rows), against the feature's sorted cuts fv and their order keys fc.
fn bin_block(
  data : FixedArray[Float],
  cols : Int32,
  f : Int32,
  fv : FixedArray[Float],
  fc : FixedArray[Int32],
  by_col : U16s,
  rows : Int32,
  lo : Int32,
  hi : Int32,
) -> Unit {
  // the bin of a value is one more than the number of cuts <= it, found
  // by steps that add without a branch (`cut_step`); four
  // rows search side by side, as each search is one long dependency chain.
  // A missing value keeps bin 0.
  let mut r = lo
  while r + 4 <= hi {
    let v0 = data[r * cols + f]
    let x0 = order_key(v0)
    let v1 = data[(r + 1) * cols + f]
    let x1 = order_key(v1)
    let v2 = data[(r + 2) * cols + f]
    let x2 = order_key(v2)
    let v3 = data[(r + 3) * cols + f]
    let x3 = order_key(v3)
    let mut k0 = 0
    let mut k1 = 0
    let mut k2 = 0
    let mut k3 = 0
    let mut len = fc.length()
    while len > 0 {
      let half = len / 2
      let step = len - half
      k0 += cut_step(fv, fc, k0 + half, v0, x0, step)
      k1 += cut_step(fv, fc, k1 + half, v1, x1, step)
      k2 += cut_step(fv, fc, k2 + half, v2, x2, step)
      k3 += cut_step(fv, fc, k3 + half, v3, x3, step)
      len = half
    }
    let at = f * rows + r
    by_col.unsafe_set(at, bin_code(v0, k0))
    by_col.unsafe_set(at + 1, bin_code(v1, k1))
    by_col.unsafe_set(at + 2, bin_code(v2, k2))
    by_col.unsafe_set(at + 3, bin_code(v3, k3))
    r += 4
  }
  while r < hi {
    let v = data[r * cols + f]
    let x = order_key(v)
    let mut k = 0
    let mut len = fc.length()
    while len > 0 {
      let half = len / 2
      k += cut_step(fv, fc, k + half, v, x, len - half)
      len = half
    }
    by_col.unsafe_set(f * rows + r, bin_code(v, k))
    r += 1
  }
}

///|
/// One-byte bins of feature f for rows lo..hi: the bin less `adj`, into
/// the row words and the feature-major bytes.
fn pack_block(
  by_col : U16s,
  bins8 : Words,
  by8 : FixedArray[Byte],
  words : Int32,
  n : Int32,
  f : Int32,
  adj : Int32,
  lo : Int32,
  hi : Int32,
) -> Unit {
  let column = f / word_bins
  let shift = f % word_bins * 8
  for r in lo.. Unit {
  for r in lo.. Int32 {
  let b = (x + 0.0).reinterpret_as_int()
  b ^ ((b >> 31) & 0x7FFFFFFF)
}

///|
fn block_end(lo : Int32, n : Int32) -> Int32 {
  if n - lo > block {
    lo + block
  } else {
    n
  }
}

///|
/// The bin of a value with k cuts at or below it: k + 1, or 0 when missing.
fn bin_code(v : Float, k : Int32) -> UInt16 {
  (if v.is_nan() { 0 } else { k + 1 }).to_uint16()
}

///|
fn bin_matrix(m : DenseMatrix, max_bin : Int32) -> Binned {
  let rows = m.rows
  let cols = m.cols
  let cuts : Array[Float] = []
  let cut_start = FixedArray::make(cols + 1, 0)
  let by_col = u16s_make(rows * cols)
  let missing = FixedArray::make(cols, false)
  for f in 0.. 0 {
      // count distinct values
      let mut distinct = 1
      for i in 1.. vals[0] &&
            (cuts.length() == base || cuts[cuts.length() - 1] < c) {
            cuts.push(c)
          }
        }
      }
    }
    cut_start[f + 1] = cuts.length()
    let lo = base
    let hi = cuts.length()
    let fv = FixedArray::makei(hi - lo, fn(i) { cuts[lo + i] })
    let fc = FixedArray::makei(hi - lo, fn(i) { order_key(fv[i]) })
    let data = m.data
    for lo = 0; lo < rows; lo = lo + block {
      bin_block(data, cols, f, fv, fc, by_col, rows, lo, block_end(lo, rows))
    }
    for r in 0.. GrowTree {
  {
    left: [],
    right: [],
    parent: [],
    split_index: [],
    split_cond: [],
    default_left: [],
    base_weight: [],
    loss_change: [],
    sum_hess: [],
  }
}

///|
fn GrowTree::add(
  self : GrowTree,
  parent : Int32,
  weight : Double,
  hess : Double,
) -> Int32 {
  self.left.push(-1)
  self.right.push(-1)
  self.parent.push(parent)
  self.split_index.push(0)
  self.split_cond.push(0.0)
  self.default_left.push(false)
  self.base_weight.push(Float::from_double(weight))
  self.loss_change.push(0.0)
  self.sum_hess.push(Float::from_double(hess))
  self.left.length() - 1
}

///|
priv struct Split {
  gain : Double
  feature : Int32
  bin : Int32 // left takes bins 0 ..= bin
  default_left : Bool
  gl : Double
  hl : Double
}

///|
priv struct Grower {
  data : Binned
  p : TrainParams
  // gradient and hessian of row r at 2r and 2r + 1
  gh : F32s
  // the same pair quantised to integers and packed as (g << 32) + h, so a
  // histogram slot is one integer add; gs and hs are the scales
  gq : QArr
  mut gs : Double
  mut hs : Double
  mut igs : Double // 1 / gs
  // deeper subtrees work on their own contiguous copy of their rows' bins
  // and gradients (indexed by position, with the original row in `orig`),
  // so deep, scattered nodes stay cache local.
  // level 0 is the original arrays; a subtree is copied to the next level
  // when its depth reaches compact_at[level]
  compact_at : FixedArray[Int32]
  // copied bins take one byte, slot - cbase[feature], when every feature's
  // slots in use span at most 256 (narrow); otherwise two, the slot itself
  narrow : Bool
  // when narrow, the original bins in the same one-byte form, word_bins
  // to a word: feature f of row r is byte f % word_bins of
  // bins8[r * words + f / word_bins], so
  // a row's bins load and copy a word at a time
  bins8 : Words
  words : Int32
  // and column by column: by8[f * rows + r]
  by8 : FixedArray[Byte]
  cbins : FixedArray[Words]
  cbase : FixedArray[Int32]
  // cbase per byte of the row words; the padding bytes of a last, partial
  // word count into spare slots past nbins
  wbase : FixedArray[Int32]
  cbins16 : FixedArray[U16s]
  cq : FixedArray[QArr]
  cgh : FixedArray[F32s]
  orig : FixedArray[I32s]
  mut ihs : Double // 1 / hs
  // rows of the nodes at the current depth; partitioning writes the
  // children's rows to `scratch`, and the two swap while the children grow
  mut rows : I32s
  mut scratch : I32s
  // leaf node reached by each copied position (orig[0] maps positions to
  // rows); a leaf above the copy depth fills its own positions and orig[0]
  leaf_at : I32s
  nbins : Int32 // total histogram slots: per feature, missing + (cuts + 1)
  hist_start : FixedArray[Int32]
}

///|
fn Grower::set_scales(
  self : Grower,
  n : Int32,
  gmax : Double,
  hmax : Double,
) -> Unit {
  // sums over all n rows stay inside 31 bits for g and 32 bits for h
  let lg = (2147483647 / n - 1).to_double()
  let lh = (2147483647 / n - 1).to_double() * 2.0
  self.gs = if gmax > 0.0 { lg / gmax } else { 1.0 }
  self.hs = if hmax > 0.0 { lh / hmax } else { 1.0 }
  self.igs = 1.0 / self.gs
  self.ihs = 1.0 / self.hs
}

///|
fn Grower::weight(self : Grower, g : Double, h : Double) -> Double {
  -g / (h + self.p.lambda)
}

///|
fn Grower::score(self : Grower, g : Double, h : Double) -> Double {
  g * g / (h + self.p.lambda)
}

///|
/// Copies the bins and gradients of rows[lo:hi] to positions lo..hi of the
/// next level's arrays, and makes rows[lo:hi] hold those positions.
fn Grower::compact(
  self : Grower,
  lo : Int32,
  hi : Int32,
  level : Int32,
) -> Unit {
  // subtrees are copied from the original arrays only (compact_at has one
  // depth), so the source is always level 0
  guard level == 0 else { abort("subtrees are copied once") }
  let cols = self.data.cols
  let rows = self.rows
  let q = self.gq
  let gh = self.gh
  let bins = self.data.bins
  let tq = self.cq[0]
  let tg = self.cgh[0]
  let to = self.orig[0]
  // indices are in range: rows[lo:hi] are rows, i < n
  if self.narrow {
    let tb = self.cbins[0]
    let b8 = self.bins8
    let words = self.words
    for i in lo.. Split? {
  let parent = self.score(g, h)
  let mcw = self.p.min_child_weight
  let mut best : Split? = None
  let mut best_gain = self.p.gamma
  for f in 0..= mcw && hr >= mcw {
        let gain = self.score(gl, hl) + self.score(gr, hr) - parent
        if gain > best_gain {
          best_gain = gain
          best = Some({ gain, feature: f, bin: b, default_left: false, gl, hl, })
        }
      }
      // missing values to the left
      if mh > 0.0 {
        let gl2 = gl + mg
        let hl2 = hl + mh
        let gr2 = g - gl2
        let hr2 = h - hl2
        if hl2 >= mcw && hr2 >= mcw {
          let gain = self.score(gl2, hl2) + self.score(gr2, hr2) - parent
          if gain > best_gain {
            best_gain = gain
            best = Some({
              gain,
              feature: f,
              bin: b,
              default_left: true,
              gl: gl2,
              hl: hl2,
            })
          }
        }
      }
    }
  }
  best
}

///|
/// For one-byte bins: whether each byte of the split feature goes left
/// (1) or right (0).
fn Grower::left_table(self : Grower, s : Split) -> FixedArray[Int32] {
  let limit = s.bin + 1
  let miss = if s.default_left { 0 } else { 1 << 20 }
  let add = self.cbase[s.feature] - self.hist_start[s.feature]
  FixedArray::makei(256, fn(byte) {
    let bin = byte + add
    let key = bin + (((bin - 1) >> 31) & miss)
    if key <= limit {
      1
    } else {
      0
    }
  })
}

///|
/// Moves rows[lo:hi] going left to the front; returns where the right part
/// starts.
fn Grower::partition(
  self : Grower,
  lo : Int32,
  hi : Int32,
  s : Split,
  level : Int32,
) -> Int32 {
  let limit = s.bin + 1
  // a missing value (bin 0) goes left as bin 0, or right as a bin past limit
  let miss = if s.default_left { 0 } else { 1 << 20 }
  let rows = self.rows
  let dst = self.scratch
  let mut a = lo
  let mut b = hi - 1
  // without branches: left rows fill dst upwards from lo and right rows
  // downwards from hi - 1; each row is written at both cursors and only
  // one advances, so every slot ends with the row last meant for it
  if self.narrow {
    let go = self.left_table(s)
    if level > 0 {
      // the feature's byte of position r is in word r * words + column
      let cb = self.cbins[level - 1]
      let words = self.words
      let column = s.feature / word_bins
      let shift = s.feature % word_bins * 8
      for i in lo.. 0 {
      (
        self.cbins16[level - 1],
        self.data.cols,
        s.feature,
        self.hist_start[s.feature],
      )
    } else {
      (self.data.by_col, 1, s.feature * self.gh.length() / 2, 0)
    }
    for i in lo..> 31) & miss)
      let left = if key <= limit { 1 } else { 0 }
      dst.unsafe_set(a, r)
      dst.unsafe_set(b, r)
      a += left
      b -= 1 - left
    }
  }
  a
}

///|
fn Grower::swap_rows(self : Grower) -> Unit {
  let t = self.rows
  self.rows = self.scratch
  self.scratch = t
}

///|
/// Partitions rows[lo:hi] (original rows) like `partition`, but writes each
/// row's bins and gradients to the copy level at its new position, left
/// rows upwards from lo and right rows downwards from hi - 1; the
/// children's rows in scratch are then those positions.
fn Grower::partition_copy(
  self : Grower,
  lo : Int32,
  hi : Int32,
  s : Split,
) -> Int32 {
  let limit = s.bin + 1
  let miss = if s.default_left { 0 } else { 1 << 20 }
  let cols = self.data.cols
  let n = self.leaf_at.length()
  let rows = self.rows
  let dst = self.scratch
  let q = self.gq
  let gh = self.gh
  let tq = self.cq[0]
  let tg = self.cgh[0]
  let to = self.orig[0]
  let mut a = lo
  let mut b = hi - 1
  // indices are in range: rows[lo:hi] are rows, and a + (hi - 1 - b)
  // counts rows seen
  if self.narrow {
    let by8 = self.by8
    let b8 = self.bins8
    let tb = self.cbins[0]
    let words = self.words
    let column = s.feature * n
    let go = self.left_table(s)
    for i in lo..> 31) & miss)
      let left = if key <= limit { 1 } else { 0 }
      let p = b + (a - b) * left
      let src = r * cols
      let at = p * cols
      for f in 0.. Unit {
  let level = if level < self.compact_at.length() &&
    depth >= self.compact_at[level] &&
    depth < self.p.max_depth {
    self.compact(lo, hi, level)
    level + 1
  } else {
    level
  }
  let split = if depth < self.p.max_depth && hi - lo >= 2 {
    self.best_split(hist, g, h)
  } else {
    None
  }
  match split {
    None => {
      // leaf values use the exact gradient sums
      let mut eg = 0.0
      let mut eh = 0.0
      let gh = if level > 0 { self.cgh[level - 1] } else { self.gh }
      let rows = self.rows
      let leaf_at = self.leaf_at
      // indices are in range: rows[lo:hi] are rows or copied positions
      // positions in rows[lo:hi] are those of one copy level (there is at
      // most one); a leaf above it is given the positions lo..hi, which no
      // copied subtree uses
      if level > 0 {
        for i in lo.. {
      // a node just above the copy depth partitions its rows straight
      // into the copy, reading each row once in row order
      let copy = level == 0 &&
        self.compact_at.length() > 0 &&
        depth + 1 == self.compact_at[0] &&
        depth + 1 < self.p.max_depth
      let mid = if copy {
        self.partition_copy(lo, hi, s)
      } else {
        self.partition(lo, hi, s, level)
      }
      let level = if copy { 1 } else { level }
      // the children's rows are in scratch; they become the current rows
      // until both children have grown
      self.swap_rows()
      let gl = s.gl
      let hl = s.hl
      let gr = g - gl
      let hr = h - hl
      let l = tree.add(node, self.weight(gl, hl), hl)
      let r = tree.add(node, self.weight(gr, hr), hr)
      tree.left[node] = l
      tree.right[node] = r
      tree.split_index[node] = s.feature
      tree.split_cond[node] = self.data.cuts[self.data.cut_start[s.feature] +
        s.bin]
      tree.default_left[node] = s.default_left
      tree.loss_change[node] = Float::from_double(s.gain)
      // children at the depth limit become leaves and need no histogram;
      // otherwise build the smaller child's and derive the other's
      let (hl_hist, hr_hist) = if depth + 1 >= self.p.max_depth {
        (hist, hist)
      } else {
        let (small_lo, small_hi) = if mid - lo <= hi - mid {
          (lo, mid)
        } else {
          (mid, hi)
        }
        let small = self.histogram(small_lo, small_hi, level, depth + 1)
        // the parent's histogram becomes the larger child's
        hist_sub(hist, small)
        if small_lo == lo {
          (small, hist)
        } else {
          (hist, small)
        }
      }
      self.grow(tree, l, lo, mid, hl_hist, gl, hl, depth + 1, level)
      self.grow(tree, r, mid, hi, hr_hist, gr, hr, depth + 1, level)
      self.swap_rows()
    }
  }
}

///|
/// A float32 as JSON text that XGBoost reads as a number rather than an
/// integer: it always has a fraction or an exponent.
fn json_float(buf : StringBuilder, x : Float) -> Unit {
  let t = x.to_string()
  buf.write_string(t)
  if !(t.contains(".") || t.contains("e") || t.contains("E")) {
    buf.write_string(".0")
  }
}

///|
fn json_floats(buf : StringBuilder, a : Array[Float]) -> Unit {
  buf.write_char('[')
  for i, x in a {
    if i > 0 {
      buf.write_char(',')
    }
    json_float(buf, x)
  }
  buf.write_char(']')
}

///|
fn json_ints(buf : StringBuilder, a : Array[Int32]) -> Unit {
  buf.write_char('[')
  for i, x in a {
    if i > 0 {
      buf.write_char(',')
    }
    buf.write_string(x.to_string())
  }
  buf.write_char(']')
}

///|
fn tree_json(
  buf : StringBuilder,
  t : GrowTree,
  id : Int32,
  num_feature : Int32,
) -> Unit {
  let n = t.left.length()
  buf.write_string("{\"base_weights\":")
  json_floats(buf, t.base_weight)
  buf.write_string(
    ",\"categories\":[],\"categories_nodes\":[],\"categories_segments\":[],\"categories_sizes\":[],\"default_left\":",
  )
  json_ints(buf, t.default_left.map(b => if b { 1 } else { 0 }))
  buf.write_string(",\"id\":\{id},\"left_children\":")
  json_ints(buf, t.left)
  buf.write_string(",\"loss_changes\":")
  json_floats(buf, t.loss_change)
  buf.write_string(",\"parents\":")
  json_ints(buf, t.parent.map(p => if p < 0 { 2147483647 } else { p }))
  buf.write_string(",\"right_children\":")
  json_ints(buf, t.right)
  buf.write_string(",\"split_conditions\":")
  json_floats(buf, t.split_cond)
  buf.write_string(",\"split_indices\":")
  json_ints(buf, t.split_index)
  buf.write_string(",\"split_type\":")
  json_ints(buf, Array::make(n, 0))
  buf.write_string(",\"sum_hessian\":")
  json_floats(buf, t.sum_hess)
  buf.write_string(
    ",\"tree_param\":{\"num_deleted\":\"0\",\"num_feature\":\"\{num_feature}\",\"num_nodes\":\"\{n}\",\"size_leaf_vector\":\"1\"}}",
  )
}

///|
/// A float written the way XGBoost writes its parameters.
fn xgb_float_text(x : Float) -> String {
  x.to_string()
}

///|
/// Trains a model and returns it as an XGBoost JSON document, which both
/// moonboost and XGBoost load. `label` has one entry per row: the target,
/// a 0/1 label, or a class index.
pub fn train_xgboost_json(
  data : DenseMatrix,
  label : ArrayView[Float],
  params~ : TrainParams = TrainParams::default(),
) -> String raise ModelError {
  train_json(data, label, params, true)
}

///|
/// Gradients of class k for rows lo..hi: stores each row's exact pair and
/// quantised pair and resets rows[r] = r; returns gsum and hsum with the
/// rows' gradients added in row order.
fn Grower::gradients(
  self : Grower,
  label : ArrayView[Float],
  margin : FixedArray[Float],
  probs : FixedArray[Double],
  groups : Int32,
  k : Int32,
  kind : Int32,
  lo : Int32,
  hi : Int32,
  gsum : Double,
  hsum : Double,
) -> (Double, Double) {
  let gh = self.gh
  let gq = self.gq
  let rows = self.rows
  let mut gsum = gsum
  let mut hsum = hsum
  for r in lo.. (m - y, 1.0)
      1 => {
        let pr = 1.0 / (1.0 + train_exp(-m))
        let h = pr * (1.0 - pr)
        (pr - y, if h < 1.0e-16 { 1.0e-16 } else { h })
      }
      _ => {
        let pr = probs[r * groups + k]
        let t = if y.to_int() == k { 1.0 } else { 0.0 }
        let h = 2.0 * pr * (1.0 - pr)
        (pr - t, if h < 1.0e-16 { 1.0e-16 } else { h })
      }
    }
    let g = Float::from_double(g).to_double()
    let h = Float::from_double(h).to_double()
    gh.unsafe_set(r * 2, Float::from_double(g))
    gh.unsafe_set(r * 2 + 1, Float::from_double(h))
    self.pack_at(gq, r, g, h)
    rows.unsafe_set(r, r)
    gsum += g
    hsum += h
  }
  (gsum, hsum)
}

///|
/// Adds each copied position's leaf value to its row's margin of class k,
/// for positions lo..hi.
fn add_leaves(
  margin : FixedArray[Float],
  orig : I32s,
  leaf_at : I32s,
  leaves : FixedArray[Float],
  groups : Int32,
  k : Int32,
  lo : Int32,
  hi : Int32,
) -> Unit {
  for i in lo.. String raise ModelError {
  let p = params
  let n = data.rows
  if label.length() != n {
    raise InvalidModel("\{label.length()} labels for \{n} rows")
  }
  if n == 0 {
    raise InvalidModel("no training rows")
  }
  if p.max_bin < 2 || p.max_bin > 65535 || p.max_depth < 1 || p.num_round < 0 {
    raise InvalidModel("bad training parameters")
  }
  let groups = match p.objective {
    "reg:squarederror" | "binary:logistic" => 1
    "multi:softprob" | "multi:softmax" => {
      if p.num_class < 2 {
        raise InvalidModel("`num_class` must be at least 2")
      }
      p.num_class
    }
    o => raise Unsupported("training objective \{o}")
  }
  for y in label {
    if y.is_nan() {
      raise InvalidModel("missing label")
    }
    if p.objective == "binary:logistic" && (y < 0.0 || y > 1.0) {
      raise InvalidModel("binary labels must be in [0, 1]")
    }
    if groups > 1 &&
      (
        y < 0.0 ||
        y.to_int() >= groups ||
        y.to_int().to_double() != y.to_double()
      ) {
      raise InvalidModel("class labels must be 0 .. num_class - 1")
    }
  }
  // intercept, in the space XGBoost stores it
  let mut mean = 0.0
  for y in label {
    mean += y.to_double()
  }
  mean = mean / n.to_double()
  let (base_text, base_margin) = match p.objective {
    "reg:squarederror" => {
      let b = Float::from_double(mean)
      ("[" + xgb_float_text(b) + "]", b.to_double())
    }
    "binary:logistic" => {
      let pr = Float::from_double(
        if mean < 1.0e-6 {
          1.0e-6
        } else if mean > 1.0 - 1.0e-6 {
          1.0 - 1.0e-6
        } else {
          mean
        },
      )
      let x = pr.to_double()
      ("[" + xgb_float_text(pr) + "]", @math.ln(x / (1.0 - x)))
    }
    _ => ("[" + Array::make(groups, "0").join(",") + "]", 0.0)
  }
  let kind = match p.objective {
    "reg:squarederror" => 0
    "binary:logistic" => 1
    _ => 2
  }
  // histogram slots are stored as UInt16
  if data.cols * (p.max_bin + 1) > 65535 {
    raise InvalidModel("too many features times bins for training")
  }
  let binned = bin_matrix(data, p.max_bin)
  let hist_start = FixedArray::make(data.cols + 1, 0)
  for f in 0.. 255 {
      narrow = false
    }
  }
  let copies = if narrow { 0 } else { n * data.cols }
  let cols = data.cols
  let words = (cols + word_bins - 1) / word_bins
  let wn = if narrow { n * words } else { 0 }
  let bins8 = words_make(wn)
  let by8 = FixedArray::make(n * cols - copies, b'\x00')
  let by_col = binned.by_col
  if narrow {
    // one-byte bins: the bin, plus one for a feature with missing values
    // (whose missing bin is 0)
    for f in 0.. 1 {
      let out = FixedArray::make(n * groups, 0.0)
      for r in 0.. mx {
            mx = v
          }
        }
        let mut sum = 0.0
        for k in 0.. {
          let mut gmax = 0.0
          for r in 0.. gmax {
              gmax = d
            }
          }
          gr.set_scales(
            n,
            Float::from_double(gmax).to_double() * 1.0000001,
            1.0,
          )
        }
        1 => gr.set_scales(n, 1.0, 0.25)
        _ => gr.set_scales(n, 1.0, 0.5)
      }
      for lo = 0; lo < n; lo = lo + block {
        let (g, h) = gr.gradients(
          label,
          margin,
          probs,
          groups,
          k,
          kind,
          lo,
          block_end(lo, n),
          gsum,
          hsum,
        )
        gsum = g
        hsum = h
      }
      let tree = GrowTree::new()
      let root = tree.add(-1, gr.weight(gsum, hsum), hsum)
      let hist = gr.histogram(0, n, 0, 0)
      // every row is in exactly one slot of feature 0, so those slots sum
      // to the quantised totals
      let mut qg = 0.0
      let mut qh = 0.0
      for slot in hist_start[0].. 0 {
        trees.write_char(',')
      }
      tree_json(trees, tree, num_trees, data.cols)
      num_trees += 1
    }
  }
  let buf = StringBuilder()
  buf.write_string(
    "{\"learner\":{\"attributes\":{},\"feature_names\":[],\"feature_types\":[],\"gradient_booster\":{\"model\":{\"cats\":{\"enc\":[],\"feature_segments\":[],\"sorted_idx\":[]},",
  )
  buf.write_string(
    "\"gbtree_model_param\":{\"num_parallel_tree\":\"1\",\"num_trees\":\"\{num_trees}\"},\"iteration_indptr\":",
  )
  json_ints(buf, Array::makei(p.num_round + 1, i => i * groups))
  buf.write_string(",\"tree_info\":")
  json_ints(buf, Array::makei(num_trees, i => i % groups))
  buf.write_string(",\"trees\":[")
  buf.write_string(trees.to_string())
  buf.write_string("]},\"name\":\"gbtree\"},\"learner_model_param\":{")
  let num_class = if groups > 1 { groups } else { 0 }
  buf.write_string(
    "\"base_score\":\"\{base_text}\",\"boost_from_average\":\"1\",\"num_class\":\"\{num_class}\",\"num_feature\":\"\{data.cols}\",\"num_target\":\"1\"},",
  )
  if groups > 1 {
    buf.write_string(
      "\"objective\":{\"name\":\"\{p.objective}\",\"softmax_multiclass_param\":{\"num_class\":\"\{groups}\"}}",
    )
  } else {
    buf.write_string(
      "\"objective\":{\"name\":\"\{p.objective}\",\"reg_loss_param\":{\"scale_pos_weight\":\"1\"}}",
    )
  }
  buf.write_string("},\"version\":[3,4,1]}")
  buf.to_string()
}

///|
/// Trains a model (see `train_xgboost_json`).
pub fn Model::train(
  data : DenseMatrix,
  label : ArrayView[Float],
  params~ : TrainParams = TrainParams::default(),
) -> Model raise ModelError {
  Model::from_xgboost_json(train_xgboost_json(data, label, params~))
}