From 82b0b605dc1f67f728478781f830eebbbce39d5f Mon Sep 17 00:00:00 2001
From: Timotej Lazar <timotej.lazar@araneo.org>
Date: Thu, 29 Jan 2015 17:51:53 +0100
Subject: Refactor monkey.monkey.fix

---
 monkey/monkey.py | 93 +++++++++++++++++++++++++++++---------------------------
 1 file changed, 48 insertions(+), 45 deletions(-)

(limited to 'monkey')

diff --git a/monkey/monkey.py b/monkey/monkey.py
index 5d26c6e..ef4ac2c 100755
--- a/monkey/monkey.py
+++ b/monkey/monkey.py
@@ -26,49 +26,10 @@ def fix(name, code, edits, aux_code='', timeout=30, debug=False):
     todo = PQueue()  # priority queue of candidate solutions
     done = set()     # set of already-analyzed solutions
 
-    # Add a new candidate solution ([lines]+[rules]) to the priority queue.
-    # This solution is generated by applying [step] with [cost] to [prev] task.
-    def add_task(lines, rules, prev=None, step=None, cost=None):
-        if prev is None:
-            path = ()
-            path_cost = 1.0
-        else:
-            path = tuple(list(prev[1]) + [step])
-            path_cost = prev[2] * cost
-        todo.push(((tuple(lines), tuple(rules)), path, path_cost), -path_cost)
-
-    lines, rules = decompose(code)
-    add_task(lines, rules)
-
     inserts, removes, changes = classify_edits(edits)
-    start_time = time.monotonic()
-    n_tested = 0
-    while True:
-        total_time = time.monotonic() - start_time
-        if total_time > timeout:
-            break
-
-        task = todo.pop()
-        if task == None:
-            break
 
-        (lines, rules), path, path_cost = task
-        code = compose(lines, rules)
-        if code in done:
-            continue
-        done.add(code)
-
-        if debug:
-            print('Cost {:.12f}'.format(path_cost))
-            for line, (before, after) in path:
-                print('line ' + str(line) + ':\t' + stringify(before) + ' → ' + stringify(after))
-
-        # If the code is correct, we are done.
-        if test(name, code + '\n' + aux_code):
-            return code, path, total_time, n_tested
-        n_tested += 1
-
-        # Otherwise generate new solutions.
+    # Generate states that can be reached from (lines, rules) with one edit.
+    def step(lines, rules):
         rule_no = 0
         for start, end in rules:
             rule = lines[start:end]
@@ -90,7 +51,7 @@ def fix(name, code, edits, aux_code='', timeout=30, debug=False):
                         new_lines = lines[:line_idx] + (after_real,) + lines[line_idx+1:]
                         new_step = ((rule_no, line_idx-start), (tuple(line), after_real))
 
-                        add_task(new_lines, rules, prev=task, step=new_step, cost=cost)
+                        yield (new_lines, rules, new_step, cost)
 
                 # if nothing could be done with this line, try removing it
                 # (maybe try removing in any case?)
@@ -105,7 +66,7 @@ def fix(name, code, edits, aux_code='', timeout=30, debug=False):
                     new_step = ((rule_no, line_idx-start), (tuple(line), ()))
                     new_cost = removes[line_normal] if line_normal in removes.keys() else 0.9
 
-                    add_task(new_lines, new_rules, prev=task, step=new_step, cost=new_cost)
+                    yield (new_lines, new_rules, new_step, new_cost)
 
             # try adding a line to this rule… would need to distinguish between
             # head/body lines in transforms
@@ -120,7 +81,7 @@ def fix(name, code, edits, aux_code='', timeout=30, debug=False):
                                       old_end + (0 if old_end < end else 1)))
                 new_step = ((rule_no, end-start), ((), after_real))
 
-                add_task(new_lines, new_rules, prev=task, step=new_step, cost=cost)
+                yield (new_lines, new_rules, new_step, cost)
             rule_no += 1
 
         # try adding a new fact
@@ -130,6 +91,48 @@ def fix(name, code, edits, aux_code='', timeout=30, debug=False):
                 new_rules = rules + (((len(lines), len(lines)+1)),)
                 new_step = ((len(new_rules)-1, 0), (tuple(), tuple(after)))
 
-                add_task(new_lines, new_rules, prev=task, step=new_step, cost=cost)
+                yield (new_lines, new_rules, new_step, cost)
+
+    # Add the initial program to the queue.
+    lines, rules = decompose(code)
+    todo.push(((tuple(lines), tuple(rules)), (), 1.0), -1.0)
+
+    start_time = time.monotonic()
+    n_tested = 0
+    while True:
+        # Have we been at it for too long?
+        total_time = time.monotonic() - start_time
+        if total_time > timeout:
+            break
+
+        # Get next candidate.
+        task = todo.pop()
+        if task == None:
+            break
+        (lines, rules), path, path_cost = task
+
+        # If we have already seen this code, skip it.
+        code = compose(lines, rules)
+        if code in done:
+            continue
+        done.add(code)
+
+        if debug:
+            print('Cost {:.12f}'.format(path_cost))
+            for line, (before, after) in path:
+                print('line ' + str(line) + ':\t' + stringify(before) + ' → ' + stringify(after))
+
+        # If the code is correct, we are done.
+        if test(name, code + '\n' + aux_code):
+            return code, path, total_time, n_tested
+        n_tested += 1
+
+        # Otherwise generate new solutions.
+        path = list(path)
+        for new_lines, new_rules, new_step, new_cost in step(lines, rules):
+            new_path = tuple(path + [new_step])
+            new_path_cost = path_cost * new_cost * 0.99
+            if new_path_cost > 0.005:
+                todo.push(((tuple(new_lines), tuple(new_rules)), new_path, new_path_cost), -new_path_cost)
 
     return '', [], total_time, n_tested
-- 
cgit v1.2.1