(* If you would like, write how many hours you spent on this homework:

  XXX

*)

(** HELPER FUNCTIONS **)

let rec forall gen prop n = 
    if n <= 0 then None else
        let x = gen () in 
        if prop x then forall gen prop (n - 1) else Some x

let string_of_char_list (cs : char list) : string = 
    String.of_seq (List.to_seq cs)

let char_list_of_string (s : string) : char list = 
    List.of_seq (String.to_seq s)


let last (xs : 'a list) : 'a option = 
    if List.is_empty xs then None else Some (List.nth xs (List.length xs - 1))

(* General state machine type *)

type ('s, 'i, 'o) machine = {
    init : 's;
    step : 's -> 'i -> ('s * 'o)
}

(* CSV format types *)

type token = | TokChar of char  (* Any character except `,`, `\n`, and `^` *)
             | TokEscaped of string (* string cannot contain character ^ *)
type value = token list (* Can be arbitrarily long *)
type row = value list (* must have length n, where n is number of columns *)
type csv = row list (* Only used if we are talking about the ENTIRE CSV (not when we make the state machine) *)

(* Helper functions to convert CSV data back to strings *)
let string_of_token (t : token) = 
        match t with 
        | TokChar c -> String.init 1 (fun _ -> c)
        | TokEscaped s -> "^" ^ s ^ "^"
let string_of_value (v : value) = 
    String.concat "" (List.map string_of_token v)
let string_of_row (r : row) = 
    String.concat "," (List.map string_of_value r)


(* Q1 *)
let well_formed_csv (n : int) (c : csv) : bool = 
  failwith "TODO"


(** Q2 **)
type csv_input = char
type csv_output = | Ok | Error | RowFinished of row

type csv_state = unit (* TODO: fill in with your type! *)

let csv_step (s : csv_state) (i : char) : csv_state * csv_output = 
  failwith "TODO"

let csv_machine n = {
  init = ();  (* Fill in with your initial state! *)
  step = csv_step
}

(* Run this to interact with your machine. *)
let run_csv_machine (m : ('s, csv_input, csv_output) machine) : unit = 
  let string_of_output (o : csv_output) = 
      match o with 
      | Ok -> "Ok"
      | Error -> "Error"
      | RowFinished r -> string_of_row r
  in
  let rec go s = 
    let c = 
      print_string "USER INPUT: ";
      try Some (Scanf.scanf "%c" (fun c -> c))
      with End_of_file -> None
    in
    match c with 
    | None -> ()
    | Some c -> 
      let (s', o) = m.step s c in
      print_endline (string_of_output o); 
      go s'
    in
  go m.init


(** Q3 **)
      
(* Helper function to run a state machine on a list of characters. *)
(* To not miss out on any data, we assume here that `cs` must end with a newline. *)
let make_parsed_csv (m : ('s, csv_input, csv_output) machine) (cs : char list) : csv option = 
  let rec go (curr : 's) (cs : char list) : csv option = 
      match cs with 
      | [] -> Some []
      | c :: cs' -> 
          let (next, o) = m.step curr c in 
          match o with 
          | Ok -> go next cs' 
          | Error -> None
          | RowFinished r -> 
              match go next cs' with 
              | None -> None
              | Some c -> Some (r :: c)
  in
  go m.init cs




(* Serializer for CSV. *)
let serialize_csv (c : csv) = 
  let string_of_csv (c : csv) = 
      String.concat "\n" (List.map string_of_row c)
  in
  char_list_of_string (string_of_csv c) @ ['\n']


(* Parsing, then serializing, gets you back to where you started. *)
let parse_serialize_prop (m : ('s, csv_input, csv_output) machine) (cs : char list) : bool = 
    if last cs = Some '\n' then 
        match make_parsed_csv m cs with 
        | None -> true
        | Some parsed -> 
            let cs' = serialize_csv parsed in 
            cs = cs'
    else 
        true

(* Serializing, then parsing, gets you back to where you started. *)
let serialize_parse_prop (m : ('s, csv_input, csv_output) machine) (n : int) (c : csv) =
    if well_formed_csv n c then 
        make_parsed_csv m (serialize_csv c)
        = 
        Some c
  else true

(* Property 1:

forall n >= 2, forall cs : char list, 
    parse_serialize_prop (csv_machine n) cs = true

*)

(* Property 2: 

forall n >= 2, forall c : csv, 
    serialize_parse_prop (csv_machine n) n c = true.

*)


(* TODO:
  1. Design generators for number of columns, `char list` and `csv` to test the validity of the two properties above. 
  2. Test the validity of both properties using your generators.
  3. Write up your results in a report below in a comment, including an argument
  for why the generators you wrote were good choices; and for what kinds of inputs are
  the properties true and false. 

*)