src/Pure/unify.ML
changeset 79743 3648e9c88d0c
parent 79742 2e4518e8a36b
child 80328 559909bd7715
equal deleted inserted replaced
79742:2e4518e8a36b 79743:3648e9c88d0c
    10 *)
    10 *)
    11 
    11 
    12 signature UNIFY =
    12 signature UNIFY =
    13 sig
    13 sig
    14   val search_bound: int Config.T
    14   val search_bound: int Config.T
       
    15   val unify_trace: bool Config.T
    15   val unify_trace_bound: int Config.T
    16   val unify_trace_bound: int Config.T
    16   val unify_trace_simp: bool Config.T
    17   val unify_trace_simp: bool Config.T
    17   val unify_trace_types: bool Config.T
    18   val unify_trace_types: bool Config.T
    18   val hounifiers: (string * typ) list -> Context.generic * Envir.env * ((term * term) list) ->
    19   val hounifiers: (string * typ) list -> Context.generic * Envir.env * ((term * term) list) ->
    19     (Envir.env * (term * term) list) Seq.seq
    20     (Envir.env * (term * term) list) Seq.seq
    31 val search_bound = Config.declare_int ("unify_search_bound", \<^here>) (K 60);
    32 val search_bound = Config.declare_int ("unify_search_bound", \<^here>) (K 60);
    32 
    33 
    33 
    34 
    34 (* diagnostics *)
    35 (* diagnostics *)
    35 
    36 
       
    37 val unify_trace = Config.declare_bool ("unify_trace", \<^here>) (K false);
       
    38 
    36 (*tracing starts above this depth, 0 for full*)
    39 (*tracing starts above this depth, 0 for full*)
    37 val unify_trace_bound = Config.declare_int ("unify_trace_bound", \<^here>) (K 50);
    40 val unify_trace_bound = Config.declare_int ("unify_trace_bound", \<^here>) (K 50);
    38 
    41 
    39 (*print dpairs before calling SIMPL*)
    42 (*print dpairs before calling SIMPL*)
    40 val unify_trace_simp = Config.declare_bool ("unify_trace_simp", \<^here>) (K false);
    43 val unify_trace_simp = Config.declare_bool ("unify_trace_simp", \<^here>) (K false);
    41 
    44 
    42 (*announce potential incompleteness of type unification*)
    45 (*announce potential incompleteness of type unification*)
    43 val unify_trace_types = Config.declare_bool ("unify_trace_types", \<^here>) (K false);
    46 val unify_trace_types = Config.declare_bool ("unify_trace_types", \<^here>) (K false);
       
    47 
       
    48 fun cond_tracing ctxt msg =
       
    49   if Config.get_generic ctxt unify_trace andalso Context_Position.is_visible_generic ctxt then
       
    50     tracing (msg ())
       
    51   else ();
    44 
    52 
    45 
    53 
    46 type binderlist = (string * typ) list;
    54 type binderlist = (string * typ) list;
    47 
    55 
    48 type dpair = binderlist * term * term;
    56 type dpair = binderlist * term * term;
   179 fun unify_types context TU env =
   187 fun unify_types context TU env =
   180   Pattern.unify_types context TU env handle Pattern.Unif => raise CANTUNIFY;
   188   Pattern.unify_types context TU env handle Pattern.Unif => raise CANTUNIFY;
   181 
   189 
   182 fun test_unify_types context (T, U) env =
   190 fun test_unify_types context (T, U) env =
   183   let
   191   let
   184     fun trace () =
   192     fun msg () =
   185       if Context_Position.is_visible_generic context then
   193       let val str_of = Syntax.string_of_typ (Context.proof_of context)
   186         let val str_of = Syntax.string_of_typ (Context.proof_of context)
   194       in "Potential loss of completeness: " ^ str_of U ^ " = " ^ str_of T end
   187         in tracing ("Potential loss of completeness: " ^ str_of U ^ " = " ^ str_of T) end
       
   188       else ();
       
   189     val env' = unify_types context (T, U) env;
   195     val env' = unify_types context (T, U) env;
   190   in if is_TVar T orelse is_TVar U then trace () else (); env' end;
   196   in if is_TVar T orelse is_TVar U then cond_tracing context msg else (); env' end;
   191 
   197 
   192 (*Is the term eta-convertible to a single variable with the given rbinder?
   198 (*Is the term eta-convertible to a single variable with the given rbinder?
   193   Examples: ?a   ?f(B.0)   ?g(B.1,B.0)
   199   Examples: ?a   ?f(B.0)   ?g(B.1,B.0)
   194   Result is var a for use in SIMPL. *)
   200   Result is var a for use in SIMPL. *)
   195 fun get_eta_var ([], _, Var vT) = vT
   201 fun get_eta_var ([], _, Var vT) = vT
   566 
   572 
   567 (*Print a tracing message + list of dpairs.
   573 (*Print a tracing message + list of dpairs.
   568   In t \<equiv> u print u first because it may be rigid or flexible --
   574   In t \<equiv> u print u first because it may be rigid or flexible --
   569     t is always flexible.*)
   575     t is always flexible.*)
   570 fun print_dpairs context msg (env, dpairs) =
   576 fun print_dpairs context msg (env, dpairs) =
   571   if Context_Position.is_visible_generic context then
   577   let
   572     let
   578     fun pdp (rbinder, t, u) =
   573       fun pdp (rbinder, t, u) =
   579       let
   574         let
   580         val ctxt = Context.proof_of context;
   575           val ctxt = Context.proof_of context;
   581         fun termT t =
   576           fun termT t =
   582           Syntax.pretty_term ctxt (Envir.norm_term env (Logic.rlist_abs (rbinder, t)));
   577             Syntax.pretty_term ctxt (Envir.norm_term env (Logic.rlist_abs (rbinder, t)));
   583         val prt = Pretty.blk (0, [termT u, Pretty.str " \<equiv>\<^sup>?", Pretty.brk 1, termT t]);
   578           val prt = Pretty.blk (0, [termT u, Pretty.str " \<equiv>\<^sup>?", Pretty.brk 1, termT t]);
   584       in Pretty.string_of prt end;
   579         in tracing (Pretty.string_of prt) end;
   585   in
   580     in tracing msg; List.app pdp dpairs end
   586     cond_tracing context (fn () => msg);
   581   else ();
   587     List.app (fn dp => cond_tracing context (fn () => pdp dp)) dpairs
       
   588   end;
   582 
   589 
   583 
   590 
   584 (*Unify the dpairs in the environment.
   591 (*Unify the dpairs in the environment.
   585   Returns flex-flex disagreement pairs NOT IN normal form.
   592   Returns flex-flex disagreement pairs NOT IN normal form.
   586   SIMPL may raise exception CANTUNIFY. *)
   593   SIMPL may raise exception CANTUNIFY. *)
   600         in
   607         in
   601           (case flexrigid of
   608           (case flexrigid of
   602             [] => SOME (fold_rev (add_ffpair context) flexflex (env', []), reseq)
   609             [] => SOME (fold_rev (add_ffpair context) flexflex (env', []), reseq)
   603           | dp :: frigid' =>
   610           | dp :: frigid' =>
   604               if tdepth > search_bound then
   611               if tdepth > search_bound then
   605                 (if Context_Position.is_visible_generic context
   612                 (if Context_Position.is_visible_generic context then
   606                  then warning "Unification bound exceeded" else (); Seq.pull reseq)
   613                    warning "Unification bound exceeded -- see unify trace for details"
       
   614                  else (); Seq.pull reseq)
   607               else
   615               else
   608                (if tdepth > unify_trace_bound then
   616                (if tdepth > unify_trace_bound then
   609                   print_dpairs context "Enter MATCH" (env',flexrigid@flexflex)
   617                   print_dpairs context "Enter MATCH" (env',flexrigid@flexflex)
   610                 else ();
   618                 else ();
   611                 Seq.pull (Seq.it_right
   619                 Seq.pull (Seq.it_right
   612                     (add_unify (tdepth + 1)) (MATCH context (env',dp, frigid'@flexflex), reseq))))
   620                     (add_unify (tdepth + 1)) (MATCH context (env',dp, frigid'@flexflex), reseq))))
   613         end
   621         end
   614         handle CANTUNIFY =>
   622         handle CANTUNIFY =>
   615          (if tdepth > unify_trace_bound andalso Context_Position.is_visible_generic context
   623          (if tdepth > unify_trace_bound
   616           then tracing "Failure node"
   624           then cond_tracing context (fn () => "Failure node")
   617           else (); Seq.pull reseq));
   625           else (); Seq.pull reseq));
   618     val dps = map (fn (t, u) => (binders, t, u)) tus;
   626     val dps = map (fn (t, u) => (binders, t, u)) tus;
   619   in add_unify 1 ((env, dps), Seq.empty) end;
   627   in add_unify 1 ((env, dps), Seq.empty) end;
   620 
   628 
   621 fun unifiers (params as (context, env, tus)) =
   629 fun unifiers (params as (context, env, tus)) =