Fixed a bug in deep_eq: we generated new clauses but neglected the

[helm.git] / helm / software / components / ng_paramodulation / superposition.ml

diff --git a/helm/software/components/ng_paramodulation/superposition.ml b/helm/software/components/ng_paramodulation/superposition.ml
index 585fbe2371caf146bb2377e072cc75b37039addb..f38acb536a707eeb5d0871b781af25cd2af412eb 100644 (file)
--- a/helm/software/components/ng_paramodulation/superposition.ml
+++ b/helm/software/components/ng_paramodulation/superposition.ml
@@ -20,9 +20,13 @@ module Superposition (B : Orderings.Blob) =
     module Utils = FoUtils.Utils(B)
     module Pp = Pp.Pp(B)
     
-    exception Success of B.t Terms.bag * int * B.t Terms.unit_clause
+    exception Success of 
+      B.t Terms.bag 
+      * int 
+      * B.t Terms.unit_clause
+      * B.t Terms.substitution
 
-    (* let debug s = prerr_endline (Lazy.force s);; *)
+    let print s = prerr_endline (Lazy.force s);; 
     let debug _ = ();; 
     let enable = true;;
 
@@ -243,10 +247,12 @@ module Superposition (B : Orderings.Blob) =
                      ((*prerr_endline ("Filtering: " ^ 
                         Pp.pp_foterm side ^ " =(< || =)" ^ 
                         Pp.pp_foterm newside ^ " coming from " ^ 
-                        Pp.pp_unit_clause uc );*)None)
+                        Pp.pp_unit_clause uc );*)
+                      debug (lazy "not applied");None)
                  else
                    Some (newside, subst, id, dir)
-               with FoUnif.UnificationFailure _ -> None)
+               with FoUnif.UnificationFailure _ -> 
+                 debug (lazy "not applied"); None)
         (IDX.ClauseSet.elements cands)
     ;;
 
@@ -264,7 +270,7 @@ module Superposition (B : Orderings.Blob) =
     ;;
       
     let rec demodulate bag (id, literal, vl, pr) table =
-      debug (lazy "demodulate...");
+      debug (lazy ("demodulate " ^ (string_of_int id)));
        match literal with
       | Terms.Predicate t -> assert false
       | Terms.Equation (l,r,ty,_) ->
@@ -311,22 +317,33 @@ module Superposition (B : Orderings.Blob) =
     ;;
 
     (* move away *)
-    let is_identity_clause ~unify = function
+    let is_identity_clause = function
       | _, Terms.Equation (_,_,_,Terms.Eq), _, _ -> true
-      | _, Terms.Equation (l,r,_,_), vl, proof when unify ->
-          (try ignore(Unif.unification (* vl *) [] l r); true
-          with FoUnif.UnificationFailure _ -> false)
       | _, Terms.Equation (_,_,_,_), _, _ -> false
       | _, Terms.Predicate _, _, _ -> assert false          
     ;;
 
-    let build_new_clause bag maxvar filter rule t subst id id2 pos dir =
+    let is_identity_goal = function
+      | _, Terms.Equation (_,_,_,Terms.Eq), _, _ -> Some []
+      | _, Terms.Equation (l,r,_,_), vl, proof ->
+          (try Some (Unif.unification (* vl *) [] l r)
+           with FoUnif.UnificationFailure _ -> None)
+      | _, Terms.Predicate _, _, _ -> assert false          
+    ;;
+
+    let build_new_clause_reloc bag maxvar filter rule t subst id id2 pos dir =
       let maxvar, _vl, subst = Utils.relocate maxvar (Terms.vars_of_term
       (Subst.apply_subst subst t)) subst in
       match build_clause bag filter rule t subst id id2 pos dir with
-      | Some (bag, c) -> Some ((bag, maxvar), c)
-      | None -> None
+      | Some (bag, c) -> Some ((bag, maxvar), c), subst
+      | None -> None,subst
     ;;
