///|
pub(all) struct ObjectRef {
  kind : String
  id : String
} derive(Debug, Eq)

///|
pub(all) struct SubjectRef {
  kind : String
  id : String
  relation : String
} derive(Debug, Eq)

///|
pub(all) struct RelationTuple {
  object : ObjectRef
  relation : String
  subject : SubjectRef
} derive(Debug, Eq)

///|
pub(all) struct PolicyRule {
  object_namespace : String
  permission : String
  source_relation : String
  target_permission : String
  effect : Int
} derive(Debug, Eq)

///|
pub(all) struct PolicyEngine {
  tuples : Array[RelationTuple]
  rules : Array[PolicyRule]
  max_depth : Int
} derive(Debug)

///|
pub(all) struct CheckResult {
  allowed : Bool
  denied : Bool
  reason : String
  steps : Array[String]
  max_depth_seen : Int
  cycle_detected : Bool
} derive(Debug)

///|
pub(all) struct CheckRequest {
  object : ObjectRef
  permission : String
  principal : SubjectRef
} derive(Debug, Eq)

///|
pub(all) struct PolicyStats {
  tuples : Int
  rules : Int
  object_kinds : Int
  relations : Int
  permissions : Int
} derive(Debug, Eq)

///|
pub(all) struct ValidationIssue {
  code : String
  message : String
} derive(Debug, Eq)

///|
priv struct RelationMatch {
  matched : Bool
  steps : Array[String]
  max_depth_seen : Int
  cycle_detected : Bool
}

///|
priv struct PermissionMatch {
  allowed : Bool
  denied : Bool
  steps : Array[String]
  max_depth_seen : Int
  cycle_detected : Bool
}

///|
pub fn ObjectRef::new(kind : String, id : String) -> ObjectRef {
  { kind, id }
}

///|
pub fn ObjectRef::key(self : ObjectRef) -> String {
  "\{self.kind}:\{self.id}"
}

///|
pub fn SubjectRef::direct(kind : String, id : String) -> SubjectRef {
  { kind, id, relation: "" }
}

///|
pub fn SubjectRef::userset(
  kind : String,
  id : String,
  relation : String,
) -> SubjectRef {
  { kind, id, relation }
}

///|
pub fn SubjectRef::object(self : SubjectRef) -> ObjectRef {
  ObjectRef::new(self.kind, self.id)
}

///|
pub fn SubjectRef::key(self : SubjectRef) -> String {
  if self.relation == "" {
    "\{self.kind}:\{self.id}"
  } else {
    "\{self.kind}:\{self.id}#\{self.relation}"
  }
}

///|
pub fn RelationTuple::new(
  object : ObjectRef,
  relation : String,
  subject : SubjectRef,
) -> RelationTuple {
  { object, relation, subject }
}

///|
pub fn RelationTuple::key(self : RelationTuple) -> String {
  "\{self.object.key()}#\{self.relation}@\{self.subject.key()}"
}

///|
pub fn PolicyRule::direct_allow(
  object_namespace : String,
  permission : String,
  source_relation : String,
) -> PolicyRule {
  {
    object_namespace,
    permission,
    source_relation,
    target_permission: "",
    effect: 1,
  }
}

///|
pub fn PolicyRule::direct_deny(
  object_namespace : String,
  permission : String,
  source_relation : String,
) -> PolicyRule {
  {
    object_namespace,
    permission,
    source_relation,
    target_permission: "",
    effect: -1,
  }
}

///|
pub fn PolicyRule::traverse_allow(
  object_namespace : String,
  permission : String,
  source_relation : String,
  target_permission : String,
) -> PolicyRule {
  {
    object_namespace,
    permission,
    source_relation,
    target_permission,
    effect: 1,
  }
}

///|
pub fn PolicyRule::traverse_deny(
  object_namespace : String,
  permission : String,
  source_relation : String,
  target_permission : String,
) -> PolicyRule {
  {
    object_namespace,
    permission,
    source_relation,
    target_permission,
    effect: -1,
  }
}

///|
pub fn PolicyEngine::new(max_depth? : Int = 16) -> PolicyEngine {
  {
    tuples: [],
    rules: [],
    max_depth: if max_depth < 1 {
      1
    } else {
      max_depth
    },
  }
}

///|
pub fn PolicyEngine::add_tuple(
  self : PolicyEngine,
  tuple : RelationTuple,
) -> Bool {
  for current in self.tuples {
    if current == tuple {
      return false
    }
  }
  self.tuples.push(tuple)
  true
}

