(* Copyright (C) 2004-2005, HELM Team.
 * 
 * This file is part of HELM, an Hypertextual, Electronic
 * Library of Mathematics, developed at the Computer Science
 * Department, University of Bologna, Italy.
 * 
 * HELM is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * HELM is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HELM; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA  02111-1307, USA.
 * 
 * For details, see the HELM World-Wide-Web page,
 * http://helm.cs.unibo.it/
 *)

open Printf

module Pt = CicNotationPt
module Env = CicNotationEnv
module Util = CicNotationUtil

type pattern_id = int

exception No_match

module OrderedInt =
  struct
  type t = int
  let compare (x1:t) (x2:t) = Pervasives.compare x2 x1  (* reverse order *)
  end

module IntSet = Set.Make (OrderedInt)

let int_set_of_int_list l =
  List.fold_left (fun acc i -> IntSet.add i acc) IntSet.empty l

module type PATTERN =
  sig
  type pattern_t
  val compatible : pattern_t -> pattern_t -> bool
  end

module Patterns (P: PATTERN) =
  struct
  type row_t = P.pattern_t list * P.pattern_t list * pattern_id
  type t = row_t list

  let empty = []

  let matched = List.map (fun (matched, _, pid) -> matched, pid)

  let partition t pidl =
    let partitions = Hashtbl.create 11 in
    let add pid row = Hashtbl.add partitions pid row in
    (try
      List.iter2 add pidl t
    with Invalid_argument _ -> assert false);
    let pidset = int_set_of_int_list pidl in
    IntSet.fold
      (fun pid acc ->
        match Hashtbl.find_all partitions pid with
        | [] -> acc
        | patterns -> (pid, List.rev patterns) :: acc)
      pidset []

  let are_empty t =
    match t with
    | (_, [], _) :: _ -> true
      (* if first row has an empty list of patterns, then others have as well *)
    | _ -> false

    (* return 2 lists of rows, first one containing homogeneous rows according
     * to "compatible" below *)
  let horizontal_split t =
    let ap, first_row, t' =
      match t with
      | [] -> assert false
      | (_, [], _) :: _ ->
          assert false  (* are_empty should have been invoked in advance *)
      | ((_, hd :: _ , _) as row) :: tl -> hd, row, tl
    in
    let rec aux prev_t = function
      | [] -> List.rev prev_t, []
      | (_, [], _) :: _ -> assert false
      | ((_, hd :: _, _) as row) :: tl when P.compatible ap hd ->
          aux (row :: prev_t) tl
      | t -> List.rev prev_t, t
    in
    aux [first_row] t'

    (* return 2 lists, first one representing first column, second one
     * representing a new pattern matrix where matched patterns have been moved
     * to decl *)
  let vertical_split t =
    List.map
      (function
        | decls, hd :: tl, pid -> hd :: decls, tl, pid
        | _ -> assert false)
      t
  end

module T21 =
struct

module P = Patterns (CicNotationTag)

(* let return_closure matched =
  (fun matched_terms terms ->
    prerr_endline "T21.return_closure";
    match terms with
    | [] -> matched_terms, matched
    | _ -> assert false) *)

let variable_closure k =
  (fun matched_terms terms ->
    prerr_endline "T21.variable_closure";
    match terms with
    | hd :: tl ->
        prerr_endline (sprintf "binding: %s" (CicNotationPp.pp_term hd));
        k (hd :: matched_terms) tl
    | _ -> assert false)

let constructor_closure ks k =
  (fun matched_terms terms ->
    prerr_endline "T21.constructor_closure";
    match terms with
    | t :: tl ->
        prerr_endline (sprintf "on term %s" (CicNotationPp.pp_term t));
        (try
          let tag, subterms = CicNotationTag.get_tag t in
          let k' = List.assoc tag ks in
          k' matched_terms (subterms @ tl)
        with Not_found -> k matched_terms terms)
    | [] -> assert false)

(* let fold_closure kind p_names names matcher success_k k =
  let acc_name = try List.hd names with Failure _ -> assert false in
|+   List.iter (fun (name, _) -> Printf.printf "/// %s\n" name) p_names ; +|
  (fun matched_terms terms ->
    prerr_endline "T21.fold_closure";
    (match terms with
    | t :: tl ->
        let rec aux t =
          prerr_endline "PORCA TORCIA SONO IN AUX" ;
          match matcher t with
          | _, [] -> None
          | matched_terms, [matched_p, 0] -> Some (matched_terms, [])
          | matched_terms, [matched_p, 1] ->
              let acc = CicNotationEnv.lookup_term env acc_name in
              let env = CicNotationEnv.remove env acc_name in
              (match aux acc with
              | None -> None
              | Some env' -> Some (env :: env'))
          | envl ->
              List.iter
                (fun (env, pid) ->
                   Printf.printf "*** %s %d\n" (CicNotationPp.pp_env env) pid)
                envl ;
              flush stdout ;
              assert false |+ overlapping patterns, to be handled ... +|
        in
        (match aux t with
        | None -> k terms envl
        | Some env ->
            let magic_env = CicNotationEnv.coalesce_env p_names env in
            List.map (fun (env, pid) -> magic_env @ env, pid) envl)
    | [] -> assert false)) *)

