Source file evalClock.ml
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
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
open LicEvalConst
open Lic
open Lxm
open Lv6errors
open UnifyClock
let dbg = (Lv6Verbose.get_flag "clock-check")
(**
** Foreword.
The clock mechanism of Lustre is a simple kind of type dependant
system. Indeed, clocks depend on program variables. More
precisely, and according to Pouzet&Colaco [emsoft03], the clock
type system of Lustre is equivalent to a "firt class abstract
type system".
Note however that here, things are simpler than in emsoft03,
since we are not interested in type reconstruction (or
inference), but only in checking types are provided in node
headers.
** clock checking of expressions.
nb:
In the following, we speak about input/output arguments/parameters of an
expression because:
- the difficult case wrt clock checking concerns nodes
- other kind of expressions can be seen as nodes, as they «take» some input
arguments, and return some outputs.
The clock checking consists in verifying that expression arguments clocks
are compatible with the expression parameters clocks.
For instance, for a node of profile:
node toto(a; b when a) returns (x when a; y when x);
when it is called, e.g., like that:
(v1,v2) = toto(v3,v4);
we need to check that:
- the argument clocks are ok, i.e., v4 is on v3 (1)
cf the [check_arg] function below
- the result clocks are ok, i.e., v2 is on v1 + v1 is on v3 (2)
cf the [check_res] function below
** Checking expression arguments
--------------------------------
ok. So now, let us detail how we clock check expression arguments.
e.g., in the equation
(x,y)=toto(a,b);
we want to make sure that the clocks of the argument "a" and "b" are compatible
with the input clock profile of "toto".
To do that, we suppose we have already computed:
- "cil_par" the expe cted input clock profile (via "get_clock_profile")
- "cil_arg" the list of clocks of arguments (via a rec call to f)
In order to check that this call is correct, we check that both
terms match.
It also modifies the substitution s (acculumated all along the
clock checking of the node) such that:
- the clock var in the callee parameters migth be be substituted
- ??? what else
*)
let rec fold_left3 f accu l1 l2 l3 =
match (l1, l2, l3) with
([], [], []) -> accu
| (a1::l1, a2::l2, a3::l3) -> fold_left3 f (f accu a1 a2 a3) l1 l2 l3
| (_, _, _) -> invalid_arg "in EvalClock.fold_left3"
let (check_args : Lxm.t -> Lxm.t list -> subst -> Lic.id_clock list ->
Lic.id_clock list -> subst) =
fun lxm lxms (s1,s2) cil_par cil_arg ->
Lv6Verbose.exe
~flag:dbg (
fun () ->
let pos = Lxm.position lxm in
let id_clock2str (id,c) = Printf.sprintf "[%s,%s]" id
(LicDump.string_of_clock2 c) in
let par = String.concat "," (List.map id_clock2str cil_par) in
let arg = String.concat "," (List.map id_clock2str cil_arg) in
Printf.printf
"# EvalClock.check_args (%s) \n#\t clock params=%s\n#\t clock args = %s\n"
pos par arg;
flush stdout
);
assert (List.length cil_par = List.length cil_arg);
let idl_par,cil_par = List.split cil_par
and idl_arg,cil_arg = List.split cil_arg
in
let ns1 = (List.map2 (fun x y -> x,y) idl_arg idl_par)@s1 in
let ns =
assert (List.length cil_arg = List.length cil_par);
fold_left3 UnifyClock.f (ns1,s2) lxms cil_arg cil_par
in
let res = (s1,snd ns) in
Lv6Verbose.exe
~flag:dbg (
fun () ->
let s1 = UnifyClock.subst_to_string (s1,s2) in
let s2 = UnifyClock.subst_to_string ns in
let s3 = UnifyClock.subst_to_string res in
Printf.printf "# EvalClock.check_args result:\n#\t s=%s\n#\t ns=%s \n#\t res=%s\n"
s1 s2 s3;
flush stdout
);
res
(** Checking expression result
--------------------------
It is the same thing, except that we have Lic.left list instead
of Lic.id_clock list.
e.g., in the equation:
(x,y)=toto(a,b);
we want to check that the clocks of "x" and "y" are compatible with
the output clock profile of node "toto".
To do that, we suppose we have:
- "left" the list of Lic.left
- "rigth" the list of result clock. (via "get_clock_profile" again)
and we just need to check that both side match.
*)
let rec (var_info_eff_of_left_eff: Lic.left -> Lic.var_info) =
function
| LeftVarLic (v, _) -> v
| LeftFieldLic (l, id,_) ->
let v = var_info_eff_of_left_eff l in
let new_name = (Lv6Id.to_string v.var_name_eff) ^ "." ^ (Lv6Id.to_string id) in
{ v with var_name_eff = Lv6Id.of_string new_name }
| LeftArrayLic (l,i,_) ->
let v = var_info_eff_of_left_eff l in
let new_name = (Lv6Id.to_string v.var_name_eff) ^ "[" ^
(string_of_int i) ^ "]"
in
{ v with var_name_eff = Lv6Id.of_string new_name }
| LeftSliceLic (l,si,_) ->
let v = var_info_eff_of_left_eff l in
let new_name = (Lv6Id.to_string v.var_name_eff) ^
(LicDump.string_of_slice_info_eff si)
in
{ v with var_name_eff = Lv6Id.of_string new_name }
let var_info_eff_to_clock_eff v = v.var_clock_eff
let (check_res : Lxm.t list -> subst -> Lic.left list -> Lic.id_clock list -> unit) =
fun lxms (s1,s2) left rigth ->
let left_vi = List.map var_info_eff_of_left_eff left in
let left_ci = List.map var_info_eff_to_clock_eff left_vi in
if (List.length left_ci <> List.length rigth) then assert false;
let idl_rigth,rigth = List.split rigth
and idl_left, left_ci = List.split left_ci in
let s = (List.combine idl_rigth idl_left)@s1, s2 in
assert (List.length left_ci = List.length rigth);
Lv6Verbose.exe
~flag:dbg (
fun () ->
let s1 = UnifyClock.subst_to_string (s1,s2) in
let s2 = UnifyClock.subst_to_string s in
let pos = Lxm.position (List.hd lxms) in
Printf.printf "# EvalClock.check_res (%s):\n#\t s=%s\n#\t s=%s\n"
pos s1 s2;
flush stdout
);
let ns = fold_left3 UnifyClock.f s lxms left_ci rigth in
Lv6Verbose.exe
~flag:dbg (
fun () ->
let s2 = UnifyClock.subst_to_string s in
let s3 = UnifyClock.subst_to_string ns in
let pos = Lxm.position (List.hd lxms) in
Printf.printf "# EvalClock.check_res (%s):\n#\t s=%s\n#\t ns=%s \n"
pos s2 s3;
flush stdout
)
(** In order to clock check "when" statements, we need to know if a clock [sc]
is a sub_clock of another one c (i.e., for all instants i, c(i) => sc(i))
If it is a sub_clock, we return the accumulator (the current substitution)
*)
let (is_a_sub_clock :
Lxm.t -> subst -> Lic.id_clock -> Lic.id_clock -> subst option) =
fun lxm s (_id_sc,sc) (_id_c,c) ->
let rec aux sc c =
match sc, c with
| BaseLic, (BaseLic|On(_,_)|ClockVar _) -> Some s
| On(_,_), BaseLic -> None
| sc, On(_,c_clk) -> (
try Some(UnifyClock.f s lxm sc c)
with Compile_error _ -> aux sc c_clk
)
| _,_ ->
try Some(UnifyClock.f s lxm sc c)
with Compile_error _ -> None
in
aux sc c
type clock_profile = Lic.id_clock list * Lic.id_clock list
let (get_clock_profile : Lic.node_exp -> clock_profile) =
fun n ->
(List.map var_info_eff_to_clock_eff n.inlist_eff,
List.map var_info_eff_to_clock_eff n.outlist_eff)
let ci2str = LicDump.string_of_clock2
let list_fill x n =
let rec aux x n acc =
if n <= 0 then acc else aux x (n-1) (x::acc)
in
aux x n []
let rec (get_lxm_list : Lic.val_exp list -> int -> Lxm.t list) =
fun args n ->
if n <> List.length args then
(match args with
| [{ve_core=CallByPosLic({it=Lic.TUPLE;_}, args);_}] -> get_lxm_list args n
| _ ->
let lxm = lxm_of_val_exp (List.hd args) in
list_fill lxm n
)
else
List.map lxm_of_val_exp args
(** Now we can go on and define [f]. *)
let rec (f : IdSolver.t -> subst -> Lic.val_exp -> Lxm.t list -> Lic.clock list ->
Lic.val_exp * Lic.id_clock list * subst) =
fun id_solver s ve lxms exp_clks ->
let ve, inf_clks, s = f_aux id_solver s ve in
let s =
if exp_clks = [] then s else (
if (List.length exp_clks <> List.length inf_clks) then
let msg = Printf.sprintf "Bad arity: %i expected, %i found"
(List.length exp_clks) (List.length inf_clks)
in
raise (Compile_error(lxm_of_val_exp ve, msg))
else
fold_left3
(fun s lxm eclk iclk -> UnifyClock.f s lxm eclk iclk)
s
lxms
exp_clks
(List.map (fun (_,clk) -> clk) inf_clks)
)
in
let inf_clks = List.map (fun (id,clk) -> id, apply_subst2 s clk) inf_clks in
let clks = snd (List.split inf_clks) in
let ve = apply_subst_val_exp s ve in
if Lv6Verbose.level() > 2 then
print_string (
"Clocking the expression '" ^ (LicDump.string_of_val_exp_eff false ve) ^"': "^
(LicDump.string_of_clock2 (List.hd clks)) ^"\n");
assert(ve.ve_clk <> []);
ve, inf_clks, s
and (f_aux : IdSolver.t -> subst -> Lic.val_exp
-> Lic.val_exp * Lic.id_clock list * subst) =
fun id_solver s ve ->
let ve, cel, s, lxm =
match ve.ve_core with
| CallByPosLic ({it=posop; src=lxm}, args) -> (
let args, cel, s = eval_by_pos_clock id_solver posop lxm args s in
if
(match posop with CURRENT _ -> true | _ -> false) &&
(List.length args = 1) && Lic.val_exp_is_constant (List.hd args)
then
let ve,cel,s = f_aux id_solver s (List.hd args) in
ve, cel, s, lxm
else
let ve =
match posop,args with
| CURRENT None, { ve_clk = (On((cc,cv,ct),cv_clk))::clks ;_ }::_ ->
let cv_val_exp = flagit (Lic.VAR_REF cv) lxm in
let cv_val_exp = Lic.CallByPosLic(cv_val_exp,[]) in
let cv_val_exp = { ve_core = cv_val_exp ; ve_typ = [ct] ;
ve_clk = [cv_clk];ve_src = lxm } in
let posop,args = CURRENT (Some cc), cv_val_exp::args in
List.iter
(fun clk -> assert(clk = On((cc,cv,ct),cv_clk))) clks;
let ve = { ve with
ve_core = CallByPosLic ({it=posop; src=lxm}, args) ;
ve_clk = cv_clk::(List.map (fun _ -> cv_clk) clks)
}
in
ve
| _ -> { ve with ve_core = CallByPosLic ({it=posop; src=lxm}, args)}
in
ve, cel, s, lxm
)
| CallByNameLic ({it=nmop; src=lxm}, nmargs) -> (
try
let nmargs, cel, s = eval_by_name_clock id_solver nmop lxm nmargs s in
let ve = { ve with ve_core = CallByNameLic ({it=nmop; src=lxm}, nmargs) } in
List.iter (fun (_,arg) -> assert (arg.ve_clk <> [])) nmargs;
ve, cel, s, lxm
with EvalConst_error msg ->
raise (Compile_error(lxm, "\n*** can't eval constant: "^msg))
)
| Merge(ce, cl) ->
let ce, _cel, s = f_aux id_solver s ce in
let (merge_clk : Lic.clock) = List.hd ce.ve_clk in
let ce_id,lxm = match ce with
| { ve_core= CallByPosLic({it = VAR_REF id ;_},[]) ;_} -> id, ve.ve_src
| _ -> assert false
in
let check_case (s,acc) (c,ve) =
let id_clk =
match c.it with
| Bool_const_eff true -> "Lustre", "true"
| Bool_const_eff false -> "Lustre", "false"
| Enum_const_eff (s,_) -> s
| _ -> assert false
in
let id_clk = (id_clk, ce_id, Lic.type_of_const c.it) in
let exp_clk = On(id_clk, merge_clk) in
let exp_clk = List.map (fun _ -> exp_clk) ve.ve_typ in
let lxms = List.map (fun _ -> c.src) ve.ve_typ in
let ve,_cel,s = f id_solver s ve lxms exp_clk in
s, (c,ve)::acc
in
let s,cl = List.fold_left check_case (s,[]) cl in
let ve = { ve with ve_core = Merge(ce, List.rev cl) } in
let merge_clk = List.map (fun _ -> ce_id, merge_clk) ve.ve_typ in
ve, merge_clk, s, lxm
in
let new_clk = snd (List.split cel) in
let s, ve =
if ve.ve_clk = [] then (s, { ve with ve_clk = new_clk }) else
let s =
assert(List.length ve.ve_clk = List.length new_clk);
List.fold_left2 (fun s -> UnifyClock.f s lxm) s ve.ve_clk new_clk in
s, ve
in
let ve = apply_subst_val_exp s ve in
ve, cel, s
and (f_list : IdSolver.t -> subst -> Lic.val_exp list ->
Lic.val_exp list * Lic.id_clock list list * subst) =
fun id_solver s args ->
let aux (args,acc,s) arg =
let arg, cil, s = f_aux id_solver s arg in
(arg::args, cil::acc, s)
in
let (args, cil, s) = List.fold_left aux ([],[],s) args in
let args = List.rev args in
let cil = List.rev cil in
let cil = List.map (List.map(fun (id,clk) -> id, apply_subst2 s clk)) cil in
args, cil, s
and (eval_by_pos_clock : IdSolver.t -> Lic.by_pos_op -> Lxm.t -> Lic.val_exp list ->
subst -> Lic.val_exp list * Lic.id_clock list * subst) =
fun id_solver posop lxm args s ->
let apply_subst s (id,clk) = id, UnifyClock.apply_subst s clk in
let args, (cl,s) =
match posop,args with
| Lic.CURRENT (Some _), _clk_arg::_ -> assert false
| Lic.CURRENT None, [arg] -> (
let args, clocks_of_args, s = f_list id_solver s [arg] in
let current_clock = function
| (id, BaseLic) -> (id, BaseLic)
| (id, On(_,clk)) -> (id, clk)
| (id, ClockVar i) -> (id, ClockVar i)
in
args, (List.map current_clock (List.flatten clocks_of_args), s)
)
| Lic.CURRENT None, _ -> assert false
| Lic.CURRENT (Some _), _ -> assert false
| Lic.WHEN when_exp_clk,args -> (
let c_clk =
match when_exp_clk with
| BaseLic -> BaseLic
| ClockVar _ -> assert false
| On((_cc,_c,_), c_clk) ->
c_clk
in
let aux_when exp_clk s =
match is_a_sub_clock lxm s exp_clk (fst exp_clk,c_clk) with
| None ->
let msg = "\n*** clock error: '" ^ (ci2str (snd exp_clk)) ^
"' is not a sub-clock of '" ^ (ci2str c_clk) ^ "'"
in
raise (Compile_error(lxm, msg))
| Some s ->
let id_when_exp_clk, s =
match exp_clk with
| id, On(_var,_) -> (id, when_exp_clk), s
| id, BaseLic -> (id, when_exp_clk), s
| id, ClockVar i ->
let id_when_exp_clk = id, when_exp_clk in
let (s1,s2) = s in
id_when_exp_clk,
(s1, UnifyClock.add_subst2 i when_exp_clk s2)
in
id_when_exp_clk, s
in
let res =
(match f_list id_solver s args with
| args,[[exp_clk]], s ->
let (exp_clk,s) = aux_when exp_clk s in
args,([exp_clk], s)
| args, [exp_clk_list], s ->
let exp_clk_list, s =
List.fold_left
(fun (acc,s) exp_clk ->
let (exp_clk,s) = aux_when exp_clk s in
exp_clk::acc, s
)
([],s)
exp_clk_list
in
args,(List.rev exp_clk_list, s)
| _ -> assert false
)
in
Lv6Verbose.exe
~flag:dbg (
fun () ->
let _,(clk_list,_) = res in
let id_clock2str (id,c) = Printf.sprintf "[%s,%s]"
id (LicDump.string_of_clock2 c)
in
let str = List.map id_clock2str clk_list in
let str = String.concat "," str in
let pos = Lxm.position lxm in
Printf.printf
"# EvalClock.eval_by_pos_clock @When (%s) %s\n" pos str;
flush stdout
);
res
)
| Lic.HAT(_i), [] -> assert false
| Lic.HAT(_i), ve::_ ->
let (ve,clk,s) = f_aux id_solver s ve in
[ve],(clk,s)
| Lic.VAR_REF id,args ->
let vi = IdSolver.var_info_of_ident id_solver id lxm in
args,([var_info_eff_to_clock_eff vi], s)
| Lic.CONST c, args -> (
let s, clk = UnifyClock.new_clock_var s in
args,([Lic.string_of_const c, clk], s)
)
| Lic.ARRAY,[] -> (
let s, clk = UnifyClock.new_clock_var s in
[],(["[]", clk],s)
)
| Lic.CONST_REF idl,args ->
let _const = IdSolver.const_eff_of_item_key id_solver idl lxm in
let s, clk = UnifyClock.new_clock_var s in
args,([Lv6Id.of_long idl, clk], s)
| Lic.CALL nkf,args ->
let node_key = nkf.it in
let lxm = nkf.src in
let node_exp_eff = IdSolver.node_exp_of_node_key id_solver node_key lxm in
let (cil_arg, cil_res) = get_clock_profile node_exp_eff in
let s, rel_base = UnifyClock.new_clock_var s in
let (replace_base : Lic.clock -> Lic.id_clock -> Lic.id_clock) =
fun rel_base (id,ci) ->
let rec aux ci =
match ci with
| BaseLic -> rel_base
| On(v,clk) -> On(v, aux clk)
| ClockVar _i -> ci
in
id, aux ci
in
let cil_arg = List.map (replace_base rel_base) cil_arg in
let cil_res = List.map (replace_base rel_base) cil_res in
let args, clk_args, s = f_list id_solver s args in
let lxms = get_lxm_list args (List.length cil_arg) in
let s = check_args lxm lxms s cil_arg (List.flatten clk_args) in
let cil_res = List.map (apply_subst s) cil_res in
args, (cil_res, s)
| Lic.PREDEF_CALL (nkf),args ->
let op = AstPredef.string_to_op (snd(fst nkf.it)) in
let args, clk_args, s = f_list id_solver s args in
let flat_clk_args = List.flatten clk_args in
let _,flat_clk_args = List.split flat_clk_args in
let lxms = get_lxm_list args (List.length flat_clk_args) in
let clk_list, s =
if args = [] then [],s else
let s = UnifyClock.list lxms flat_clk_args s in
List.map (List.map (apply_subst s)) clk_args, s
in
args, LicEvalClock.f id_solver op lxm s clk_list
| Lic.PRE,args
| Lic.STRUCT_ACCESS _,args
| Lic.ARRAY_ACCES (_),args
| Lic.ARRAY_SLICE (_),args ->
assert(List.length args = 1);
let (arg,clk,s) = f_aux id_solver s (List.hd args) in
[arg], (clk,s)
| Lic.TUPLE,args
| Lic.ARROW,args
| Lic.FBY ,args
| Lic.CONCAT,args
| Lic.ARRAY,args -> (
let args, clk_args, s = f_list id_solver s args in
let flat_clk_args = List.flatten clk_args in
let idl,flat_clk_args = List.split flat_clk_args in
let lxms = get_lxm_list args (List.length flat_clk_args) in
let s = UnifyClock.list lxms flat_clk_args s in
let clk_list =
match posop, clk_args with
| Lic.TUPLE,_ ->
let clk_l = List.map (UnifyClock.apply_subst s) flat_clk_args in
List.combine idl clk_l
| _, [] -> assert false
| _, _ -> List.map (apply_subst s) (List.hd clk_args)
in
args, (clk_list, s)
)
in
args, cl, s
and (eval_by_name_clock : IdSolver.t -> Lic.by_name_op -> Lxm.t ->
(Lv6Id.t Lxm.srcflagged * Lic.val_exp) list -> subst ->
(Lv6Id.t Lxm.srcflagged * Lic.val_exp) list * Lic.id_clock list * subst) =
fun id_solver namop _lxm namargs s ->
let apply_subst s (id,clk) = id, UnifyClock.apply_subst s clk in
let args = List.map (fun (_id,ve) -> ve) namargs in
let args, clk_args, s = f_list id_solver s args in
let namargs = List.map2 (fun (id,_ve) ve -> id,ve) namargs args in
let flat_clk_args = List.flatten clk_args in
let _,flat_clk_args = List.split flat_clk_args in
let lxms = get_lxm_list args (List.length flat_clk_args) in
let s = UnifyClock.list lxms flat_clk_args s in
let clk_list = List.map (apply_subst s) (List.hd clk_args) in
match namop with
| Lic.STRUCT_anonymous -> assert false
| Lic.STRUCT(_) -> namargs, clk_list, s
| Lic.STRUCT_with(_, _dft) ->
namargs,clk_list, s