Common — library colibrilib.pbdd — module PBDD
248
module PBDD : PBDD_intf

Implemented

249
use ref.Ref
250
use mach.int.Int63
251
use list.List
252
use list.Mem
253
use list.Distinct
254
use colibrilib.bdd.Key
255
use int.Int
256
use int.MinMax
257
use set.Set
258
use bool.Bool
259
use colibrilib.sbdd.SBDD
260
use colibrilib.sbdd.SBDDShift
261
use colibrilib.bdd.IArray63
262
use seq.Seq
263
use mach.array.Array63
264
use colibrilib.sbdd.SNode
265
use colibrilib.zarith.Zbit
266
267
function
to_indexes
(id:int) : SBDD.indexes = (fun (i:int63) -> Zbit.bittest id (to_int i))
268
Valid (107ms) (cvc4)
269
lemma
to_indexes_lor
: forall a b. to_indexes (Zbit.lor a b) = Set.union (to_indexes a) (to_indexes b)
270
Valid (92ms) (cvc4)
271
let lemma
to_indexes_lsl_1
(i:int63) : unit
272
requires { 0 <= to_int i }
273
ensures { to_indexes (Zbit.lsl 1 (to_int i)) = Set.singleton i }
274
=
275
assert { forall j. 0 <= to_int j ->
276
Zbit.bittest (Zbit.asr 1 (0 - to_int i)) (to_int j)
277
= Zbit.bittest 1 (to_int j + (0 - to_int i)) }
278
Valid (698ms) (cvc4)
279
let lemma
to_indexes_change
(id:int) (i:int63) (v:bool) : unit
280
requires { 0 <= to_int i }
281
ensures { to_indexes (Zbit.change id (to_int i) v) = Map.set (to_indexes id) i v }
282
=
283
assert { forall j. 0 <= to_int j ->
284
Zbit.bittest (Zbit.change id (to_int i) v) (to_int j)
285
= (if j = i then v else to_indexes id j) };
286
assert { forall j. to_indexes (Zbit.change id (to_int i) v) j
287
= Map.set (to_indexes id) i v j }
288
289
Valid (92ms) (colibri2 2) (cvc4) (cvc5) (split_vc) (depth 1)
290
let lemma
numbits_bound_from_indexes
(r wit:int) : ()
291
requires { 0 <= r }
292
requires { 0 <= wit }
293
requires { numbits wit <= Int63.max_int + 1 }
294
requires { forall i. Int63.max_int < i -> not (bittest r i) }
295
requires { Set.subset (to_indexes r) (to_indexes wit) }
296
ensures { numbits r <= numbits wit }
297
=
298
for i=0 to Int63.max_int do
299
invariant { forall j. 0 <= j < i -> Zbit.bittest r j -> Zbit.bittest wit j }
300
()
301
done
302
Valid (2.3s) (colibri2 15) (cvc5 5) (split_vc 4) (depth 4)
303
let rec ghost function
from_indexes
(s:SBDD.indexes) (wit:int) : int
304
requires { 0 <= wit }
305
requires { numbits wit <= Int63.max_int + 1 }
306
requires { Set.subset s (to_indexes wit) }
307
ensures { (to_indexes result) = s }
308
ensures { numbits result <= numbits wit }
309
ensures { 0 <= result }
310
=
311
let rec aux (k:int63) : int
312
requires { 0 <= k }
313
ensures { 0 <= result }
314
ensures { forall i. to_int k < i -> not (bittest result i) }
315
ensures { forall j:int63. j <= k ->
316
((to_indexes result) j <-> s j) }
317
ensures { forall j:int63. j <= k ->
318
(to_indexes result) j -> (to_indexes wit) j }
319
variant { k }
320
= if k = 0 then (if s 0 then 1 else 0)
321
else
322
let prev = aux (k - 1) in
323
change_nonneg prev (to_int k) (s k);
324
Zbit.change prev (to_int k) (s k)
325
in
326
let r = aux Int63.max_int in
327
numbits_bound_from_indexes r wit;
328
r
329
Valid (284ms) (colibri2 3) (cvc5) (split_vc) (depth 1)
330
let lemma
to_indexes_subset
(a:int) (b:int) : ()
331
requires { 0 <= a }
332
requires { Zbit.numbits a <= Int63.max_int + 1 }
333
requires { Set.subset (to_indexes a) (to_indexes b) }
334
ensures { Zbit.subset a b }
335
=
336
for i=0 to Int63.max_int do
337
invariant { forall j. 0 <= j < i -> Zbit.bittest a j -> Zbit.bittest b j }
338
()
339
done
340
Valid (60ms) (colibri2)
341
type
t
= {
342
b
: SBDD.t;
343
ghost
indexes
: int;
344
} invariant { to_indexes indexes = b.SBDD.dom_indexes }
345
invariant { Zbit.numbits indexes <= Int63.max_int + 1 }
346
invariant { 0 <= indexes }
347
by { b = SBDD.tfalse (); indexes = 0 }
348
349
type
indexes
= int
350
type
snodes
= Set.set snode
351
352
function
dom_indexes
(x:t) : indexes = x.indexes
353
354
function
dom_snodes
(x:t) : snodes = x.b.SBDD.dom_snodes
355
function
v
(x:t) : indexes -> snodes -> bool = (fun id sn -> x.b.SBDD.v (to_indexes id) sn)
356
Valid (111ms) (cvc4)
357
let lemma
support_v
(x:t) (id1 id2:indexes) (sn:snodes) : unit
358
requires { forall i. 0 <= i -> Zbit.bittest x.dom_indexes i -> (Zbit.bittest id1 i <-> Zbit.bittest id2 i) }
359
ensures { x.v id1 sn = x.v id2 sn }
360
=
361
SBDD.support_v x.b (to_indexes id1) (to_indexes id2) sn sn
362
Valid (200ms) (cvc4)
363
let
dand
(x y: t) : t
364
ensures { result.dom_indexes = Zbit.lor x.dom_indexes y.dom_indexes }
365
ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
366
ensures { result.v = (fun id sn -> andb (x.v id sn) (y.v id sn)) } =
367
{ b = SBDD.dand x.b y.b; indexes = Zbit.lor x.indexes y.indexes }
368
Valid (202ms) (cvc4)
369
let
dor
(x y: t) : t
370
ensures { result.dom_indexes = Zbit.lor x.dom_indexes y.dom_indexes }
371
ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
372
ensures { result.v = (fun id sn -> orb (x.v id sn) (y.v id sn)) } =
373
{ b = SBDD.dor x.b y.b; indexes = Zbit.lor x.indexes y.indexes }
374
Valid (796ms) (cvc4)
375
let
dxor
(x y: t) : t
376
ensures { result.dom_indexes = Zbit.lor x.dom_indexes y.dom_indexes }
377
ensures { result.dom_snodes = Set.union x.dom_snodes y.dom_snodes }
378
ensures { result.v = (fun id sn -> xorb (x.v id sn) (y.v id sn)) } =
379
{ b = SBDD.dxor x.b y.b; indexes = Zbit.lor x.indexes y.indexes }
380
Valid (379ms) (colibri2 5) (cvc4) (split_vc) (depth 1)
381
let
tfalse
() : t
382
ensures { result.dom_indexes = 0 }
383
ensures { result.dom_snodes = Set.empty }
384
ensures { result.v = (fun _ _ -> False) } =
385
{ b = SBDD.tfalse (); indexes = 0 }
386
Valid (158ms) (colibri2 6) (split_vc) (depth 1)
387
let
ttrue
() : t
388
ensures { result.dom_indexes = 0 }
389
ensures { result.dom_snodes = Set.empty }
390
ensures { result.v = (fun _ _ -> True) } =
391
{ b = SBDD.ttrue (); indexes = 0 }
392
Valid (655ms) (cvc4)
393
let
dnot
(a: t) : t
394
ensures { result.dom_indexes = a.dom_indexes }
395
ensures { result.dom_snodes = a.dom_snodes }
396
ensures { result.v = (fun id sn -> notb (a.v id sn)) } =
397
{ b = SBDD.dnot a.b; indexes = a.indexes }
398
Valid (999ms) (cvc4)
399
let
is_equal
(x y: t) : (result: bool, ghost wid: indexes, ghost wsn: snodes)
400
ensures { result = (forall id sn. x.v id sn = y.v id sn) }
401
ensures { not result ->
402
0 <= wid /\ numbits wid <= numbits (Zbit.lor x.dom_indexes y.dom_indexes) /\
403
(Zbit.subset wid (Zbit.lor x.dom_indexes y.dom_indexes)) /\
404
(Set.subset wsn (Set.union x.dom_snodes y.dom_snodes)) /\
405
x.v wid wsn <> y.v wid wsn } =
406
let (r, ghost sid, ghost ssn) = SBDD.is_equal x.b y.b in
407
if r then (r,0,Set.empty) else
408
begin
409
lor_numbits x.dom_indexes y.dom_indexes;
410
assert { numbits (Zbit.lor x.dom_indexes y.dom_indexes)
411
= max (numbits x.dom_indexes) (numbits y.dom_indexes) };
412
let ghost id1 = from_indexes sid (Zbit.lor x.dom_indexes y.dom_indexes) in
413
let ghost sn1 = ssn in
414
to_indexes_subset id1 (Zbit.lor x.dom_indexes y.dom_indexes);
415
(r, id1, sn1)
416
end
417
Valid (105ms) (cvc4)
418
let
is_inter_empty
(x y: t) : (result: bool, ghost wid: indexes, ghost wsn: snodes)
419
ensures { result = (forall id sn. not (x.v id sn /\ y.v id sn)) }
420
ensures { not result ->
421
0 <= wid /\ numbits wid <= numbits (Zbit.lor x.dom_indexes y.dom_indexes) /\
422
(Zbit.subset wid (Zbit.lor x.dom_indexes y.dom_indexes)) /\
423
(Set.subset wsn (Set.union x.dom_snodes y.dom_snodes)) /\
424
x.v wid wsn /\ y.v wid wsn } =
425
let (r, ghost sid, ghost ssn) = SBDD.is_inter_empty x.b y.b in
426
if r then (r,0,Set.empty) else begin
427
lor_numbits x.dom_indexes y.dom_indexes;
428
assert { numbits (Zbit.lor x.dom_indexes y.dom_indexes)
429
= max (numbits x.dom_indexes) (numbits y.dom_indexes) };
430
let ghost id1 = from_indexes sid (Zbit.lor x.dom_indexes y.dom_indexes) in
431
let ghost sn1 = ssn in
432
to_indexes_subset id1 (Zbit.lor x.dom_indexes y.dom_indexes);
433
(r, id1, sn1)
434
end
435
Valid (108ms) (cvc4)
436
let partial
bdd_of_index
(i: int63) : t
437
requires { 0 <= to_int i }
438
ensures { result.dom_indexes = Zbit.lsl 1 (to_int i) }
439
ensures { result.dom_snodes = Set.empty }
440
ensures { result.v = (fun id _ -> Zbit.bittest id (to_int i)) } =
441
to_indexes_lsl_1 i;
442
{ b = SBDD.bdd_of_index i; indexes = Zbit.lsl 1 (to_int i) }
443
Valid (392ms) (colibri2 5) (cvc4) (split_vc) (depth 1)
444
let partial
bdd_of_snode
(v: snode) : t
445
ensures { result.dom_indexes = 0 }
446
ensures { result.dom_snodes = Set.singleton v }
447
ensures { result.v = (fun _ sn -> sn v) } =
448
{ b = SBDD.bdd_of_snode v; indexes = 0 }
449
Valid (412ms) (colibri2 5) (cvc4) (split_vc) (depth 1)
450
let partial
bdd_not_snode
(v: snode) : t
451
ensures { result.dom_indexes = 0 }
452
ensures { result.dom_snodes = Set.singleton v }
453
ensures { result.v = (fun _ sn -> not (sn v)) } =
454
{ b = SBDD.bdd_not_snode v; indexes = 0 }
455
Valid (1.6s) (colibri2 8) (cvc4 3) (split_vc) (depth 1)
456
let partial
ite_index
(i: int63) (aa bb: t) : t
457
requires { 0 <= to_int i }
458
ensures { result.dom_indexes = Zbit.set (Zbit.lor aa.dom_indexes bb.dom_indexes) i }
459
ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }
460
ensures { result.v = (fun id sn -> if Zbit.bittest id (to_int i) then aa.v id sn else bb.v id sn) } =
461
let ghost l = Zbit.lor aa.indexes bb.indexes in
462
lor_numbits aa.indexes bb.indexes;
463
numbits_set l (to_int i);
464
assert { forall j:int63. to_indexes (Zbit.set l (to_int i)) j
465
= Set.add i (Set.union aa.b.SBDD.dom_indexes bb.b.SBDD.dom_indexes) j };
466
{ b = SBDD.ite_index i aa.b bb.b; indexes = Zbit.set l (to_int i) }
467
Valid (1.4s) (colibri2 10) (cvc4 2) (split_vc) (depth 1)
468
let ghost
ite_index_g
(i: int63) (aa bb: t) : t
469
requires { 0 <= to_int i < 3 }
470
ensures { result.dom_indexes = Zbit.set (Zbit.lor aa.dom_indexes bb.dom_indexes) i }
471
ensures { result.dom_snodes = Set.union aa.dom_snodes bb.dom_snodes }
472
ensures { result.v = (fun id sn -> if Zbit.bittest id (to_int i) then aa.v id sn else bb.v id sn) } =
473
let l = Zbit.lor aa.indexes bb.indexes in
474
lor_numbits aa.indexes bb.indexes;
475
numbits_set l (to_int i);
476
assert { forall j:int63. to_indexes (Zbit.set l (to_int i)) j
477
= Set.add i (Set.union aa.b.SBDD.dom_indexes bb.b.SBDD.dom_indexes) j };
478
{ b = SBDD.ite_index_g i aa.b bb.b; indexes = Zbit.set l (to_int i) }
479
Valid (1.2s) (cvc4)
480
let partial
ite_snode
(v: snode) (aa bb: t) : t
481
ensures { result.dom_indexes = (Zbit.lor aa.dom_indexes bb.dom_indexes) }
482
ensures { result.dom_snodes = Set.add v (Set.union aa.dom_snodes bb.dom_snodes) }
483
ensures { result.v = (fun id sn -> if sn v then aa.v id sn else bb.v id sn) } =
484
{ b = SBDD.ite_snode v aa.b bb.b; indexes = Zbit.lor aa.indexes bb.indexes }
485
486
function
nb_nodes
(a:t) : int = SBDD.nb_nodes a.b
487
488
function
support_snodes
(a:t) : snodes = SBDD.support_snodes a.b
489
Valid (33ms) (colibri2)
490
let lemma
support_snodes_dom
(x:t) : unit
491
ensures { Set.subset (support_snodes x) x.dom_snodes }
492
= SBDD.support_dom x.b
493
Valid (93ms) (cvc4)
494
let lemma
support_snodes_dep
(x:t) (nd: snode) : unit
495
requires { Set.mem nd (support_snodes x) }
496
ensures { exists id sn. x.v id (Set.add nd sn) <> x.v id (Set.remove nd sn) }
497
=
498
let ghost (sid, sn) = SBDD.support_snodes_dep x.b nd in
499
SBDD.support_dom x.b;
500
let ghost id = from_indexes (Set.inter sid x.b.SBDD.dom_indexes) x.indexes in
501
SBDD.support_exact x.b (to_indexes id) sid (Set.add nd sn) (Set.add nd sn);
502
SBDD.support_exact x.b (to_indexes id) sid (Set.remove nd sn) (Set.remove nd sn);
503
assert { x.v id (Set.add nd sn) <> x.v id (Set.remove nd sn) }
504
Valid (43ms) (colibri2)
505
let lemma
support_snodes_v
(x:t) (id:indexes) (sn1 sn2:snodes) : unit
506
requires { forall nd. Set.mem nd (support_snodes x) -> sn1 nd = sn2 nd }
507
ensures { x.v id sn1 = x.v id sn2 }
508
=
509
SBDD.support_exact x.b (to_indexes id) (to_indexes id) sn1 sn2
510
Valid (36ms) (colibri2)
511
let
vars
(a:t) : list Key.t
512
ensures { forall n s ab. Mem.mem (Key.Var n s ab) result <-> Set.mem { n = n; s = s; scal = ab } (support_snodes a) }
513
ensures { Distinct.distinct result }
514
= SBDD.vars a.b
515
Valid (46ms) (colibri2)
516
let lemma
numbits_le_bits
(x w: int) : unit
517
requires { 0 <= x /\ 0 <= w }
518
requires { forall i. 0 <= i -> bittest x i -> i < w }
519
ensures { numbits x <= w }
520
= if x > 0 then numbits_top_bit x
521
522
function
subst_bits
(subst: IArray63.t t) (id: indexes) (sn: snodes) : int -> bool =
523
fun i -> (subst i).v id sn
524
Valid (3.3s) (colibri2 44) (cvc4 19) (split_vc 3) (depth 2)
525
let partial
compose_shift
(subst: IArray63.t t) (off: int63) (x: t) : t
526
requires { numbits x.dom_indexes <= subst.IArray63.length }
527
ensures { forall nd. Set.mem nd (support_snodes x) -> nd.scal \/ in_bounds (to_int nd.s - to_int off) }
528
raises { Overflow -> exists nd. Set.mem nd (support_snodes x) /\ not nd.scal /\ not (in_bounds (to_int nd.s - to_int off)) }
529
ensures { (forall j. 0 <= j < subst.IArray63.length ->
530
numbits (subst j).dom_indexes <= subst.IArray63.length) ->
531
numbits result.dom_indexes <= subst.IArray63.length }
532
ensures { forall id sn. result.v id sn =
533
x.v (of_bits (subst_bits subst id sn) subst.IArray63.length)
534
(shifted sn (to_int off)) }
535
ensures { forall nd''. Set.mem nd'' (support_snodes result) ->
536
(exists j. 0 <= j < subst.IArray63.length /\ Set.mem nd'' (support_snodes (subst j))) \/
537
(exists nd. Set.mem nd (support_snodes x) /\ nd'' = shift_snode nd (to_int off)) }
538
=
539
let n = subst.IArray63.length in
540
let a = Array63.make n (SBDD.tfalse ()) in
541
for j = 0 to n - 1 do
542
invariant { forall k. 0 <= k < j -> Seq.get a.Array63.elts k = (subst k).b }
543
a[j] <- (IArray63.get subst j).b
544
done;
545
let sa = IArray63.of_array a in
546
assert { forall k. 0 <= k < n -> sa k = (subst k).b };
547
let lemma supp (i: int63) : unit
548
requires { Set.mem i (SBDD.support_indexes x.b) }
549
ensures { 0 <= i < n }
550
=
551
assert { Set.mem i x.b.SBDD.dom_indexes };
552
assert { Zbit.bittest x.indexes (to_int i) };
553
if x.indexes > 0 && to_int i >= Zbit.numbits x.indexes then numbits_high_clear x.indexes (to_int i)
554
in
555
assert { forall i. Set.mem i (SBDD.support_indexes x.b) -> 0 <= i < n };
556
let r = SBDDShift.compose_shift sa off x.b in
557
let ghost wit = pure { of_bits (fun i -> bittest x.indexes i \/
558
exists k. 0 <= k < n /\ bittest (subst k).indexes i)
559
(Int63.max_int + 1) } in
560
numbits_le_bits wit pure { Int63.max_int + 1 };
561
let lemma sub (i: int63) : unit
562
requires { Set.mem i r.SBDD.dom_indexes }
563
ensures { to_indexes wit i }
564
=
565
if Set.mem i x.b.SBDD.dom_indexes then assert { bittest x.indexes i }
566
else assert { exists k. 0 <= k < n /\ bittest (subst k).indexes i }
567
in
568
let res = { b = r; indexes = from_indexes r.SBDD.dom_indexes wit } in
569
let lemma dom (_:unit) : unit
570
requires { forall j. 0 <= j < n -> numbits (subst j).dom_indexes <= n }
571
ensures { numbits res.dom_indexes <= n }
572
=
573
let ghost w = to_int n in
574
let lemma bit (i: int) : unit
575
requires { 0 <= i }
576
requires { bittest res.indexes i }
577
ensures { i < w }
578
=
579
if i >= w then begin
580
numbits_high_clear x.indexes i;
581
assert { forall k. 0 <= k < n -> not (bittest (subst k).indexes i) };
582
assert { not (bittest wit i) };
583
if pure { i > Int63.max_int } then begin
584
if res.indexes > 0 then numbits_high_clear res.indexes i
585
end else begin
586
let j = Int63.of_int i in
587
assert { to_indexes res.indexes j -> to_indexes wit j }
588
end
589
end
590
in
591
numbits_le_bits res.indexes w
592
in
593
let lemma value (id: indexes) (sn: snodes) : unit
594
ensures { res.v id sn =
595
x.v (of_bits (subst_bits subst id sn) n)
596
(shifted sn (to_int off)) }
597
=
598
SBDD.support_v x.b
599
pure { fun (i:int63) -> if 0 <= i < n then (sa i).SBDD.v (to_indexes id) sn else to_indexes id i }
600
pure { to_indexes (of_bits (subst_bits subst id sn) n) }
601
pure { shifted sn (to_int off) }
602
pure { shifted sn (to_int off) }
603
in
604
(* the snodes of the support of the result *)
605
let lemma img (nd'': snode) : unit
606
requires { Set.mem nd'' (support_snodes res) }
607
ensures { (exists j. 0 <= j < n /\ Set.mem nd'' (support_snodes (subst j))) \/
608
(exists nd. Set.mem nd (support_snodes x) /\ nd'' = shift_snode nd (to_int off)) }
609
=
610
support_snodes_dep res nd'';
611
let ghost (id, sn) = any (indexes, snodes)
612
ensures { let (id, sn) = result in res.v id (Set.add nd'' sn) <> res.v id (Set.remove nd'' sn) } in
613
let ghost sn1 = Set.add nd'' sn in
614
let ghost sn2 = Set.remove nd'' sn in
615
if pure { not (exists j. 0 <= j < n /\ Set.mem nd'' (support_snodes (subst j))) /\
616
not (exists nd. Set.mem nd (support_snodes x) /\ nd'' = shift_snode nd (to_int off)) } then begin
617
let lemma sj (j: int) : unit
618
requires { 0 <= j < n }
619
ensures { (subst j).v id sn1 = (subst j).v id sn2 }
620
= support_snodes_v pure { subst j } id sn1 sn2
621
in
622
let lemma same_id (_: unit) : unit
623
ensures { of_bits (subst_bits subst id sn1) n = of_bits (subst_bits subst id sn2) n }
624
= let lemma bt (i: int) : unit
625
requires { 0 <= i }
626
ensures { bittest (of_bits (subst_bits subst id sn1) n) i <-> bittest (of_bits (subst_bits subst id sn2) n) i }
627
= if i < to_int n then assert { (subst i).v id sn1 = (subst i).v id sn2 }
628
in
629
ext_bittest pure { of_bits (subst_bits subst id sn1) n } pure { of_bits (subst_bits subst id sn2) n }
630
in same_id ();
631
let lemma sx (nd: snode) : unit
632
requires { Set.mem nd (support_snodes x) }
633
ensures { sn1 (shift_snode nd (to_int off)) = sn2 (shift_snode nd (to_int off)) }
634
= assert { shift_snode nd (to_int off) <> nd'' }
635
in
636
let ghost g1 = pure { shifted sn1 (to_int off) } in
637
let ghost g2 = pure { shifted sn2 (to_int off) } in
638
let ghost ids = pure { of_bits (subst_bits subst id sn1) n } in
639
support_snodes_v x ids g1 g2;
640
value id sn1; value id sn2;
641
assert { res.v id sn1 = x.v ids g1 };
642
assert { res.v id sn2 = x.v (of_bits (subst_bits subst id sn2) n) g2 };
643
assert { ids = of_bits (subst_bits subst id sn2) n };
644
assert { res.v id sn1 = res.v id sn2 }
645
end
646
in
647
res
648
Valid (1.3s) (colibri2)
649
let partial
cofactors_snode
(nd: snode) (a: t) : (t, t)
650
returns { (p, n) ->
651
p.dom_indexes = a.dom_indexes /\
652
n.dom_indexes = a.dom_indexes /\
653
p.dom_snodes = Set.remove nd a.dom_snodes /\
654
n.dom_snodes = Set.remove nd a.dom_snodes /\
655
p.v = (fun id sn -> a.v id (Set.add nd sn)) /\
656
n.v = (fun id sn -> a.v id (Set.remove nd sn)) }
657
=
658
let (p, n) = SBDD.cofactors_snode nd a.b in
659
({ b = p; indexes = a.indexes }, { b = n; indexes = a.indexes })

