(* Pidgin PEG parser based on caronte.py, based on Darius Bacon's min_parson.py *)

let startswith needle haystack =        (* XXX keep both halves *)
  let nl = String.length needle and hl = String.length haystack in
  if nl <= hl then needle = String.sub haystack 0 nl else false
let lit t s =                       (* XXX redefine in terms of get *)
  if startswith t s then
    let tl = String.length t in Some ([], String.sub s tl (String.length s - tl))
  else None
and get t s =
  if startswith t s then
    let tl = String.length t in
    Some ([String.sub s 0 tl], String.sub s tl (String.length s - tl))
  else None
and seq p q s =
  match p s with
    None -> None
  | Some (pr, ps) -> 
      match q ps with
        Some (qr, qs) -> Some ((List.append pr qr), qs)
      | None -> None
and alt p q s = match p s with Some item -> Some item | None -> q s
and rep element =
  let rec f results s =
    match element s with
      None -> Some (results, s)
    | Some (er, es) -> f (List.append results er) es in
  f [] ;;