crates/hub/src/backups.rs at 7b9f4570daf5 · andymccall/oxygenhub

# 7b9f4570daf5 oxygenhub / crates / hub / src / backups.rs
74.6 KiB · Rust · last changed Backups to S3, keylessly 23 days ago source blame history raw
//! Backups (docs/backups.md, oxygenhub#169): each user and organisation
//! copies its repositories, on a schedule, to a destination it controls.
//!
//! A repository is its store directory (`.oxy/`): packs and loose objects
//! that never change once written, and small files that do (refs, the
//! operation log, policies, signature indexes). A run copies each file
//! once, named by its BLAKE3 (`blobs/`), and writes a manifest of path to
//! hash per repository (`runs/<at>/repos/`), so only what changed travels
//! and any kept run can be restored byte for byte, signatures and all.
//! The large files are copied first; the walk is then repeated under the
//! repository's read lock, which pushes wait on, so each manifest is one
//! consistent moment. Beside each manifest go the hub's records for the
//! repository as JSON (never a secret value), the owner's records, and
//! last a `DONE` marker: a run without one was cut short and is ignored.

use crate::db::{self, Pool};
use crate::repos::RepoName;
use crate::Shared;
use anyhow::{bail, Context, Result};
use serde::{Deserialize, Serialize};
use std::collections::HashMap;
use std::path::{Path, PathBuf};

/// How often, as the settings offer it.
pub const EVERY: &[(&str, &str)] = &[("off", "Off"), ("hourly", "Every hour"), ("daily", "Every day")];
/// How long runs are kept, in days.
pub const KEEP: &[i64] = &[7, 30, 90];

/// What an owner backs up, where and how often.
#[derive(Clone, Debug, sqlx::FromRow, Serialize)]
pub struct Setting {
    pub owner: String,
    pub kind: String,
    pub every: String,
    pub destination: String,
    pub target: String,
    pub prefix: String,
    pub provider: String,
    pub keep_days: i64,
    pub updated_ms: i64,
    /// An S3 bucket's region (migration 0063).
    #[sqlx(default)]
    pub region: String,
}

impl Setting {
    pub fn off(owner: &str, kind: &str) -> Setting {
        Setting {
            owner: owner.into(),
            kind: kind.into(),
            every: "off".into(),
            destination: "dir".into(),
            target: String::new(),
            prefix: String::new(),
            provider: String::new(),
            keep_days: 30,
            updated_ms: 0,
            region: String::new(),
        }
    }

    /// Seconds between runs; none when off.
    pub fn period_s(&self) -> Option<i64> {
        match self.every.as_str() {
            "hourly" => Some(3600),
            "daily" => Some(86_400),
            _ => None,
        }
    }
}

/// One run, as the settings page and the API show it.
#[derive(Clone, Debug, sqlx::FromRow, Serialize)]
pub struct Run {
    pub id: i64,
    pub owner: String,
    pub started_ms: i64,
    pub finished_ms: Option<i64>,
    pub status: String,
    pub at: String,
    pub repos: i64,
    pub files: i64,
    pub sent: i64,
    pub bytes: i64,
    pub detail: String,
    pub trigger: String,
}

pub async fn setting(pool: &Pool, owner: &str) -> sqlx::Result<Option<Setting>> {
    sqlx::query_as("SELECT * FROM backup_settings WHERE owner = ?").bind(owner).fetch_optional(pool).await
}

pub async fn save(pool: &Pool, s: &Setting) -> sqlx::Result<()> {
    sqlx::query(
        "INSERT INTO backup_settings (owner, kind, every, destination, target, prefix, provider, keep_days, updated_ms, region) \
         VALUES (?, ?, ?, ?, ?, ?, ?, ?, ?, ?) ON CONFLICT(owner) DO UPDATE SET kind = excluded.kind, every = excluded.every, \
         destination = excluded.destination, target = excluded.target, prefix = excluded.prefix, provider = excluded.provider, \
         keep_days = excluded.keep_days, updated_ms = excluded.updated_ms, region = excluded.region",
    )
    .bind(&s.owner)
    .bind(&s.kind)
    .bind(&s.every)
    .bind(&s.destination)
    .bind(&s.target)
    .bind(&s.prefix)
    .bind(&s.provider)
    .bind(s.keep_days)
    .bind(db::now_ms())
    .bind(&s.region)
    .execute(pool)
    .await?;
    Ok(())
}

pub async fn runs(pool: &Pool, owner: &str, limit: i64) -> sqlx::Result<Vec<Run>> {
    sqlx::query_as("SELECT * FROM backup_runs WHERE owner = ? ORDER BY id DESC LIMIT ?").bind(owner).bind(limit).fetch_all(pool).await
}

/// What a repository may choose about its backup (§5): with its owner's,
/// left out, or at least hourly or daily whatever its owner's schedule.
pub const REPO_CHOICES: &[(&str, &str)] =
    &[("", "With its owner's backup"), ("hourly", "At least every hour"), ("daily", "At least every day"), ("off", "Left out")];

/// Whether `row` is in its owner's run: never when it is left out, always
/// when it has its own schedule, else as its owner's schedule says (a run
/// asked for by hand takes every repository not left out).
pub fn included(s: &Setting, row: &db::repos::RepoRow, by_hand: bool) -> bool {
    match row.backup.as_str() {
        "off" => false,
        "hourly" | "daily" => true,
        _ => by_hand || s.every != "off",
    }
}

/// Seconds between an owner's runs: the shortest of its own schedule and
/// its repositories' own; none when nothing is scheduled.
pub fn period_with(s: &Setting, repos: &[db::repos::RepoRow]) -> Option<i64> {
    let own = repos.iter().filter_map(|r| match r.backup.as_str() {
        "hourly" => Some(3600),
        "daily" => Some(86_400),
        _ => None,
    });
    s.period_s().into_iter().chain(own).min()
}

/// One owner's backup as Admin › Backups shows it (§5): its setting, its
/// newest run, and how many runs failed in the last day. An administrator
/// sees that it ran, never what it wrote.
#[derive(Clone, Debug, Serialize)]
pub struct Overview {
    pub setting: Setting,
    pub last: Option<Run>,
    pub failed_day: i64,
    /// The repositories it covers now.
    pub repos: i64,
}

impl Overview {
    /// Where its runs go, as a person reads it.
    pub fn place(&self) -> String {
        let s = &self.setting;
        match s.destination.as_str() {
            "gcs" if s.prefix.is_empty() => format!("gs://{}", s.target),
            "gcs" => format!("gs://{}/{}", s.target, s.prefix),
            "s3" if s.prefix.is_empty() => format!("s3://{} ({})", s.target, s.region),
            "s3" => format!("s3://{}/{} ({})", s.target, s.prefix, s.region),
            _ => format!("{}/{}", s.target, s.owner),
        }
    }
}

/// Every owner's backup (Admin › Backups), and the owners of repositories
/// that none covers, with how many each has.
pub async fn overview(pool: &Pool) -> sqlx::Result<(Vec<Overview>, Vec<(String, i64)>)> {
    let settings: Vec<Setting> = sqlx::query_as("SELECT * FROM backup_settings ORDER BY owner").fetch_all(pool).await?;
    let counts: Vec<(String, i64)> =
        sqlx::query_as("SELECT owner, COUNT(*) FROM repositories GROUP BY owner ORDER BY owner").fetch_all(pool).await?;
    let day_ago = db::now_ms() - 86_400_000;
    let mut out = Vec::new();
    for s in settings {
        let last = runs(pool, &s.owner, 1).await?.into_iter().next();
        let failed_day: i64 =
            sqlx::query_scalar("SELECT COUNT(*) FROM backup_runs WHERE owner = ? AND status = 'failed' AND started_ms >= ?")
                .bind(&s.owner)
                .bind(day_ago)
                .fetch_one(pool)
                .await?;
        let repos = db::repos::list(pool).await?.iter().filter(|r| r.owner == s.owner && included(&s, r, false)).count() as i64;
        out.push(Overview { setting: s, last, failed_day, repos });
    }
    let uncovered = counts.into_iter().filter(|(owner, _)| !out.iter().any(|o| o.setting.owner == *owner && o.repos > 0)).collect();
    Ok((out, uncovered))
}

// ---------------------------------------------------------------- where

/// Where backups are written: keys are `/`-separated paths.
pub trait Destination: Send + Sync {
    fn exists(&self, key: &str) -> Result<bool>;
    /// Write `bytes` at `key`, whole or not at all.
    fn put(&self, key: &str, bytes: &[u8]) -> Result<()>;
    fn get(&self, key: &str) -> Result<Vec<u8>>;
    /// The names directly under `prefix` (files and "directories").
    fn list(&self, prefix: &str) -> Result<Vec<String>>;
    /// Remove `key` and everything under it.
    fn remove(&self, key: &str) -> Result<()>;
}

/// A directory on the hub's host.
pub struct Directory {
    pub root: PathBuf,
}

impl Directory {
    fn path(&self, key: &str) -> Result<PathBuf> {
        if key.split('/').any(|p| p == ".." || p == ".") || key.starts_with('/') {
            bail!("not a clean key: {key}");
        }
        Ok(self.root.join(key))
    }
}

