helm/gTopLevel/disambiguate.ml

   1 (* Copyright (C) 2000-2002, 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 (******************************************************************************)
  27 (*                                                                            *)
  28 (*                               PROJECT HELM                                 *)
  29 (*                                                                            *)
  30 (*                Claudio Sacerdoti Coen <sacerdot@cs.unibo.it>               *)
  31 (*                                 06/01/2002                                 *)
  32 (*                                                                            *)
  33 (*                                                                            *)
  34 (******************************************************************************)
  35
  36 (** Functions that should be moved in another module **)
  37
  38 exception IllFormedUri of string;;
  39
  40 let string_of_cic_textual_parser_uri uri =
  41  let module C = Cic in
  42  let module CTP = CicTextualParser0 in
  43   let uri' =
  44    match uri with
  45       CTP.ConUri uri -> UriManager.string_of_uri uri
  46     | CTP.VarUri uri -> UriManager.string_of_uri uri
  47     | CTP.IndTyUri (uri,tyno) ->
  48        UriManager.string_of_uri uri ^ "#1/" ^ string_of_int (tyno + 1)
  49     | CTP.IndConUri (uri,tyno,consno) ->
  50        UriManager.string_of_uri uri ^ "#1/" ^ string_of_int (tyno + 1) ^ "/" ^
  51         string_of_int consno
  52   in
  53    (* 4 = String.length "cic:" *)
  54    String.sub uri' 4 (String.length uri' - 4)
  55 ;;
  56
  57 let cic_textual_parser_uri_of_string uri' =
  58  prerr_endline ("cic_textual_parser_uri_of_string INPUT = " ^ uri');
  59  try
  60   (* Constant *)
  61   if String.sub uri' (String.length uri' - 4) 4 = ".con" then
  62    CicTextualParser0.ConUri (UriManager.uri_of_string uri')
  63   else
  64    if String.sub uri' (String.length uri' - 4) 4 = ".var" then
  65     CicTextualParser0.VarUri (UriManager.uri_of_string uri')
  66    else
  67     (try
  68       (* Inductive Type *)
  69       let uri'',typeno = CicTextualLexer.indtyuri_of_uri uri' in
  70        CicTextualParser0.IndTyUri (uri'',typeno)
  71      with
  72       _ ->
  73        (* Constructor of an Inductive Type *)
  74        let uri'',typeno,consno =
  75         CicTextualLexer.indconuri_of_uri uri'
  76        in
  77         CicTextualParser0.IndConUri (uri'',typeno,consno)
  78     )
  79  with
  80   _ -> raise (IllFormedUri uri')
  81 ;;
  82 let cic_textual_parser_uri_of_string uri' =
  83   let res = cic_textual_parser_uri_of_string uri' in
  84   prerr_endline ("RESULT: " ^ (string_of_cic_textual_parser_uri res));
  85   res
  86
  87 (* CSC: quick fix: a function from [uri#xpointer(path)] to [uri#path] *)
  88 let wrong_xpointer_format_from_wrong_xpointer_format' uri =
  89  try
  90   let index_sharp =  String.index uri '#' in
  91   let index_rest = index_sharp + 10 in
  92    let baseuri = String.sub uri 0 index_sharp in
  93    let rest =
  94     String.sub uri index_rest (String.length uri - index_rest - 1)
  95    in
  96     baseuri ^ "#" ^ rest
  97  with Not_found -> uri
  98 ;;
  99
 100 (* CSC: IMPERATIVE AND NOT VERY CLEAN, TO GET THE LAST ISSUED QUERY *)
 101 let get_last_query =
 102  let query = ref "" in
 103   MQueryGenerator.set_confirm_query
 104    (function q -> query := MQueryUtil.text_of_query q ; true) ;
 105   function result ->
 106    !query ^ " <h1>Result:</h1> " ^ MQueryUtil.text_of_result result "<br>"
 107 ;;
 108
 109 (** This module provides a functor to disambiguate the input **)
 110 (** given a set of user-interface call-backs                 **)
 111
 112 module type Callbacks =
 113   sig
 114     val output_html : string -> unit
 115     val interactive_user_uri_choice :
 116       selection_mode:[`SINGLE | `EXTENDED] ->
 117       ?ok:string ->
 118       ?enable_button_for_non_vars:bool ->
 119       title:string -> msg:string -> id:string -> string list -> string list
 120     val interactive_interpretation_choice :
 121       (string * string) list list -> int
 122     val input_or_locate_uri : title:string -> UriManager.uri
 123   end
 124 ;;
 125
 126 type domain_and_interpretation =
 127  string list * (string -> CicTextualParser0.uri option)
 128 ;;
 129
 130 module Make(C:Callbacks) =
 131   struct
 132
 133    let locate_one_id id =
 134     let result = MQueryGenerator.locate id in
 135     let uris =
 136      List.map
 137       (function uri,_ ->
 138         wrong_xpointer_format_from_wrong_xpointer_format' uri
 139       ) result in
 140     let html=
 141      " <h1>Locate Query: </h1><pre>" ^ get_last_query result ^ "</pre>"
 142     in
 143      C.output_html html ;
 144      let uris' =
 145       match uris with
 146          [] ->
 147           [UriManager.string_of_uri
 148            (C.input_or_locate_uri
 149              ~title:("URI matching \"" ^ id ^ "\" unknown."))]
 150        | [uri] -> [uri]
 151        | _ ->
 152          C.interactive_user_uri_choice
 153           ~selection_mode:`EXTENDED
 154           ~ok:"Try every selection."
 155           ~enable_button_for_non_vars:true
 156           ~title:"Ambiguous input."
 157           ~msg:
 158             ("Ambiguous input \"" ^ id ^
 159              "\". Please, choose one or more interpretations:")
 160           ~id
 161           uris
 162      in
 163       List.map cic_textual_parser_uri_of_string uris'
 164
 165
 166    exception ThereDoesNotExistAnyWellTypedInterpretationOfTheInput
 167
 168    type test_result =
 169       Ok of Cic.term * Cic.metasenv
 170     | Ko
 171     | Uncertain
 172
 173    let disambiguate_input context metasenv dom mk_metasenv_and_expr ~id_to_uris=
 174     let known_ids,resolve_id = id_to_uris in
 175     let dom' =
 176      let rec filter =
 177       function
 178          [] -> []
 179        | he::tl ->
 180           if List.mem he known_ids then filter tl else he::(filter tl)
 181      in
 182       filter dom
 183     in
 184      (* for each id in dom' we get the list of uris associated to it *)
 185      let list_of_uris = List.map locate_one_id dom' in
 186      let tests_no =
 187       List.fold_left (fun i uris -> i * List.length uris) 1 list_of_uris
 188      in
 189       if tests_no > 1 then
 190        C.output_html
 191         ("<h1>Disambiguation phase started: " ^
 192           string_of_int tests_no ^ " cases will be tried.") ;
 193      (* and now we compute the list of all possible assignments from *)
 194      (* id to uris that generate well-typed terms                    *)
 195      let resolve_ids =
 196       (* function to test if a partial interpretation is so far correct *)
 197       let test resolve_id residual_dom =
 198        (* We put implicits in place of every identifier that is not *)
 199        (* resolved by resolve_id                                    *)
 200        let resolve_id'' =
 201         let resolve_id' =
 202          function id ->
 203           match resolve_id id with
 204              None -> None
 205            | Some uri -> Some (CicTextualParser0.Uri uri)
 206         in
 207          List.fold_left
 208           (fun f id ->
 209             function id' ->
 210              if id = id' then Some (CicTextualParser0.Implicit) else f id'
 211           ) resolve_id' residual_dom
 212        in
 213         (* and we try to refine the term *)
 214         let saved_status = !CicTextualParser0.metasenv in
 215         let metasenv',expr = mk_metasenv_and_expr resolve_id'' in
 216 (*CSC: Bug here: we do not try to typecheck also the metasenv' *)
 217         (* The parser is imperative ==> we must restore the old status ;-(( *)
 218         CicTextualParser0.metasenv := saved_status ;
 219          try
 220           let term,_,_,metasenv'' =
 221            CicRefine.type_of_aux' metasenv' context expr
 222           in
 223            Ok (term,metasenv'')
 224          with
 225             CicRefine.MutCaseFixAndCofixRefineNotImplemented ->
 226              (try
 227                let term = CicTypeChecker.type_of_aux' metasenv' context expr in
 228                 Ok (term,metasenv')
 229               with _ -> Ko
 230              )
 231           | CicRefine.Uncertain _ ->
 232 prerr_endline ("%%% UNCERTAIN!!! " ^ CicPp.ppterm expr) ;
 233              Uncertain
 234           | _ ->
 235 prerr_endline ("%%% PRUNED!!! " ^ CicPp.ppterm expr) ;
 236             Ko
 237       in
 238       let rec aux resolve_id ids list_of_uris =
 239        match ids,list_of_uris with
 240           [],[] ->
 241            (match test resolve_id [] with
 242                Ok (term,metasenv) -> [resolve_id,term,metasenv]
 243              | Ko | Uncertain -> [])
 244         | id::idtl,uris::uristl ->
 245            let rec filter =
 246             function
 247                [] -> []
 248              | uri::uritl ->
 249                 let resolve_id' =
 250                  function id' -> if id = id' then Some uri else resolve_id id'
 251                 in
 252                  (match test resolve_id' idtl with
 253                      Ok (term,metasenv) ->
 254                       (* the next three ``if''s are used to avoid the base   *)
 255                       (* case where the term would be refined a second time. *)
 256                       (if uristl = [] then
 257                         [resolve_id',term,metasenv]
 258                        else
 259                         (aux resolve_id' idtl uristl)
 260                       ) @ (filter uritl)
 261                    | Uncertain ->
 262                       (if uristl = [] then []
 263                        else
 264                         (aux resolve_id' idtl uristl)
 265                       ) @ (filter uritl)
 266                    | Ko ->
 267                       filter uritl
 268                  )
 269            in
 270             filter uris
 271         | _,_ -> assert false
 272       in
 273        aux resolve_id dom' list_of_uris
 274      in
 275       List.iter
 276        (function (resolve,term,newmetasenv) ->
 277          (* If metasen <> newmetasenv is a normal condition, we should *)
 278          (* be prepared to apply the returned substitution to the      *)
 279          (* whole current proof.                                       *)
 280          if metasenv <> newmetasenv then
 281           begin
 282            prerr_endline
 283             ("+++++ ASSERTION FAILED: " ^
 284              "a refine operation should not modify the metasenv") ;
 285            (* an assert would raise an exception that could be caught *)
 286            exit 1
 287           end
 288        ) resolve_ids ;
 289       let resolve_id',term,metasenv' =
 290        match resolve_ids with
 291           [] -> raise ThereDoesNotExistAnyWellTypedInterpretationOfTheInput
 292         | [resolve_id] -> resolve_id
 293         | _ ->
 294           let choices =
 295            List.map
 296             (function (resolve,_,_) ->
 297               List.map
 298                (function id ->
 299                  id,
 300                   match resolve id with
 301                      None -> assert false
 302                    | Some uri ->
 303                       match uri with
 304                          CicTextualParser0.ConUri uri
 305                        | CicTextualParser0.VarUri uri ->
 306                           UriManager.string_of_uri uri
 307                        | CicTextualParser0.IndTyUri (uri,tyno) ->
 308                           UriManager.string_of_uri uri ^ "#xpointer(1/" ^
 309                            string_of_int (tyno+1) ^ ")"
 310                        | CicTextualParser0.IndConUri (uri,tyno,consno) ->
 311                           UriManager.string_of_uri uri ^ "#xpointer(1/" ^
 312                            string_of_int (tyno+1) ^ "/" ^ string_of_int consno ^                           ")"
 313                ) dom
 314             ) resolve_ids
 315           in
 316            let index = C.interactive_interpretation_choice choices in
 317             List.nth resolve_ids index
 318       in
 319        (known_ids @ dom', resolve_id'), metasenv',term
 320 end
 321 ;;