1 def remove_html_markup(s): # type: ignore\n", "
2 tag = False\n", "
3 quote = False\n", "
4 out = ""\n", "
5\n", "
6 for c in s:\n", "
7 if c == '<' and not quote:\n", "
8 tag = True\n", "
9 elif c == '>' and not quote:\n", "
10 tag = False\n", "
11 elif c == '"' or c == "'" and tag:\n", "
12 quote = not quote\n", "
13 elif not tag:\n", "
14 out = out + c\n", "
15\n", "
16 return out\n", "\n", "\n", "### Ranking Events\n", "\n", "The method `rank()` returns a ranked list of events, starting with the most suspicious. This is useful for automated techniques that need potential defect locations.\n", "\n", "```python\n", ">>> debugger.rank()\n", "[('remove_html_markup', 12),\n", " ('remove_html_markup', 11),\n", " ('remove_html_markup', 14),\n", " ('remove_html_markup', 3),\n", " ('remove_html_markup', 6),\n", " ('remove_html_markup', 9),\n", " ('remove_html_markup', 1),\n", " ('remove_html_markup', 7),\n", " ('remove_html_markup', 4),\n", " ('remove_html_markup', 13),\n", " ('remove_html_markup', 16),\n", " ('remove_html_markup', 2),\n", " ('remove_html_markup', 10),\n", " ('remove_html_markup', 8)]\n", "```\n", "### Classes and Methods\n", "\n", "Here are all classes defined in this chapter:\n", "\n", "![](PICS/StatisticalDebugger-synopsis-1.svg)\n", "\n", "![](PICS/StatisticalDebugger-synopsis-2.svg)\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Introduction\n", "\n", "The idea behind _statistical debugging_ is fairly simple. We have a program that sometimes passes and sometimes fails. This outcome can be _correlated_ with events that precede it – properties of the input, properties of the execution, properties of the program state. If we, for instance, can find that \"the program always fails when Line 123 is executed, and it always passes when Line 123 is _not_ executed\", then we have a strong correlation between Line 123 being executed and failure.\n", "\n", "Such _correlation_ does not necessarily mean _causation_. For this, we would have to prove that executing Line 123 _always_ leads to failure, and that _not_ executing it does not lead to (this) failure. Also, a correlation (or even a causation) does not mean that Line 123 contains the defect – for this, we would have to show that it actually is an error. Still, correlations make excellent hints as it comes to search for failure causes – in all generality, if you let your search be guided by _events that correlate with failures_, you are more likely to find _important hints on how the failure comes to be_." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": true, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Collecting Events\n", "\n", "How can we determine events that correlate with failure? We start with a general mechanism to actually _collect_ events during execution. The abstract `Collector` class provides\n", "\n", "* a `collect()` method made for collecting events, called from the `traceit()` tracer; and\n", "* an `events()` method made for retrieving these events.\n", "\n", "Both of these are _abstract_ and will be defined further in subclasses." ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.413781Z", "iopub.status.busy": "2023-11-12T12:41:20.413650Z", "iopub.status.idle": "2023-11-12T12:41:20.512433Z", "shell.execute_reply": "2023-11-12T12:41:20.512036Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from Tracer import Tracer" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.514475Z", "iopub.status.busy": "2023-11-12T12:41:20.514325Z", "iopub.status.idle": "2023-11-12T12:41:20.516281Z", "shell.execute_reply": "2023-11-12T12:41:20.516009Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "# ignore\n", "from typing import Any, Callable, Optional, Type, Tuple\n", "from typing import Dict, Set, List, TypeVar, Union" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.517861Z", "iopub.status.busy": "2023-11-12T12:41:20.517741Z", "iopub.status.idle": "2023-11-12T12:41:20.519446Z", "shell.execute_reply": "2023-11-12T12:41:20.519141Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from types import FrameType, TracebackType" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.521301Z", "iopub.status.busy": "2023-11-12T12:41:20.521177Z", "iopub.status.idle": "2023-11-12T12:41:20.523659Z", "shell.execute_reply": "2023-11-12T12:41:20.523390Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class Collector(Tracer):\n", " \"\"\"A class to record events during execution.\"\"\"\n", "\n", " def collect(self, frame: FrameType, event: str, arg: Any) -> None:\n", " \"\"\"Collecting function. To be overridden in subclasses.\"\"\"\n", " pass\n", "\n", " def events(self) -> Set:\n", " \"\"\"Return a collection of events. To be overridden in subclasses.\"\"\"\n", " return set()\n", "\n", " def traceit(self, frame: FrameType, event: str, arg: Any) -> None:\n", " self.collect(frame, event, arg)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "A `Collector` class is used like `Tracer`, using a `with` statement. Let us apply it on the buggy variant of `remove_html_markup()` from the [Introduction to Debugging](Intro_Debugging.ipynb):" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.525239Z", "iopub.status.busy": "2023-11-12T12:41:20.525124Z", "iopub.status.idle": "2023-11-12T12:41:20.527415Z", "shell.execute_reply": "2023-11-12T12:41:20.527061Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def remove_html_markup(s): # type: ignore\n", " tag = False\n", " quote = False\n", " out = \"\"\n", "\n", " for c in s:\n", " if c == '<' and not quote:\n", " tag = True\n", " elif c == '>' and not quote:\n", " tag = False\n", " elif c == '\"' or c == \"'\" and tag:\n", " quote = not quote\n", " elif not tag:\n", " out = out + c\n", "\n", " return out" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.529639Z", "iopub.status.busy": "2023-11-12T12:41:20.529472Z", "iopub.status.idle": "2023-11-12T12:41:20.532120Z", "shell.execute_reply": "2023-11-12T12:41:20.531765Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "'abc'" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "with Collector() as c:\n", " out = remove_html_markup('\"abc\"')\n", "out" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "There's not much we can do with our collector, as the `collect()` and `events()` methods are yet empty. However, we can introduce an `id()` method which returns a string identifying the collector. This string is defined from the _first function call_ encountered." ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.533770Z", "iopub.status.busy": "2023-11-12T12:41:20.533657Z", "iopub.status.idle": "2023-11-12T12:41:20.535373Z", "shell.execute_reply": "2023-11-12T12:41:20.535107Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "Coverage = Set[Tuple[Callable, int]]" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.537492Z", "iopub.status.busy": "2023-11-12T12:41:20.537342Z", "iopub.status.idle": "2023-11-12T12:41:20.543360Z", "shell.execute_reply": "2023-11-12T12:41:20.543002Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class Collector(Collector):\n", " def __init__(self) -> None:\n", " \"\"\"Constructor.\"\"\"\n", " self._function: Optional[Callable] = None\n", " self._args: Optional[Dict[str, Any]] = None\n", " self._argstring: Optional[str] = None\n", " self._exception: Optional[Type] = None\n", " self.items_to_ignore: List[Union[Type, Callable]] = [self.__class__]\n", "\n", " def traceit(self, frame: FrameType, event: str, arg: Any) -> None:\n", " \"\"\"\n", " Tracing function.\n", " Saves the first function and calls collect().\n", " \"\"\"\n", " for item in self.items_to_ignore:\n", " if (isinstance(item, type) and 'self' in frame.f_locals and\n", " isinstance(frame.f_locals['self'], item)):\n", " # Ignore this class\n", " return\n", " if item.__name__ == frame.f_code.co_name:\n", " # Ignore this function\n", " return\n", "\n", " if self._function is None and event == 'call':\n", " # Save function\n", " self._function = self.create_function(frame)\n", " self._args = frame.f_locals.copy()\n", " self._argstring = \", \".join([f\"{var}={repr(self._args[var])}\" \n", " for var in self._args])\n", "\n", " self.collect(frame, event, arg)\n", "\n", " def collect(self, frame: FrameType, event: str, arg: Any) -> None:\n", " \"\"\"Collector function. To be overloaded in subclasses.\"\"\"\n", " pass\n", "\n", " def id(self) -> str:\n", " \"\"\"Return an identifier for the collector, \n", " created from the first call\"\"\"\n", " return f\"{self.function().__name__}({self.argstring()})\"\n", "\n", " def function(self) -> Callable:\n", " \"\"\"Return the function from the first call, as a function object\"\"\"\n", " if not self._function:\n", " raise ValueError(\"No call collected\")\n", " return self._function\n", "\n", " def argstring(self) -> str:\n", " \"\"\"\n", " Return the list of arguments from the first call,\n", " as a printable string\n", " \"\"\"\n", " if not self._argstring:\n", " raise ValueError(\"No call collected\")\n", " return self._argstring\n", "\n", " def args(self) -> Dict[str, Any]:\n", " \"\"\"Return a dict of argument names and values from the first call\"\"\"\n", " if not self._args:\n", " raise ValueError(\"No call collected\")\n", " return self._args\n", "\n", " def exception(self) -> Optional[Type]:\n", " \"\"\"Return the exception class from the first call,\n", " or None if no exception was raised.\"\"\"\n", " return self._exception\n", "\n", " def __repr__(self) -> str:\n", " \"\"\"Return a string representation of the collector\"\"\"\n", " # We use the ID as default representation when printed\n", " return self.id()\n", "\n", " def covered_functions(self) -> Set[Callable]:\n", " \"\"\"Set of covered functions. To be overloaded in subclasses.\"\"\"\n", " return set()\n", "\n", " def coverage(self) -> Coverage:\n", " \"\"\"\n", " Return a set (function, lineno) with locations covered.\n", " To be overloaded in subclasses.\n", " \"\"\"\n", " return set()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Here's how the collector works. We use a `with` clause to collect details on a function call:" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.545309Z", "iopub.status.busy": "2023-11-12T12:41:20.545143Z", "iopub.status.idle": "2023-11-12T12:41:20.547151Z", "shell.execute_reply": "2023-11-12T12:41:20.546874Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "with Collector() as c:\n", " remove_html_markup('abc')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "We can now retrieve details such as the function called..." ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.548773Z", "iopub.status.busy": "2023-11-12T12:41:20.548653Z", "iopub.status.idle": "2023-11-12T12:41:20.550818Z", "shell.execute_reply": "2023-11-12T12:41:20.550559Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "
\n", "
\"<b>Don't do this!</b>\"
. Which of these lines are executed? Use the code to find out!\n", "
\n", " \n", " \n", " \n", "\n", "
\n", "
\n", " \n", " \n", " \n", "{line.rstrip()}'''\n", " elif color:\n", " line = f'
{line}'\n", " else:\n", " line = line.rstrip()\n", "\n", " out += line + '\\n'\n", " line_number += 1\n", "\n", " return out" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "We introduce a few helper methods to visualize the code with colors in various forms." ] }, { "cell_type": "code", "execution_count": 67, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.865013Z", "iopub.status.busy": "2023-11-12T12:41:20.864926Z", "iopub.status.idle": "2023-11-12T12:41:20.867145Z", "shell.execute_reply": "2023-11-12T12:41:20.866856Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class SpectrumDebugger(SpectrumDebugger):\n", " def _repr_html_(self) -> str:\n", " \"\"\"When output in Jupyter, visualize as HTML\"\"\"\n", " return self.code(color=True)\n", "\n", " def __str__(self) -> str:\n", " \"\"\"Show code as string\"\"\"\n", " return self.code(color=False, suspiciousness=True)\n", "\n", " def __repr__(self) -> str:\n", " \"\"\"Show code as string\"\"\"\n", " return self.code(color=False, suspiciousness=True)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "So far, however, central methods like `suspiciousness()` or `color()` were abstract – that is, to be defined in subclasses. Our `DiscreteSpectrumDebugger` subclass provides concrete implementations for these, with `color()` returning one of the three colors depending on the line number:" ] }, { "cell_type": "code", "execution_count": 68, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.868567Z", "iopub.status.busy": "2023-11-12T12:41:20.868486Z", "iopub.status.idle": "2023-11-12T12:41:20.871890Z", "shell.execute_reply": "2023-11-12T12:41:20.871600Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class DiscreteSpectrumDebugger(SpectrumDebugger):\n", " \"\"\"Visualize differences between executions using three discrete colors\"\"\"\n", "\n", " def suspiciousness(self, event: Any) -> Optional[float]:\n", " \"\"\"\n", " Return a suspiciousness value [0, 1.0]\n", " for the given event, or `None` if unknown.\n", " \"\"\"\n", " passing = self.all_pass_events()\n", " failing = self.all_fail_events()\n", "\n", " if event in passing and event in failing:\n", " return 0.5\n", " elif event in failing:\n", " return 1.0\n", " elif event in passing:\n", " return 0.0\n", " else:\n", " return None\n", "\n", " def color(self, event: Any) -> Optional[str]:\n", " \"\"\"\n", " Return a HTML color for the given event.\n", " \"\"\"\n", " suspiciousness = self.suspiciousness(event)\n", " if suspiciousness is None:\n", " return None\n", "\n", " if suspiciousness > 0.8:\n", " return 'mistyrose'\n", " if suspiciousness >= 0.5:\n", " return 'lightyellow'\n", "\n", " return 'honeydew'\n", "\n", " def tooltip(self, event: Any) -> str:\n", " \"\"\"Return a tooltip for the given event.\"\"\"\n", " passing = self.all_pass_events()\n", " failing = self.all_fail_events()\n", "\n", " if event in passing and event in failing:\n", " return \"in passing and failing runs\"\n", " elif event in failing:\n", " return \"only in failing runs\"\n", " elif event in passing:\n", " return \"only in passing runs\"\n", " else:\n", " return \"never\"" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "This is how the `only_pass_events()` and `only_fail_events()` sets look like when visualized with code. The \"culprit\" line is well highlighted:" ] }, { "cell_type": "code", "execution_count": 69, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.873317Z", "iopub.status.busy": "2023-11-12T12:41:20.873225Z", "iopub.status.idle": "2023-11-12T12:41:20.875169Z", "shell.execute_reply": "2023-11-12T12:41:20.874927Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "debugger = test_debugger_html(DiscreteSpectrumDebugger())" ] }, { "cell_type": "code", "execution_count": 70, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.876637Z", "iopub.status.busy": "2023-11-12T12:41:20.876542Z", "iopub.status.idle": "2023-11-12T12:41:20.880477Z", "shell.execute_reply": "2023-11-12T12:41:20.880187Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/html": [ "
1 def remove_html_markup(s): # type: ignore\n", "
2 tag = False\n", "
3 quote = False\n", "
4 out = ""\n", "
5\n", "
6 for c in s:\n", "
7 if c == '<' and not quote:\n", "
8 tag = True\n", "
9 elif c == '>' and not quote:\n", "
10 tag = False\n", "
11 elif c == '"' or c == "'" and tag:\n", "
12 quote = not quote\n", "
13 elif not tag:\n", "
14 out = out + c\n", "
15\n", "
16 return out\n" ], "text/markdown": [ "| `remove_html_markup` | `s='abc'` | `s='abc'` | `s='\"abc\"'` | \n", "| --------------------- | ---- | ---- | ---- | \n", "| remove_html_markup:1 | X | X | X | \n", "| remove_html_markup:2 | X | X | X | \n", "| remove_html_markup:3 | X | X | X | \n", "| remove_html_markup:4 | X | X | X | \n", "| remove_html_markup:6 | X | X | X | \n", "| remove_html_markup:7 | X | X | X | \n", "| remove_html_markup:8 | - | X | - | \n", "| remove_html_markup:9 | X | X | X | \n", "| remove_html_markup:10 | - | X | - | \n", "| remove_html_markup:11 | X | X | X | \n", "| remove_html_markup:12 | - | - | X | \n", "| remove_html_markup:13 | X | X | X | \n", "| remove_html_markup:14 | X | X | X | \n", "| remove_html_markup:16 | X | X | X | \n" ], "text/plain": [ " 1 50% def remove_html_markup(s): # type: ignore\n", " 2 50% tag = False\n", " 3 50% quote = False\n", " 4 50% out = \"\"\n", " 5\n", " 6 50% for c in s:\n", " 7 50% if c == '<' and not quote:\n", " 8 0% tag = True\n", " 9 50% elif c == '>' and not quote:\n", " 10 0% tag = False\n", " 11 50% elif c == '\"' or c == \"'\" and tag:\n", " 12 100% quote = not quote\n", " 13 50% elif not tag:\n", " 14 50% out = out + c\n", " 15\n", " 16 50% return out" ] }, "execution_count": 70, "metadata": {}, "output_type": "execute_result" } ], "source": [ "debugger" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "We can clearly see that the failure is correlated with the presence of quotes in the input string (which is an important hint!). But does this also show us _immediately_ where the defect to be fixed is?" ] }, { "cell_type": "code", "execution_count": 71, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.882024Z", "iopub.status.busy": "2023-11-12T12:41:20.881898Z", "iopub.status.idle": "2023-11-12T12:41:20.886005Z", "shell.execute_reply": "2023-11-12T12:41:20.885744Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", "
\n", "
quote = not quote
actually contain the defect?\n", "
\n", " \n", " \n", " \n", "1 def remove_html_markup(s): # type: ignore\n", "
2 tag = False\n", "
3 quote = False\n", "
4 out = ""\n", "
5\n", "
6 for c in s:\n", "
7 if c == '<' and not quote:\n", "
8 tag = True\n", "
9 elif c == '>' and not quote:\n", "
10 tag = False\n", "
11 elif c == '"' or c == "'" and tag:\n", "
12 quote = not quote\n", "
13 elif not tag:\n", "
14 out = out + c\n", "
15\n", "
16 return out\n" ], "text/markdown": [ "| `remove_html_markup` | `s='abc'` | `s='abc'` | `s=''` | `s='\"abc\"'` | \n", "| --------------------- | ---- | ---- | ---- | ---- | \n", "| remove_html_markup:1 | X | X | X | X | \n", "| remove_html_markup:2 | X | X | X | X | \n", "| remove_html_markup:3 | X | X | X | X | \n", "| remove_html_markup:4 | X | X | X | X | \n", "| remove_html_markup:6 | X | X | X | X | \n", "| remove_html_markup:7 | X | X | X | X | \n", "| remove_html_markup:8 | - | X | X | - | \n", "| remove_html_markup:9 | X | X | X | X | \n", "| remove_html_markup:10 | - | X | X | - | \n", "| remove_html_markup:11 | X | X | X | X | \n", "| remove_html_markup:12 | - | - | X | X | \n", "| remove_html_markup:13 | X | X | X | X | \n", "| remove_html_markup:14 | X | X | - | X | \n", "| remove_html_markup:16 | X | X | X | X | \n" ], "text/plain": [ " 1 50% def remove_html_markup(s): # type: ignore\n", " 2 50% tag = False\n", " 3 50% quote = False\n", " 4 50% out = \"\"\n", " 5\n", " 6 50% for c in s:\n", " 7 50% if c == '<' and not quote:\n", " 8 0% tag = True\n", " 9 50% elif c == '>' and not quote:\n", " 10 0% tag = False\n", " 11 50% elif c == '\"' or c == \"'\" and tag:\n", " 12 50% quote = not quote\n", " 13 50% elif not tag:\n", " 14 50% out = out + c\n", " 15\n", " 16 50% return out" ] }, "execution_count": 76, "metadata": {}, "output_type": "execute_result" } ], "source": [ "debugger" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "We therefore introduce a different method for highlighting lines, based on their _relative_ occurrence with respect to all runs: If a line has been _mostly_ executed in failing runs, its color should shift towards red; if a line has been _mostly_ executed in passing runs, its color should shift towards green." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "This _continuous spectrum_ has been introduced by the seminal _Tarantula_ tool \\cite{Jones2002}. In Tarantula, the color _hue_ for each line is defined as follows:" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "$$\n", "\\textit{color hue}(\\textit{line}) = \\textit{low color(red)} + \\frac{\\%\\textit{passed}(\\textit{line})}{\\%\\textit{passed}(\\textit{line}) + \\%\\textit{failed}(\\textit{line})} \\times \\textit{color range}\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Here, `%passed` and `%failed` denote the percentage at which a line has been executed in passing and failing runs, respectively. A hue of 0.0 stands for red, a hue of 1.0 stands for green, and a hue of 0.5 stands for equal fractions of red and green, yielding yellow." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "We can implement these measures right away as methods in a new `ContinuousSpectrumDebugger` class:" ] }, { "cell_type": "code", "execution_count": 77, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.906908Z", "iopub.status.busy": "2023-11-12T12:41:20.906828Z", "iopub.status.idle": "2023-11-12T12:41:20.910609Z", "shell.execute_reply": "2023-11-12T12:41:20.910356Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class ContinuousSpectrumDebugger(DiscreteSpectrumDebugger):\n", " \"\"\"Visualize differences between executions using a color spectrum\"\"\"\n", "\n", " def collectors_with_event(self, event: Any, category: str) -> Set[Collector]:\n", " \"\"\"\n", " Return all collectors in a category\n", " that observed the given event.\n", " \"\"\"\n", " all_runs = self.collectors[category]\n", " collectors_with_event = set(collector for collector in all_runs \n", " if event in collector.events())\n", " return collectors_with_event\n", "\n", " def collectors_without_event(self, event: Any, category: str) -> Set[Collector]:\n", " \"\"\"\n", " Return all collectors in a category\n", " that did not observe the given event.\n", " \"\"\"\n", " all_runs = self.collectors[category]\n", " collectors_without_event = set(collector for collector in all_runs \n", " if event not in collector.events())\n", " return collectors_without_event\n", "\n", " def event_fraction(self, event: Any, category: str) -> float:\n", " if category not in self.collectors:\n", " return 0.0\n", "\n", " all_collectors = self.collectors[category]\n", " collectors_with_event = self.collectors_with_event(event, category)\n", " fraction = len(collectors_with_event) / len(all_collectors)\n", " # print(f\"%{category}({event}) = {fraction}\")\n", " return fraction\n", "\n", " def passed_fraction(self, event: Any) -> float:\n", " return self.event_fraction(event, self.PASS)\n", "\n", " def failed_fraction(self, event: Any) -> float:\n", " return self.event_fraction(event, self.FAIL)\n", "\n", " def hue(self, event: Any) -> Optional[float]:\n", " \"\"\"Return a color hue from 0.0 (red) to 1.0 (green).\"\"\"\n", " passed = self.passed_fraction(event)\n", " failed = self.failed_fraction(event)\n", " if passed + failed > 0:\n", " return passed / (passed + failed)\n", " else:\n", " return None" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Having a continuous hue also implies a continuous suspiciousness and associated tooltips:" ] }, { "cell_type": "code", "execution_count": 78, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.912118Z", "iopub.status.busy": "2023-11-12T12:41:20.912028Z", "iopub.status.idle": "2023-11-12T12:41:20.914334Z", "shell.execute_reply": "2023-11-12T12:41:20.914070Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class ContinuousSpectrumDebugger(ContinuousSpectrumDebugger):\n", " def suspiciousness(self, event: Any) -> Optional[float]:\n", " hue = self.hue(event)\n", " if hue is None:\n", " return None\n", " return 1 - hue\n", "\n", " def tooltip(self, event: Any) -> str:\n", " return self.percentage(event)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The hue for lines executed only in failing runs is (deep) red, as expected:" ] }, { "cell_type": "code", "execution_count": 79, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.915960Z", "iopub.status.busy": "2023-11-12T12:41:20.915854Z", "iopub.status.idle": "2023-11-12T12:41:20.917736Z", "shell.execute_reply": "2023-11-12T12:41:20.917482Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "debugger = test_debugger_html(ContinuousSpectrumDebugger())" ] }, { "cell_type": "code", "execution_count": 80, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.919153Z", "iopub.status.busy": "2023-11-12T12:41:20.919046Z", "iopub.status.idle": "2023-11-12T12:41:20.920789Z", "shell.execute_reply": "2023-11-12T12:41:20.920535Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "('remove_html_markup', 12) 0.0\n" ] } ], "source": [ "for location in debugger.only_fail_events():\n", " print(location, debugger.hue(location))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Likewise, the hue for lines executed in passing runs is (deep) green:" ] }, { "cell_type": "code", "execution_count": 81, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.922216Z", "iopub.status.busy": "2023-11-12T12:41:20.922114Z", "iopub.status.idle": "2023-11-12T12:41:20.923879Z", "shell.execute_reply": "2023-11-12T12:41:20.923645Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "('remove_html_markup', 8) 1.0\n", "('remove_html_markup', 10) 1.0\n" ] } ], "source": [ "for location in debugger.only_pass_events():\n", " print(location, debugger.hue(location))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The Tarantula tool not only sets the hue for a line, but also uses _brightness_ as measure for support – that is, how often was the line executed at all. The brighter a line, the stronger the correlation with a passing or failing outcome." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The brightness is defined as follows:" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "$$\\textit{brightness}(line) = \\max(\\%\\textit{passed}(\\textit{line}), \\%\\textit{failed}(\\textit{line}))$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "and it is easily implemented, too:" ] }, { "cell_type": "code", "execution_count": 82, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.925581Z", "iopub.status.busy": "2023-11-12T12:41:20.925469Z", "iopub.status.idle": "2023-11-12T12:41:20.927482Z", "shell.execute_reply": "2023-11-12T12:41:20.927065Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "class ContinuousSpectrumDebugger(ContinuousSpectrumDebugger):\n", " def brightness(self, event: Any) -> float:\n", " return max(self.passed_fraction(event), self.failed_fraction(event))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Our single \"only in fail\" line has a brightness of 1.0 (the maximum)." ] }, { "cell_type": "code", "execution_count": 83, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.929570Z", "iopub.status.busy": "2023-11-12T12:41:20.929442Z", "iopub.status.idle": "2023-11-12T12:41:20.932136Z", "shell.execute_reply": "2023-11-12T12:41:20.931819Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "('remove_html_markup', 12) 1.0\n" ] } ], "source": [ "debugger = test_debugger_html(ContinuousSpectrumDebugger())\n", "for location in debugger.only_fail_events():\n", " print(location, debugger.brightness(location))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "With this, we can now define a color for each line. To this end, we override the (previously discrete) `color()` method such that it returns a color specification giving hue and brightness. We use the HTML format `hsl(hue, saturation, lightness)` where the hue is given as a value between 0 and 360 (0 is red, 120 is green) and saturation and lightness are provided as percentages." ] }, { "cell_type": "code", "execution_count": 84, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.933932Z", "iopub.status.busy": "2023-11-12T12:41:20.933793Z", "iopub.status.idle": "2023-11-12T12:41:20.936214Z", "shell.execute_reply": "2023-11-12T12:41:20.935897Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class ContinuousSpectrumDebugger(ContinuousSpectrumDebugger):\n", " def color(self, event: Any) -> Optional[str]:\n", " hue = self.hue(event)\n", " if hue is None:\n", " return None\n", " saturation = self.brightness(event)\n", "\n", " # HSL color values are specified with: \n", " # hsl(hue, saturation, lightness).\n", " return f\"hsl({hue * 120}, {saturation * 100}%, 80%)\"" ] }, { "cell_type": "code", "execution_count": 85, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.937703Z", "iopub.status.busy": "2023-11-12T12:41:20.937600Z", "iopub.status.idle": "2023-11-12T12:41:20.939533Z", "shell.execute_reply": "2023-11-12T12:41:20.939274Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "debugger = test_debugger_html(ContinuousSpectrumDebugger())" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Lines executed only in failing runs are still shown in red:" ] }, { "cell_type": "code", "execution_count": 86, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.941071Z", "iopub.status.busy": "2023-11-12T12:41:20.940961Z", "iopub.status.idle": "2023-11-12T12:41:20.942708Z", "shell.execute_reply": "2023-11-12T12:41:20.942443Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "('remove_html_markup', 12) hsl(0.0, 100.0%, 80%)\n" ] } ], "source": [ "for location in debugger.only_fail_events():\n", " print(location, debugger.color(location))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "... whereas lines executed only in passing runs are still shown in green:" ] }, { "cell_type": "code", "execution_count": 87, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.944221Z", "iopub.status.busy": "2023-11-12T12:41:20.944107Z", "iopub.status.idle": "2023-11-12T12:41:20.945916Z", "shell.execute_reply": "2023-11-12T12:41:20.945649Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "('remove_html_markup', 8) hsl(120.0, 50.0%, 80%)\n", "('remove_html_markup', 10) hsl(120.0, 50.0%, 80%)\n" ] } ], "source": [ "for location in debugger.only_pass_events():\n", " print(location, debugger.color(location))" ] }, { "cell_type": "code", "execution_count": 88, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.947542Z", "iopub.status.busy": "2023-11-12T12:41:20.947435Z", "iopub.status.idle": "2023-11-12T12:41:20.951068Z", "shell.execute_reply": "2023-11-12T12:41:20.950797Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/html": [ "
1 def remove_html_markup(s): # type: ignore\n", "
2 tag = False\n", "
3 quote = False\n", "
4 out = ""\n", "
5\n", "
6 for c in s:\n", "
7 if c == '<' and not quote:\n", "
8 tag = True\n", "
9 elif c == '>' and not quote:\n", "
10 tag = False\n", "
11 elif c == '"' or c == "'" and tag:\n", "
12 quote = not quote\n", "
13 elif not tag:\n", "
14 out = out + c\n", "
15\n", "
16 return out\n" ], "text/markdown": [ "| `remove_html_markup` | `s='abc'` | `s='abc'` | `s='\"abc\"'` | \n", "| --------------------- | ---- | ---- | ---- | \n", "| remove_html_markup:1 | X | X | X | \n", "| remove_html_markup:2 | X | X | X | \n", "| remove_html_markup:3 | X | X | X | \n", "| remove_html_markup:4 | X | X | X | \n", "| remove_html_markup:6 | X | X | X | \n", "| remove_html_markup:7 | X | X | X | \n", "| remove_html_markup:8 | - | X | - | \n", "| remove_html_markup:9 | X | X | X | \n", "| remove_html_markup:10 | - | X | - | \n", "| remove_html_markup:11 | X | X | X | \n", "| remove_html_markup:12 | - | - | X | \n", "| remove_html_markup:13 | X | X | X | \n", "| remove_html_markup:14 | X | X | X | \n", "| remove_html_markup:16 | X | X | X | \n" ], "text/plain": [ " 1 50% def remove_html_markup(s): # type: ignore\n", " 2 50% tag = False\n", " 3 50% quote = False\n", " 4 50% out = \"\"\n", " 5\n", " 6 50% for c in s:\n", " 7 50% if c == '<' and not quote:\n", " 8 0% tag = True\n", " 9 50% elif c == '>' and not quote:\n", " 10 0% tag = False\n", " 11 50% elif c == '\"' or c == \"'\" and tag:\n", " 12 100% quote = not quote\n", " 13 50% elif not tag:\n", " 14 50% out = out + c\n", " 15\n", " 16 50% return out" ] }, "execution_count": 88, "metadata": {}, "output_type": "execute_result" } ], "source": [ "debugger" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "What happens with our `quote = not quote` \"culprit\" line if it is executed in passing runs, too?" ] }, { "cell_type": "code", "execution_count": 89, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.952587Z", "iopub.status.busy": "2023-11-12T12:41:20.952493Z", "iopub.status.idle": "2023-11-12T12:41:20.954372Z", "shell.execute_reply": "2023-11-12T12:41:20.954097Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "with debugger.collect_pass():\n", " out = remove_html_markup('')" ] }, { "cell_type": "code", "execution_count": 90, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.955910Z", "iopub.status.busy": "2023-11-12T12:41:20.955816Z", "iopub.status.idle": "2023-11-12T12:41:20.959811Z", "shell.execute_reply": "2023-11-12T12:41:20.959524Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", "
\n", "
quote = not quote
\"culprit\" line be shown after executing the above code?\n", "
\n", " \n", " \n", " \n", "1 def remove_html_markup(s): # type: ignore\n", "
2 tag = False\n", "
3 quote = False\n", "
4 out = ""\n", "
5\n", "
6 for c in s:\n", "
7 if c == '<' and not quote:\n", "
8 tag = True\n", "
9 elif c == '>' and not quote:\n", "
10 tag = False\n", "
11 elif c == '"' or c == "'" and tag:\n", "
12 quote = not quote\n", "
13 elif not tag:\n", "
14 out = out + c\n", "
15\n", "
16 return out\n" ], "text/markdown": [ "| `remove_html_markup` | `s='abc'` | `s='abc'` | `s=''` | `s='\"abc\"'` | \n", "| --------------------- | ---- | ---- | ---- | ---- | \n", "| remove_html_markup:1 | X | X | X | X | \n", "| remove_html_markup:2 | X | X | X | X | \n", "| remove_html_markup:3 | X | X | X | X | \n", "| remove_html_markup:4 | X | X | X | X | \n", "| remove_html_markup:6 | X | X | X | X | \n", "| remove_html_markup:7 | X | X | X | X | \n", "| remove_html_markup:8 | - | X | X | - | \n", "| remove_html_markup:9 | X | X | X | X | \n", "| remove_html_markup:10 | - | X | X | - | \n", "| remove_html_markup:11 | X | X | X | X | \n", "| remove_html_markup:12 | - | - | X | X | \n", "| remove_html_markup:13 | X | X | X | X | \n", "| remove_html_markup:14 | X | X | - | X | \n", "| remove_html_markup:16 | X | X | X | X | \n" ], "text/plain": [ " 1 50% def remove_html_markup(s): # type: ignore\n", " 2 50% tag = False\n", " 3 50% quote = False\n", " 4 50% out = \"\"\n", " 5\n", " 6 50% for c in s:\n", " 7 50% if c == '<' and not quote:\n", " 8 0% tag = True\n", " 9 50% elif c == '>' and not quote:\n", " 10 0% tag = False\n", " 11 50% elif c == '\"' or c == \"'\" and tag:\n", " 12 75% quote = not quote\n", " 13 50% elif not tag:\n", " 14 60% out = out + c\n", " 15\n", " 16 50% return out" ] }, "execution_count": 91, "metadata": {}, "output_type": "execute_result" } ], "source": [ "debugger" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Here's another example, coming right from the Tarantula paper. The `middle()` function takes three numbers `x`, `y`, and `z`, and returns the one that is neither the minimum nor the maximum of the three:" ] }, { "cell_type": "code", "execution_count": 92, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.967101Z", "iopub.status.busy": "2023-11-12T12:41:20.967005Z", "iopub.status.idle": "2023-11-12T12:41:20.969033Z", "shell.execute_reply": "2023-11-12T12:41:20.968772Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "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" ] }, { "cell_type": "code", "execution_count": 93, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.970527Z", "iopub.status.busy": "2023-11-12T12:41:20.970431Z", "iopub.status.idle": "2023-11-12T12:41:20.972679Z", "shell.execute_reply": "2023-11-12T12:41:20.972409Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 93, "metadata": {}, "output_type": "execute_result" } ], "source": [ "middle(1, 2, 3)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Unfortunately, `middle()` can fail:" ] }, { "cell_type": "code", "execution_count": 94, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.974022Z", "iopub.status.busy": "2023-11-12T12:41:20.973938Z", "iopub.status.idle": "2023-11-12T12:41:20.976003Z", "shell.execute_reply": "2023-11-12T12:41:20.975710Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 94, "metadata": {}, "output_type": "execute_result" } ], "source": [ "middle(2, 1, 3)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Let is see whether we can find the bug with a few additional test cases:" ] }, { "cell_type": "code", "execution_count": 95, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.977496Z", "iopub.status.busy": "2023-11-12T12:41:20.977388Z", "iopub.status.idle": "2023-11-12T12:41:20.979185Z", "shell.execute_reply": "2023-11-12T12:41:20.978916Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "# ignore\n", "T3 = TypeVar('T3', bound='DifferenceDebugger')" ] }, { "cell_type": "code", "execution_count": 96, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.980665Z", "iopub.status.busy": "2023-11-12T12:41:20.980561Z", "iopub.status.idle": "2023-11-12T12:41:20.982814Z", "shell.execute_reply": "2023-11-12T12:41:20.982569Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def test_debugger_middle(debugger: T3) -> T3:\n", " with debugger.collect_pass():\n", " middle(3, 3, 5)\n", " with debugger.collect_pass():\n", " middle(1, 2, 3)\n", " with debugger.collect_pass():\n", " middle(3, 2, 1)\n", " with debugger.collect_pass():\n", " middle(5, 5, 5)\n", " with debugger.collect_pass():\n", " middle(5, 3, 4)\n", " with debugger.collect_fail():\n", " middle(2, 1, 3)\n", " return debugger" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Note that in order to collect data from multiple function invocations, you need to have a separate `with` clause for every invocation. The following will _not_ work correctly:\n", "\n", "```python\n", " with debugger.collect_pass():\n", " middle(3, 3, 5)\n", " middle(1, 2, 3)\n", " ...\n", "```" ] }, { "cell_type": "code", "execution_count": 97, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.984220Z", "iopub.status.busy": "2023-11-12T12:41:20.984112Z", "iopub.status.idle": "2023-11-12T12:41:20.985792Z", "shell.execute_reply": "2023-11-12T12:41:20.985545Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "debugger = test_debugger_middle(ContinuousSpectrumDebugger())" ] }, { "cell_type": "code", "execution_count": 98, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.987434Z", "iopub.status.busy": "2023-11-12T12:41:20.987311Z", "iopub.status.idle": "2023-11-12T12:41:20.989727Z", "shell.execute_reply": "2023-11-12T12:41:20.989475Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/markdown": [ "| `middle` | `x=3, y=3, z=5` | `x=1, y=2, z=3` | `x=3, y=2, z=1` | `x=5, y=5, z=5` | `x=5, y=3, z=4` | `x=2, y=1, z=3` | \n", "| --------- | ---- | ---- | ---- | ---- | ---- | ---- | \n", "| middle:1 | X | X | X | X | X | X | \n", "| middle:2 | X | X | X | X | X | X | \n", "| middle:3 | X | X | - | - | X | X | \n", "| middle:4 | - | X | - | - | - | - | \n", "| middle:5 | X | - | - | - | X | X | \n", "| middle:6 | X | - | - | - | - | X | \n", "| middle:8 | - | - | X | X | - | - | \n", "| middle:9 | - | - | X | - | - | - | \n", "| middle:10 | - | - | - | X | - | - | \n", "| middle:12 | - | - | - | X | X | - | \n" ], "text/plain": [ "
1 def middle(x, y, z): # type: ignore\n", "
2 if y < z:\n", "
3 if x < y:\n", "
4 return y\n", "
5 elif x < z:\n", "
6 return y\n", "
7 else:\n", "\n", "
8 if x > y:\n", "
9 return y\n", "
10 elif x > z:\n", "
11 return x\n", "\n", "
12 return z\n" ], "text/markdown": [ "| `middle` | `x=3, y=3, z=5` | `x=1, y=2, z=3` | `x=3, y=2, z=1` | `x=5, y=5, z=5` | `x=5, y=3, z=4` | `x=2, y=1, z=3` | \n", "| --------- | ---- | ---- | ---- | ---- | ---- | ---- | \n", "| middle:1 | X | X | X | X | X | X | \n", "| middle:2 | X | X | X | X | X | X | \n", "| middle:3 | X | X | - | - | X | X | \n", "| middle:4 | - | X | - | - | - | - | \n", "| middle:5 | X | - | - | - | X | X | \n", "| middle:6 | X | - | - | - | - | X | \n", "| middle:8 | - | - | X | X | - | - | \n", "| middle:9 | - | - | X | - | - | - | \n", "| middle:10 | - | - | - | X | - | - | \n", "| middle:12 | - | - | - | X | X | - | \n" ], "text/plain": [ " 1 50% def middle(x, y, z): # type: ignore\n", " 2 50% if y < z:\n", " 3 62% if x < y:\n", " 4 0% return y\n", " 5 71% elif x < z:\n", " 6 83% return y\n", " 7 else:\n", " 8 0% if x > y:\n", " 9 0% return y\n", " 10 0% elif x > z:\n", " 11 return x\n", " 12 0% return z" ] }, "execution_count": 99, "metadata": {}, "output_type": "execute_result" } ], "source": [ "debugger" ] }, { "cell_type": "code", "execution_count": 100, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:20.995997Z", "iopub.status.busy": "2023-11-12T12:41:20.995896Z", "iopub.status.idle": "2023-11-12T12:41:21.000054Z", "shell.execute_reply": "2023-11-12T12:41:20.999774Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", "
\n", "
\n", "
\n", " \n", " \n", " \n", "1 def remove_html_markup(s): # type: ignore\n", "
2 tag = False\n", "
3 quote = False\n", "
4 out = ""\n", "
5\n", "
6 for c in s:\n", "
7 if c == '<' and not quote:\n", "
8 tag = True\n", "
9 elif c == '>' and not quote:\n", "
10 tag = False\n", "
11 elif c == '"' or c == "'" and tag:\n", "
12 quote = not quote\n", "
13 elif not tag:\n", "
14 out = out + c\n", "
15\n", "
16 return out\n" ], "text/markdown": [ "| `remove_html_markup` | `s='abc'` | `s='abc'` | `s='\"abc\"'` | \n", "| --------------------- | ---- | ---- | ---- | \n", "| remove_html_markup:1 | X | X | X | \n", "| remove_html_markup:2 | X | X | X | \n", "| remove_html_markup:3 | X | X | X | \n", "| remove_html_markup:4 | X | X | X | \n", "| remove_html_markup:6 | X | X | X | \n", "| remove_html_markup:7 | X | X | X | \n", "| remove_html_markup:8 | - | X | - | \n", "| remove_html_markup:9 | X | X | X | \n", "| remove_html_markup:10 | - | X | - | \n", "| remove_html_markup:11 | X | X | X | \n", "| remove_html_markup:12 | - | - | X | \n", "| remove_html_markup:13 | X | X | X | \n", "| remove_html_markup:14 | X | X | X | \n", "| remove_html_markup:16 | X | X | X | \n" ], "text/plain": [ "[('remove_html_markup', 12), ('remove_html_markup', 11), ('remove_html_markup', 14), ('remove_html_markup', 3), ('remove_html_markup', 6), ('remove_html_markup', 9), ('remove_html_markup', 1), ('remove_html_markup', 7), ('remove_html_markup', 4), ('remove_html_markup', 13), ('remove_html_markup', 16), ('remove_html_markup', 2), ('remove_html_markup', 10), ('remove_html_markup', 8)]" ] }, "execution_count": 106, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tarantula_html" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Here's our ranking of lines, from most suspicious to least suspicious:" ] }, { "cell_type": "code", "execution_count": 107, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.023800Z", "iopub.status.busy": "2023-11-12T12:41:21.023717Z", "iopub.status.idle": "2023-11-12T12:41:21.026063Z", "shell.execute_reply": "2023-11-12T12:41:21.025782Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "[('remove_html_markup', 12),\n", " ('remove_html_markup', 11),\n", " ('remove_html_markup', 14),\n", " ('remove_html_markup', 3),\n", " ('remove_html_markup', 6),\n", " ('remove_html_markup', 9),\n", " ('remove_html_markup', 1),\n", " ('remove_html_markup', 7),\n", " ('remove_html_markup', 4),\n", " ('remove_html_markup', 13),\n", " ('remove_html_markup', 16),\n", " ('remove_html_markup', 2),\n", " ('remove_html_markup', 10),\n", " ('remove_html_markup', 8)]" ] }, "execution_count": 107, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tarantula_html.rank()" ] }, { "cell_type": "code", "execution_count": 108, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.027606Z", "iopub.status.busy": "2023-11-12T12:41:21.027449Z", "iopub.status.idle": "2023-11-12T12:41:21.029792Z", "shell.execute_reply": "2023-11-12T12:41:21.029504Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "1.0" ] }, "execution_count": 108, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tarantula_html.suspiciousness(tarantula_html.rank()[0])" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "We see that the first line in the list is indeed the most suspicious; the two \"green\" lines come at the very end." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "For the `middle()` function, we also obtain a ranking from \"reddest\" to \"greenest\"." ] }, { "cell_type": "code", "execution_count": 109, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.031256Z", "iopub.status.busy": "2023-11-12T12:41:21.031174Z", "iopub.status.idle": "2023-11-12T12:41:21.032882Z", "shell.execute_reply": "2023-11-12T12:41:21.032631Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "tarantula_middle = test_debugger_middle(TarantulaDebugger())" ] }, { "cell_type": "code", "execution_count": 110, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.034162Z", "iopub.status.busy": "2023-11-12T12:41:21.034081Z", "iopub.status.idle": "2023-11-12T12:41:21.037223Z", "shell.execute_reply": "2023-11-12T12:41:21.036962Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/html": [ "
1 def middle(x, y, z): # type: ignore\n", "
2 if y < z:\n", "
3 if x < y:\n", "
4 return y\n", "
5 elif x < z:\n", "
6 return y\n", "
7 else:\n", "\n", "
8 if x > y:\n", "
9 return y\n", "
10 elif x > z:\n", "
11 return x\n", "\n", "
12 return z\n" ], "text/markdown": [ "| `middle` | `x=3, y=3, z=5` | `x=1, y=2, z=3` | `x=3, y=2, z=1` | `x=5, y=5, z=5` | `x=5, y=3, z=4` | `x=2, y=1, z=3` | \n", "| --------- | ---- | ---- | ---- | ---- | ---- | ---- | \n", "| middle:1 | X | X | X | X | X | X | \n", "| middle:2 | X | X | X | X | X | X | \n", "| middle:3 | X | X | - | - | X | X | \n", "| middle:4 | - | X | - | - | - | - | \n", "| middle:5 | X | - | - | - | X | X | \n", "| middle:6 | X | - | - | - | - | X | \n", "| middle:8 | - | - | X | X | - | - | \n", "| middle:9 | - | - | X | - | - | - | \n", "| middle:10 | - | - | - | X | - | - | \n", "| middle:12 | - | - | - | X | X | - | \n" ], "text/plain": [ "[('middle', 6), ('middle', 5), ('middle', 3), ('middle', 2), ('middle', 1), ('middle', 12), ('middle', 9), ('middle', 8), ('middle', 4), ('middle', 10)]" ] }, "execution_count": 110, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tarantula_middle" ] }, { "cell_type": "code", "execution_count": 111, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.038786Z", "iopub.status.busy": "2023-11-12T12:41:21.038690Z", "iopub.status.idle": "2023-11-12T12:41:21.041069Z", "shell.execute_reply": "2023-11-12T12:41:21.040793Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "[('middle', 6),\n", " ('middle', 5),\n", " ('middle', 3),\n", " ('middle', 2),\n", " ('middle', 1),\n", " ('middle', 12),\n", " ('middle', 9),\n", " ('middle', 8),\n", " ('middle', 4),\n", " ('middle', 10)]" ] }, "execution_count": 111, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tarantula_middle.rank()" ] }, { "cell_type": "code", "execution_count": 112, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.042704Z", "iopub.status.busy": "2023-11-12T12:41:21.042570Z", "iopub.status.idle": "2023-11-12T12:41:21.044717Z", "shell.execute_reply": "2023-11-12T12:41:21.044453Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "0.8333333333333333" ] }, "execution_count": 112, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tarantula_middle.suspiciousness(tarantula_middle.rank()[0])" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### The Ochiai Metric\n", "\n", "The _Ochiai_ Metric \\cite{Ochiai1957} first introduced in the biology domain \\cite{daSilvaMeyer2004} and later applied for fault localization by Abreu et al. \\cite{Abreu2009}, is defined as follows:" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "$$\n", "\\textit{suspiciousness}_\\textit{ochiai} = \\frac\n", "{\\textit{failed}(\\textit{event})}\n", "{\\sqrt{\n", "\\bigl(\\textit{failed}(\\textit{event}) + \\textit{not-in-failed}(\\textit{event})\\bigr)\n", "\\times\n", "\\bigl(\\textit{failed}(\\textit{event}) + \\textit{passed}(\\textit{event})\\bigr)\n", "}}\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "where\n", "\n", "* $\\textit{failed}(\\textit{event})$ is the number of times the event occurred in _failing_ runs\n", "* $\\textit{not-in-failed}(\\textit{event})$ is the number of times the event did _not_ occur in failing runs\n", "* $\\textit{passed}(\\textit{event})$ is the number of times the event occurred in _passing_ runs.\n", "\n", "We can easily implement this formula:" ] }, { "cell_type": "code", "execution_count": 113, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.046395Z", "iopub.status.busy": "2023-11-12T12:41:21.046164Z", "iopub.status.idle": "2023-11-12T12:41:21.047813Z", "shell.execute_reply": "2023-11-12T12:41:21.047582Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import math" ] }, { "cell_type": "code", "execution_count": 114, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.049278Z", "iopub.status.busy": "2023-11-12T12:41:21.049169Z", "iopub.status.idle": "2023-11-12T12:41:21.052155Z", "shell.execute_reply": "2023-11-12T12:41:21.051890Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class OchiaiDebugger(ContinuousSpectrumDebugger, RankingDebugger):\n", " \"\"\"Spectrum-based Debugger using the Ochiai metric for suspiciousness\"\"\"\n", "\n", " def suspiciousness(self, event: Any) -> Optional[float]:\n", " failed = len(self.collectors_with_event(event, self.FAIL))\n", " not_in_failed = len(self.collectors_without_event(event, self.FAIL))\n", " passed = len(self.collectors_with_event(event, self.PASS))\n", "\n", " try:\n", " return failed / math.sqrt((failed + not_in_failed) * (failed + passed))\n", " except ZeroDivisionError:\n", " return None\n", "\n", " def hue(self, event: Any) -> Optional[float]:\n", " suspiciousness = self.suspiciousness(event)\n", " if suspiciousness is None:\n", " return None\n", " return 1 - suspiciousness" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Applied on the `remove_html_markup()` function, the individual suspiciousness scores differ from Tarantula. However, we obtain a very similar visualization, and the same ranking." ] }, { "cell_type": "code", "execution_count": 115, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.053503Z", "iopub.status.busy": "2023-11-12T12:41:21.053404Z", "iopub.status.idle": "2023-11-12T12:41:21.055133Z", "shell.execute_reply": "2023-11-12T12:41:21.054866Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "ochiai_html = test_debugger_html(OchiaiDebugger())" ] }, { "cell_type": "code", "execution_count": 116, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.056571Z", "iopub.status.busy": "2023-11-12T12:41:21.056459Z", "iopub.status.idle": "2023-11-12T12:41:21.059802Z", "shell.execute_reply": "2023-11-12T12:41:21.059517Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/html": [ "
1 def remove_html_markup(s): # type: ignore\n", "
2 tag = False\n", "
3 quote = False\n", "
4 out = ""\n", "
5\n", "
6 for c in s:\n", "
7 if c == '<' and not quote:\n", "
8 tag = True\n", "
9 elif c == '>' and not quote:\n", "
10 tag = False\n", "
11 elif c == '"' or c == "'" and tag:\n", "
12 quote = not quote\n", "
13 elif not tag:\n", "
14 out = out + c\n", "
15\n", "
16 return out\n" ], "text/markdown": [ "| `remove_html_markup` | `s='abc'` | `s='abc'` | `s='\"abc\"'` | \n", "| --------------------- | ---- | ---- | ---- | \n", "| remove_html_markup:1 | X | X | X | \n", "| remove_html_markup:2 | X | X | X | \n", "| remove_html_markup:3 | X | X | X | \n", "| remove_html_markup:4 | X | X | X | \n", "| remove_html_markup:6 | X | X | X | \n", "| remove_html_markup:7 | X | X | X | \n", "| remove_html_markup:8 | - | X | - | \n", "| remove_html_markup:9 | X | X | X | \n", "| remove_html_markup:10 | - | X | - | \n", "| remove_html_markup:11 | X | X | X | \n", "| remove_html_markup:12 | - | - | X | \n", "| remove_html_markup:13 | X | X | X | \n", "| remove_html_markup:14 | X | X | X | \n", "| remove_html_markup:16 | X | X | X | \n" ], "text/plain": [ "[('remove_html_markup', 12), ('remove_html_markup', 11), ('remove_html_markup', 14), ('remove_html_markup', 3), ('remove_html_markup', 6), ('remove_html_markup', 9), ('remove_html_markup', 1), ('remove_html_markup', 7), ('remove_html_markup', 4), ('remove_html_markup', 13), ('remove_html_markup', 16), ('remove_html_markup', 2), ('remove_html_markup', 10), ('remove_html_markup', 8)]" ] }, "execution_count": 116, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ochiai_html" ] }, { "cell_type": "code", "execution_count": 117, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.061367Z", "iopub.status.busy": "2023-11-12T12:41:21.061265Z", "iopub.status.idle": "2023-11-12T12:41:21.063773Z", "shell.execute_reply": "2023-11-12T12:41:21.063487Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "[('remove_html_markup', 12),\n", " ('remove_html_markup', 11),\n", " ('remove_html_markup', 14),\n", " ('remove_html_markup', 3),\n", " ('remove_html_markup', 6),\n", " ('remove_html_markup', 9),\n", " ('remove_html_markup', 1),\n", " ('remove_html_markup', 7),\n", " ('remove_html_markup', 4),\n", " ('remove_html_markup', 13),\n", " ('remove_html_markup', 16),\n", " ('remove_html_markup', 2),\n", " ('remove_html_markup', 10),\n", " ('remove_html_markup', 8)]" ] }, "execution_count": 117, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ochiai_html.rank()" ] }, { "cell_type": "code", "execution_count": 118, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.065162Z", "iopub.status.busy": "2023-11-12T12:41:21.065070Z", "iopub.status.idle": "2023-11-12T12:41:21.067263Z", "shell.execute_reply": "2023-11-12T12:41:21.067032Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "1.0" ] }, "execution_count": 118, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ochiai_html.suspiciousness(ochiai_html.rank()[0])" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The same observations also apply for the `middle()` function." ] }, { "cell_type": "code", "execution_count": 119, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.087133Z", "iopub.status.busy": "2023-11-12T12:41:21.086988Z", "iopub.status.idle": "2023-11-12T12:41:21.088906Z", "shell.execute_reply": "2023-11-12T12:41:21.088592Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "ochiai_middle = test_debugger_middle(OchiaiDebugger())" ] }, { "cell_type": "code", "execution_count": 120, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.090482Z", "iopub.status.busy": "2023-11-12T12:41:21.090361Z", "iopub.status.idle": "2023-11-12T12:41:21.093340Z", "shell.execute_reply": "2023-11-12T12:41:21.093068Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/html": [ "
1 def middle(x, y, z): # type: ignore\n", "
2 if y < z:\n", "
3 if x < y:\n", "
4 return y\n", "
5 elif x < z:\n", "
6 return y\n", "
7 else:\n", "\n", "
8 if x > y:\n", "
9 return y\n", "
10 elif x > z:\n", "
11 return x\n", "\n", "
12 return z\n" ], "text/markdown": [ "| `middle` | `x=3, y=3, z=5` | `x=1, y=2, z=3` | `x=3, y=2, z=1` | `x=5, y=5, z=5` | `x=5, y=3, z=4` | `x=2, y=1, z=3` | \n", "| --------- | ---- | ---- | ---- | ---- | ---- | ---- | \n", "| middle:1 | X | X | X | X | X | X | \n", "| middle:2 | X | X | X | X | X | X | \n", "| middle:3 | X | X | - | - | X | X | \n", "| middle:4 | - | X | - | - | - | - | \n", "| middle:5 | X | - | - | - | X | X | \n", "| middle:6 | X | - | - | - | - | X | \n", "| middle:8 | - | - | X | X | - | - | \n", "| middle:9 | - | - | X | - | - | - | \n", "| middle:10 | - | - | - | X | - | - | \n", "| middle:12 | - | - | - | X | X | - | \n" ], "text/plain": [ "[('middle', 6), ('middle', 5), ('middle', 3), ('middle', 2), ('middle', 1), ('middle', 12), ('middle', 9), ('middle', 8), ('middle', 4), ('middle', 10)]" ] }, "execution_count": 120, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ochiai_middle" ] }, { "cell_type": "code", "execution_count": 121, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.094739Z", "iopub.status.busy": "2023-11-12T12:41:21.094638Z", "iopub.status.idle": "2023-11-12T12:41:21.097034Z", "shell.execute_reply": "2023-11-12T12:41:21.096632Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "[('middle', 6),\n", " ('middle', 5),\n", " ('middle', 3),\n", " ('middle', 2),\n", " ('middle', 1),\n", " ('middle', 12),\n", " ('middle', 9),\n", " ('middle', 8),\n", " ('middle', 4),\n", " ('middle', 10)]" ] }, "execution_count": 121, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ochiai_middle.rank()" ] }, { "cell_type": "code", "execution_count": 122, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.099136Z", "iopub.status.busy": "2023-11-12T12:41:21.098939Z", "iopub.status.idle": "2023-11-12T12:41:21.101772Z", "shell.execute_reply": "2023-11-12T12:41:21.101346Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "0.7071067811865475" ] }, "execution_count": 122, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ochiai_middle.suspiciousness(ochiai_middle.rank()[0])" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### How Useful is Ranking?\n", "\n", "So, which metric is better? The standard method to evaluate such rankings is to determine a _ground truth_ – that is, the set of locations that eventually are fixed – and to check at which point in the ranking any such location occurs – the earlier, the better. In our `remove_html_markup()` and `middle()` examples, both the Tarantula and the Ochiai metric perform flawlessly, as the \"culprit\" line is always ranked at the top. However, this need not always be the case; the exact performance depends on the nature of the code and the observed runs. (Also, the question of whether there always is exactly one possible location where the program can be fixed is open for discussion.)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "You will be surprised that over time, _several dozen_ metrics have been proposed \\cite{Wong2016}, each performing somewhat better or somewhat worse depending on which benchmark they were applied on. The two metrics discussed above each have their merits – the Tarantula metric was among the first such metrics, and the Ochiai metric is generally shown to be among the most effective ones \\cite{Abreu2009}." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "While rankings can be easily _evaluated_, it is not necessarily clear whether and how much they serve programmers. As stated above, the assumption of rankings is that developers examine one potentially defective statement after another until they find the actually defective one. However, in a series of human studies with developers, Parnin and Orso \\cite{Parnin2011} found that this assumption may not hold:\n", "\n", "> It is unclear whether developers can actually determine the faulty nature of a statement by simply looking at it, without any additional information (e.g., the state of the program when the statement was executed or the statements that were executed before or after that one).\n", "\n", "In their study, they found that rankings could help completing a task faster, but this effect was limited to experienced developers and simpler code. Artificially changing the rank of faulty statements had little to no effect, implying that developers would not strictly follow the ranked list of statements, but rather search through the code to understand it. At this point, a _visualization_ as in the Tarantula tool can be helpful to programmers as it _guides_ the search, but a _ranking_ that _defines_ where to search may be less useful." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Having said that, ranking has its merits – notably as it comes to informing _automated_ debugging techniques. In the [chapter on program repair](Repairer.ipynb), we will see how ranked lists of potentially faulty statements tell automated repair techniques where to try to repair the program first. And once such a repair is successful, we have a very strong indication on where and how the program could be fixed!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Using Large Test Suites" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "In fault localization, the larger and the more thorough the test suite, the higher the precision. Let us try out what happens if we extend the `middle()` test suite with additional test cases." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The function `middle_testcase()` returns a random input for `middle()`:" ] }, { "cell_type": "code", "execution_count": 123, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.103681Z", "iopub.status.busy": "2023-11-12T12:41:21.103564Z", "iopub.status.idle": "2023-11-12T12:41:21.105097Z", "shell.execute_reply": "2023-11-12T12:41:21.104842Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "import random" ] }, { "cell_type": "code", "execution_count": 124, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.106436Z", "iopub.status.busy": "2023-11-12T12:41:21.106352Z", "iopub.status.idle": "2023-11-12T12:41:21.108316Z", "shell.execute_reply": "2023-11-12T12:41:21.108053Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def middle_testcase() -> Tuple[int, int, int]:\n", " x = random.randrange(10)\n", " y = random.randrange(10)\n", " z = random.randrange(10)\n", " return x, y, z" ] }, { "cell_type": "code", "execution_count": 125, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.109638Z", "iopub.status.busy": "2023-11-12T12:41:21.109545Z", "iopub.status.idle": "2023-11-12T12:41:21.112092Z", "shell.execute_reply": "2023-11-12T12:41:21.111825Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "[(9, 0, 5), (0, 1, 9), (9, 0, 9), (2, 9, 0), (4, 7, 2)]" ] }, "execution_count": 125, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[middle_testcase() for i in range(5)]" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The function `middle_test()` simply checks if `middle()` operates correctly – by placing `x`, `y`, and `z` in a list, sorting it, and checking the middle argument. If `middle()` fails, `middle_test()` raises an exception." ] }, { "cell_type": "code", "execution_count": 126, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.113681Z", "iopub.status.busy": "2023-11-12T12:41:21.113571Z", "iopub.status.idle": "2023-11-12T12:41:21.115461Z", "shell.execute_reply": "2023-11-12T12:41:21.115201Z" }, "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": 127, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.116864Z", "iopub.status.busy": "2023-11-12T12:41:21.116767Z", "iopub.status.idle": "2023-11-12T12:41:21.118318Z", "shell.execute_reply": "2023-11-12T12:41:21.118085Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "middle_test(4, 5, 6)" ] }, { "cell_type": "code", "execution_count": 128, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.119708Z", "iopub.status.busy": "2023-11-12T12:41:21.119620Z", "iopub.status.idle": "2023-11-12T12:41:21.121371Z", "shell.execute_reply": "2023-11-12T12:41:21.121079Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from ExpectError import ExpectError" ] }, { "cell_type": "code", "execution_count": 129, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.122803Z", "iopub.status.busy": "2023-11-12T12:41:21.122712Z", "iopub.status.idle": "2023-11-12T12:41:21.124619Z", "shell.execute_reply": "2023-11-12T12:41:21.124366Z" }, "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_26712/3661663124.py\", line 2, in
1 def middle(x, y, z): # type: ignore\n", "
2 if y < z:\n", "
3 if x < y:\n", "
4 return y\n", "
5 elif x < z:\n", "
6 return y\n", "
7 else:\n", "\n", "
8 if x > y:\n", "
9 return y\n", "
10 elif x > z:\n", "
11 return x\n", "
12 return z\n" ], "text/markdown": [ "| `middle` | `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=7, y=7, z=0` | `x=4, y=9, z=8` | `x=3, y=8, z=4` | `x=3, y=3, z=5` | `x=3, y=2, z=2` | `x=8, y=8, z=1` | `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: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: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: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 | \n", "| middle:4 | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | X | - | - | X | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | X | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | \n", "| middle:5 | - | - | - | - | - | - | - | - | - | X | X | X | - | - | - | - | X | - | - | - | - | - | X | X | - | - | X | - | - | X | - | - | X | - | - | - | X | - | - | - | - | - | - | - | - | X | - | - | - | X | X | - | - | - | - | - | - | - | X | - | - | - | - | - | - | X | - | - | X | - | X | - | - | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | X | X | - | X | - | - | - | - | - | X | - | - | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | 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: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 | \n", "| middle: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 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | \n", "| middle:9 | X | - | X | - | - | - | - | - | X | - | - | - | X | - | - | X | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | X | - | - | - | X | X | - | - | - | X | - | - | X | - | - | - | - | X | - | - | - | - | X | - | X | X | - | - | X | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | X | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | \n", "| middle: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 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | \n", "| middle:11 | - | X | - | - | - | - | - | - | - | - | - | - | - | X | - | - | - | - | - | - | - | X | - | - | X | - | - | - | - | - | - | X | - | - | X | X | - | - | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | X | X | - | X | - | - | - | - | X | - | - | - | - | X | - | - | - | - | - | X | X | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | X | - | X | - | - | - | - | X | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | \n", "| middle: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 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | \n" ], "text/plain": [ "[('middle', 6), ('middle', 5), ('middle', 3), ('middle', 2), ('middle', 1), ('middle', 12), ('middle', 9), ('middle', 8), ('middle', 11), ('middle', 4), ('middle', 10)]" ] }, "execution_count": 138, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ochiai_middle" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "We see that the \"culprit\" line is still the most likely to be fixed, but the two conditions leading to the error (`x < y` and `x < z`) are also listed as potentially faulty. That is because the error might also be fixed be changing these conditions – although this would result in a more complex fix." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Other Events besides Coverage\n", "\n", "We close this chapter with two directions for further thought. If you wondered why in the above code, we were mostly talking about `events` rather than lines covered, that is because our framework allows for tracking arbitrary events, not just coverage. In fact, any data item a collector can extract from the execution can be used for correlation analysis. (It may not be so easily visualized, though.)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Here's an example. We define a `ValueCollector` class that collects pairs of (local) variables and their values during execution. Its `events()` method then returns the set of all these pairs." ] }, { "cell_type": "code", "execution_count": 139, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.177843Z", "iopub.status.busy": "2023-11-12T12:41:21.177716Z", "iopub.status.idle": "2023-11-12T12:41:21.180243Z", "shell.execute_reply": "2023-11-12T12:41:21.179972Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "class ValueCollector(Collector):\n", " \"\"\"\"A class to collect local variables and their values.\"\"\"\n", "\n", " def __init__(self) -> None:\n", " \"\"\"Constructor.\"\"\"\n", " super().__init__()\n", " self.vars: Set[str] = set()\n", "\n", " def collect(self, frame: FrameType, event: str, arg: Any) -> None:\n", " local_vars = frame.f_locals\n", " for var in local_vars:\n", " value = local_vars[var]\n", " self.vars.add(f\"{var} = {repr(value)}\")\n", "\n", " def events(self) -> Set[str]:\n", " \"\"\"A set of (variable, value) pairs observed\"\"\"\n", " return self.vars" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "If we apply this collector on our set of HTML test cases, these are all the events that we obtain – essentially all variables and all values ever seen:" ] }, { "cell_type": "code", "execution_count": 140, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.181980Z", "iopub.status.busy": "2023-11-12T12:41:21.181822Z", "iopub.status.idle": "2023-11-12T12:41:21.184632Z", "shell.execute_reply": "2023-11-12T12:41:21.184211Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "out = 'ab'\n", "s = 'abc'\n", "quote = True\n", "out = 'abc'\n", "s = '\"abc\"'\n", "out = 'a'\n", "tag = False\n", "out = ''\n", "c = 'b'\n", "c = '>'\n", "c = 'a'\n", "tag = True\n", "c = '\"'\n", "s = 'abc'\n", "c = 'c'\n", "c = '/'\n", "quote = False\n", "c = '<'\n" ] } ], "source": [ "debugger = test_debugger_html(ContinuousSpectrumDebugger(ValueCollector))\n", "for event in debugger.all_events():\n", " print(event)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "However, some of these events only occur in the failing run:" ] }, { "cell_type": "code", "execution_count": 141, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.186930Z", "iopub.status.busy": "2023-11-12T12:41:21.186767Z", "iopub.status.idle": "2023-11-12T12:41:21.188700Z", "shell.execute_reply": "2023-11-12T12:41:21.188418Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "s = '\"abc\"'\n", "c = '\"'\n", "quote = True\n" ] } ], "source": [ "for event in debugger.only_fail_events():\n", " print(event)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Some of these differences are spurious – the string `\"abc\"` (with quotes) only occurs in the failing run – but others, such as `quote` being True and `c` containing a single quote are actually relevant for explaining when the failure comes to be." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "We can even visualize the suspiciousness of the individual events, setting the (so far undiscussed) `color` flag for producing an event table:" ] }, { "cell_type": "code", "execution_count": 142, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:21.190269Z", "iopub.status.busy": "2023-11-12T12:41:21.190113Z", "iopub.status.idle": "2023-11-12T12:41:21.192523Z", "shell.execute_reply": "2023-11-12T12:41:21.192289Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/markdown": [ "| `remove_html_markup` | `s='abc'` | `s='abc'` | `s='\"abc\"'` | \n", "| ---------------- | ---- | ---- | ---- | \n", "| c = '"' | - | - | X | \n", "| c = '/' | - | X | - | \n", "| c = '<' | - | X | - | \n", "| c = '>' | - | X | - | \n", "| c = 'a' | X | X | X | \n", "| c = 'b' | X | X | X | \n", "| c = 'c' | X | X | X | \n", "| out = '' | X | X | X | \n", "| out = 'a' | X | X | X | \n", "| out = 'ab' | X | X | X | \n", "| out = 'abc' | X | X | X | \n", "| quote = False | X | X | X | \n", "| quote = True | - | - | X | \n", "| s = '"abc"' | - | - | X | \n", "| s = '<b>abc</b>' | - | X | - | \n", "| s = 'abc' | X | - | - | \n", "| tag = False | X | X | X | \n", "| tag = True | - | X | - | \n" ], "text/plain": [ "
1 def remove_html_markup(s): # type: ignore\n", "
2 tag = False\n", "
3 quote = False\n", "
4 out = ""\n", "
5\n", "
6 for c in s:\n", "
7 if c == '<' and not quote:\n", "
8 tag = True\n", "
9 elif c == '>' and not quote:\n", "
10 tag = False\n", "
11 elif c == '"' or c == "'" and tag:\n", "
12 quote = not quote\n", "
13 elif not tag:\n", "
14 out = out + c\n", "
15\n", "
16 return out\n" ], "text/markdown": [ "| `remove_html_markup` | `s='abc'` | `s='abc'` | `s='\"abc\"'` | \n", "| --------------------- | ---- | ---- | ---- | \n", "| remove_html_markup:1 | X | X | X | \n", "| remove_html_markup:2 | X | X | X | \n", "| remove_html_markup:3 | X | X | X | \n", "| remove_html_markup:4 | X | X | X | \n", "| remove_html_markup:6 | X | X | X | \n", "| remove_html_markup:7 | X | X | X | \n", "| remove_html_markup:8 | - | X | - | \n", "| remove_html_markup:9 | X | X | X | \n", "| remove_html_markup:10 | - | X | - | \n", "| remove_html_markup:11 | X | X | X | \n", "| remove_html_markup:12 | - | - | X | \n", "| remove_html_markup:13 | X | X | X | \n", "| remove_html_markup:14 | X | X | X | \n", "| remove_html_markup:16 | X | X | X | \n" ], "text/plain": [ "[('remove_html_markup', 12), ('remove_html_markup', 11), ('remove_html_markup', 14), ('remove_html_markup', 3), ('remove_html_markup', 6), ('remove_html_markup', 9), ('remove_html_markup', 1), ('remove_html_markup', 7), ('remove_html_markup', 4), ('remove_html_markup', 13), ('remove_html_markup', 16), ('remove_html_markup', 2), ('remove_html_markup', 10), ('remove_html_markup', 8)]" ] }, "execution_count": 164, "metadata": {}, "output_type": "execute_result" } ], "source": [ "debugger" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Ranking Events\n", "\n", "The method `rank()` returns a ranked list of events, starting with the most suspicious. This is useful for automated techniques that need potential defect locations." ] }, { "cell_type": "code", "execution_count": 165, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:24.627617Z", "iopub.status.busy": "2023-11-12T12:41:24.627498Z", "iopub.status.idle": "2023-11-12T12:41:24.630288Z", "shell.execute_reply": "2023-11-12T12:41:24.629993Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "[('remove_html_markup', 12),\n", " ('remove_html_markup', 11),\n", " ('remove_html_markup', 14),\n", " ('remove_html_markup', 3),\n", " ('remove_html_markup', 6),\n", " ('remove_html_markup', 9),\n", " ('remove_html_markup', 1),\n", " ('remove_html_markup', 7),\n", " ('remove_html_markup', 4),\n", " ('remove_html_markup', 13),\n", " ('remove_html_markup', 16),\n", " ('remove_html_markup', 2),\n", " ('remove_html_markup', 10),\n", " ('remove_html_markup', 8)]" ] }, "execution_count": 165, "metadata": {}, "output_type": "execute_result" } ], "source": [ "debugger.rank()" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Classes and Methods\n", "\n", "Here are all classes defined in this chapter:" ] }, { "cell_type": "code", "execution_count": 166, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:24.631810Z", "iopub.status.busy": "2023-11-12T12:41:24.631691Z", "iopub.status.idle": "2023-11-12T12:41:24.633377Z", "shell.execute_reply": "2023-11-12T12:41:24.633126Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "# ignore\n", "from ClassDiagram import display_class_hierarchy" ] }, { "cell_type": "code", "execution_count": 167, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:41:24.634700Z", "iopub.status.busy": "2023-11-12T12:41:24.634612Z", "iopub.status.idle": "2023-11-12T12:41:25.088950Z", "shell.execute_reply": "2023-11-12T12:41:25.088505Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "