///|
/// Parse an RFC 4515 filter string into a structured `LdapFilter`.
pub fn parse_filter(s : String) -> Result[LdapFilter, LdapError] {
  result_of_ldap(fn() raise LdapError {
    let p = FilterParser::new(s)
    let f = p.parse_filter()
    if p.pos != p.data.length() {
      raise invalid_filter("unexpected trailing characters at offset \{p.pos}")
    }
    f
  })
}

///|
/// Unescape an RFC 4515 assertion value: `\XX` becomes the byte `XX`.
pub fn unescape_filter_value(s : String) -> Result[Bytes, LdapError] {
  result_of_ldap(fn() raise LdapError {
    let p = FilterParser::new(s)
    let out : Array[Byte] = []
    while true {
      match p.peek_byte() {
        None => break
        Some(_) =>
          for b in p.read_value_byte() {
            out.push(b)
          }
      }
    }
    Bytes::from_array(out)
  })
}

///|
/// Escape a raw assertion value for inclusion in a filter string. Escapes
/// `*`, `(`, `)`, `\` and NUL using the `\XX` form. Runs of non-special
/// bytes are decoded as UTF-8 so multi-byte characters survive the round
/// trip.
pub fn escape_filter_value(value : Bytes) -> String {
  let sb = StringBuilder()
  let run : Array[Byte] = []
  for b in value {
    let v = b.to_int()
    if v == 0x2A || v == 0x28 || v == 0x29 || v == 0x5C || v == 0x00 {
      if !run.is_empty() {
        sb.write_string(@utf8.decode_lossy(Bytes::from_array(run)[:]))
        run.clear()
      }
      sb.write_char('\\')
      sb.write_string(to_hex_upper(Bytes::from_array([b])))
    } else {
      run.push(b)
    }
  }
  if !run.is_empty() {
    sb.write_string(@utf8.decode_lossy(Bytes::from_array(run)[:]))
  }
  sb.to_string()
}

///|
priv struct FilterParser {
  data : Bytes
  mut pos : Int
}

///|
fn FilterParser::new(s : String) -> FilterParser {
  { data: @utf8.encode(s), pos: 0 }
}

///|
fn invalid_filter(msg : String) -> LdapError {
  LdapError::InvalidFilter(msg)
}

///|
fn FilterParser::peek_byte(self : FilterParser) -> Int? {
  if self.pos >= self.data.length() {
    return None
  }
  Some(self.data.get(self.pos).unwrap().to_int())
}

///|
fn FilterParser::peek_next(self : FilterParser) -> Int? {
  if self.pos + 1 >= self.data.length() {
    return None
  }
  Some(self.data.get(self.pos + 1).unwrap().to_int())
}

///|
fn FilterParser::advance(self : FilterParser) -> Unit {
  self.pos = self.pos + 1
}

///|
fn FilterParser::expect(self : FilterParser, ch : Int) -> Unit raise LdapError {
  if self.peek_byte() != Some(ch) {
    raise invalid_filter(
      "expected '\{ch.unsafe_to_char()}' at offset \{self.pos}",
    )
  }
  self.advance()
}

///|
fn FilterParser::parse_filter(
  self : FilterParser,
) -> LdapFilter raise LdapError {
  self.expect('('.to_int())
  let f = self.parse_filtercomp()
  self.expect(')'.to_int())
  f
}

///|
fn FilterParser::parse_filtercomp(
  self : FilterParser,
) -> LdapFilter raise LdapError {
  match self.peek_byte() {
    Some(c) if c == '&'.to_int() => {
      self.advance()
      And(self.parse_filterlist())
    }
    Some(c) if c == '|'.to_int() => {
      self.advance()
      Or(self.parse_filterlist())
    }
    Some(c) if c == '!'.to_int() => {
      self.advance()
      Not(self.parse_filter())
    }
    _ => self.parse_item()
  }
}

///|
fn FilterParser::parse_filterlist(
  self : FilterParser,
) -> Array[LdapFilter] raise LdapError {
  let out : Array[LdapFilter] = []
  while self.peek_byte() == Some('('.to_int()) {
    out.push(self.parse_filter())
  }
  if out.is_empty() {
    raise invalid_filter("expected at least one sub-filter")
  }
  out
}

