components/cic/path_indexing.ml

   1 (* Copyright (C) 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://cs.unibo.it/helm/.
  24  *)
  25
  26 (* $Id$ *)
  27
  28 (* path indexing implementation *)
  29
  30 (* position of the subterm, subterm (Appl are not stored...) *)
  31
  32 module PathIndexing =
  33   functor(A:Set.S) ->
  34     struct
  35
  36 type path_string_elem = Index of int | Term of Cic.term;;
  37 type path_string = path_string_elem list;;
  38
  39
  40 let rec path_strings_of_term index =
  41   let module C = Cic in function
  42   | C.Meta _ -> [ [Index index; Term (C.Implicit None)] ]
  43   | C.Appl (hd::tl) ->
  44       let p = if index > 0 then [Index index; Term hd] else [Term hd] in
  45       let _, res =
  46         List.fold_left
  47           (fun (i, r) t ->
  48              let rr = path_strings_of_term i t in
  49              (i+1, r @ (List.map (fun ps -> p @ ps) rr)))
  50           (1, []) tl
  51       in
  52       res
  53   | term -> [ [Index index; Term term] ]
  54 ;;
  55
  56 (*
  57 let string_of_path_string ps =
  58   String.concat "."
  59     (List.map
  60        (fun e ->
  61           let s =
  62             match e with
  63             | Index i -> "Index " ^ (string_of_int i)
  64             | Term t -> "Term " ^ (CicPp.ppterm t)
  65           in
  66           "(" ^ s ^ ")")
  67        ps)
  68 ;;
  69 *)
  70
  71 module OrderedPathStringElement = struct
  72   type t = path_string_elem
  73
  74   let compare t1 t2 =
  75     match t1, t2 with
  76     | Index i, Index j -> Pervasives.compare i j
  77     | Term t1, Term t2 -> if t1 = t2 then 0 else Pervasives.compare t1 t2
  78     | Index _, Term _ -> -1
  79     | Term _, Index _ -> 1
  80 end
  81
  82 module PSMap = Map.Make(OrderedPathStringElement);;
  83
  84 module PSTrie = Trie.Make(PSMap);;
  85
  86 type t = A.t PSTrie.t
  87 type key = Cic.term
  88 let empty = PSTrie.empty
  89 let arities = Hashtbl.create 0
  90
  91 let index trie term info =
  92   let ps = path_strings_of_term 0 term in
  93   List.fold_left
  94   (fun trie ps ->
  95      let ps_set = try PSTrie.find ps trie with Not_found -> A.empty in
  96      let trie = PSTrie.add ps (A.add info ps_set) trie in
  97        trie) trie ps
  98
  99 let remove_index trie term info=
 100   let ps = path_strings_of_term 0 term in
 101   List.fold_left
 102     (fun trie ps ->
 103        try
 104         let ps_set = A.remove info (PSTrie.find ps trie) in
 105         if A.is_empty ps_set then
 106           PSTrie.remove ps trie
 107         else
 108           PSTrie.add ps ps_set trie
 109        with Not_found -> trie) trie ps
 110 ;;
 111
 112 let in_index trie term test =
 113   let ps = path_strings_of_term 0 term in
 114   let ok ps =
 115     try
 116       let set = PSTrie.find ps trie in
 117         A.exists test set
 118     with Not_found ->
 119       false
 120   in
 121   List.exists ok ps
 122 ;;
 123
 124
 125 let head_of_term = function
 126   | Cic.Appl (hd::tl) -> hd
 127   | term -> term
 128 ;;
 129
 130
 131 let subterm_at_pos index term =
 132   if index = 0 then
 133     term
 134   else
 135     match term with
 136     | Cic.Appl l ->
 137         (try List.nth l index with Failure _ -> raise Not_found)
 138     | _ -> raise Not_found
 139 ;;
 140
 141
 142 let rec retrieve_generalizations trie term =
 143   match trie with
 144   | PSTrie.Node (value, map) ->
 145       let res =
 146         match term with
 147         | Cic.Meta _ -> A.empty
 148         | term ->
 149             let hd_term = head_of_term term in
 150             try
 151               let n = PSMap.find (Term hd_term) map in
 152               match n with
 153               | PSTrie.Node (Some s, _) -> s
 154               | PSTrie.Node (None, m) ->
 155                   let l =
 156                     PSMap.fold
 157                       (fun k v res ->
 158                          match k with
 159                          | Index i ->
 160                              let t = subterm_at_pos i term in
 161                              let s = retrieve_generalizations v t in
 162                              s::res
 163                          | _ -> res)
 164                       m []
 165                   in
 166                   match l with
 167                   | hd::tl ->
 168                       List.fold_left (fun r s -> A.inter r s) hd tl
 169                   | _ -> A.empty
 170             with Not_found ->
 171               A.empty
 172       in
 173       try
 174         let n = PSMap.find (Term (Cic.Implicit None)) map in
 175         match n with
 176         | PSTrie.Node (Some s, _) -> A.union res s
 177         | _ -> res
 178       with Not_found ->
 179         res
 180 ;;
 181
 182
 183 let rec retrieve_unifiables trie term =
 184   match trie with
 185   | PSTrie.Node (value, map) ->
 186       let res =
 187         match term with
 188         | Cic.Meta _ ->
 189             PSTrie.fold
 190               (fun ps v res -> A.union res v)
 191               (PSTrie.Node (None, map))
 192               A.empty
 193         | _ ->
 194             let hd_term = head_of_term term in
 195             try
 196               let n = PSMap.find (Term hd_term) map in
 197               match n with
 198               | PSTrie.Node (Some v, _) -> v
 199               | PSTrie.Node (None, m) ->
 200                   let l =
 201                     PSMap.fold
 202                       (fun k v res ->
 203                          match k with
 204                          | Index i ->
 205                              let t = subterm_at_pos i term in
 206                              let s = retrieve_unifiables v t in
 207                              s::res
 208                          | _ -> res)
 209                       m []
 210                   in
 211                   match l with
 212                   | hd::tl ->
 213                       List.fold_left (fun r s -> A.inter r s) hd tl
 214                   | _ -> A.empty
 215             with Not_found ->
 216               A.empty
 217       in
 218       try
 219         let n = PSMap.find (Term (Cic.Implicit None)) map in
 220         match n with
 221         | PSTrie.Node (Some s, _) -> A.union res s
 222         | _ -> res
 223       with Not_found ->
 224         res
 225 ;;
 226
 227 end