summaryrefslogtreecommitdiff
path: root/monkey/rules.py
blob: d3bdf714f845559f06985e6441461967ed9d4957 (plain)
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
# CodeQ: an online programming tutor.
# Copyright (C) 2017 UL FRI
#
# This program is free software: you can redistribute it and/or modify it under
# the terms of the GNU Affero General Public License as published by the Free
# Software Foundation, either version 3 of the License, or (at your option) any
# later version.
#
# This program is distributed in the hope that it will be useful, but WITHOUT
# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
# FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
# details.
#
# You should have received a copy of the GNU Affero General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.

import collections

from nltk import Tree

from .patterns import get_patterns

# return a hint for the best applicable buggy rule
def suggest_buggy(bugs, program, patterns):
    for rule in [r for r in bugs['rules'] if not r['class']]:
        matches = []
        for rule_pattern in rule['condition']:
            for pattern, nodes in patterns:
                if rule_pattern == pattern:
                    matches.append((pattern, nodes))
                    break

        # found a rule, now do the cha-cha-hint
        if len(matches) == len(rule['condition']):
            hints = []
            for pattern, nodes in matches:
                # find subtrees to point out to student
                top_nodes = []
                for node in nodes:
                    # highlight the node
                    hints.append({'id': 'monkey_highlight', 'start': node.start, 'end': node.end})
                    # find top-level clause (or similar) node containing the highlighted node
                    while node.parent().label() in {'compound', 'binop', 'unop', 'args', 'list', 'h', 't'}:
                        node = node.parent()
                    if not any(n is node for n in top_nodes):
                        top_nodes.append(node)

                hint = {'args': {'fragments': [program[n.start:n.end] for n in top_nodes]}}
                if all(isinstance(n, Tree) and n.label() == 'variable' for n in nodes):
                    # two instances of a variable
                    hint['id'] = 'monkey_singleton' if len(nodes) == 1 else 'monkey_buggy_variable'
                    hint['args']['variable'] = str(nodes[0][0])
                else:
                    # a literal and another literal/variable in the same clause
                    hint['id'] = 'monkey_buggy_literal'
                    hint['args']['literals'] = [program[n.start:n.end] for n in nodes]
                hints.append(hint)
            return hints
    return None

# return a hint from rules with the most matching patterns
# (most common nonmatching pattern is used as hint)
def suggest_true(bugs, program, patterns):
    # find a list of found / missing patterns for each intent rule
    matches = collections.defaultdict(list)
    for rule in [r for r in bugs['rules'] if r['class']]:
        match = {True: [], False: []}  # lists of found / missing patterns
        for rule_pattern in rule['condition']:
            found = any(pattern == rule_pattern for pattern, nodes in patterns)
            match[found].append(rule_pattern)
        n_found = len(match[True])
        matches[n_found].append(match)

    # we want at least two matching patterns to consider hinting
    if max(matches) < 2:
        return None

    # consider only rules that have maximum matching patterns
    candidate_rules = matches[max(matches)]

    # if there is candidate a with no missing patterns, the program should
    # already be correct, so do not try hinting because we know nothing
    if any(not match[False] for match in candidate_rules):
        return None

    # find the number of candidate rules missing each pattern
    missing_patterns = collections.Counter()
    for match in candidate_rules:
        for pattern in match[False]:
            missing_patterns[pattern] += 1

    # consider only the most commonly missing patterns
    max_count = max(missing_patterns.values())
    candidate_patterns = [pattern for pattern, count in missing_patterns.items() if count == max_count]

    # find the most common (in the learning set) pattern among the candidates
    for pattern in bugs['patterns']:
        if pattern in candidate_patterns:
            return [{'id': 'monkey_missing'}]
    return None

# check if any pattern in the program has not been observed before, and return as buggy
def suggest_unknown_pattern(bugs, program, patterns):
    hints = []
    top_nodes = []
    for pattern, nodes in patterns:
        if len(nodes) == 2 and pattern not in bugs['patterns']:
            for node in nodes:
                # highlight the node
                hints.append({'id': 'monkey_highlight', 'start': node.start, 'end': node.end})
                # find top-level clause (or similar) node containing the highlighted node
                while node.parent().label() in {'compound', 'binop', 'unop', 'args', 'list', 'h', 't'}:
                    node = node.parent()
                if not any(n is node for n in top_nodes):
                    top_nodes.append(node)
            break  # report only one pattern at a time
    if hints:
        hints.append({
            'id': 'monkey_unknown',
            'args': {'fragments': [program[n.start:n.end] for n in top_nodes]}
        })
        return hints
    return None

def suggest(bugs, program):
    try:
        patterns = list(get_patterns(program))
        hints = suggest_buggy(bugs, program, patterns)
        if not hints:
            hints = suggest_true(bugs, program, patterns)
        if not hints:
            hints = suggest_unknown_pattern(bugs, program, patterns)
        return hints
    except:
        # should never happen
        return None