///|
fn FilterParser::parse_item(self : FilterParser) -> LdapFilter raise LdapError {
  let attr = self.read_attr_name()
  match self.peek_byte() {
    Some(c) if c == ':'.to_int() => self.parse_extensible(attr)
    Some(c) if c == '='.to_int() => {
      self.advance()
      self.parse_equal(attr)
    }
    Some(c) if c == '>'.to_int() => {
      self.advance()
      self.expect('='.to_int())
      let value = self.read_simple_value()
      GreaterOrEqual(attr, value)
    }
    Some(c) if c == '<'.to_int() => {
      self.advance()
      self.expect('='.to_int())
      let value = self.read_simple_value()
      LessOrEqual(attr, value)
    }
    Some(c) if c == '~'.to_int() => {
      self.advance()
      self.expect('='.to_int())
      let value = self.read_simple_value()
      Approx(attr, value)
    }
    _ => raise invalid_filter("expected an operator after '\{attr}'")
  }
}

///|
fn FilterParser::read_attr_name(self : FilterParser) -> String {
  let sb = StringBuilder()
  while true {
    match self.peek_byte() {
      Some(c) if is_attr_char(c) => {
        sb.write_char(c.unsafe_to_char())
        self.advance()
      }
      _ => break
    }
  }
  sb.to_string()
}

///|
fn is_attr_char(c : Int) -> Bool {
  if c >= 'a'.to_int() && c <= 'z'.to_int() {
    return true
  }
  if c >= 'A'.to_int() && c <= 'Z'.to_int() {
    return true
  }
  if c >= '0'.to_int() && c <= '9'.to_int() {
    return true
  }
  c == '-'.to_int() || c == '.'.to_int() || c == '_'.to_int()
}

///|
fn FilterParser::parse_equal(
  self : FilterParser,
  attr : String,
) -> LdapFilter raise LdapError {
  // Scan the value, splitting on unescaped `*`.
  let segs : Array[Bytes] = []
  let cur : Array[Byte] = []
  let mut has_star = false
  while true {
    match self.peek_byte() {
      Some(c) if c == ')'.to_int() => break
      None => break
      Some(c) if c == '*'.to_int() => {
        has_star = true
        segs.push(Bytes::from_array(cur))
        cur.clear()
        self.advance()
      }
      Some(_) => {
        let b = self.read_value_byte()
        cur.push(b[0])
      }
    }
  }
  segs.push(Bytes::from_array(cur))
  if !has_star {
    return Equality(attr, segs[0])
  }
  if segs.length() == 2 && segs[0].is_empty() && segs[1].is_empty() {
    return Present(attr)
  }
  let initial = if segs[0].is_empty() { None } else { Some(segs[0]) }
  let any : Array[Bytes] = []
  for i in 1..<(segs.length() - 1) {
    if !segs[i].is_empty() {
      any.push(segs[i])
    }
  }
  let final_ = if segs.length() > 1 && !segs[segs.length() - 1].is_empty() {
    Some(segs[segs.length() - 1])
  } else {
    None
  }
  Substrings(attr, SubstringFilter::new(initial, any, final_))
}

///|
fn FilterParser::read_simple_value(
  self : FilterParser,
) -> Bytes raise LdapError {
  let out : Array[Byte] = []
  while true {
    match self.peek_byte() {
      Some(c) if c == ')'.to_int() => break
      Some(c) if c == '*'.to_int() =>
        raise invalid_filter("unescaped '*' is not allowed in this value")
      None => break
      Some(_) => {
        let b = self.read_value_byte()
        out.push(b[0])
      }
    }
  }
  Bytes::from_array(out)
}

///|
fn FilterParser::read_value_byte(
  self : FilterParser,
) -> Array[Byte] raise LdapError {
  match self.peek_byte() {
    Some(c) if c == '\\'.to_int() => {
      self.advance()
      let h1 = self.peek_byte()
      self.advance()
      let h2 = self.peek_byte()
      self.advance()
      match (h1, h2) {
        (Some(a), Some(b)) => {
          let hi = hex_nibble(a)
          let lo = hex_nibble(b)
          if hi < 0 || lo < 0 {
            raise invalid_filter(
              "invalid escape sequence at offset \{self.pos}",
            )
          }
          [((hi << 4) | lo).to_byte()]
        }
        _ => raise invalid_filter("truncated escape sequence")
      }
    }
    Some(c) => {
      self.advance()
      [c.to_byte()]
    }
    None => raise invalid_filter("unexpected end of input")
  }
}

///|
fn hex_nibble(c : Int) -> Int {
  if c >= '0'.to_int() && c <= '9'.to_int() {
    return c - '0'.to_int()
  }
  if c >= 'a'.to_int() && c <= 'f'.to_int() {
    return c - 'a'.to_int() + 10
  }
  if c >= 'A'.to_int() && c <= 'F'.to_int() {
    return c - 'A'.to_int() + 10
  }
  -1
}

///|
fn FilterParser::parse_extensible(
  self : FilterParser,
  attr : String,
) -> LdapFilter raise LdapError {
  self.expect(':'.to_int())
  let mut dn_attrs = false
  if self.peek_byte() == Some('d'.to_int()) &&
    self.peek_next() == Some('n'.to_int()) {
    // ":dn:" prefix
    self.advance()
    self.advance()
    self.expect(':'.to_int())
    dn_attrs = true
  }
  let rule = StringBuilder()
  let mut ended_with_colon = false
  while true {
    match self.peek_byte() {
      Some(c) if c == ':'.to_int() => {
        ended_with_colon = true
        break
      }
      Some(c) if c == '='.to_int() => break
      None => raise invalid_filter("unterminated extensible match")
      Some(c) => {
        rule.write_char(c.unsafe_to_char())
        self.advance()
      }
    }
  }
  if ended_with_colon {
    self.advance()
    self.expect('='.to_int())
  } else {
    self.expect('='.to_int())
  }
  let value = self.read_simple_value()
  let rule_str = rule.to_string()
  Extensible(
    ExtensibleMatch::new(
      if rule_str.is_empty() {
        None
      } else {
        Some(rule_str)
      },
      if attr.is_empty() {
        None
      } else {
        Some(attr)
      },
      value,
      dn_attrs,
    ),
  )
}

///|
/// Render a filter back to an RFC 4515 string (lossless round trip).
pub fn LdapFilter::to_string(self : LdapFilter) -> String {
  match self {
    And(items) => {
      let sb = StringBuilder()
      sb.write_string("(&")
      for item in items {
        sb.write_string(item.to_string())
      }
      sb.write_string(")")
      sb.to_string()
    }
    Or(items) => {
      let sb = StringBuilder()
      sb.write_string("(|")
      for item in items {
        sb.write_string(item.to_string())
      }
      sb.write_string(")")
      sb.to_string()
    }
    Not(inner) => "(!\{inner.to_string()})"
    Equality(attr, value) => "(\{attr}=\{escape_filter_value(value)})"
    Substrings(attr, sf) => "(\{attr}=\{substring_to_string(sf)})"
    GreaterOrEqual(attr, value) => "(\{attr}>=\{escape_filter_value(value)})"
    LessOrEqual(attr, value) => "(\{attr}<=\{escape_filter_value(value)})"
    Present(attr) => "(\{attr}=*)"
    Approx(attr, value) => "(\{attr}~=\{escape_filter_value(value)})"
    Extensible(em) => "(\{extensible_to_string(em)})"
  }
}

///|
fn substring_to_string(sf : SubstringFilter) -> String {
  let sb = StringBuilder()
  match sf.initial {
    Some(i) => sb.write_string(escape_filter_value(i))
    None => ()
  }
  if sf.any.is_empty() {
    match sf.final_ {
      Some(f) => {
        sb.write_char('*')
        sb.write_string(escape_filter_value(f))
      }
      None => sb.write_char('*')
    }
  } else {
    for seg in sf.any {
      sb.write_char('*')
      sb.write_string(escape_filter_value(seg))
    }
    match sf.final_ {
      Some(f) => {
        sb.write_char('*')
        sb.write_string(escape_filter_value(f))
      }
      None => sb.write_char('*')
    }
  }
  sb.to_string()
}

///|
fn extensible_to_string(em : ExtensibleMatch) -> String {
  let sb = StringBuilder()
  match em.attr_type {
    Some(t) => sb.write_string(t)
    None => ()
  }
  if em.dn_attributes {
    sb.write_string(":dn")
  }
  match em.matching_rule {
    Some(r) => {
      sb.write_char(':')
      sb.write_string(r)
    }
    None => ()
  }
  sb.write_string(":=")
  sb.write_string(escape_filter_value(em.match_value))
  sb.to_string()
}