impl Destination for Directory {
    fn exists(&self, key: &str) -> Result<bool> {
        Ok(self.path(key)?.exists())
    }
    fn put(&self, key: &str, bytes: &[u8]) -> Result<()> {
        let p = self.path(key)?;
        std::fs::create_dir_all(p.parent().context("no parent")?)?;
        let tmp = p.with_extension(format!("part-{}", std::process::id()));
        std::fs::write(&tmp, bytes)?;
        std::fs::rename(&tmp, &p)?;
        Ok(())
    }
    fn get(&self, key: &str) -> Result<Vec<u8>> {
        let p = self.path(key)?;
        std::fs::read(&p).with_context(|| format!("read {}", p.display()))
    }
    fn list(&self, prefix: &str) -> Result<Vec<String>> {
        let p = self.path(prefix)?;
        let mut out: Vec<String> = match std::fs::read_dir(&p) {
            Ok(d) => d.flatten().map(|e| e.file_name().to_string_lossy().into_owned()).collect(),
            Err(e) if e.kind() == std::io::ErrorKind::NotFound => Vec::new(),
            Err(e) => return Err(e.into()),
        };
        out.sort();
        Ok(out)
    }
    fn remove(&self, key: &str) -> Result<()> {
        let p = self.path(key)?;
        if p.is_dir() {
            std::fs::remove_dir_all(p)?;
        } else if p.exists() {
            std::fs::remove_file(p)?;
        }
        Ok(())
    }
}

/// A Cloud Storage bucket, reached keylessly (docs/backups.md §3, §6):
/// the hub mints a short token as `backup:OWNER`, Google's STS exchanges
/// it for an access token through the owner's workload identity
/// provider, and that writes the bucket. No key exists anywhere; the
/// access token lasts an hour and is fetched again before it runs out.
pub struct Gcs {
    bucket: String,
    /// Keys go under this, when set.
    prefix: String,
    storage: String,
    sts: String,
    /// The provider's resource name, `//iam.googleapis.com/projects/…`.
    provider: String,
    subject: String,
    app: Shared,
    client: reqwest::Client,
    rt: tokio::runtime::Handle,
    token: std::sync::Mutex<Option<(String, i64)>>,
}

impl Gcs {
    pub fn new(app: &Shared, s: &Setting) -> Gcs {
        Gcs {
            bucket: s.target.clone(),
            prefix: s.prefix.trim_matches('/').to_string(),
            storage: app.config.backups.storage_url.trim_end_matches('/').to_string(),
            sts: app.config.backups.sts_url.trim_end_matches('/').to_string(),
            provider: s.provider.clone(),
            subject: format!("backup:{}", s.owner),
            app: app.clone(),
            client: reqwest::Client::builder().timeout(std::time::Duration::from_secs(300)).build().unwrap_or_default(),
            rt: tokio::runtime::Handle::current(),
            token: std::sync::Mutex::new(None),
        }
    }

    fn name(&self, key: &str) -> String {
        if self.prefix.is_empty() {
            key.to_string()
        } else {
            format!("{}/{key}", self.prefix)
        }
    }

    /// An access token, exchanged for a fresh one of the hub's when the
    /// last is within five minutes of running out.
    fn access(&self) -> Result<String> {
        let now = db::now_ms();
        if let Some((t, until)) = self.token.lock().unwrap().as_ref() {
            if *until - now > 300_000 {
                return Ok(t.clone());
            }
        }
        let (token, expires_in) = self.rt.block_on(async {
            let issuer = self.app.oidc().await?;
            // Google's default audience for a provider: its name over https.
            let audience = format!("https:{}", self.provider);
            let jwt = issuer.mint_for(self.app.config.base_url(), &self.subject, &audience, db::now_ms(), 600);
            let res = self
                .client
                .post(format!("{}/v1/token", self.sts))
                .json(&serde_json::json!({
                    "grantType": "urn:ietf:params:oauth:grant-type:token-exchange",
                    "audience": self.provider,
                    "scope": "https://www.googleapis.com/auth/devstorage.read_write",
                    "requestedTokenType": "urn:ietf:params:oauth:token-type:access_token",
                    "subjectToken": jwt,
                    "subjectTokenType": "urn:ietf:params:oauth:token-type:jwt",
                }))
                .send()
                .await?;
            let status = res.status();
            let body: serde_json::Value = res.json().await.unwrap_or_default();
            if !status.is_success() {
                bail!(
                    "Google's token exchange refused {}: {} (check the provider's issuer is this hub's address and its attribute condition admits backup:)",
                    self.subject,
                    body["error_description"].as_str().or(body["error"].as_str()).unwrap_or("no reason given")
                );
            }
            let token = body["access_token"].as_str().context("the token exchange gave no access token")?.to_string();
            anyhow::Ok((token, body["expires_in"].as_i64().unwrap_or(3600)))
        })?;
        *self.token.lock().unwrap() = Some((token.clone(), now + expires_in * 1000));
        Ok(token)
    }

    fn object_url(&self, key: &str) -> Result<reqwest::Url> {
        let mut u = reqwest::Url::parse(&format!("{}/storage/v1/b/{}/o", self.storage, self.bucket))?;
        u.path_segments_mut().map_err(|_| anyhow::anyhow!("bad storage URL"))?.push(&self.name(key));
        Ok(u)
    }

    fn refused(&self, what: &str, status: reqwest::StatusCode, body: &str) -> anyhow::Error {
        let hint = if status == reqwest::StatusCode::FORBIDDEN || status == reqwest::StatusCode::UNAUTHORIZED {
            format!(" (grant roles/storage.objectAdmin on gs://{} to the principal …/subject/{})", self.bucket, self.subject)
        } else {
            String::new()
        };
        anyhow::anyhow!("GCS {what}: {status}{hint}: {}", body.chars().take(200).collect::<String>())
    }

    /// Every object name under `full` (no delimiter), for removal.
    fn all_under(&self, full: &str) -> Result<Vec<String>> {
        let mut out = Vec::new();
        let mut page: Option<String> = None;
        loop {
            let token = self.access()?;
            let mut u = reqwest::Url::parse(&format!("{}/storage/v1/b/{}/o", self.storage, self.bucket))?;
            u.query_pairs_mut().append_pair("prefix", full).append_pair("fields", "items(name),nextPageToken");
            if let Some(p) = &page {
                u.query_pairs_mut().append_pair("pageToken", p);
            }
            let body: serde_json::Value = self.rt.block_on(async {
                let res = self.client.get(u).bearer_auth(&token).send().await?;
                let status = res.status();
                let text = res.text().await?;
                if !status.is_success() {
                    return Err(self.refused("list", status, &text));
                }
                anyhow::Ok(serde_json::from_str(&text)?)
            })?;
            out.extend(body["items"].as_array().into_iter().flatten().filter_map(|i| i["name"].as_str().map(String::from)));
            match body["nextPageToken"].as_str() {
                Some(p) => page = Some(p.to_string()),
                None => return Ok(out),
            }
        }
    }
}

/// An S3 bucket, written keylessly (§3): the hub's own short-lived token
/// (`sub = backup:OWNER`, audience `sts.amazonaws.com`) is exchanged at AWS
/// STS (AssumeRoleWithWebIdentity) for an hour's credentials of the role
/// the owner names, and they sign each request (Signature Version 4).
pub struct S3 {
    bucket: String,
    prefix: String,
    region: String,
    /// The bucket's endpoint: scheme, host and any path before keys.
    base: reqwest::Url,
    sts: String,
    /// The IAM role's ARN.
    role: String,
    subject: String,
    app: Shared,
    client: reqwest::Client,
    rt: tokio::runtime::Handle,
    creds: std::sync::Mutex<Option<Creds>>,
}

#[derive(Clone)]
struct Creds {
    id: String,
    secret: String,
    token: String,
    until: i64,
}

/// The audience AWS expects of a web identity token.
pub const AWS_AUDIENCE: &str = "sts.amazonaws.com";

/// Percent-encoding as AWS signs it: everything but unreserved characters,
/// and `/` too unless `keep_slash`.
pub fn aws_encode(s: &str, keep_slash: bool) -> String {
    let mut out = String::new();
    for b in s.bytes() {
        match b {
            b'A'..=b'Z' | b'a'..=b'z' | b'0'..=b'9' | b'-' | b'_' | b'.' | b'~' => out.push(b as char),
            b'/' if keep_slash => out.push('/'),
            _ => out.push_str(&format!("%{b:02X}")),
        }
    }
    out
}

fn hmac(key: &[u8], data: &str) -> Vec<u8> {
    use hmac::Mac;
    let mut m = hmac::Hmac::<sha2::Sha256>::new_from_slice(key).expect("any key length");
    m.update(data.as_bytes());
    m.finalize().into_bytes().to_vec()
}

fn sha256_hex(data: &[u8]) -> String {
    use sha2::Digest;
    hex::encode(sha2::Sha256::digest(data))
}

/// AWS Signature Version 4: the `Authorization` header for one request.
/// `uri` is the path as encoded on the wire, `query` the decoded pairs,
/// `headers` the signed ones (any case), `payload` the body's SHA-256 in
/// hex, `amz_date` as `20130524T000000Z`.
#[allow(clippy::too_many_arguments)]
pub fn sigv4(
    method: &str,
    uri: &str,
    query: &[(String, String)],
    headers: &[(String, String)],
    payload: &str,
    (id, secret): (&str, &str),
    region: &str,
    service: &str,
    amz_date: &str,
) -> String {
    let mut q: Vec<(String, String)> = query.iter().map(|(k, v)| (aws_encode(k, false), aws_encode(v, false))).collect();
    q.sort();
    let query = q.iter().map(|(k, v)| format!("{k}={v}")).collect::<Vec<_>>().join("&");
    let mut h: Vec<(String, String)> = headers.iter().map(|(k, v)| (k.to_ascii_lowercase(), v.trim().to_string())).collect();
    h.sort();
    let canonical_headers: String = h.iter().map(|(k, v)| format!("{k}:{v}\n")).collect();
    let signed = h.iter().map(|(k, _)| k.as_str()).collect::<Vec<_>>().join(";");
    let request = format!("{method}\n{uri}\n{query}\n{canonical_headers}\n{signed}\n{payload}");
    let date = &amz_date[..8];
    let scope = format!("{date}/{region}/{service}/aws4_request");
    let to_sign = format!("AWS4-HMAC-SHA256\n{amz_date}\n{scope}\n{}", sha256_hex(request.as_bytes()));
    let key = hmac(&hmac(&hmac(&hmac(format!("AWS4{secret}").as_bytes(), date), region), service), "aws4_request");
    let signature = hex::encode(hmac(&key, &to_sign));
    format!("AWS4-HMAC-SHA256 Credential={id}/{scope}, SignedHeaders={signed}, Signature={signature}")
}

