path: root/monkey/edits.py

#!/usr/bin/python3

import collections
import math

from .action import expand, parse
from .graph import Node
from prolog.util import normalized, rename_vars, stringify, tokenize
from .util import get_line, avg, logistic

# Parse the sequence of actions in [trace] and return a directed acyclic graph
# representing development history. Each node represents a particular version
# of some line, and each edge represents a "line edit" (contiguous sequence of
# inserts/removes within a single line).
# Return a list of nodes (first element is the root), and sets of submissions
# (program versions tested by the user) and queries in this attempt.
def trace_graph(trace, debug=False):
    # Return values.
    nodes = [Node([0, 0, ()])]  # Node data: rank (Y), line no. (X), and tokens.
    submissions = set()         # Program versions at 'test' actions.
    queries = set()             # Queries run by the student.

    # State variables.
    leaves = {0: nodes[0]}  # Current leaf node for each line.
    rank = 1                # Rank (order / y-position) for the next node.
    code_next = ''          # Program code after applying the current action.
    done = False            # Set to True on first correct version.

    # Parse trace actions and ensure there is a separate action for each
    # inserted/removed character.
    try:
        actions = parse(trace)
        expand(actions)
    except:
        # Only a few traces fail to parse, so just skip them.
        actions = []

    for action_id, action in enumerate(actions):
        code = code_next
        code_next = action.apply(code)

        if action.type == 'test':
            submissions.add(code)
            if action.total == action.passed:
                done = True

        elif action.type == 'solve' or action.type == 'solve_all':
            queries.add(action.query)

        elif action.type == 'insert' or action.type == 'remove':
            # Ignore edits after the first correct version.
            if done:
                continue

            # Number of the changed line.
            line = code[:action.offset].count('\n')
            # Current leaf node for this line.
            parent = leaves[line]
            # Tokens in this line after applying [action].
            tokens_next = tuple(tokenize(get_line(code_next, line)))

            # If a new node is inserted, clone each leaf into the next rank.
            # This makes it easier to print the graph for graphviz; when
            # analyzing the graph, duplicate nodes without siblings should be
            # ignored.
            new_leaves = {}

            if action.text == '\n':
                if action.type == 'insert':
                    tokens_next_right = tuple(tokenize(get_line(code_next, line+1)))

                    child_left = Node([rank, line, tokens_next])
                    parent.add_out(child_left)

                    child_right = Node([rank, line+1, tokens_next_right])
                    parent.add_out(child_right)

                    # Create new leaf nodes.
                    for i, leaf in leaves.items():
                        if i < line:
                            new_leaves[i] = Node([rank, i, leaf.data[2]])
                            leaf.add_out(new_leaves[i])
                        elif i > line:
                            new_leaves[i+1] = Node([rank, i+1, leaf.data[2]])
                            leaf.add_out(new_leaves[i+1])
                    new_leaves[line] = child_left
                    new_leaves[line+1] = child_right

                elif action.type == 'remove':
                    parent_right = leaves[line+1]

                    child = Node([rank, line, tokens_next])
                    parent_right.add_out(child)
                    parent.add_out(child)

                    # Create new leaf nodes.
                    for i, leaf in leaves.items():
                        if i < line:
                            new_leaves[i] = Node([rank, i, leaf.data[2]])
                            leaf.add_out(new_leaves[i])
                        elif i > line+1:
                            new_leaves[i-1] = Node([rank, i-1, leaf.data[2]])
                            leaf.add_out(new_leaves[i-1])
                    new_leaves[line] = child
            else:
                # Skip the node if the next action is insert/remove (except \n)
                # on the same line.
                if action_id < len(actions)-1:
                    action_next = actions[action_id+1]
                    if action_next.type in ('insert', 'remove'):
                        line_next = code_next[:action_next.offset].count('\n')
                        if action_next.text != '\n' and line == line_next:
                            continue

                # Skip the node if it is the same as the parent.
                if tokens_next == parent.data[2]:
                    continue

                child = Node([rank, line, tokens_next])
                parent.add_out(child)

                # Create new leaf nodes.
                for i, leaf in leaves.items():
                    if i != line:
                        new_leaves[i] = Node([rank, i, leaf.data[2]])
                        leaf.add_out(new_leaves[i])
                new_leaves[line] = child

            leaves = new_leaves
            nodes += leaves.values()
            rank += 1

    return nodes, submissions, queries