///|
pub fn PolicyEngine::remove_tuple(
  self : PolicyEngine,
  tuple : RelationTuple,
) -> Bool {
  for i = 0; i < self.tuples.length(); i = i + 1 {
    if self.tuples[i] == tuple {
      ignore(self.tuples.remove(i))
      return true
    }
  }
  false
}

///|
pub fn PolicyEngine::add_rule(self : PolicyEngine, rule : PolicyRule) -> Bool {
  for current in self.rules {
    if current == rule {
      return false
    }
  }
  self.rules.push(rule)
  true
}

///|
pub fn PolicyEngine::tuple_count(self : PolicyEngine) -> Int {
  self.tuples.length()
}

///|
pub fn PolicyEngine::rule_count(self : PolicyEngine) -> Int {
  self.rules.length()
}

///|
fn string_array_contains(items : Array[String], target : String) -> Bool {
  for item in items {
    if item == target {
      return true
    }
  }
  false
}

///|
fn copy_strings(items : Array[String]) -> Array[String] {
  let result : Array[String] = []
  for item in items {
    result.push(item)
  }
  result
}

///|
fn append_strings(target : Array[String], source : Array[String]) -> Unit {
  for item in source {
    target.push(item)
  }
}

///|
fn max_int(a : Int, b : Int) -> Int {
  if a > b {
    a
  } else {
    b
  }
}

///|
fn direct_subject_matches(subject : SubjectRef, principal : SubjectRef) -> Bool {
  subject.relation == "" &&
  principal.relation == "" &&
  subject.kind == principal.kind &&
  subject.id == principal.id
}

///|
fn PolicyEngine::relation_contains(
  self : PolicyEngine,
  object : ObjectRef,
  relation : String,
  principal : SubjectRef,
  depth : Int,
  visited : Array[String],
) -> RelationMatch {
  let steps : Array[String] = []
  let query_key = "relation|\{object.key()}#\{relation}@\{principal.key()}"
  if depth > self.max_depth {
    steps.push("depth-limit \{query_key}")
    return {
      matched: false,
      steps,
      max_depth_seen: depth,
      cycle_detected: false,
    }
  }
  if string_array_contains(visited, query_key) {
    steps.push("cycle \{query_key}")
    return {
      matched: false,
      steps,
      max_depth_seen: depth,
      cycle_detected: true,
    }
  }
  let next_visited = copy_strings(visited)
  next_visited.push(query_key)
  let mut max_depth_seen = depth
  let mut cycle_detected = false
  for tuple in self.tuples {
    if tuple.object == object && tuple.relation == relation {
      steps.push("inspect \{tuple.key()}")
      if direct_subject_matches(tuple.subject, principal) {
        steps.push("match direct \{principal.key()}")
        return { matched: true, steps, max_depth_seen, cycle_detected }
      }
      if tuple.subject.relation != "" {
        let nested = self.relation_contains(
          tuple.subject.object(),
          tuple.subject.relation,
          principal,
          depth + 1,
          next_visited,
        )
        append_strings(steps, nested.steps)
        max_depth_seen = max_int(max_depth_seen, nested.max_depth_seen)
        cycle_detected = cycle_detected || nested.cycle_detected
        if nested.matched {
          steps.push("match userset \{tuple.subject.key()}")
          return { matched: true, steps, max_depth_seen, cycle_detected }
        }
      }
    }
  }
  steps.push("no-match \{query_key}")
  { matched: false, steps, max_depth_seen, cycle_detected }
}

///|
fn PolicyEngine::permission_effect(
  self : PolicyEngine,
  object : ObjectRef,
  permission : String,
  principal : SubjectRef,
  depth : Int,
  visited : Array[String],
) -> PermissionMatch {
  let steps : Array[String] = []
  let query_key = "permission|\{object.key()}#\{permission}@\{principal.key()}"
  if depth > self.max_depth {
    steps.push("depth-limit \{query_key}")
    return {
      allowed: false,
      denied: false,
      steps,
      max_depth_seen: depth,
      cycle_detected: false,
    }
  }
  if string_array_contains(visited, query_key) {
    steps.push("cycle \{query_key}")
    return {
      allowed: false,
      denied: false,
      steps,
      max_depth_seen: depth,
      cycle_detected: true,
    }
  }
  let next_visited = copy_strings(visited)
  next_visited.push(query_key)
  let mut allowed = false
  let mut denied = false
  let mut max_depth_seen = depth
  let mut cycle_detected = false
  for rule in self.rules {
    if rule.object_namespace == object.kind && rule.permission == permission {
      if rule.target_permission == "" {
        let relation_result = self.relation_contains(
          object,
          rule.source_relation,
          principal,
          depth + 1,
          next_visited,
        )
        append_strings(steps, relation_result.steps)
        max_depth_seen = max_int(max_depth_seen, relation_result.max_depth_seen)
        cycle_detected = cycle_detected || relation_result.cycle_detected
        if relation_result.matched {
          if rule.effect < 0 {
            denied = true
            steps.push("rule deny \{object.kind}#\{permission}")
          } else {
            allowed = true
            steps.push("rule allow \{object.kind}#\{permission}")
          }
        }
      } else {
        for tuple in self.tuples {
          if tuple.object == object &&
            tuple.relation == rule.source_relation &&
            tuple.subject.relation == "" {
            steps.push("traverse \{tuple.key()}")
            let nested = self.permission_effect(
              tuple.subject.object(),
              rule.target_permission,
              principal,
              depth + 1,
              next_visited,
            )
            append_strings(steps, nested.steps)
            max_depth_seen = max_int(max_depth_seen, nested.max_depth_seen)
            cycle_detected = cycle_detected || nested.cycle_detected
            if nested.denied || nested.allowed {
              if rule.effect < 0 {
                denied = true
                steps.push("rule deny via \{tuple.subject.object().key()}")
              } else if nested.allowed && !nested.denied {
                allowed = true
                steps.push("rule allow via \{tuple.subject.object().key()}")
              }
            }
          }
        }
      }
    }
  }
  { allowed, denied, steps, max_depth_seen, cycle_detected }
}

///|
pub fn PolicyEngine::check(
  self : PolicyEngine,
  object : ObjectRef,
  permission : String,
  principal : SubjectRef,
) -> CheckResult {
  let effect = self.permission_effect(object, permission, principal, 0, [])
  if effect.denied {
    {
      allowed: false,
      denied: true,
      reason: "explicit-deny",
      steps: effect.steps,
      max_depth_seen: effect.max_depth_seen,
      cycle_detected: effect.cycle_detected,
    }
  } else if effect.allowed {
    {
      allowed: true,
      denied: false,
      reason: "allow",
      steps: effect.steps,
      max_depth_seen: effect.max_depth_seen,
      cycle_detected: effect.cycle_detected,
    }
  } else {
    {
      allowed: false,
      denied: false,
      reason: "no-matching-rule",
      steps: effect.steps,
      max_depth_seen: effect.max_depth_seen,
      cycle_detected: effect.cycle_detected,
    }
  }
}

///|
pub fn CheckResult::to_json(self : CheckResult) -> String {
  let buf = StringBuilder()
  buf.write_string(
    "{\"allowed\":\{self.allowed},\"denied\":\{self.denied},\"reason\":\"\{self.reason}\",\"max_depth_seen\":\{self.max_depth_seen},\"cycle_detected\":\{self.cycle_detected},\"steps\":[",
  )
  for i = 0; i < self.steps.length(); i = i + 1 {
    if i > 0 {
      buf.write_char(',')
    }
    buf.write_string("\"")
    buf.write_string(self.steps[i])
    buf.write_string("\"")
  }
  buf.write_string("]}")
  buf.to_string()
}

///|
pub fn CheckRequest::new(
  object : ObjectRef,
  permission : String,
  principal : SubjectRef,
) -> CheckRequest {
  { object, permission, principal }
}

///|
pub fn PolicyEngine::check_many(
  self : PolicyEngine,
  requests : Array[CheckRequest],
) -> Array[CheckResult] {
  let results : Array[CheckResult] = []
  for request in requests {
    results.push(
      self.check(request.object, request.permission, request.principal),
    )
  }
  results
}

///|
pub fn PolicyEngine::filter_allowed(
  self : PolicyEngine,
  objects : Array[ObjectRef],
  permission : String,
  principal : SubjectRef,
) -> Array[ObjectRef] {
  let result : Array[ObjectRef] = []
  for object in objects {
    if self.check(object, permission, principal).allowed {
      result.push(object)
    }
  }
  result
}

///|
fn push_unique(items : Array[String], value : String) -> Unit {
  if !string_array_contains(items, value) {
    items.push(value)
  }
}