/// The text of the first `<tag>` in `xml`, unescaped.
fn xml_text(xml: &str, tag: &str) -> Option<String> {
    xml_blocks(xml, tag).into_iter().next().map(xml_unescape)
}

/// The inside of every `<tag>…</tag>` in `xml`.
fn xml_blocks<'a>(xml: &'a str, tag: &str) -> Vec<&'a str> {
    let (open, close) = (format!("<{tag}>"), format!("</{tag}>"));
    let mut out = Vec::new();
    let mut rest = xml;
    while let Some(i) = rest.find(&open) {
        let after = &rest[i + open.len()..];
        let Some(j) = after.find(&close) else { break };
        out.push(&after[..j]);
        rest = &after[j + close.len()..];
    }
    out
}

fn xml_unescape(s: &str) -> String {
    s.replace("&lt;", "<").replace("&gt;", ">").replace("&quot;", "\"").replace("&apos;", "'").replace("&amp;", "&")
}

fn amz_date(ms: i64) -> String {
    let t = time::OffsetDateTime::from_unix_timestamp_nanos(ms as i128 * 1_000_000).unwrap_or(time::OffsetDateTime::UNIX_EPOCH);
    format!("{:04}{:02}{:02}T{:02}{:02}{:02}Z", t.year(), u8::from(t.month()), t.day(), t.hour(), t.minute(), t.second())
}

impl S3 {
    pub fn new(app: &Shared, s: &Setting) -> S3 {
        let url = app.config.backups.s3_url.replace("{bucket}", &s.target).replace("{region}", &s.region);
        S3 {
            bucket: s.target.clone(),
            prefix: s.prefix.trim_matches('/').to_string(),
            region: s.region.clone(),
            base: reqwest::Url::parse(url.trim_end_matches('/')).unwrap_or_else(|_| reqwest::Url::parse("https://invalid.").unwrap()),
            sts: app.config.backups.aws_sts_url.trim_end_matches('/').to_string(),
            role: s.provider.clone(),
            subject: format!("backup:{}", s.owner),
            app: app.clone(),
            client: reqwest::Client::builder().timeout(std::time::Duration::from_secs(300)).build().unwrap_or_default(),
            rt: tokio::runtime::Handle::current(),
            creds: std::sync::Mutex::new(None),
        }
    }

    fn name(&self, key: &str) -> String {
        if self.prefix.is_empty() {
            key.to_string()
        } else {
            format!("{}/{key}", self.prefix)
        }
    }

    /// Credentials of the owner's role, exchanged again when the last are
    /// within five minutes of running out.
    fn creds(&self) -> Result<Creds> {
        let now = db::now_ms();
        if let Some(c) = self.creds.lock().unwrap().as_ref() {
            if c.until - now > 300_000 {
                return Ok(c.clone());
            }
        }
        let session: String = format!("oxygenhub-{}", self.subject.trim_start_matches("backup:"))
            .chars()
            .filter(|c| c.is_ascii_alphanumeric() || "=,.@-_".contains(*c))
            .take(64)
            .collect();
        let c = self.rt.block_on(async {
            let issuer = self.app.oidc().await?;
            let jwt = issuer.mint_for(self.app.config.base_url(), &self.subject, AWS_AUDIENCE, db::now_ms(), 600);
            let res = self
                .client
                .post(format!("{}/", self.sts))
                .form(&[
                    ("Action", "AssumeRoleWithWebIdentity"),
                    ("Version", "2011-06-15"),
                    ("RoleArn", self.role.as_str()),
                    ("RoleSessionName", session.as_str()),
                    ("WebIdentityToken", jwt.as_str()),
                    ("DurationSeconds", "3600"),
                ])
                .send()
                .await?;
            let status = res.status();
            let text = res.text().await.unwrap_or_default();
            if !status.is_success() {
                bail!(
                    "AWS STS refused {} for {}: {} (check the role's trust policy: this hub's address as its OIDC provider, audience {AWS_AUDIENCE}, and sub {})",
                    self.subject,
                    self.role,
                    xml_text(&text, "Message").unwrap_or_else(|| status.to_string()),
                    self.subject
                );
            }
            let get = |t: &str| xml_text(&text, t).with_context(|| format!("AWS STS gave no {t}"));
            anyhow::Ok(Creds { id: get("AccessKeyId")?, secret: get("SecretAccessKey")?, token: get("SessionToken")?, until: now + 3_600_000 })
        })?;
        *self.creds.lock().unwrap() = Some(c.clone());
        Ok(c)
    }

    /// One signed request: `key` is an object's (none for the bucket).
    fn send(
        &self,
        method: reqwest::Method,
        key: Option<&str>,
        query: &[(String, String)],
        body: Vec<u8>,
    ) -> Result<(reqwest::StatusCode, Vec<u8>)> {
        let c = self.creds()?;
        let base_path = self.base.path().trim_end_matches('/');
        let uri = match key {
            Some(k) => format!("{base_path}/{}", aws_encode(&self.name(k), true)),
            None => format!("{base_path}/"),
        };
        let host = match self.base.port() {
            Some(p) => format!("{}:{p}", self.base.host_str().unwrap_or_default()),
            None => self.base.host_str().unwrap_or_default().to_string(),
        };
        let payload = sha256_hex(&body);
        let date = amz_date(db::now_ms());
        let headers = vec![
            ("host".to_string(), host.clone()),
            ("x-amz-content-sha256".to_string(), payload.clone()),
            ("x-amz-date".to_string(), date.clone()),
            ("x-amz-security-token".to_string(), c.token.clone()),
        ];
        let auth = sigv4(method.as_str(), &uri, query, &headers, &payload, (&c.id, &c.secret), &self.region, "s3", &date);
        let mut q: Vec<(String, String)> = query.iter().map(|(k, v)| (aws_encode(k, false), aws_encode(v, false))).collect();
        q.sort();
        let qs = q.iter().map(|(k, v)| format!("{k}={v}")).collect::<Vec<_>>().join("&");
        let url = format!("{}://{host}{uri}{}{qs}", self.base.scheme(), if qs.is_empty() { "" } else { "?" });
        self.rt.block_on(async {
            let mut req = self
                .client
                .request(method, &url)
                .header("authorization", auth)
                .header("x-amz-content-sha256", &payload)
                .header("x-amz-date", &date)
                .header("x-amz-security-token", &c.token);
            if !body.is_empty() {
                req = req.header("content-type", "application/octet-stream").body(body);
            }
            let res = req.send().await?;
            let status = res.status();
            anyhow::Ok((status, res.bytes().await?.to_vec()))
        })
    }

    fn refused(&self, what: &str, status: reqwest::StatusCode, body: &[u8]) -> anyhow::Error {
        let text = String::from_utf8_lossy(body);
        let hint = if status == reqwest::StatusCode::FORBIDDEN {
            format!(" (the role {} needs s3:GetObject, s3:PutObject, s3:DeleteObject and s3:ListBucket on {})", self.role, self.bucket)
        } else {
            String::new()
        };
        anyhow::anyhow!("S3 {what}: {status}{hint}: {}", xml_text(&text, "Message").unwrap_or_else(|| text.chars().take(200).collect()))
    }

    /// The keys under `full` (`delimited`: and the next level's prefixes).
    fn listing(&self, full: &str, delimited: bool) -> Result<(Vec<String>, Vec<String>)> {
        let (mut keys, mut prefixes) = (Vec::new(), Vec::new());
        let mut token: Option<String> = None;
        loop {
            let mut q = vec![("list-type".to_string(), "2".to_string()), ("prefix".to_string(), full.to_string())];
            if delimited {
                q.push(("delimiter".to_string(), "/".to_string()));
            }
            if let Some(t) = &token {
                q.push(("continuation-token".to_string(), t.clone()));
            }
            let (status, body) = self.send(reqwest::Method::GET, None, &q, Vec::new())?;
            if !status.is_success() {
                return Err(self.refused("list", status, &body));
            }
            let text = String::from_utf8_lossy(&body).into_owned();
            for c in xml_blocks(&text, "Contents") {
                keys.extend(xml_text(c, "Key"));
            }
            for c in xml_blocks(&text, "CommonPrefixes") {
                prefixes.extend(xml_text(c, "Prefix"));
            }
            match (xml_text(&text, "IsTruncated").as_deref(), xml_text(&text, "NextContinuationToken")) {
                (Some("true"), Some(t)) => token = Some(t),
                _ => return Ok((keys, prefixes)),
            }
        }
    }
}

