///|
pub(all) enum Rule {
  Overlap
  Fit
  Size
  Contrast
  Containment
  Endpoint
  Limit
} derive(Eq, Debug)

///|
pub struct Finding {
  rule : Rule
  identities : ReadOnlyArray[String]
  message : String
} derive(Eq, Debug)

///|
pub extend Rule with Eq::{equal, not_equal}

///|
pub extend Rule with @debug.Debug::{to_repr}

///|
pub extend Finding with Eq::{equal, not_equal}

///|
pub extend Finding with @debug.Debug::{to_repr}

///|
fn crosses(a : Point, b : Point, box : Rect) -> Bool {
  let left = box.x + 0.5
  let right = box.x + box.width - 0.5
  let top = box.y + 0.5
  let bottom = box.y + box.height - 0.5
  if left >= right || top >= bottom {
    return false
  }
  let dx = b.x - a.x
  let dy = b.y - a.y
  let mut low = 0.0
  let mut high = 1.0
  for
    (p, q) in [
      (-dx, a.x - left),
      (dx, right - a.x),
      (-dy, a.y - top),
      (dy, bottom - a.y),
    ] {
    if p == 0.0 {
      if q < 0.0 {
        return false
      }
    } else {
      let t = q / p
      if p < 0.0 {
        low = Double::max(low, t)
      } else {
        high = Double::min(high, t)
      }
      if low > high {
        return false
      }
    }
  }
  low < high
}

///|
/// Check measured geometry independently of its painter. Intended nested
/// containment is allowed; ownership, labels, true outline ports and unrelated
/// line intersections are inspected under one explicit work/finding budget.
pub fn check(
  geometry : Geometry,
  palette : @theme.Palette,
  work_limit~ : Int32 = 1000000,
) -> ReadOnlyArray[Finding] {
  let findings = []
  let mut work = 0
  let mut exhausted = false
  fn charge(units : Int32) -> Bool {
    if exhausted {
      return false
    }
    if units < 0 || units > work_limit - work {
      findings.push({
        rule: Limit,
        identities: [],
        message: "Legibility search limit exceeded",
      })
      exhausted = true
      return false
    }
    work += units
    true
  }
  fn add(rule : Rule, ids : ArrayView[String], message : String) {
    if exhausted {
      return
    }
    if findings.length() < 255 {
      findings.push({
        rule,
        identities: ReadOnlyArray::from_array(ids),
        message,
      })
    } else {
      findings.push({
        rule: Limit,
        identities: [],
        message: "Legibility finding limit exceeded",
      })
      exhausted = true
    }
  }
  let by_id : Map[String, Shape] = Map([])
  for shape in geometry.shapes {
    if !charge(shape.id.length() + 1) {
      break
    }
    by_id[shape.id] = shape
  }
  fn ancestor(child : Shape, parent : String) -> Bool {
    let mut current = child.parent
    let seen = Map([])
    while current is Some(id) {
      if !charge(1) || seen.contains(id) {
        return false
      }
      seen[id] = true
      if id == parent {
        return true
      }
      current = by_id.get(id).bind(s => s.parent)
    }
    false
  }
  let labels = []
  for i, shape in geometry.shapes {
    if !charge(1) {
      break
    }
    if !shape.box.contains(shape.outline_box, tolerance=0.1) {
      add(Containment, [shape.id], "Painted outline leaves its layout bounds")
    }
    if shape.parent is Some(parent) {
      if by_id.get(parent) is Some(parent_shape) {
        if !parent_shape.box.contains(shape.box, tolerance=0.1) {
          add(
            Containment,
            [shape.id, parent],
            "Shape \{shape.id} leaves its owner \{parent}",
          )
        }
      } else {
        add(Containment, [shape.id, parent], "Shape owner is absent")
      }
    }
    if shape.label is Some(label) {
      labels.push(label)
      if !shape.box.contains(label.box, tolerance=0.1) {
        add(Fit, [shape.id], "Label overflows \{shape.id}")
      }
      if shape.kind == Node {
        let boundary = outline(shape.shape, shape.outline_box)
        for j, a in boundary {
          if !charge(1) {
            break
          }
          if crosses(a, boundary[(j + 1) % boundary.length()], label.box) {
            add(Fit, [shape.id], "Label intersects its painted outline")
            break
          }
        }
      }
    }
    for j in (i + 1).. {
        ["f-circ", "sm-circ", "anchor", "fork"].contains(s.shape) &&
        s.outline_box.contains(label.box)
      })
      .unwrap_or(false)
    let ink = if filled {
      palette.bg
    } else {
      label.family.map(f => palette.family(f).ink).unwrap_or(palette.text)
    }
    let bg = if filled {
      label.family.map(f => palette.family(f).ink).unwrap_or(palette.text)
    } else {
      label.family
      .map(f => @theme.over(palette.family(f).fill, palette.bg))
      .unwrap_or(palette.bg)
    }
    if @theme.contrast(ink, bg) < 4.5 {
      add(Contrast, [label.owner], "Text contrast is below 4.5:1")
    }
    if !charge(label.text.length()) {
      break
    }
    let (w, h) = measure(
      label.text,
      size=label.size.ceil().to_int(),
      weight=label.weight,
    )
    if w > label.box.width + 0.1 || h > label.box.height + 0.1 {
      add(Fit, [label.owner], "Measured label exceeds its bounds")
    }
    for j in (i + 1)..