aboutsummaryrefslogtreecommitdiffstats
path: root/src/trace/smtForm.ml
blob: 6075b3ffba7b3c0e74262e0e9630365bccb0b863 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
(**************************************************************************)
(*                                                                        *)
(*     SMTCoq                                                             *)
(*     Copyright (C) 2011 - 2015                                          *)
(*                                                                        *)
(*     Michaël Armand                                                     *)
(*     Benjamin Grégoire                                                  *)
(*     Chantal Keller                                                     *)
(*                                                                        *)
(*     Inria - École Polytechnique - MSR-Inria Joint Lab                  *)
(*                                                                        *)
(*   This file is distributed under the terms of the CeCILL-C licence     *)
(*                                                                        *)
(**************************************************************************)
open Util
open SmtMisc
open CoqTerms
open Errors

module type ATOM = 
  sig 

    type t 
    val index : t -> int

    val equal : t -> t -> bool

    val is_bool_type : t -> bool

  end 


type fop =
  | Ftrue
  | Ffalse
  | Fand
  | For
  | Fxor
  | Fimp
  | Fiff
  | Fite
  | Fnot2 of int

type ('a,'f) gen_pform = 
  | Fatom of 'a
  | Fapp of fop * 'f array


module type FORM =
  sig 
    type hatom 
    type t
    type pform = (hatom, t) gen_pform

      val pform_true : pform
      val pform_false : pform

      val equal : t -> t -> bool

      val to_lit : t -> int
      val index : t -> int
      val pform : t -> pform

      val neg : t -> t
      val is_pos : t -> bool
      val is_neg : t -> bool

      val to_smt : (Format.formatter -> hatom -> unit) -> Format.formatter -> t -> unit

      (* Building formula from positive formula *)
      exception NotWellTyped of pform
      type reify 
      val create : unit -> reify 
      val clear : reify -> unit
      val get : reify -> pform -> t
      
      (** Give a coq term, build the corresponding formula *)  
      val of_coq : (Term.constr -> hatom) -> reify -> Term.constr -> t
   
      (** Flattening of [Fand] and [For], removing of [Fnot2]  *)
      val flatten : reify -> t -> t

      (** Producing Coq terms *) 

      val to_coq : t -> Term.constr

      val pform_tbl : reify -> pform array

      val to_array : reify -> 'a -> (pform -> 'a) -> int * 'a array
      val interp_tbl : reify -> Term.constr * Term.constr
      val nvars : reify -> int 
      (** Producing a Coq term corresponding to the interpretation 
          of a formula *)
      (** [interp_atom] map [hatom] to coq term, it is better if it produce
          shared terms. *)
      val interp_to_coq : 
	  (hatom -> Term.constr) -> (int, Term.constr) Hashtbl.t -> 
	    t -> Term.constr
  end