+
+    let build_new_clause bag maxvar filter rule t subst id id2 pos dir =
+      fst (build_new_clause_reloc bag maxvar filter rule t 
+            subst id id2 pos dir)
+    ;;
+
     let prof_build_new_clause = HExtlib.profile ~enable "build_new_clause";;
     let build_new_clause bag maxvar filter rule t subst id id2 pos x =
       prof_build_new_clause.HExtlib.profile (build_new_clause bag maxvar filter
@@ -415,13 +432,14 @@ module Superposition (B : Orderings.Blob) =
                       (Terms.Node[Terms.Leaf B.eqP;ty;contextl r;contextr r]) 
                   in
                     (match 
-                      build_new_clause bag maxvar (fun _ -> true)
+                      build_new_clause_reloc bag maxvar (fun _ -> true)
                         Terms.Superposition id_t 
                         subst1 id id2 (pos@[2]) dir 
                     with
-                    | Some ((bag, maxvar), c) -> 
+                    | Some ((bag, maxvar), c), r ->
+                       let newsubst = Subst.concat r newsubst in
                         Some(bag,maxvar,c,newsubst)
-                    | None -> assert false)
+                    | None, _ -> assert false)
               | None ->
                   match l,r with 
                   | Terms.Node (a::la), Terms.Node (b::lb) when 
@@ -443,6 +461,7 @@ module Superposition (B : Orderings.Blob) =
                       in acc
                   | _,_ -> None
     ;;
+
     let prof_deep_eq = HExtlib.profile ~enable "deep_eq";;
     let deep_eq ~unify l r ty pos contextl contextr table x =
       prof_deep_eq.HExtlib.profile (deep_eq ~unify l r ty pos contextl contextr table) x
@@ -475,10 +494,10 @@ module Superposition (B : Orderings.Blob) =
     (* demodulate and check for subsumption *)
     let simplify table maxvar bag clause =
       debug (lazy "simplify...");
-      if is_identity_clause ~unify:false clause then bag,None
+      if is_identity_clause clause then bag,None
       (* else if orphan_murder bag actives clause then bag,None *)
       else let bag, clause = demodulate bag clause table in
-      if is_identity_clause ~unify:false clause then bag,None
+      if is_identity_clause clause then bag,None
       else
         match is_subsumed ~unify:false bag maxvar clause table with
           | None -> bag, Some clause
@@ -607,10 +626,13 @@ module Superposition (B : Orderings.Blob) =
       let bag, clause = 
         if no_demod then bag, clause else demodulate bag clause table 
       in
+      let _ = debug (lazy ("demodulated goal  : " 
+                            ^ Pp.pp_unit_clause clause))
+      in
       if List.exists (are_alpha_eq clause) g_actives then None
-      else if (is_identity_clause ~unify:true clause)
-      then raise (Success (bag, maxvar, clause))
-      else   
+      else match (is_identity_goal clause) with
+       | Some subst -> raise (Success (bag,maxvar,clause,subst))
+       | None ->
         let (id,lit,vl,_) = clause in 
         (* this optimization makes sense only if we demodulated, since in 
           that case the clause should have been turned into an identity *)
@@ -627,7 +649,7 @@ module Superposition (B : Orderings.Blob) =
          | None -> Some (bag,clause)
          | Some (bag,maxvar,cl,subst) -> 
              debug (lazy "Goal subsumed");
-             raise (Success (bag,maxvar,cl))
+             raise (Success (bag,maxvar,cl,subst))
 (*
         match is_subsumed ~unify:true bag maxvar clause table with
         | None -> Some (bag, clause)
@@ -740,6 +762,10 @@ module Superposition (B : Orderings.Blob) =
              bag, maxvar, newc @ acc)
           (bag, maxvar, []) alist
       in
+        debug
+       (lazy 
+        ("New clauses :" ^ (String.concat ";\n" 
+           (List.map Pp.pp_unit_clause new_clauses)))); 
         debug (lazy "First superpositions");
         (* We add current to active clauses so that it can be *
          * superposed with itself                             *)