Added count_occurrences.

[helm.git] / helm / software / components / ng_kernel / nCicUntrusted.ml

diff --git a/helm/software/components/ng_kernel/nCicUntrusted.ml b/helm/software/components/ng_kernel/nCicUntrusted.ml
index 524a00cd35f73cdd4477b8e3191f30ceff7bca31..b110d0651adff6d6afd61978a43d8589fe1f6900 100644 (file)
--- a/helm/software/components/ng_kernel/nCicUntrusted.ml
+++ b/helm/software/components/ng_kernel/nCicUntrusted.ml
@@ -312,3 +312,28 @@ let relations_of_menv subst m c =
 let sort_metasenv subst (m : NCic.metasenv) =
   (MS.topological_sort m (relations_of_menv subst m) : NCic.metasenv)
 ;;
+
+let count_occurrences ~subst context n t = 
+  let occurrences = ref 0 in
+  let rec aux k _ = function
+    | C.Rel m when m = n+k -> incr occurrences
+    | C.Rel m ->
+        (try match List.nth context (m-1-k) with
+          | _,C.Def (bo,_) -> aux (n-m) () bo
+          | _ -> ()
+         with Failure _ -> assert false)
+    | C.Meta (_,(_,(C.Irl 0 | C.Ctx []))) -> (* closed meta *) ()
+    | C.Meta (mno,(s,l)) ->
+         (try
+            (* possible optimization here: try does_not_occur on l and
+               perform substitution only if DoesOccur is raised *)
+            let _,_,term,_ = NCicUtils.lookup_subst mno subst in
+            aux (k-s) () (NCicSubstitution.subst_meta (0,l) term)
+          with NCicUtils.Subst_not_found _ -> () (*match l with
+          | C.Irl len -> if not (n+k >= s+len || s > nn+k) then raise DoesOccur
+          | C.Ctx lc -> List.iter (aux (k-s) ()) lc*))
+    | t -> NCicUtils.fold (fun _ k -> k + 1) k aux () t
+  in
+   aux 0 () t;
+   !occurrences
+;;