← Back to branch summary

~ubuntu-branches/ubuntu/wily/coq-doc/wily

« back to all changes in this revision

Viewing changes to tactics/dn.ml

  • Committer: Bazaar Package Importer
  • Author(s): Stéphane Glondu, Stéphane Glondu, Samuel Mimram
  • Date: 2010-01-07 22:50:39 UTC
  • mfrom: (1.2.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20100107225039-n3cq82589u0qt0s2
Tags: 8.2pl1-1
http://bugs.debian.org/563669
http://bugs.debian.org/543545
[ Stéphane Glondu ]
* New upstream release (Closes: #563669)
  - remove patches
* Packaging overhaul:
  - use git, advertise it in Vcs-* fields of debian/control
  - use debhelper 7 and dh with override
  - use source format 3.0 (quilt)
* debian/control:
  - set Maintainer to d-o-m, set Uploaders to Sam and myself
  - add Homepage field
  - bump Standards-Version to 3.8.3
* Register PDF documentation into doc-base
* Add debian/watch
* Update debian/copyright

[ Samuel Mimram ]
* Change coq-doc's description to mention that it provides documentation in
  pdf format, not postscript, closes: #543545.

Show diffs side-by-side

added added

removed removed

Lines of Context:
tactics/dn.ml
 
1
(* -*- compile-command: "make -C .. bin/coqtop.byte" -*- *)
 
2
(************************************************************************)
 
3
(*  v      *   The Coq Proof Assistant  /  The Coq Development Team     *)
 
4
(* <O___,, * CNRS-Ecole Polytechnique-INRIA Futurs-Universite Paris Sud *)
 
5
(*   \VV/  **************************************************************)
 
6
(*    //   *      This file is distributed under the terms of the       *)
 
7
(*         *       GNU Lesser General Public License Version 2.1        *)
 
8
(************************************************************************)
 
9
 
 
10
(* $Id: dn.ml 11282 2008-07-28 11:51:53Z msozeau $ *)
 
11
 
 
12
(* This file implements the basic structure of what Chet called
 
13
   ``discrimination nets''. If my understanding is right, it serves
 
14
   to associate actions (for example, tactics) with a priority to term
 
15
   patterns, so that if a hypothesis matches a pattern in the net,
 
16
   then the associated tactic is applied. Discrimination nets are used
 
17
   (only) to implement the tactics Auto, DHyp and Point.
 
18
 
 
19
   A discrimination net is a tries structure, that is, a tree structure 
 
20
   specially conceived for searching patterns, like for example strings
 
21
   --see the file Tlm.ml in the directory lib/util--. Here the tries
 
22
   structure are used for looking for term patterns.
 
23
 
 
24
   This module is then used in :
 
25
     - termdn.ml   (discrimination nets of terms);
 
26
     - btermdn.ml  (discrimination nets of terms with bounded depth,
 
27
                    used in the tactic auto);
 
28
     - nbtermdn.ml (named discrimination nets with bounded depth, used
 
29
                    in the tactics Dhyp and Point).
 
30
  Eduardo (4/8/97) *)
 
31
 
 
32
(* Definition of the basic structure *)
 
33
 
 
34
type ('lbl,'pat) decompose_fun = 'pat -> ('lbl * 'pat list) option
 
35
 
 
36
type 'res lookup_res = Label of 'res | Nothing | Everything
 
37
    
 
38
type ('lbl,'tree) lookup_fun = 'tree -> ('lbl * 'tree list) lookup_res
 
39
 
 
40
type ('lbl,'pat,'inf) t = (('lbl * int) option,'pat * 'inf) Tlm.t
 
41
 
 
42
let create () = Tlm.empty
 
43
 
 
44
(* [path_of dna pat] returns the list of nodes of the pattern [pat] read in 
 
45
prefix ordering, [dna] is the function returning the main node of a pattern *)
 
46
 
 
47
let path_of dna =
 
48
  let rec path_of_deferred = function
 
49
    | [] -> []
 
50
    | h::tl -> pathrec tl h
 
51
            
 
52
  and pathrec deferred t =
 
53
    match dna t with
 
54
    | None -> 
 
55
        None :: (path_of_deferred deferred)
 
56
    | Some (lbl,[]) ->
 
57
        (Some (lbl,0))::(path_of_deferred deferred)
 
58
    | Some (lbl,(h::def_subl as v)) ->
 
59
        (Some (lbl,List.length v))::(pathrec (def_subl@deferred) h)
 
60
  in 
 
61
  pathrec []
 
62
    
 
63
let tm_of tm lbl =
 
64
  try [Tlm.map tm lbl, true] with Not_found -> []
 
65
    
 
66
let rec skip_arg n tm =
 
67
  if n = 0 then [tm,true]
 
68
  else
 
69
    List.flatten 
 
70
      (List.map 
 
71
          (fun a -> match a with
 
72
          | None -> skip_arg (pred n) (Tlm.map tm a)
 
73
          | Some (lbl,m) -> 
 
74
              skip_arg (pred n + m) (Tlm.map tm a)) 
 
75
          (Tlm.dom tm))
 
76
      
 
77
let lookup tm dna t =
 
78
  let rec lookrec t tm =
 
79
    match dna t with
 
80
    | Nothing -> tm_of tm None
 
81
    | Label(lbl,v) ->
 
82
        tm_of tm None@
 
83
          (List.fold_left 
 
84
              (fun l c -> 
 
85
                List.flatten(List.map (fun (tm, b) ->
 
86
                  if b then lookrec c tm
 
87
                  else [tm,b]) l))
 
88
              (tm_of tm (Some(lbl,List.length v))) v)
 
89
    | Everything -> skip_arg 1 tm
 
90
  in 
 
91
    List.flatten (List.map (fun (tm,b) -> Tlm.xtract tm) (lookrec t tm))
 
92
 
 
93
let add tm dna (pat,inf) =
 
94
  let p = path_of dna pat in Tlm.add tm (p,(pat,inf))
 
95
    
 
96
let rmv tm dna (pat,inf) =
 
97
  let p = path_of dna pat in Tlm.rmv tm (p,(pat,inf))
 
98
    
 
99
let app f tm = Tlm.app (fun (_,p) -> f p) tm
 
100