zefancainlp's picture
download
raw
4.85 kB
"""Structured live-in/may-write/must-write analysis for Python regions.
Counting every identifier as an input is unsound: a region that initializes a
variable cannot be replaced by one that merely reads an existing value.
"""
import ast
def target_names(node):
if isinstance(node,ast.Name):return {node.id}
if isinstance(node,(ast.Tuple,ast.List)):return set().union(*(target_names(n)for n in node.elts))
if isinstance(node,ast.Starred):return target_names(node.value)
return set()
def analyze(nodes,local,defined=None,loop_depth=0):
known=set(defined or());reads=set();may=set();must=set();exits=set()
def expression(n,scope=None):
if n is None:return
bound=known if scope is None else scope
for x in ast.walk(n):
if isinstance(x,ast.Name)and isinstance(x.ctx,ast.Load)and x.id in local and x.id not in bound:reads.add(x.id)
def mutation_target(n):
if isinstance(n,(ast.Subscript,ast.Attribute)):
expression(n)
while isinstance(n,(ast.Subscript,ast.Attribute)):n=n.value
if isinstance(n,ast.Name)and n.id in local:may.add(n.id);must.add(n.id)
def branch(body,start,depth=loop_depth):
r,w,m,end,e=analyze(body,local,start,depth);reads.update(r);may.update(w);exits.update(e);return m,end
for node in nodes:
if isinstance(node,ast.Assign):
expression(node.value)
for target in node.targets:
names=target_names(target)&local;may|=names;must|=names;known|=names;mutation_target(target)
elif isinstance(node,ast.AnnAssign):
if node.value is not None:expression(node.value);names=target_names(node.target)&local;may|=names;must|=names;known|=names;mutation_target(node.target)
elif isinstance(node,ast.AugAssign):
expression(node.target);expression(node.value)
if isinstance(node.target,ast.Name)and node.target.id in local:
if node.target.id not in known:reads.add(node.target.id)
may.add(node.target.id);must.add(node.target.id);known.add(node.target.id)
else:mutation_target(node.target)
elif isinstance(node,ast.If):
expression(node.test);m1,k1=branch(node.body,known);m2,k2=branch(node.orelse,known);must|=m1&m2;known=k1&k2
elif isinstance(node,(ast.For,ast.AsyncFor)):
expression(node.iter);bound=target_names(node.target)&local;may|=bound;branch(node.body,known|bound,loop_depth+1);branch(node.orelse,known)
elif isinstance(node,ast.While):expression(node.test);branch(node.body,known,loop_depth+1);branch(node.orelse,known)
elif isinstance(node,(ast.With,ast.AsyncWith)):
for item in node.items:
expression(item.context_expr);bound=target_names(item.optional_vars)&local if item.optional_vars else set();known|=bound;may|=bound;must|=bound
m,end=branch(node.body,known);must|=m;known=end
elif isinstance(node,ast.Try):
states=[];writes=[];m,k=branch(node.body,known);m2,k2=branch(node.orelse,k);states.append(k2);writes.append(m|m2)
for handler in node.handlers:
expression(handler.type);bound={handler.name}if handler.name else set();m,k=branch(handler.body,known|bound);states.append(k-bound);writes.append(m-bound)
if states:known=set.intersection(*states);must|=set.intersection(*writes)
m,k=branch(node.finalbody,known);must|=m;known=k
elif isinstance(node,ast.Return):expression(node.value);exits.add('return')
elif isinstance(node,ast.Break):
if loop_depth==0:exits.add('break')
elif isinstance(node,ast.Continue):
if loop_depth==0:exits.add('continue')
elif isinstance(node,(ast.FunctionDef,ast.AsyncFunctionDef,ast.ClassDef)):
for d in node.decorator_list:expression(d)
if isinstance(node,(ast.FunctionDef,ast.AsyncFunctionDef)):
for value in node.args.defaults+node.args.kw_defaults:expression(value)
if node.name in local:known.add(node.name);may.add(node.name);must.add(node.name)
elif isinstance(node,(ast.Import,ast.ImportFrom)):
bound={n.asname or n.name.split('.')[0]for n in node.names}&local;known|=bound;may|=bound;must|=bound
elif isinstance(node,ast.Delete):
for target in node.targets:
names=target_names(target)&local
for name in names:
if name not in known:reads.add(name)
may|=names;known-=names;mutation_target(target)
else:expression(node)
for call in ast.walk(node):
if isinstance(call,ast.Call)and isinstance(call.func,ast.Name)and call.func.id=='print':may.add('@stdout');must.add('@stdout')
return reads,may,must,known,exits

Xet Storage Details

Size:
4.85 kB
·
Xet hash:
d4560a9ea3c936cb8f9d607c72c1ea9f039fd23c3e279dc96f544ae6b452b05b

Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.