{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Repairing Code Automatically\n",
"\n",
"So far, we have discussed how to track failures and how to locate defects in code. Let us now discuss how to _repair_ defects – that is, to correct the code such that the failure no longer occurs. We will discuss how to _repair code automatically_ – by systematically searching through possible fixes and evolving the most promising candidates."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:29.256586Z",
"iopub.status.busy": "2023-11-12T12:47:29.256416Z",
"iopub.status.idle": "2023-11-12T12:47:29.294650Z",
"shell.execute_reply": "2023-11-12T12:47:29.294356Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
" \n",
" "
],
"text/plain": [
""
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from bookutils import YouTubeVideo\n",
"YouTubeVideo(\"UJTf7cW0idI\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"**Prerequisites**\n",
"\n",
"* Re-read the [introduction to debugging](Intro_Debugging.ipynb), notably on how to properly fix code.\n",
"* We make use of automatic fault localization, as discussed in the [chapter on statistical debugging](StatisticalDebugger.ipynb).\n",
"* We make extensive use of code transformations, as discussed in the [chapter on tracing executions](Tracer.ipynb).\n",
"* We make use of [delta debugging](DeltaDebugger.ipynb)."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"button": false,
"execution": {
"iopub.execute_input": "2023-11-12T12:47:29.315182Z",
"iopub.status.busy": "2023-11-12T12:47:29.314987Z",
"iopub.status.idle": "2023-11-12T12:47:29.318221Z",
"shell.execute_reply": "2023-11-12T12:47:29.317883Z"
},
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import bookutils.setup"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"## Synopsis\n",
"\n",
"\n",
"To [use the code provided in this chapter](Importing.ipynb), write\n",
"\n",
"```python\n",
">>> from debuggingbook.Repairer import \n",
"```\n",
"\n",
"and then make use of the following features.\n",
"\n",
"\n",
"This chapter provides tools and techniques for automated repair of program code. The `Repairer` class takes a `RankingDebugger` debugger as input (such as `OchiaiDebugger` from the [chapter on statistical debugging](StatisticalDebugger.ipynb). A typical setup looks like this:\n",
"\n",
"```python\n",
"from debuggingbook.StatisticalDebugger import OchiaiDebugger\n",
"\n",
"debugger = OchiaiDebugger()\n",
"for inputs in TESTCASES:\n",
" with debugger:\n",
" test_foo(inputs)\n",
"...\n",
"\n",
"repairer = Repairer(debugger)\n",
"```\n",
"Here, `test_foo()` is a function that raises an exception if the tested function `foo()` fails. If `foo()` passes, `test_foo()` should not raise an exception.\n",
"\n",
"The `repair()` method of a `Repairer` searches for a repair of the code covered in the debugger (except for methods whose name starts or ends in `test`, such that `foo()`, not `test_foo()` is repaired). `repair()` returns the best fix candidate as a pair `(tree, fitness)` where `tree` is a [Python abstract syntax tree](http://docs.python.org/3/library/ast) (AST) of the fix candidate, and `fitness` is the fitness of the candidate (a value between 0 and 1). A `fitness` of 1.0 means that the candidate passed all tests. A typical usage looks like this:\n",
"\n",
"```python\n",
"tree, fitness = repairer.repair()\n",
"print(ast.unparse(tree), fitness)\n",
"```\n",
"\n",
"Here is a complete example for the `middle()` program. This is the original source code of `middle()`:\n",
"\n",
"```python\n",
"def middle(x, y, z): # type: ignore\n",
" if y < z:\n",
" if x < y:\n",
" return y\n",
" elif x < z:\n",
" return y\n",
" else:\n",
" if x > y:\n",
" return y\n",
" elif x > z:\n",
" return x\n",
" return z\n",
"```\n",
"We set up a function `middle_test()` that tests it. The `middle_debugger` collects testcases and outcomes:\n",
"\n",
"```python\n",
">>> middle_debugger = OchiaiDebugger()\n",
">>> for x, y, z in MIDDLE_PASSING_TESTCASES + MIDDLE_FAILING_TESTCASES:\n",
">>> with middle_debugger:\n",
">>> middle_test(x, y, z)\n",
"```\n",
"The repairer is instantiated with the debugger used (`middle_debugger`):\n",
"\n",
"```python\n",
">>> middle_repairer = Repairer(middle_debugger)\n",
"```\n",
"The `repair()` method of the repairer attempts to repair the function invoked by the test (`middle()`).\n",
"\n",
"```python\n",
">>> tree, fitness = middle_repairer.repair()\n",
"```\n",
"The returned AST `tree` can be output via `ast.unparse()`:\n",
"\n",
"```python\n",
">>> print(ast.unparse(tree))\n",
"def middle(x, y, z):\n",
" if y < z:\n",
" if x < y:\n",
" return y\n",
" elif x < z:\n",
" return x\n",
" elif x > y:\n",
" return y\n",
" elif x > z:\n",
" return x\n",
" return z\n",
"\n",
"```\n",
"The `fitness` value shows how well the repaired program fits the tests. A fitness value of 1.0 shows that the repaired program satisfies all tests.\n",
"\n",
"```python\n",
">>> fitness\n",
"1.0\n",
"```\n",
"Hence, the above program indeed is a perfect repair in the sense that all previously failing tests now pass – our repair was successful.\n",
"\n",
"Here are the classes defined in this chapter. A `Repairer` repairs a program, using a `StatementMutator` and a `CrossoverOperator` to evolve a population of candidates.\n",
"\n",
"![](PICS/Repairer-synopsis-1.svg)\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": true,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Automatic Code Repairs\n",
"\n",
"So far, we have discussed how to locate defects in code, how to track failures back to the defects that caused them, and how to systematically determine failure conditions. Let us now address the last step in debugging – namely, how to _automatically fix code_.\n",
"\n",
"Already in the [introduction to debugging](Intro_Debugging.ipynb), we have discussed how to fix code manually. Notably, we have established that a _diagnosis_ (which induces a fix) should show _causality_ (i.e., how the defect causes the failure) and _incorrectness_ (how the defect is wrong). Is it possible to obtain such a diagnosis automatically?"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"In this chapter, we introduce a technique of _automatic code repair_ – that is, for a given failure, automatically determine a fix that makes the failure go away. To do so, we randomly (but systematically) _mutate_ the program code – that is, insert, change, and delete fragments – until we find a change that actually causes the failing test to pass."
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"If this sounds like an audacious idea, that is because it is. But not only is _automated program repair_ one of the hottest topics of software research in the last decade, it is also being increasingly deployed in industry. At Facebook, for instance, every failing test report comes with an automatically generated _repair suggestion_ – a suggestion that already has been validated to work. Programmers can apply the suggestion as is or use it as basis for their own fixes."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### The middle() Function"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Let us introduce our ongoing example. In the [chapter on statistical debugging](StatisticalDebugger.ipynb), we have introduced the `middle()` function – a function that returns the \"middle\" of three numbers `x`, `y`, and `z`:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:29.320106Z",
"iopub.status.busy": "2023-11-12T12:47:29.320010Z",
"iopub.status.idle": "2023-11-12T12:47:29.948163Z",
"shell.execute_reply": "2023-11-12T12:47:29.947833Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from StatisticalDebugger import middle"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:29.950050Z",
"iopub.status.busy": "2023-11-12T12:47:29.949890Z",
"iopub.status.idle": "2023-11-12T12:47:29.951543Z",
"shell.execute_reply": "2023-11-12T12:47:29.951302Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"# ignore\n",
"from bookutils import print_content"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:29.952992Z",
"iopub.status.busy": "2023-11-12T12:47:29.952890Z",
"iopub.status.idle": "2023-11-12T12:47:29.954467Z",
"shell.execute_reply": "2023-11-12T12:47:29.954229Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"# ignore\n",
"import inspect"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:29.955963Z",
"iopub.status.busy": "2023-11-12T12:47:29.955844Z",
"iopub.status.idle": "2023-11-12T12:47:30.017834Z",
"shell.execute_reply": "2023-11-12T12:47:30.017554Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"708 \u001b[34mdef\u001b[39;49;00m \u001b[32mmiddle\u001b[39;49;00m(x, y, z): \u001b[37m# type: ignore\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
"709 \u001b[34mif\u001b[39;49;00m y < z:\u001b[37m\u001b[39;49;00m\n",
"710 \u001b[34mif\u001b[39;49;00m x < y:\u001b[37m\u001b[39;49;00m\n",
"711 \u001b[34mreturn\u001b[39;49;00m y\u001b[37m\u001b[39;49;00m\n",
"712 \u001b[34melif\u001b[39;49;00m x < z:\u001b[37m\u001b[39;49;00m\n",
"713 \u001b[34mreturn\u001b[39;49;00m y\u001b[37m\u001b[39;49;00m\n",
"714 \u001b[34melse\u001b[39;49;00m:\u001b[37m\u001b[39;49;00m\n",
"715 \u001b[34mif\u001b[39;49;00m x > y:\u001b[37m\u001b[39;49;00m\n",
"716 \u001b[34mreturn\u001b[39;49;00m y\u001b[37m\u001b[39;49;00m\n",
"717 \u001b[34melif\u001b[39;49;00m x > z:\u001b[37m\u001b[39;49;00m\n",
"718 \u001b[34mreturn\u001b[39;49;00m x\u001b[37m\u001b[39;49;00m\n",
"719 \u001b[34mreturn\u001b[39;49;00m z\u001b[37m\u001b[39;49;00m"
]
}
],
"source": [
"# ignore\n",
"_, first_lineno = inspect.getsourcelines(middle)\n",
"middle_source = inspect.getsource(middle)\n",
"print_content(middle_source, '.py', start_line_number=first_lineno)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"In most cases, `middle()` just runs fine:"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.019424Z",
"iopub.status.busy": "2023-11-12T12:47:30.019311Z",
"iopub.status.idle": "2023-11-12T12:47:30.021463Z",
"shell.execute_reply": "2023-11-12T12:47:30.021195Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"middle(4, 5, 6)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"In some other cases, though, it does not work correctly:"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.023051Z",
"iopub.status.busy": "2023-11-12T12:47:30.022940Z",
"iopub.status.idle": "2023-11-12T12:47:30.024989Z",
"shell.execute_reply": "2023-11-12T12:47:30.024714Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"middle(2, 1, 3)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Validated Repairs"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Now, if we only want a repair that fixes this one given failure, this would be very easy. All we have to do is to replace the entire body by a single statement:"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.026636Z",
"iopub.status.busy": "2023-11-12T12:47:30.026524Z",
"iopub.status.idle": "2023-11-12T12:47:30.028153Z",
"shell.execute_reply": "2023-11-12T12:47:30.027903Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def middle_sort_of_fixed(x, y, z): # type: ignore\n",
" return x"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"You will concur that the failure no longer occurs:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.029650Z",
"iopub.status.busy": "2023-11-12T12:47:30.029549Z",
"iopub.status.idle": "2023-11-12T12:47:30.031551Z",
"shell.execute_reply": "2023-11-12T12:47:30.031289Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"2"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"middle_sort_of_fixed(2, 1, 3)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"But this, of course, is not the aim of automatic fixes, nor of fixes in general: We want our fixes not only to make the given failure go away, but we also want the resulting code to be _correct_ (which, of course, is a lot harder)."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Automatic repair techniques therefore assume the existence of a _test suite_ that can check whether an implementation satisfies its requirements. Better yet, one can use the test suite to gradually check _how close_ one is to perfection: A piece of code that satisfies 99% of all tests is better than one that satisfies ~33% of all tests, as `middle_sort_of_fixed()` would do (assuming the test suite evenly checks the input space)."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Genetic Optimization"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The common approach for automatic repair follows the principle of _genetic optimization_. Roughly spoken, genetic optimization is a _metaheuristic_ inspired by the process of _natural selection_. The idea is to _evolve_ a selection of _candidate solutions_ towards a maximum _fitness_:\n",
"\n",
"1. Have a selection of _candidates_.\n",
"2. Determine the _fitness_ of each candidate.\n",
"3. Retain those candidates with the _highest fitness_.\n",
"4. Create new candidates from the retained candidates, by applying genetic operations:\n",
" * _Mutation_ mutates some aspect of a candidate.\n",
" * _CrossoverOperator_ creates new candidates combining features of two candidates.\n",
"5. Repeat until an optimal solution is found."
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Applied for automated program repair, this means the following steps:\n",
"\n",
"1. Have a _test suite_ with both failing and passing tests that helps to assert correctness of possible solutions.\n",
"2. With the test suite, use [fault localization](StatisticalDebugger.ipynb) to determine potential code locations to be fixed.\n",
"3. Systematically _mutate_ the code (by adding, changing, or deleting code) and _cross_ code to create possible fix candidates.\n",
"4. Identify the _fittest_ fix candidates – that is, those that satisfy the most tests.\n",
"5. _Evolve_ the fittest candidates until a perfect fix is found, or until time resources are depleted."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Let us illustrate these steps in the following sections."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## A Test Suite"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"In automated repair, the larger and the more thorough the test suite, the higher the quality of the resulting fix (if any). Hence, if we want to repair `middle()` automatically, we need a good test suite – with good inputs, but also with good checks. Note that running the test suite commonly takes the most time of automated repair, so a large test suite also comes with extra cost."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Let us first focus on achieving high-quality repairs. Hence, we will use the extensive test suites introduced in the [chapter on statistical debugging](StatisticalDebugger.ipynb):"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.033396Z",
"iopub.status.busy": "2023-11-12T12:47:30.033272Z",
"iopub.status.idle": "2023-11-12T12:47:30.034893Z",
"shell.execute_reply": "2023-11-12T12:47:30.034655Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from StatisticalDebugger import MIDDLE_PASSING_TESTCASES, MIDDLE_FAILING_TESTCASES"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The `middle_test()` function fails whenever `middle()` returns an incorrect result:"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.036434Z",
"iopub.status.busy": "2023-11-12T12:47:30.036331Z",
"iopub.status.idle": "2023-11-12T12:47:30.038158Z",
"shell.execute_reply": "2023-11-12T12:47:30.037909Z"
},
"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": 13,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.039809Z",
"iopub.status.busy": "2023-11-12T12:47:30.039685Z",
"iopub.status.idle": "2023-11-12T12:47:30.041322Z",
"shell.execute_reply": "2023-11-12T12:47:30.041051Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from ExpectError import ExpectError"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.042769Z",
"iopub.status.busy": "2023-11-12T12:47:30.042679Z",
"iopub.status.idle": "2023-11-12T12:47:30.044539Z",
"shell.execute_reply": "2023-11-12T12:47:30.044292Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"Traceback (most recent call last):\n",
" File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_33724/3661663124.py\", line 2, in \n",
" middle_test(2, 1, 3)\n",
" File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_33724/40742806.py\", line 3, in middle_test\n",
" assert m == sorted([x, y, z])[1]\n",
"AssertionError (expected)\n"
]
}
],
"source": [
"with ExpectError():\n",
" middle_test(2, 1, 3)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Locating the Defect"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Our next step is to find potential defect locations – that is, those locations in the code our mutations should focus upon. Since we already do have two test suites, we can make use of [statistical debugging](StatisticalDebugger.ipynb) to identify likely faulty locations. Our `OchiaiDebugger` ranks individual code lines by how frequently they are executed in failing runs (and not in passing runs)."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.046287Z",
"iopub.status.busy": "2023-11-12T12:47:30.046167Z",
"iopub.status.idle": "2023-11-12T12:47:30.047820Z",
"shell.execute_reply": "2023-11-12T12:47:30.047548Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from StatisticalDebugger import OchiaiDebugger, RankingDebugger"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.049377Z",
"iopub.status.busy": "2023-11-12T12:47:30.049263Z",
"iopub.status.idle": "2023-11-12T12:47:30.056166Z",
"shell.execute_reply": "2023-11-12T12:47:30.055832Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"middle_debugger = OchiaiDebugger()\n",
"\n",
"for x, y, z in MIDDLE_PASSING_TESTCASES + MIDDLE_FAILING_TESTCASES:\n",
" with middle_debugger:\n",
" middle_test(x, y, z)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"We see that the upper half of the `middle()` code is definitely more suspicious:"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.057802Z",
"iopub.status.busy": "2023-11-12T12:47:30.057704Z",
"iopub.status.idle": "2023-11-12T12:47:30.086073Z",
"shell.execute_reply": "2023-11-12T12:47:30.085776Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"data": {
"text/html": [
"
\n"
],
"text/markdown": [
"| `middle_test` | `x=9, y=0, z=5` | `x=0, y=1, z=9` | `x=9, y=0, z=9` | `x=2, y=9, z=0` | `x=4, y=7, z=2` | `x=1, y=6, z=1` | `x=7, y=5, z=4` | `x=6, y=6, z=2` | `x=7, y=6, z=4` | `x=0, y=7, z=7` | `x=3, y=9, z=7` | `x=2, y=3, z=8` | `x=2, y=6, z=3` | `x=2, y=8, z=4` | `x=8, y=7, z=5` | `x=0, y=0, z=6` | `x=5, y=2, z=5` | `x=9, y=6, z=9` | `x=8, y=5, z=5` | `x=1, y=7, z=0` | `x=0, y=4, z=4` | `x=8, y=7, z=5` | `x=7, y=1, z=5` | `x=3, y=5, z=3` | `x=6, y=3, z=2` | `x=3, y=9, z=8` | `x=1, y=3, z=8` | `x=5, y=9, z=1` | `x=5, y=5, z=7` | `x=9, y=0, z=3` | `x=5, y=6, z=3` | `x=7, y=9, z=8` | `x=2, y=2, z=3` | `x=1, y=8, z=1` | `x=3, y=3, z=3` | `x=7, y=3, z=6` | `x=3, y=7, z=6` | `x=2, y=3, z=1` | `x=8, y=0, z=6` | `x=5, y=4, z=0` | `x=5, y=9, z=2` | `x=6, y=7, z=1` | `x=1, y=1, z=7` | `x=1, y=6, z=8` | `x=0, y=9, z=1` | `x=5, y=9, z=7` | `x=1, y=5, z=6` | `x=1, y=6, z=1` | `x=7, y=8, z=4` | `x=2, y=8, z=4` | `x=3, y=4, z=3` | `x=8, y=4, z=5` | `x=0, y=5, z=8` | `x=9, y=7, z=0` | `x=1, y=5, z=4` | `x=9, y=8, z=9` | `x=9, y=2, z=4` | `x=3, y=2, z=0` | `x=8, y=5, z=2` | `x=4, y=9, z=7` | `x=4, y=8, z=0` | `x=5, y=9, z=1` | `x=7, y=6, z=4` | `x=8, y=9, z=2` | `x=9, y=1, z=4` | `x=9, y=7, z=2` | `x=1, y=9, z=5` | `x=1, y=9, z=1` | `x=7, y=8, z=0` | `x=4, y=8, z=6` | `x=9, y=2, z=1` | `x=9, y=4, z=5` | `x=0, y=4, z=2` | `x=6, y=8, z=4` | `x=0, y=0, z=1` | `x=6, y=4, z=3` | `x=8, y=0, z=3` | `x=9, y=5, z=1` | `x=7, y=6, z=6` | `x=4, y=6, z=0` | `x=1, y=1, z=0` | `x=8, y=4, z=1` | `x=1, y=6, z=2` | `x=4, y=5, z=1` | `x=1, y=1, z=6` | `x=1, y=2, z=1` | `x=2, y=4, z=2` | `x=7, y=3, z=3` | `x=2, y=7, z=4` | `x=0, y=8, z=0` | `x=4, y=6, z=4` | `x=1, y=5, z=2` | `x=0, y=8, z=2` | `x=3, y=5, z=6` | `x=7, y=2, z=4` | `x=5, y=4, z=5` | `x=2, y=3, z=4` | `x=2, y=2, z=4` | `x=3, y=6, z=2` | `x=9, y=4, z=0` | `x=2, y=1, z=5` | `x=5, y=2, z=9` | `x=2, y=1, z=3` | `x=3, y=0, z=7` | `x=4, y=1, z=6` | `x=2, y=0, z=9` | `x=4, y=3, z=7` | `x=5, y=3, z=8` | `x=6, y=0, z=9` | `x=2, y=0, z=4` | `x=4, y=0, z=5` | `x=6, y=5, z=9` | `x=5, y=3, z=9` | `x=7, y=0, z=9` | `x=5, y=3, z=9` | `x=2, y=1, z=6` | `x=3, y=2, z=4` | `x=2, y=1, z=5` | `x=3, y=2, z=6` | `x=6, y=4, z=7` | `x=5, y=2, z=6` | `x=4, y=2, z=5` | `x=6, y=2, z=9` | `x=4, y=2, z=8` | `x=2, y=0, z=3` | `x=2, y=1, z=5` | `x=2, y=1, z=9` | `x=7, y=6, z=9` | `x=6, y=0, z=9` | `x=7, y=6, z=9` | `x=8, y=6, z=9` | `x=7, y=6, z=9` | `x=1, y=0, z=2` | `x=1, y=0, z=3` | `x=3, y=2, z=7` | `x=6, y=5, z=9` | `x=1, y=0, z=3` | `x=6, y=4, z=7` | `x=8, y=7, z=9` | `x=2, y=0, z=4` | `x=5, y=1, z=7` | `x=6, y=4, z=9` | `x=8, y=0, z=9` | `x=2, y=1, z=4` | `x=4, y=1, z=8` | `x=3, y=0, z=4` | `x=3, y=1, z=5` | `x=7, y=5, z=8` | `x=6, y=2, z=9` | `x=2, y=0, z=4` | `x=7, y=6, z=9` | `x=2, y=1, z=6` | `x=3, y=0, z=8` | `x=5, y=3, z=8` | `x=5, y=0, z=9` | `x=4, y=0, z=9` | `x=7, y=5, z=8` | `x=4, y=2, z=7` | `x=3, y=1, z=6` | `x=2, y=0, z=4` | `x=4, y=0, z=8` | `x=2, y=1, z=8` | `x=5, y=3, z=9` | `x=4, y=3, z=5` | `x=6, y=4, z=9` | `x=7, y=6, z=8` | `x=3, y=1, z=9` | `x=4, y=2, z=7` | `x=1, y=0, z=6` | `x=1, y=0, z=5` | `x=7, y=0, z=9` | `x=4, y=0, z=7` | `x=3, y=2, z=9` | `x=4, y=1, z=6` | `x=5, y=2, z=9` | `x=8, y=0, z=9` | `x=2, y=1, z=9` | `x=4, y=3, z=6` | `x=6, y=0, z=9` | `x=3, y=1, z=4` | `x=7, y=6, z=8` | `x=6, y=1, z=7` | `x=6, y=2, z=7` | `x=3, y=0, z=9` | `x=5, y=4, z=9` | `x=8, y=6, z=9` | `x=5, y=3, z=6` | `x=2, y=1, z=7` | `x=3, y=0, z=5` | `x=6, y=1, z=8` | `x=2, y=0, z=5` | `x=2, y=0, z=9` | `x=6, y=5, z=8` | `x=2, y=0, z=4` | `x=5, y=0, z=9` | `x=1, y=0, z=9` | `x=3, y=1, z=6` | `x=3, y=1, z=5` | `x=5, y=1, z=9` | `x=6, y=2, z=7` | \n",
"| ------------- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | \n",
"| middle:708 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| middle:709 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| middle:710 | X | X | X | - | - | - | - | - | - | - | - | X | - | - | - | X | X | X | - | - | - | - | X | - | - | - | X | - | X | X | - | - | X | - | - | X | - | - | X | - | - | - | X | X | - | - | X | - | - | - | - | X | X | - | - | X | X | - | - | - | - | - | - | - | X | - | - | - | - | - | - | X | - | - | X | - | X | - | - | - | - | - | - | - | X | - | - | - | - | - | - | - | - | X | X | X | X | X | - | - | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| middle:711 | - | X | - | - | - | - | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | X | - | - | X | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | X | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | \n",
"| middle:712 | X | - | X | - | - | - | - | - | - | - | - | - | - | - | - | X | X | X | - | - | - | - | X | - | - | - | - | - | X | X | - | - | X | - | - | X | - | - | X | - | - | - | X | - | - | - | - | - | - | - | - | X | - | - | - | X | X | - | - | - | - | - | - | - | X | - | - | - | - | - | - | X | - | - | X | - | X | - | - | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | X | X | - | X | - | - | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| middle:713 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | X | - | - | - | X | - | - | - | - | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | X | - | - | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| middle:715 | - | - | - | X | X | X | X | X | X | X | X | - | X | X | X | - | - | - | X | X | X | X | - | X | X | X | - | X | - | - | X | X | - | X | X | - | X | X | - | X | X | X | - | - | X | X | - | X | X | X | X | - | - | X | X | - | - | X | X | X | X | X | X | X | - | X | X | X | X | X | X | - | X | X | - | X | - | X | X | X | X | X | X | X | - | X | X | X | X | X | X | X | X | - | - | - | - | - | X | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | \n",
"| middle:716 | - | - | - | - | - | - | X | - | X | - | - | - | - | - | X | - | - | - | X | - | - | X | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | X | - | - | - | X | X | - | - | - | X | - | - | X | - | - | - | - | X | - | - | - | - | X | - | X | X | - | - | X | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | \n",
"| middle:717 | - | - | - | X | X | X | - | X | - | X | X | - | X | X | - | - | - | - | - | X | X | - | - | X | - | X | - | X | - | - | X | X | - | X | X | - | X | X | - | - | X | X | - | - | X | X | - | X | X | X | X | - | - | - | X | - | - | - | - | X | X | X | - | X | - | - | X | X | X | X | - | - | X | X | - | - | - | - | - | X | X | - | X | X | - | X | X | - | X | X | X | X | X | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | \n",
"| middle:718 | - | - | - | X | X | - | - | X | - | - | - | - | - | - | - | - | - | - | - | X | - | - | - | - | - | - | - | X | - | - | X | - | - | - | - | - | - | X | - | - | X | X | - | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | X | X | - | X | - | - | - | - | X | - | - | - | - | X | - | - | - | - | - | X | X | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | \n",
"| middle:719 | X | - | X | - | - | X | - | - | - | X | X | - | X | X | - | - | X | X | - | - | X | - | X | X | - | X | - | - | - | X | - | X | - | X | X | X | X | - | X | - | - | - | - | - | X | X | - | X | - | X | X | X | - | - | X | X | X | - | - | X | - | - | - | - | X | - | X | X | - | X | - | X | X | - | - | - | X | - | - | - | - | - | X | - | - | X | X | - | X | X | X | X | X | - | X | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | \n",
"| middle_test:1 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| middle_test:2 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| middle_test:3 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n"
],
"text/plain": [
"[('middle', 713), ('middle', 712), ('middle', 710), ('middle_test', 2), ('middle', 708), ('middle_test', 3), ('middle_test', 1), ('middle', 709), ('middle', 716), ('middle', 719), ('middle', 711), ('middle', 717), ('middle', 715), ('middle', 718)]"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"middle_debugger"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The most suspicious line is:"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.087738Z",
"iopub.status.busy": "2023-11-12T12:47:30.087628Z",
"iopub.status.idle": "2023-11-12T12:47:30.121675Z",
"shell.execute_reply": "2023-11-12T12:47:30.121390Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"713 \u001b[34mreturn\u001b[39;49;00m y\u001b[37m\u001b[39;49;00m"
]
}
],
"source": [
"# ignore\n",
"location = middle_debugger.rank()[0]\n",
"(func_name, lineno) = location\n",
"lines, first_lineno = inspect.getsourcelines(middle)\n",
"print(lineno, end=\"\")\n",
"print_content(lines[lineno - first_lineno], '.py')"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"with a suspiciousness of:"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.123363Z",
"iopub.status.busy": "2023-11-12T12:47:30.123265Z",
"iopub.status.idle": "2023-11-12T12:47:30.125655Z",
"shell.execute_reply": "2023-11-12T12:47:30.125393Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"0.9667364890456637"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# ignore\n",
"middle_debugger.suspiciousness(location)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Random Code Mutations"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Our third step in automatic code repair is to _randomly mutate the code_. Specifically, we want to randomly _delete_, _insert_, and _replace_ statements in the program to be repaired. However, simply synthesizing code _from scratch_ is unlikely to yield anything meaningful – the number of combinations is simply far too high. Already for a three-character identifier name, we have more than 200,000 combinations:"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.127311Z",
"iopub.status.busy": "2023-11-12T12:47:30.127190Z",
"iopub.status.idle": "2023-11-12T12:47:30.128787Z",
"shell.execute_reply": "2023-11-12T12:47:30.128518Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import string"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.130245Z",
"iopub.status.busy": "2023-11-12T12:47:30.130156Z",
"iopub.status.idle": "2023-11-12T12:47:30.132326Z",
"shell.execute_reply": "2023-11-12T12:47:30.131948Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"string.ascii_letters"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.133875Z",
"iopub.status.busy": "2023-11-12T12:47:30.133766Z",
"iopub.status.idle": "2023-11-12T12:47:30.135985Z",
"shell.execute_reply": "2023-11-12T12:47:30.135709Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"210357"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(string.ascii_letters + '_') * \\\n",
" len(string.ascii_letters + '_' + string.digits) * \\\n",
" len(string.ascii_letters + '_' + string.digits)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Hence, we do _not_ synthesize code from scratch, but instead _reuse_ elements from the program to be fixed, hypothesizing that \"a program that contains an error in one area likely implements the correct behavior elsewhere\" \\cite{LeGoues2012}. This insight has been dubbed the *plastic surgery hypothesis*: content of new code can often be assembled out of fragments of code that already exist in the code base \\citeBarr2014}."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"For our \"plastic surgery\", we do not operate on a _textual_ representation of the program, but rather on a _structural_ representation, which by construction allows us to avoid lexical and syntactical errors in the first place.\n",
"\n",
"This structural representation is the _abstract syntax tree_ (AST), which we already have seen in various chapters, such as the [chapter on delta debugging](DeltaDebugger.ipynb), the [chapter on tracing](Tracer.ipynb), and excessively in the [chapter on slicing](Slicer.ipynb). The [official Python `ast` reference](http://docs.python.org/3/library/ast) is complete, but a bit brief; the documentation [\"Green Tree Snakes - the missing Python AST docs\"](https://greentreesnakes.readthedocs.io/en/latest/) provides an excellent introduction.\n",
"\n",
"Recapitulating, an AST is a tree representation of the program, showing a hierarchical structure of the program's elements. Here is the AST for our `middle()` function."
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.137611Z",
"iopub.status.busy": "2023-11-12T12:47:30.137501Z",
"iopub.status.idle": "2023-11-12T12:47:30.139102Z",
"shell.execute_reply": "2023-11-12T12:47:30.138814Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import ast\n",
"import inspect"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.140615Z",
"iopub.status.busy": "2023-11-12T12:47:30.140510Z",
"iopub.status.idle": "2023-11-12T12:47:30.142072Z",
"shell.execute_reply": "2023-11-12T12:47:30.141832Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from bookutils import print_content, show_ast"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.143707Z",
"iopub.status.busy": "2023-11-12T12:47:30.143588Z",
"iopub.status.idle": "2023-11-12T12:47:30.145272Z",
"shell.execute_reply": "2023-11-12T12:47:30.145031Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def middle_tree() -> ast.AST:\n",
" return ast.parse(inspect.getsource(middle))"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.146783Z",
"iopub.status.busy": "2023-11-12T12:47:30.146673Z",
"iopub.status.idle": "2023-11-12T12:47:30.566795Z",
"shell.execute_reply": "2023-11-12T12:47:30.566373Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"show_ast(middle_tree())"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
" You see that it consists of one function definition (`FunctionDef`) with three `arguments` and two statements – one `If` and one `Return`. Each `If` subtree has three branches – one for the condition (`test`), one for the body to be executed if the condition is true (`body`), and one for the `else` case (`orelse`). The `body` and `orelse` branches again are lists of statements."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"An AST can also be shown as text, which is more compact, yet reveals more information. `ast.dump()` gives not only the class names of elements, but also how they are constructed – actually, the whole expression can be used to construct an AST."
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.568651Z",
"iopub.status.busy": "2023-11-12T12:47:30.568529Z",
"iopub.status.idle": "2023-11-12T12:47:30.570905Z",
"shell.execute_reply": "2023-11-12T12:47:30.570648Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Module(body=[FunctionDef(name='middle', args=arguments(posonlyargs=[], args=[arg(arg='x'), arg(arg='y'), arg(arg='z')], kwonlyargs=[], kw_defaults=[], defaults=[]), body=[If(test=Compare(left=Name(id='y', ctx=Load()), ops=[Lt()], comparators=[Name(id='z', ctx=Load())]), body=[If(test=Compare(left=Name(id='x', ctx=Load()), ops=[Lt()], comparators=[Name(id='y', ctx=Load())]), body=[Return(value=Name(id='y', ctx=Load()))], orelse=[If(test=Compare(left=Name(id='x', ctx=Load()), ops=[Lt()], comparators=[Name(id='z', ctx=Load())]), body=[Return(value=Name(id='y', ctx=Load()))], orelse=[])])], orelse=[If(test=Compare(left=Name(id='x', ctx=Load()), ops=[Gt()], comparators=[Name(id='y', ctx=Load())]), body=[Return(value=Name(id='y', ctx=Load()))], orelse=[If(test=Compare(left=Name(id='x', ctx=Load()), ops=[Gt()], comparators=[Name(id='z', ctx=Load())]), body=[Return(value=Name(id='x', ctx=Load()))], orelse=[])])]), Return(value=Name(id='z', ctx=Load()))], decorator_list=[])], type_ignores=[])\n"
]
}
],
"source": [
"print(ast.dump(middle_tree()))"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"This is the path to the first `return` statement:"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.572373Z",
"iopub.status.busy": "2023-11-12T12:47:30.572262Z",
"iopub.status.idle": "2023-11-12T12:47:30.574629Z",
"shell.execute_reply": "2023-11-12T12:47:30.574362Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"\"Return(value=Name(id='y', ctx=Load()))\""
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ast.dump(middle_tree().body[0].body[0].body[0].body[0]) # type: ignore"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Picking Statements"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"For our mutation operators, we want to use statements from the program itself. Hence, we need a means to find those very statements. The `StatementVisitor` class iterates through an AST, adding all statements it finds in function definitions to its `statements` list. To do so, it subclasses the Python `ast` `NodeVisitor` class, described in the [official Python `ast` reference](http://docs.python.org/3/library/ast)."
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.576180Z",
"iopub.status.busy": "2023-11-12T12:47:30.576065Z",
"iopub.status.idle": "2023-11-12T12:47:30.577736Z",
"shell.execute_reply": "2023-11-12T12:47:30.577457Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from ast import NodeVisitor"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.579297Z",
"iopub.status.busy": "2023-11-12T12:47:30.579169Z",
"iopub.status.idle": "2023-11-12T12:47:30.580923Z",
"shell.execute_reply": "2023-11-12T12:47:30.580673Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"# ignore\n",
"from typing import Any, Callable, Optional, Type, Tuple\n",
"from typing import Dict, Union, Set, List, cast"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.582516Z",
"iopub.status.busy": "2023-11-12T12:47:30.582398Z",
"iopub.status.idle": "2023-11-12T12:47:30.587038Z",
"shell.execute_reply": "2023-11-12T12:47:30.586717Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class StatementVisitor(NodeVisitor):\n",
" \"\"\"Visit all statements within function defs in an AST\"\"\"\n",
"\n",
" def __init__(self) -> None:\n",
" self.statements: List[Tuple[ast.AST, str]] = []\n",
" self.func_name = \"\"\n",
" self.statements_seen: Set[Tuple[ast.AST, str]] = set()\n",
" super().__init__()\n",
"\n",
" def add_statements(self, node: ast.AST, attr: str) -> None:\n",
" elems: List[ast.AST] = getattr(node, attr, [])\n",
" if not isinstance(elems, list):\n",
" elems = [elems] # type: ignore\n",
"\n",
" for elem in elems:\n",
" stmt = (elem, self.func_name)\n",
" if stmt in self.statements_seen:\n",
" continue\n",
"\n",
" self.statements.append(stmt)\n",
" self.statements_seen.add(stmt)\n",
"\n",
" def visit_node(self, node: ast.AST) -> None:\n",
" # Any node other than the ones listed below\n",
" self.add_statements(node, 'body')\n",
" self.add_statements(node, 'orelse')\n",
"\n",
" def visit_Module(self, node: ast.Module) -> None:\n",
" # Module children are defs, classes and globals - don't add\n",
" super().generic_visit(node)\n",
"\n",
" def visit_ClassDef(self, node: ast.ClassDef) -> None:\n",
" # Class children are defs and globals - don't add\n",
" super().generic_visit(node)\n",
"\n",
" def generic_visit(self, node: ast.AST) -> None:\n",
" self.visit_node(node)\n",
" super().generic_visit(node)\n",
"\n",
" def visit_FunctionDef(self,\n",
" node: Union[ast.FunctionDef, ast.AsyncFunctionDef]) -> None:\n",
" if not self.func_name:\n",
" self.func_name = node.name\n",
"\n",
" self.visit_node(node)\n",
" super().generic_visit(node)\n",
" self.func_name = \"\"\n",
"\n",
" def visit_AsyncFunctionDef(self, node: ast.AsyncFunctionDef) -> None:\n",
" return self.visit_FunctionDef(node)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The function `all_statements()` returns all statements in the given AST `tree`. If an `ast` class `tp` is given, it only returns instances of that class."
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.588823Z",
"iopub.status.busy": "2023-11-12T12:47:30.588697Z",
"iopub.status.idle": "2023-11-12T12:47:30.591207Z",
"shell.execute_reply": "2023-11-12T12:47:30.590883Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def all_statements_and_functions(tree: ast.AST, \n",
" tp: Optional[Type] = None) -> \\\n",
" List[Tuple[ast.AST, str]]:\n",
" \"\"\"\n",
" Return a list of pairs (`statement`, `function`) for all statements in `tree`.\n",
" If `tp` is given, return only statements of that class.\n",
" \"\"\"\n",
"\n",
" visitor = StatementVisitor()\n",
" visitor.visit(tree)\n",
" statements = visitor.statements\n",
" if tp is not None:\n",
" statements = [s for s in statements if isinstance(s[0], tp)]\n",
"\n",
" return statements"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.592801Z",
"iopub.status.busy": "2023-11-12T12:47:30.592682Z",
"iopub.status.idle": "2023-11-12T12:47:30.594732Z",
"shell.execute_reply": "2023-11-12T12:47:30.594422Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def all_statements(tree: ast.AST, tp: Optional[Type] = None) -> List[ast.AST]:\n",
" \"\"\"\n",
" Return a list of all statements in `tree`.\n",
" If `tp` is given, return only statements of that class.\n",
" \"\"\"\n",
"\n",
" return [stmt for stmt, func_name in all_statements_and_functions(tree, tp)]"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Here are all the `return` statements in `middle()`:"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.596426Z",
"iopub.status.busy": "2023-11-12T12:47:30.596297Z",
"iopub.status.idle": "2023-11-12T12:47:30.598902Z",
"shell.execute_reply": "2023-11-12T12:47:30.598542Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"[,\n",
" ,\n",
" ,\n",
" ,\n",
" ]"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"all_statements(middle_tree(), ast.Return)"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.600615Z",
"iopub.status.busy": "2023-11-12T12:47:30.600470Z",
"iopub.status.idle": "2023-11-12T12:47:30.603238Z",
"shell.execute_reply": "2023-11-12T12:47:30.602959Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"[(, 'middle'),\n",
" (, 'middle'),\n",
" (, 'middle'),\n",
" (, 'middle'),\n",
" (, 'middle')]"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"all_statements_and_functions(middle_tree(), ast.If)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"We can randomly pick an element:"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.604839Z",
"iopub.status.busy": "2023-11-12T12:47:30.604719Z",
"iopub.status.idle": "2023-11-12T12:47:30.606392Z",
"shell.execute_reply": "2023-11-12T12:47:30.606132Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import random"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.607989Z",
"iopub.status.busy": "2023-11-12T12:47:30.607876Z",
"iopub.status.idle": "2023-11-12T12:47:30.610564Z",
"shell.execute_reply": "2023-11-12T12:47:30.610312Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'return y'"
]
},
"execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"random_node = random.choice(all_statements(middle_tree()))\n",
"ast.unparse(random_node)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Mutating Statements\n",
"\n",
"The main part in mutation, however, is to actually mutate the code of the program under test. To this end, we introduce a `StatementMutator` class – a subclass of `NodeTransformer`, described in the [official Python `ast` reference](http://docs.python.org/3/library/ast)."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The constructor provides various keyword arguments to configure the mutator."
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.612144Z",
"iopub.status.busy": "2023-11-12T12:47:30.612006Z",
"iopub.status.idle": "2023-11-12T12:47:30.613660Z",
"shell.execute_reply": "2023-11-12T12:47:30.613424Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from ast import NodeTransformer"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.615172Z",
"iopub.status.busy": "2023-11-12T12:47:30.615038Z",
"iopub.status.idle": "2023-11-12T12:47:30.616756Z",
"shell.execute_reply": "2023-11-12T12:47:30.616494Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import copy"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.618256Z",
"iopub.status.busy": "2023-11-12T12:47:30.618142Z",
"iopub.status.idle": "2023-11-12T12:47:30.621399Z",
"shell.execute_reply": "2023-11-12T12:47:30.621124Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class StatementMutator(NodeTransformer):\n",
" \"\"\"Mutate statements in an AST for automated repair.\"\"\"\n",
"\n",
" def __init__(self,\n",
" suspiciousness_func:\n",
" Optional[Callable[[Tuple[Callable, int]], float]] = None,\n",
" source: Optional[List[ast.AST]] = None,\n",
" log: Union[bool, int] = False) -> None:\n",
" \"\"\"\n",
" Constructor.\n",
" `suspiciousness_func` is a function that takes a location\n",
" (function, line_number) and returns a suspiciousness value\n",
" between 0 and 1.0. If not given, all locations get the same \n",
" suspiciousness of 1.0.\n",
" `source` is a list of statements to choose from.\n",
" \"\"\"\n",
"\n",
" super().__init__()\n",
" self.log = log\n",
"\n",
" if suspiciousness_func is None:\n",
" def suspiciousness_func(location: Tuple[Callable, int]) -> float:\n",
" return 1.0\n",
" assert suspiciousness_func is not None\n",
"\n",
" self.suspiciousness_func: Callable = suspiciousness_func\n",
"\n",
" if source is None:\n",
" source = []\n",
" self.source = source\n",
"\n",
" if self.log > 1:\n",
" for i, node in enumerate(self.source):\n",
" print(f\"Source for repairs #{i}:\")\n",
" print_content(ast.unparse(node), '.py')\n",
" print()\n",
" print()\n",
"\n",
" self.mutations = 0"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### Choosing Suspicious Statements to Mutate\n",
"\n",
"We start with deciding which AST nodes to mutate. The method `node_suspiciousness()` returns the suspiciousness for a given node, by invoking the suspiciousness function `suspiciousness_func` given during initialization."
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.622796Z",
"iopub.status.busy": "2023-11-12T12:47:30.622709Z",
"iopub.status.idle": "2023-11-12T12:47:30.624202Z",
"shell.execute_reply": "2023-11-12T12:47:30.623944Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import warnings"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.625483Z",
"iopub.status.busy": "2023-11-12T12:47:30.625401Z",
"iopub.status.idle": "2023-11-12T12:47:30.627736Z",
"shell.execute_reply": "2023-11-12T12:47:30.627406Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class StatementMutator(StatementMutator):\n",
" def node_suspiciousness(self, stmt: ast.AST, func_name: str) -> float:\n",
" if not hasattr(stmt, 'lineno'):\n",
" warnings.warn(f\"{self.format_node(stmt)}: Expected line number\")\n",
" return 0.0\n",
"\n",
" suspiciousness = self.suspiciousness_func((func_name, stmt.lineno))\n",
" if suspiciousness is None: # not executed\n",
" return 0.0\n",
"\n",
" return suspiciousness\n",
"\n",
" def format_node(self, node: ast.AST) -> str: # type: ignore\n",
" ..."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The method `node_to_be_mutated()` picks a node (statement) to be mutated. It determines the suspiciousness of all statements, and invokes `random.choices()`, using the suspiciousness as weight. Unsuspicious statements (with zero weight) will not be chosen."
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.629235Z",
"iopub.status.busy": "2023-11-12T12:47:30.629139Z",
"iopub.status.idle": "2023-11-12T12:47:30.632249Z",
"shell.execute_reply": "2023-11-12T12:47:30.631848Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class StatementMutator(StatementMutator):\n",
" def node_to_be_mutated(self, tree: ast.AST) -> ast.AST:\n",
" statements = all_statements_and_functions(tree)\n",
" assert len(statements) > 0, \"No statements\"\n",
"\n",
" weights = [self.node_suspiciousness(stmt, func_name) \n",
" for stmt, func_name in statements]\n",
" stmts = [stmt for stmt, func_name in statements]\n",
"\n",
" if self.log > 1:\n",
" print(\"Weights:\")\n",
" for i, stmt in enumerate(statements):\n",
" node, func_name = stmt\n",
" print(f\"{weights[i]:.2} {self.format_node(node)}\")\n",
"\n",
" if sum(weights) == 0.0:\n",
" # No suspicious line\n",
" return random.choice(stmts)\n",
" else:\n",
" return random.choices(stmts, weights=weights)[0]"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### Choosing a Mutation Method"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The method `visit()` is invoked on all nodes. For nodes marked with a `mutate_me` attribute, it randomly chooses a mutation method (`choose_op()`) and then invokes it on the node.\n",
"\n",
"According to the rules of `NodeTransformer`, the mutation method can return\n",
"\n",
"* a new node or a list of nodes, replacing the current node;\n",
"* `None`, deleting it; or\n",
"* the node itself, keeping things as they are."
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.634072Z",
"iopub.status.busy": "2023-11-12T12:47:30.633931Z",
"iopub.status.idle": "2023-11-12T12:47:30.635625Z",
"shell.execute_reply": "2023-11-12T12:47:30.635362Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import re"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.637126Z",
"iopub.status.busy": "2023-11-12T12:47:30.636992Z",
"iopub.status.idle": "2023-11-12T12:47:30.638721Z",
"shell.execute_reply": "2023-11-12T12:47:30.638477Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"RE_SPACE = re.compile(r'[ \\t\\n]+')"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.640246Z",
"iopub.status.busy": "2023-11-12T12:47:30.640141Z",
"iopub.status.idle": "2023-11-12T12:47:30.642575Z",
"shell.execute_reply": "2023-11-12T12:47:30.642315Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class StatementMutator(StatementMutator):\n",
" def choose_op(self) -> Callable:\n",
" return random.choice([self.insert, self.swap, self.delete])\n",
"\n",
" def visit(self, node: ast.AST) -> ast.AST:\n",
" super().visit(node) # Visits (and transforms?) children\n",
"\n",
" if not node.mutate_me: # type: ignore\n",
" return node\n",
"\n",
" op = self.choose_op()\n",
" new_node = op(node)\n",
" self.mutations += 1\n",
"\n",
" if self.log:\n",
" print(f\"{node.lineno:4}:{op.__name__ + ':':7} \"\n",
" f\"{self.format_node(node)} \"\n",
" f\"becomes {self.format_node(new_node)}\")\n",
"\n",
" return new_node"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### Swapping Statements\n",
"\n",
"Our first mutator is `swap()`, which replaces the current node `NODE` by a random node found in `source` (using a newly defined `choose_statement()`).\n",
"\n",
"As a rule of thumb, we try to avoid inserting entire subtrees with all attached statements; and try to respect only the first line of a node. If the new node has the form \n",
"\n",
"```python\n",
"if P:\n",
" BODY\n",
"```\n",
"\n",
"we thus only insert \n",
"\n",
"```python\n",
"if P: \n",
" pass\n",
"```\n",
"\n",
"since the statements in `BODY` have a later chance to get inserted. The same holds for all constructs that have a `BODY`, i.e. `while`, `for`, `try`, `with`, and more."
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.644056Z",
"iopub.status.busy": "2023-11-12T12:47:30.643943Z",
"iopub.status.idle": "2023-11-12T12:47:30.645704Z",
"shell.execute_reply": "2023-11-12T12:47:30.645486Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class StatementMutator(StatementMutator):\n",
" def choose_statement(self) -> ast.AST:\n",
" return copy.deepcopy(random.choice(self.source))"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.647089Z",
"iopub.status.busy": "2023-11-12T12:47:30.646982Z",
"iopub.status.idle": "2023-11-12T12:47:30.649511Z",
"shell.execute_reply": "2023-11-12T12:47:30.649235Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class StatementMutator(StatementMutator):\n",
" def swap(self, node: ast.AST) -> ast.AST:\n",
" \"\"\"Replace `node` with a random node from `source`\"\"\"\n",
" new_node = self.choose_statement()\n",
"\n",
" if isinstance(new_node, ast.stmt):\n",
" # The source `if P: X` is added as `if P: pass`\n",
" if hasattr(new_node, 'body'):\n",
" new_node.body = [ast.Pass()] # type: ignore\n",
" if hasattr(new_node, 'orelse'):\n",
" new_node.orelse = [] # type: ignore\n",
" if hasattr(new_node, 'finalbody'):\n",
" new_node.finalbody = [] # type: ignore\n",
"\n",
" # ast.copy_location(new_node, node)\n",
" return new_node"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### Inserting Statements\n",
"\n",
"Our next mutator is `insert()`, which randomly chooses some node from `source` and inserts it after the current node `NODE`. (If `NODE` is a `return` statement, then we insert the new node _before_ `NODE`.)\n",
"\n",
"If the statement to be inserted has the form\n",
"\n",
"```python\n",
"if P:\n",
" BODY\n",
"```\n",
"\n",
"we only insert the \"header\" of the `if`, resulting in\n",
"\n",
"```python\n",
"if P: \n",
" NODE\n",
"```\n",
"\n",
"Again, this applies to all constructs that have a `BODY`, i.e., `while`, `for`, `try`, `with`, and more."
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.651067Z",
"iopub.status.busy": "2023-11-12T12:47:30.650958Z",
"iopub.status.idle": "2023-11-12T12:47:30.653755Z",
"shell.execute_reply": "2023-11-12T12:47:30.653501Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class StatementMutator(StatementMutator):\n",
" def insert(self, node: ast.AST) -> Union[ast.AST, List[ast.AST]]:\n",
" \"\"\"Insert a random node from `source` after `node`\"\"\"\n",
" new_node = self.choose_statement()\n",
"\n",
" if isinstance(new_node, ast.stmt) and hasattr(new_node, 'body'):\n",
" # Inserting `if P: X` as `if P:`\n",
" new_node.body = [node] # type: ignore\n",
" if hasattr(new_node, 'orelse'):\n",
" new_node.orelse = [] # type: ignore\n",
" if hasattr(new_node, 'finalbody'):\n",
" new_node.finalbody = [] # type: ignore\n",
" # ast.copy_location(new_node, node)\n",
" return new_node\n",
"\n",
" # Only insert before `return`, not after it\n",
" if isinstance(node, ast.Return):\n",
" if isinstance(new_node, ast.Return):\n",
" return new_node\n",
" else:\n",
" return [new_node, node]\n",
"\n",
" return [node, new_node]"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### Deleting Statements\n",
"\n",
"Our last mutator is `delete()`, which deletes the current node `NODE`. The standard case is to replace `NODE` by a `pass` statement.\n",
"\n",
"If the statement to be deleted has the form\n",
"\n",
"```python\n",
"if P:\n",
" BODY\n",
"```\n",
"\n",
"we only delete the \"header\" of the `if`, resulting in\n",
"\n",
"```python\n",
"BODY\n",
"```\n",
"\n",
"Again, this applies to all constructs that have a `BODY`, i.e., `while`, `for`, `try`, `with`, and more. If the statement to be deleted has multiple branches, a random branch is chosen (e.g., the `else` branch of an `if` statement)."
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.655451Z",
"iopub.status.busy": "2023-11-12T12:47:30.655338Z",
"iopub.status.idle": "2023-11-12T12:47:30.657848Z",
"shell.execute_reply": "2023-11-12T12:47:30.657555Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class StatementMutator(StatementMutator):\n",
" def delete(self, node: ast.AST) -> None:\n",
" \"\"\"Delete `node`.\"\"\"\n",
"\n",
" branches = [attr for attr in ['body', 'orelse', 'finalbody']\n",
" if hasattr(node, attr) and getattr(node, attr)]\n",
" if branches:\n",
" # Replace `if P: S` by `S`\n",
" branch = random.choice(branches)\n",
" new_node = getattr(node, branch)\n",
" return new_node\n",
"\n",
" if isinstance(node, ast.stmt):\n",
" # Avoid empty bodies; make this a `pass` statement\n",
" new_node = ast.Pass()\n",
" ast.copy_location(new_node, node)\n",
" return new_node\n",
"\n",
" return None # Just delete"
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.659310Z",
"iopub.status.busy": "2023-11-12T12:47:30.659205Z",
"iopub.status.idle": "2023-11-12T12:47:30.660801Z",
"shell.execute_reply": "2023-11-12T12:47:30.660564Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from bookutils import quiz"
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:30.662150Z",
"iopub.status.busy": "2023-11-12T12:47:30.662068Z",
"iopub.status.idle": "2023-11-12T12:47:30.666886Z",
"shell.execute_reply": "2023-11-12T12:47:30.666637Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
" \n",
" \n",
" \n",
"
\n",
"
Quiz
\n",
"
\n",
"
Why are statements replaced by pass rather than deleted?
\n"
],
"text/markdown": [
"| `remove_html_markup_test` | `html='Sg$VTJ9Ji .)!$', plain='Sg$VTJ9Ji .)!$'` | `html='c[7dZC||=_:IPwT', plain='c[7dZC||=_:IPwT'` | `html='?mkp5wc4VGp~(8;', plain='?mkp5wc4VGp~(8;'` | `html='kJ(^Xo1GvK-r=rx', plain='kJ(^Xo1GvK-r=rx'` | `html='\\'36)=z(s)H$2!K5', plain=\"'36)=z(s)H$2!K5\"` | `html='N2_IRbB*-AfI!B', plain='N2_IRbB*-AfI!B'` | `html='pVJ.Nsf|[x;}5G', plain='pVJ.Nsf|[x;}5G'` | `html='GbMf1U9W7K0 RRn', plain='GbMf1U9W7K0 RRn'` | `html='+JMW-[[kT{[(\\\\Y', plain='+JMW-[[kT{[(\\\\Y'` | `html='6dxT f}b6?1N-2G', plain='6dxT f}b6?1N-2G'` | `html=';Uxz2r}LpZ9DU;k', plain=';Uxz2r}LpZ9DU;k'` | `html='us;pjg9H?VStQ{&', plain='us;pjg9H?VStQ{&'` | `html='UA4|^_naW]LK`', plain='UA4|^_naW]LK`'` | `html='ewF*0|h0pI4 J%L', plain='ewF*0|h0pI4 J%L'` | `html='RO9Ng1O58A[Dwc}', plain='RO9Ng1O58A[Dwc}'` | `html=';,EyYUYhzv1$yFX', plain=';,EyYUYhzv1$yFX'` | `html='jq^xl?)hnUpEV:U', plain='jq^xl?)hnUpEV:U'` | `html='GU^M5k/!E?+03,e', plain='GU^M5k/!E?+03,e'` | `html='O!nl4=eXxNfNF7', plain='O!nl4=eXxNfNF7'` | `html='S0iSL5$Djr0xmUJ', plain='S0iSL5$Djr0xmUJ'` | `html='`J,6~st_/1?9vT', plain='`J,6~st_/1?9vT'` | `html='7b~7?]z@M\\'czAPi', plain=\"7b~7?]z@M'czAPi\"` | `html='FdTLX-`/`^.Nq$@', plain='FdTLX-`/`^.Nq$@'` | `html='Q|tMFI)5&C??r`(', plain='Q|tMFI)5&C??r`('` | `html='G6/=\\'JEC)zgh)', plain=\"G6/='JEC)zgh)\"` | `html='=-(.8)Qr+3G;pNr', plain='=-(.8)Qr+3G;pNr'` | `html='[$QM}kc?/zec2j', plain='[$QM}kc?/zec2j'` | `html='U|LON/dC# b\\\\7Y', plain='U|LON/dC# b\\\\7Y'` | `html='G]{`6|Q)Qx.KHF', plain='G]{`6|Q)Qx.KHF'` | `html='9_/q^Cxk+wlgC[{', plain='9_/q^Cxk+wlgC[{'` | `html='y3r&Ha/u2Z B%kV', plain='y3r&Ha/u2Z B%kV'` | `html='J3VCvmS3mSotN0', plain='J3VCvmS3mSotN0'` | `html='\\\\m{Z6lgztlL{TF', plain='\\\\m{Z6lgztlL{TF'` | `html='55x4i<=\">He*R:;)Xb', plain='55x4iHe*R:;)Xb'` | `html='3*sMU.hx@bd-#p ', plain='3*sMU.hx@bd-#p '` | `html='bFJH7,kWy1V*7a4', plain='bFJH7,kWy1V*7a4'` | `html='\\'I,!kb\">KEK(bWLCLG', plain=\"'I,!kKEK(bWLCLG\"` | `html='0J3eTXP11)rn|%', plain='0J3eTXP11)rn|%'` | `html='RfVB!Ld9Db.8D/', plain='RfVB!Ld9Db.8D/'` | `html='im/RZ] u8(h3JF9', plain='im/RZ] u8(h3JF9'` | `html='G{jv0r32Tioa0$F', plain='G{jv0r32Tioa0$F'` | `html='Im#f.)QY/fF]m`6', plain='Im#f.)QY/fF]m`6'` | `html='v/{0oby|@,!\\'6#', plain=\"v/{0oby|@,!'6#\"` | `html='h{-VT 1wQavu|bz', plain='h{-VT 1wQavu|bz'` | `html='9t(c1!&RQZH#la', plain='9t(c1!&RQZH#la'` | `html='$p.)7;];`N5*Nu/', plain='$p.)7;];`N5*Nu/'` | `html='ML=)aa_l\\'EP9{|-', plain=\"ML=)aa_l'EP9{|-\"` | `html='LGTG}A]j`?5{,^X', plain='LGTG}A]j`?5{,^X'` | `html='m,iUT\\'jOzMiT2=H', plain=\"m,iUT'jOzMiT2=H\"` | `html='9H%6!|zx6m~7GP;', plain='9H%6!|zx6m~7GP;'` | `html='MFr*8C; F-ZQSGd', plain='MFr*8C; F-ZQSGd'` | `html='F.8)Gmn.V}-uk /', plain='F.8)Gmn.V}-uk /'` | `html='Kxp=_i!_G^+SDm.', plain='Kxp=_i!_G^+SDm.'` | `html='k]w\\'`\">DIho`&fD(N', plain=\"k]w'`DIho`&fD(N\"` | `html='h~k)7wIh!b\\\\D:|d', plain='h~k)7wIh!b\\\\D:|d'` | `html='(jj@9HRScIg}9=m', plain='(jj@9HRScIg}9=m'` | `html='rrCyc#q_CM#)`j,', plain='rrCyc#q_CM#)`j,'` | `html='r_l!YbL/CVvkSQ', plain='r_l!YbL/CVvkSQ'` | `html='^*G6qUv|cAh8jqE', plain='^*G6qUv|cAh8jqE'` | `html='Ta;mM}qy;Jr])', plain='Ta;mM}qy;Jr])'` | `html='R^C-pLRR:6#sS1C', plain='R^C-pLRR:6#sS1C'` | `html='(6`[&|@@W}$j8-s', plain='(6`[&|@@W}$j8-s'` | `html='_YB!;SF:sTU^GK8', plain='_YB!;SF:sTU^GK8'` | `html='#ancJ$}b\\'Ab4NB]', plain=\"#ancJ$}b'Ab4NB]\"` | `html='S^foP5 T-=sszJb', plain='S^foP5 T-=sszJb'` | `html='HJ6Jy85ZAn%h&d#', plain='HJ6Jy85ZAn%h&d#'` | `html='7.:z^B|&0S~o2j', plain='7.:z^B|&0S~o2j'` | `html='(0:$IUFMdGum?jU', plain='(0:$IUFMdGum?jU'` | `html='PdnU~&/;7X\\'r,Tv', plain=\"PdnU~&/;7X'r,Tv\"` | `html='P`,Jz3&9)K{WLp5', plain='P`,Jz3&9)K{WLp5'` | `html='/8BmYb@7Q9.dpu]', plain='/8BmYb@7Q9.dpu]'` | `html='.n:f;gYJswj:VO&', plain='.n:f;gYJswj:VO&'` | `html='TPUiP;h^D0YR[j', plain='TPUiP;h^D0YR[j'` | `html='@u04rSycYFn9[v8', plain='@u04rSycYFn9[v8'` | `html='k1mAeXJ/vMO4\\'\\\\#', plain=\"k1mAeXJ/vMO4'\\\\#\"` | `html='[JT7\\\\(;)B20l0K', plain='[JT7\\\\(;)B20l0K'` | `html='Q-E\\\\@4chbSO.%h', plain='Q-E\\\\@4chbSO.%h'` | `html='`8]zYOvIV#^SYN', plain='`8]zYOvIV#^SYN'` | `html='7T \\'Z!yMBuFem~o', plain=\"7T 'Z!yMBuFem~o\"` | `html='eTqeE7oMP8CCw#o', plain='eTqeE7oMP8CCw#o'` | `html='=;FK6@KaJre7@B;', plain='=;FK6@KaJre7@B;'` | `html='AbZXcKI6xC0y1z', plain='AbZXcKI6xC0y1z'` | `html='de G]F[.FZC0aWH', plain='de G]F[.FZC0aWH'` | `html='(8wa`~aB\">LuxO!px+|_', plain='(8wa`LuxO!px+|_'` | `html='5Ub;jx\">*+^YENJ{5', plain='5Ub;j*+^YENJ{5'` | `html='kvoFCx+`OBt~ZR=', plain='kvoFCx+`OBt~ZR='` | `html='CTIUHszx.C]zno', plain='CTIUHszx.C]zno'` | `html='+v)#7]OqTrJ~7y ', plain='+v)#7]OqTrJ~7y '` | `html='5:]W!\\\\b;!&:j$?.', plain='5:]W!\\\\b;!&:j$?.'` | `html='My$$HO#=hF`NvE', plain='My$$HO#=hF`NvE'` | `html='K(]1X2\">j7l9 c[fJ2', plain='K(]1Xj7l9 c[fJ2'` | `html='JX7aSNS.\">]ea$xl[/0', plain='JX7aS]ea$xl[/0'` | `html='*TH?Ml\\\\4_:w3MB', plain='*TH?Ml\\\\4_:w3MB'` | `html='cd ~)tPG{p$X1cz', plain='cd ~)tPG{p$X1cz'` | `html='w^1X*BD)Q:Vj9~n', plain='w^1X*BD)Q:Vj9~n'` | `html='c+k&}xR4Z28})F', plain='c+k&}xR4Z28})F'` | `html='6t0qeJ;L`]A\\'8y', plain=\"6t0qeJ;L`]A'8y\"` | `html='r7+,]*N*E0yvzxU', plain='r7+,]*N*E0yvzxU'` | `html='#6(RDp\">.0puqykQ^/', plain='#6(RD.0puqykQ^/'` | `html='N&p:i+-..ZaN*%', plain='N&p:i+-..ZaN*%'` | `html='3AGe7\"!%H6azh_', plain='3AGe7\"!%H6azh_'` | `html='1qCi2H\"\\\\m~#yi\"(', plain='1qCi2H\"\\\\m~#yi\"('` | `html='{]#_j2Ha6a#]o|\"', plain='{]#_j2Ha6a#]o|\"'` | `html='::%hZ.8Nb4\"z5t7', plain='::%hZ.8Nb4\"z5t7'` | `html='A#ZLzhZ9}d\"&E22', plain='A#ZLzhZ9}d\"&E22'` | `html='mzd%4@e+-abZGP\"', plain='mzd%4@e+-abZGP\"'` | `html='T4*dS/RO{\"@G#v', plain='T4*dS/RO{\"@G#v'` | `html='nGbORFBFO[@D\\\\\"`', plain='nGbORFBFO[@D\\\\\"`'` | `html='9?c3;fq\"Mvs&fr7', plain='9?c3;fq\"Mvs&fr7'` | `html='\"Y^0?-1XPjy04ex', plain='\"Y^0?-1XPjy04ex'` | `html='fhj\"xGrOt30=9!r', plain='fhj\"xGrOt30=9!r'` | `html='0m@U|9D_7ru5O\"}', plain='0m@U|9D_7ru5O\"}'` | `html='dKO\"jDe6KMhmAFC', plain='dKO\"jDe6KMhmAFC'` | `html='QI8%`%},-\"\\\\%MC0', plain='QI8%`%},-\"\\\\%MC0'` | `html='v|~X\"kmjI|jGETx', plain='v|~X\"kmjI|jGETx'` | `html='QcuA\"dE8j3T1-xZ', plain='QcuA\"dE8j3T1-xZ'` | `html='D.}Jm@\"u{I_12C ', plain='D.}Jm@\"u{I_12C '` | `html='Z\"Wls,T(NX`hlE\\\\', plain='Z\"Wls,T(NX`hlE\\\\'` | `html='&R&\\\\f=kg*P*\"!3-', plain='&R&\\\\f=kg*P*\"!3-'` | `html='5J;dD#8coXoE \";', plain='5J;dD#8coXoE \";'` | `html='pS:d\\'arbC.Xk3\"u', plain='pS:d\\'arbC.Xk3\"u'` | `html='`lSot[\\\\q\">|b{kG\"\"]yi', plain='`lSot|b{kG\"\"]yi'` | `html='ry`::@k*xL@v\"H6', plain='ry`::@k*xL@v\"H6'` | `html='W76\\\\ =mdG7}&\"Jo', plain='W76\\\\ =mdG7}&\"Jo'` | `html='`Hofd]v\"gft?,9*', plain='`Hofd]v\"gft?,9*'` | `html='lQs3V\"OfSMOboL&', plain='lQs3V\"OfSMOboL&'` | `html='\"PjqqLC712k@_?)', plain='\"PjqqLC712k@_?)'` | `html='h9tH*B\">.NwH$`Kz8\"', plain='h9tH*.NwH$`Kz8\"'` | `html='QL\" Zw,-,,u8d-7', plain='QL\" Zw,-,,u8d-7'` | `html=';bHXrtM2__Y8\"Ec', plain=';bHXrtM2__Y8\"Ec'` | `html=';3\\\\ZvB\"T\\'ZLfSg)', plain=';3\\\\ZvB\"T\\'ZLfSg)'` | `html='G-V,8n\"jh?57I@Z', plain='G-V,8n\"jh?57I@Z'` | `html='V#,UP\"7W,/|F;5\\'', plain='V#,UP\"7W,/|F;5\\''` | `html='ALm(K\"OMfG~V#{y', plain='ALm(K\"OMfG~V#{y'` | `html='6\"{q%2b@hG.FL9D', plain='6\"{q%2b@hG.FL9D'` | `html='QnX\"vXfOYuMBLs5', plain='QnX\"vXfOYuMBLs5'` | `html='p)*6o\"J&hEfU =', plain='p)*6o\"J&hEfU ='` | `html=', /\"&5S-pdG9G5', plain=', /\"&5S-pdG9G5'` | `html='1OCA^h#c\"K*QN\\\\', plain='1OCA^h#c\"K*QN\\\\'` | `html='R6\",q,\\'qx9-_s+a', plain='R6\",q,\\'qx9-_s+a'` | `html='q7=h\"b(Bn~5d,:r', plain='q7=h\"b(Bn~5d,:r'` | `html='686D5X,m\"Oh`kb', plain='686D5X,m\"Oh`kb'` | `html='\"urp35e\\\\L\">ew^7F?kHll', plain='\"urp3ew^7F?kHll'` | `html='1FH?P7+f(\"/919j', plain='1FH?P7+f(\"/919j'` | `html=';-E|05e\"@$e-\\'@h', plain=';-E|05e\"@$e-\\'@h'` | `html='4y;9^:z T\"Z;+=q', plain='4y;9^:z T\"Z;+=q'` | `html='V,!t=D\"N7iEjb7', plain='V,!t=D\"N7iEjb7'` | `html='tJ\"yOO.N-~38:P', plain='tJ\"yOO.N-~38:P'` | `html='5_\"@qw&gx(j4.$2', plain='5_\"@qw&gx(j4.$2'` | `html='tpJxZpom\"9&8tFr', plain='tpJxZpom\"9&8tFr'` | `html='\"+rJKWg`Lr9f-0', plain='\"+rJKWg`Lr9f-0'` | `html='1*vJ&\"5sBmxf_g]', plain='1*vJ&\"5sBmxf_g]'` | `html='jjcmnvq0-\"dC\\'|;', plain='jjcmnvq0-\"dC\\'|;'` | `html='H8Lf1&(DeIOB0\"/', plain='H8Lf1&(DeIOB0\"/'` | `html=',l4KwoG%\"w_9\\\\=', plain=',l4KwoG%\"w_9\\\\='` | `html='W5c]h\"I{h9cmCFS', plain='W5c]h\"I{h9cmCFS'` | `html='3#(2 (\">.EoiNvUc#\"', plain='3#(2 .EoiNvUc#\"'` | `html='F\"C1VPtkknd^m4,', plain='F\"C1VPtkknd^m4,'` | `html='3bwoO%%`\">F1BQ\"7=9Vd', plain='3bwoOF1BQ\"7=9Vd'` | `html='D1F-+\\\\cVX`7t:\"D', plain='D1F-+\\\\cVX`7t:\"D'` | `html='.[?=!4i\"-{{11np', plain='.[?=!4i\"-{{11np'` | `html=')cXlLQ9\"\\'\\'LRev1', plain=')cXlLQ9\"\\'\\'LRev1'` | `html='@|8Ft\\'D\"z~Ol%#4', plain='@|8Ft\\'D\"z~Ol%#4'` | `html='PR\"Q9vxT`61{pVe', plain='PR\"Q9vxT`61{pVe'` | `html='\"j5?FDp8R7qQz^?', plain='\"j5?FDp8R7qQz^?'` | `html=']L{V^MkEVO]\"G@Y', plain=']L{V^MkEVO]\"G@Y'` | `html='DN@\\'B31xWp:F^.\"', plain='DN@\\'B31xWp:F^.\"'` | `html='xKRw9qTs\"l1vg+g', plain='xKRw9qTs\"l1vg+g'` | `html='y+BtE|By/eU\\\\C\"W', plain='y+BtE|By/eU\\\\C\"W'` | `html='/j{m\"R@,+.195E', plain='/j{m\"R@,+.195E'` | `html='cv\"V9\\\\,*BD5a^&(', plain='cv\"V9\\\\,*BD5a^&('` | `html='\"sy;64o]T~/tI~ ', plain='\"sy;64o]T~/tI~ '` | `html='1_ 5UjM]`F\"ZsqZ', plain='1_ 5UjM]`F\"ZsqZ'` | `html='%\\'NeY\"yxnc{pv|?', plain='%\\'NeY\"yxnc{pv|?'` | `html='n{vAXPMFNvk\"ut@', plain='n{vAXPMFNvk\"ut@'` | `html='Nm]M_Pm__|$\"71', plain='Nm]M_Pm__|$\"71'` | `html='[Tst\"*=.@b%0Ox', plain='[Tst\"*=.@b%0Ox'` | `html='P+\"~VLteI3*Wp\\\\[', plain='P+\"~VLteI3*Wp\\\\['` | `html='g^1:yU6-);I*\"{a', plain='g^1:yU6-);I*\"{a'` | `html='\\'\"x~~[Vk@v1[\"2a', plain='\\'\"x~~[Vk@v1[\"2a'` | `html=']Y(+HAJ\"@GmaR 8', plain=']Y(+HAJ\"@GmaR 8'` | `html='FsWD,{&jChqm\"49', plain='FsWD,{&jChqm\"49'` | `html=',?k%CLi\"=i/NHm/', plain=',?k%CLi\"=i/NHm/'` | `html='.fE[/:5*fqHJ\"(', plain='.fE[/:5*fqHJ\"('` | `html='K*Xhtim\"9^K+p2c', plain='K*Xhtim\"9^K+p2c'` | `html='i\"[c6J?3Z\">^zs=xvo1Oz', plain='i\"[c6^zs=xvo1Oz'` | `html='\\\\iBTt#S\")8{%uOf', plain='\\\\iBTt#S\")8{%uOf'` | `html='84BNwqkPO\"Y@Nbj', plain='84BNwqkPO\"Y@Nbj'` | `html='x3nG&Ti\"wv]:Zhx', plain='x3nG&Ti\"wv]:Zhx'` | `html='ap!48,?[}U\"1OT3', plain='ap!48,?[}U\"1OT3'` | `html='+@s\"olO_:}q/f}3', plain='+@s\"olO_:}q/f}3'` | `html='o+=[yn=S&\"@PO~M', plain='o+=[yn=S&\"@PO~M'` | `html='C$ZQGw!Xb]G)\"~', plain='C$ZQGw!Xb]G)\"~'` | `html='V\\\\\"SR\">[Q~_!W6?i', plain='V\\\\\"S[Q~_!W6?i'` | `html='|^J5o{Y\"#f giGB', plain='|^J5o{Y\"#f giGB'` | `html='Y7Wl[]\"|b|_0IW;', plain='Y7Wl[]\"|b|_0IW;'` | `html='XU\\'Wo\"\\\\n2[RwGQh', plain='XU\\'Wo\"\\\\n2[RwGQh'` | `html='\"a\"U{e\"J{{LDMuI', plain='\"a\"U{e\"J{{LDMuI'` | `html='|vT#ytc2*.\"u.Q', plain='|vT#ytc2*.\"u.Q'` | `html='O8#k:jL(u\"y~;uf', plain='O8#k:jL(u\"y~;uf'` | \n",
"| ------------------------- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | \n",
"| remove_html_markup:1 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| remove_html_markup:2 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| remove_html_markup:3 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| remove_html_markup:4 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| remove_html_markup:6 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| remove_html_markup:7 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| remove_html_markup:8 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | - | - | X | - | X | - | - | X | - | X | X | X | X | X | X | X | X | - | X | X | X | X | X | X | X | - | - | X | - | X | - | - | X | - | X | X | X | X | - | - | X | - | X | X | X | X | X | X | - | X | X | X | X | X | - | - | X | X | X | X | - | - | - | X | X | X | X | X | - | X | - | X | X | X | X | X | - | X | X | X | X | - | X | X | - | X | X | X | X | X | X | \n",
"| remove_html_markup:9 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| remove_html_markup:10 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | - | - | X | - | X | - | - | X | - | X | X | X | X | X | X | X | X | - | X | - | X | X | X | X | X | - | - | X | - | X | - | - | X | X | X | X | X | X | - | - | X | - | X | X | X | X | X | X | - | X | X | X | X | X | - | - | X | X | X | X | - | - | - | X | X | X | X | X | - | X | - | X | X | X | X | X | X | X | X | X | X | - | X | X | X | X | X | X | X | X | X | \n",
"| remove_html_markup:11 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| remove_html_markup:12 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| remove_html_markup:13 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| remove_html_markup:14 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| remove_html_markup:16 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| remove_html_markup_test:1 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| remove_html_markup_test:2 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| remove_html_markup_test:3 | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n",
"| remove_html_markup_test:4 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | \n"
],
"text/plain": [
"[('remove_html_markup_test', 4), ('remove_html_markup', 2), ('remove_html_markup', 11), ('remove_html_markup', 14), ('remove_html_markup_test', 1), ('remove_html_markup', 3), ('remove_html_markup', 6), ('remove_html_markup', 12), ('remove_html_markup', 9), ('remove_html_markup_test', 2), ('remove_html_markup', 1), ('remove_html_markup', 7), ('remove_html_markup', 4), ('remove_html_markup', 13), ('remove_html_markup', 16), ('remove_html_markup_test', 3), ('remove_html_markup', 10), ('remove_html_markup', 8)]"
]
},
"execution_count": 160,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"html_debugger"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Let us create our repairer and run it."
]
},
{
"cell_type": "code",
"execution_count": 161,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:32.307573Z",
"iopub.status.busy": "2023-11-12T12:47:32.307459Z",
"iopub.status.idle": "2023-11-12T12:47:32.340992Z",
"shell.execute_reply": "2023-11-12T12:47:32.340712Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Target code to be repaired:\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mremove_html_markup\u001b[39;49;00m(s):\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" quote = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" out = \u001b[33m'\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mfor\u001b[39;49;00m c \u001b[35min\u001b[39;49;00m s:\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mif\u001b[39;49;00m c == \u001b[33m'\u001b[39;49;00m\u001b[33m<\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m \u001b[35mand\u001b[39;49;00m (\u001b[35mnot\u001b[39;49;00m quote):\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mTrue\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m c == \u001b[33m'\u001b[39;49;00m\u001b[33m>\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m \u001b[35mand\u001b[39;49;00m (\u001b[35mnot\u001b[39;49;00m quote):\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m c == \u001b[33m'\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m \u001b[35mor\u001b[39;49;00m (c == \u001b[33m\"\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m \u001b[35mand\u001b[39;49;00m tag):\u001b[37m\u001b[39;49;00m\n",
" quote = \u001b[35mnot\u001b[39;49;00m quote\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m \u001b[35mnot\u001b[39;49;00m tag:\u001b[37m\u001b[39;49;00m\n",
" out = out + c\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mreturn\u001b[39;49;00m out\u001b[37m\u001b[39;49;00m\n",
"\n"
]
}
],
"source": [
"html_repairer = Repairer(html_debugger, log=True)"
]
},
{
"cell_type": "code",
"execution_count": 162,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:32.342384Z",
"iopub.status.busy": "2023-11-12T12:47:32.342296Z",
"iopub.status.idle": "2023-11-12T12:47:38.676382Z",
"shell.execute_reply": "2023-11-12T12:47:38.676074Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Evolving population: iteration 19/20 fitness = 0.99 \r\n",
"Best code (fitness = 0.99):\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mremove_html_markup\u001b[39;49;00m(s):\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" quote = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" out = \u001b[33m'\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mfor\u001b[39;49;00m c \u001b[35min\u001b[39;49;00m s:\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mif\u001b[39;49;00m c == \u001b[33m'\u001b[39;49;00m\u001b[33m<\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m \u001b[35mand\u001b[39;49;00m (\u001b[35mnot\u001b[39;49;00m quote):\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mTrue\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m c == \u001b[33m'\u001b[39;49;00m\u001b[33m>\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m \u001b[35mand\u001b[39;49;00m (\u001b[35mnot\u001b[39;49;00m quote):\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m c == \u001b[33m'\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m \u001b[35mor\u001b[39;49;00m (c == \u001b[33m\"\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m \u001b[35mand\u001b[39;49;00m tag):\u001b[37m\u001b[39;49;00m\n",
" quote = \u001b[35mnot\u001b[39;49;00m quote\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m \u001b[35mnot\u001b[39;49;00m tag:\u001b[37m\u001b[39;49;00m\n",
" out = out + c\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mreturn\u001b[39;49;00m out\u001b[37m\u001b[39;49;00m\n",
"\n",
"Reduced code (fitness = 0.99):\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mremove_html_markup\u001b[39;49;00m(s):\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" quote = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" out = \u001b[33m'\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mfor\u001b[39;49;00m c \u001b[35min\u001b[39;49;00m s:\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mif\u001b[39;49;00m c == \u001b[33m'\u001b[39;49;00m\u001b[33m<\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m \u001b[35mand\u001b[39;49;00m (\u001b[35mnot\u001b[39;49;00m quote):\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mTrue\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m c == \u001b[33m'\u001b[39;49;00m\u001b[33m>\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m \u001b[35mand\u001b[39;49;00m (\u001b[35mnot\u001b[39;49;00m quote):\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m c == \u001b[33m'\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m \u001b[35mor\u001b[39;49;00m (c == \u001b[33m\"\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m \u001b[35mand\u001b[39;49;00m tag):\u001b[37m\u001b[39;49;00m\n",
" quote = \u001b[35mnot\u001b[39;49;00m quote\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m \u001b[35mnot\u001b[39;49;00m tag:\u001b[37m\u001b[39;49;00m\n",
" out = out + c\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mreturn\u001b[39;49;00m out\u001b[37m\u001b[39;49;00m\n",
"\n"
]
}
],
"source": [
"best_tree, fitness = html_repairer.repair(iterations=20)"
]
},
{
"cell_type": "code",
"execution_count": 163,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:38.677952Z",
"iopub.status.busy": "2023-11-12T12:47:38.677849Z",
"iopub.status.idle": "2023-11-12T12:47:38.679620Z",
"shell.execute_reply": "2023-11-12T12:47:38.679322Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"# docassert\n",
"assert fitness < 1.0"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"We see that the \"best\" code is still our original code, with no changes. And we can set `iterations` to 50, 100, 200... – our `Repairer` won't be able to repair it."
]
},
{
"cell_type": "code",
"execution_count": 164,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:47:38.681108Z",
"iopub.status.busy": "2023-11-12T12:47:38.680991Z",
"iopub.status.idle": "2023-11-12T12:47:38.685792Z",
"shell.execute_reply": "2023-11-12T12:47:38.685498Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
" \n",
" \n",
" \n",
"
\n",
" "
],
"text/plain": [
""
]
},
"execution_count": 180,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"quiz(\"Why aren't single quotes handled in the solution?\",\n",
" [\n",
" \"Because they're not important. \"\n",
" \"I mean, y'know, who uses 'em anyway?\",\n",
" \"Because they are not part of our tests? \"\n",
" \"Let me look up how they are constructed...\"\n",
" ], 1 << 1)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Correct! Our test cases do not include single quotes – at least not in the interior of HTML tags – and thus, automatic repair did not care to preserve their handling."
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"How can we fix this? An easy way is to include an appropriate test case in our set – a test case that passes with the original `remove_html_markup()`, yet fails with the \"repaired\" `remove_html_markup()` as shown above."
]
},
{
"cell_type": "code",
"execution_count": 181,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:30.808282Z",
"iopub.status.busy": "2023-11-12T12:48:30.808176Z",
"iopub.status.idle": "2023-11-12T12:48:30.810013Z",
"shell.execute_reply": "2023-11-12T12:48:30.809756Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"with html_debugger:\n",
" remove_html_markup_test(\"me\", \"me\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Let us repeat the repair with the extended test set:"
]
},
{
"cell_type": "code",
"execution_count": 182,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:30.811595Z",
"iopub.status.busy": "2023-11-12T12:48:30.811493Z",
"iopub.status.idle": "2023-11-12T12:48:31.922673Z",
"shell.execute_reply": "2023-11-12T12:48:31.922379Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Evolving population: iteration 2/200 fitness = 1.0 \r\n",
"\n",
"New best code (fitness = 1.0):\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mremove_html_markup\u001b[39;49;00m(s):\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" quote = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" out = \u001b[33m'\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mfor\u001b[39;49;00m c \u001b[35min\u001b[39;49;00m s:\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mif\u001b[39;49;00m c == \u001b[33m'\u001b[39;49;00m\u001b[33m<\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m \u001b[35mand\u001b[39;49;00m (\u001b[35mnot\u001b[39;49;00m quote):\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mTrue\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m c == \u001b[33m'\u001b[39;49;00m\u001b[33m>\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m \u001b[35mand\u001b[39;49;00m (\u001b[35mnot\u001b[39;49;00m quote):\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m tag \u001b[35mand\u001b[39;49;00m (c == \u001b[33m'\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m \u001b[35mor\u001b[39;49;00m (c == \u001b[33m\"\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m \u001b[35mand\u001b[39;49;00m tag)):\u001b[37m\u001b[39;49;00m\n",
" quote = \u001b[35mnot\u001b[39;49;00m quote\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m \u001b[35mnot\u001b[39;49;00m tag:\u001b[37m\u001b[39;49;00m\n",
" out = out + c\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mif\u001b[39;49;00m \u001b[35mnot\u001b[39;49;00m tag:\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mreturn\u001b[39;49;00m out\u001b[37m\u001b[39;49;00m\n",
"\n",
"\n",
"Reduced code (fitness = 1.0):\n",
"\u001b[34mdef\u001b[39;49;00m \u001b[32mremove_html_markup\u001b[39;49;00m(s):\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" quote = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" out = \u001b[33m'\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mfor\u001b[39;49;00m c \u001b[35min\u001b[39;49;00m s:\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mif\u001b[39;49;00m c == \u001b[33m'\u001b[39;49;00m\u001b[33m<\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m \u001b[35mand\u001b[39;49;00m (\u001b[35mnot\u001b[39;49;00m quote):\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mTrue\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m c == \u001b[33m'\u001b[39;49;00m\u001b[33m>\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m \u001b[35mand\u001b[39;49;00m (\u001b[35mnot\u001b[39;49;00m quote):\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m tag \u001b[35mand\u001b[39;49;00m (c == \u001b[33m'\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m \u001b[35mor\u001b[39;49;00m (c == \u001b[33m\"\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m \u001b[35mand\u001b[39;49;00m tag)):\u001b[37m\u001b[39;49;00m\n",
" quote = \u001b[35mnot\u001b[39;49;00m quote\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m \u001b[35mnot\u001b[39;49;00m tag:\u001b[37m\u001b[39;49;00m\n",
" out = out + c\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mif\u001b[39;49;00m \u001b[35mnot\u001b[39;49;00m tag:\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mreturn\u001b[39;49;00m out\u001b[37m\u001b[39;49;00m\n",
"\n"
]
}
],
"source": [
"best_tree, fitness = condition_repairer.repair(iterations=200)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Here is the final tree:"
]
},
{
"cell_type": "code",
"execution_count": 183,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:31.924431Z",
"iopub.status.busy": "2023-11-12T12:48:31.924316Z",
"iopub.status.idle": "2023-11-12T12:48:31.955725Z",
"shell.execute_reply": "2023-11-12T12:48:31.955458Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\u001b[34mdef\u001b[39;49;00m \u001b[32mremove_html_markup\u001b[39;49;00m(s):\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" quote = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" out = \u001b[33m'\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mfor\u001b[39;49;00m c \u001b[35min\u001b[39;49;00m s:\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mif\u001b[39;49;00m c == \u001b[33m'\u001b[39;49;00m\u001b[33m<\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m \u001b[35mand\u001b[39;49;00m (\u001b[35mnot\u001b[39;49;00m quote):\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mTrue\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m c == \u001b[33m'\u001b[39;49;00m\u001b[33m>\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m \u001b[35mand\u001b[39;49;00m (\u001b[35mnot\u001b[39;49;00m quote):\u001b[37m\u001b[39;49;00m\n",
" tag = \u001b[34mFalse\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m tag \u001b[35mand\u001b[39;49;00m (c == \u001b[33m'\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m \u001b[35mor\u001b[39;49;00m (c == \u001b[33m\"\u001b[39;49;00m\u001b[33m'\u001b[39;49;00m\u001b[33m\"\u001b[39;49;00m \u001b[35mand\u001b[39;49;00m tag)):\u001b[37m\u001b[39;49;00m\n",
" quote = \u001b[35mnot\u001b[39;49;00m quote\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m \u001b[35mnot\u001b[39;49;00m tag:\u001b[37m\u001b[39;49;00m\n",
" out = out + c\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mif\u001b[39;49;00m \u001b[35mnot\u001b[39;49;00m tag:\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mreturn\u001b[39;49;00m out\u001b[37m\u001b[39;49;00m"
]
}
],
"source": [
"print_content(ast.unparse(best_tree), '.py')"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"And here is its fitness:"
]
},
{
"cell_type": "code",
"execution_count": 184,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:31.957497Z",
"iopub.status.busy": "2023-11-12T12:48:31.957367Z",
"iopub.status.idle": "2023-11-12T12:48:31.959396Z",
"shell.execute_reply": "2023-11-12T12:48:31.959112Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"1.0"
]
},
"execution_count": 184,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fitness"
]
},
{
"cell_type": "code",
"execution_count": 185,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:31.960834Z",
"iopub.status.busy": "2023-11-12T12:48:31.960728Z",
"iopub.status.idle": "2023-11-12T12:48:31.962259Z",
"shell.execute_reply": "2023-11-12T12:48:31.962019Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"# docassert\n",
"assert fitness >= 1.0"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The revised candidate now passes _all_ tests (including the tricky quote test we added last). Its condition now properly checks for `tag` _and_ both quotes. (The `tag` inside the parentheses is still redundant, but so be it.) From this example, we can learn a few lessons about the possibilities and risks of automated repair:\n",
"\n",
"* First, automatic repair is highly dependent on the quality of the checking tests. The risk is that the repair may overspecialize towards the test.\n",
"* Second, when based on \"plastic surgery\", automated repair is highly dependent on the sources that program fragments are chosen from. If there is a hint of a solution somewhere in the code, there is a chance that automated repair will catch it up.\n",
"* Third, automatic repair is a deeply heuristic approach. Its behavior will vary widely with any change to the parameters (and the underlying random number generators).\n",
"* Fourth, automatic repair can take a long time. The examples we have in this chapter take less than a minute to compute, and neither Python nor our implementation is exactly fast. But as the search space grows, automated repair will take much longer.\n",
"\n",
"On the other hand, even an incomplete automated repair candidate can be much better than nothing at all – it may provide all the essential ingredients (such as the location or the involved variables) for a successful fix. When users of automated repair techniques are aware of its limitations and its assumptions, there is lots of potential in automated repair. Enjoy!"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Limitations"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The `Repairer` class is tested on our example programs, but not much more. Things that do not work include\n",
"\n",
"* Functions with inner functions are not repaired."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Synopsis"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"This chapter provides tools and techniques for automated repair of program code. The `Repairer` class takes a `RankingDebugger` debugger as input (such as `OchiaiDebugger` from the [chapter on statistical debugging](StatisticalDebugger.ipynb). A typical setup looks like this:\n",
"\n",
"```python\n",
"from debuggingbook.StatisticalDebugger import OchiaiDebugger\n",
"\n",
"debugger = OchiaiDebugger()\n",
"for inputs in TESTCASES:\n",
" with debugger:\n",
" test_foo(inputs)\n",
"...\n",
"\n",
"repairer = Repairer(debugger)\n",
"```\n",
"Here, `test_foo()` is a function that raises an exception if the tested function `foo()` fails. If `foo()` passes, `test_foo()` should not raise an exception."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The `repair()` method of a `Repairer` searches for a repair of the code covered in the debugger (except for methods whose name starts or ends in `test`, such that `foo()`, not `test_foo()` is repaired). `repair()` returns the best fix candidate as a pair `(tree, fitness)` where `tree` is a [Python abstract syntax tree](http://docs.python.org/3/library/ast) (AST) of the fix candidate, and `fitness` is the fitness of the candidate (a value between 0 and 1). A `fitness` of 1.0 means that the candidate passed all tests. A typical usage looks like this:\n",
"\n",
"```python\n",
"tree, fitness = repairer.repair()\n",
"print(ast.unparse(tree), fitness)\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Here is a complete example for the `middle()` program. This is the original source code of `middle()`:"
]
},
{
"cell_type": "code",
"execution_count": 186,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:31.963847Z",
"iopub.status.busy": "2023-11-12T12:48:31.963746Z",
"iopub.status.idle": "2023-11-12T12:48:31.993778Z",
"shell.execute_reply": "2023-11-12T12:48:31.993498Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\u001b[34mdef\u001b[39;49;00m \u001b[32mmiddle\u001b[39;49;00m(x, y, z): \u001b[37m# type: ignore\u001b[39;49;00m\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mif\u001b[39;49;00m y < z:\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mif\u001b[39;49;00m x < y:\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mreturn\u001b[39;49;00m y\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m x < z:\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mreturn\u001b[39;49;00m y\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melse\u001b[39;49;00m:\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mif\u001b[39;49;00m x > y:\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mreturn\u001b[39;49;00m y\u001b[37m\u001b[39;49;00m\n",
" \u001b[34melif\u001b[39;49;00m x > z:\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mreturn\u001b[39;49;00m x\u001b[37m\u001b[39;49;00m\n",
" \u001b[34mreturn\u001b[39;49;00m z\u001b[37m\u001b[39;49;00m"
]
}
],
"source": [
"# ignore\n",
"print_content(middle_source, '.py')"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"We set up a function `middle_test()` that tests it. The `middle_debugger` collects testcases and outcomes:"
]
},
{
"cell_type": "code",
"execution_count": 187,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:31.995304Z",
"iopub.status.busy": "2023-11-12T12:48:31.995218Z",
"iopub.status.idle": "2023-11-12T12:48:31.996889Z",
"shell.execute_reply": "2023-11-12T12:48:31.996646Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"middle_debugger = OchiaiDebugger()"
]
},
{
"cell_type": "code",
"execution_count": 188,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:31.998361Z",
"iopub.status.busy": "2023-11-12T12:48:31.998270Z",
"iopub.status.idle": "2023-11-12T12:48:32.004804Z",
"shell.execute_reply": "2023-11-12T12:48:32.004551Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"for x, y, z in MIDDLE_PASSING_TESTCASES + MIDDLE_FAILING_TESTCASES:\n",
" with middle_debugger:\n",
" middle_test(x, y, z)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The repairer is instantiated with the debugger used (`middle_debugger`):"
]
},
{
"cell_type": "code",
"execution_count": 189,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:32.006366Z",
"iopub.status.busy": "2023-11-12T12:48:32.006271Z",
"iopub.status.idle": "2023-11-12T12:48:32.009105Z",
"shell.execute_reply": "2023-11-12T12:48:32.008833Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"middle_repairer = Repairer(middle_debugger)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The `repair()` method of the repairer attempts to repair the function invoked by the test (`middle()`)."
]
},
{
"cell_type": "code",
"execution_count": 190,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:32.010664Z",
"iopub.status.busy": "2023-11-12T12:48:32.010575Z",
"iopub.status.idle": "2023-11-12T12:48:32.470744Z",
"shell.execute_reply": "2023-11-12T12:48:32.470442Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"tree, fitness = middle_repairer.repair()"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The returned AST `tree` can be output via `ast.unparse()`:"
]
},
{
"cell_type": "code",
"execution_count": 191,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:32.472568Z",
"iopub.status.busy": "2023-11-12T12:48:32.472467Z",
"iopub.status.idle": "2023-11-12T12:48:32.474371Z",
"shell.execute_reply": "2023-11-12T12:48:32.474082Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"def middle(x, y, z):\n",
" if y < z:\n",
" if x < y:\n",
" return y\n",
" elif x < z:\n",
" return x\n",
" elif x > y:\n",
" return y\n",
" elif x > z:\n",
" return x\n",
" return z\n"
]
}
],
"source": [
"print(ast.unparse(tree))"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The `fitness` value shows how well the repaired program fits the tests. A fitness value of 1.0 shows that the repaired program satisfies all tests."
]
},
{
"cell_type": "code",
"execution_count": 192,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:32.475915Z",
"iopub.status.busy": "2023-11-12T12:48:32.475807Z",
"iopub.status.idle": "2023-11-12T12:48:32.477985Z",
"shell.execute_reply": "2023-11-12T12:48:32.477735Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"1.0"
]
},
"execution_count": 192,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fitness"
]
},
{
"cell_type": "code",
"execution_count": 193,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:32.479518Z",
"iopub.status.busy": "2023-11-12T12:48:32.479416Z",
"iopub.status.idle": "2023-11-12T12:48:32.480944Z",
"shell.execute_reply": "2023-11-12T12:48:32.480708Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"# docassert\n",
"assert fitness >= 1.0"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Hence, the above program indeed is a perfect repair in the sense that all previously failing tests now pass – our repair was successful."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Here are the classes defined in this chapter. A `Repairer` repairs a program, using a `StatementMutator` and a `CrossoverOperator` to evolve a population of candidates."
]
},
{
"cell_type": "code",
"execution_count": 194,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:32.482502Z",
"iopub.status.busy": "2023-11-12T12:48:32.482415Z",
"iopub.status.idle": "2023-11-12T12:48:32.483941Z",
"shell.execute_reply": "2023-11-12T12:48:32.483690Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"# ignore\n",
"from ClassDiagram import display_class_hierarchy"
]
},
{
"cell_type": "code",
"execution_count": 195,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:32.485336Z",
"iopub.status.busy": "2023-11-12T12:48:32.485254Z",
"iopub.status.idle": "2023-11-12T12:48:33.024491Z",
"shell.execute_reply": "2023-11-12T12:48:33.024072Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 195,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# ignore\n",
"display_class_hierarchy([Repairer, ConditionMutator, CrossoverOperator],\n",
" abstract_classes=[\n",
" NodeVisitor,\n",
" NodeTransformer\n",
" ],\n",
" public_methods=[\n",
" Repairer.__init__,\n",
" Repairer.repair,\n",
" StatementMutator.__init__,\n",
" StatementMutator.mutate,\n",
" ConditionMutator.__init__,\n",
" CrossoverOperator.__init__,\n",
" CrossoverOperator.crossover,\n",
" ],\n",
" project='debuggingbook')"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": true,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Lessons Learned\n",
"\n",
"* Automated repair based on genetic optimization uses five ingredients:\n",
" 1. A _test suite_ to determine passing and failing tests\n",
" 2. _Defect localization_ (typically obtained from [statistical debugging](StatisticalDebugger.ipynb) with the test suite) to determine potential locations to be fixed\n",
" 3. _Random code mutations_ and _crossover operations_ to create and evolve a population of inputs\n",
" 4. A _fitness function_ and a _selection strategy_ to determine the part of the population that should be evolved further\n",
" 5. A _reducer_ such as [delta debugging](DeltaDebugger.ipynb) to simplify the final candidate with the highest fitness.\n",
"* The result of automated repair is a _fix candidate_ with the highest fitness for the given tests.\n",
"* A _fix candidate_ is not guaranteed to be correct or optimal, but gives important hints on how to fix the program.\n",
"* All the above ingredients offer plenty of settings and alternatives to experiment with."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Background\n",
"\n",
"The seminal work in automated repair is [GenProg](https://squareslab.github.io/genprog-code/) \\cite{LeGoues2012}, which heavily inspired our `Repairer` implementation. Major differences between GenProg and `Repairer` include:\n",
"\n",
"* GenProg includes its own defect localization (which is also dynamically updated), whereas `Repairer` builds on earlier statistical debugging.\n",
"* GenProg can apply multiple mutations on programs (or none at all), whereas `Repairer` applies exactly one mutation.\n",
"* The `StatementMutator` used by `Repairer` includes various special cases for program structures (`if`, `for`, `while`...), whereas GenProg operates on statements only.\n",
"* GenProg has been tested on large production programs.\n",
"\n",
"While GenProg is _the_ seminal work in the area (and arguably the most important software engineering research contribution of the 2010s), there have been a number of important extensions of automated repair. These include:\n",
"\n",
"* *AutoFix* \\cite{Pei2014} leverages _program contracts_ (pre- and postconditions) to generate tests and assertions automatically. Not only do such [assertions](Assertions.ipynb) help in fault localization, they also allow for much better validation of fix candidates.\n",
"* *SemFix* \\cite{Nguyen2013} and its successor *[Angelix](http://angelix.io)* \\cite{Mechtaev2016}\n",
"introduce automated program repair based on _symbolic analysis_ rather than genetic optimization. This allows leveraging program semantics, which GenProg does not consider.\n",
"\n",
"To learn more about automated program repair, see [program-repair.org](http://program-repair.org), the community page dedicated to research in program repair."
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": true,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Exercises"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Exercise 1: Automated Repair Parameters\n",
"\n",
"Automated Repair is influenced by numerous design choices – the size of the population, the number of iterations, the genetic optimization strategy, and more. How do changes to these design choices affect its effectiveness? \n",
"\n",
"* Consider the constants defined in this chapter (such as `POPULATION_SIZE` or `WEIGHT_PASSING` vs. `WEIGHT_FAILING`). How do changes affect the effectiveness of automated repair?\n",
"* As an effectiveness metric, consider the number of iterations it takes to produce a fix candidate.\n",
"* Since genetic optimization is a random algorithm, you need to determine effectiveness averages over a large number of runs (say, 100)."
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
},
"solution": "hidden",
"solution2": "hidden",
"solution2_first": true,
"solution_first": true
},
"source": [
"### Exercise 2: Elitism\n",
"\n",
"[_Elitism_](https://en.wikipedia.org/wiki/Genetic_algorithm#Elitism) (also known as _elitist selection_) is a variant of genetic selection in which a small fraction of the fittest candidates of the last population are included unchanged in the offspring.\n",
"\n",
"* Implement elitist selection by subclassing the `evolve()` method. Experiment with various fractions (5%, 10%, 25%) of \"elites\" and see how this improves results."
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
},
"solution": "hidden",
"solution2": "hidden",
"solution2_first": true,
"solution_first": true
},
"source": [
"### Exercise 3: Evolving Values\n",
"\n",
"Following the steps of `ConditionMutator`, implement a `ValueMutator` class that replaces one constant value by another one found in the source (say, `0` by `1` or `True` by `False`).\n",
"\n",
"For validation, consider the following failure in the `square_root()` function from the [chapter on assertions](Assertions.ipynb):"
]
},
{
"cell_type": "code",
"execution_count": 196,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:33.026743Z",
"iopub.status.busy": "2023-11-12T12:48:33.026597Z",
"iopub.status.idle": "2023-11-12T12:48:33.028564Z",
"shell.execute_reply": "2023-11-12T12:48:33.028265Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from Assertions import square_root # minor dependency"
]
},
{
"cell_type": "code",
"execution_count": 197,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:33.030122Z",
"iopub.status.busy": "2023-11-12T12:48:33.029995Z",
"iopub.status.idle": "2023-11-12T12:48:33.031897Z",
"shell.execute_reply": "2023-11-12T12:48:33.031633Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"Traceback (most recent call last):\n",
" File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_33724/1107282428.py\", line 2, in \n",
" square_root_of_zero = square_root(0)\n",
" File \"/Users/zeller/Projects/debuggingbook/notebooks/Assertions.ipynb\", line 61, in square_root\n",
" guess = (approx + x / approx) / 2\n",
"ZeroDivisionError: float division by zero (expected)\n"
]
}
],
"source": [
"with ExpectError():\n",
" square_root_of_zero = square_root(0)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
},
"solution2": "hidden",
"solution2_first": true
},
"source": [
"Can your `ValueMutator` automatically fix this failure?"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
},
"solution2": "hidden"
},
"source": [
"**Solution.** Your solution will be effective if it also includes named constants such as `None`."
]
},
{
"cell_type": "code",
"execution_count": 198,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:33.033496Z",
"iopub.status.busy": "2023-11-12T12:48:33.033360Z",
"iopub.status.idle": "2023-11-12T12:48:33.034918Z",
"shell.execute_reply": "2023-11-12T12:48:33.034685Z"
},
"slideshow": {
"slide_type": "skip"
},
"solution2": "hidden"
},
"outputs": [],
"source": [
"import math"
]
},
{
"cell_type": "code",
"execution_count": 199,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:33.036333Z",
"iopub.status.busy": "2023-11-12T12:48:33.036249Z",
"iopub.status.idle": "2023-11-12T12:48:33.038457Z",
"shell.execute_reply": "2023-11-12T12:48:33.038151Z"
},
"slideshow": {
"slide_type": "skip"
},
"solution2": "hidden"
},
"outputs": [],
"source": [
"def square_root_fixed(x): # type: ignore\n",
" assert x >= 0 # precondition\n",
"\n",
" approx = 0 # <-- FIX: Change `None` to 0\n",
" guess = x / 2\n",
" while approx != guess:\n",
" approx = guess\n",
" guess = (approx + x / approx) / 2\n",
"\n",
" assert math.isclose(approx * approx, x)\n",
" return approx"
]
},
{
"cell_type": "code",
"execution_count": 200,
"metadata": {
"execution": {
"iopub.execute_input": "2023-11-12T12:48:33.039960Z",
"iopub.status.busy": "2023-11-12T12:48:33.039873Z",
"iopub.status.idle": "2023-11-12T12:48:33.042257Z",
"shell.execute_reply": "2023-11-12T12:48:33.041980Z"
},
"slideshow": {
"slide_type": "skip"
},
"solution2": "hidden"
},
"outputs": [
{
"data": {
"text/plain": [
"0"
]
},
"execution_count": 200,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"square_root_fixed(0)"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
},
"solution": "hidden",
"solution2": "hidden",
"solution2_first": true,
"solution_first": true
},
"source": [
"### Exercise 4: Evolving Variable Names\n",
"\n",
"Following the steps of `ConditionMutator`, implement a `IdentifierMutator` class that replaces one identifier by another one found in the source (say, `y` by `x`). Does it help to fix the `middle()` error?"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
},
"solution": "hidden",
"solution2": "hidden",
"solution2_first": true,
"solution_first": true
},
"source": [
"### Exercise 5: Parallel Repair\n",
"\n",
"Automatic Repair is a technique that is embarrassingly parallel – all tests for one candidate can all be run in parallel, and all tests for _all_ candidates can also be run in parallel. Set up an infrastructure for running concurrent tests using Pythons [asyncio](https://docs.python.org/3/library/asyncio.html) library."
]
}
],
"metadata": {
"ipub": {
"bibliography": "fuzzingbook.bib",
"toc": true
},
"kernelspec": {
"display_name": "Python 3",
"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.10.2"
},
"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,
"vscode": {
"interpreter": {
"hash": "4185989cf89c47c310c2629adcadd634093b57a2c49dffb5ae8d0d14fa302f2b"
}
}
},
"nbformat": 4,
"nbformat_minor": 4
}