The cube of the snodes of l

    Valid (1.1s) (colibri2)
662
let rec partial
snodes_cube
(l: list Key.t) : SBDD.t
663
variant { l }
664
ensures { SBDD.is_support result }
665
ensures { SBDD.support_indexes result = Set.empty }
666
ensures { forall nd. Set.mem nd (SBDD.support_snodes result) <-> Mem.mem (Key.Var nd.n nd.s nd.scal) l }
667
= match l with
668
| Nil -> SBDD.cube_true ()
669
| Cons (Key.Var n s a) l' -> SBDD.support_union (SBDD.cube_snode { n = n; s = s; scal = a }) (snodes_cube l')
670
| Cons (Key.Index _) l' -> snodes_cube l'
671
end
672
Valid (391ms) (cvc4)
673
let lemma
no_snode
(x: t) : unit
674
requires { forall id sn sn'. x.v id sn = x.v id sn' }
675
ensures { support_snodes x = Set.empty }
676
=
677
let lemma none (nd: snode) : unit
678
ensures { not (Set.mem nd (support_snodes x)) }
679
= if pure { Set.mem nd (support_snodes x) } then support_snodes_dep x nd
680
in
681
assert { (support_snodes x) = Set.empty }
682
Valid (667ms) (colibri2 15) (cvc4 6) (split_vc) (depth 1)
683
let partial
exist_snodes
(x: t) : t
684
ensures { result.dom_indexes = x.dom_indexes }
685
ensures { support_snodes result = Set.empty }
686
ensures { forall id sn. result.v id sn <-> exists sn'. x.v id sn' }
687
=
688
let c = snodes_cube (vars x) in
689
let r = SBDD.dexist c x.b in
690
let lemma memc (nd: snode) : unit
691
ensures { Set.mem nd (SBDD.support_snodes c) <-> Set.mem nd (SBDD.support_snodes x.b) }
692
= assert { nd = { n = nd.n; s = nd.s; scal = nd.scal } }
693
in
694
assert { forall nd. (SBDD.support_snodes c) nd = (SBDD.support_snodes x.b) nd };
695
assert { (SBDD.support_snodes c) = (SBDD.support_snodes x.b) };
696
assert { r.SBDD.dom_indexes = x.b.SBDD.dom_indexes };
697
let res = { b = r; indexes = x.indexes } in
698
let lemma value (id: indexes) (sn: snodes) : unit
699
ensures { res.v id sn <-> exists sn'. x.v id sn' }
700
=
701
let ghost sid = to_indexes id in
702
assert { res.v id sn <-> exists id' sn'. x.b.SBDD.v (SBDD.update_id sid (SBDD.support_indexes c) id')
703
(SBDD.update_sn sn (SBDD.support_snodes c) sn') };
704
assert { forall id'. SBDD.update_id sid (SBDD.support_indexes c) id' = sid };
705
let lemma upd (sn': snodes) : unit
706
ensures { x.b.SBDD.v sid (SBDD.update_sn sn (SBDD.support_snodes c) sn') = x.v id sn' }
707
= SBDD.support_exact x.b sid sid (SBDD.update_sn sn (SBDD.support_snodes x.b) sn') sn'
708
in
709
if pure { exists sn'. x.v id sn' } then begin
710
let ghost w = any snodes ensures { x.v id result } in
711
upd w;
712
assert { x.b.SBDD.v (SBDD.update_id sid (SBDD.support_indexes c) sid) (SBDD.update_sn sn (SBDD.support_snodes c) w) }
713
end
714
in
715
no_snode res;
716
res
717
Valid (548ms) (colibri2 31) (cvc4 4) (cvc5 4) (split_vc) (depth 1)
718
let partial
get_pos
(a: t) (pos s: int63) : t
719
requires { 0 <= s /\ numbits a.dom_indexes <= s }
720
requires { 0 <= pos /\ numbits pos <= s }
721
ensures { result.dom_indexes = 0 }
722
ensures { Set.subset result.dom_snodes a.dom_snodes }
723
ensures { forall id sn. result.v id sn <-> a.v pos sn }
724
=
725
let c = ref (SBDD.cube_true ()) in
726
SBDD.cube_empty_good !c;
727
for i = 0 to s - 1 do
728
invariant { SBDD.good_cube !c }
729
invariant { forall j: int63. Set.mem j (SBDD.support_indexes !c) <-> 0 <= j < i }
730
invariant { SBDD.support_snodes !c = Set.empty }
731
invariant { forall j: int63. Set.mem j (SBDD.get_cube_indexes !c) <-> (0 <= j < i /\ bittest pos j) }
732
invariant { SBDD.get_cube_snodes !c = Set.empty }
733
invariant { (!c).SBDD.dom_snodes = Set.empty }
734
let l = SBDD.cube_lit i (Zbit.test_bit (to_int pos) i) in
735
c := SBDD.cube_and !c l
736
done;
737
let ghost cs = SBDD.support_indexes !c in
738
let lemma dom (j: int63) : unit
739
ensures { Set.mem j a.b.SBDD.dom_indexes -> Set.mem j cs }
740
= if Set.mem j a.b.SBDD.dom_indexes && to_int j >= to_int s then
741
numbits_high_clear a.indexes (to_int j)
742
in
743
let r = SBDD.cofactor a.b !c in
744
assert { forall j. not (Set.mem j r.SBDD.dom_indexes) };
745
assert { r.SBDD.dom_indexes = Set.empty };
746
assert { forall j. not (Set.mem j (to_indexes 0)) };
747
assert { to_indexes 0 = Set.empty };
748
let res = { b = r; indexes = 0 } in
749
let lemma value (id: indexes) (sn: snodes) : unit
750
ensures { res.v id sn <-> a.v pos sn }
751
=
752
let ghost u = Set.union (Set.diff (to_indexes id) cs) (SBDD.get_cube_indexes !c) in
753
let ghost w = Set.union (Set.diff sn (SBDD.support_snodes !c)) (SBDD.get_cube_snodes !c) in
754
assert { forall x. Set.mem x w <-> sn x };
755
SBDD.support_dom a.b;
756
SBDD.support_exact a.b u (to_indexes (to_int pos)) w sn
757
in
758
res
759
Valid (578ms) (colibri2 35) (cvc4 5) (split_vc) (depth 1)
760
let partial
exist_window
(x: t) (s: int63) : t
761
requires { 0 <= s /\ numbits x.dom_indexes <= s }
762
ensures { result.dom_indexes = 0 }
763
ensures { Set.subset result.dom_snodes x.dom_snodes }
764
ensures { forall id sn. result.v id sn <-> exists p. 0 <= p /\ numbits p <= s /\ x.v p sn }
765
=
766
let c = ref (SBDD.cube_true ()) in
767
for i = 0 to s - 1 do
768
invariant { SBDD.is_support !c }
769
invariant { forall j: int63. Set.mem j (SBDD.support_indexes !c) <-> 0 <= j < i }
770
invariant { SBDD.support_snodes !c = Set.empty }
771
c := SBDD.support_union !c (SBDD.cube_index i)
772
done;
773
let ghost cs = SBDD.support_indexes !c in
774
let lemma dom (j: int63) : unit
775
ensures { Set.mem j x.b.SBDD.dom_indexes -> Set.mem j cs }
776
= if Set.mem j x.b.SBDD.dom_indexes && to_int j >= to_int s then
777
numbits_high_clear x.indexes (to_int j)
778
in
779
let r = SBDD.dexist !c x.b in
780
assert { forall j. not (Set.mem j r.SBDD.dom_indexes) };
781
assert { r.SBDD.dom_indexes = Set.empty };
782
assert { forall j. not (Set.mem j (to_indexes 0)) };
783
assert { to_indexes 0 = Set.empty };
784
let res = { b = r; indexes = 0 } in
785
let lemma value (id: indexes) (sn: snodes) : unit
786
ensures { res.v id sn <-> exists p. 0 <= p /\ numbits p <= s /\ x.v p sn }
787
=
788
let ghost sid = to_indexes id in
789
assert { forall sn'. SBDD.update_sn sn (SBDD.support_snodes !c) sn' = sn };
790
if pure { exists id' sn'. x.b.SBDD.v (SBDD.update_id sid cs id') (SBDD.update_sn sn (SBDD.support_snodes !c) sn') }
791
then begin
792
let ghost id' = any SBDD.indexes ensures { exists sn'. x.b.SBDD.v (SBDD.update_id sid cs result) (SBDD.update_sn sn (SBDD.support_snodes !c) sn') } in
793
let ghost u = SBDD.update_id sid cs id' in
794
mask_nonneg (to_int s);
795
mask_numbits (to_int s);
796
let ghost p = from_indexes (Set.inter u cs) (mask (to_int s)) in
797
SBDD.support_dom x.b;
798
SBDD.support_exact x.b (to_indexes p) u sn sn;
799
assert { x.v p sn }
800
end else begin
801
let lemma no (p: int) : unit
802
requires { 0 <= p /\ numbits p <= s }
803
ensures { not x.v p sn }
804
=
805
SBDD.support_dom x.b;
806
SBDD.support_exact x.b (SBDD.update_id sid cs (to_indexes p)) (to_indexes p) sn sn;
807
assert { forall sn'. not (x.b.SBDD.v (SBDD.update_id sid cs (to_indexes p))
808
(SBDD.update_sn sn (SBDD.support_snodes !c) sn')) };
809
assert { SBDD.update_sn sn (SBDD.support_snodes !c) sn = sn };
810
assert { not (x.b.SBDD.v (SBDD.update_id sid cs (to_indexes p)) sn) }
811
in ()
812
end
813
in
814
res
815
Valid (824ms) (colibri2 17) (cvc4 4) (split_vc) (depth 1)
816
let partial
forall_snodes
(x: t) : t
817
ensures { result.dom_indexes = x.dom_indexes }
818
ensures { support_snodes result = Set.empty }
819
ensures { forall id sn. result.v id sn <-> forall sn'. x.v id sn' }
820
=
821
let c = snodes_cube (vars x) in
822
let r = SBDD.dforall c x.b in
823
let lemma memc (nd: snode) : unit
824
ensures { Set.mem nd (SBDD.support_snodes c) <-> Set.mem nd (SBDD.support_snodes x.b) }
825
= assert { nd = { n = nd.n; s = nd.s; scal = nd.scal } }
826
in
827
assert { forall nd. (SBDD.support_snodes c) nd = (SBDD.support_snodes x.b) nd };
828
assert { (SBDD.support_snodes c) = (SBDD.support_snodes x.b) };
829
assert { r.SBDD.dom_indexes = x.b.SBDD.dom_indexes };
830
let res = { b = r; indexes = x.indexes } in
831
let lemma value (id: indexes) (sn: snodes) : unit
832
ensures { res.v id sn <-> forall sn'. x.v id sn' }
833
=
834
let ghost sid = to_indexes id in
835
assert { res.v id sn <-> forall id' sn'. x.b.SBDD.v (SBDD.update_id sid (SBDD.support_indexes c) id')
836
(SBDD.update_sn sn (SBDD.support_snodes c) sn') };
837
assert { forall id'. SBDD.update_id sid (SBDD.support_indexes c) id' = sid };
838
let lemma upd (sn': snodes) : unit
839
ensures { x.b.SBDD.v sid (SBDD.update_sn sn (SBDD.support_snodes c) sn') = x.v id sn' }
840
= SBDD.support_exact x.b sid sid (SBDD.update_sn sn (SBDD.support_snodes x.b) sn') sn'
841
in
842
if pure { not (forall sn'. x.v id sn') } then begin
843
let ghost w = any snodes ensures { not (x.v id result) } in
844
upd w;
845
assert { not (x.b.SBDD.v (SBDD.update_id sid (SBDD.support_indexes c) sid) (SBDD.update_sn sn (SBDD.support_snodes c) w)) }
846
end
847
in
848
no_snode res;
849
res
850
851
predicate
mem_key
(nd: snode) (l: list (snode, t)) =
852
match l with Nil -> false | Cons (nd', _) l' -> nd = nd' \/ mem_key nd l' end
853
854
predicate
distinct_keys
(l: list (snode, t)) =
855
match l with Nil -> true | Cons (nd, _) l' -> not (mem_key nd l') /\ distinct_keys l' end
856
857
function
subst_sn
(l: list (snode, t)) (id: indexes) (sn: snodes) : snodes =
858
match l with
859
| Nil -> sn
860
| Cons (nd, f) l' -> Map.set (subst_sn l' id sn) nd (f.v id sn)
861
end
862
Valid (156ms) (colibri2)
863
let rec
conv
(l: list (snode, t)) : list (snode, SBDD.t)
864
variant { l }
865
ensures { forall nd. SBDDShift.mem_key nd result <-> mem_key nd l }
866
ensures { distinct_keys l -> SBDDShift.distinct_keys result }
867
ensures { forall id sn. SBDDShift.subst_sn result (to_indexes id) sn = subst_sn l id sn }
868
ensures { forall nd g. Mem.mem (nd, g) result -> exists f. Mem.mem (nd, f) l /\ g = f.b }
869
= match l with
870
| Nil -> Nil
871
| Cons (nd, f) l' -> Cons (nd, f.b) (conv l')
872
end
873
Valid (527ms) (colibri2 13) (cvc4 4) (split_vc) (depth 1)
874
let partial
compose_snodes
(ghost w: int) (l: list (snode, t)) (x: t) : t
875
requires { distinct_keys l }
876
requires { 0 <= w <= Int63.max_int + 1 /\ numbits x.dom_indexes <= w }
877
requires { forall nd f. Mem.mem (nd, f) l -> numbits f.dom_indexes <= w }
878
ensures { numbits result.dom_indexes <= w }
879
ensures { forall id sn. result.v id sn = x.v id (subst_sn l id sn) }
880
=
881
let cl = conv l in
882
let r = SBDDShift.compose_snodes cl x.b in
883
let ghost wit = mask w in
884
mask_nonneg w;
885
mask_numbits w;
886
let lemma sub (i: int63) : unit
887
requires { Set.mem i r.SBDD.dom_indexes }
888
ensures { to_indexes wit i }
889
=
890
if Set.mem i x.b.SBDD.dom_indexes then begin
891
if to_int i >= w then numbits_high_clear x.indexes (to_int i)
892
end else begin
893
assert { exists nd g. Mem.mem (nd, g) cl /\ Set.mem i g.SBDD.dom_indexes };
894
assert { exists nd f. Mem.mem (nd, f) l /\ bittest f.indexes i };
895
if to_int i >= w then
896
assert { forall nd f. Mem.mem (nd, f) l -> not (bittest f.indexes i) by
897
numbits f.indexes <= w }
898
end
899
in
900
{ b = r; indexes = from_indexes r.SBDD.dom_indexes wit }
901
902
type
inspect
=
Bool
bool |
IteIndex
int63 t t |
IteSnode
snode t t

The PBDD of a sub–BDD of a

    Valid (50ms) (colibri2)
905
let
sub
(a:t) (th:SBDD.t) : t
906
requires { Set.subset th.SBDD.dom_indexes a.b.SBDD.dom_indexes }
907
ensures { result.b = th }
908
= { b = th; indexes = from_indexes th.SBDD.dom_indexes a.indexes }
909
Valid (638ms) (colibri2 49) (cvc4 3) (split_vc 8) (depth 3)
910
let
inspect
(a:t) : inspect
911
ensures { match result with
912
| Bool b -> a.v = (fun _ _ -> b) /\ support_snodes a = Set.empty
913
| IteIndex i th el ->
914
Set.subset (support_snodes th) (support_snodes a) /\
915
Set.subset (support_snodes el) (support_snodes a) /\
916
0 <= to_int i /\ Zbit.bittest a.dom_indexes i /\
917
Zbit.subset th.dom_indexes (Zbit.unset a.dom_indexes i) /\
918
Zbit.subset el.dom_indexes (Zbit.unset a.dom_indexes i) /\
919
Set.subset th.dom_snodes a.dom_snodes /\
920
Set.subset el.dom_snodes a.dom_snodes /\
921
0 <= nb_nodes th < nb_nodes a /\ 0 <= nb_nodes el < nb_nodes a /\
922
a.v = (fun id sn -> if Zbit.bittest id i then th.v id sn else el.v id sn)
923
| IteSnode nd th el ->
924
Set.mem nd (support_snodes a) /\
925
Set.subset (support_snodes th) (Set.remove nd (support_snodes a)) /\
926
Set.subset (support_snodes el) (Set.remove nd (support_snodes a)) /\
927
Set.mem nd a.dom_snodes /\
928
Zbit.subset th.dom_indexes a.dom_indexes /\
929
Zbit.subset el.dom_indexes a.dom_indexes /\
930
Set.subset th.dom_snodes (Set.remove nd a.dom_snodes) /\
931
Set.subset el.dom_snodes (Set.remove nd a.dom_snodes) /\
932
0 <= nb_nodes th < nb_nodes a /\ 0 <= nb_nodes el < nb_nodes a /\
933
a.v = (fun id sn -> if sn nd then th.v id sn else el.v id sn)
934
end }
935
=
936
match SBDD.inspect a.b with
937
| SBDD.Bool b -> Bool b
938
| SBDD.IteIndex i th el ->
939
let th' = sub a th in
940
let el' = sub a el in
941
let ghost u = Zbit.unset a.indexes (to_int i) in
942
unset_nonneg a.indexes (to_int i);
943
let lemma unset_bits (j: int) : unit
944
ensures { bittest u j <-> (j <> to_int i /\ bittest a.indexes j) }
945
= if 0 <= j then begin
946
def_asr 1 (- to_int i) j;
947
assert { bittest (lsl 1 i) j <-> j = to_int i }
948
end
949
in
950
assert { forall j: int63. Set.mem j (to_indexes u) <-> (j <> i /\ Set.mem j (to_indexes a.indexes)) };
951
to_indexes_subset th'.indexes u;
952
to_indexes_subset el'.indexes u;
953
IteIndex i th' el'
954
| SBDD.IteSnode nd th el -> IteSnode nd (sub a th) (sub a el)
955
end
956
Valid (370ms) (colibri2 12) (cvc4) (cvc5) (split_vc) (depth 1)
957
let partial
compose_index
(i: int63) (f a: t) : t
958
requires { 0 <= to_int i }
959
ensures { result.dom_indexes = (Zbit.lor f.dom_indexes (Zbit.unset a.dom_indexes (to_int i))) }
960
ensures { result.dom_snodes = Set.union f.dom_snodes a.dom_snodes }
961
ensures { result.v = (fun id sn -> a.v (Zbit.change id (to_int i) (f.v id sn)) sn) } =
962
let ghost u = Zbit.unset a.indexes (to_int i) in
963
let lemma unset_bits (j: int) : unit
964
ensures { bittest u j <-> (j <> to_int i /\ bittest a.indexes j) }
965
= if 0 <= j then begin
966
def_asr 1 (- to_int i) j;
967
assert { bittest (lsl 1 i) j <-> j = to_int i }
968
end
969
in
970
assert { forall j: int63. Set.mem j (to_indexes u) <-> (j <> i /\ Set.mem j (to_indexes a.indexes)) };
971
assert { forall j: int63. to_indexes u j = Set.remove i (to_indexes a.indexes) j };
972
assert { to_indexes u = Set.remove i (to_indexes a.indexes) };
973
assert { to_indexes (Zbit.lor f.indexes u) = Set.union (to_indexes f.indexes) (to_indexes u) };
974
let res = { b = SBDD.compose_index i f.b a.b; indexes = Zbit.lor f.indexes (Zbit.unset a.indexes (to_int i)) } in
975
assert { forall id sn. res.v id sn
976
= (a.v (Zbit.change id (to_int i) (f.v id sn)) sn) };
977
res
978
979
end