zefancainlp's picture
download
raw
7.99 kB
"""The same source graph, with automatically discovered caller-region moves."""
import copy,json,itertools
from source_graph import Family,sha
from regions import discover,replace,overlaps
class RegionFamily(Family):
def __init__(self,sources,entry,base):
super().__init__(sources,entry,base);self.regions={key:discover(s.text)for key,s in self.sources.items()};self.by_contract={}
for provider,regions in self.regions.items():
for key,r in regions.items():self.by_contract.setdefault(r.contract,[]).append((provider,key))
def initial(self,source=None):return dict(root=source or self.base,patches={},regions={})
def canonical(self,config):
c=super().canonical(config);chosen={};active=[]
for key,value in sorted(config.get('regions',{}).items()):
provider,donorkey=value
r=self.regions[c['root']][key];d=self.regions[provider][donorkey]
if r.contract!=d.contract:raise ValueError('source-region local-state/control contract differs')
if r.function!='@module'and(r.function not in self.active_ports(c)or r.function in c['patches']):raise ValueError('caller region is hidden inside a replaced/closed implementation')
if any(overlaps(r,x)for x in active):raise ValueError('overlapping source edits must form one enclosing region')
active.append(r);chosen[key]=[provider,donorkey]
c['regions']=chosen;return c
def identity(self,config):
c=self.canonical(config);parent=super().identity(c);parts={}
for key,(p,k)in c['regions'].items():
r=self.regions[p][k];names=r.writes if r.function=='@module'and r.writes<=self.sources[p].binding_identities.keys()else r.global_names
parts[key]=[r.fingerprint,{name:self.sources[p].global_fingerprint(name)for name in names}]
return sha(json.dumps(dict(parent=parent,regions=parts),sort_keys=True))
def proposals(self,config):
c=self.canonical(config);seen={self.identity(c)}
# Whole caller regions first, followed by increasingly fine regions.
# Larger dependency closures retain co-designed preparation and use.
original_active=(self.active_ports(c)-c['patches'].keys())|{'@module'}
eligible=sorted(((k,r)for k,r in self.regions[c['root']].items()if r.function in original_active),key=lambda kv:(len(kv[1].path),kv[0]));buckets={}
for pair in eligible:buckets.setdefault(len(pair[1].nodes),[]).append(pair)
# Cover both complete contexts and fine edits in a finite budget.
# Region size is a source property, independent of any task or score.
streams=[iter(buckets[k])for k in sorted(buckets,reverse=True)];pool=[]
while streams:
remaining=[]
for stream in streams:
try:pool.append(next(stream));remaining.append(stream)
except StopIteration:pass
streams=remaining
def moves_at(key,r):
# Whole-function transplantation is already represented by a
# function/component move; do not sell it as a new region.
if not r.path and r.start==0 and r.stop==self.sources[c['root']].statement_count(r.function):return
for provider,donorkey in self.by_contract.get(r.contract,[]):
donor=self.regions[provider][donorkey]
dnames=donor.writes if donor.function=='@module'and donor.writes<=self.sources[provider].binding_identities.keys()else donor.global_names
rnames=r.writes if r.function=='@module'and r.writes<=self.sources[c['root']].binding_identities.keys()else r.global_names
same=(donor.fingerprint==r.fingerprint and {n:self.sources[provider].global_fingerprint(n)for n in dnames}=={n:self.sources[c['root']].global_fingerprint(n)for n in rnames})
if provider==c['root']or same:continue
regions={k:v for k,v in c['regions'].items()if not overlaps(r,self.regions[c['root']][k])};regions[key]=[provider,donorkey]
# Source-owned implementation/state dependencies form a
# coarse transaction. Its finer single-binding move also
# remains available for cross-context correction.
if r.function=='@module':
required=set();todo=list(donor.writes)
while todo:
name=todo.pop()
for dep in self.sources[provider].binding_requires.get(name,[]):
if dep not in required:required.add(dep);todo.append(dep)
joint=copy.deepcopy(regions)
for name in required:
rr=next(((rk,x)for rk,x in self.regions[c['root']].items()if x.function=='@module'and x.writes=={name}),None)
dd=next(((dk,x)for dk,x in self.regions[provider].items()if x.function=='@module'and x.writes=={name}),None)
if rr and dd and rr[1].contract==dd[1].contract:joint[rr[0]]=[provider,dd[0]]
if joint!=regions:yield dict(c,regions=joint)
yield dict(c,regions=regions)
def region_moves():
tiers={0:[],1:[],2:[]}
for key,r in pool:
tier=0 if r.function=='@module'else 1 if len(r.nodes)==1 else 2
tiers[tier].append(iter(moves_at(key,r)))
# Fairness is applied to actual proposals, not just region names:
# one region with many donors cannot monopolize the first batch.
while any(tiers.values()):
for tier in [0,1,2]:
while tiers[tier]:
stream=tiers[tier].pop(0)
try:value=next(stream)
except StopIteration:continue
tiers[tier].append(stream);yield value;break
def function_moves():
for v in super(RegionFamily,self).proposals(c):
v['regions']=copy.deepcopy(c['regions']);yield v
# Both granularities receive queries; a large helper library cannot
# hide the caller/control regions at the end of a finite budget.
for pair in itertools.zip_longest(region_moves(),function_moves()):
for v in pair:
if v is None:continue
try:identity=self.identity(v)
except ValueError:continue
if identity in seen:continue
seen.add(identity);yield v
def emit(self,config):
c=self.canonical(config)
if not c['regions']:return super().emit(c)
edits=[];owners={}
for i,(key,(p,k))in enumerate(c['regions'].items()):
symbol='_sg_region_owner_'+str(i);owners[symbol]=p;edits.append((self.regions[c['root']][key],self.regions[p][k],symbol))
modified=replace(self.sources[c['root']].text,edits)
raw=super().emit(c)
# Provider namespaces are instantiated before the receiving source;
# globals in the donor region are explicit, local variables stay local.
raw=raw.replace("_sg_spec['sources'][provider]", "(_sg_modified if provider==_sg_spec['config']['root'] and owner=='root' else _sg_spec['sources'][provider])")
raw=raw.replace(" root=instance(_sg_spec['config']['root'],'root')", " for symbol,provider in _sg_region_owners.items():_context[symbol]=instance(provider,'region:'+symbol)\n root=instance(_sg_spec['config']['root'],'root')")
return '_sg_modified='+repr(modified)+'\n_sg_region_owners='+repr(owners)+'\n'+raw
def manifest(self):
out=super().manifest();out['regions']={p:{k:dict(function=r.function,path=r.path,start=r.start,stop=r.stop,reads=sorted(r.reads),writes=sorted(r.writes),exits=sorted(r.exits),spine=r.spine)for k,r in rows.items()}for p,rows in self.regions.items()};return out

Xet Storage Details

Size:
7.99 kB
·
Xet hash:
94f70d8beb2b0800a61355ca8c005496fbb9c22f6cd48c206f392c232548c63e

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