public
Last active

  • Download Gist
stacksort.py
Python
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
#!/usr/bin/env python
 
import ast
import inspect
import copy
import stackexchange
import BeautifulSoup
 
namegen_count = 0
def namegen():
global namegen_count
namegen_count += 1
return 'name_%d' % namegen_count
 
def is_sorted(l):
try:
return all(l[i] <= l[i+1] for i in xrange(len(l)-1))
except:
return False
 
# Some samples
s1 = 'rows.sort()'
s2 = 'return sorted(rows)'
s3 = 'def dothesort(rows): return sorted(rows)'
 
class FunctionVisitor(ast.NodeVisitor):
def __init__(self):
super(FunctionVisitor , self).__init__()
self.functions_found = []
def visit_FunctionDef(self, node):
func_name = node.name
 
# Build a Module to contain it, as that's what compile expects
code_obj = compile(ast.Module(body=[node]), 'stackoverflow', 'exec')
# Evaluate it and get the compiled function out
 
gdict = {} # Globals dict
try:
# XXX: THIS IS THE DANGEROUS PART
eval(code_obj, gdict)
except:
return
func = gdict[func_name]
 
# Check that the function could be called as func(arg)
argspec = inspect.getargspec(func)
if argspec.defaults is not None:
defargs, nondefargs = (argspec.args[-len(argspec.defaults):],
argspec.args[:-len(argspec.defaults)])
else:
defargs = []
nondefargs = argspec.args
 
if len(nondefargs) == 1 or (len(nondefargs) == 0 and defarg_len > 0):
self.functions_found.append(func)
 
class NameVisitor(ast.NodeVisitor):
def __init__(self):
super(NameVisitor , self).__init__()
self.names_found = []
def visit_Name(self, node):
self.names_found.append(node.id)
 
def make_functions(s):
"""Makes function(s) out of an arbitrary snippet of code by
trying a few different heuristics.
"""
 
func_candidates = []
 
try:
parsed = ast.parse(s)
except SyntaxError:
return []
 
# First try: run all functions with appropriate arity
fv = FunctionVisitor()
fv.visit(parsed)
func_candidates += fv.functions_found
 
# Second try: get names of possible arguments, and make a function
nv = NameVisitor()
nv.visit(parsed)
newmod = ast.Module(body=[])
for name in nv.names_found:
fdef = ast.FunctionDef(
name=namegen(),
args=ast.arguments(
args=[ast.Name(id=name,ctx=ast.Param())],
defaults=[]
),
body=parsed.body,
decorator_list=[],
)
newmod.body.append(fdef)
 
newmod = ast.fix_missing_locations(newmod)
fv = FunctionVisitor()
fv.visit(newmod)
func_candidates += fv.functions_found
 
return func_candidates
 
def try_functions(test_data, funcs, oracle, byref=True):
"""Try a list of funcs to see if test_data satisfies some
(arity 1) oracle. If byref is True, then assume the function
might modify its input and try oracle on the input as well.
"""
for func in funcs:
try:
lcopy = copy.copy(test_data)
res = func(lcopy)
# Returns the answer?
if oracle(res): return res
# Modifies the input in place?
if byref and oracle(lcopy): return lcopy
except: pass
return None
 
def try_tests(test_data, answers, funcs):
"""Try a list of funcs to see if a list of test_data produces the correct
answers.
"""
assert len(test_data) == len(answers)
 
for func in funcs:
results = []
for test, ans in zip(test_data, answers):
try:
results.append(func(test))
except:
pass
 
if len(results) != len(answers): continue
 
if all(res == ans for res,ans in zip(results, answers)): return True
return None
 
def extract_snippets(body):
soup = BeautifulSoup.BeautifulSoup(body)
for c in soup.findAll('code'):
# Try interpreter text as well
snippet = c.text.replace('&gt;&gt;&gt; ','')
yield snippet
 
def search_so(query):
snippets = []
so = stackexchange.StackOverflow()
so.be_inclusive() # Fetch answer bodies
#so.impose_throttling = True # Be polite
res = so.search(tagged=['python'], intitle=query)
for question in res:
print "Checking answers for: '%s'" % question
question.fetch()
# Maybe the submitter got it right?
for snip in extract_snippets(question.body): yield snip
# Ok, then maybe one of the answers is correct
for ans in question.answers:
for snip in extract_snippets(ans.body): yield snip
def main(oracle, test_data, query):
for snip in search_so(query):
candidates = make_functions(snip)
res = try_functions(test_data,candidates,oracle)
if res:
print "Success with:"
print snip
print res
break
 
def main2(test_data, answers, query):
for snip in search_so(query):
candidates = make_functions(snip)
res = try_tests(test_data, answers, candidates)
if res:
print "Success with:"
print snip
break
 
if __name__ == "__main__":
main(is_sorted, [2,5,6,3,1], "sort a list")
#nums = [37, 2, 10, 7, 99]
#primes = [True, True, False, True, False]
#main2(nums, primes, "primality")

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.