package mopsa

  1. Overview
  2. Docs
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

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
(****************************************************************************)
(*                                                                          *)
(* This file is part of MOPSA, a Modular Open Platform for Static Analysis. *)
(*                                                                          *)
(* Copyright (C) 2017-2019 The MOPSA Project.                               *)
(*                                                                          *)
(* This program is free software: you can redistribute it and/or modify     *)
(* it under the terms of the GNU Lesser General Public License as published *)
(* by the Free Software Foundation, either version 3 of the License, or     *)
(* (at your option) any later version.                                      *)
(*                                                                          *)
(* This program is distributed in the hope that it will be useful,          *)
(* but WITHOUT ANY WARRANTY; without even the implied warranty of           *)
(* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *)
(* GNU Lesser General Public License for more details.                      *)
(*                                                                          *)
(* You should have received a copy of the GNU Lesser General Public License *)
(* along with this program.  If not, see <http://www.gnu.org/licenses/>.    *)
(*                                                                          *)
(****************************************************************************)

(** 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 (* is it global? *)
  | 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 (* left *)
                      * operator list (* ops *)
                      * expr list (* comparators *)
  | E_py_annot of expr
  (* checking type annotations using stubs *)
  | 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 (* expression to bind to obj.attr, or None if we want to delete obj.attr (as tp_setattr behaves in cpython) *)


(*==========================================================================*)
                           (** {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; (* variable argument arg (usually *args), if any *)
  py_func_kwonly_args: var list; (* list of keyword-only arguments *)
  py_func_kwonly_defaults: expr option list; (* default values associated to keyword-only arguments *)
  py_func_kwarg: var option; (* keyword-based variable argument (usually **kwargs) if any *)
  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; (* list of cell vars, ie variables that may be part of function closures *)
  py_func_freevars: var list;
}

type py_func_sig =
  {
    py_funcs_parameters: var list;
    py_funcs_defaults: bool list; (* true iff argument has default *)
    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; (* bases from the typing module, hopefully *)
  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 (*t test *) * stmt (* then *) * stmt (* else *)

  (** while loops. *)
  | S_py_while of expr (* test *) * stmt (* body *) * stmt (* orelse *)

  (** 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 =
  (* call with kwargs *)
  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
OCaml

Innovation. Community. Security.