module Make (Atom:ATOM) =
  struct 

    type hatom = Atom.t 

    type pform = (Atom.t, t) gen_pform
 
    and hpform = pform gen_hashed
	  
    and t = 
      | Pos of hpform
      | Neg of hpform 

    let pform_true = Fapp (Ftrue,[||])
    let pform_false = Fapp (Ffalse,[||])

    let equal h1 h2 = 
      match h1, h2 with
      | Pos hp1, Pos hp2 -> hp1.index == hp2.index
      | Neg hp1, Neg hp2 -> hp1.index == hp2.index
      | _, _ -> false

    let index = function
      | Pos hp -> hp.index
      | Neg hp -> hp.index

    let to_lit = function
      | Pos hp -> hp.index * 2
      | Neg hp -> hp.index * 2 + 1

    let neg = function
      | Pos hp -> Neg hp
      | Neg hp -> Pos hp
	    
    let is_pos = function
      | Pos _ -> true
      | _ -> false
	    
    let is_neg = function
      | Neg _ -> true
      | _ -> false

    let pform = function
      | Pos hp -> hp.hval
      | Neg hp -> hp.hval


    let rec to_smt atom_to_smt fmt = function
      | Pos hp -> to_smt_pform atom_to_smt fmt hp.hval
      | Neg hp ->
        Format.fprintf fmt "(not ";
        to_smt_pform atom_to_smt fmt hp.hval;
        Format.fprintf fmt ")"

    and to_smt_pform atom_to_smt fmt = function
      | Fatom a -> atom_to_smt fmt a
      | Fapp (op,args) -> to_smt_op atom_to_smt fmt op args

    and to_smt_op atom_to_smt fmt op args =
      let s = match op with
        | Ftrue -> "true"
        | Ffalse -> "false"
        | Fand -> "and"
        | For -> "or"
        | Fxor -> "xor"
        | Fimp -> "=>"
        | Fiff -> "="
        | Fite -> "ite"
        | Fnot2 _ -> "" in
      let (s1,s2) = if Array.length args = 0 then ("","") else ("(",")") in
      Format.fprintf fmt "%s%s" s1 s;
      Array.iter (fun h -> Format.fprintf fmt " "; to_smt atom_to_smt fmt h) args;
      Format.fprintf fmt "%s" s2


    module HashedForm =
      struct 
	
	type t = pform
	      
	let equal pf1 pf2 = 
	  match pf1, pf2 with
	  | Fatom ha1, Fatom ha2 -> Atom.equal ha1 ha2
	  | Fapp(op1,args1), Fapp(op2,args2) ->
	      op1 = op2 && 
	      Array.length args1 == Array.length args2 &&
	      (try 
		for i = 0 to Array.length args1 - 1 do
		  if not (equal args1.(i) args2.(i)) then raise Not_found 
		done;
		true
	      with Not_found -> false)
	  | _, _ -> false

	let hash pf = 
	  match pf with
	  | Fatom ha1 -> Atom.index ha1 * 2 
	  | Fapp(op, args) -> 
	      let hash_args =
		match Array.length args with
		| 0 -> 0
		| 1 -> to_lit args.(0)
		| 2 -> (to_lit args.(1)) lsl 2 + to_lit args.(0)
		| _ -> 
		    (to_lit args.(2)) lsl 4 + (to_lit args.(1)) lsl 2 +
		      to_lit args.(0) in
	      (hash_args * 10 + Hashtbl.hash op) * 2 + 1
		
      end

    module HashForm = Hashtbl.Make (HashedForm)

    type reify = {
	mutable count : int;
                tbl : t HashForm.t 
      }  

    exception NotWellTyped of pform
   	
    let check pf = 
      match pf with
      | Fatom ha ->  if not (Atom.is_bool_type ha) then raise (NotWellTyped pf)
      | Fapp (op, args) ->
	  match op with
	  | Ftrue | Ffalse -> 
	      if Array.length args <> 0 then raise (NotWellTyped pf)
	  | Fnot2 _ -> 
	      if Array.length args <> 1 then raise (NotWellTyped pf)
	  | Fand | For -> ()
	  | Fxor | Fimp | Fiff ->
	      if Array.length args <> 2 then raise (NotWellTyped pf)
	  | Fite ->
	      if Array.length args <> 3 then raise (NotWellTyped pf)

    let declare reify pf =
      check pf;
      let res = Pos {index = reify.count; hval = pf} in
      HashForm.add reify.tbl pf res;
      reify.count <- reify.count + 1;
      res

    let create () =
      let reify = 
	{ count = 0; 
	  tbl =  HashForm.create 17 } in
      let _ = declare reify pform_true in
      let _ = declare reify pform_false in
      reify

    let clear r =
      r.count <- 0;
      HashForm.clear r.tbl;
      let _ = declare r pform_true in
      let _ = declare r pform_false in
      ()

    let get reify pf =
      try HashForm.find reify.tbl pf 
      with Not_found -> declare reify pf


    (** Given a coq term, build the corresponding formula *)  
    type coq_cst = 
      | CCtrue
      | CCfalse
      | CCnot
      | CCand
      | CCor
      | CCxor
      | CCimp
      | CCiff
      | CCifb
      | CCunknown

    let op_tbl () =
      let tbl = Hashtbl.create 29 in
      let add (c1,c2) = Hashtbl.add tbl (Lazy.force c1) c2 in
      List.iter add 
	[
	 ctrue,CCtrue; cfalse,CCfalse;
	 candb,CCand; corb,CCor; cxorb,CCxor; cimplb,CCimp; cnegb,CCnot;
         ceqb,CCiff; cifb,CCifb ];
      tbl

    let op_tbl = lazy (op_tbl ())

    let empty_args = [||]

    let of_coq atom_of_coq reify c =
      let op_tbl = Lazy.force op_tbl in
      let get_cst c = 
	try Hashtbl.find op_tbl c with Not_found -> CCunknown in
      let rec mk_hform h =
	let c, args = Term.decompose_app h in
	match get_cst c with
	| CCtrue  -> get reify (Fapp(Ftrue,empty_args))
	| CCfalse -> get reify (Fapp(Ffalse,empty_args))
	| CCnot -> mk_fnot 1 args
	| CCand -> mk_fand [] args
	| CCor  -> mk_for [] args
	| CCxor -> op2 (fun l -> Fapp(Fxor,l)) args
	| CCiff -> op2 (fun l -> Fapp(Fiff,l)) args
	| CCimp ->
          (match args with
            | [b1;b2] ->
              let l1 = mk_hform b1 in
              let l2 = mk_hform b2 in
              get reify (Fapp (Fimp, [|l1;l2|]))
            | _ -> error "SmtForm.Form.of_coq: wrong number of arguments for implb")
	| CCifb ->
	    (* We should also be able to syntaxify if then else *)
	    begin match args with
	    | [b1;b2;b3] ->
		let l1 = mk_hform b1 in
		let l2 = mk_hform b2 in
		let l3 = mk_hform b3 in
		get reify (Fapp(Fite, [|l1;l2;l3|]))
	    | _ -> error "SmtForm.Form.of_coq: wrong number of arguments for ifb"
	    end
	| _ -> 
	    let a = atom_of_coq  h in
            get reify (Fatom a)

      and op2 f args =
	match args with
	| [b1;b2] ->
	    let l1 = mk_hform b1 in
            let l2 = mk_hform b2 in
            get reify (f [|l1; l2|])
	| _ ->  error "SmtForm.Form.of_coq: wrong number of arguments"
	  
      and mk_fnot i args =
	match args with
	| [t] -> 
	    let c,args = Term.decompose_app t in
	    if c = Lazy.force cnegb then
              mk_fnot (i+1) args
	    else 
              let q,r = i lsr 1 , i land 1 in
              let l = mk_hform t in
              let l = if r = 0 then l else neg l in
	      if q = 0 then l
	      else get reify (Fapp(Fnot2 q, [|l|]))
	| _ -> error "SmtForm.Form.mk_hform: wrong number of arguments for negb"
	  
      and mk_fand acc args = 
	match args with
	| [t1;t2] -> 
	    let l2 = mk_hform t2 in
	    let c, args = Term.decompose_app t1 in
	    if c = Lazy.force candb then
              mk_fand (l2::acc) args
	    else 
	      let l1 = mk_hform t1 in
	      get reify (Fapp(Fand, Array.of_list  (l1::l2::acc)))
	| _ -> error "SmtForm.Form.mk_hform: wrong number of arguments for andb" 

      and mk_for acc args = 
	match args with
	| [t1;t2] -> 
	    let l2 = mk_hform t2 in
	    let c, args = Term.decompose_app t1 in
	    if c = Lazy.force corb then
              mk_for (l2::acc) args
	    else 
	      let l1 = mk_hform t1 in
	      get reify (Fapp(For, Array.of_list (l1::l2::acc)))
	| _ -> error "SmtForm.Form.mk_hform: wrong number of arguments for orb" in

      let l = mk_hform c in
      l

    (** Flattening of Fand and For, removing of Fnot2 *)
    let set_sign f f' =
      if is_pos f then f' else neg f'

    let rec flatten reify f = 
      match pform f with
      | Fatom _ -> f
      | Fapp(Fnot2 _,args) -> set_sign f (flatten reify args.(0))
      | Fapp(Fand, args) -> set_sign f (flatten_and reify [] (Array.to_list args))
      | Fapp(For,args) -> set_sign f (flatten_or reify [] (Array.to_list args))
      | Fapp(op,args) ->
          (* TODO change Fimp into For ? *)
	  set_sign f (get reify (Fapp(op, Array.map (flatten reify) args)))

    and flatten_and reify acc args =
      match args with
      | [] -> get reify (Fapp(Fand, Array.of_list (List.rev acc)))
      | a::args ->
	  (* TODO change (not For) and (not Fimp) into Fand *)
	  match pform a with
	  | Fapp(Fand, args') when is_pos a ->
	      let args = Array.fold_right (fun a args -> a::args) args' args in
	      flatten_and reify acc args
	  | _ -> flatten_and reify (flatten reify a :: acc) args

    and flatten_or reify acc args =
      (* TODO change Fimp and (not Fand) into For *)
      match args with
      | [] -> get reify (Fapp(For, Array.of_list (List.rev acc)))
      | a::args ->
	  match pform a with
	  | Fapp(For, args') when is_pos a ->
	      let args = Array.fold_right (fun a args -> a::args) args' args in
	      flatten_or reify acc args
	  | _ -> flatten_or reify (flatten reify a :: acc) args

    (** Producing Coq terms *) 

    let to_coq hf = mkInt (to_lit hf)

    let args_to_coq args =
      let cargs = Array.make (Array.length args + 1) (mkInt 0) in
      Array.iteri (fun i hf -> cargs.(i) <- to_coq hf) args;
      Term.mkArray (Lazy.force cint, cargs)
	
    let pf_to_coq = function
      | Fatom a -> mklApp cFatom [|mkInt (Atom.index a)|]	
      | Fapp(op,args) ->
        match op with
	| Ftrue -> Lazy.force cFtrue
	| Ffalse -> Lazy.force cFfalse
	| Fand -> mklApp cFand [| args_to_coq args|]
	| For  -> mklApp cFor [| args_to_coq args|]
	| Fimp -> mklApp cFimp [| args_to_coq args|]
	| Fxor -> mklApp cFxor (Array.map to_coq args)
	| Fiff -> mklApp cFiff (Array.map to_coq args)
	| Fite -> mklApp cFite (Array.map to_coq args)
	| Fnot2 i -> mklApp cFnot2 [|mkInt i; to_coq args.(0)|]

    let pform_tbl reify =
      let t = Array.make reify.count pform_true in
      let set _ h =
	match h with
	| Pos hp -> t.(hp.index) <- hp.hval
	| _ -> assert false in
      HashForm.iter set reify.tbl;
      t

    let to_array reify dft f =
      let t = Array.make (reify.count + 1) dft in
      let set _ h =
	match h with
	| Pos hp -> t.(hp.index) <- f hp.hval
	| _ -> assert false in
      HashForm.iter set reify.tbl;
      (reify.count, t)

    let interp_tbl reify =
      let (i,t) = to_array reify (Lazy.force cFtrue) pf_to_coq in
      (mkInt i, Term.mkArray (Lazy.force cform, t))

    let nvars reify = reify.count
    (** Producing a Coq term corresponding to the interpretation of a formula *)
    (** [interp_atom] map [Atom.t] to coq term, it is better if it produce
	shared terms. *)
    let interp_to_coq interp_atom form_tbl f =
      let rec interp_form f = 
	let l = to_lit f in
	try Hashtbl.find form_tbl l 
	with Not_found ->
	  if is_neg f then 
	    let pc = interp_form (neg f) in
	    let nc = mklApp cnegb [|pc|] in
	    Hashtbl.add form_tbl l nc;
	    nc
	  else
	    let pc = 
	      match pform f with
	      | Fatom a -> interp_atom a
	      | Fapp(op, args) ->
		  match op with
		  | Ftrue -> Lazy.force ctrue
		  | Ffalse -> Lazy.force cfalse
		  | Fand -> interp_args candb args
		  | For -> interp_args corb args
		  | Fxor -> interp_args cxorb args
		  | Fimp -> 
		      let r = ref (interp_form args.(Array.length args - 1)) in
		      for i = Array.length args - 2 downto 0 do
			r := mklApp cimplb [|interp_form args.(i); !r|]
		      done;
		      !r
		  | Fiff -> interp_args ceqb args
		  | Fite -> 
		      (* TODO with if here *)
		      mklApp cifb (Array.map interp_form args)
		  | Fnot2 n -> 
		      let r = ref (interp_form args.(0)) in
		      for i = 1 to n do	r := mklApp cnegb [|!r|] done;
		      !r in 
	    Hashtbl.add form_tbl l pc;
	    pc
      and interp_args op args =
	let r = ref (interp_form args.(0)) in
	for i = 1 to Array.length args - 1 do
	  r := mklApp op [|!r;interp_form args.(i)|] 
	done;
	!r in
      interp_form f

  end