~ knotless Search/
↑↓ move↵ open⇧↵ all results
0
0
918 lines · 51.1 KB Raw History
// An S3-compatible object store in this process, kept in memory: the
// buckets a server under test keeps its blobs in, which the harness reads
// and makes fail. Addressing is path-style only (`/<bucket>/<key>`); every
// request is authenticated with SigV4 in its `Authorization` header, checked
// as S3 checks it, and every body, plain or `aws-chunked`, against the
// hashes, signatures and checksums it carries.

import { createServer } from 'node:http'
import { createHash, createHmac } from 'node:crypto'
import { crc32 } from 'node:zlib'

/// The bucket each side keeps its blobs in.
export const BUCKETS = { reference: 'reference', server: 'server' }
/// The credentials both sides sign their requests with.
export const S3_KEYS = { accessKeyId: 'harness-access', secretAccessKey: 'harness-secret-key-0123456789abcdefghijk' }
/// How long either side waits for a request to the store, an upload among
/// them, before giving it up.
export const S3_TIMEOUT_MS = 2000

/// The operations that write an object, which `'store-then-hang'` lets
/// through before it hangs.
const WRITES = ['PutObject', 'CopyObject', 'CompleteMultipartUpload']
/// A response that is never sent: what an operation stores under
/// `'store-then-hang'` it answers to nobody.
const UNANSWERED = { writeHead() {}, end() {}, setHeader() {} }
/// A response that sends its head and the first half of its body's bytes,
/// then drops the connection: what `'cut'` answers.
const cutShort = (res) => ({
  setHeader: (k, v) => res.setHeader(k, v),
  writeHead: (...args) => res.writeHead(...args),
  end(data) {
    const b = data == null ? Buffer.alloc(0) : Buffer.from(data)
    res.write(b.subarray(0, Math.floor(b.length / 2)), () => res.socket?.destroy())
  },
})

const XMLNS = 'http://s3.amazonaws.com/doc/2006-03-01/'
const EMPTY_SHA256 = 'e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855'
const MIN_PART = 5 * 1024 * 1024
const SKEW_MS = 15 * 60 * 1000
const STREAMING = {
  'STREAMING-AWS4-HMAC-SHA256-PAYLOAD': { signed: true, trailer: false },
  'STREAMING-AWS4-HMAC-SHA256-PAYLOAD-TRAILER': { signed: true, trailer: true },
  'STREAMING-UNSIGNED-PAYLOAD-TRAILER': { signed: false, trailer: true },
}
/// The query parameters each operation takes; a request with any other is
/// an operation this store does not have.
const PARAMS = {
  CreateBucket: [],
  ListObjectsV2: ['list-type', 'prefix', 'delimiter', 'max-keys', 'continuation-token', 'start-after', 'encoding-type', 'fetch-owner'],
  DeleteObjects: ['delete'],
  PutObject: [],
  CopyObject: [],
  GetObject: ['response-content-type', 'response-content-language', 'response-expires', 'response-cache-control', 'response-content-disposition', 'response-content-encoding'],
  HeadObject: [],
  DeleteObject: [],
  CreateMultipartUpload: ['uploads'],
  UploadPart: ['partNumber', 'uploadId'],
  CompleteMultipartUpload: ['uploadId'],
  AbortMultipartUpload: ['uploadId'],
}
/// The object headers kept with an object and given back with it.
const KEPT = ['cache-control', 'content-disposition', 'content-language', 'expires']
const FAULT_CODES = {
  400: ['InvalidRequest', 'Invalid Request'],
  403: ['AccessDenied', 'Access Denied'],
  404: ['NoSuchKey', 'The specified key does not exist.'],
  409: ['OperationAborted', 'A conflicting conditional operation is currently in progress against this resource.'],
  412: ['PreconditionFailed', 'At least one of the pre-conditions you specified did not hold'],
  500: ['InternalError', 'We encountered an internal error. Please try again.'],
  501: ['NotImplemented', 'A header you provided implies functionality that is not implemented'],
  503: ['SlowDown', 'Please reduce your request rate.'],
}

class S3Error extends Error {
  constructor(status, code, message, extra = {}, headers = {}) {
    super(message)
    Object.assign(this, { status, code, extra, headers })
  }
}

