notebooks/Repairing_Code.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Third Project - Automated Repair"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Overview"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### The Task\n",
    "\n",
    "For the first two submissions we asked you to implement a _Debugger_ as well as an _Input Reducer_. Both of these tools are used to help the developer to locate bugs and then manually fix them.\n",
    "\n",
    "In this project, you will implement a technique of automatic code repair. To do so, you will extend the `Repairer` introduced in the [Repairing Code Automatically](https://www.debuggingbook.org/beta/html/Repairer.html) chapter of [The Debugging Book](https://www.debuggingbook.org/beta).\n",
    "\n",
    "Your own `Repairer` should automatically generate _repair suggestions_ to the faulty functions we provide later in this notebook. This can be achieved, for instance, by changing various components of the mutator, changing the debugger, or the reduction algorithm. However, you are neither reguired to make all these changes nor required to limit yourself to the changes proposed here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### The Submission\n",
    "\n",
    "The time frame for this project is **3 weeks**, and the deadline is **Februrary 5th, 23:59**.  \n",
    "\n",
    "The submission should be in form of a Jupyter notebook and you are expected to hand in the submission as a .zip-archive. The notebook should, apart from the code itself, also provide sufficient explanations and reasoning (in markdown cells) behind the decisions that lead to the solution provided. Projects that do not include explanations cannot get more than **15 points**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import bookutils.setup"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ignore\n",
    "from typing import Any, Callable, Optional, Tuple, List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## A Faulty Function and How to Repair It\n",
    "Before discussing how to use and extend the Repairer, we first start by introducing a new (and highly complex) function that is supposed to return the larger of two values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def larger(x: Any, y: Any) -> Any:\n",
    "    if x < y:\n",
    "        return x\n",
    "    return y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Unfortunately, we introduced a bug which makes the function behave the exact opposite way as it is supposed to:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "larger(1, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "To fix this issue, we could try to debug it, using the tools we have already seen. However, given the complexity of the function under test (sorry for the irony), we might want to automatically repair the function, using the *Repairer* introduced in *The Debugging Book*.\n",
    "\n",
    "To do so, we first need to define set of test cases, which help the *Repairer* in fixing the function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def larger_testcase() -> Tuple[int, int]:\n",
    "    x = random.randrange(100)\n",
    "    y = random.randrange(100)\n",
    "    return x, y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def larger_test(x: Any, y: Any) -> None:\n",
    "    m = larger(x, y)\n",
    "    assert m == max(x, y), f\"expected {max(x, y)}, but got {m}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import math\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "random.seed(42)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Let us generate a random test case for our function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "larger_input = larger_testcase()\n",
    "print(larger_input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "and then feed it into our `larger_test()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from ExpectError import ExpectError"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "with ExpectError():\n",
    "    larger_test(*larger_input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "As expected, we got an error – the `larger()` function has adefect."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "For a complete test suite, we need a set of passing and failing tests. To be sure we have both, we create functions which produce dedicated inputs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def larger_passing_testcase() -> Tuple:\n",
    "    while True:\n",
    "        try:\n",
    "            x, y = larger_testcase()\n",
    "            larger_test(x, y)\n",
    "            return x, y\n",
    "        except AssertionError:\n",
    "            pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def larger_failing_testcase() -> Tuple:\n",
    "    while True:\n",
    "        try:\n",
    "            x, y = larger_testcase()\n",
    "            larger_test(x, y)\n",
    "        except AssertionError:\n",
    "            return x, y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "passing_input = larger_passing_testcase()\n",
    "print(passing_input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "With `passing_input`, our `larger()` function produces a correct result, and its test function does not fail."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "larger_test(*passing_input)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "failing_input = larger_failing_testcase()\n",
    "print(failing_input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "While `failing_input` leads to an error:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "with ExpectError():\n",
    "    larger_test(*failing_input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "With the above defined functions, we can now start to create a number of passing and failing tests:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "TESTS = 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "LARGER_PASSING_TESTCASES = [larger_passing_testcase()\n",
    "                            for i in range(TESTS)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "LARGER_FAILING_TESTCASES = [larger_failing_testcase()\n",
    "                            for i in range(TESTS)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from StatisticalDebugger import OchiaiDebugger"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Next, let us use _statistical debugging_ to identify likely faulty locations. The `OchiaiDebugger` ranks individual code lines by how frequently they are executed in failing runs (and not in passing runs)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "larger_debugger = OchiaiDebugger()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for x, y in LARGER_PASSING_TESTCASES + LARGER_FAILING_TESTCASES:\n",
    "    with larger_debugger:\n",
    "        larger_test(x, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Given the results of statistical debugging, we can now use the *Repairer* introduced in the book to repair our function. Here we use the default implementation which is initialized with the simple _StatementMutator_ mutator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from Repairer import Repairer\n",
    "from Repairer import ConditionMutator, CrossoverOperator\n",
    "from Repairer import DeltaDebugger"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "repairer = Repairer(larger_debugger, log=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "best_tree, fitness = repairer.repair()  # type: ignore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The *Repairer* successfully produced a fix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Implementation\n",
    "\n",
    "As stated above, the goal of this project is to implement a repairer capable of producing a fix to the functions defined in *the Evaluation section*, as well as secret functions.  \n",
    "To do this, you need to work with the _Repairer_ class from the book.\n",
    "The _Repairer_ class is very configurable, so that it is easy to update and plug in various components: the fault localization (pass a different debugger that is a subclass of DifferenceDebugger), the mutation operator (set mutator_class to a subclass of `StatementMutator`), the crossover operator (set crossover_class to a subclass of `CrossoverOperator`), and the reduction algorithm (set reducer_class to a subclass of `Reducer`). You may change any of these components or make other changes at will."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "For us to be able to test your implementation, you will have to implement the `debug_and_repair()` function defined here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from bookutils import print_content, show_ast"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def debug_and_repair(f: Callable,\n",
    "                     testcases: List[Tuple[Any, ...]],\n",
    "                     test_function: Callable,\n",
    "                     log: bool = False) -> Optional[str]:\n",
    "    '''\n",
    "    Debugs a function with the given testcases and the test_function\n",
    "    and tries to repair it afterwards.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    f : function\n",
    "        The faulty function, to be debugged and repaired\n",
    "    testcases : List\n",
    "        A list that includes test inputs for the function under test\n",
    "    test_function : function\n",
    "        A function that takes the test inputs and tests whether the\n",
    "        function under test produces the correct output.\n",
    "    log: bool\n",
    "        Turn logging on/off.\n",
    "    Returns\n",
    "    -------\n",
    "    str\n",
    "        The repaired version of f as a string.\n",
    "    '''\n",
    "\n",
    "    # TODO: implement this function\n",
    "\n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The function `debug_and_repair()` is the function that needs to implement everything. We will provide you with the function to be repaired, as well as testcases for this function and a test-function. Let us show you how the function can be used and should behave:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "random.seed(42)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import ast"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def simple_debug_and_repair(f: Callable,\n",
    "                            testcases: List[Tuple[Any, ...]],\n",
    "                            test_function: Callable, \n",
    "                            log: bool = False) -> str:\n",
    "    '''\n",
    "    Debugs a function with the given testcases and the test_function\n",
    "    and tries to repair it afterwards.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    f : function\n",
    "        The faulty function, to be debugged and repaired\n",
    "    testcases : List\n",
    "        A list that includes test inputs for the function under test\n",
    "    test_function : function\n",
    "        A function, that takes the test inputs and tests whether the\n",
    "        function under test produces the correct output.\n",
    "    log: bool\n",
    "        Turn logging on/off.\n",
    "    Returns\n",
    "    -------\n",
    "    str\n",
    "        The repaired version of f as a string.\n",
    "    '''\n",
    "\n",
    "    debugger = OchiaiDebugger()\n",
    "\n",
    "    for i in testcases:\n",
    "        with debugger:\n",
    "            test_function(*i)  # Ensure that you use *i here.\n",
    "\n",
    "    repairer = Repairer(debugger,\n",
    "                        mutator_class=ConditionMutator,\n",
    "                        crossover_class=CrossoverOperator,\n",
    "                        reducer_class=DeltaDebugger,\n",
    "                        log=log)\n",
    "\n",
    "    # Ensure that you specify a sufficient number of\n",
    "    # iterations to evolve.\n",
    "    best_tree, fitness = repairer.repair(iterations=100)  # type: ignore\n",
    "\n",
    "    return ast.unparse(best_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Here we again used the _Ochiai_ statistical debugger and the _Repairer_ described in [The Debugging Book](https://www.debuggingbook.org/beta/html/Repairer.html). In contrast to the initial example, now we used another type of mutator – `ConditionMutator`. It can successfully fix the `larger` function as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "repaired = simple_debug_and_repair(larger,\n",
    "                                   LARGER_PASSING_TESTCASES +\n",
    "                                   LARGER_FAILING_TESTCASES,\n",
    "                                   larger_test, False)\n",
    "print_content(repaired, '.py')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Although `simple_debug_and_repair` produced a correct solution for our example, it does not generalize to other functions.  \n",
    "So your task is to create the `debug_and_repair()` function which can be applied on any faulty function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Apart from the function `debug_and_repair()`, you may of course implement your own classes. Make sure, however, that you are using these classes within `debug_and_repair()`. Also, keep in mind to tune the _iteration_ parameter of the `Repairer` so that it has sufficient number of generation to evolve. As it may take too much time to find a solution for an ill-programmed repairer (e.g., consider an infinite `while`loop introduced in the fix), we impose a _10-minute timeout_ for each repair."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Evaluation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Having you implement `debug_and_repair()` allows us to easily test your implementation by calling the function with its respective arguments and testing the correctness of its output. In this section, we will provide you with some test cases as well as the testing framework for this project. This will help you to assess the quality of your work.  \n",
    "\n",
    "We define functions as well as test-case generators for these functions. The functions given here should be considered as **public tests**. If you pass all public tests, without hard-coding the solutions, you are guaranteed to achieve **10 points**. The secret tests for the remaining 10 must-have-points have similar defects."
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Factorial\n",
    "\n",
    "The first function we implement is a _factorial_ function. It is supposed to compute the following formula:  \n",
    "\\begin{equation*}\n",
    "n! = \\textit{factorial}(n) = \\prod_{k=1}^{n}k, \\quad \\text{for $k\\geq 1$}\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Here we define three faulty functions `factorial1`, `factorial2`, and `factorial3` that are supposed to compute the factorial."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def factorial1(n):  # type: ignore\n",
    "    res = 1\n",
    "    for i in range(1, n):\n",
    "        res *= i\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "From the first sight, `factorial1` looks to be correctly implemented, still it produces the wrong answer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "factorial1(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "while the correct value for 5! is 120."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def factorial_testcase() -> int:\n",
    "    n = random.randrange(100)\n",
    "    return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def factorial1_test(n: int) -> None:\n",
    "    m = factorial1(n)\n",
    "    assert m == math.factorial(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def factorial_passing_testcase() -> Tuple:\n",
    "    while True:\n",
    "        try:\n",
    "            n = factorial_testcase()\n",
    "            factorial1_test(n)\n",
    "            return (n,)\n",
    "        except AssertionError:\n",
    "            pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def factorial_failing_testcase() -> Tuple:\n",
    "    while True:\n",
    "        try:\n",
    "            n = factorial_testcase()\n",
    "            factorial1_test(n)\n",
    "        except AssertionError:\n",
    "            return (n,)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "FACTORIAL_PASSING_TESTCASES_1 = [factorial_passing_testcase() for i in range(TESTS)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "FACTORIAL_FAILING_TESTCASES_1 = [factorial_failing_testcase() for i in range(TESTS)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "As we can see, our simple Repairer cannot produce a fix. (Or more precisely, the \"fix\" it produces is pretty much pointless.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "repaired = \\\n",
    "    simple_debug_and_repair(factorial1,\n",
    "                            FACTORIAL_PASSING_TESTCASES_1 +\n",
    "                            FACTORIAL_FAILING_TESTCASES_1,\n",
    "                            factorial1_test, True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The problem is that the current `Repairer` does not provide a suitable mutation to change the right part of the code.\n",
    "\n",
    "How can we repair this? Consider extending `StatementMutator` operator such that it can mutate various parts of the code, such as ranges, arithmetic operations, variable names etc. (As a reference of how to do that, look at the `ConditionMutator` class.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The next faulty function is `factorial2()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def factorial2(n):  # type: ignore\n",
    "    i = 1\n",
    "    for i in range(1, n + 1):\n",
    "        i *= i\n",
    "    return i"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Again, it outputs the incorrect answer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "factorial2(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def factorial2_test(n: int) -> None:\n",
    "    m = factorial2(n)\n",
    "    assert m == math.factorial(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def factorial_passing_testcase() -> Tuple:  # type: ignore\n",
    "    while True:\n",
    "        try:\n",
    "            n = factorial_testcase()\n",
    "            factorial2_test(n)\n",
    "            return (n,)\n",
    "        except AssertionError:\n",
    "            pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def factorial_failing_testcase() -> Tuple:  # type: ignore\n",
    "    while True:\n",
    "        try:\n",
    "            n = factorial_testcase()\n",
    "            factorial2_test(n)\n",
    "        except AssertionError:\n",
    "            return (n,)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "FACTORIAL_PASSING_TESTCASES_2 = [factorial_passing_testcase()\n",
    "                                 for i in range(TESTS)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "FACTORIAL_FAILING_TESTCASES_2 = [factorial_failing_testcase()\n",
    "                                 for i in range(TESTS)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The third faulty function is `factorial3()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def factorial3(n):  # type: ignore\n",
    "    res = 1\n",
    "    for i in range(1, n + 1):\n",
    "        res += i\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "factorial3(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def factorial3_test(n: int) -> None:\n",
    "    m = factorial3(n)\n",
    "    assert m == math.factorial(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def factorial_passing_testcase() -> Tuple:  # type: ignore\n",
    "    while True:\n",
    "        try:\n",
    "            n = factorial_testcase()\n",
    "            factorial3_test(n)\n",
    "            return (n,)\n",
    "        except AssertionError:\n",
    "            pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def factorial_failing_testcase() -> Tuple:  # type: ignore\n",
    "    while True:\n",
    "        try:\n",
    "            n = factorial_testcase()\n",
    "            factorial3_test(n)\n",
    "        except AssertionError:\n",
    "            return (n,)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "FACTORIAL_PASSING_TESTCASES_3 = [factorial_passing_testcase()\n",
    "                                 for i in range(TESTS)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "FACTORIAL_FAILING_TESTCASES_3 = [factorial_failing_testcase()\n",
    "                                 for i in range(TESTS)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Middle\n",
    "\n",
    "The following faulty function is the already well known _Middle_ function, though with another defect."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def middle(x, y, z):  # type: ignore\n",
    "    if x < x:\n",
    "        if y < z:\n",
    "            return y\n",
    "        if x < z:\n",
    "            return z\n",
    "        return x\n",
    "    if x < z:\n",
    "        return x\n",
    "    if y < z:\n",
    "        return z\n",
    "    return y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "It should return the second largest number of the input, but it does not:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "middle(2, 3, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def middle_testcase() -> Tuple:\n",
    "    x = random.randrange(10)\n",
    "    y = random.randrange(10)\n",
    "    z = random.randrange(10)\n",
    "    return x, y, z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def middle_test(x: int, y: int, z: int) -> None:\n",
    "    m = middle(x, y, z)\n",
    "    assert m == sorted([x, y, z])[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def middle_passing_testcase() -> Tuple:\n",
    "    while True:\n",
    "        try:\n",
    "            x, y, z = middle_testcase()\n",
    "            middle_test(x, y, z)\n",
    "            return x, y, z\n",
    "        except AssertionError:\n",
    "            pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def middle_failing_testcase() -> Tuple:\n",
    "    while True:\n",
    "        try:\n",
    "            x, y, z = middle_testcase()\n",
    "            middle_test(x, y, z)\n",
    "        except AssertionError:\n",
    "            return x, y, z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "MIDDLE_PASSING_TESTCASES = [middle_passing_testcase()\n",
    "                            for i in range(TESTS)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "MIDDLE_FAILING_TESTCASES = [middle_failing_testcase()\n",
    "                            for i in range(TESTS)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Power\n",
    "\n",
    "The power function should implement the following formular:\n",
    "\\begin{equation*}\n",
    "\\textit{power}(x, n) = x^n, \\quad \\text{for $x\\geq 0$ and $n \\geq 0$}\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def power(x, n):  # type: ignore\n",
    "    res = 1\n",
    "    for i in range(0, x):\n",
    "        res *= n\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "However, this `power()` function either has an uncommon interpretation of $x^y$ – or it is simply wrong:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "power(2, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We go with the simpler explanation that `power()` is wrong. The correct value, of course, should be $2^5 = 32$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def power_testcase() -> Tuple:\n",
    "    x = random.randrange(100)\n",
    "    n = random.randrange(100)\n",
    "    return x, n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def power_test(x: int, n: int) -> None:\n",
    "    m = power(x, n)\n",
    "    assert m == pow(x, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def power_passing_testcase() -> Tuple:\n",
    "    while True:\n",
    "        try:\n",
    "            x, n = power_testcase()\n",
    "            power_test(x, n)\n",
    "            return x, n\n",
    "        except AssertionError:\n",
    "            pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def power_failing_testcase() -> Tuple:\n",
    "    while True:\n",
    "        try:\n",
    "            x, n = power_testcase()\n",
    "            power_test(x, n)\n",
    "        except AssertionError:\n",
    "            return x, n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "POWER_PASSING_TESTCASES = [power_passing_testcase()\n",
    "                           for i in range(TESTS)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "POWER_FAILING_TESTCASES = [power_failing_testcase()\n",
    "                           for i in range(TESTS)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Tester Class"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "To make it convenient to test your solution we provide a testing framework:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class Test:\n",
    "    def __init__(self,\n",
    "                 function: Callable,\n",
    "                 testcases: List, \n",
    "                 test_function: Callable,\n",
    "                 assert_function: Callable) -> None:\n",
    "        self.function = function\n",
    "        self.testcases = testcases\n",
    "        self.test_function = test_function\n",
    "        self.assert_function = assert_function\n",
    "\n",
    "    def run(self, repair_function: Callable) -> None:\n",
    "        repaired = repair_function(self.function,\n",
    "                                   self.testcases,\n",
    "                                   self.test_function)\n",
    "        repaired = re.sub(self.function.__name__, 'foo', repaired)\n",
    "        exec(repaired, globals())\n",
    "\n",
    "        for test in self.testcases:\n",
    "            res = foo(*test)  # type: ignore\n",
    "            assert res == self.assert_function(*test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def middle_assert(x, y, z):  # type: ignore\n",
    "    return sorted([x, y, z])[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "test0 = Test(factorial1, FACTORIAL_PASSING_TESTCASES_1 + FACTORIAL_FAILING_TESTCASES_1, factorial1_test, math.factorial)\n",
    "test1 = Test(factorial2, FACTORIAL_PASSING_TESTCASES_2 + FACTORIAL_FAILING_TESTCASES_2, factorial2_test, math.factorial)\n",
    "test2 = Test(factorial3, FACTORIAL_PASSING_TESTCASES_3 + FACTORIAL_FAILING_TESTCASES_3, factorial3_test, math.factorial)\n",
    "test3 = Test(middle, MIDDLE_PASSING_TESTCASES + MIDDLE_FAILING_TESTCASES, middle_test, middle_assert)\n",
    "test4 = Test(power, POWER_PASSING_TESTCASES + POWER_FAILING_TESTCASES, power_test, pow)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "tests = [test0, test1, test2, test3, test4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class Tester:\n",
    "    def __init__(self, function: Callable, tests: List) -> None:\n",
    "        self.function = function\n",
    "        self.tests = tests\n",
    "        random.seed(42)  # We use this seed for our evaluation; don't change it.\n",
    "\n",
    "    def run_tests(self) -> None:\n",
    "        for test in self.tests:\n",
    "            try:\n",
    "                test.run(self.function)\n",
    "                print(f'Test {test.function.__name__}: OK')\n",
    "            except AssertionError:\n",
    "                print(f'Test {test.function.__name__}: Failed')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "tester = Tester(simple_debug_and_repair, tests)  # TODO: replace simple_debug_and_repair by your debug_and_repair function\n",
    "tester.run_tests()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "By executing the `Tester` as shown above, you can assess the quality of your repairing approach, by testing your own `debug_and_repair()` function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Grading\n",
    "\n",
    "Your project will be graded by _automated tests_. The tests are executed in the same manner as shown above.\n",
    "In total there are **20 points** + **10 bonus points** to be awarded for this project. **20 points** for the must-haves, **10 bonus points** for may-haves."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Must-Haves (20 points)\n",
    "\n",
    "Must haves include an implementation of the `debug_and_repair` function in a way that it automatically repairs faulty functions given sufficiantly large test suites.\n",
    "**10 points** are awarded for passing the tests in this notebook. Each passing test being worth two points.\n",
    "**10 points** are awarded for passing secret tests."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### May-Haves (10 points)\n",
    "\n",
    "May-haves will also be tested with secret tests, and award **2 points** each. The may-have-features for this project are a more robust implementation, that is able to cope with a wider range of defects:\n",
    "\n",
    "* Infinite loops\n",
    "* Infinite recursion (`RecursionError` in Python)\n",
    "* Type errors (`TypeError` in Python)\n",
    "* Undefined identifiers (`NameError` in Python)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### General Rules\n",
    "\n",
    "You need to achieve at least **10 points** to be awarded any points at all.  \n",
    "Tests must be passed without hard-coding results, otherwise no points are awarded.  \n",
    "Your code needs to be sufficiently documented in order to achieve points!"
   ]
  }
 ],
 "metadata": {
  "ipub": {
   "bibliography": "fuzzingbook.bib"
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  },
  "toc-autonumbering": false
 },
 "nbformat": 4,
 "nbformat_minor": 4
}