# Generate all interesting paths in the edit graph rooted at [root].
def get_paths(root, path=None, done=None):
    if done is None:
        done = set()

    # Add [root] to [path] if it is the first node or different than previous.
    if not path:
        path = (root.data[2],)
    elif root.data[2] != path[-1]:
        path = path + (root.data[2],)

    # Return the current path if [root] is a leaf or an empty node.
    if len(path) > 1:
        if not root.eout or not root.data[2]:
            yield path

    # If [root] is an empty node, start a new path.
    if not root.data[2]:
        path = (root.data[2],)
        done.add(root)

    for node in root.eout:
        if node not in done:
            yield from get_paths(node, path, done)

# Build an edit graph for each trace and find "meaningful" (to be defined)
# edits. Return a dictionary of edits and their frequencies, and also
# submissions and queries in [traces].
def get_edits_from_traces(traces):
    # Return values: counts for observed edits, lines, submissions and queries.
    edits = collections.Counter()
    submissions = collections.Counter()
    queries = collections.Counter()

    # Counts of traces where each line appears as a leaf / any node.
    n_leaf = collections.Counter()
    n_all = collections.Counter()

    for trace in traces:
        nodes, trace_submissions, trace_queries = trace_graph(trace)

        # Update the submissions/queries counters (use normalized variables).
        for submission in trace_submissions:
            code = stringify(rename_vars(tokenize(submission)))
            submissions[code] += 1
        for query in trace_queries:
            code = stringify(rename_vars(tokenize(query)))
            queries[code] += 1

        # Get edits.
        trace_edits = set()
        for path in get_paths(nodes[0]):
            for i in range(1, len(path)):
                # Normalize path[i-1] → path[i] into start → end. Reuse
                # variable names from start when normalizing end.
                var_names = {}
                start = normalized(path[i-1], var_names)
                end = normalized(path[i], var_names)

                # Disallow edits that insert a whole rule (a → … :- …).
                # TODO improve trace_graph to handle this.
                if 'FROM' in [t.type for t in end[:-1]]:
                    continue

                # This should always succeed but check anyway.
                if start != end:
                    edit = (start, end)
                    trace_edits.add(edit)
        edits.update(trace_edits)

        # Update node counts.
        n_leaf.update(set([normalized(n.data[2]) for n in nodes if n.data[2] and not n.eout]))
        n_all.update(set([normalized(n.data[2]) for n in nodes if n.data[2]]))

    # Discard edits that only occur in one trace.
    singletons = [edit for edit in edits if edits[edit] < 2]
    for edit in singletons:
        del edits[edit]

    # Find the probability of each edit a → b.
    for (a, b), count in edits.items():
        p = 1.0
        if a:
            p *= 1 - (n_leaf[a] / (n_all[a]+1))
        if b:
            b_normal = normalized(b)
            p *= n_leaf[b_normal] / (n_all[b_normal]+1)
        if a and b:
            p = math.sqrt(p)
        edits[(a, b)] = p

    # Tweak the edit distribution to improve search.
    avg_p = avg(edits.values())
    for edit, p in edits.items():
        edits[edit] = logistic(p, k=3, x_0=avg_p)

    lines = dict(n_leaf)

    return edits, lines, submissions, queries

def classify_edits(edits):
    inserts = {}
    removes = {}
    changes = {}
    for (before, after), cost in edits.items():
        if after and not before:
            inserts[after] = cost
        elif before and not after:
            removes[before] = cost
        else:
            changes[(before, after)] = cost
    return inserts, removes, changes

if __name__ == '__main__':
    import os
    import pickle
    import django

    # Load django models.
    os.environ['DJANGO_SETTINGS_MODULE'] = 'webmonkey.settings'
    django.setup()
    from django.contrib.auth.models import User
    from tutor.models import Attempt, Problem

    edits = {}
    lines = {}
    submissions = {}
    queries = {}
    for problem in Problem.objects.all():
        print(problem.name)
        pid = problem.pk
        traces = [a.trace for a in Attempt.objects.filter(problem=problem, done=True)]
        edits[pid], lines[pid], submissions[pid], queries[pid] = get_edits_from_traces(traces)

    pickle.dump((edits, lines, submissions, queries), open('edits.pickle', 'wb'))