impl Destination for S3 {
    fn exists(&self, key: &str) -> Result<bool> {
        let (status, body) = self.send(reqwest::Method::HEAD, Some(key), &[], Vec::new())?;
        match status {
            s if s.is_success() => Ok(true),
            reqwest::StatusCode::NOT_FOUND => Ok(false),
            s => Err(self.refused("read", s, &body)),
        }
    }
    fn put(&self, key: &str, bytes: &[u8]) -> Result<()> {
        let (status, body) = self.send(reqwest::Method::PUT, Some(key), &[], bytes.to_vec())?;
        if !status.is_success() {
            return Err(self.refused("write", status, &body));
        }
        Ok(())
    }
    fn get(&self, key: &str) -> Result<Vec<u8>> {
        let (status, body) = self.send(reqwest::Method::GET, Some(key), &[], Vec::new())?;
        if !status.is_success() {
            return Err(self.refused(&format!("read {key}"), status, &body));
        }
        Ok(body)
    }
    fn list(&self, prefix: &str) -> Result<Vec<String>> {
        let full = format!("{}/", self.name(prefix.trim_end_matches('/')));
        let (keys, prefixes) = self.listing(&full, true)?;
        let mut out: std::collections::BTreeSet<String> = keys.iter().map(|k| k.trim_start_matches(&full).to_string()).collect();
        out.extend(prefixes.iter().map(|p| p.trim_start_matches(&full).trim_end_matches('/').to_string()));
        Ok(out.into_iter().filter(|n| !n.is_empty()).collect())
    }
    fn remove(&self, key: &str) -> Result<()> {
        let full = self.name(key);
        let (mut keys, _) = self.listing(&format!("{full}/"), false)?;
        keys.push(full);
        for k in keys {
            let rel = if self.prefix.is_empty() { k.clone() } else { k.trim_start_matches(&format!("{}/", self.prefix)).to_string() };
            let (status, body) = self.send(reqwest::Method::DELETE, Some(&rel), &[], Vec::new())?;
            if !status.is_success() && status != reqwest::StatusCode::NOT_FOUND {
                return Err(self.refused("remove", status, &body));
            }
        }
        Ok(())
    }
}

impl Destination for Gcs {
    fn exists(&self, key: &str) -> Result<bool> {
        let token = self.access()?;
        let mut u = self.object_url(key)?;
        u.query_pairs_mut().append_pair("fields", "name");
        self.rt.block_on(async {
            let res = self.client.get(u).bearer_auth(&token).send().await?;
            match res.status() {
                s if s.is_success() => Ok(true),
                reqwest::StatusCode::NOT_FOUND => Ok(false),
                s => Err(self.refused("read", s, &res.text().await.unwrap_or_default())),
            }
        })
    }
    fn put(&self, key: &str, bytes: &[u8]) -> Result<()> {
        let token = self.access()?;
        let mut u = reqwest::Url::parse(&format!("{}/upload/storage/v1/b/{}/o", self.storage, self.bucket))?;
        u.query_pairs_mut().append_pair("uploadType", "media").append_pair("name", &self.name(key));
        let body = bytes.to_vec();
        self.rt.block_on(async {
            let res = self.client.post(u).bearer_auth(&token).header("content-type", "application/octet-stream").body(body).send().await?;
            let status = res.status();
            if !status.is_success() {
                return Err(self.refused("write", status, &res.text().await.unwrap_or_default()));
            }
            Ok(())
        })
    }
    fn get(&self, key: &str) -> Result<Vec<u8>> {
        let token = self.access()?;
        let mut u = self.object_url(key)?;
        u.query_pairs_mut().append_pair("alt", "media");
        self.rt.block_on(async {
            let res = self.client.get(u).bearer_auth(&token).send().await?;
            let status = res.status();
            if !status.is_success() {
                return Err(self.refused(&format!("read {key}"), status, &res.text().await.unwrap_or_default()));
            }
            Ok(res.bytes().await?.to_vec())
        })
    }
    fn list(&self, prefix: &str) -> Result<Vec<String>> {
        let full = format!("{}/", self.name(prefix.trim_end_matches('/')));
        let mut out = std::collections::BTreeSet::new();
        let mut page: Option<String> = None;
        loop {
            let token = self.access()?;
            let mut u = reqwest::Url::parse(&format!("{}/storage/v1/b/{}/o", self.storage, self.bucket))?;
            u.query_pairs_mut()
                .append_pair("prefix", &full)
                .append_pair("delimiter", "/")
                .append_pair("fields", "items(name),prefixes,nextPageToken");
            if let Some(p) = &page {
                u.query_pairs_mut().append_pair("pageToken", p);
            }
            let body: serde_json::Value = self.rt.block_on(async {
                let res = self.client.get(u).bearer_auth(&token).send().await?;
                let status = res.status();
                let text = res.text().await?;
                if !status.is_success() {
                    return Err(self.refused("list", status, &text));
                }
                anyhow::Ok(serde_json::from_str(&text)?)
            })?;
            for n in body["items"].as_array().into_iter().flatten().filter_map(|i| i["name"].as_str()) {
                out.insert(n.trim_start_matches(&full).to_string());
            }
            for p in body["prefixes"].as_array().into_iter().flatten().filter_map(|p| p.as_str()) {
                out.insert(p.trim_start_matches(&full).trim_end_matches('/').to_string());
            }
            match body["nextPageToken"].as_str() {
                Some(p) => page = Some(p.to_string()),
                None => return Ok(out.into_iter().filter(|n| !n.is_empty()).collect()),
            }
        }
    }
    fn remove(&self, key: &str) -> Result<()> {
        let mut names = self.all_under(&format!("{}/", self.name(key)))?;
        names.push(self.name(key));
        for n in names {
            let token = self.access()?;
            let mut u = reqwest::Url::parse(&format!("{}/storage/v1/b/{}/o", self.storage, self.bucket))?;
            u.path_segments_mut().map_err(|_| anyhow::anyhow!("bad storage URL"))?.push(&n);
            self.rt.block_on(async {
                let res = self.client.delete(u).bearer_auth(&token).send().await?;
                match res.status() {
                    s if s.is_success() || s == reqwest::StatusCode::NOT_FOUND => Ok(()),
                    s => Err(self.refused("delete", s, &res.text().await.unwrap_or_default())),
                }
            })?;
        }
        Ok(())
    }
}

/// Check a destination end to end: write a probe, read it back, remove it.
pub fn probe(dest: &dyn Destination) -> Result<()> {
    let marker = format!("probe {}", db::now_ms());
    dest.put(".oxyhub-probe", marker.as_bytes())?;
    if dest.get(".oxyhub-probe")? != marker.as_bytes() {
        bail!("the probe read back differently");
    }
    dest.remove(".oxyhub-probe")
}

/// The owner's destination, from its setting and the site's rules.
pub fn destination(app: &Shared, s: &Setting) -> Result<Box<dyn Destination>> {
    match s.destination.as_str() {
        "dir" => {
            let allowed = &app.config.backups.directories;
            let target = PathBuf::from(&s.target);
            if !allowed.contains(&target) {
                bail!("{} is not a backup directory this hub allows (hub.toml [backups] directories)", s.target);
            }
            let mut root = target.join(&s.owner);
            if !s.prefix.is_empty() {
                root = root.join(s.prefix.trim_matches('/'));
            }
            Ok(Box::new(Directory { root }))
        }
        "gcs" => {
            if s.target.is_empty() || s.provider.is_empty() {
                bail!("a GCS destination needs its bucket and its workload identity provider");
            }
            Ok(Box::new(Gcs::new(app, s)))
        }
        "s3" => {
            if s.target.is_empty() || s.provider.is_empty() || s.region.is_empty() {
                bail!("an S3 destination needs its bucket, its region and the IAM role the hub assumes");
            }
            Ok(Box::new(S3::new(app, s)))
        }
        other => bail!("unknown destination {other:?}"),
    }
}

// ---------------------------------------------------------------- what

/// One file of a repository's store, in a manifest.
#[derive(Clone, Debug, Serialize, Deserialize, PartialEq, Eq)]
pub struct File {
    pub path: String,
    pub size: u64,
    /// Its modification time in nanoseconds: unchanged size and time mean
    /// unchanged content, so it is not hashed again.
    pub mtime: i128,
    pub hash: String,
}

/// A repository at one run.
#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct Manifest {
    pub owner: String,
    pub name: String,
    /// `repos` or `wikis`.
    pub kind: String,
    pub files: Vec<File>,
}

fn blob_key(hash: &str) -> String {
    format!("blobs/{}/{hash}", &hash[..2])
}

/// The large files that never change once written come first.
fn immutable(path: &str) -> bool {
    path.starts_with(".oxy/objects/") && (path.contains("/pack-") || path.contains("/loose/"))
}

#[derive(Default)]
struct Sent {
    files: i64,
    sent: i64,
    bytes: i64,
}

/// Walk `dir`, sending each file the destination lacks; `known` says which
/// paths are unchanged since the last run (and their hashes).
fn copy_dir(dest: &dyn Destination, dir: &Path, known: &HashMap<String, File>, only_immutable: bool, sent: &mut Sent) -> Result<Vec<File>> {
    let mut out = Vec::new();
    let mut stack = vec![dir.to_path_buf()];
    while let Some(d) = stack.pop() {
        let entries = match std::fs::read_dir(&d) {
            Ok(e) => e,
            Err(e) if e.kind() == std::io::ErrorKind::NotFound => continue,
            Err(e) => return Err(e.into()),
        };
        for e in entries.flatten() {
            let p = e.path();
            let ft = e.file_type()?;
            if ft.is_dir() {
                stack.push(p);
                continue;
            }
            if !ft.is_file() {
                continue;
            }
            let rel = p.strip_prefix(dir).unwrap_or(&p).to_string_lossy().replace('\\', "/");
            if only_immutable && !immutable(&rel) {
                continue;
            }
            // A file packed away while the walk ran is simply gone.
            let Ok(md) = std::fs::metadata(&p) else { continue };
            let mtime =
                md.modified().ok().and_then(|t| t.duration_since(std::time::UNIX_EPOCH).ok()).map(|d| d.as_nanos() as i128).unwrap_or(0);
            let size = md.len();
            sent.files += 1;
            if let Some(k) = known.get(&rel).filter(|k| k.size == size && k.mtime == mtime) {
                out.push(k.clone());
                continue;
            }
            let Ok(bytes) = std::fs::read(&p) else { continue };
            let hash = blake3::hash(&bytes).to_hex().to_string();
            let key = blob_key(&hash);
            if !dest.exists(&key)? {
                dest.put(&key, &bytes)?;
                sent.sent += 1;
                sent.bytes += bytes.len() as i64;
            }
            out.push(File { path: rel, size, mtime, hash });
        }
    }
    out.sort_by(|a, b| a.path.cmp(&b.path));
    Ok(out)
}

// ---------------------------------------------------------------- records

/// Tables and columns never written: secrets, credentials, sessions.
fn private_table(t: &str) -> bool {
    ["secret", "token", "session", "password", "totp", "recovery", "sqlx"].iter().any(|w| t.contains(w))
}

fn private_column(c: &str) -> bool {
    ["secret", "token", "password", "salt", "totp", "sealed", "hash_key"].iter().any(|w| c.contains(w))
}

async fn tables(pool: &Pool) -> Result<Vec<String>> {
    let mut t: Vec<String> =
        sqlx::query_scalar("SELECT name FROM sqlite_master WHERE type = 'table' AND name NOT LIKE 'sqlite_%'").fetch_all(pool).await?;
    t.retain(|t| !private_table(t));
    t.sort();
    Ok(t)
}

async fn columns(pool: &Pool, table: &str) -> Result<Vec<String>> {
    Ok(sqlx::query_scalar(&format!("SELECT name FROM pragma_table_info('{table}')")).fetch_all(pool).await?)
}

/// The rows of `table` matching `cond`, as a JSON array, private columns
/// left out and blobs as hex.
async fn rows(pool: &Pool, table: &str, cond: &str) -> Result<serde_json::Value> {
    let cols = columns(pool, table).await?;
    let fields: Vec<String> = cols
        .iter()
        .filter(|c| !private_column(c))
        .map(|c| format!("'{c}', CASE WHEN typeof(\"{c}\") = 'blob' THEN hex(\"{c}\") ELSE \"{c}\" END"))
        .collect();
    if fields.is_empty() {
        return Ok(serde_json::json!([]));
    }
    let sql = format!("SELECT json_group_array(json_object({})) FROM \"{table}\" WHERE {cond}", fields.join(", "));
    let text: String = sqlx::query_scalar(&sql).fetch_one(pool).await?;
    Ok(serde_json::from_str(&text)?)
}

/// Every row about something: the tables with column `key` equal to `id`,
/// then, three levels deep, the tables whose foreign keys point at rows
/// already taken (an issue's comments, a proposal's reviews and their
/// threads).
async fn records(pool: &Pool, key: &str, id: i64) -> Result<serde_json::Value> {
    let all = tables(pool).await?;
    let mut conds: Vec<(String, String)> = Vec::new();
    for t in &all {
        if columns(pool, t).await?.iter().any(|c| c == key) {
            conds.push((t.clone(), format!("\"{key}\" = {id}")));
        }
    }
    for _ in 0..3 {
        let mut more = Vec::new();
        for t in &all {
            if conds.iter().any(|(c, _)| c == t) || more.iter().any(|(c, _): &(String, String)| c == t) {
                continue;
            }
            let fks: Vec<(String, String, String)> =
                sqlx::query_as(&format!("SELECT \"table\", \"from\", \"to\" FROM pragma_foreign_key_list('{t}')")).fetch_all(pool).await?;
            if let Some((parent, from, to, pcond)) = fks
                .iter()
                .find_map(|(p, f, to)| conds.iter().find(|(c, _)| c == p).map(|(_, pc)| (p.clone(), f.clone(), to.clone(), pc.clone())))
            {
                more.push((t.clone(), format!("\"{from}\" IN (SELECT \"{to}\" FROM \"{parent}\" WHERE {pcond})")));
            }
        }
        if more.is_empty() {
            break;
        }
        conds.extend(more);
    }
    let mut out = serde_json::Map::new();
    for (t, cond) in conds {
        let r = rows(pool, &t, &cond).await?;
        if r.as_array().is_some_and(|a| !a.is_empty()) {
            out.insert(t, r);
        }
    }
    Ok(serde_json::Value::Object(out))
}

/// The key of a run's records naming the accounts, teams and organisations
/// their rows point at, by id: `{"accounts": {"7": "andy"}, …}`.
const NAMES: &str = "_names";

/// Tables a restore leaves out: the search index (rebuilt from what is
/// restored), and what is passing or personal rather than the
/// repository's: inboxes, webhook deliveries, runners' declines.
const NOT_RESTORED: [&str; 5] = ["search", "notifications", "deliveries", "flow_declines", NAMES];

async fn fk_list(pool: &Pool, table: &str) -> Result<Vec<(String, String, String)>> {
    Ok(sqlx::query_as(&format!("SELECT \"table\", \"from\", \"to\" FROM pragma_foreign_key_list('{table}')")).fetch_all(pool).await?)
}

/// The names behind the account, team and organisation ids that `rec`'s
/// rows point at, so a restore on another hub finds them again by name.
async fn names_of(pool: &Pool, rec: &serde_json::Value) -> Result<serde_json::Value> {
    let mut ids: HashMap<String, std::collections::BTreeSet<i64>> = HashMap::new();
    for (table, rows) in rec.as_object().into_iter().flatten() {
        let Some(rows) = rows.as_array() else { continue };
        for (parent, from, _) in fk_list(pool, table).await? {
            if ["accounts", "teams", "organisations"].contains(&parent.as_str()) {
                ids.entry(parent).or_default().extend(rows.iter().filter_map(|r| r[&from].as_i64()));
            }
        }
    }
    let mut out = serde_json::Map::new();
    for (kind, sql) in [
        ("accounts", "SELECT id, username FROM accounts WHERE id = ?"),
        ("organisations", "SELECT id, name FROM organisations WHERE id = ?"),
        ("teams", "SELECT t.id, o.name || '/' || t.name FROM teams t JOIN organisations o ON o.id = t.org_id WHERE t.id = ?"),
    ] {
        let mut m = serde_json::Map::new();
        for id in ids.get(kind).into_iter().flatten() {
            if let Some((id, name)) = sqlx::query_as::<_, (i64, String)>(sql).bind(id).fetch_optional(pool).await? {
                m.insert(id.to_string(), name.into());
            }
        }
        out.insert(kind.into(), m.into());
    }
    Ok(out.into())
}

/// The id `name` has on this hub as one of `_names`' kinds.
async fn id_by_name(pool: &Pool, kind: &str, name: &str) -> Result<Option<i64>> {
    Ok(match kind {
        "accounts" => sqlx::query_scalar("SELECT id FROM accounts WHERE username = ?").bind(name).fetch_optional(pool).await?,
        "organisations" => sqlx::query_scalar("SELECT id FROM organisations WHERE name = ?").bind(name).fetch_optional(pool).await?,
        "teams" => match name.split_once('/') {
            Some((org, team)) => {
                sqlx::query_scalar("SELECT t.id FROM teams t JOIN organisations o ON o.id = t.org_id WHERE o.name = ? AND t.name = ?")
                    .bind(org)
                    .bind(team)
                    .fetch_optional(pool)
                    .await?
            }
            None => None,
        },
        _ => None,
    })
}

/// One column of a table on this hub.
struct Col {
    name: String,
    ty: String,
    notnull: bool,
    default: Option<String>,
    pk: i64,
}

async fn table_cols(pool: &Pool, table: &str) -> Result<Vec<Col>> {
    let rows: Vec<(String, String, i64, Option<String>, i64)> =
        sqlx::query_as(&format!("SELECT name, type, \"notnull\", dflt_value, pk FROM pragma_table_info('{table}')"))
            .fetch_all(pool)
            .await?;
    Ok(rows.into_iter().map(|(name, ty, notnull, default, pk)| Col { name, ty, notnull: notnull != 0, default, pk }).collect())
}

/// Bind one value of a backed-up row: blobs were written as hex.
fn bind_json<'q>(
    q: sqlx::query::Query<'q, sqlx::Sqlite, sqlx::sqlite::SqliteArguments<'q>>,
    v: serde_json::Value,
    blob: bool,
) -> sqlx::query::Query<'q, sqlx::Sqlite, sqlx::sqlite::SqliteArguments<'q>> {
    match v {
        serde_json::Value::Null => q.bind(None::<i64>),
        serde_json::Value::Bool(b) => q.bind(b as i64),
        serde_json::Value::Number(n) => match n.as_i64() {
            Some(i) => q.bind(i),
            None => q.bind(n.as_f64().unwrap_or(0.0)),
        },
        serde_json::Value::String(s) if blob => q.bind(hex::decode(&s).unwrap_or_else(|_| s.into_bytes())),
        serde_json::Value::String(s) => q.bind(s),
        other => q.bind(other.to_string()),
    }
}