/// Start an S3-compatible server on 127.0.0.1, on a free port, taking
/// requests signed with `accessKeyId` and `secretAccessKey` for `region`.
/// Answers `{url, makeBucket, objects, remove, requests, rejected, fail,
/// put, clearFailures, close}`:
/// - `requests`, every request in the order it came, `{at, method, op,
///   bucket, key, path, status, ms, signed, connection}`, `path` the request
///   target as sent, `connection` the number of the connection it came on,
///   from 1 in the order they were made; `status` and `ms` are set once it is answered and stay null for
///   one that never is. Besides: `code`, the S3 error code it was answered
///   with; `fault`, `'status'`, `'hang'`, `'store-then-hang'`, `'reset'` or `'cut'` when `fail` made it
///   fail; `payload`, its `x-amz-content-sha256`; `encoding`, its
///   `Content-Encoding`; `checksum`, the `x-amz-checksum-*` checked and where
///   it came (`'crc32 header'`, `'crc32 trailer'`); `error`, the stack of an
///   error this store threw answering it.
/// - `rejected`, the requests refused for authentication, `{at, method,
///   path, op, bucket, key, code, why}`.
/// - `objects(bucket)`, the bucket's objects, live: key -> `{bytes,
///   contentType, etag, lastModified, meta, headers, checksum}`,
///   `contentType` null where none was given (it is served as
///   `binary/octet-stream`), `etag` quoted as S3 gives it, `meta` the
///   `x-amz-meta-*` headers, `headers` the `KEPT` ones, `checksum` the
///   `{algorithm, value}` it was stored with or null.
/// - `fail({bucket, key, op, times, mode})`, see `fail` below; a request it
///   made `'store-then-hang'` has `stored`, true, or the S3 error code it
///   would have been answered with.
/// - `put(bucket, key, bytes, contentType)` and `remove(bucket, key)`, an
///   object stored or deleted without a request.
export async function startS3({ accessKeyId, secretAccessKey, region = 'us-east-1' }) {
  const buckets = new Map()
  const uploads = new Map()
  const failures = []
  const sockets = new Set()
  let connections = 0
  let served = 0
  let uploadsMade = 0
  const s3 = { requests: [], rejected: [] }

  const server = createServer((req, res) => {
    handle(req, res).catch((err) => {
      if (!res.headersSent && !res.destroyed) {
        res.writeHead(500, { 'content-type': 'application/xml' })
        res.end(errorXml('InternalError', String(err.message), req.url, res.getHeader('x-amz-request-id'), {}))
      }
    })
  })
  server.on('connection', (c) => {
    c.number = ++connections
    sockets.add(c)
    c.on('close', () => sockets.delete(c))
  })

  async function handle(req, res) {
    const started = performance.now()
    const requestId = (++served).toString(16).toUpperCase().padStart(16, '0')
    const rec = { at: Date.now(), method: req.method, op: 'Unknown', bucket: null, key: null, path: req.url, status: null, ms: null, signed: false, connection: req.socket.number }
    s3.requests.push(rec)
    res.setHeader('x-amz-request-id', requestId)
    res.setHeader('x-amz-id-2', requestId)
    res.on('finish', () => {
      rec.status = res.statusCode
      rec.ms = performance.now() - started
    })
    try {
      const target = parseTarget(req.url)
      rec.bucket = target.bucket
      rec.key = target.key
      rec.op = classify(req, target)
      const rule = failures.find(
        (f) => f.count < f.times && (f.bucket == null || f.bucket === rec.bucket) && (f.key == null || f.key === rec.key) && (f.op == null || [f.op].flat().includes(rec.op)),
      )
      let storeThenHang = false
      let cut = false
      if (rule) {
        rule.count += 1
        if (rule.mode === 'reset') {
          rec.fault = 'reset'
          return req.socket.destroy()
        }
        if (rule.mode === 'hang' || (rule.mode === 'store-then-hang' && !WRITES.includes(rec.op))) {
          rec.fault = 'hang'
          return req.resume()
        }
        if (rule.mode === 'store-then-hang') {
          rec.fault = 'store-then-hang'
          storeThenHang = true
        } else if (rule.mode === 'cut') {
          rec.fault = 'cut'
          cut = true
        } else if (rule.mode.delayMs) {
          rec.fault = 'delay'
          await new Promise((ok) => setTimeout(ok, rule.mode.delayMs))
        } else {
          rec.fault = 'status'
          await readBody(req)
          const [code, message] = FAULT_CODES[rule.mode.status] ?? ['InternalError', 'Injected failure']
          throw new S3Error(rule.mode.status, rule.mode.code ?? code, rule.mode.message ?? message)
        }
      }
      const raw = await readBody(req)
      const auth = authenticate(req, target, rec)
      rec.signed = true
      rec.payload = req.headers['x-amz-content-sha256']
      rec.encoding = req.headers['content-encoding'] ?? null
      const body = decodePayload(req, raw, auth, rec)
      if (rec.op === 'Unknown') throw new S3Error(501, 'NotImplemented', `${req.method} ${req.url}: no such operation here`)
      if (rec.op !== 'CompleteMultipartUpload') body.checksum = checkChecksums(req, body, rec)
      if (storeThenHang) {
        try {
          OPS[rec.op](req, UNANSWERED, target, body)
          rec.stored = true
        } catch (err) {
          if (!(err instanceof S3Error)) throw err
          rec.stored = err.code
        }
        return
      }
      await OPS[rec.op](req, cut ? cutShort(res) : res, target, body)
    } catch (err) {
      if (!(err instanceof S3Error)) {
        rec.error = String(err.stack)
        throw err
      }
      rec.code = err.code
      if (res.headersSent || res.destroyed) return
      res.writeHead(err.status, { 'content-type': 'application/xml', ...err.headers })
      res.end(req.method === 'HEAD' ? undefined : errorXml(err.code, err.message, req.url.split('?')[0], requestId, err.extra))
    }
  }

  /// Refuse a request for authentication, recording why.
  function refuse(req, target, rec, status, code, message, why, extra = {}) {
    s3.rejected.push({ at: Date.now(), method: req.method, path: req.url, op: rec.op, bucket: target.bucket, key: target.key, code, why })
    return new S3Error(status, code, message, extra)
  }

  /// Check a request's SigV4 `Authorization` header. Answers what its
  /// streamed chunks are signed with: `{signingKey, scope, amzDate,
  /// signature}`.
  function authenticate(req, target, rec) {
    const no = (status, code, message, why, extra) => refuse(req, target, rec, status, code, message, why, extra)
    const header = req.headers.authorization
    if (!header) throw no(403, 'AccessDenied', 'Access Denied', 'no Authorization header')
    if (!header.startsWith('AWS4-HMAC-SHA256 ')) throw no(400, 'InvalidArgument', 'Unsupported Authorization Type', `Authorization ${header.split(' ')[0]}, not AWS4-HMAC-SHA256`)
    const fields = Object.fromEntries(
      header
        .slice('AWS4-HMAC-SHA256 '.length)
        .split(',')
        .map((f) => f.trim())
        .map((f) => [f.slice(0, f.indexOf('=')), f.slice(f.indexOf('=') + 1)]),
    )
    const { Credential: credential, SignedHeaders: signedHeaders, Signature: signature } = fields
    if (!credential || !signedHeaders || !signature) throw no(400, 'AuthorizationHeaderMalformed', 'The authorization header is malformed; it must have Credential, SignedHeaders and Signature.', `Authorization ${header}`)
    const [keyId, date, scopeRegion, service, terminator, ...more] = credential.split('/')
    if (more.length || terminator === undefined) throw no(400, 'AuthorizationHeaderMalformed', `The authorization header is malformed; the Credential is mal-formed; expecting "<YOUR-AKID>/YYYYMMDD/REGION/SERVICE/aws4_request".`, `Credential ${credential}`)
    if (keyId !== accessKeyId) throw no(403, 'InvalidAccessKeyId', 'The AWS Access Key Id you provided does not exist in our records.', `access key ${keyId}`, { AWSAccessKeyId: keyId })
    if (scopeRegion !== region) throw no(400, 'AuthorizationHeaderMalformed', `The authorization header is malformed; the region '${scopeRegion}' is wrong; expecting '${region}'`, `region ${scopeRegion}, not ${region}`, { Region: region })
    if (service !== 's3') throw no(400, 'AuthorizationHeaderMalformed', `The authorization header is malformed; incorrect service "${service}". This endpoint belongs to "s3".`, `service ${service}`)
    if (terminator !== 'aws4_request') throw no(400, 'AuthorizationHeaderMalformed', `The authorization header is malformed; incorrect terminal "${terminator}". This endpoint uses "aws4_request".`, `terminator ${terminator}`)
    const amzDate = req.headers['x-amz-date']
    const m = /^(\d{4})(\d{2})(\d{2})T(\d{2})(\d{2})(\d{2})Z$/.exec(amzDate ?? '')
    if (!m) throw no(403, 'AccessDenied', 'AWS authentication requires a valid Date or x-amz-date header', `x-amz-date ${amzDate}`)
    if (date !== amzDate.slice(0, 8)) throw no(400, 'AuthorizationHeaderMalformed', `The authorization header is malformed; Invalid credential date "${date}". This date is not the same as X-Amz-Date: "${amzDate.slice(0, 8)}".`, `credential date ${date}, x-amz-date ${amzDate}`)
    const signedAt = Date.UTC(m[1], m[2] - 1, m[3], m[4], m[5], m[6])
    if (Math.abs(Date.now() - signedAt) > SKEW_MS) throw no(403, 'RequestTimeTooSkewed', 'The difference between the request time and the current time is too large.', `x-amz-date ${amzDate}, now ${new Date().toISOString()}`, { RequestTime: amzDate, ServerTime: new Date().toISOString(), MaxAllowedSkewMilliseconds: 900000 })
    const payloadHash = req.headers['x-amz-content-sha256']
    if (payloadHash === undefined) throw no(400, 'InvalidRequest', 'Missing required header for this request: x-amz-content-sha256', 'no x-amz-content-sha256')
    if (!(payloadHash === 'UNSIGNED-PAYLOAD' || payloadHash in STREAMING || /^[0-9a-f]{64}$/.test(payloadHash))) throw no(400, 'InvalidArgument', 'x-amz-content-sha256 must be UNSIGNED-PAYLOAD, STREAMING-AWS4-HMAC-SHA256-PAYLOAD[-TRAILER], STREAMING-UNSIGNED-PAYLOAD-TRAILER or a valid sha256 value.', `x-amz-content-sha256 ${payloadHash}`)
    const headers = rawHeaders(req)
    const names = signedHeaders.split(';')
    if (names.some((n, i) => n !== n.toLowerCase() || (i && names[i - 1] >= n))) throw no(400, 'AuthorizationHeaderMalformed', 'The authorization header is malformed; SignedHeaders must be lowercase, sorted and distinct.', `SignedHeaders ${signedHeaders}`)
    if (!names.includes('host')) throw no(403, 'AccessDenied', 'Host header is not signed.', `SignedHeaders ${signedHeaders} lacks host`)
    const unsigned = [...headers.keys()].filter((n) => n.startsWith('x-amz-') && !names.includes(n))
    if (unsigned.length) throw no(403, 'AccessDenied', 'There were headers present in the request which were not signed', `unsigned ${unsigned.join(', ')}`, { HeadersNotSigned: unsigned.join(', ') })
    const missing = names.filter((n) => !headers.has(n))
    if (missing.length) throw no(403, 'SignatureDoesNotMatch', 'The request signature we calculated does not match the signature you provided.', `signed headers absent: ${missing.join(', ')}`)
    const canonicalRequest = [
      req.method,
      target.canonicalPath,
      target.canonicalQuery,
      ...names.map((n) => `${n}:${headers.get(n).map((v) => v.replace(/[ \t]+/g, ' ').trim()).join(',')}`),
      '',
      signedHeaders,
      payloadHash,
    ].join('\n')
    const scope = `${date}/${region}/s3/aws4_request`
    const stringToSign = ['AWS4-HMAC-SHA256', amzDate, scope, sha256Hex(canonicalRequest)].join('\n')
    const signingKey = ['s3', 'aws4_request'].reduce((k, s) => hmac(k, s), hmac(hmac(`AWS4${secretAccessKey}`, date), region))
    const expected = hmac(signingKey, stringToSign).toString('hex')
    if (signature !== expected)
      throw no(403, 'SignatureDoesNotMatch', 'The request signature we calculated does not match the signature you provided. Check your key and signing method.', `signature ${signature}, expected ${expected}; canonical request:\n${canonicalRequest}`, {
        AWSAccessKeyId: keyId,
        StringToSign: stringToSign,
        SignatureProvided: signature,
        CanonicalRequest: canonicalRequest,
      })
    return { signingKey, scope, amzDate, signature, refuse: no }
  }

  /// The body a request carries, decoded from `aws-chunked` where it is
  /// streamed, each chunk and trailer signature and the payload's hash
  /// checked: `{bytes, trailers}`, trailers by lowercase name.
  function decodePayload(req, raw, auth, rec) {
    const payloadHash = req.headers['x-amz-content-sha256']
    const declared = (req.headers['x-amz-trailer'] ?? '').split(',').map((t) => t.trim().toLowerCase()).filter(Boolean)
    const streaming = STREAMING[payloadHash]
    if (declared.length && !streaming?.trailer) throw new S3Error(400, 'InvalidRequest', `x-amz-trailer is given, but x-amz-content-sha256 is ${payloadHash}`)
    if (!streaming) {
      if (payloadHash !== 'UNSIGNED-PAYLOAD' && sha256Hex(raw) !== payloadHash)
        throw new S3Error(400, 'XAmzContentSHA256Mismatch', "The provided 'x-amz-content-sha256' header does not match what was computed.", { ClientComputedContentSHA256: payloadHash, S3ComputedContentSHA256: sha256Hex(raw) })
      rec.bytes = raw.length
      return { bytes: raw, trailers: new Map() }
    }
    const length = req.headers['x-amz-decoded-content-length']
    if (length === undefined || !/^\d+$/.test(length)) throw new S3Error(411, 'MissingContentLength', 'You must provide the Content-Length HTTP header (x-amz-decoded-content-length for a streamed payload).')
    const bad = (why) => new S3Error(400, 'IncompleteBody', `The request body is not valid aws-chunked encoding: ${why}`)
    const chunkSignatureWrong = (why) => auth.refuse(403, 'SignatureDoesNotMatch', 'The request signature we calculated does not match the signature you provided. Check your key and signing method.', why)
    const line = (at) => {
      const end = raw.indexOf('\r\n', at)
      if (end < 0) throw bad('a line has no CRLF')
      return [raw.toString('latin1', at, end), end + 2]
    }
    const chunks = []
    let at = 0
    let previous = auth.signature
    for (;;) {
      let head
      ;[head, at] = line(at)
      const [sizeHex, ...extensions] = head.split(';')
      if (!/^[0-9a-fA-F]+$/.test(sizeHex)) throw bad(`chunk size ${JSON.stringify(sizeHex)}`)
      const size = parseInt(sizeHex, 16)
      if (at + size > raw.length) throw bad('a chunk runs past the end of the body')
      const data = raw.subarray(at, at + size)
      at += size
      if (streaming.signed) {
        const signature = extensions.find((e) => e.startsWith('chunk-signature='))?.slice('chunk-signature='.length)
        if (!signature) throw chunkSignatureWrong(`chunk of ${size} bytes has no chunk-signature`)
        const expected = hmac(auth.signingKey, ['AWS4-HMAC-SHA256-PAYLOAD', auth.amzDate, auth.scope, previous, EMPTY_SHA256, sha256Hex(data)].join('\n')).toString('hex')
        if (signature !== expected) throw chunkSignatureWrong(`chunk ${chunks.length} of ${size} bytes: chunk-signature ${signature}, expected ${expected}`)
        previous = signature
      }
      if (size === 0) break
      if (raw.toString('latin1', at, at + 2) !== '\r\n') throw bad('a chunk does not end in CRLF')
      at += 2
      chunks.push(data)
    }
    const trailers = new Map()
    let trailerSignature = null
    const canonicalTrailers = []
    for (;;) {
      let text
      ;[text, at] = line(at)
      if (text === '') break
      if (!streaming.trailer) throw bad('trailing headers, where x-amz-content-sha256 has none')
      const colon = text.indexOf(':')
      if (colon < 0) throw bad(`trailer ${JSON.stringify(text)}`)
      const name = text.slice(0, colon).trim().toLowerCase()
      const value = text.slice(colon + 1).trim()
      if (name === 'x-amz-trailer-signature') trailerSignature = value
      else {
        trailers.set(name, value)
        canonicalTrailers.push(`${name}:${value}\n`)
      }
    }
    if (at !== raw.length) throw bad(`${raw.length - at} bytes after the last chunk`)
    if (streaming.signed && streaming.trailer) {
      const expected = hmac(auth.signingKey, ['AWS4-HMAC-SHA256-TRAILER', auth.amzDate, auth.scope, previous, sha256Hex(canonicalTrailers.join(''))].join('\n')).toString('hex')
      if (trailerSignature !== expected) throw chunkSignatureWrong(`x-amz-trailer-signature ${trailerSignature}, expected ${expected}`)
    }
    for (const name of declared) if (!trailers.has(name)) throw new S3Error(400, 'MalformedTrailerError', `The request contained trailing data that was not well-formed: x-amz-trailer names ${name}, which did not come.`)
    for (const name of trailers.keys()) if (!declared.includes(name)) throw new S3Error(400, 'MalformedTrailerError', `The request contained trailing data that was not well-formed: ${name} was not declared in x-amz-trailer.`)
    const bytes = Buffer.concat(chunks)
    if (bytes.length !== Number(length)) throw new S3Error(400, 'IncompleteBody', `You did not provide the number of bytes specified by the x-amz-decoded-content-length HTTP header: ${length}, but ${bytes.length} came.`)
    rec.bytes = bytes.length
    return { bytes, trailers }
  }

  const bucket = (name) => {
    const b = buckets.get(name)
    if (!b) throw new S3Error(404, 'NoSuchBucket', 'The specified bucket does not exist', { BucketName: name })
    return b
  }
  const object = (target) => {
    const o = bucket(target.bucket).get(target.key)
    if (!o) throw new S3Error(404, 'NoSuchKey', 'The specified key does not exist.', { Key: target.key })
    return o
  }
  const upload = (target, id) => {
    const u = uploads.get(id)
    if (!u || u.bucket !== target.bucket || u.key !== target.key) throw new S3Error(404, 'NoSuchUpload', 'The specified upload does not exist. The upload ID may be invalid, or the upload may have been aborted or completed.', { UploadId: id })
    return u
  }
  const xmlReply = (res, xml, headers = {}) => {
    res.writeHead(200, { 'content-type': 'application/xml', ...headers })
    res.end(`<?xml version="1.0" encoding="UTF-8"?>\n${xml}`)
  }

  const OPS = {
    CreateBucket(req, res, target, { bytes }) {
      if (!/^[a-z0-9][a-z0-9.-]{1,61}[a-z0-9]$/.test(target.bucket)) throw new S3Error(400, 'InvalidBucketName', 'The specified bucket is not valid.', { BucketName: target.bucket })
      const constraint = /<LocationConstraint>([^<]*)<\/LocationConstraint>/.exec(bytes.toString())?.[1]
      if (constraint !== undefined && constraint !== region) throw new S3Error(400, 'IllegalLocationConstraintException', `The ${constraint} location constraint is incompatible for the region specific endpoint this request was sent to.`)
      // S3 in us-east-1 answers 200 to its owner creating a bucket it has.
      if (buckets.has(target.bucket) && region !== 'us-east-1') throw new S3Error(409, 'BucketAlreadyOwnedByYou', 'Your previous request to create the named bucket succeeded and you already own it.', { BucketName: target.bucket })
      if (!buckets.has(target.bucket)) buckets.set(target.bucket, new Map())
      res.writeHead(200, { location: `/${target.bucket}` })
      res.end()
    },

    ListObjectsV2(req, res, target) {
      const objects = bucket(target.bucket)
      const q = target.params
      const prefix = q.get('prefix') ?? ''
      const delimiter = q.get('delimiter') || null
      const encoding = q.get('encoding-type') ?? null
      if (encoding !== null && encoding !== 'url') throw new S3Error(400, 'InvalidArgument', 'Invalid Encoding Method specified in Request', { ArgumentName: 'encoding-type', ArgumentValue: encoding })
      const maxText = q.get('max-keys') ?? '1000'
      if (!/^\d+$/.test(maxText)) throw new S3Error(400, 'InvalidArgument', 'Provided max-keys not an integer or within integer range', { ArgumentName: 'max-keys', ArgumentValue: maxText })
      const max = Math.min(Number(maxText), 1000)
      const token = q.get('continuation-token') ?? null
      const startAfter = q.get('start-after') ?? null
      let after = startAfter ?? ''
      let afterPrefix = false
      if (token !== null) {
        try {
          ;[after, afterPrefix] = JSON.parse(Buffer.from(token, 'base64url').toString())
          if (typeof after !== 'string' || typeof afterPrefix !== 'boolean') throw new Error()
        } catch {
          throw new S3Error(400, 'InvalidArgument', 'The continuation token provided is incorrect', { ArgumentName: 'continuation-token' })
        }
      }
      const keys = [...objects.keys()].filter((k) => k.startsWith(prefix) && byteOrder(k, after) > 0 && !(afterPrefix && k.startsWith(after))).sort(byteOrder)
      const contents = []
      const prefixes = []
      let truncated = false
      let last = null
      for (const k of keys) {
        const cut = delimiter === null ? -1 : k.indexOf(delimiter, prefix.length)
        const commonPrefix = cut < 0 ? null : k.slice(0, cut + delimiter.length)
        if (commonPrefix !== null && last?.[1] && last[0] === commonPrefix) continue
        if (contents.length + prefixes.length >= max) {
          truncated = true
          break
        }
        if (commonPrefix === null) contents.push(k)
        else prefixes.push(commonPrefix)
        last = [commonPrefix ?? k, commonPrefix !== null]
      }
      const enc = (s) => (encoding === 'url' ? awsEncode(s).replace(/%2F/g, '/') : s)
      const el = (name, value) => `<${name}>${xmlEscape(String(value))}</${name}>`
      let xml = `<ListBucketResult xmlns="${XMLNS}">${el('Name', target.bucket)}${el('Prefix', enc(prefix))}`
      if (delimiter !== null) xml += el('Delimiter', enc(delimiter))
      if (startAfter !== null) xml += el('StartAfter', enc(startAfter))
      if (token !== null) xml += el('ContinuationToken', token)
      xml += `${el('KeyCount', contents.length + prefixes.length)}${el('MaxKeys', max)}`
      if (encoding !== null) xml += el('EncodingType', encoding)
      xml += el('IsTruncated', truncated)
      if (truncated) xml += el('NextContinuationToken', Buffer.from(JSON.stringify(last ?? [after, afterPrefix])).toString('base64url'))
      for (const k of contents) {
        const o = objects.get(k)
        xml += `<Contents>${el('Key', enc(k))}${el('LastModified', o.lastModified.toISOString())}${el('ETag', o.etag)}${el('Size', o.bytes.length)}${el('StorageClass', 'STANDARD')}</Contents>`
      }
      for (const p of prefixes) xml += `<CommonPrefixes>${el('Prefix', enc(p))}</CommonPrefixes>`
      xmlReply(res, `${xml}</ListBucketResult>`)
    },

    DeleteObjects(req, res, target, { bytes, checksum }) {
      const objects = bucket(target.bucket)
      if (!req.headers['content-md5'] && !checksum) throw new S3Error(400, 'InvalidRequest', 'Missing required header for this request: Content-MD5 or x-amz-checksum-*')
      const text = bytes.toString()
      const root = /^\s*(?:<\?xml[^>]*\?>\s*)?<Delete(?:\s[^>]*)?>([\s\S]*)<\/Delete>\s*$/.exec(text)
      if (!root) throw new S3Error(400, 'MalformedXML', 'The XML you provided was not well-formed or did not validate against our published schema')
      const keys = [...root[1].matchAll(/<Object>([\s\S]*?)<\/Object>/g)].map(([, inner]) => /<Key>([\s\S]*?)<\/Key>/.exec(inner)?.[1])
      if (!keys.length || keys.length > 1000 || keys.some((k) => k === undefined)) throw new S3Error(400, 'MalformedXML', 'The XML you provided was not well-formed or did not validate against our published schema')
      const quiet = /<Quiet>\s*true\s*<\/Quiet>/i.test(root[1])
      let xml = `<DeleteResult xmlns="${XMLNS}">`
      for (const k of keys.map(xmlUnescape)) {
        objects.delete(k)
        if (!quiet) xml += `<Deleted><Key>${xmlEscape(k)}</Key></Deleted>`
      }
      xmlReply(res, `${xml}</DeleteResult>`)
    },

    PutObject(req, res, target, { bytes, checksum }) {
      const objects = bucket(target.bucket)
      needLength(req)
      precondition(req, objects.get(target.key))
      const o = stored(bytes, req, checksum)
      objects.set(target.key, o)
      res.writeHead(200, { etag: o.etag, ...checksumHeaders(checksum) })
      res.end()
    },

    CopyObject(req, res, target) {
      const objects = bucket(target.bucket)
      let source = req.headers['x-amz-copy-source']
      if (source.includes('?')) throw new S3Error(400, 'InvalidArgument', 'Copying a version of an object is not supported here: this store keeps no versions.', { ArgumentName: 'x-amz-copy-source', ArgumentValue: source })
      try {
        source = decodeURIComponent(source).replace(/^\//, '')
      } catch {
        throw new S3Error(400, 'InvalidArgument', 'Invalid copy source encoding', { ArgumentName: 'x-amz-copy-source', ArgumentValue: source })
      }
      const slash = source.indexOf('/')
      if (slash <= 0 || slash === source.length - 1) throw new S3Error(400, 'InvalidArgument', 'Copy Source must mention the source bucket and key: sourcebucket/sourcekey', { ArgumentName: 'x-amz-copy-source', ArgumentValue: source })
      const from = object({ bucket: source.slice(0, slash), key: source.slice(slash + 1) })
      const ifMatch = req.headers['x-amz-copy-source-if-match']
      const ifNoneMatch = req.headers['x-amz-copy-source-if-none-match']
      if ((ifMatch !== undefined && !etagMatches(ifMatch, from.etag)) || (ifNoneMatch !== undefined && etagMatches(ifNoneMatch, from.etag))) throw new S3Error(412, 'PreconditionFailed', 'At least one of the pre-conditions you specified did not hold', { Condition: ifMatch !== undefined ? 'x-amz-copy-source-If-Match' : 'x-amz-copy-source-If-None-Match' })
      const directive = req.headers['x-amz-metadata-directive'] ?? 'COPY'
      if (directive !== 'COPY' && directive !== 'REPLACE') throw new S3Error(400, 'InvalidArgument', 'Unknown metadata directive.', { ArgumentName: 'x-amz-metadata-directive', ArgumentValue: directive })
      if (directive === 'COPY' && source.slice(0, slash) === target.bucket && source.slice(slash + 1) === target.key)
        throw new S3Error(400, 'InvalidRequest', "This copy request is illegal because it is trying to copy an object to itself without changing the object's metadata, storage class, website redirect location or encryption attributes.")
      const o =
        directive === 'COPY'
          ? { ...from, etag: `"${md5(from.bytes).toString('hex')}"`, lastModified: now() }
          : stored(from.bytes, req, from.checksum)
      objects.set(target.key, o)
      xmlReply(res, `<CopyObjectResult><LastModified>${o.lastModified.toISOString()}</LastModified><ETag>${xmlEscape(o.etag)}</ETag></CopyObjectResult>`)
    },

    GetObject(req, res, target) {
      const o = object(target)
      if (conditional(req, res, o)) return
      const size = o.bytes.length
      const headers = objectHeaders(o)
      for (const [param, value] of target.params) if (param.startsWith('response-')) headers[param.slice('response-'.length)] = value
      const range = parseRange(req.headers.range, size)
      if (range) {
        headers['content-range'] = `bytes ${range[0]}-${range[1]}/${size}`
        headers['content-length'] = range[1] - range[0] + 1
        res.writeHead(206, headers)
        return res.end(o.bytes.subarray(range[0], range[1] + 1))
      }
      if (req.headers['x-amz-checksum-mode'] === 'ENABLED') Object.assign(headers, checksumHeaders(o.checksum))
      res.writeHead(200, headers)
      res.end(o.bytes)
    },

    HeadObject(req, res, target) {
      const o = object(target)
      if (conditional(req, res, o)) return
      const headers = objectHeaders(o)
      if (req.headers['x-amz-checksum-mode'] === 'ENABLED') Object.assign(headers, checksumHeaders(o.checksum))
      res.writeHead(200, headers)
      res.end()
    },

    DeleteObject(req, res, target) {
      bucket(target.bucket).delete(target.key)
      res.writeHead(204)
      res.end()
    },

    CreateMultipartUpload(req, res, target) {
      bucket(target.bucket)
      const id = `upload-${(++uploadsMade).toString(16).padStart(8, '0')}`
      const algorithm = req.headers['x-amz-checksum-algorithm']?.toLowerCase() ?? null
      uploads.set(id, { bucket: target.bucket, key: target.key, parts: new Map(), template: stored(Buffer.alloc(0), req, null), algorithm })
      xmlReply(res, `<InitiateMultipartUploadResult xmlns="${XMLNS}"><Bucket>${xmlEscape(target.bucket)}</Bucket><Key>${xmlEscape(target.key)}</Key><UploadId>${id}</UploadId></InitiateMultipartUploadResult>`, algorithm ? { 'x-amz-checksum-algorithm': algorithm.toUpperCase() } : {})
    },

    UploadPart(req, res, target, { bytes, checksum }) {
      bucket(target.bucket)
      needLength(req)
      const u = upload(target, target.params.get('uploadId'))
      const n = target.params.get('partNumber')
      if (!/^\d+$/.test(n) || Number(n) < 1 || Number(n) > 10000) throw new S3Error(400, 'InvalidArgument', 'Part number must be an integer between 1 and 10000, inclusive', { ArgumentName: 'partNumber', ArgumentValue: n })
      const digest = md5(bytes)
      u.parts.set(Number(n), { bytes, md5: digest, etag: `"${digest.toString('hex')}"`, checksum })
      res.writeHead(200, { etag: `"${digest.toString('hex')}"`, ...checksumHeaders(checksum) })
      res.end()
    },

    CompleteMultipartUpload(req, res, target, { bytes }) {
      const objects = bucket(target.bucket)
      const u = upload(target, target.params.get('uploadId'))
      const malformed = () => new S3Error(400, 'MalformedXML', 'The XML you provided was not well-formed or did not validate against our published schema')
      const root = /^\s*(?:<\?xml[^>]*\?>\s*)?<CompleteMultipartUpload(?:\s[^>]*)?>([\s\S]*)<\/CompleteMultipartUpload>\s*$/.exec(bytes.toString())
      if (!root) throw malformed()
      const listed = [...root[1].matchAll(/<Part>([\s\S]*?)<\/Part>/g)].map(([, inner]) => ({
        number: /<PartNumber>\s*(\d+)\s*<\/PartNumber>/.exec(inner)?.[1],
        etag: /<ETag>([\s\S]*?)<\/ETag>/.exec(inner)?.[1],
        checksums: [...inner.matchAll(/<Checksum(CRC32C|CRC32|SHA1|SHA256|CRC64NVME)>([\s\S]*?)<\/Checksum\1>/g)].map(([, a, v]) => [a.toLowerCase(), v.trim()]),
      }))
      if (!listed.length || listed.some((p) => p.number === undefined || p.etag === undefined)) throw malformed()
      const parts = []
      for (const [i, p] of listed.entries()) {
        const n = Number(p.number)
        if (i && n <= Number(listed[i - 1].number)) throw new S3Error(400, 'InvalidPartOrder', 'The list of parts was not in ascending order. Parts must be ordered by part number.', { UploadId: target.params.get('uploadId') })
        const part = u.parts.get(n)
        const etag = `"${xmlUnescape(p.etag).trim().replace(/^"|"$/g, '')}"`
        if (!part || part.etag !== etag) throw new S3Error(400, 'InvalidPart', 'One or more of the specified parts could not be found. The part may not have been uploaded, or the specified entity tag may not match the part\'s entity tag.', { UploadId: target.params.get('uploadId'), PartNumber: n, ETag: etag })
        for (const [algorithm, value] of p.checksums)
          if (part.checksum?.algorithm === algorithm && part.checksum.value !== value) throw new S3Error(400, 'InvalidPart', `The ${algorithm.toUpperCase()} of part ${n} does not match the one it was uploaded with.`, { PartNumber: n })
        parts.push(part)
      }
      for (const [i, part] of parts.entries()) if (i < parts.length - 1 && part.bytes.length < MIN_PART) throw new S3Error(400, 'EntityTooSmall', 'Your proposed upload is smaller than the minimum allowed object size.', { ProposedSize: part.bytes.length, MinSizeAllowed: MIN_PART, PartNumber: listed[i].number })
      const whole = Buffer.concat(parts.map((p) => p.bytes))
      const checksum = fullObjectChecksum(req, whole)
      const o = { ...u.template, bytes: whole, etag: `"${md5(Buffer.concat(parts.map((p) => p.md5))).toString('hex')}-${parts.length}"`, lastModified: now(), checksum }
      objects.set(target.key, o)
      uploads.delete(target.params.get('uploadId'))
      xmlReply(
        res,
        `<CompleteMultipartUploadResult xmlns="${XMLNS}"><Location>${xmlEscape(`${s3.url}/${target.bucket}/${awsEncode(target.key).replace(/%2F/g, '/')}`)}</Location><Bucket>${xmlEscape(target.bucket)}</Bucket><Key>${xmlEscape(target.key)}</Key><ETag>${xmlEscape(o.etag)}</ETag></CompleteMultipartUploadResult>`,
      )
    },

    AbortMultipartUpload(req, res, target) {
      bucket(target.bucket)
      upload(target, target.params.get('uploadId'))
      uploads.delete(target.params.get('uploadId'))
      res.writeHead(204)
      res.end()
    },
  }

  await new Promise((ok) => server.listen(0, '127.0.0.1', ok))
  s3.url = `http://127.0.0.1:${server.address().port}`
  /// Make a bucket, if there is none of that name.
  s3.makeBucket = (name) => {
    if (!buckets.has(name)) buckets.set(name, new Map())
  }
  /// The objects of a bucket, by key, live.
  s3.objects = (name) => {
    const b = buckets.get(name)
    if (!b) throw new Error(`no bucket ${name}`)
    return b
  }
  /// Delete an object without a request; answers whether there was one.
  s3.remove = (name, key) => s3.objects(name).delete(key)
  /// Store an object without a request, replacing any of that key.
  s3.put = (name, key, bytes, contentType = 'application/octet-stream') => {
    const b = Buffer.from(bytes)
    s3.objects(name).set(key, { bytes: b, contentType, etag: `"${md5(b).toString('hex')}"`, lastModified: now(), meta: {}, headers: {}, checksum: null })
  }
  /// Make the requests to `bucket`, for `key` (an upload's key, for a
  /// multipart one), for `op` (one name or a list of them) fail, each of the
  /// three any if not given, until `times` of them have or until
  /// `clearFailures`, the earliest rule matching a request failing it.
  /// `mode` is `{status, code, message}`, an S3 error answered once the
  /// body is read (code and message by status, if not given); `{delayMs}`,
  /// the request handled as ever, that long after it came; `'hang'`,
  /// read the request and never answer; `'store-then-hang'`, for a request
  /// that writes an object (`WRITES`), store it as if it succeeded and never
  /// answer, and for any other `'hang'`; `'reset'`, destroy the
  /// connection at once; or `'cut'`, answer as ever but send only the head
  /// and the first half of the body's bytes, then destroy the connection.
  /// Answers the rule, whose `count` is how many it has failed.
  s3.fail = ({ bucket, key, op, times = Infinity, mode }) => {
    if (!['hang', 'store-then-hang', 'reset', 'cut'].includes(mode) && !(Number.isInteger(mode?.status) && mode.status >= 300) && !(Number.isInteger(mode?.delayMs) && mode.delayMs > 0))
      throw new Error(`fail: mode ${JSON.stringify(mode)}: not 'hang', 'store-then-hang', 'reset', 'cut', {status, code} or {delayMs}`)
    const rule = { bucket, key, op, times, mode, count: 0 }
    failures.push(rule)
    return rule
  }
  s3.clearFailures = () => {
    failures.length = 0
  }
  /// Stop, dropping every connection, those held by `'hang'` among them.
  s3.close = async () => {
    const closed = new Promise((ok) => server.close(ok))
    for (const c of sockets) c.destroy()
    await closed
  }
  return s3
}

// ------------------------------------------------------------- requests

/// A request target, path-style: its bucket and key, decoded, its query
/// parameters, decoded, and the path and query as SigV4 canonicalises them,
/// each segment and parameter decoded and encoded again once.
function parseTarget(url) {
  const q = url.indexOf('?')
  const rawPath = q < 0 ? url : url.slice(0, q)
  const rawQuery = q < 0 ? '' : url.slice(q + 1)
  const invalid = () => new S3Error(400, 'InvalidURI', "Couldn't parse the specified URI.", { URI: url })
  if (!rawPath.startsWith('/')) throw invalid()
  let segments, query
  try {
    segments = rawPath.split('/').map(decodeURIComponent)
    query = rawQuery
      .split('&')
      .filter(Boolean)
      .map((p) => {
        const eq = p.indexOf('=')
        return eq < 0 ? [decodeURIComponent(p), ''] : [decodeURIComponent(p.slice(0, eq)), decodeURIComponent(p.slice(eq + 1))]
      })
  } catch {
    throw invalid()
  }
  const canonicalQuery = query
    .map(([k, v]) => [awsEncode(k), awsEncode(v)])
    .sort(([a, x], [b, y]) => (a < b ? -1 : a > b ? 1 : x < y ? -1 : x > y ? 1 : 0))
    .map(([k, v]) => `${k}=${v}`)
    .join('&')
  const key = segments.slice(2).join('/')
  if (Buffer.byteLength(key) > 1024) throw new S3Error(400, 'KeyTooLongError', 'Your key is too long', { Size: Buffer.byteLength(key), MaxSizeAllowed: 1024 })
  return {
    bucket: segments[1] || null,
    key: key || null,
    query,
    params: new Map(query),
    canonicalPath: segments.map(awsEncode).join('/'),
    canonicalQuery,
  }
}

/// The S3 operation a request is, by its method, path, query and headers;
/// `'Unknown'` for any other, among them one with a query parameter the
/// operation does not take (`x-id`, which the AWS SDK adds, aside).
function classify(req, { bucket, key, params }) {
  const has = (p) => params.has(p)
  const op = (() => {
    if (!bucket) return 'Unknown'
    if (!key) {
      if (req.method === 'PUT') return 'CreateBucket'
      if (req.method === 'GET' && params.get('list-type') === '2') return 'ListObjectsV2'
      if (req.method === 'POST' && has('delete')) return 'DeleteObjects'
      return 'Unknown'
    }
    const copy = req.headers['x-amz-copy-source'] !== undefined
    if (req.method === 'PUT') {
      if (has('partNumber') && has('uploadId')) return copy ? 'Unknown' : 'UploadPart'
      return copy ? 'CopyObject' : 'PutObject'
    }
    if (req.method === 'GET') return 'GetObject'
    if (req.method === 'HEAD') return 'HeadObject'
    if (req.method === 'DELETE') return has('uploadId') ? 'AbortMultipartUpload' : 'DeleteObject'
    if (req.method === 'POST') return has('uploads') ? 'CreateMultipartUpload' : has('uploadId') ? 'CompleteMultipartUpload' : 'Unknown'
    return 'Unknown'
  })()
  if (op === 'Unknown') return op
  return [...params.keys()].every((p) => p === 'x-id' || PARAMS[op].includes(p)) ? op : 'Unknown'
}

/// A request's headers by lowercase name, each with its values in order.
function rawHeaders(req) {
  const headers = new Map()
  for (let i = 0; i < req.rawHeaders.length; i += 2) {
    const name = req.rawHeaders[i].toLowerCase()
    headers.set(name, [...(headers.get(name) ?? []), req.rawHeaders[i + 1]])
  }
  return headers
}

async function readBody(req) {
  const chunks = []
  for await (const c of req) chunks.push(c)
  return Buffer.concat(chunks)
}

/// A body to store has a length: its `Content-Length`, or, streamed
/// `aws-chunked` (which may come `Transfer-Encoding: chunked`), its
/// `x-amz-decoded-content-length`, which `decodePayload` holds it to.
function needLength(req) {
  if (req.headers['content-length'] === undefined && !(req.headers['x-amz-content-sha256'] in STREAMING))
    throw new S3Error(411, 'MissingContentLength', 'You must provide the Content-Length HTTP header.')
}

// ------------------------------------------------------------- checksums

// x-amz-checksum-crc64nvme is not checked: neither node:crypto nor zlib
// computes CRC-64/NVME. The rest are.
const CRC32C_TABLE = Int32Array.from({ length: 256 }, (_, n) => {
  let c = n
  for (let k = 0; k < 8; k++) c = c & 1 ? (c >>> 1) ^ 0x82f63b78 : c >>> 1
  return c
})
const u32 = (n) => {
  const b = Buffer.alloc(4)
  b.writeUInt32BE(n >>> 0)
  return b
}
const CHECKSUMS = {
  crc32: (b) => u32(crc32(b)),
  crc32c: (b) => {
    let c = -1
    for (let i = 0; i < b.length; i++) c = CRC32C_TABLE[(c ^ b[i]) & 0xff] ^ (c >>> 8)
    return u32(~c)
  },
  sha1: (b) => createHash('sha1').update(b).digest(),
  sha256: (b) => createHash('sha256').update(b).digest(),
}
const CHECKSUM_NAMES = ['crc32', 'crc32c', 'crc64nvme', 'sha1', 'sha256']

/// Check a body against its `Content-MD5` and the one `x-amz-checksum-*`
/// header or trailer it may carry; answers that checksum, `{algorithm,
/// value}`, or null.
function checkChecksums(req, { bytes, trailers }, rec) {
  const md5Header = req.headers['content-md5']
  if (md5Header !== undefined) {
    if (!/^[A-Za-z0-9+/]{22}==$/.test(md5Header)) throw new S3Error(400, 'InvalidDigest', 'The Content-MD5 you specified was invalid.', { 'Content-MD5': md5Header })
    if (md5(bytes).toString('base64') !== md5Header) throw new S3Error(400, 'BadDigest', 'The Content-MD5 you specified did not match what we received.', { ExpectedDigest: md5Header, CalculatedDigest: md5(bytes).toString('base64') })
  }
  const given = []
  for (const name of CHECKSUM_NAMES) {
    const header = req.headers[`x-amz-checksum-${name}`]
    if (header !== undefined) given.push([name, header, 'header'])
    const trailer = trailers.get(`x-amz-checksum-${name}`)
    if (trailer !== undefined) given.push([name, trailer, 'trailer'])
  }
  const sdk = req.headers['x-amz-sdk-checksum-algorithm']?.toLowerCase()
  if (given.length > 1) throw new S3Error(400, 'InvalidRequest', 'Expecting a single x-amz-checksum- header. Multiple checksum Types are not allowed.')
  if (!given.length) {
    if (sdk !== undefined) throw new S3Error(400, 'InvalidRequest', `x-amz-sdk-checksum-algorithm specified, but no corresponding x-amz-checksum-* or x-amz-trailer headers were found.`)
    return null
  }
  const [algorithm, value, where] = given[0]
  if (sdk !== undefined && sdk !== algorithm) throw new S3Error(400, 'InvalidRequest', `Value for x-amz-sdk-checksum-algorithm header is ${sdk}, but the checksum given is x-amz-checksum-${algorithm}.`)
  rec.checksum = `${algorithm} ${where}${CHECKSUMS[algorithm] ? '' : ' (not checked)'}`
  if (CHECKSUMS[algorithm] && CHECKSUMS[algorithm](bytes).toString('base64') !== value)
    throw new S3Error(400, 'BadDigest', `The ${algorithm.toUpperCase()} you specified did not match the calculated checksum.`)
  return { algorithm, value }
}

/// The checksum of the whole object a CompleteMultipartUpload's
/// `x-amz-checksum-*` header gives, checked where it is of the whole object
/// (a composite one, `<value>-<parts>`, is not, and is not kept).
function fullObjectChecksum(req, whole) {
  for (const algorithm of CHECKSUM_NAMES) {
    const value = req.headers[`x-amz-checksum-${algorithm}`]
    if (value === undefined || /-\d+$/.test(value)) continue
    if (CHECKSUMS[algorithm] && CHECKSUMS[algorithm](whole).toString('base64') !== value)
      throw new S3Error(400, 'BadDigest', `The ${algorithm.toUpperCase()} you specified did not match the calculated checksum.`)
    return { algorithm, value }
  }
  return null
}

const checksumHeaders = (checksum) => (checksum ? { [`x-amz-checksum-${checksum.algorithm}`]: checksum.value, 'x-amz-checksum-type': 'FULL_OBJECT' } : {})

// ------------------------------------------------------------- objects

const now = () => new Date(Math.floor(Date.now() / 1000) * 1000)

/// An object of `bytes`, with the type, metadata and headers `req` gives.
function stored(bytes, req, checksum) {
  const meta = {}
  const headers = {}
  for (const [name, value] of Object.entries(req.headers)) {
    if (name.startsWith('x-amz-meta-')) meta[name.slice('x-amz-meta-'.length)] = value
    if (KEPT.includes(name)) headers[name] = value
  }
  const encoding = (req.headers['content-encoding'] ?? '')
    .split(',')
    .map((e) => e.trim())
    .filter((e) => e && e !== 'aws-chunked')
  if (encoding.length) headers['content-encoding'] = encoding.join(', ')
  return { bytes, contentType: req.headers['content-type'] ?? null, etag: `"${md5(bytes).toString('hex')}"`, lastModified: now(), meta, headers, checksum }
}

function objectHeaders(o) {
  const headers = {
    'content-type': o.contentType ?? 'binary/octet-stream',
    'content-length': o.bytes.length,
    etag: o.etag,
    'last-modified': o.lastModified.toUTCString(),
    'accept-ranges': 'bytes',
    ...o.headers,
  }
  for (const [name, value] of Object.entries(o.meta)) headers[`x-amz-meta-${name}`] = value
  return headers
}

const etagMatches = (header, etag) => header.split(',').some((t) => t.trim() === '*' || t.trim().replace(/^W\//, '') === etag || `"${t.trim()}"` === etag)

/// Answer a GetObject or HeadObject's conditions, as S3 weighs them: true
/// when they were answered (304) and the object is not to be sent.
function conditional(req, res, o) {
  const h = req.headers
  const since = (d) => (d === undefined || Number.isNaN(Date.parse(d)) ? null : Date.parse(d))
  if (h['if-match'] !== undefined ? !etagMatches(h['if-match'], o.etag) : since(h['if-unmodified-since']) !== null && o.lastModified.getTime() > since(h['if-unmodified-since']))
    throw new S3Error(412, 'PreconditionFailed', 'At least one of the pre-conditions you specified did not hold', { Condition: h['if-match'] !== undefined ? 'If-Match' : 'If-Unmodified-Since' })
  if (h['if-none-match'] !== undefined ? etagMatches(h['if-none-match'], o.etag) : since(h['if-modified-since']) !== null && o.lastModified.getTime() <= since(h['if-modified-since'])) {
    res.writeHead(304, { etag: o.etag, 'last-modified': o.lastModified.toUTCString() })
    res.end()
    return true
  }
  return false
}

/// A PutObject's `If-None-Match: *` and `If-Match`, against the object it
/// would replace.
function precondition(req, existing) {
  const ifNoneMatch = req.headers['if-none-match']
  const ifMatch = req.headers['if-match']
  if (ifNoneMatch !== undefined && ifNoneMatch.trim() !== '*') throw new S3Error(501, 'NotImplemented', 'A header you provided implies functionality that is not implemented', { Header: 'If-None-Match' })
  if (ifNoneMatch !== undefined && existing) throw new S3Error(412, 'PreconditionFailed', 'At least one of the pre-conditions you specified did not hold', { Condition: 'If-None-Match' })
  if (ifMatch !== undefined && !existing) throw new S3Error(404, 'NoSuchKey', 'The specified key does not exist.')
  if (ifMatch !== undefined && !etagMatches(ifMatch, existing.etag)) throw new S3Error(412, 'PreconditionFailed', 'At least one of the pre-conditions you specified did not hold', { Condition: 'If-Match' })
}

/// The inclusive byte range a `Range` header asks of `size` bytes, or null
/// for the whole (no header, or one S3 ignores: not one `bytes=` range).
function parseRange(header, size) {
  const m = /^bytes=(\d*)-(\d*)$/.exec(header?.trim() ?? '')
  if (!m || (m[1] === '' && m[2] === '')) return null
  const unsatisfiable = () => new S3Error(416, 'InvalidRange', 'The requested range is not satisfiable', { RangeRequested: header, ActualObjectSize: size }, { 'content-range': `bytes */${size}` })
  if (m[1] === '') {
    const n = Number(m[2])
    if (n === 0 || size === 0) throw unsatisfiable()
    return [Math.max(0, size - n), size - 1]
  }
  const start = Number(m[1])
  const end = m[2] === '' ? size - 1 : Math.min(Number(m[2]), size - 1)
  if (m[2] !== '' && Number(m[2]) < start) return null
  if (start >= size) throw unsatisfiable()
  return [start, end]
}

// ------------------------------------------------------------- encoding

const md5 = (b) => createHash('md5').update(b).digest()
const sha256Hex = (b) => createHash('sha256').update(b).digest('hex')
const hmac = (key, data) => createHmac('sha256', key).update(data).digest()

/// UTF-8 bytes in order, as S3 lists keys.
const byteOrder = (a, b) => Buffer.compare(Buffer.from(a), Buffer.from(b))

/// Percent-encode all but `A-Z a-z 0-9 - _ . ~`, as SigV4 does.
const awsEncode = (s) => encodeURIComponent(s).replace(/[!'()*]/g, (c) => `%${c.charCodeAt(0).toString(16).toUpperCase()}`)

const xmlEscape = (s) =>
  s.replace(/[&<>"'\u0000-\u001f]/g, (c) => ({ '&': '&amp;', '<': '&lt;', '>': '&gt;', '"': '&quot;', "'": '&apos;' })[c] ?? `&#${c.charCodeAt(0)};`)

const xmlUnescape = (s) =>
  s.replace(/&(amp|lt|gt|quot|apos|#\d+|#x[0-9a-fA-F]+);/g, (_, e) =>
    e[0] === '#' ? String.fromCodePoint(e[1] === 'x' ? parseInt(e.slice(2), 16) : Number(e.slice(1))) : { amp: '&', lt: '<', gt: '>', quot: '"', apos: "'" }[e],
  )

function errorXml(code, message, resource, requestId, extra) {
  const fields = Object.entries(extra)
    .map(([k, v]) => `<${k}>${xmlEscape(String(v))}</${k}>`)
    .join('')
  return `<?xml version="1.0" encoding="UTF-8"?>\n<Error><Code>${code}</Code><Message>${xmlEscape(message)}</Message>${fields}<Resource>${xmlEscape(resource)}</Resource><RequestId>${requestId}</RequestId></Error>`
}