///|
priv struct RowRef {
  table : String
  key : String
}

///|
priv struct Visit {
  row : RowRef
  expand : Bool
}

///|
fn row_key(row : Map[String, Json], fields : Array[String]) -> String? {
  let values : Array[Json] = []
  for col in fields {
    let value = row[col]
    if value is Null {
      return None
    }
    values.push(value)
  }
  Some(Json::array(values).stringify())
}

///|
fn index_rows(
  spec : Spec,
  data : Dataset,
) -> Map[String, Map[String, Map[String, Json]]] raise BranchError {
  let result : Map[String, Map[String, Map[String, Json]]] = Map([])
  require(
    data.tables.length() == spec.tables.length(),
    "snapshot tables do not match recipe",
  )
  for table in spec.tables {
    guard data.tables.get(table.name) is Some(rows) else {
      raise Invalid("missing snapshot table: \{table.name}")
    }
    let index : Map[String, Map[String, Json]] = Map([])
    for row in rows {
      require(
        row.length() == table.columns.length(),
        "unexpected row columns in \{table.name}",
      )
      for col in table.columns {
        require(
          row.get(col) is Some(value) && safe_input(value),
          "expected text or null for \{table.name}.\{col}",
        )
      }
      guard row_key(row, table.key) is Some(key) else {
        raise Invalid("null primary key in \{table.name}")
      }
      require(!index.contains(key), "duplicate primary key in \{table.name}")
      index[key] = row
    }
    result[table.name] = index
  }
  result
}

///|
/// Roots and opted-in descendants can expand downward. Rows included only
/// to satisfy a foreign key cannot bring in unrelated rows below them.
pub fn slice(spec : Spec, data : Dataset) -> Dataset raise BranchError {
  validate(spec)
  let rows = index_rows(spec, data)
  let tables : Map[String, Table] = Map([])
  let chosen : Map[String, Map[String, Bool]] = Map([])
  let expanded : Map[String, Map[String, Bool]] = Map([])
  let outgoing : Map[String, Array[(String, Map[String, Array[String]])]] = Map([],
  )
  for table in spec.tables {
    tables[table.name] = table
    chosen[table.name] = {}
    expanded[table.name] = {}
    outgoing[table.name] = []
  }
  for edge in spec.follow {
    let index : Map[String, Array[String]] = Map([])
    let fields = tables[edge.child].foreign_keys[edge.foreign_key].columns
    for key, row in rows[edge.child] {
      if row_key(row, fields) is Some(parent_key) {
        if index.get(parent_key) is Some(children) {
          children.push(key)
        } else {
          index[parent_key] = [key]
        }
      }
    }
    outgoing[edge.from].push((edge.child, index))
  }
  let queue : Array[Visit] = []
  for root in spec.roots {
    for values in root.keys {
      queue.push({
        row: { table: root.table, key: Json::array(values).stringify(), },
        expand: true,
      })
    }
  }
  let mut count = 0
  for i = 0; i < queue.length(); i = i + 1 {
    let { row: { table, key, }, expand, } = queue[i]
    guard rows[table].get(key) is Some(row) else {
      raise Invalid("root or referenced row not found in \{table}")
    }
    if !chosen[table].contains(key) {
      count += 1
      require(count <= spec.max_rows, "slice exceeds max_rows")
      chosen[table][key] = true
      for fk in tables[table].foreign_keys {
        if row_key(row, fk.columns) is Some(parent_key) {
          queue.push({
            row: { table: fk.parent, key: parent_key, },
            expand: false,
          })
        }
      }
    }
    if expand && !expanded[table].contains(key) {
      expanded[table][key] = true
      for pair in outgoing[table] {
        let (child, index) = pair
        if index.get(key) is Some(keys) {
          for child_key in keys {
            queue.push({ row: { table: child, key: child_key, }, expand: true, })
          }
        }
      }
    }
  }
  let output : Map[String, Array[Map[String, Json]]] = Map([])
  for table in spec.tables {
    let keys = chosen[table.name].keys().collect()
    keys.sort()
    output[table.name] = keys.map(fn(key) {
      let ordered = Map([])
      for col in table.columns {
        ordered[col] = mask_value(spec, table.name, col).unwrap_or(
          rows[table.name][key][col],
        )
      }
      ordered
    })
  }
  { tables: output, }
}