/// Restore one repository's records from a run into this hub, the
/// repository being `repo` here and `old` in the backup (docs/backups.md
/// §7): its issues, proposals, labels, milestones, releases and their
/// assets, checks, Flow runs and the rest, each table after the tables it
/// points at, every id mapped to its new one and every account, team and
/// organisation found again by name. A row pointing at an account this
/// hub lacks keeps a blank reference where it may, and is left out where
/// it may not. What needs re-entering (webhook secrets, never backed up)
/// and what was left out come back as notes.
async fn restore_records(
    app: &Shared,
    dest: &std::sync::Arc<dyn Destination>,
    rec: &serde_json::Value,
    old: i64,
    repo: i64,
) -> Result<Vec<String>> {
    let pool = &app.db;
    let obj = rec.as_object().context("the records are not an object")?;
    let mut by_name: HashMap<(String, i64), Option<i64>> = HashMap::new();
    for (kind, m) in obj.get(NAMES).and_then(|n| n.as_object()).into_iter().flatten() {
        for (id, name) in m.as_object().into_iter().flatten() {
            let (Ok(id), Some(name)) = (id.parse::<i64>(), name.as_str()) else { continue };
            by_name.insert((kind.clone(), id), id_by_name(pool, kind, name).await?);
        }
    }
    let here: std::collections::HashSet<String> = tables(pool).await?.into_iter().collect();
    let mut notes = Vec::new();
    let mut todo: Vec<String> = Vec::new();
    for t in obj.keys().filter(|t| t.as_str() != "repositories" && !NOT_RESTORED.contains(&t.as_str())) {
        if here.contains(t) {
            todo.push(t.clone());
        } else {
            notes.push(format!("{t}: not a table on this hub, left out"));
        }
    }
    let mut fks: HashMap<String, Vec<(String, String, String)>> = HashMap::new();
    for t in &todo {
        fks.insert(t.clone(), fk_list(pool, t).await?);
    }
    // Each table after the tables of the records it points at.
    let mut order = Vec::new();
    while !todo.is_empty() {
        let mut ready: Vec<String> =
            todo.iter().filter(|t| fks[*t].iter().all(|(p, _, _)| p == *t || !todo.contains(p))).cloned().collect();
        if ready.is_empty() {
            ready.push(todo[0].clone());
        }
        todo.retain(|t| !ready.contains(t));
        order.extend(ready);
    }
    let mut maps: HashMap<String, HashMap<i64, i64>> = HashMap::new();
    maps.insert("repositories".into(), [(old, repo)].into());
    let mut left_out: std::collections::BTreeMap<String, usize> = Default::default();
    let mut tx = pool.begin().await?;
    for table in &order {
        let cols = table_cols(pool, table).await?;
        let keys: Vec<&str> = cols.iter().filter(|c| c.pk > 0).map(|c| c.name.as_str()).collect();
        let by_id = keys == ["id"] && cols.iter().any(|c| c.name == "id" && c.ty.eq_ignore_ascii_case("INTEGER"));
        let verb = if keys == ["repo_id"] {
            "INSERT OR REPLACE"
        } else if by_id {
            "INSERT"
        } else {
            "INSERT OR IGNORE"
        };
        let mut rows: Vec<&serde_json::Map<String, serde_json::Value>> =
            obj[table].as_array().into_iter().flatten().filter_map(|r| r.as_object()).collect();
        rows.sort_by_key(|r| r.get("id").and_then(|v| v.as_i64()).unwrap_or(0));
        'row: for row in rows {
            let (mut names, mut values) = (Vec::new(), Vec::new());
            for c in &cols {
                if by_id && c.name == "id" {
                    continue;
                }
                let mut v = row.get(&c.name).cloned().filter(|v| !v.is_null());
                if let Some((parent, _, _)) = fks[table].iter().find(|(_, from, _)| *from == c.name) {
                    if let Some(was) = v.as_ref().and_then(|v| v.as_i64()) {
                        let now = match parent.as_str() {
                            "accounts" | "teams" | "organisations" => by_name.get(&(parent.clone(), was)).copied().flatten(),
                            p => maps.get(p).and_then(|m| m.get(&was)).copied(),
                        };
                        if now.is_none() && c.notnull {
                            *left_out.entry(table.clone()).or_default() += 1;
                            continue 'row;
                        }
                        v = now.map(serde_json::Value::from);
                    }
                }
                let blob = c.ty.to_ascii_uppercase().contains("BLOB");
                match v {
                    Some(v) => {
                        names.push(c.name.clone());
                        values.push((v, blob));
                    }
                    // Never backed up (a secret): blank here, to enter again.
                    None if c.notnull && c.default.is_none() => {
                        names.push(c.name.clone());
                        let blank = if c.ty.to_ascii_uppercase().contains("INT") { serde_json::json!(0) } else { serde_json::json!("") };
                        values.push((blank, false));
                    }
                    None => {}
                }
            }
            let sql = format!(
                "{verb} INTO \"{table}\" ({}) VALUES ({})",
                names.iter().map(|n| format!("\"{n}\"")).collect::<Vec<_>>().join(", "),
                vec!["?"; names.len()].join(", ")
            );
            let mut q = sqlx::query(&sql);
            for (v, blob) in values {
                q = bind_json(q, v, blob);
            }
            let done = q.execute(&mut *tx).await.with_context(|| format!("restore a row of {table}"))?;
            if let (true, Some(was)) = (by_id, row.get("id").and_then(|v| v.as_i64())) {
                maps.entry(table.clone()).or_default().insert(was, done.last_insert_rowid());
            }
        }
    }
    tx.commit().await?;
    for (table, n) in left_out {
        notes.push(format!("{table}: {n} row(s) left out: they name accounts or rows this hub lacks"));
    }
    // Search finds what came back.
    for (kind, table) in [("issue", "issues"), ("proposal", "proposals")] {
        let found: Vec<(i64, i64, String, String)> =
            sqlx::query_as(&format!("SELECT id, number, title, body FROM {table} WHERE repo_id = ?")).bind(repo).fetch_all(pool).await?;
        for (id, number, title, body) in found {
            db::notify::index(pool, kind, repo, id, number, &title, &body).await?;
        }
    }
    // Webhook secrets were never written: they are entered again.
    let hooks: Vec<String> =
        sqlx::query_scalar("SELECT url FROM hooks WHERE repo_id = ? AND secret = ''").bind(repo).fetch_all(pool).await?;
    for url in hooks {
        notes.push(format!("webhook {url}: enter its secret again (Settings › Webhooks)"));
    }
    // Release assets, each checked against its name.
    for hash in obj.get("release_assets").and_then(|a| a.as_array()).into_iter().flatten().filter_map(|a| a["hash"].as_str()) {
        if hash.len() != 64 || !hash.bytes().all(|b| b.is_ascii_hexdigit()) {
            continue;
        }
        let path = crate::web::releases::blob_path(app, hash);
        if path.exists() {
            continue;
        }
        let got = tokio::task::block_in_place(|| dest.get(&blob_key(hash)));
        match got {
            Ok(bytes) if blake3::hash(&bytes).to_hex().as_str() == hash => {
                std::fs::create_dir_all(path.parent().context("no parent")?)?;
                std::fs::write(&path, &bytes)?;
            }
            Ok(_) => notes.push(format!("release asset {}: the copy does not match its hash", &hash[..12])),
            Err(_) => notes.push(format!("release asset {}: not in the backup", &hash[..12])),
        }
    }
    Ok(notes)
}

// ---------------------------------------------------------------- a run

fn run_name(ms: i64) -> String {
    let t = time::OffsetDateTime::from_unix_timestamp_nanos(ms as i128 * 1_000_000).unwrap_or(time::OffsetDateTime::UNIX_EPOCH);
    format!("{:04}{:02}{:02}T{:02}{:02}{:02}Z", t.year(), u8::from(t.month()), t.day(), t.hour(), t.minute(), t.second())
}

/// The last whole run's manifests, by `kind/name`.
fn last_manifests(dest: &dyn Destination) -> HashMap<String, HashMap<String, File>> {
    let mut out = HashMap::new();
    let Ok(at) = dest.get("LATEST").map(|b| String::from_utf8_lossy(&b).trim().to_string()) else { return out };
    for name in dest.list(&format!("runs/{at}/repos")).unwrap_or_default() {
        if let Ok(m) = dest.get(&format!("runs/{at}/repos/{name}")).and_then(|b| Ok(serde_json::from_slice::<Manifest>(&b)?)) {
            out.insert(format!("{}/{}", m.kind, m.name), m.files.into_iter().map(|f| (f.path.clone(), f)).collect());
        }
    }
    out
}

/// Back up `owner` now, as its setting says. The run is recorded whatever
/// happens; a failure notifies the owner once until a run succeeds.
pub async fn run(app: &Shared, owner: &str, trigger: &str) -> Result<Run> {
    let s = setting(&app.db, owner).await?.with_context(|| format!("{owner} has no backup set up"))?;
    let started = db::now_ms();
    let at = run_name(started);
    let id: i64 =
        sqlx::query_scalar("INSERT INTO backup_runs (owner, started_ms, status, at, trigger) VALUES (?, ?, 'running', ?, ?) RETURNING id")
            .bind(owner)
            .bind(started)
            .bind(&at)
            .bind(trigger)
            .fetch_one(&app.db)
            .await?;
    let outcome = run_into(app, &s, &at, trigger == "now").await;
    let (status, detail, sent) = match outcome {
        Ok((sent, problems)) if problems.is_empty() => ("ok", String::new(), sent),
        Ok((sent, problems)) => ("partial", problems.join("; "), sent),
        Err(e) => ("failed", format!("{e:#}"), (0, Sent::default())),
    };
    sqlx::query("UPDATE backup_runs SET finished_ms = ?, status = ?, detail = ?, repos = ?, files = ?, sent = ?, bytes = ? WHERE id = ?")
        .bind(db::now_ms())
        .bind(status)
        .bind(&detail)
        .bind(sent.0)
        .bind(sent.1.files)
        .bind(sent.1.sent)
        .bind(sent.1.bytes)
        .bind(id)
        .execute(&app.db)
        .await?;
    if status != "ok" {
        notify_failure(app, &s, status, &detail).await;
    }
    let r: Run = sqlx::query_as("SELECT * FROM backup_runs WHERE id = ?").bind(id).fetch_one(&app.db).await?;
    Ok(r)
}