///|
pub fn PolicyEngine::stats(self : PolicyEngine) -> PolicyStats {
  let object_kinds : Array[String] = []
  let relations : Array[String] = []
  let permissions : Array[String] = []
  for tuple in self.tuples {
    push_unique(object_kinds, tuple.object.kind)
    push_unique(object_kinds, tuple.subject.kind)
    push_unique(relations, tuple.relation)
    if tuple.subject.relation != "" {
      push_unique(relations, tuple.subject.relation)
    }
  }
  for rule in self.rules {
    push_unique(object_kinds, rule.object_namespace)
    push_unique(relations, rule.source_relation)
    push_unique(permissions, rule.permission)
    if rule.target_permission != "" {
      push_unique(permissions, rule.target_permission)
    }
  }
  {
    tuples: self.tuples.length(),
    rules: self.rules.length(),
    object_kinds: object_kinds.length(),
    relations: relations.length(),
    permissions: permissions.length(),
  }
}

///|
pub fn PolicyStats::to_json(self : PolicyStats) -> String {
  "{\"tuples\":\{self.tuples},\"rules\":\{self.rules},\"object_kinds\":\{self.object_kinds},\"relations\":\{self.relations},\"permissions\":\{self.permissions}}"
}

///|
fn rule_exists(
  rules : Array[PolicyRule],
  object_kind : String,
  permission : String,
) -> Bool {
  for rule in rules {
    if rule.object_namespace == object_kind && rule.permission == permission {
      return true
    }
  }
  false
}

///|
fn relation_exists(
  tuples : Array[RelationTuple],
  object_kind : String,
  relation : String,
) -> Bool {
  for tuple in tuples {
    if tuple.object.kind == object_kind && tuple.relation == relation {
      return true
    }
  }
  false
}

///|
pub fn PolicyEngine::validate(self : PolicyEngine) -> Array[ValidationIssue] {
  let issues : Array[ValidationIssue] = []
  for tuple in self.tuples {
    if tuple.object.kind == "" ||
      tuple.object.id == "" ||
      tuple.relation == "" ||
      tuple.subject.kind == "" ||
      tuple.subject.id == "" {
      issues.push({
        code: "empty-tuple-field",
        message: "tuple contains an empty object, relation, or subject field",
      })
    }
  }
  for rule in self.rules {
    if rule.object_namespace == "" ||
      rule.permission == "" ||
      rule.source_relation == "" {
      issues.push({
        code: "empty-rule-field",
        message: "rule contains an empty object kind, permission, or relation",
      })
    }
    if rule.effect != 1 && rule.effect != -1 {
      issues.push({
        code: "invalid-effect",
        message: "rule effect must be allow (1) or deny (-1)",
      })
    }
    if !relation_exists(
        self.tuples,
        rule.object_namespace,
        rule.source_relation,
      ) {
      issues.push({
        code: "unused-relation",
        message: "\{rule.object_namespace}#\{rule.source_relation} has no tuples",
      })
    }
    if rule.target_permission != "" {
      let mut target_found = false
      for tuple in self.tuples {
        if tuple.object.kind == rule.object_namespace &&
          tuple.relation == rule.source_relation &&
          tuple.subject.relation == "" &&
          rule_exists(self.rules, tuple.subject.kind, rule.target_permission) {
          target_found = true
        }
      }
      if !target_found {
        issues.push({
          code: "dangling-traversal",
          message: "\{rule.object_namespace}#\{rule.permission} cannot resolve \{rule.target_permission}",
        })
      }
    }
  }
  issues
}

///|
pub fn PolicyEngine::to_json(self : PolicyEngine) -> String {
  let buf = StringBuilder()
  buf.write_string("{\"max_depth\":")
  buf.write_string(self.max_depth.to_string())
  buf.write_string(",\"tuples\":[")
  for i = 0; i < self.tuples.length(); i = i + 1 {
    if i > 0 {
      buf.write_char(',')
    }
    let tuple = self.tuples[i]
    buf.write_string(
      "{\"object\":\"\{tuple.object.key()}\",\"relation\":\"\{tuple.relation}\",\"subject\":\"\{tuple.subject.key()}\"}",
    )
  }
  buf.write_string("],\"rules\":[")
  for i = 0; i < self.rules.length(); i = i + 1 {
    if i > 0 {
      buf.write_char(',')
    }
    let rule = self.rules[i]
    buf.write_string(
      "{\"object_kind\":\"\{rule.object_namespace}\",\"permission\":\"\{rule.permission}\",\"source_relation\":\"\{rule.source_relation}\",\"target_permission\":\"\{rule.target_permission}\",\"effect\":\{rule.effect}}",
    )
  }
  buf.write_string("]}")
  buf.to_string()
}