helm/ocaml/cic_notation/cicNotationMatcher.ml

   1 (* Copyright (C) 2004-2005, HELM Team.
   2  *
   3  * This file is part of HELM, an Hypertextual, Electronic
   4  * Library of Mathematics, developed at the Computer Science
   5  * Department, University of Bologna, Italy.
   6  *
   7  * HELM is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation; either version 2
  10  * of the License, or (at your option) any later version.
  11  *
  12  * HELM is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with HELM; if not, write to the Free Software
  19  * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  20  * MA  02111-1307, USA.
  21  *
  22  * For details, see the HELM World-Wide-Web page,
  23  * http://helm.cs.unibo.it/
  24  *)
  25
  26 open Printf
  27
  28 module Ast = CicNotationPt
  29 module Env = CicNotationEnv
  30 module Pp = CicNotationPp
  31 module Util = CicNotationUtil
  32
  33 type pattern_id = int
  34
  35 exception No_match
  36
  37 module OrderedInt =
  38 struct
  39   type t = int
  40   let compare (x1:t) (x2:t) = Pervasives.compare x2 x1  (* reverse order *)
  41 end
  42
  43 module IntSet = Set.Make (OrderedInt)
  44
  45 let int_set_of_int_list l =
  46   List.fold_left (fun acc i -> IntSet.add i acc) IntSet.empty l
  47
  48 type pattern_kind = Variable | Constructor
  49 type tag_t = int
  50
  51 module type PATTERN =
  52 sig
  53   type pattern_t
  54   type term_t
  55   val classify : pattern_t -> pattern_kind
  56   val tag_of_pattern : pattern_t -> tag_t * pattern_t list
  57   val tag_of_term : term_t -> tag_t * term_t list
  58 end
  59
  60 module Matcher (P: PATTERN) =
  61 struct
  62   type row_t = P.pattern_t list * P.pattern_t list * pattern_id
  63   type t = row_t list
  64
  65   let compatible p1 p2 = P.classify p1 = P.classify p2
  66
  67   let matched = List.map (fun (matched, _, pid) -> matched, pid)
  68
  69   let partition t pidl =
  70     let partitions = Hashtbl.create 11 in
  71     let add pid row = Hashtbl.add partitions pid row in
  72     (try
  73       List.iter2 add pidl t
  74     with Invalid_argument _ -> assert false);
  75     let pidset = int_set_of_int_list pidl in
  76     IntSet.fold
  77       (fun pid acc ->
  78         match Hashtbl.find_all partitions pid with
  79         | [] -> acc
  80         | patterns -> (pid, List.rev patterns) :: acc)
  81       pidset []
  82
  83   let are_empty t =
  84     match t with
  85     | (_, [], _) :: _ -> true
  86       (* if first row has an empty list of patterns, then others have as well *)
  87     | _ -> false
  88
  89     (* return 2 lists of rows, first one containing homogeneous rows according
  90      * to "compatible" below *)
  91   let horizontal_split t =
  92     let ap, first_row, t', first_row_class =
  93       match t with
  94       | [] -> assert false
  95       | (_, [], _) :: _ ->
  96           assert false  (* are_empty should have been invoked in advance *)
  97       | ((_, hd :: _ , _) as row) :: tl -> hd, row, tl, P.classify hd
  98     in
  99     let rec aux prev_t = function
 100       | [] -> List.rev prev_t, []
 101       | (_, [], _) :: _ -> assert false
 102       | ((_, hd :: _, _) as row) :: tl when compatible ap hd ->
 103           aux (row :: prev_t) tl
 104       | t -> List.rev prev_t, t
 105     in
 106     let rows1, rows2 = aux [first_row] t' in
 107     first_row_class, rows1, rows2
 108
 109     (* return 2 lists, first one representing first column, second one
 110      * representing a new pattern matrix where matched patterns have been moved
 111      * to decl *)
 112   let vertical_split t =
 113     List.map
 114       (function
 115         | decls, hd :: tl, pid -> hd :: decls, tl, pid
 116         | _ -> assert false)
 117       t
 118
 119   let variable_closure k =
 120     (fun matched_terms terms ->
 121       match terms with
 122       | hd :: tl -> k (hd :: matched_terms) tl
 123       | _ -> assert false)
 124
 125   let success_closure ks k =
 126     (fun matched_terms terms ->
 127        match ks matched_terms with
 128            None ->
 129              begin
 130                (* the match has failed, we rollback the last matched term
 131                 * into the unmatched ones and call the failure continuation
 132                 *)
 133                match matched_terms with
 134                    hd :: tl -> k tl (hd :: terms)
 135                  | _ -> assert false
 136              end
 137          | Some v -> Some v)
 138
 139   let constructor_closure ks k =
 140     (fun matched_terms terms ->
 141       match terms with
 142       | t :: tl ->
 143           (try
 144             let tag, subterms = P.tag_of_term t in
 145             let k' = List.assoc tag ks in
 146             k' matched_terms (subterms @ tl)
 147           with Not_found -> k matched_terms terms)
 148       | [] -> assert false)
 149
 150   let compiler rows match_cb fail_k =
 151     let rec aux t k =
 152       if t = [] then
 153         k
 154       else if are_empty t then
 155         success_closure (match_cb (matched t)) k
 156       else
 157         match horizontal_split t with
 158         | _, [], _ -> assert false
 159         | Variable, t', [] -> variable_closure (aux (vertical_split t') k)
 160         | Constructor, t', [] ->
 161             let tagl =
 162               List.map
 163                 (function
 164                   | _, p :: _, _ -> fst (P.tag_of_pattern p)
 165                   | _ -> assert false)
 166                 t'
 167             in
 168             let clusters = partition t' tagl in
 169             let ks =
 170               List.map
 171                 (fun (tag, cluster) ->
 172                   let cluster' =
 173                     List.map  (* add args as patterns heads *)
 174                       (function
 175                         | matched_p, p :: tl, pid ->
 176                             let _, subpatterns = P.tag_of_pattern p in
 177                             matched_p, subpatterns @ tl, pid
 178                         | _ -> assert false)
 179                       cluster
 180                   in
 181                   tag, aux cluster' k)
 182                 clusters
 183             in
 184             constructor_closure ks k
 185         | _, t', t'' -> aux t' (aux t'' k)
 186     in
 187     let t = List.map (fun (p, pid) -> [], [p], pid) rows in
 188     let matcher = aux t (fun _ _ -> fail_k ()) in
 189     (fun term -> matcher [] [term])
 190 end
 191
 192 module Matcher21 =
 193 struct
 194   module Pattern21 =
 195   struct
 196     type pattern_t = Ast.term
 197     type term_t = Ast.term
 198     let rec classify = function
 199       | Ast.AttributedTerm (_, t) -> classify t
 200       | Ast.Variable _ -> Variable
 201       | Ast.Magic _
 202       | Ast.Layout _
 203       | Ast.Literal _ as t -> assert false
 204       | _ -> Constructor
 205     let tag_of_pattern = CicNotationTag.get_tag
 206     let tag_of_term = CicNotationTag.get_tag
 207   end
 208
 209   module M = Matcher (Pattern21)
 210
 211   let extract_magic term =
 212     let magic_map = ref [] in
 213     let add_magic m =
 214       let name = Util.fresh_name () in
 215       magic_map := (name, m) :: !magic_map;
 216       Ast.Variable (Ast.TermVar name)
 217     in
 218     let rec aux = function
 219       | Ast.AttributedTerm (_, t) -> assert false
 220       | Ast.Literal _
 221       | Ast.Layout _ -> assert false
 222       | Ast.Variable v -> Ast.Variable v
 223       | Ast.Magic m -> add_magic m
 224       | t -> Util.visit_ast aux t
 225     in
 226     let term' = aux term in
 227     term', !magic_map
 228
 229   let env_of_matched pl tl =
 230     List.map2
 231       (fun p t ->
 232         match p, t with
 233           Ast.Variable (Ast.TermVar name), _ ->
 234             name, (Env.TermType, Env.TermValue t)
 235         | Ast.Variable (Ast.NumVar name), (Ast.Num (s, _)) ->
 236             name, (Env.NumType, Env.NumValue s)
 237         | Ast.Variable (Ast.IdentVar name), (Ast.Ident (s, None)) ->
 238             name, (Env.StringType, Env.StringValue s)
 239         | _ -> assert false)
 240       pl tl
 241
 242   let rec compiler rows =
 243     let rows', magic_maps =
 244       List.split
 245         (List.map
 246           (fun (p, pid) ->
 247             let p', map = extract_magic p in
 248             (p', pid), (pid, map))
 249           rows)
 250     in
 251     let magichecker map =
 252       List.fold_left
 253         (fun f (name, m) ->
 254           let m_checker = compile_magic m in
 255           (fun env ->
 256             match m_checker (Env.lookup_term env name) env with
 257             | None -> None
 258             | Some env' ->
 259                 f env'))
 260         (fun env -> Some env)
 261         map
 262     in
 263     let magichooser candidates =
 264       List.fold_left
 265         (fun f (pid, pl, checker) ->
 266           (fun matched_terms ->
 267             let env = env_of_matched pl matched_terms in
 268             match checker env with
 269             | None -> f matched_terms
 270             | Some env ->
 271                 let magic_map =
 272                   try List.assoc pid magic_maps with Not_found -> assert false
 273                 in
 274                 let env' = Env.remove_names env (List.map fst magic_map) in
 275                 Some (env', pid)))
 276         (fun _ -> None)
 277         (List.rev candidates)
 278     in
 279     let match_cb rows =
 280       let candidates =
 281         List.map
 282           (fun (pl, pid) ->
 283             let magic_map =
 284               try List.assoc pid magic_maps with Not_found -> assert false
 285             in
 286             pid, pl, magichecker magic_map)
 287           rows
 288       in
 289         magichooser candidates
 290     in
 291     M.compiler rows' match_cb (fun _ -> None)
 292
 293   and compile_magic = function
 294     | Ast.Fold (kind, p_base, names, p_rec) ->
 295         let p_rec_decls = Env.declarations_of_term p_rec in
 296           (* LUCA: p_rec_decls should not contain "names" *)
 297         let acc_name = try List.hd names with Failure _ -> assert false in
 298         let compiled_base = compiler [p_base, 0]
 299         and compiled_rec = compiler [p_rec, 0] in
 300           (fun term env ->
 301              let aux_base term =
 302                match compiled_base term with
 303                  | None -> None
 304                  | Some (env', _) -> Some (env', [])
 305              in
 306              let rec aux term =
 307                match compiled_rec term with
 308                  | None -> aux_base term
 309                  | Some (env', _) ->
 310                      begin
 311                        let acc = Env.lookup_term env' acc_name in
 312                        let env'' = Env.remove_name env' acc_name in
 313                          match aux acc with
 314                            | None -> aux_base term
 315                            | Some (base_env, rec_envl) ->
 316                                Some (base_env, env'' :: rec_envl)
 317                      end
 318              in
 319                match aux term with
 320                  | None -> None
 321                  | Some (base_env, rec_envl) ->
 322                      Some (base_env @ Env.coalesce_env p_rec_decls rec_envl @ env)) (* @ env LUCA!!! *)
 323
 324     | Ast.Default (p_some, p_none) ->  (* p_none can't bound names *)
 325         let p_some_decls = Env.declarations_of_term p_some in
 326         let none_env = List.map Env.opt_binding_of_name p_some_decls in
 327         let compiled = compiler [p_some, 0] in
 328         (fun term env ->
 329           match compiled term with
 330           | None -> Some none_env (* LUCA: @ env ??? *)
 331           | Some (env', 0) -> Some (List.map Env.opt_binding_some env' @ env)
 332           | _ -> assert false)
 333
 334     | Ast.If (p_test, p_true, p_false) ->
 335         let compiled_test = compiler [p_test, 0]
 336         and compiled_true = compiler [p_true, 0]
 337         and compiled_false = compiler [p_false, 0] in
 338           (fun term env ->
 339              let branch =
 340                match compiled_test term with
 341                  | None -> compiled_false
 342                  | Some _ -> compiled_true
 343              in
 344                match branch term with
 345                  | None -> None
 346                  | Some (env', _) -> Some (env' @ env))
 347
 348     | Ast.Fail -> (fun _ _ -> None)
 349
 350     | _ -> assert false
 351 end
 352
 353 module Matcher32 =
 354 struct
 355   module Pattern32 =
 356   struct
 357     type cic_mask_t =
 358       Blob
 359     | Uri of UriManager.uri
 360     | Appl of cic_mask_t list
 361
 362     let uri_of_term t = CicUtil.uri_of_term (Deannotate.deannotate_term t)
 363
 364     let mask_of_cic = function
 365       | Cic.AAppl (_, tl) -> Appl (List.map (fun _ -> Blob) tl), tl
 366       | Cic.AConst (_, _, [])
 367       | Cic.AVar (_, _, [])
 368       | Cic.AMutInd (_, _, _, [])
 369       | Cic.AMutConstruct (_, _, _, _, []) as t -> Uri (uri_of_term t), []
 370       | _ -> Blob, []
 371
 372     let tag_of_term t =
 373       let mask, tl = mask_of_cic t in
 374       Hashtbl.hash mask, tl
 375
 376     let mask_of_appl_pattern = function
 377       | Ast.UriPattern uri -> Uri uri, []
 378       | Ast.ImplicitPattern
 379       | Ast.VarPattern _ -> Blob, []
 380       | Ast.ApplPattern pl -> Appl (List.map (fun _ -> Blob) pl), pl
 381
 382     let tag_of_pattern p =
 383       let mask, pl = mask_of_appl_pattern p in
 384       Hashtbl.hash mask, pl
 385
 386     type pattern_t = Ast.cic_appl_pattern
 387     type term_t = Cic.annterm
 388
 389     let classify = function
 390       | Ast.ImplicitPattern
 391       | Ast.VarPattern _ -> Variable
 392       | Ast.UriPattern _
 393       | Ast.ApplPattern _ -> Constructor
 394   end
 395
 396   module M = Matcher (Pattern32)
 397
 398   let compiler rows =
 399     let match_cb rows =
 400       let pl, pid = try List.hd rows with Not_found -> assert false in
 401       (fun matched_terms ->
 402         let env =
 403           List.map2
 404             (fun p t ->
 405               match p with
 406               | Ast.ImplicitPattern -> Util.fresh_name (), t
 407               | Ast.VarPattern name -> name, t
 408               | _ -> assert false)
 409             pl matched_terms
 410         in
 411         Some (env, pid))
 412     in
 413     M.compiler rows match_cb (fun () -> None)
 414 end
 415