async fn run_into(app: &Shared, s: &Setting, at: &str, by_hand: bool) -> Result<((i64, Sent), Vec<String>)> {
    let dest: std::sync::Arc<dyn Destination> = destination(app, s)?.into();
    let known = {
        let d = dest.clone();
        tokio::task::spawn_blocking(move || last_manifests(d.as_ref())).await?
    };
    // Its repositories, but those left out (§5).
    let mine: Vec<db::repos::RepoRow> =
        db::repos::list(&app.db).await?.into_iter().filter(|r| r.owner == s.owner && included(s, r, by_hand)).collect();
    let mut problems = Vec::new();
    let mut sent = Sent::default();
    let mut repos = 0i64;
    for row in &mine {
        let Some(name) = RepoName::new(&row.owner, &row.name) else { continue };
        for (kind, store) in [("repos", &app.repos), ("wikis", &app.wikis)] {
            if !store.exists(&name) {
                continue;
            }
            let dir = store.dir(&name);
            let k = known.get(&format!("{kind}/{}", row.name)).cloned().unwrap_or_default();
            // The large, unchanging files without the lock, then the whole
            // walk again under the read lock: pushes wait for that moment.
            let (d1, dir1, k1) = (dest.clone(), dir.clone(), k.clone());
            let first = tokio::task::spawn_blocking(move || {
                let mut s = Sent::default();
                copy_dir(d1.as_ref(), &dir1, &k1, true, &mut s).map(|f| (f, s))
            })
            .await?;
            let mut k2 = k;
            if let Ok((files, _)) = &first {
                for f in files {
                    k2.insert(f.path.clone(), f.clone());
                }
            }
            let guard = store.read_guard(&name).await;
            let (d2, dir2) = (dest.clone(), dir.clone());
            let second = tokio::task::spawn_blocking(move || {
                let _guard = guard;
                let mut s = Sent::default();
                copy_dir(d2.as_ref(), &dir2, &k2, false, &mut s).map(|f| (f, s))
            })
            .await?;
            match second {
                Ok((files, s2)) => {
                    let s1 = first.map(|(_, s)| s).unwrap_or_default();
                    sent.files += s2.files;
                    sent.sent += s1.sent + s2.sent;
                    sent.bytes += s1.bytes + s2.bytes;
                    let m = Manifest { owner: row.owner.clone(), name: row.name.clone(), kind: kind.into(), files };
                    let key = format!("runs/{at}/repos/{kind}-{}.json", row.name);
                    tokio::task::block_in_place(|| dest.put(&key, &serde_json::to_vec(&m)?))?;
                    if kind == "repos" {
                        repos += 1;
                    }
                }
                Err(e) => problems.push(format!("{}/{} ({kind}): {e:#}", row.owner, row.name)),
            }
        }
        let rec = async {
            let mut r = records(&app.db, "repo_id", row.id).await?;
            // The repository's own row, which restore recreates first, and
            // the names behind the accounts, teams and organisations its
            // rows point at, which another hub finds them by.
            let own = rows(&app.db, "repositories", &format!("id = {}", row.id)).await?;
            let names = names_of(&app.db, &r).await?;
            if let Some(m) = r.as_object_mut() {
                m.insert("repositories".into(), own);
                m.insert(NAMES.into(), names);
            }
            anyhow::Ok(r)
        };
        match rec.await {
            Ok(r) => {
                tokio::task::block_in_place(|| dest.put(&format!("runs/{at}/records/{}.json", row.name), &serde_json::to_vec(&r)?))?;
                // Release assets live beside the stores, named by their
                // BLAKE3: each sent once, as the stores' files are.
                for hash in r["release_assets"].as_array().into_iter().flatten().filter_map(|a| a["hash"].as_str()) {
                    if hash.len() != 64 || !hash.bytes().all(|b| b.is_ascii_hexdigit()) {
                        continue;
                    }
                    let path = crate::web::releases::blob_path(app, hash);
                    let key = blob_key(hash);
                    let put = tokio::task::block_in_place(|| -> Result<Option<i64>> {
                        if dest.exists(&key)? {
                            return Ok(None);
                        }
                        let bytes = std::fs::read(&path).with_context(|| format!("read release asset {}", &hash[..12]))?;
                        dest.put(&key, &bytes)?;
                        Ok(Some(bytes.len() as i64))
                    });
                    match put {
                        Ok(Some(n)) => {
                            sent.files += 1;
                            sent.sent += 1;
                            sent.bytes += n;
                        }
                        Ok(None) => sent.files += 1,
                        Err(e) => problems.push(format!("{}/{} release asset: {e:#}", row.owner, row.name)),
                    }
                }
            }
            Err(e) => problems.push(format!("{}/{} records: {e:#}", row.owner, row.name)),
        }
    }
    // The owner itself.
    let owner_rows = if s.kind == "org" {
        match db::accounts::org_by_name(&app.db, &s.owner).await? {
            Some(o) => records(&app.db, "org_id", o.id).await?,
            None => serde_json::json!({}),
        }
    } else {
        match db::accounts::account_by_name(&app.db, &s.owner).await? {
            Some(a) => records(&app.db, "account_id", a.id).await?,
            None => serde_json::json!({}),
        }
    };
    // The blocking calls of a destination (GCS drives its client on this
    // runtime) run where blocking is allowed.
    tokio::task::block_in_place(|| -> Result<()> {
        dest.put(&format!("runs/{at}/owner.json"), &serde_json::to_vec(&owner_rows)?)?;
        dest.put(&format!("runs/{at}/DONE"), at.as_bytes())?;
        dest.put("LATEST", at.as_bytes())?;
        prune(dest.as_ref(), s.keep_days)
    })?;
    Ok(((repos, sent), problems))
}

/// Drop whole runs older than `keep_days`, and the blobs no kept run
/// names. The newest whole run is always kept.
pub fn prune(dest: &dyn Destination, keep_days: i64) -> Result<()> {
    let cutoff = run_name(db::now_ms() - keep_days.max(1) * 86_400_000);
    let runs = dest.list("runs")?;
    let whole: Vec<&String> = runs.iter().filter(|r| dest.exists(&format!("runs/{r}/DONE")).unwrap_or(false)).collect();
    let newest = whole.last().map(|s| s.to_string());
    let mut removed = false;
    for r in &runs {
        if r.as_str() < cutoff.as_str() && Some(r.to_string()) != newest {
            dest.remove(&format!("runs/{r}"))?;
            removed = true;
        }
    }
    if !removed {
        return Ok(());
    }
    let mut wanted = std::collections::HashSet::new();
    for r in dest.list("runs")? {
        for m in dest.list(&format!("runs/{r}/repos"))? {
            if let Ok(m) = dest.get(&format!("runs/{r}/repos/{m}")).and_then(|b| Ok(serde_json::from_slice::<Manifest>(&b)?)) {
                wanted.extend(m.files.into_iter().map(|f| f.hash));
            }
        }
    }
    for shard in dest.list("blobs")? {
        for b in dest.list(&format!("blobs/{shard}"))? {
            if !wanted.contains(&b) {
                dest.remove(&format!("blobs/{shard}/{b}"))?;
            }
        }
    }
    Ok(())
}

async fn notify_failure(app: &Shared, s: &Setting, status: &str, detail: &str) {
    // Once per spell of failures: not when the run before failed too.
    let before: Option<String> =
        sqlx::query_scalar("SELECT status FROM backup_runs WHERE owner = ? AND finished_ms IS NOT NULL ORDER BY id DESC LIMIT 1 OFFSET 1")
            .bind(&s.owner)
            .fetch_optional(&app.db)
            .await
            .ok()
            .flatten();
    if before.as_deref().is_some_and(|b| b != "ok") {
        return;
    }
    let (who, url): (Vec<i64>, String) = if s.kind == "org" {
        match db::accounts::org_by_name(&app.db, &s.owner).await.ok().flatten() {
            Some(o) => (
                db::accounts::org_members(&app.db, o.id)
                    .await
                    .unwrap_or_default()
                    .into_iter()
                    .filter(|(_, r)| r == "owner")
                    .map(|(a, _)| a.id)
                    .collect(),
                format!("/orgs/{}/settings#backups", s.owner),
            ),
            None => return,
        }
    } else {
        match db::accounts::account_by_name(&app.db, &s.owner).await.ok().flatten() {
            Some(a) => (vec![a.id], "/settings/backups".into()),
            None => return,
        }
    };
    let title = format!("Backup of {} {status}: {}", s.owner, detail.chars().take(160).collect::<String>());
    for id in who {
        let _ = db::notify::add(
            &app.db,
            db::notify::New {
                account_id: id,
                repo_id: None,
                reason: db::notify::Reason::Participating,
                kind: "backup",
                title: &title,
                url: &url,
                actor: "",
            },
        )
        .await;
    }
}

/// Run each owner's backup when it is due, one at a time. A run left
/// "running" by a restart is marked failed first.
pub async fn scheduler(app: Shared) {
    let _ = sqlx::query(
        "UPDATE backup_runs SET status = 'failed', detail = 'the hub restarted during the run', finished_ms = ? WHERE status = 'running'",
    )
    .bind(db::now_ms())
    .execute(&app.db)
    .await;
    loop {
        tokio::time::sleep(std::time::Duration::from_secs(60)).await;
        for s in due(&app.db).await.unwrap_or_default() {
            if let Err(e) = run(&app, &s.owner, "schedule").await {
                tracing::warn!("backup of {}: {e:#}", s.owner);
            }
        }
    }
}

