wala / ML

Eclipse Public License 2.0
24 stars 17 forks source link

Missing the map() built-in function #98

Open khatchad opened 8 months ago

khatchad commented 8 months ago

The map() built-in function is missing, which has consequences for lambdas. Consider the following code:

# From https://docs.python.org/3/tutorial/datastructures.html#list-comprehensions

my_list = [10]

def fun_with_side_effects(y):
    my_list[0] = 1
    return y ** 2

def f():
    squares = list(map(lambda x: fun_with_side_effects(x), range(10)))

f()

The IR for f():

callees of node f : [range, list]

IR of node 3, context CallStringContext: [ script A.py.do()LRoot;@113 ]
<Code body of function Lscript A.py/f>
CFG:
BB0[-1..-2]
    -> BB1
BB1[0..6]
    -> BB2
    -> BB5
BB2[7..7]
    -> BB3
    -> BB5
BB3[8..8]
    -> BB4
    -> BB5
BB4[9..9]
    -> BB5
BB5[-1..-2]
Instructions:
BB0
BB1
0   v5 = lexical:list@Lscript A.py           A.py [12:14] -> [12:18]
1   v8 = lexical:map@Lscript A.py            A.py [12:19] -> [12:22]
2   v10 = new <PythonLoader,Lscript A.py/f/lambda1>@2<no information>
3   global:global script A.py/f/lambda1 = v10<no information>
4   putfield v1.< PythonLoader, LRoot, lambda1, <PythonLoader,LRoot> > = v10<no information> [1=[the function]]
5   v15 = lexical:range@Lscript A.py         A.py [12:59] -> [12:64]
6   v13 = invokeFunction < PythonLoader, LCodeBody, do()LRoot; > v15,v16:#10 @6 exception:v17A.py [12:59] -> [12:68]
BB2
7   v6 = invokeFunction < PythonLoader, LCodeBody, do()LRoot; > v8,v10,v13 @7 exception:v18A.py [12:19] -> [12:69]
BB3
8   v3 = invokeFunction < PythonLoader, LCodeBody, do()LRoot; > v5,v6 @8 exception:v19A.py [12:14] -> [12:70] [3=[squares]]
BB4
BB5

So far so good. For comparison, we can compare list() above, that is not missing (FYI). But, in the pointer analysis, map() maps to nothing:

[Node: <Code body of function Lscript A.py/f> Context: CallStringContext: [ script A.py.do()LRoot;@113 ], v8] --> []

By contrast, list() is populated:

[Node: <Code body of function Lscript A.py/f> Context: CallStringContext: [ script A.py.do()LRoot;@113 ], v5] --> [[com.ibm.wala.cast.python.ipa.summaries.BuiltinFunctions$BuiltinFunction@9053b33]]

One consequence of this issue is that a lambda given to map() is not showing in the call graph. In other words, there is no call graph node for the lambda above, and subsequently, we have no node for fun_with_side_effects either.

Digression

  1. The map() function returns an iterator, but there is no such type in PythonTypes. We would seemingly have to add it.
  2. List comprehensions do work, and I would think lambdas would be similar if they are not also implemented. It's just tough to see if they are if the functions that take them as arguments aren't implemented.