///|
fn insert_order(tables : Array[Table]) -> Array[Table] {
  let ordered : Array[Table] = []
  let done : Map[String, Bool] = Map([])
  while ordered.length() < tables.length() {
    let before = ordered.length()
    for table in tables {
      if !done.contains(table.name) &&
        table.foreign_keys.all(fn(fk) {
          fk.parent == table.name || done.contains(fk.parent)
        }) {
        ordered.push(table)
        done[table.name] = true
      }
    }
    if before == ordered.length() {
      // Cross-table cycles are checked by PostgreSQL after INSERT when their
      // constraints are deferrable. Immediate constraints still apply.
      for table in tables {
        if !done.contains(table.name) {
          ordered.push(table)
        }
      }
    }
  }
  ordered
}

///|
pub fn verify_branch(spec : Spec, data : Dataset) -> Unit raise BranchError {
  let canonical = @json.ToJson::to_json(slice(spec, data)).stringify()
  require(
    canonical == @json.ToJson::to_json(data).stringify(),
    "branch has extra, unsorted, or unmasked rows",
  )
}

///|
/// Generate a transaction for an empty, pre-migrated development database.
pub fn restore_sql(spec : Spec, data : Dataset) -> String raise BranchError {
  verify_branch(spec, data)
  let sql = StringBuilder()
  sql.write_string("BEGIN;\n\{pg_settings}")
  sql.write_string(
    assert_sql(
      "current_database() ~ '^moonbranch_[a-z0-9_]+$' AND NOT pg_is_in_recovery() AND current_setting('session_replication_role') = 'origin'",
      "restore requires a writable database named moonbranch_*",
    ),
  )
  sql.write_string("LOCK TABLE \{lock_list(spec)} IN ACCESS EXCLUSIVE MODE;\n")
  sql.write_string(catalog_checks(spec))
  for table in spec.tables {
    let name = qualified(spec.schema, table.name)
    sql.write_string(
      assert_sql(
        "NOT EXISTS (SELECT 1 FROM \{name})",
        "target is not empty: \{table.name}",
      ),
    )
    sql.write_string(
      assert_sql(
        "NOT EXISTS (SELECT 1 FROM pg_catalog.pg_trigger WHERE tgrelid = \{literal(name)}::regclass AND NOT tgisinternal AND tgenabled <> 'D') AND NOT EXISTS (SELECT 1 FROM pg_catalog.pg_rewrite WHERE ev_class = \{literal(name)}::regclass AND ev_enabled <> 'D')",
        "enabled user triggers or rewrite rules in target: \{table.name}",
      ),
    )
  }
  sql.write_string("SET CONSTRAINTS ALL DEFERRED;\n")
  for table in insert_order(spec.tables) {
    let rows = data.tables[table.name]
    if rows.is_empty() {
      continue
    }
    let name = qualified(spec.schema, table.name)
    let columns = table.columns.map(ident).join(", ")
    let values = rows
      .map(fn(row) {
        let values = table.columns
          .map(fn(col) {
            match row[col] {
              String(value) => literal(value)
              _ => "NULL"
            }
          })
          .join(", ")
        "(\{values})"
      })
      .join(",\n")
    sql.write_string("INSERT INTO \{name} (\{columns}) VALUES\n\{values};\n")
  }
  sql.write_string("SET CONSTRAINTS ALL IMMEDIATE;\nCOMMIT;\n")
  sql.to_string()
}