X-Git-Url: http://matita.cs.unibo.it/gitweb/?a=blobdiff_plain;f=helm%2Focaml%2Fcic_notation%2FcicNotationMatcher.ml;fp=helm%2Focaml%2Fcic_notation%2FcicNotationMatcher.ml;h=8da7a483d6d4d123cfa71d8307f1926a63ce3af4;hb=50377dde5b5b1a8e5c7b2fb48b47defde9508b50;hp=0000000000000000000000000000000000000000;hpb=1b21075e987872a2e3103203b4e67c939e4a9f6a;p=helm.git

diff --git a/helm/ocaml/cic_notation/cicNotationMatcher.ml b/helm/ocaml/cic_notation/cicNotationMatcher.ml
new file mode 100644
index 000000000..8da7a483d
--- /dev/null
+++ b/helm/ocaml/cic_notation/cicNotationMatcher.ml
@@ -0,0 +1,333 @@
+(* 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
+