## APKINDEX parsing and dependency resolution.
##
## An APKINDEX is blank-line-separated records of single-letter fields:
##
##   P:openssl-dev
##   V:3.3.7-r1
##   D:libcrypto3=3.3.7-r1 libssl3=3.3.7-r1 pkgconfig
##   p:openssl3-dev=3.3.7-r1 pc:libssl=3.3.7
##
## `D:` depends and `p:` provides both carry optional version constraints, and a
## dependency may name a *provide* (`so:libssl.so.3`) rather than a package.

import std/[sets, strutils, tables]

type
  Pkg* = object
    name*, version*, arch*, description*, origin*, license*: string
    size*: int              ## download size in bytes, from `S:`
    checksum*: string       ## `C:` — apk's control-segment hash, not the file's
    depends*: seq[string]
    provides*: seq[string]
    repo*: string           ## main | community | …, filled in by the caller

  Index* = object
    packages*: OrderedTable[string, Pkg]
    providers*: Table[string, string]  ## provide name → package name

func stripConstraint*(dep: string): string =
  ## `musl=1.2.5-r11` → `musl`; `so:libssl.so.3=3` → `so:libssl.so.3`.
  ## Alpine writes constraints as =, >=, <=, >, < or ~.
  for i, c in dep:
    if c in {'=', '>', '<', '~'}:
      return dep[0 ..< i]
  dep

func isConflict*(dep: string): bool = dep.startsWith("!")

proc parseIndex*(text: string, repo = ""): Index =
  ## Parse one APKINDEX body. Later records win, matching apk's own behavior of
  ## letting a repository shadow an earlier one.
  var
    idx: Index
    cur: Pkg

  proc flush(idx: var Index, cur: var Pkg, repo: string) =
    if cur.name.len > 0:
      cur.repo = repo
      idx.packages[cur.name] = cur
      idx.providers[cur.name] = cur.name
      for p in cur.provides:
        idx.providers[stripConstraint(p)] = cur.name
    cur = Pkg()

  for rawLine in text.splitLines:
    let line = rawLine.strip(leading = false)
    if line.len == 0:
      flush(idx, cur, repo)
      continue
    if line.len < 2 or line[1] != ':':
      continue
    let val = line[2 .. ^1]
    case line[0]
    of 'P': cur.name = val
    of 'V': cur.version = val
    of 'A': cur.arch = val
    of 'T': cur.description = val
    of 'L': cur.license = val
    of 'o': cur.origin = val
    of 'C': cur.checksum = val
    of 'S': cur.size = try: parseInt(val) except ValueError: 0
    of 'D': cur.depends = val.splitWhitespace()
    of 'p': cur.provides = val.splitWhitespace()
    else: discard
  flush(idx, cur, repo)
  idx

proc merge*(a: var Index, b: Index) =
  ## Fold another repository's index in. `b` wins on collisions.
  for name, pkg in b.packages:
    a.packages[name] = pkg
  for provide, name in b.providers:
    a.providers[provide] = name

proc find*(idx: Index, want: string): string =
  ## Resolve a name-or-provide to a package name, or "" if nothing supplies it.
  let key = stripConstraint(want)
  if key in idx.packages: return key
  idx.providers.getOrDefault(key, "")

proc resolve*(idx: Index, wanted: openArray[string], withDeps = true): seq[Pkg] =
  ## Depth-first closure over `wanted`, in install order (dependencies first).
  ## Raises KeyError naming the first request nothing in the index supplies.
  var seen: HashSet[string]
  var order: seq[Pkg]

  proc visit(want, requestedBy: string) =
    if isConflict(want): return
    let name = idx.find(want)
    if name.len == 0:
      let ctx = if requestedBy.len > 0: " (needed by " & requestedBy & ")" else: ""
      raise newException(KeyError, "no package provides '" &
                         stripConstraint(want) & "'" & ctx)
    if name in seen: return
    seen.incl name
    let pkg = idx.packages[name]
    if withDeps:
      for dep in pkg.depends:
        visit(dep, name)
    order.add pkg

  for want in wanted:
    visit(want, "")
  order