-
Erwan Jahier authored
nb : programs do run, but I did not check that they run correctly... Also fix a regression introduced in the previous change where incorrect ec code was generated for diese.
Erwan Jahier authorednb : programs do run, but I did not check that they run correctly... Also fix a regression introduced in the previous change where incorrect ec code was generated for diese.
evalClock.ml 16.21 KiB
(* Time-stamp: <modified the 03/04/2013 (at 14:22) by Erwan Jahier> *)
open AstPredef
open LicEvalConst
open AstV6
open AstCore
open Lic
open IdSolver
open Printf
open Lxm
open Errors
open UnifyClock
(**
** 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 expected 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 are unifiable.
*)
let (check_args : Lxm.t -> subst -> Lic.id_clock list -> Lic.id_clock list -> subst) =
fun lxm s cil_par cil_arg ->
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 s = List.fold_left2 (UnifyClock.f lxm) s cil_arg cil_par in
s
(** 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 are unifiable.
*)
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 = (Ident.to_string v.var_name_eff) ^ "." ^ (Ident.to_string id) in
{ v with var_name_eff = Ident.of_string new_name }
| LeftArrayLic (l,i,_) ->
let v = var_info_eff_of_left_eff l in
let new_name = (Ident.to_string v.var_name_eff) ^ "[" ^
(string_of_int i) ^ "]"
in
{ v with var_name_eff = Ident.of_string new_name }
| LeftSliceLic (l,si,_) ->
let v = var_info_eff_of_left_eff l in
let new_name = (Ident.to_string v.var_name_eff) ^ (LicDump.string_of_slice_info_eff si)
in
{ v with var_name_eff = Ident.of_string new_name }
let var_info_eff_to_clock_eff v = v.var_clock_eff
(* exported *)
let (check_res : Lxm.t -> subst -> Lic.left list -> Lic.id_clock list -> unit) =
fun lxm (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
ignore(List.fold_left2 (UnifyClock.f lxm) s left_ci rigth)
(******************************************************************************)
(** 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 rec (is_a_sub_clock :
Lxm.t -> subst -> Lic.id_clock -> Lic.id_clock -> subst option) =
fun lxm s (id_sc,sc) (id_c,c) ->
(* Check if [sc] is a sub-clock of [c] (in the large sense).
Returns Some updated substitution if it is the case, and None otherwise *)
let rec aux sc c =
match sc, c with
(* the base clock is a sub-clock of all clocks *)
| BaseLic, (BaseLic|On(_,_)|ClockVar _) -> Some s
| On(_,_), BaseLic -> None
| sc, On(_,c_clk) -> (
try Some(UnifyClock.f lxm s sc c)
with Compile_error _ -> aux sc c_clk
)
| _,_ ->
try Some(UnifyClock.f lxm s 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
(******************************************************************************)
(** Now we can go on and define [f]. *)
let rec (f : Lxm.t -> IdSolver.t -> subst -> Lic.val_exp -> Lic.clock list ->
Lic.val_exp * Lic.id_clock list * subst) =
fun lxm id_solver s ve exp_clks ->
(* we split f so that we can reinit the fresh clock var generator *)
let ve, inf_clks, s = f_aux id_solver s ve in
let s =
if exp_clks = [] then s else
List.fold_left2
(fun s eclk iclk -> UnifyClock.f lxm s eclk iclk)
s
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 = { ve with ve_clk = clks } in
if Verbose.level() > 2 then
print_string (
"Clocking the expression '" ^ (LicDump.string_of_val_exp_eff ve) ^"': "^
(LicDump.string_of_clock2 (List.hd clks)) ^"\n");
ve, inf_clks, s
and f_aux id_solver s ve =
let (cel, s), lxm =
match ve.ve_core with
| CallByPosLic ({it=posop; src=lxm}, args) ->
eval_by_pos_clock id_solver posop lxm args s, lxm
| CallByNameLic ({it=nmop; src=lxm}, nmargs ) -> (
try eval_by_name_clock id_solver nmop lxm nmargs s, lxm with EvalConst_error msg ->
raise (Compile_error(lxm, "\n*** can't eval constant: "^msg))
)
| Merge(ce, cl) ->
let ce_id, (merge_clk : Lic.clock) =
var_info_eff_to_clock_eff (IdSolver.var_info_of_ident id_solver ce.it ce.src)
in
let check_case s (c,ve) =
(* Check that ve is on c(ce) on merge_clk *)
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.it, Lic.type_of_const c.it) in
let exp_clk = [On(id_clk, merge_clk)] in
let _ve,cel,s = f c.src id_solver s ve exp_clk in
s
in
let s = List.fold_left check_case s cl in
([ce.it,merge_clk],s), ce.src
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 = List.fold_left2 (UnifyClock.f lxm) s ve.ve_clk new_clk in
s, ve
in
apply_subst_val_exp s ve, cel, s
(* iterate f on a list of expressions *)
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.id_clock list * subst) =
fun id_solver posop lxm args s ->
let apply_subst s (id,clk) = id, UnifyClock.apply_subst s clk in
match posop,args with
| Lic.CURRENT,args -> ( (* we return the clock of the argument *)
let _args, clocks_of_args, s = f_list id_solver s args in
let current_clock = function
| (id, BaseLic) -> (id, BaseLic)
| (id, On(_,clk)) -> (id, clk)
| (_, ClockVar _) -> assert false
in
List.map current_clock (List.flatten clocks_of_args), s
)
| Lic.WHEN when_exp_clk,args -> (
let c_clk =
match when_exp_clk with
| BaseLic -> BaseLic
| ClockVar _ -> assert false
| On((cc,c,_), c_clk) ->
(* | NamedClock { it = (cc,c) ; src = lxm } -> *)
(* let id, c_clk = (id_solver.id2var c lxm).var_clock_eff in *)
c_clk
in let aux_when exp_clk s =
(*
In order to clock check an expression such as
exp when C(c)
we first need to check that the clock of c (c_clk)
is a sub-clock of the clock of exp (exp_clk).
*)
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
(match f_list id_solver s args with
(* XXX ce cas ne sert rien !!!
le traitement du cas ou la liste ne contient qu'un element
n'a aucun raison d'etre particulier, si ???
*)
| _args,[[exp_clk]], s ->
let (exp_clk,s) = aux_when exp_clk s in
([exp_clk], s)
| _args, [exp_clk_list], s ->
(* when on tuples *)
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
(List.rev exp_clk_list, s)
| _ -> assert false (* "(x1,x2) when node (x,y)" *)
)
)
(* f_aux id_solver (List.hd args) *)
| Lic.HAT(i),[ve] ->
let (_,clk,s) = f_aux id_solver s ve in
clk,s
| Lic.HAT(i),_ -> assert false
| Lic.VAR_REF id,args ->
let vi = IdSolver.var_info_of_ident id_solver id lxm in
([var_info_eff_to_clock_eff vi], s)
| Lic.CONST c, args -> (
let s, clk = UnifyClock.new_clock_var s in
[Lic.string_of_const c, 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
([Ident.of_long idl, clk], s)
| Lic.CALL nkf,args ->
let node_key = nkf.it 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
(* the value of the base clock of a node is actually relative
to the context into which the node is called.
Hence we create a fresh var clock, that will be instanciated
by the caller.
*)
let (replace_base : Lic.clock -> Lic.id_clock -> Lic.id_clock) =
fun rel_base (id,ci) ->
(* [replace_base rel_base ci ] replaces in [ci] any occurences of the
base clock by [rel_base] *)
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 s = check_args lxm s cil_arg (List.flatten clk_args) in
List.map (apply_subst s) 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 (* all predef nodes are mono-clock! *)
let _,flat_clk_args = List.split flat_clk_args in
let clk_list, s =
if args = [] then [],s else
let _clk,s = UnifyClock.list lxm flat_clk_args s in
List.map (List.map (apply_subst s)) clk_args, s
in
LicEvalClock.f id_solver op lxm s clk_list
(* One argument. *)
| Lic.PRE,args
| Lic.STRUCT_ACCESS _,args
| Lic.ARRAY_ACCES (_),args
| Lic.ARRAY_SLICE (_),args ->
assert(List.length args = 1);
let (_,clk,s) = f_aux id_solver s (List.hd args) in
clk,s
(* may have tuples as arguments *)
| Lic.TUPLE,args
| Lic.ARROW,args
| Lic.FBY ,args
| Lic.CONCAT,args
| Lic.ARRAY,args -> (
(* Check that all args are of the same (unifiable) clocks.
XXX : we suppose that all those operators are
mono-clocks (i.e., when they return tuples, all elements
are on the same clock). It would be sensible to have,
e.g., arrows on multiple clocks. We'll refine later. *)
let args, clk_args, s = f_list id_solver s args in
let flat_clk_args = List.flatten clk_args in (* => mono-clock! *)
let idl,flat_clk_args = List.split flat_clk_args in
let clk,s = UnifyClock.list lxm flat_clk_args s in
let clk_list = match posop with
| Lic.TUPLE ->
let clk_l = List.map (UnifyClock.apply_subst s) flat_clk_args in
List.combine idl clk_l
| _ -> List.map (apply_subst s) (List.hd clk_args)
in
clk_list, s
)
and (eval_by_name_clock : IdSolver.t -> Lic.by_name_op -> Lxm.t ->
(Ident.t Lxm.srcflagged * Lic.val_exp) list -> subst ->
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
(* XXX The 3 following lines duplicates the code of TUPLE_eff and co *)
let args, clk_args, s = f_list id_solver s args in
let flat_clk_args = List.flatten clk_args in (* => mono-clock! *)
let _,flat_clk_args = List.split flat_clk_args in
let clk,s = UnifyClock.list lxm 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 (* cf EvalType.E *)
| Lic.STRUCT(_) -> clk_list, s
| Lic.STRUCT_with(_, dft) ->
(* XXX should i do something here ??? *)
clk_list, s