Source file ast.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
(** Python AST *)
open Mopsa
open Universal.Ast
(** {2 Constants} *)
type constant +=
| C_py_ellipsis
| C_py_none
| C_py_not_implemented
| C_py_imag of float
(** {2 Types} *)
type py_type =
| Bool | NotImplemented | Complex | NoneType | Bytes | Str | Int | Float of float_prec
(** Python-specific types *)
type typ +=
| T_py of py_type option
let is_py_exp e =
match etyp e with
| T_py _ -> true
| _ -> false
(** {2 Expressions} *)
(** Python objects *)
type py_object = addr (** uid + type *) * expr option (** optional value representation *)
let compare_py_object (obj1: py_object) (obj2: py_object) : int =
let addr1 = fst obj1 and addr2 = fst obj2 in
compare_addr addr1 addr2
type operator +=
| O_py_and (** and *)
| O_py_or (** or *)
| O_py_floor_div (** // *)
| O_py_is (** is *)
| O_py_is_not (** is not *)
| O_py_in (** in *)
| O_py_not_in (** not in *)
| O_py_mat_mult (** @ *)
| O_py_not
let is_arith_op = function
| Universal.Ast.O_plus
| Universal.Ast.O_minus
| Universal.Ast.O_mult
| O_py_mat_mult
| Universal.Ast.O_div
| O_py_floor_div
| Universal.Ast.O_bit_invert
| Universal.Ast.O_mod
| Universal.Ast.O_pow
| Universal.Ast.O_bit_lshift
| Universal.Ast.O_bit_rshift
| Universal.Ast.O_bit_and
| Universal.Ast.O_bit_xor
| Universal.Ast.O_bit_or ->
true
| _ -> false
let is_arith_binop_fun cl str =
let splitted = String.split_on_char '.' str in
let l = ListExt.nth splitted (ListExt.length splitted - 1) in
ListExt.hd splitted = cl &&
match l with
| "__add__"
| "__radd__"
| "__floordiv__"
| "__rfloordiv__"
| "__mod__"
| "__rmod__"
| "__mul__"
| "__rmul__"
| "__pow__"
| "__rpow__"
| "__truediv__"
| "__rtruediv__"
| "__sub__"
| "__rsub__" -> true
| "__and__"
| "__rand__"
| "__rshift__"
| "__rrshift__"
| "__lshift__"
| "__rlshift__"
| "__or__"
| "__ror__"
| "__xor__"
| "__rxor__" -> cl = "int"
| _ -> false
let is_arith_div_fun cl str =
let splitted = String.split_on_char '.' str in
let l = ListExt.nth splitted (ListExt.length splitted - 1) in
ListExt.hd splitted = cl &&
match l with
| "__floordiv__"
| "__rfloordiv__"
| "__mod__"
| "__rmod__"
| "__truediv__"
| "__rtruediv__" -> true
| _ -> false
let is_reverse_operator str =
let splitted = String.split_on_char '.' str in
let l = ListExt.nth splitted (ListExt.length splitted - 1) in
match l with
| "__radd__"
| "__rfloordiv__"
| "__rmod__"
| "__rmul__"
| "__rpow__"
| "__rtruediv__"
| "__rsub__"
| "__rand__"
| "__rrshift__"
| "__rlshift__"
| "__ror__"
| "__rxor__" -> true
| _ -> false
let is_comp_op = function
| O_eq
| O_ne
| O_lt
| O_le
| O_gt
| O_ge -> true
| _ -> false
let is_compare_op_fun cl str =
let splitted = String.split_on_char '.' str in
let l = ListExt.nth splitted (ListExt.length splitted - 1) in
ListExt.hd splitted = cl &&
match l with
| "__eq__"
| "__ne__"
| "__lt__"
| "__le__"
| "__gt__"
| "__ge__" -> true
| _ -> false
(** Lambda functions. *)
type py_lambda = {
py_lambda_body: expr; (** Body. *)
py_lambda_parameters: var list; (** list of parameters variables *)
py_lambda_defaults: expr option list; (** list of default parameters values *)
}
type expr_kind +=
| E_py_undefined of bool
| E_py_object of py_object
| E_py_list of expr list
| E_py_index_subscript of expr (** object *) * expr (** index *)
| E_py_slice_subscript of expr (** object *) * expr (** start *) * expr (** end *) * expr (** step *)
| E_py_attribute of expr (** object *) * string (** attribute name *)
| E_py_dict of expr list (** keys *) * expr list (** values *)
| E_py_set of expr list
| E_py_generator_comprehension of
expr (** generator expression *) *
(
expr (** target *) *
expr (** iterator *) *
expr list (** list of conditions *)
) list (** list of comprehensions *)
| E_py_list_comprehension of
expr (** value expression *) *
(
expr (** target *) *
expr (** iterator *) *
expr list (** list of conditions *)
) list (** list of comprehensions *)
| E_py_set_comprehension of
expr (** value expression *) *
(
expr (** target *) *
expr (** iterator *) *
expr list (** list of conditions *)
) list (** list of comprehensions *)
| E_py_dict_comprehension of
expr (** key expression *) *
expr (** value expression *) *
(
expr (** target *) *
expr (** iterator *) *
expr list (** list of conditions *)
) list (** list of comprehensions *)
| E_py_call of expr (** function *) *
expr list (** arguments *) *
(string option * expr) list (** keywords (None id for **kwargs) *)
| E_py_yield of expr
| E_py_yield_from of expr
| E_py_if of expr (** test *) * expr (** body *) * expr (** orelse *)
| E_py_tuple of expr list
| E_py_bytes of string
| E_py_lambda of py_lambda
| E_py_multi_compare of expr
* operator list
* expr list
| E_py_annot of expr
| E_py_check_annot of expr * expr
(** low-level hasattribute working at the object level only *)
| E_py_ll_hasattr of expr (** object *) * expr (** attribute name *)
(** low-level attribute access working at the object level only *)
| E_py_ll_getattr of expr (** object *) * expr (** attribute name *)
(** low-level attribute setter working at the object level only *)
| E_py_ll_setattr of expr (** object *) * expr (** attribute name *) * expr option
(** {2 Statements} *)
(** Python function descriptor *)
type py_fundec = {
py_func_var: var; (** function object variable *)
py_func_parameters: var list; (** list of parameters variables *)
py_func_defaults: expr option list; (** list of default parameters values *)
py_func_vararg: var option;
py_func_kwonly_args: var list;
py_func_kwonly_defaults: expr option list;
py_func_kwarg: var option;
py_func_locals: var list; (** list of local variables *)
py_func_body: stmt; (** function body *)
py_func_is_generator: bool; (** is the function a generator? *)
py_func_decors: expr list;
py_func_types_in: expr option list;
py_func_type_out: expr option;
py_func_range: range; (** range of the function *)
py_func_ret_var: var;
py_func_cellvars: var list;
py_func_freevars: var list;
}
type py_func_sig =
{
py_funcs_parameters: var list;
py_funcs_defaults: bool list;
py_funcs_exceptions: expr list;
py_funcs_types_in: expr option list;
py_funcs_type_out: expr option;
}
type py_func_annot = {
py_funca_var: var;
py_funca_decors: expr list;
py_funca_range: range;
py_funca_ret_var: var;
py_funca_sig: py_func_sig list;
}
let pp_py_func_sig (fmt: Format.formatter) (sign: py_func_sig) =
(Format.pp_print_list ~pp_sep:(fun fmt () -> Format.pp_print_string fmt ", ") (fun fmt (p, a) ->
Format.fprintf fmt "%a: %a" pp_var p (OptionExt.print pp_expr) a))
fmt (List.combine sign.py_funcs_parameters sign.py_funcs_types_in)
let compare_py_func_sig s s' =
Compare.compose
[ (fun () -> Compare.list (OptionExt.compare compare_expr) s.py_funcs_types_in s'.py_funcs_types_in);
(fun () -> OptionExt.compare compare_expr s.py_funcs_type_out s'.py_funcs_type_out) ]
let pp_py_func_annot (fmt:Format.formatter) (a:py_func_annot) =
List.iter (fun sign ->
Format.fprintf fmt "%a%a(%a) -> %a: ...@\n"
(fun fmt _ -> if a.py_funca_decors = [] then Format.fprintf fmt ""
else Format.fprintf fmt "@%a@\n" (Format.pp_print_list ~pp_sep:(fun fmt () -> Format.pp_print_string fmt ", ") pp_expr) a.py_funca_decors) ()
pp_var a.py_funca_var
pp_py_func_sig sign
(OptionExt.print pp_expr) sign.py_funcs_type_out
) a.py_funca_sig
(** A Python class *)
type py_clsdec = {
py_cls_var : var; (** class object variable *)
py_cls_body : stmt;
py_cls_static_attributes: var list; (** list of declared attributes: static variables and methods *)
py_cls_bases : expr list; (** base classes *)
py_cls_decors: expr list;
py_cls_keywords: (string option * expr) list; (** keywords (None id for **kwargs) *)
py_cls_range : range; (** range of the class *)
}
type py_cls_annot = {
py_cls_a_var : var;
py_cls_a_body : stmt;
py_cls_a_bases : expr list;
py_cls_a_abases : expr list;
py_cls_a_static_attributes: var list;
py_cls_a_range : range;
}
(** Exception handler *)
type py_excpt = {
py_excpt_type : expr option; (** exception class. None is used for the default except *)
py_excpt_name : var option; (** optional name of exception instance *)
py_excpt_body : stmt; (** body of the except handler *)
}
(** Statements *)
type stmt_kind +=
(** class definition *)
| S_py_class of py_clsdec
(** function definition *)
| S_py_function of py_fundec
(** try/except statements *)
| S_py_try
of stmt (** body *) *
py_excpt list (** exception handlers *) *
stmt (** else body *) *
stmt (** final body *)
(** exception instance *)
| S_py_raise of expr option
(** if condition *)
| S_py_if of expr * stmt * stmt
(** while loops. *)
| S_py_while of expr * stmt * stmt
(** assign a expression to a list of lvals *)
| S_py_multi_assign of expr list * expr
(** increment assignments *)
| S_py_aug_assign of expr * operator * expr
(** type annotations for variables *)
| S_py_annot of expr * expr
(** type annotation check for variables *)
| S_py_check_annot of expr * expr
(** for loops *)
| S_py_for of expr (** target *) *
expr (** iterator *) *
stmt (** body *) *
stmt (** else *)
(** package import *)
| S_py_import of string (** module *) *
var option (** asname *) *
var (** root module *)
| S_py_import_from of string (** module *) *
string (** name *) *
var (** root module *) *
var (** module var *)
| S_py_delete of expr
| S_py_assert of expr (** test *) * expr option (** message *)
| S_py_with of expr (** context *) *
expr option (** as *) *
stmt (** body *)
(** {2 Programs} *)
type prog_kind +=
| Py_program of
string (** name *) *
var list (** global variables *) *
stmt (** body *)
(** Flow-insensitive context to keep the analyzed C program *)
module K = GenContextKey(struct
type 'a t = string * var list * stmt
let print pp fmt prog = Format.fprintf fmt "Python program"
end)
let py_program_ctx = K.key
(** Set the Python program in the flow *)
let set_py_program prog flow =
Flow.set_ctx (Flow.get_ctx flow |> add_ctx py_program_ctx prog) flow
(** Get the Python program from the flow *)
let get_py_program flow =
Flow.get_ctx flow |> find_ctx py_program_ctx
(** {2 Utility functions} *)
let mk_py_in ?(strict = false) ?(left_strict = false) ?(right_strict = false) v e1 e2 erange =
match strict, left_strict, right_strict with
| true, _, _
| false, true, true ->
mk_binop ~etyp:(T_py None)
(mk_binop ~etyp:(T_py None) e1 O_lt v erange)
O_py_and
(mk_binop ~etyp:(T_py None) v O_lt e2 erange)
erange
| false, true, false ->
mk_binop ~etyp:(T_py None)
(mk_binop ~etyp:(T_py None) e1 O_lt v erange)
O_py_and
(mk_binop ~etyp:(T_py None) v O_le e2 erange)
erange
| false, false, true ->
mk_binop ~etyp:(T_py None)
(mk_binop ~etyp:(T_py None) e1 O_le v erange)
O_py_and
(mk_binop ~etyp:(T_py None) v O_lt e2 erange)
erange
| false, false, false ->
mk_binop ~etyp:(T_py None)
(mk_binop ~etyp:(T_py None) e1 O_le v erange)
O_py_and
(mk_binop ~etyp:(T_py None) v O_le e2 erange)
erange
let mk_py_not exp range =
mk_unop ~etyp:(T_py (Some Bool)) O_py_not exp range
let mk_except typ name body =
{
py_excpt_type = typ;
py_excpt_name = name;
py_excpt_body = body;
}
let mk_try body except orelse finally range =
mk_stmt
(S_py_try (
body,
except,
orelse,
finally
))
range
let mk_raise exc range =
mk_stmt (S_py_raise (Some exc)) range
let mk_py_call func args range =
mk_expr ~etyp:(T_py None) (E_py_call (func, args, [])) range
let mk_py_kall func args kwargs range =
mk_expr ~etyp:(T_py None) (E_py_call (func, args, kwargs)) range
let mk_py_attr obj attr ?(etyp=(T_py None)) range =
mk_expr (E_py_attribute (obj, attr)) ~etyp range
let mk_py_index_subscript obj index ?(etyp=(T_py None)) range =
mk_expr (E_py_index_subscript (obj, index)) ~etyp range
let mk_py_object (addr, e) range =
mk_expr ~etyp:(T_py None) (E_py_object (addr, e)) range
let mk_py_object_attr obj attr ?(etyp=(T_py None)) range =
mk_py_attr (mk_py_object obj range) attr ~etyp range
let mk_py_bool b range =
mk_constant (C_bool b) ~etyp:(T_py (Some Bool)) range
let mk_py_true = mk_py_bool true
let mk_py_false = mk_py_bool false
let mk_py_top t range =
let t = match t with
| T_py _ -> t
| T_int -> T_py (Some Int)
| T_float f -> T_py (Some (Float f))
| T_bool -> T_py (Some Bool)
| T_string -> T_py (Some Str)
| _ -> assert false in
mk_constant (C_top t) ~etyp:t range
let object_of_expr e =
match ekind e with
| E_py_object o -> o
| _ -> assert false
let mk_py_none range =
mk_constant ~etyp:(T_py (Some NoneType)) C_py_none range
(** {2 Decorators} *)
let is_stub_fundec fundec =
List.exists (fun exp -> match ekind exp with
| E_py_attribute({ekind = E_var( {vkind = V_uniq ("mopsa",_)}, _)}, "stub") -> true
| _ -> false
) fundec.py_func_decors
let is_builtin_fundec fundec =
List.exists (fun exp -> match ekind exp with
| E_py_call({ekind = E_py_attribute({ekind = E_var( {vkind = V_uniq ("mopsa",_)}, _)}, "builtin")}, _, []) -> true
| _ -> false
)
fundec.py_func_decors
let is_builtin_clsdec clsdec =
List.exists (fun exp -> match ekind exp with
| E_py_call({ekind = E_py_attribute({ekind = E_var( {vkind = V_uniq ("mopsa",_)}, _)}, "builtin")}, _, []) -> true
| _ -> false
)
clsdec.py_cls_decors
let is_unsupported_fundec fundec =
List.exists (fun exp -> match ekind exp with
| E_py_attribute({ekind = E_var( {vkind = V_uniq ("mopsa",_)}, _)}, "unsupported") -> true
| _ -> false)
fundec.py_func_decors
let is_unsupported_clsdec clsdec =
List.exists (fun exp -> match ekind exp with
| E_py_attribute({ekind = E_var( {vkind = V_uniq ("mopsa",_)}, _)}, "unsupported") -> true
| _ -> false)
clsdec.py_cls_decors
let builtin_fundec_name fundec =
let decor = List.find (fun exp -> match ekind exp with
| E_py_call({ekind = E_py_attribute({ekind = E_var( {vkind = V_uniq ("mopsa",_)}, _)}, "builtin")}, [{ekind = E_constant (C_string name)}], []) -> true
| _ -> false) fundec.py_func_decors in
match ekind decor with
| E_py_call({ekind = E_py_attribute({ekind = E_var( {vkind = V_uniq ("mopsa",_)}, _)}, "builtin")}, [{ekind = E_constant (C_string name)}], []) -> name
| _ -> assert false
let builtin_clsdec_name clsdec =
let decor = List.find (fun exp -> match ekind exp with
| E_py_call({ekind = E_py_attribute({ekind = E_var( {vkind = V_uniq ("mopsa",_)}, _)}, "builtin")}, [{ekind = E_constant (C_string name)}], []) -> true
| _ -> false) clsdec.py_cls_decors in
match ekind decor with
| E_py_call({ekind = E_py_attribute({ekind = E_var( {vkind = V_uniq ("mopsa",_)}, _)}, "builtin")}, [{ekind = E_constant (C_string name)}], []) -> name
| _ -> assert false
let builtin_type_name default fundec =
let decor = List.find_opt (fun exp -> match ekind exp with
| E_py_call({ekind = E_py_attribute({ekind = E_var( {vkind = V_uniq ("mopsa",_)}, _)}, "type")}, [{ekind = E_constant (C_string name)}], []) -> true
| _ -> false) fundec.py_func_decors in
match decor with
| None -> default
| Some {ekind = E_py_call({ekind = E_py_attribute({ekind = E_var( {vkind = V_uniq ("mopsa",_)}, _)}, "type")}, [{ekind = E_constant (C_string name)}], [])} -> name
| _ -> assert false
let py_or e1 e2 ?(etyp=T_py (Some Bool)) range = mk_binop e1 O_py_or e2 ~etyp range
let py_and e1 e2 ?(etyp=T_py (Some Bool)) range = mk_binop e1 O_py_and e2 ~etyp range
let mk_py_ll_hasattr instance attr range =
mk_expr ~etyp:(T_py None) (E_py_ll_hasattr(instance, attr)) range
let mk_py_ll_getattr instance attr range =
mk_expr ~etyp:(T_py None) (E_py_ll_getattr(instance, attr)) range
let mk_py_ll_setattr instance attr valu range =
mk_expr ~etyp:(T_py None) (E_py_ll_setattr(instance, attr, Some valu)) range
let mk_py_ll_delattr instance attr range =
mk_expr ~etyp:(T_py None) (E_py_ll_setattr(instance, attr, None)) range