/// The owners whose next run is due now: by their own schedule, or by
/// the shortest schedule one of their repositories chose (§5). A run takes
/// every included repository and sends only what changed, so each run
/// stays whole and a restore point has everything.
pub async fn due(pool: &Pool) -> sqlx::Result<Vec<Setting>> {
    let all: Vec<Setting> = sqlx::query_as("SELECT * FROM backup_settings WHERE updated_ms > 0").fetch_all(pool).await?;
    let repos = db::repos::list(pool).await?;
    let now = db::now_ms();
    let mut out = Vec::new();
    for s in all {
        let theirs: Vec<db::repos::RepoRow> = repos.iter().filter(|r| r.owner == s.owner).cloned().collect();
        let Some(period) = period_with(&s, &theirs) else { continue };
        let last: Option<i64> =
            sqlx::query_scalar("SELECT MAX(started_ms) FROM backup_runs WHERE owner = ?").bind(&s.owner).fetch_one(pool).await?;
        if last.is_none_or(|l| now - l >= period * 1000) {
            out.push(s);
        }
    }
    Ok(out)
}

/// Restore every repository of the whole run `at` (the latest when none)
/// from `dest` into `repos_root/OWNER/NAME` and `wikis_root/…`, refusing to
/// overwrite one that exists. Each file is checked against its hash.
pub fn restore(dest: &dyn Destination, at: Option<&str>, repos_root: &Path, wikis_root: &Path) -> Result<Vec<String>> {
    let at = match at {
        Some(a) => a.to_string(),
        None => String::from_utf8_lossy(&dest.get("LATEST").context("no whole run at this destination")?).trim().to_string(),
    };
    if !dest.exists(&format!("runs/{at}/DONE"))? {
        bail!("run {at} is not whole (no DONE): pick another with --run");
    }
    let mut done = Vec::new();
    for name in dest.list(&format!("runs/{at}/repos"))? {
        let m: Manifest = serde_json::from_slice(&dest.get(&format!("runs/{at}/repos/{name}"))?)?;
        let root = if m.kind == "wikis" { wikis_root } else { repos_root };
        let dir = root.join(&m.owner).join(&m.name);
        if dir.exists() {
            bail!("{} exists: restore into an empty hub, or move it aside", dir.display());
        }
        for f in &m.files {
            let bytes = dest.get(&blob_key(&f.hash))?;
            if blake3::hash(&bytes).to_hex().as_str() != f.hash {
                bail!("{}/{} {}: the copy does not match its hash", m.owner, m.name, f.path);
            }
            let p = dir.join(&f.path);
            std::fs::create_dir_all(p.parent().context("no parent")?)?;
            std::fs::write(&p, &bytes)?;
        }
        done.push(format!("{}/{} ({})", m.owner, m.name, m.kind));
    }
    Ok(done)
}

/// Restore the whole run `at` (the latest when none) into this hub: each
/// repository's and wiki's store byte for byte, then its row and settings,
/// then its records (issues, proposals, releases and the rest), so it shows
/// on the hub as it was (docs/backups.md §7). What was restored, then any
/// notes (`note: …`) on what needs entering again or was left out.
pub async fn restore_into_hub(app: &Shared, dest: std::sync::Arc<dyn Destination>, at: Option<String>) -> Result<Vec<String>> {
    let (repos_root, wikis_root) = (app.repos.root().to_path_buf(), app.wikis.root().to_path_buf());
    let (d, a) = (dest.clone(), at.clone());
    let done = tokio::task::spawn_blocking(move || restore(d.as_ref(), a.as_deref(), &repos_root, &wikis_root)).await??;
    let at = match at {
        Some(a) => a,
        None => String::from_utf8_lossy(&tokio::task::block_in_place(|| dest.get("LATEST"))?).trim().to_string(),
    };
    let mut notes = Vec::new();
    for name in tokio::task::block_in_place(|| dest.list(&format!("runs/{at}/records")))? {
        let rec: serde_json::Value =
            serde_json::from_slice(&tokio::task::block_in_place(|| dest.get(&format!("runs/{at}/records/{name}")))?)?;
        let Some(row) = rec["repositories"].as_array().and_then(|a| a.first()) else { continue };
        let (owner, repo) = (row["owner"].as_str().unwrap_or_default(), row["name"].as_str().unwrap_or_default());
        if owner.is_empty() || db::repos::get(&app.db, owner, repo).await?.is_some() {
            continue;
        }
        let visibility = match row["visibility"].as_str() {
            Some("private") => hub_api::Visibility::Private,
            Some("internal") => hub_api::Visibility::Internal,
            _ => hub_api::Visibility::Public,
        };
        let made = db::repos::create(&app.db, owner, repo, row["description"].as_str().unwrap_or_default(), visibility).await?;
        // Its settings as they were: every column the row kept but its
        // name, its id and a fork's parent (another hub's id).
        let cols = table_cols(&app.db, "repositories").await?;
        let set: Vec<(&Col, serde_json::Value)> = cols
            .iter()
            .filter(|c| !["id", "owner", "name", "forked_from"].contains(&c.name.as_str()))
            .filter_map(|c| row.get(&c.name).filter(|v| !v.is_null()).map(|v| (c, v.clone())))
            .collect();
        if !set.is_empty() {
            let sql = format!(
                "UPDATE repositories SET {} WHERE id = ?",
                set.iter().map(|(c, _)| format!("\"{}\" = ?", c.name)).collect::<Vec<_>>().join(", ")
            );
            let mut q = sqlx::query(&sql);
            for (c, v) in set {
                q = bind_json(q, v, c.ty.to_ascii_uppercase().contains("BLOB"));
            }
            q.bind(made.id).execute(&app.db).await?;
        }
        let old = row["id"].as_i64().unwrap_or(-1);
        for n in restore_records(app, &dest, &rec, old, made.id).await.with_context(|| format!("restore {owner}/{repo}'s records"))? {
            notes.push(format!("note: {owner}/{repo}: {n}"));
        }
    }
    let mut done = done;
    done.extend(notes);
    Ok(done)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn a_directory_destination_keeps_keys_inside_its_root() {
        let d = tempfile::tempdir().unwrap();
        let dest = Directory { root: d.path().to_path_buf() };
        dest.put("runs/a/DONE", b"a").unwrap();
        assert_eq!(dest.get("runs/a/DONE").unwrap(), b"a");
        assert_eq!(dest.list("runs").unwrap(), vec!["a"]);
        assert!(dest.put("../escape", b"x").is_err() && dest.put("/abs", b"x").is_err());
        dest.remove("runs").unwrap();
        assert!(dest.list("runs").unwrap().is_empty());
    }

    #[test]
    fn files_are_sent_once_and_unchanged_ones_not_read_again() {
        let src = tempfile::tempdir().unwrap();
        let out = tempfile::tempdir().unwrap();
        let dest = Directory { root: out.path().to_path_buf() };
        std::fs::create_dir_all(src.path().join(".oxy/objects/loose")).unwrap();
        std::fs::write(src.path().join(".oxy/objects/loose/aa"), b"object").unwrap();
        std::fs::write(src.path().join(".oxy/ops-head"), b"ref one").unwrap();
        let mut s = Sent::default();
        let files = copy_dir(&dest, src.path(), &HashMap::new(), false, &mut s).unwrap();
        assert_eq!((files.len(), s.sent), (2, 2));
        let known: HashMap<String, File> = files.iter().map(|f| (f.path.clone(), f.clone())).collect();
        let mut s = Sent::default();
        let again = copy_dir(&dest, src.path(), &known, false, &mut s).unwrap();
        assert_eq!((again, s.sent), (files.clone(), 0), "nothing new travels");
        // The first pass takes only the files that never change.
        let mut s = Sent::default();
        let first = copy_dir(&dest, src.path(), &HashMap::new(), true, &mut s).unwrap();
        assert_eq!(first.iter().map(|f| f.path.as_str()).collect::<Vec<_>>(), vec![".oxy/objects/loose/aa"]);
    }

    #[test]
    fn requests_are_signed_as_aws_documents() {
        // AWS's own example (S3 API reference, "Signature calculations":
        // GET Object), with its published signature.
        let empty = "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855";
        let headers = vec![
            ("Host".to_string(), "examplebucket.s3.amazonaws.com".to_string()),
            ("Range".to_string(), "bytes=0-9".to_string()),
            ("x-amz-content-sha256".to_string(), empty.to_string()),
            ("x-amz-date".to_string(), "20130524T000000Z".to_string()),
        ];
        let auth = sigv4(
            "GET",
            "/test.txt",
            &[],
            &headers,
            empty,
            ("AKIAIOSFODNN7EXAMPLE", "wJalrXUtnFEMI/K7MDENG/bPxRfiCYEXAMPLEKEY"),
            "us-east-1",
            "s3",
            "20130524T000000Z",
        );
        assert_eq!(
            auth,
            "AWS4-HMAC-SHA256 Credential=AKIAIOSFODNN7EXAMPLE/20130524/us-east-1/s3/aws4_request, \
             SignedHeaders=host;range;x-amz-content-sha256;x-amz-date, \
             Signature=f0e8bdb87c964420e857bd35b5d6ed310bd44f0170aba48dd91039c6036bdb41"
        );
        assert_eq!(aws_encode("runs/2026 x+y", true), "runs/2026%20x%2By");
        assert_eq!(aws_encode("a/b", false), "a%2Fb");
        assert_eq!(xml_text("<A><Key>runs/x&amp;y</Key></A>", "Key").as_deref(), Some("runs/x&y"));
    }

    #[test]
    fn run_names_sort_by_time() {
        assert_eq!(run_name(0), "19700101T000000Z");
        assert!(run_name(1_791_900_000_000) < run_name(1_791_903_600_000));
    }
}
`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet
Keyboard