let compiler0 rows match_cb fail_k =
  let rec aux t k =
    if t = [] then
      k
    else if P.are_empty t then
      match_cb (P.matched t)
    else
      match P.horizontal_split t with
      | t', [] ->
          (match t' with
          | []
          | (_, [], _) :: _ -> assert false
          | (_, Pt.Variable _ :: _, _) :: _ ->
              variable_closure (aux (P.vertical_split t') k)
          | _ ->
              let tagl =
                List.map
                  (function
                    | _, p :: _, _ -> fst (CicNotationTag.get_tag p)
                    | _ -> assert false)
                  t'
              in
              let clusters = P.partition t' tagl in
              let ks =
                List.map
                  (fun (tag, cluster) ->
                    let cluster' =
                      List.map  (* add args as patterns heads *)
                        (function
                          | matched_p, p :: tl, pid ->
                              let _, subpatterns = CicNotationTag.get_tag p in
                              matched_p, subpatterns @ tl, pid
                          | _ -> assert false)
                        cluster
                    in
                    tag, aux cluster' k)
                  clusters
              in
              constructor_closure ks k)
      | t', tl -> aux t' (aux tl k)
  in
  let t = List.map (fun (p, pid) -> [], [p], pid) rows in
  let matcher = aux t (fun _ _ -> fail_k ()) in
  (fun term -> matcher [] [term])

let extract_magic term =
  let magic_map = ref [] in
  let add_magic m =
    let name = Util.fresh_name () in
    magic_map := (name, m) :: !magic_map;
    Pt.Variable (Pt.TermVar name)
  in
  let rec aux = function
    | Pt.AttributedTerm (_, t) -> aux t
    | Pt.Literal _
    | Pt.Layout _ -> assert false
    | Pt.Variable v -> Pt.Variable v
    | Pt.Magic m -> add_magic m
    | t -> Util.visit_ast aux t
  in
  let term' = aux term in
  term', !magic_map

let env_of_matched pl tl =
  List.map2
    (fun p t ->
      match p, t with
        Pt.Variable (Pt.TermVar name), _ ->
          name, (Env.TermType, Env.TermValue t)
      | Pt.Variable (Pt.NumVar name), (Pt.Num (s, _)) ->
          name, (Env.NumType, Env.NumValue s)
      | Pt.Variable (Pt.IdentVar name), (Pt.Ident (s, None)) ->
          name, (Env.StringType, Env.StringValue s)
      | _ -> assert false)
    pl tl

let decls_of_pattern p = 
  List.map Env.declaration_of_var (Util.variables_of_term p)

let rec compiler rows =
  let rows', magic_maps =
    List.split
      (List.map
        (fun (p, pid) ->
          let p', map = extract_magic p in
          (p', pid), (pid, map))
        rows)
  in
  let magichecker map =
    List.fold_left
      (fun f (name, m) ->
        let m_checker = compile_magic m in
        (fun env ->
          match m_checker (Env.lookup_term env name) env with
          | None -> None
          | Some env' -> f env'))
      (fun env -> Some env)
      map
  in
  let magichooser candidates =
    List.fold_left
      (fun f (pid, pl, checker) ->
        (fun matched_terms ->
          let env = env_of_matched pl matched_terms in
          match checker env with
          | None -> f matched_terms
          | Some env -> Some (env, pid)))
      (fun _ -> None)
      candidates
  in
  let match_cb rows =
    prerr_endline (sprintf "match_cb on %d row(s)" (List.length rows));
    let candidates =
      List.map
        (fun (pl, pid) ->
          let magic_map =
            try List.assoc pid magic_maps with Not_found -> assert false
          in
          pid, pl, magichecker magic_map)
        rows
    in
    (fun matched_terms _ -> magichooser candidates matched_terms)
  in
  compiler0 rows match_cb (fun _ -> None)

and compile_magic = function
  | Pt.Fold (kind, p_base, names, p_rec) ->
      let p_rec_decls = decls_of_pattern p_rec in
      let acc_name = try List.hd names with Failure _ -> assert false in
      let t_magic = [p_base, 0; p_rec, 1] in
      let compiled = compiler t_magic in
      (fun term env ->
        let rec aux term =
          match compiled term with
          | None -> None
          | Some (env', 0) -> Some (env', [])
          | Some (env', 1) ->
              begin
                let acc = Env.lookup_term env' acc_name in
                let env'' = Env.remove env' acc_name in
                match aux acc with
                | None -> None
                | Some (base_env, rec_envl) -> 
                    Some (base_env, env'' :: rec_envl )
              end
          | _ -> assert false
        in
          match aux term with
          | None -> None
          | Some (base_env, rec_envl) ->
              Some (base_env @ Env.coalesce_env p_rec_decls rec_envl))
  | _ -> assert false

end