diff options
| -rw-r--r-- | monkey/patterns.py | 149 | ||||
| -rw-r--r-- | monkey/rules.py | 131 | ||||
| -rw-r--r-- | server/problems.py | 8 | ||||
| -rw-r--r-- | server/prolog_session.py | 30 |
4 files changed, 296 insertions, 22 deletions
diff --git a/monkey/patterns.py b/monkey/patterns.py new file mode 100644 index 0000000..7dfa96f --- /dev/null +++ b/monkey/patterns.py @@ -0,0 +1,149 @@ +# CodeQ: an online programming tutor. +# Copyright (C) 2016,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 itertools import chain, combinations, product + +from nltk import Tree + +from prolog.util import parse as prolog_parse + +# construct pattern to match the structure of nodes given by [include], +# supports variables and literals +def pattern(node, include): + if not isinstance(node, Tree): + return None + + label = node.label() + if any(n is node for n in include): + if label == 'literal': + return '"{}"'.format(node[0].val) + if label == 'variable': + return '{}'.format(label) + return None + if label == 'functor': + return '({} "{}")'.format(label, node[0].val) + + subpats = [pattern(child, include) for child in node] + pat = None + if any(subpats): + if label == 'and': + if subpats[1]: + pat = subpats[1] + if subpats[0]: + if pat: + pat = subpats[0] + ' ' + pat + else: + pat = subpats[0] + elif label == 'args': + pat = label + for i, subpat in enumerate(subpats): + if subpat: + pat += ' {}'.format(subpat) + pat = '(' + pat + ')' + elif label == 'unop': + pat = '(' + label + ' ' + node[0].val + ' ' + subpats[1] + ')' + elif label == 'binop': + pat = label + if subpats[0]: + pat += ' {}'.format(subpats[0]) + pat += ' "{}"'.format(node[1].val) + if subpats[2]: + pat += ' {}'.format(subpats[2]) + pat = '(' + pat + ')' + elif label == 'clause': + pat = label + for i, subpat in enumerate(subpats): + if subpat: + pat += ' {}'.format(subpats[i]) + return '(' + pat + ')' + elif label == 'compound': + if len(subpats) > 1 and subpats[1]: + pat = label + for i, subpat in enumerate(subpats): + pat += ' {}'.format(subpat) + pat = '(' + pat + ')' + else: + return None + elif label == 'head': + pat = label + pat += ' {}'.format(subpats[0]) + pat = '(' + pat + ')' + elif label == 'list': + pat = 'list ' + if subpats[0]: + pat += '(h {})'.format(subpats[0]) + if subpats[0] and subpats[1]: + pat += ' ' + if subpats[1]: + pat += '(t {})'.format(subpats[1]) + pat = '(' + pat + ')' + if not pat: + for s in subpats: + if s: + pat = s + break + return pat + +def get_patterns(tree): + if isinstance(tree, str): + tree = prolog_parse(tree) + if tree is None: + return + + # get patterns separately for each clause + for clause in tree: + # collect variable nodes in this clause + variables = collections.defaultdict(list) + for node in clause.subtrees(): + if isinstance(node, Tree) and node.label() == 'variable': + name = node[0].val + variables[name].append(node) + + # yield patterns for singleton variables + for var, nodes in variables.items(): + if len(nodes) == 1: + pat = pattern(clause, nodes) + if pat: + yield pat, nodes + + # yield patterns for variable-variable pairs (within a clause) + for var, nodes in variables.items(): + for selected in combinations(nodes, 2): + pat = pattern(clause, selected) + if pat: + yield pat, selected + + # yield patterns for variable-literal / literal-literal pairs + # yield patterns for singleton literals + # (only within a topmost compound / binop / unop) + def patterns_with_literals(node): + if not isinstance(node, Tree): + return + if node.label() in {'compound', 'binop', 'unop'}: + vars = [n for n in node.subtrees() if n.label() == 'variable'] + lits = [n for n in node.subtrees() if n.label() == 'literal'] + for selected in chain( + combinations(lits, 1), + combinations(lits, 2), + product(lits, vars)): + pat = pattern(clause, selected) + if pat: + yield pat, selected + else: + for child in node: + yield from patterns_with_literals(child) + yield from patterns_with_literals(clause) diff --git a/monkey/rules.py b/monkey/rules.py new file mode 100644 index 0000000..fcd9582 --- /dev/null +++ b/monkey/rules.py @@ -0,0 +1,131 @@ +# 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) + + # consider only rules that have maximum matching patterns + candidate_rules = matches[max(matches)] + + # if there is candidate with no missing patterns, the program should already + # be correct, so do not try hinting + 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) + 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 diff --git a/server/problems.py b/server/problems.py index 10dec0d..9cccc21 100644 --- a/server/problems.py +++ b/server/problems.py @@ -65,6 +65,14 @@ def load_problem(language, problem_group, problem, tail_module): def load_facts(language, fact_module): return load_module('{0}.facts.{1}'.format(language, fact_module)) +def load_file(language, group, problem, name): + path = os.path.join(_path_prefix, language, 'problems', group, problem, name) + try: + with open(path, 'r') as f: + return f.read() + except: + return None + def load_problems(language, tuples, tail_module): modules = [] for problem_group, problem in tuples: diff --git a/server/prolog_session.py b/server/prolog_session.py index 6cb1592..8c101c6 100644 --- a/server/prolog_session.py +++ b/server/prolog_session.py @@ -14,19 +14,19 @@ # 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 json import operator import os.path -import pickle import threading from db.models import CodeqUser, Problem from db.util import make_identifier -import monkey +import monkey.rules import prolog.engine from prolog.util import used_predicates import server import server.user_session -from server.problems import get_facts, load_language, load_problem, solutions_for_problems +from server.problems import get_facts, load_file, load_language, load_problem, solutions_for_problems __all__ = ['PrologSession'] @@ -145,16 +145,11 @@ class PrologSession(server.LanguageSession): hints = problem_module.hint(program, aux_code=aux_code) # automatic hints - if not hints and problem_id in _edits and \ - allowed_hints in ('all', 'automatic'): - # Testing function for monkey. - def tester(code): - n_correct, n_all, _ = problem_module.test(code, aux_code=aux_code) - return n_correct, n_all - solution, steps, fix_time, n_tested = monkey.fix( - program, _edits[problem_id], tester, timeout=3) - if solution and steps: - hints = [{'id': 'monkey_main'}] + monkey.fix_hints(program, steps) + if not hints and allowed_hints in ('all', 'automatic'): + bug_data = load_file(problem.language, problem.group, problem.identifier, 'bugs.json') + if bug_data is not None: + bugs = json.loads(bug_data) + hints = monkey.rules.suggest(bugs, program) # generic language hints (style etc.) if not hints and hasattr(language_module, 'hint'): @@ -205,12 +200,3 @@ class PrologSession(server.LanguageSession): return messages, status, have_more server.language_session_handlers['prolog'] = lambda user_session, problem_id, language_identifier, group_identifier, problem_identifier: PrologSession() - -# Load edit data. -try: - _edits, _submissions, _queries = pickle.load( - open(os.path.join(os.path.dirname(os.path.realpath(__file__)), '..', 'edits.pickle'), 'rb')) -except: - _edits = {} - _submissions = {} - _queries = {} |