{ "cells": [ { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "# Introduction to Debugging\n", "\n", "In this book, we want to explore _debugging_ - the art and science of fixing bugs in computer software. In particular, we want to explore techniques that _automatically_ answer questions like: Where is the bug? When does it occur? And how can we repair it? But before we start automating the debugging process, we first need to understand what this process is.\n", "\n", "In this chapter, we introduce basic concepts of systematic software debugging and the debugging process, and at the same time get acquainted with Python and interactive notebooks." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:22.868642Z", "iopub.status.busy": "2023-11-12T12:39:22.868502Z", "iopub.status.idle": "2023-11-12T12:39:22.911722Z", "shell.execute_reply": "2023-11-12T12:39:22.911343Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " " ], "text/plain": [ "" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from bookutils import YouTubeVideo, quiz\n", "YouTubeVideo(\"bCHRCehDOq0\")" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "**Prerequisites**\n", "\n", "* The book is meant to be a standalone reference; however, a number of _great books on debugging_ are listed at the end,\n", "* Knowing a bit of _Python_ is helpful for understanding the code examples in the book." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "## Synopsis\n", "\n", "\n", "To [use the code provided in this chapter](Importing.ipynb), write\n", "\n", "```python\n", ">>> from debuggingbook.Intro_Debugging import \n", "```\n", "\n", "and then make use of the following features.\n", "\n", "\n", "In this chapter, we introduce some basics of how failures come to be as well as a general process for debugging.\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": true, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## A Simple Function" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:22.935043Z", "iopub.status.busy": "2023-11-12T12:39:22.934792Z", "iopub.status.idle": "2023-11-12T12:39:22.937295Z", "shell.execute_reply": "2023-11-12T12:39:22.936941Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "# ignore\n", "\n", "# If this is the first time you are opening a notebook, please read this.\n", "#\n", "# Interaction basics\n", "# ------------------\n", "#\n", "# * The notebook is composed of _code cells_ (like this one) and\n", "# _text cells_ (like the one above).\n", "# \n", "# * To interact with the notebook, click into a cell (or type `Return`) \n", "# and start editing. Type `Shift+Return` to execute the code, or \n", "# `Esc` to leave without executing it.\n", "# \n", "# * Since code cells depend on earlier cells, you will have to execute\n", "# those first - beginning from the top of the notebook.\n", "# \n", "# * You can change code (and text) at your leisure to try out alternatives.\n", "# In Jupyter, use `b` to add a new cell below, and `Return` to enter it.\n", "# Type `x` to delete (cut) a cell, and `z` to undo this.\n", "# \n", "# * There's a `Help` menu at the top of Jupyter Notebook. Enjoy!\n", "#\n", "#\n", "# `# ignore` markers\n", "# ------------------\n", "#\n", "# * In the notebook, there are some extra code cells starting with `# ignore`\n", "# (like this one, actually). These are code blocks used to create diagrams,\n", "# run tests, create or tear down special environments or more - code blocks\n", "# that are not necessary for reading (but for creation).\n", "#\n", "#\n", "# `# type: ignore` markers\n", "# ------------------------\n", "#\n", "# * In the notebook, some lines come with a comment `# type: ignore`. This tells\n", "# static code checkers to ignore any typing errors in that line. Most frequently,\n", "# this is used to mark untyped Python code (as in our examples) such that the\n", "# static code checker does not mark it as erroneous." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": true, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Your Task: Remove HTML Markup\n", "\n", "Let us start with a simple example. You may have heard of how documents on the Web are made out of text and HTML markup. HTML markup consists of _tags_ in angle brackets that surround the text, providing additional information on how the text should be interpreted. For instance, in the HTML text\n", "\n", "```html\n", "This is emphasized.\n", "```\n", "\n", "the word \"emphasized\" is enclosed in the HTML tags `` (start) and `` (end), meaning that it should be interpreted (and rendered) in an emphasized way – typically in italics. In your environment, the HTML text gets rendered as\n", "\n", "> This is emphasized.\n", "\n", "There's HTML tags for pretty much everything – text markup (bold text, strikethrough text), text structure (titles, lists), references (links) to other documents, and many more. These HTML tags shape the Web as we know it." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "However, with all the HTML markup, it may become difficult to actually access the _text_ that lies within. We'd like to implement a simple function that removes _HTML markup_ and converts it into text. If our input is\n", "\n", "```html\n", "Here's some strong argument.\n", "```\n", "the output should be\n", "\n", "> Here's some strong argument." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Here's a Python function which does exactly this. It takes a (HTML) string and returns the text without markup." ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:22.939140Z", "iopub.status.busy": "2023-11-12T12:39:22.939022Z", "iopub.status.idle": "2023-11-12T12:39:22.941614Z", "shell.execute_reply": "2023-11-12T12:39:22.941179Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def remove_html_markup(s): # type: ignore\n", " tag = False\n", " out = \"\"\n", "\n", " for c in s:\n", " if c == '<': # start of markup\n", " tag = True\n", " elif c == '>': # end of markup\n", " tag = False\n", " elif not tag:\n", " out = out + c\n", "\n", " return out" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "This function works, but not always. Before we start debugging things, let us first explore its code and how it works." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Understanding Python Programs\n", "\n", "If you're new to Python, you might first have to understand what the above code does. We very much recommend the [Python tutorial](https://docs.python.org/3/tutorial/) to get an idea on how Python works. The most important things for you to understand the above code are these three:\n", "\n", "1. Python structures programs through _indentation_, so the function and `for` bodies are defined by being indented.\n", "2. Python is _dynamically typed_, meaning that the type of variables like `c`, `tag`, or `out` is determined at run-time.\n", "3. Most of Python's syntactic features are inspired by other common languages, such as control structures (`while`, `if`, `for`), assignments (`=`), or comparisons (`==`, `!=`, `<`).\n", "\n", "With that, you can already understand what the above code does: `remove_html_markup()` takes a (HTML) string `s` and then iterates over the individual characters (`for c in s`). By default, these characters are added to the return string `out`. However, if `remove_html_markup()` finds a `<` character, it sets the `tag` flag, meaning that all further characters are ignored until a `>` character is found.\n", "\n", "In contrast to other languages, Python makes no difference between strings and characters – there are only strings. As in HTML, strings can be enclosed in single quotes (`'a'`) and in double quotes (`\"a\"`). This is useful if you want to specify a string that contains quotes, as in `'She said \"hello\", and then left'` or `\"The first character is a 'c'\"`" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Running a Function\n", "\n", "To find out whether `remove_html_markup()` works correctly, we can *test* it with a few values. For the string\n", "\n", "```html\n", "Here's some strong argument.\n", "```\n", "\n", "for instance, it produces the correct value:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:22.943720Z", "iopub.status.busy": "2023-11-12T12:39:22.943579Z", "iopub.status.idle": "2023-11-12T12:39:22.946056Z", "shell.execute_reply": "2023-11-12T12:39:22.945731Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "\"Here's some strong argument.\"" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "remove_html_markup(\"Here's some strong argument.\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Interacting with Notebooks\n", "\n", "If you are reading this in the interactive notebook, you can try out `remove_html_markup()` with other values as well. Click on the above cells with the invocation of `remove_html_markup()` and change the value – say, to `remove_html_markup(\"foo\")`. Press Shift+Enter (or click on the play symbol) to execute it and see the result. If you get an error message, go to the above cell with the definition of `remove_html_markup()` and execute this first. You can also run _all_ cells at once; see the Notebook menu for details. (You can actually also change the text by clicking on it, and corect mistaks such as in this sentence.)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Executing a single cell does not execute other cells, so if your cell builds on a definition in another cell that you have not executed yet, you will get an error. You can select `Run all cells above` from the menu to ensure all definitions are set." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Also keep in mind that, unless overwritten, all definitions are kept across executions. Occasionally, it thus helps to _restart the kernel_ (i.e. start the Python interpreter from scratch) to get rid of older, superfluous definitions." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Testing a Function" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Since one can change not only invocations, but also definitions, we want to ensure that our function works properly now and in the future. To this end, we introduce tests through _assertions_ – a statement that fails if the given _check_ is false. The following assertion, for instance, checks that the above call to `remove_html_markup()` returns the correct value:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:22.947987Z", "iopub.status.busy": "2023-11-12T12:39:22.947857Z", "iopub.status.idle": "2023-11-12T12:39:22.949834Z", "shell.execute_reply": "2023-11-12T12:39:22.949557Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "assert remove_html_markup(\"Here's some strong argument.\") == \\\n", " \"Here's some strong argument.\"" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "If you change the code of `remove_html_markup()` such that the above assertion fails, you will have introduced a bug." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Oops! A Bug!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "As nice and simple as `remove_html_markup()` is, it is buggy. Some HTML markup is not properly stripped away. Consider this HTML tag:\n", "\n", "```html\n", "\">\n", "```\n", "\n", "This would render as an input field in a form:\n", "\n", "> \">\n", "\n", "If we feed this string into `remove_html_markup()`, we would expect an empty string as the result. Instead, this is what we get:" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:22.951590Z", "iopub.status.busy": "2023-11-12T12:39:22.951458Z", "iopub.status.idle": "2023-11-12T12:39:22.953850Z", "shell.execute_reply": "2023-11-12T12:39:22.953556Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "'\"'" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "remove_html_markup('\">')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Every time we encounter a bug, this means that our earlier tests have failed. We thus need to introduce another test that documents not only how the bug came to be, but also the result we actually expected." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The assertion we write now fails with an error message. (The `ExpectError` magic ensures we see the error message, but the rest of the notebook is still executed.)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:22.955693Z", "iopub.status.busy": "2023-11-12T12:39:22.955554Z", "iopub.status.idle": "2023-11-12T12:39:22.985660Z", "shell.execute_reply": "2023-11-12T12:39:22.985237Z" }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from ExpectError import ExpectError" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:22.987963Z", "iopub.status.busy": "2023-11-12T12:39:22.987766Z", "iopub.status.idle": "2023-11-12T12:39:22.990343Z", "shell.execute_reply": "2023-11-12T12:39:22.989894Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_20417/145241764.py\", line 2, in \n", " assert remove_html_markup('\">') == \"\"\n", "AssertionError (expected)\n" ] } ], "source": [ "with ExpectError():\n", " assert remove_html_markup('\">') == \"\"" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "With this, we now have our task: _Fix the failure as above._" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Visualizing Code\n", "\n", "To properly understand what is going on here, it helps drawing a diagram on how `remove_html_markup()` works. Technically, `remove_html_markup()` implements a _state machine_ with two states `tag` and `¬ tag`. We change between these states depending on the characters we process. This is visualized in the following diagram:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:22.992722Z", "iopub.status.busy": "2023-11-12T12:39:22.992492Z", "iopub.status.idle": "2023-11-12T12:39:23.016568Z", "shell.execute_reply": "2023-11-12T12:39:23.015700Z" }, "ipub": { "ignore": true }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from graphviz import Digraph, nohtml" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.019504Z", "iopub.status.busy": "2023-11-12T12:39:23.019140Z", "iopub.status.idle": "2023-11-12T12:39:23.021388Z", "shell.execute_reply": "2023-11-12T12:39:23.020921Z" }, "ipub": { "ignore": true }, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from IPython.display import display" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.023960Z", "iopub.status.busy": "2023-11-12T12:39:23.023701Z", "iopub.status.idle": "2023-11-12T12:39:23.026299Z", "shell.execute_reply": "2023-11-12T12:39:23.025836Z" }, "ipub": { "ignore": true }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "# ignore\n", "PASS = \"✔\"\n", "FAIL = \"✘\"\n", "\n", "PASS_COLOR = 'darkgreen' # '#006400' # darkgreen\n", "FAIL_COLOR = 'red4' # '#8B0000' # darkred\n", "\n", "STEP_COLOR = 'peachpuff'\n", "FONT_NAME = 'Raleway'" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.028605Z", "iopub.status.busy": "2023-11-12T12:39:23.028430Z", "iopub.status.idle": "2023-11-12T12:39:23.031164Z", "shell.execute_reply": "2023-11-12T12:39:23.030688Z" }, "ipub": { "ignore": true }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "# ignore\n", "def graph(comment: str =\"default\") -> Digraph:\n", " return Digraph(name='', comment=comment, graph_attr={'rankdir': 'LR'},\n", " node_attr={'style': 'filled',\n", " 'fillcolor': STEP_COLOR,\n", " 'fontname': FONT_NAME},\n", " edge_attr={'fontname': FONT_NAME})" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.033231Z", "iopub.status.busy": "2023-11-12T12:39:23.033100Z", "iopub.status.idle": "2023-11-12T12:39:23.035620Z", "shell.execute_reply": "2023-11-12T12:39:23.035235Z" }, "ipub": { "ignore": true }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "# ignore\n", "state_machine = graph()\n", "state_machine.node('Start', )\n", "state_machine.edge('Start', '¬ tag')\n", "state_machine.edge('¬ tag', '¬ tag', label=\" ¬ '<'\\\\nadd character\")\n", "state_machine.edge('¬ tag', 'tag', label=\"'<'\")\n", "state_machine.edge('tag', '¬ tag', label=\"'>'\")\n", "state_machine.edge('tag', 'tag', label=\"¬ '>'\")" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.037500Z", "iopub.status.busy": "2023-11-12T12:39:23.037349Z", "iopub.status.idle": "2023-11-12T12:39:23.477533Z", "shell.execute_reply": "2023-11-12T12:39:23.477175Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "Start\n", "\n", "Start\n", "\n", "\n", "\n", "¬ tag\n", "\n", "¬ tag\n", "\n", "\n", "\n", "Start->¬ tag\n", "\n", "\n", "\n", "\n", "\n", "¬ tag->¬ tag\n", "\n", "\n", " ¬ '<'\n", "add character\n", "\n", "\n", "\n", "tag\n", "\n", "tag\n", "\n", "\n", "\n", "¬ tag->tag\n", "\n", "\n", "'<'\n", "\n", "\n", "\n", "tag->¬ tag\n", "\n", "\n", "'>'\n", "\n", "\n", "\n", "tag->tag\n", "\n", "\n", "¬ '>'\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# ignore\n", "display(state_machine)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "You see that we start in the non-tag state (`¬ tag`). Here, for every character that is not `'<'`, we add the character and stay in the same state. When we read a `'<'`, though, we end in the tag state (`tag`) and stay in that state (skipping characters) until we find a closing `'>'` character." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## A First Fix\n", "\n", "We will now iteratively try to find a correct solution to our bug. On the way we will come up with different _interim solutions_ that bring us closer and closer to the perfect code. Of course, we could come up with a near-perfect solution right away, but each of these interim solutions illustrate some techniques we can use during debugging." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Let us look at the above state machine, and process through our input:\n", "\n", "```html\n", "\">\n", "```" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "So what you can see is: We are interpreting the `'>'` of `\"\"` as the closing of the tag. However, this is a quoted string, so the `'>'` should be interpreted as a regular character, not as markup. This is an example of _missing functionality:_ We do not handle quoted characters correctly. We haven't claimed yet to take care of all functionality, so we still need to extend our code." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "So we extend the whole thing. We set up a special \"quote\" state which processes quoted inputs in tags until the end of the quoted string is reached. This is how the state machine looks like:" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.479643Z", "iopub.status.busy": "2023-11-12T12:39:23.479528Z", "iopub.status.idle": "2023-11-12T12:39:23.482356Z", "shell.execute_reply": "2023-11-12T12:39:23.482070Z" }, "ipub": { "ignore": true }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "# ignore\n", "state_machine = graph()\n", "state_machine.node('Start')\n", "state_machine.edge('Start', '¬ quote\\\\n¬ tag')\n", "state_machine.edge('¬ quote\\\\n¬ tag', '¬ quote\\\\n¬ tag',\n", " label=\"¬ '<'\\\\nadd character\")\n", "state_machine.edge('¬ quote\\\\n¬ tag', '¬ quote\\\\ntag', label=\"'<'\")\n", "state_machine.edge('¬ quote\\\\ntag', 'quote\\\\ntag', label=\"'\\\"'\")\n", "state_machine.edge('¬ quote\\\\ntag', '¬ quote\\\\ntag', label=\"¬ '\\\"' ∧ ¬ '>'\")\n", "state_machine.edge('quote\\\\ntag', 'quote\\\\ntag', label=\"¬ '\\\"'\")\n", "state_machine.edge('quote\\\\ntag', '¬ quote\\\\ntag', label=\"'\\\"'\")\n", "state_machine.edge('¬ quote\\\\ntag', '¬ quote\\\\n¬ tag', label=\"'>'\")" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.483767Z", "iopub.status.busy": "2023-11-12T12:39:23.483662Z", "iopub.status.idle": "2023-11-12T12:39:23.938826Z", "shell.execute_reply": "2023-11-12T12:39:23.938333Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "Start\n", "\n", "Start\n", "\n", "\n", "\n", "¬ quote\\n¬ tag\n", "\n", "¬ quote\n", "¬ tag\n", "\n", "\n", "\n", "Start->¬ quote\\n¬ tag\n", "\n", "\n", "\n", "\n", "\n", "¬ quote\\n¬ tag->¬ quote\\n¬ tag\n", "\n", "\n", "¬ '<'\n", "add character\n", "\n", "\n", "\n", "¬ quote\\ntag\n", "\n", "¬ quote\n", "tag\n", "\n", "\n", "\n", "¬ quote\\n¬ tag->¬ quote\\ntag\n", "\n", "\n", "'<'\n", "\n", "\n", "\n", "¬ quote\\ntag->¬ quote\\n¬ tag\n", "\n", "\n", "'>'\n", "\n", "\n", "\n", "¬ quote\\ntag->¬ quote\\ntag\n", "\n", "\n", "¬ '"' ∧ ¬ '>'\n", "\n", "\n", "\n", "quote\\ntag\n", "\n", "quote\n", "tag\n", "\n", "\n", "\n", "¬ quote\\ntag->quote\\ntag\n", "\n", "\n", "'"'\n", "\n", "\n", "\n", "quote\\ntag->¬ quote\\ntag\n", "\n", "\n", "'"'\n", "\n", "\n", "\n", "quote\\ntag->quote\\ntag\n", "\n", "\n", "¬ '"'\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# ignore\n", "display(state_machine)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "This is a bit more complex already. Proceeding from left to right, we first have the state `¬ quote ∧ ¬ tag`, which is our \"standard\" state for text. If we encounter a `'<'`, we again switch to the \"tagged\" state `¬ quote ∧ tag`. In this state, however (and only in this state), if we encounter a quotation mark, we switch to the \"quotation\" state `quote ∧ tag`, in which we remain until we see another quotation mark indicating the end of the string – and then continue in the \"tagged\" state `¬ quote ∧ tag` until we see the end of the string." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Things get even more complicated as HTML allows both single and double quotation characters. Here's a revised implementation of `remove_html_markup()` that takes the above states into account:" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.941096Z", "iopub.status.busy": "2023-11-12T12:39:23.940950Z", "iopub.status.idle": "2023-11-12T12:39:23.943554Z", "shell.execute_reply": "2023-11-12T12:39:23.943272Z" }, "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": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Now, our previous input works well:" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.945271Z", "iopub.status.busy": "2023-11-12T12:39:23.945150Z", "iopub.status.idle": "2023-11-12T12:39:23.947562Z", "shell.execute_reply": "2023-11-12T12:39:23.947286Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "''" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "remove_html_markup('\">')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "and our earlier tests also pass:" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.949211Z", "iopub.status.busy": "2023-11-12T12:39:23.949099Z", "iopub.status.idle": "2023-11-12T12:39:23.950780Z", "shell.execute_reply": "2023-11-12T12:39:23.950544Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "assert remove_html_markup(\"Here's some strong argument.\") == \\\n", " \"Here's some strong argument.\"" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.952184Z", "iopub.status.busy": "2023-11-12T12:39:23.952095Z", "iopub.status.idle": "2023-11-12T12:39:23.953986Z", "shell.execute_reply": "2023-11-12T12:39:23.953689Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "assert remove_html_markup('\">') == \"\"" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "However, the above code still has a bug. In two of these inputs, HTML markup is still not properly stripped:\n", "\n", "```html\n", "foo\n", "\"foo\"\n", "\"foo\"\n", "<\"b\">foo\n", "```\n", "\n", "Can you guess which ones these are?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Again, a simple assertion will reveal the culprits:" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.955481Z", "iopub.status.busy": "2023-11-12T12:39:23.955376Z", "iopub.status.idle": "2023-11-12T12:39:23.957192Z", "shell.execute_reply": "2023-11-12T12:39:23.956921Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "with ExpectError():\n", " assert remove_html_markup('foo') == 'foo'" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.958643Z", "iopub.status.busy": "2023-11-12T12:39:23.958535Z", "iopub.status.idle": "2023-11-12T12:39:23.960339Z", "shell.execute_reply": "2023-11-12T12:39:23.960073Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_20417/4031927246.py\", line 2, in \n", " assert remove_html_markup('\"foo\"') == '\"foo\"'\n", "AssertionError (expected)\n" ] } ], "source": [ "with ExpectError():\n", " assert remove_html_markup('\"foo\"') == '\"foo\"'" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.961846Z", "iopub.status.busy": "2023-11-12T12:39:23.961746Z", "iopub.status.idle": "2023-11-12T12:39:23.963465Z", "shell.execute_reply": "2023-11-12T12:39:23.963210Z" }, "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_20417/242211734.py\", line 2, in \n", " assert remove_html_markup('\"foo\"') == '\"foo\"'\n", "AssertionError (expected)\n" ] } ], "source": [ "with ExpectError():\n", " assert remove_html_markup('\"foo\"') == '\"foo\"'" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.964895Z", "iopub.status.busy": "2023-11-12T12:39:23.964795Z", "iopub.status.idle": "2023-11-12T12:39:23.966529Z", "shell.execute_reply": "2023-11-12T12:39:23.966262Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "with ExpectError():\n", " assert remove_html_markup('<\"b\">foo') == 'foo'" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "So, unfortunately, we're not done yet – our function still has errors." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## The Devil's Guide to Debugging\n", "\n", "Let us now discuss a couple of methods that do _not_ work well for debugging. (These \"devil's suggestions\" are adapted from the 1993 book \"Code Complete\" from Steve McConnell.)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Printf Debugging\n", "\n", "When I was a student, I never got any formal training in debugging, so I had to figure this out for myself. What I learned was how to use _debugging output_; in Python, this would be the `print()` function. For instance, I would go and scatter `print()` calls everywhere:" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.968032Z", "iopub.status.busy": "2023-11-12T12:39:23.967926Z", "iopub.status.idle": "2023-11-12T12:39:23.970437Z", "shell.execute_reply": "2023-11-12T12:39:23.970113Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def remove_html_markup_with_print(s): # type: ignore\n", " tag = False\n", " quote = False\n", " out = \"\"\n", "\n", " for c in s:\n", " print(\"c =\", repr(c), \"tag =\", tag, \"quote =\", quote)\n", "\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": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "This way of inspecting executions is commonly called \"Printf debugging\", after the C `printf()` function. Then, running this would allow me to see what's going on in my code:" ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.971989Z", "iopub.status.busy": "2023-11-12T12:39:23.971870Z", "iopub.status.idle": "2023-11-12T12:39:23.975533Z", "shell.execute_reply": "2023-11-12T12:39:23.975178Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "c = '<' tag = False quote = False\n", "c = 'b' tag = True quote = False\n", "c = '>' tag = True quote = False\n", "c = '\"' tag = False quote = False\n", "c = 'f' tag = False quote = True\n", "c = 'o' tag = False quote = True\n", "c = 'o' tag = False quote = True\n", "c = '\"' tag = False quote = True\n", "c = '<' tag = False quote = False\n", "c = '/' tag = True quote = False\n", "c = 'b' tag = True quote = False\n", "c = '>' tag = True quote = False\n" ] }, { "data": { "text/plain": [ "'foo'" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "remove_html_markup_with_print('\"foo\"')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Yes, one sees what is going on – but this is horribly inefficient! Think of a 1,000-character input – you'd have to go through 1,000 lines of logs. It may help you, but it's a total time waster. Plus, you have to enter these statements, remove them again... it's a maintenance nightmare." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "(You may even forget printf's in your code, creating a security problem: Mac OS X versions 10.7 to 10.7.3 would log the password in clear because someone had forgotten to turn off debugging output.)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Debugging into Existence" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "I would also try to _debug the program into existence._ Just change things until they work. Let me see: If I remove the conditions \"and not quote\" from the program, it would actually work again:" ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.977324Z", "iopub.status.busy": "2023-11-12T12:39:23.977237Z", "iopub.status.idle": "2023-11-12T12:39:23.979392Z", "shell.execute_reply": "2023-11-12T12:39:23.979145Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def remove_html_markup_without_quotes(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": 28, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.980960Z", "iopub.status.busy": "2023-11-12T12:39:23.980877Z", "iopub.status.idle": "2023-11-12T12:39:23.982486Z", "shell.execute_reply": "2023-11-12T12:39:23.982251Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "assert remove_html_markup_without_quotes('foo') == 'foo'" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Cool! Unfortunately, the function still fails on the other input:" ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.984198Z", "iopub.status.busy": "2023-11-12T12:39:23.984105Z", "iopub.status.idle": "2023-11-12T12:39:23.986034Z", "shell.execute_reply": "2023-11-12T12:39:23.985739Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_20417/3864559921.py\", line 2, in \n", " assert remove_html_markup_without_quotes('\"foo\"') == '\"foo\"'\n", "AssertionError (expected)\n" ] } ], "source": [ "with ExpectError():\n", " assert remove_html_markup_without_quotes('\"foo\"') == '\"foo\"'" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "So, maybe we can change things again, such that both work? And maybe the other tests we had earlier won't fail? Let's just continue to change things randomly again and again and again." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Oh, and of course, I would never back up earlier versions such that I would be able to keep track of what has changed and when.\n", "Especially keep in mind that our tests will never cover all corner cases. Randomly patching code will just lead to harder to find bugs." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Use the Most Obvious Fix" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "My favorite: Use the most obvious fix. This means that you're fixing the symptom, not the problem. In our case, this would be something like:" ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.988193Z", "iopub.status.busy": "2023-11-12T12:39:23.987900Z", "iopub.status.idle": "2023-11-12T12:39:23.989850Z", "shell.execute_reply": "2023-11-12T12:39:23.989591Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "def remove_html_markup_fixed(s): # type: ignore\n", " if s == '\"foo\"':\n", " return '\"foo\"'\n", " ..." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Miracle! Our earlier failing assertion now works! Now we can do the same for the other failing test, too, and we're done.\n", "(Rumor has it that some programmers use this technique to get their tests to pass...)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Things to do Instead\n", "\n", "As with any devil's guide, you get an idea of how to do things by doing the _opposite._ What this means is:\n", "\n", "1. Understand the code\n", "2. Fix the problem, not the symptom\n", "3. Proceed systematically\n", "\n", "which is what we will apply for the rest of this chapter." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## From Defect to Failure\n", "\n", "To understand how to systematically debug a program, we first have to understand _how failures come to be._ The typical debugging situation looks like this:\n", "\n", "* We have a program (execution), taking some input and producing some output.\n", "* The output is in *error* (✘), meaning an unwanted and unintended deviation from what is correct, right, or true.\n", "* The input, in contrast, is assumed to be correct (✔) – that is, it should be properly processed by the program in question. \n", "\n", "If the input is incorrect, we wouldn't normally be searching for the bug in our program, but in whatever produced its input. If the input is under control of a third party, though (which typically is the case for _system inputs_), your program must check its correctness and reject it if it is incorrect. Once your program accepts a system input as valid, it must be properly processed by the program in question.\n", "\n", "Hence, the (very simple) situation we're having can be shown as:" ] }, { "cell_type": "code", "execution_count": 31, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.991670Z", "iopub.status.busy": "2023-11-12T12:39:23.991504Z", "iopub.status.idle": "2023-11-12T12:39:23.993121Z", "shell.execute_reply": "2023-11-12T12:39:23.992817Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "# ignore\n", "from typing import List, Optional" ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:23.994851Z", "iopub.status.busy": "2023-11-12T12:39:23.994665Z", "iopub.status.idle": "2023-11-12T12:39:24.000291Z", "shell.execute_reply": "2023-11-12T12:39:24.000009Z" }, "ipub": { "ignore": true }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "# ignore\n", "def execution_diagram(show_steps: bool = True, variables: List[str] = [],\n", " steps: int = 3, error_step: int = 666,\n", " until: int = 666, fault_path: List[str] = []) -> Digraph:\n", " dot = graph()\n", "\n", " dot.node('input', shape='none', fillcolor='white', label=f\"Input {PASS}\",\n", " fontcolor=PASS_COLOR)\n", " last_outgoing_states = ['input']\n", "\n", " for step in range(1, min(steps + 1, until)):\n", "\n", " step_color: Optional[str]\n", " if step == error_step:\n", " step_label = f'Step {step} {FAIL}'\n", " step_color = FAIL_COLOR\n", " else:\n", " step_label = f'Step {step}'\n", " step_color = None\n", "\n", " if step >= error_step:\n", " state_label = f'State {step} {FAIL}'\n", " state_color = FAIL_COLOR\n", " else:\n", " state_label = f'State {step} {PASS}'\n", " state_color = PASS_COLOR\n", "\n", " state_name = f's{step}'\n", " outgoing_states = []\n", " incoming_states = []\n", "\n", " if not variables:\n", " dot.node(name=state_name, shape='box',\n", " label=state_label, color=state_color,\n", " fontcolor=state_color)\n", " else:\n", " var_labels = []\n", " for v in variables:\n", " vpath = f's{step}:{v}'\n", " if vpath in fault_path:\n", " var_label = f'<{v}>{v} ✘'\n", " outgoing_states.append(vpath)\n", " incoming_states.append(vpath)\n", " else:\n", " var_label = f'<{v}>{v}'\n", " var_labels.append(var_label)\n", " record_string = \" | \".join(var_labels)\n", " dot.node(name=state_name, shape='record',\n", " label=nohtml(record_string), color=state_color,\n", " fontcolor=state_color)\n", "\n", " if not outgoing_states:\n", " outgoing_states = [state_name]\n", " if not incoming_states:\n", " incoming_states = [state_name]\n", "\n", " for outgoing_state in last_outgoing_states:\n", " for incoming_state in incoming_states:\n", " if show_steps:\n", " dot.edge(outgoing_state, incoming_state,\n", " label=step_label, fontcolor=step_color)\n", " else:\n", " dot.edge(outgoing_state, incoming_state)\n", "\n", " last_outgoing_states = outgoing_states\n", "\n", " if until > steps + 1:\n", " # Show output\n", " if error_step > steps:\n", " dot.node('output', shape='none', fillcolor='white',\n", " label=f\"Output {PASS}\", fontcolor=PASS_COLOR)\n", " else:\n", " dot.node('output', shape='none', fillcolor='white',\n", " label=f\"Output {FAIL}\", fontcolor=FAIL_COLOR)\n", "\n", " for outgoing_state in last_outgoing_states:\n", " label = \"Execution\" if steps == 0 else None\n", " dot.edge(outgoing_state, 'output', label=label)\n", "\n", " display(dot)" ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:24.001928Z", "iopub.status.busy": "2023-11-12T12:39:24.001825Z", "iopub.status.idle": "2023-11-12T12:39:24.429627Z", "shell.execute_reply": "2023-11-12T12:39:24.429212Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "input\n", "\n", "Input ✔\n", "\n", "\n", "\n", "output\n", "\n", "Output ✘\n", "\n", "\n", "\n", "input->output\n", "\n", "\n", "Execution\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# ignore\n", "execution_diagram(show_steps=False, steps=0, error_step=0)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "This situation we see above is what we call a *failure*: An externally visible _error_ in the program behavior, with the error again being an unwanted and unintended deviation from what is correct, right, or true." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "How does this failure come to be? The execution we see above breaks down into several program _states_, one after the other." ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:24.431580Z", "iopub.status.busy": "2023-11-12T12:39:24.431441Z", "iopub.status.idle": "2023-11-12T12:39:26.546705Z", "shell.execute_reply": "2023-11-12T12:39:26.546229Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "input\n", "\n", "Input ✔\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "input\n", "\n", "Input ✔\n", "\n", "\n", "\n", "s1\n", "\n", "State 1 ✔\n", "\n", "\n", "\n", "input->s1\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "input\n", "\n", "Input ✔\n", "\n", "\n", "\n", "s1\n", "\n", "State 1 ✔\n", "\n", "\n", "\n", "input->s1\n", "\n", "\n", "\n", "\n", "\n", "s2\n", "\n", "State 2 ✘\n", "\n", "\n", "\n", "s1->s2\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "input\n", "\n", "Input ✔\n", "\n", "\n", "\n", "s1\n", "\n", "State 1 ✔\n", "\n", "\n", "\n", "input->s1\n", "\n", "\n", "\n", "\n", "\n", "s2\n", "\n", "State 2 ✘\n", "\n", "\n", "\n", "s1->s2\n", "\n", "\n", "\n", "\n", "\n", "s3\n", "\n", "State 3 ✘\n", "\n", "\n", "\n", "s2->s3\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "input\n", "\n", "Input ✔\n", "\n", "\n", "\n", "s1\n", "\n", "State 1 ✔\n", "\n", "\n", "\n", "input->s1\n", "\n", "\n", "\n", "\n", "\n", "s2\n", "\n", "State 2 ✘\n", "\n", "\n", "\n", "s1->s2\n", "\n", "\n", "\n", "\n", "\n", "s3\n", "\n", "State 3 ✘\n", "\n", "\n", "\n", "s2->s3\n", "\n", "\n", "\n", "\n", "\n", "output\n", "\n", "Output ✘\n", "\n", "\n", "\n", "s3->output\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# ignore\n", "for until in range(1, 6):\n", " execution_diagram(show_steps=False, until=until, error_step=2)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Initially, the program state is still correct (✔). However, at some point in the execution, the state gets an _error_, also known as a *fault*. This fault – again an unwanted and unintended deviation from what is correct, right, or true – then propagates along the execution, until it becomes externally visible as a _failure_.\n", "(In reality, there are many, many more states than just this, but these would not fit in a diagram.)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "How does a fault come to be? Each of these program states is produced by a _step_ in the program code. These steps take a state as input and produce another state as output. Technically speaking, the program inputs and outputs are also parts of the program state, so the input flows into the first step, and the output is the state produced by the last step." ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:26.548629Z", "iopub.status.busy": "2023-11-12T12:39:26.548495Z", "iopub.status.idle": "2023-11-12T12:39:28.696356Z", "shell.execute_reply": "2023-11-12T12:39:28.695959Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "input\n", "\n", "Input ✔\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "input\n", "\n", "Input ✔\n", "\n", "\n", "\n", "s1\n", "\n", "State 1 ✔\n", "\n", "\n", "\n", "input->s1\n", "\n", "\n", "Step 1\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "input\n", "\n", "Input ✔\n", "\n", "\n", "\n", "s1\n", "\n", "State 1 ✔\n", "\n", "\n", "\n", "input->s1\n", "\n", "\n", "Step 1\n", "\n", "\n", "\n", "s2\n", "\n", "State 2 ✘\n", "\n", "\n", "\n", "s1->s2\n", "\n", "\n", "Step 2 ✘\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "input\n", "\n", "Input ✔\n", "\n", "\n", "\n", "s1\n", "\n", "State 1 ✔\n", "\n", "\n", "\n", "input->s1\n", "\n", "\n", "Step 1\n", "\n", "\n", "\n", "s2\n", "\n", "State 2 ✘\n", "\n", "\n", "\n", "s1->s2\n", "\n", "\n", "Step 2 ✘\n", "\n", "\n", "\n", "s3\n", "\n", "State 3 ✘\n", "\n", "\n", "\n", "s2->s3\n", "\n", "\n", "Step 3\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "input\n", "\n", "Input ✔\n", "\n", "\n", "\n", "s1\n", "\n", "State 1 ✔\n", "\n", "\n", "\n", "input->s1\n", "\n", "\n", "Step 1\n", "\n", "\n", "\n", "s2\n", "\n", "State 2 ✘\n", "\n", "\n", "\n", "s1->s2\n", "\n", "\n", "Step 2 ✘\n", "\n", "\n", "\n", "s3\n", "\n", "State 3 ✘\n", "\n", "\n", "\n", "s2->s3\n", "\n", "\n", "Step 3\n", "\n", "\n", "\n", "output\n", "\n", "Output ✘\n", "\n", "\n", "\n", "s3->output\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# ignore\n", "for until in range(1, 6):\n", " execution_diagram(show_steps=True, until=until, error_step=2)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Now, in the diagram above, Step 2 gets a _correct_ state as input and produces a _faulty_ state as output. The produced fault then propagates across more steps to finally become visible as a _failure_." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The goal of debugging thus is to _search_ for the step in which the state first becomes faulty. The _code_ associated with this step is again an error – an unwanted and unintended deviation from what is correct, right, or true – and is called a _defect_. This is what we have to find – and to fix." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Sounds easy, right? Unfortunately, things are not that easy, and that has something to do with the program state. Let us assume our state consists of three variables, `var1` to `var3`, and that Step 2 produces a fault in `var2`. This fault then propagates to the output:" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:28.698246Z", "iopub.status.busy": "2023-11-12T12:39:28.698116Z", "iopub.status.idle": "2023-11-12T12:39:30.836374Z", "shell.execute_reply": "2023-11-12T12:39:30.836029Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "input\n", "\n", "Input ✔\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "input\n", "\n", "Input ✔\n", "\n", "\n", "\n", "s1\n", "\n", "var1\n", "\n", "var2\n", "\n", "var3\n", "\n", "\n", "\n", "input->s1\n", "\n", "\n", "Step 1\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "input\n", "\n", "Input ✔\n", "\n", "\n", "\n", "s1\n", "\n", "var1\n", "\n", "var2\n", "\n", "var3\n", "\n", "\n", "\n", "input->s1\n", "\n", "\n", "Step 1\n", "\n", "\n", "\n", "s2\n", "\n", "var1\n", "\n", "var2 ✘\n", "\n", "var3\n", "\n", "\n", "\n", "s1->s2:var2\n", "\n", "\n", "Step 2 ✘\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "input\n", "\n", "Input ✔\n", "\n", "\n", "\n", "s1\n", "\n", "var1\n", "\n", "var2\n", "\n", "var3\n", "\n", "\n", "\n", "input->s1\n", "\n", "\n", "Step 1\n", "\n", "\n", "\n", "s2\n", "\n", "var1\n", "\n", "var2 ✘\n", "\n", "var3\n", "\n", "\n", "\n", "s1->s2:var2\n", "\n", "\n", "Step 2 ✘\n", "\n", "\n", "\n", "s3\n", "\n", "var1\n", "\n", "var2 ✘\n", "\n", "var3\n", "\n", "\n", "\n", "s2:var2->s3:var2\n", "\n", "\n", "Step 3\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "input\n", "\n", "Input ✔\n", "\n", "\n", "\n", "s1\n", "\n", "var1\n", "\n", "var2\n", "\n", "var3\n", "\n", "\n", "\n", "input->s1\n", "\n", "\n", "Step 1\n", "\n", "\n", "\n", "s2\n", "\n", "var1\n", "\n", "var2 ✘\n", "\n", "var3\n", "\n", "\n", "\n", "s1->s2:var2\n", "\n", "\n", "Step 2 ✘\n", "\n", "\n", "\n", "s3\n", "\n", "var1\n", "\n", "var2 ✘\n", "\n", "var3\n", "\n", "\n", "\n", "s2:var2->s3:var2\n", "\n", "\n", "Step 3\n", "\n", "\n", "\n", "output\n", "\n", "Output ✘\n", "\n", "\n", "\n", "s3:var2->output\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# ignore\n", "for until in range(1, 6):\n", " execution_diagram(show_steps=True, variables=['var1', 'var2', 'var3'],\n", " error_step=2,\n", " until=until, fault_path=['s2:var2', 's3:var2'])" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The way these faults propagate is called a *cause-effect chain*:\n", "\n", "* The _defect_ in the code _causes_ a fault in the state when executed.\n", "* This _fault_ in the state then _propagates_ through further execution steps...\n", "* ... until it becomes visible as a _failure_.\n", "\n", "Even worse: in most cases the fault often expresses itself first in the control flow rather than the variable contents.\n", "Such a deviation from a normal execution is in general even harder to find." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Since the code was originally written by a human, any defect can be related to some original _mistake_ the programmer made. This gives us a number of terms that all are more precise than the general \"error\" or the colloquial \"bug\":\n", "\n", "* A _mistake_ is a human act or decision resulting in an error.\n", "* A _defect_ is an error in the program code. Also called *bug*.\n", "* A _fault_ is an error in the program state. Also called *infection*.\n", "* A _failure_ is an externally visible error in the program behavior. Also called *malfunction*.\n", "\n", "The cause-effect chain of events is thus\n", "\n", "* Mistake → Defect → Fault → ... → Fault → Failure\n", "\n", "Note that not every defect also causes a failure, which is despite all testing, there can still be defects in the code looming around until the right conditions are met to trigger them. On the other hand, though, _every failure can be traced back to the defect that causes it_. Our job is to break the cause-effect chain." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## From Failure to Defect\n", "\n", "To find a defect from a failure, we _trace back_ the faults along their _propagation_ – that is, we find out which faults in the earlier state have caused the later faults. We start from the very end of the execution and then gradually progress backwards in time, examining fault after fault until we find a _transition_ from a correct state to a faulty state – that is, a\n", "step in which a correct state comes in and a faulty state comes out. At this point, we have found the origin of the failure – and the defect that causes it." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "What sounds like a straight-forward strategy, unfortunately, doesn't always work this way in practice. That is because of the following problems of debugging:\n", "\n", "* First, program states are actually _large_, encompassing dozens to thousands of variables, possibly even more. If you have to search all of these manually and check them for faults, you will spend a lot of time for a single state.\n", "\n", "* Second, you do not always know _whether a state is correct or not._ While most programs have some form of specification for their inputs and outputs, these do not necessarily exist for intermediate results. If one had a specification that could check each state for correctness (possibly even automatically), debugging would be trivial. Unfortunately, it is not, and that's partly due to the lack of specifications.\n", "\n", "* Third, executions typically do not come in a handful of steps, as in the diagrams above; instead, they can easily encompass _thousands to millions of steps._ This means that you will have to examine not just one state, but several, making the problem much worse.\n", "\n", "To make your search efficient, you thus have to _focus_ your search – starting with most likely causes and gradually progressing to the less probable causes. This is what we call a _debugging strategy_. Intermediate assertions of the program state also come in handy, as they make the cause-effect chain smaller." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## The Scientific Method\n", "\n", "Now that we know how failures come to be, let's look into how to systematically find their causes. What we need is a _strategy_ that helps us search for how and when the failure comes to be. For this, we use a process called the *scientific method*." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "When we are debugging a program, we are trying to find the causes of a given effect – very much like natural scientists try to understand why things in nature are as they are and how they come to be. Over thousands of years, scientists have conducted _observations_ and _experiments_ to come to an understanding of how our world works. The process by which experimental scientists operate has been coined \"The scientific method\". This is how it works:" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "1. Formulate a _question_, as in \"Why does this apple fall down?\".\n", "2. Invent a _hypothesis_ based on knowledge obtained while formulating the question, that may explain the observed behavior. \n", "3. Determining the logical consequences of the hypothesis, formulate a _prediction_ that can _support_ or _refute_ the hypothesis. Ideally, the prediction would distinguish the hypothesis from likely alternatives.\n", "4. _Test_ the prediction (and thus the hypothesis) in an _experiment_. If the prediction holds, confidence in the hypothesis increases; otherwise, it decreases.\n", "5. Repeat Steps 2–4 until there are no discrepancies between hypothesis and predictions and/or observations." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "At this point, your hypothesis may be named a *theory* – that is, a predictive and comprehensive description of some aspect of the natural world. The gravitational theory, for instance, predicts very well how the moon revolves around the earth, and how the earth revolves around the sun. Our debugging problems are of a slightly lesser scale – we'd like a theory of how our failure came to be – but the process is pretty much the same." ] }, { "cell_type": "code", "execution_count": 37, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:30.838418Z", "iopub.status.busy": "2023-11-12T12:39:30.838289Z", "iopub.status.idle": "2023-11-12T12:39:30.842365Z", "shell.execute_reply": "2023-11-12T12:39:30.841874Z" }, "ipub": { "ignore": true }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "# ignore\n", "dot = graph()\n", "\n", "dot.node('Hypothesis')\n", "dot.node('Observation')\n", "dot.node('Prediction')\n", "dot.node('Experiment')\n", "\n", "dot.edge('Hypothesis', 'Observation',\n", " label=\"is supported:
Refine it>\",\n", " dir='back')\n", "dot.edge('Hypothesis', 'Prediction')\n", "\n", "dot.node('Problem Report', shape='none', fillcolor='white')\n", "dot.edge('Problem Report', 'Hypothesis')\n", "\n", "dot.node('Code', shape='none', fillcolor='white')\n", "dot.edge('Code', 'Hypothesis')\n", "\n", "dot.node('Runs', shape='none', fillcolor='white')\n", "dot.edge('Runs', 'Hypothesis')\n", "\n", "dot.node('More Runs', shape='none', fillcolor='white')\n", "dot.edge('More Runs', 'Hypothesis')\n", "\n", "dot.edge('Prediction', 'Experiment')\n", "dot.edge('Experiment', 'Observation')\n", "dot.edge('Observation', 'Hypothesis',\n", " label=\"is rejected:
Seek alternative>\")" ] }, { "cell_type": "code", "execution_count": 38, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:30.844229Z", "iopub.status.busy": "2023-11-12T12:39:30.844122Z", "iopub.status.idle": "2023-11-12T12:39:31.290763Z", "shell.execute_reply": "2023-11-12T12:39:31.290414Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "Hypothesis\n", "\n", "Hypothesis\n", "\n", "\n", "\n", "Observation\n", "\n", "Observation\n", "\n", "\n", "\n", "Hypothesis->Observation\n", "\n", "\n", "Hypothesis\n", "is \n", "supported:\n", "Refine it\n", "\n", "\n", "\n", "Prediction\n", "\n", "Prediction\n", "\n", "\n", "\n", "Hypothesis->Prediction\n", "\n", "\n", "\n", "\n", "\n", "Observation->Hypothesis\n", "\n", "\n", "Hypothesis\n", "is \n", "rejected:\n", "Seek alternative\n", "\n", "\n", "\n", "Experiment\n", "\n", "Experiment\n", "\n", "\n", "\n", "Prediction->Experiment\n", "\n", "\n", "\n", "\n", "\n", "Experiment->Observation\n", "\n", "\n", "\n", "\n", "\n", "Problem Report\n", "\n", "Problem Report\n", "\n", "\n", "\n", "Problem Report->Hypothesis\n", "\n", "\n", "\n", "\n", "\n", "Code\n", "\n", "Code\n", "\n", "\n", "\n", "Code->Hypothesis\n", "\n", "\n", "\n", "\n", "\n", "Runs\n", "\n", "Runs\n", "\n", "\n", "\n", "Runs->Hypothesis\n", "\n", "\n", "\n", "\n", "\n", "More Runs\n", "\n", "More Runs\n", "\n", "\n", "\n", "More Runs->Hypothesis\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# ignore\n", "display(dot)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "In debugging, we proceed the very same way – indeed, we are treating bugs as if they were natural phenomena. This analogy may sound far-fetched, as programs are anything but natural. Nature, by definition, is not under our control. But bugs are _out of our control just as well._ Hence, the analogy is not that far-fetched – and we can apply the same techniques for debugging." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Finding a Hypothesis" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Let us apply the scientific method to our Python program which removes HTML tags. First of all, let us recall the problem – `remove_html_markup()` works for some inputs, but fails on others." ] }, { "cell_type": "code", "execution_count": 39, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.292714Z", "iopub.status.busy": "2023-11-12T12:39:31.292584Z", "iopub.status.idle": "2023-11-12T12:39:31.295166Z", "shell.execute_reply": "2023-11-12T12:39:31.294848Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 foo foo\n", "2 \"foo\" foo\n", "3 \"foo\" foo\n", "4 foo foo\n" ] } ], "source": [ "for i, html in enumerate(['foo',\n", " '\"foo\"',\n", " '\"foo\"',\n", " 'foo']):\n", " result = remove_html_markup(html)\n", " print(\"%-2d %-15s %s\" % (i + 1, html, result))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Input #1 and #4 work as expected, the others do not. We can write these down in a table, such that we can always look back at our previous results:\n", "\n", "|Input|Expectation|Output|Outcome|\n", "|-----|-----------|------|-------|\n", "|`foo`|`foo`|`foo`|✔|\n", "|`\"foo\"`|`\"foo\"`|`foo`|✘|\n", "|`\"foo\"`|`\"foo\"`|`foo`|✘|\n", "|`foo`|`foo`|`foo`|✔|\n" ] }, { "cell_type": "code", "execution_count": 40, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.296754Z", "iopub.status.busy": "2023-11-12T12:39:31.296643Z", "iopub.status.idle": "2023-11-12T12:39:31.301810Z", "shell.execute_reply": "2023-11-12T12:39:31.301419Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", "
\n", "

Quiz

\n", "

\n", "

From the difference between success and failure, we can already devise some observations about what is wrong with the output. Which of these can we turn into general hypotheses?
\n", "

\n", "

\n", "

\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", "
\n", "

\n", " \n", " \n", "
\n", " " ], "text/plain": [ "" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quiz(\"From the difference between success and failure,\"\n", " \" we can already devise some observations about \"\n", " \" what is wrong with the output.\"\n", " \" Which of these can we turn into general hypotheses?\",\n", " [\n", " \"Double quotes (`\\\"`) are stripped from the tagged input.\",\n", " \"Tags in double quotes are not stripped.\",\n", " \"The tag `<>` is always stripped from the input.\",\n", " \"Four-letter words are stripped.\"\n", " ], '[298 % 33, 1234 % 616]')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Testing a Hypothesis\n", "\n", "The hypotheses that remain are:\n", "\n", "1. Double quotes are stripped from the tagged input.\n", "2. Tags in double quotes are not stripped." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "These may be two separate issues, but chances are they are tied to each other. Let's focus on 1., because it is simpler. Does it hold for all inputs, even untagged ones? Our hypothesis becomes\n", "\n", "1. Double quotes are stripped from the ~~tagged~~ input." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Let's devise an experiment to validate this. If we feed the string\n", "```html\n", "\"foo\"\n", "```\n", "(including the double quotes) into `remove_html_markup()`, we should obtain\n", "```html\n", "\"foo\"\n", "```\n", "as result – that is, the output should be the unchanged input. However, if our hypothesis 1. is correct, we should obtain\n", "```html\n", "foo\n", "```\n", "as result – that is, \"Double quotes are stripped from the input\" as predicted by the hypothesis." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "We can very easily test this hypothesis:" ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.303637Z", "iopub.status.busy": "2023-11-12T12:39:31.303509Z", "iopub.status.idle": "2023-11-12T12:39:31.305745Z", "shell.execute_reply": "2023-11-12T12:39:31.305424Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "'foo'" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "remove_html_markup('\"foo\"')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Our hypothesis is confirmed! We can add this to our list of observations." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "|Input|Expectation|Output|Outcome|\n", "|-----|-----------|------|-------|\n", "|`foo`|`foo`|`foo`|✔|\n", "|`\"foo\"`|`\"foo\"`|`foo`|✘|\n", "|`\"foo\"`|`\"foo\"`|`foo`|✘|\n", "|`foo`|`foo`|`foo`|✔|\n", "|`\"foo\"`|`\"foo\"`|`foo`|✘|\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "You can try out the hypothesis with more inputs – and it remains valid. Any non-markup input that contains double quotes will have these stripped." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Where does that quote-stripping come from? This is where we need to explore the cause-effect chain. The only place in `remove_html_markup()` where quotes are handled is this line:\n", "\n", "```python\n", "elif c == '\"' or c == \"'\" and tag:\n", " quote = not quote\n", "```\n", "\n", "So, quotes should be removed only if `tag` is set. However, `tag` can be set only if the input contains a markup tag, which is not the case for a simple input like `\"foo\"`. Hence, what we observe is actually _impossible._ Yet, it happens." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Refining a Hypothesis\n", "\n", "Debugging is a game of falsifying assumptions. You assume the code works – it doesn't. You assume the `tag` flag cannot be set – yet it may be. What do we do? Again, we create a hypothesis:\n", "\n", "1. The error is due to `tag` being set." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "How do we know whether tag is being set? Let me introduce one of the most powerful debugging tools ever invented, the `assert` statement. The statement\n", "```python\n", "assert cond\n", "```\n", "evaluates the given condition `cond` and\n", "\n", "* if it holds: proceed as usual\n", "* if `cond` does not hold: throw an exception\n", "\n", "An `assert` statement _encodes our assumptions_ and as such, should never fail. If it does, well, then something is wrong.\n", "Furthermore, `assert` statements break the cause-effect chain into smaller pieces. The observable failure occurs earlier in\n", "the program execution and thus closer to the initial fault." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Using `assert`, we can check the value of `tag` all through the loop:" ] }, { "cell_type": "code", "execution_count": 42, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.307871Z", "iopub.status.busy": "2023-11-12T12:39:31.307740Z", "iopub.status.idle": "2023-11-12T12:39:31.310163Z", "shell.execute_reply": "2023-11-12T12:39:31.309906Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def remove_html_markup_with_tag_assert(s): # type: ignore\n", " tag = False\n", " quote = False\n", " out = \"\"\n", "\n", " for c in s:\n", " assert not tag # <=== Just added\n", "\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": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Our expectation is that this assertion would fail. So, do we actually get an exception? Try it out for yourself by uncommenting the following line:" ] }, { "cell_type": "code", "execution_count": 43, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.311816Z", "iopub.status.busy": "2023-11-12T12:39:31.311647Z", "iopub.status.idle": "2023-11-12T12:39:31.313335Z", "shell.execute_reply": "2023-11-12T12:39:31.313020Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "# remove_html_markup_with_tag_assert('\"foo\"')" ] }, { "cell_type": "code", "execution_count": 44, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.315028Z", "iopub.status.busy": "2023-11-12T12:39:31.314912Z", "iopub.status.idle": "2023-11-12T12:39:31.318194Z", "shell.execute_reply": "2023-11-12T12:39:31.317843Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", "
\n", "

Quiz

\n", "

\n", "

What happens after inserting the above assertion?
\n", "

\n", "

\n", "

\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", "
\n", "

\n", " \n", " \n", "
\n", " " ], "text/plain": [ "" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quiz(\"What happens after inserting the above assertion?\",\n", " [\n", " \"The program raises an exception. (i.e., `tag` is set)\",\n", " \"The output is as before, i.e., `foo` without quotes.\"\n", " \" (which means that `tag` is not set)\"\n", " ], 2)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Here's the solution:" ] }, { "cell_type": "code", "execution_count": 45, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.319732Z", "iopub.status.busy": "2023-11-12T12:39:31.319636Z", "iopub.status.idle": "2023-11-12T12:39:31.321992Z", "shell.execute_reply": "2023-11-12T12:39:31.321626Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/plain": [ "'foo'" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "with ExpectError():\n", " result = remove_html_markup_with_tag_assert('\"foo\"')\n", "result" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Refuting a Hypothesis\n", "\n", "We did not get an exception, hence we reject our hypothesis:\n", "\n", "1. ~~The error is due to `tag` being set.~~\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Again, let's go back to the only place in our code where quotes are handled:\n", "\n", "```python\n", "elif c == '\"' or c == \"'\" and tag:\n", " quote = not quote\n", "```\n", "\n", "Because of the assertion, we already know that `tag` is always False. Hence, this condition should never hold either." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "But maybe there's something wrong with the condition such that it holds? Here's our hypothesis:\n", "\n", "1. The error is due to the quote condition evaluating to true\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "If the condition evaluates to true, then `quote` should be set. We could now go and assert that `quote` is false; but we only care about the condition. So we insert an assertion that assumes that setting the code setting the `quote` flag is never reached:" ] }, { "cell_type": "code", "execution_count": 46, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.323860Z", "iopub.status.busy": "2023-11-12T12:39:31.323756Z", "iopub.status.idle": "2023-11-12T12:39:31.326202Z", "shell.execute_reply": "2023-11-12T12:39:31.325918Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "def remove_html_markup_with_quote_assert(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", " assert False # <=== Just added\n", " quote = not quote\n", " elif not tag:\n", " out = out + c\n", "\n", " return out" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Our expectation this time again is that the assertion fails. So, do we get an exception this time? Try it out for yourself by uncommenting the following line:" ] }, { "cell_type": "code", "execution_count": 47, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.327741Z", "iopub.status.busy": "2023-11-12T12:39:31.327638Z", "iopub.status.idle": "2023-11-12T12:39:31.329402Z", "shell.execute_reply": "2023-11-12T12:39:31.329120Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "# remove_html_markup_with_quote_assert('\"foo\"')" ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.330770Z", "iopub.status.busy": "2023-11-12T12:39:31.330690Z", "iopub.status.idle": "2023-11-12T12:39:31.333810Z", "shell.execute_reply": "2023-11-12T12:39:31.333434Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", "
\n", "

Quiz

\n", "

\n", "

What happens after inserting the 'assert' tag?
\n", "

\n", "

\n", "

\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", "
\n", "

\n", " \n", " \n", "
\n", " " ], "text/plain": [ "" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quiz(\"What happens after inserting the 'assert' tag?\",\n", " [\n", " \"The program raises an exception (i.e., the quote condition holds)\",\n", " \"The output is still foo (i.e., the quote condition does not hold)\"\n", " ], 29 % 7)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Here's what happens now that we have the `assert` tag:" ] }, { "cell_type": "code", "execution_count": 49, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.335382Z", "iopub.status.busy": "2023-11-12T12:39:31.335272Z", "iopub.status.idle": "2023-11-12T12:39:31.337213Z", "shell.execute_reply": "2023-11-12T12:39:31.336952Z" }, "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_20417/904218512.py\", line 2, in \n", " result = remove_html_markup_with_quote_assert('\"foo\"')\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_20417/2877654332.py\", line 12, in remove_html_markup_with_quote_assert\n", " assert False # <=== Just added\n", "AssertionError (expected)\n" ] } ], "source": [ "with ExpectError():\n", " result = remove_html_markup_with_quote_assert('\"foo\"')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "From this observation, we can deduce that our hypothesis is _confirmed_:\n", "\n", "1. The error is due to the quote condition evaluating to true (CONFIRMED)\n", "\n", "and the _condition is actually faulty._ It evaluates to True although `tag` is always False:\n", "```python\n", "elif c == '\"' or c == \"'\" and tag:\n", " quote = not quote\n", "```\n", "But this condition holds for single and double quotes. Is there a difference?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Let us see whether our observations generalize towards general quotes:\n", "\n", "1. ~~Double~~ quotes are stripped from the input.\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "We can verify these hypotheses with an additional experiment. We go back to our original implementation (without any asserts), and then check it:" ] }, { "cell_type": "code", "execution_count": 50, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.339047Z", "iopub.status.busy": "2023-11-12T12:39:31.338927Z", "iopub.status.idle": "2023-11-12T12:39:31.341141Z", "shell.execute_reply": "2023-11-12T12:39:31.340842Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "\"'foo'\"" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "remove_html_markup(\"'foo'\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Surprise: Our hypothesis is rejected and we can add another observation to our table:\n", "\n", "|Input|Expectation|Output|Outcome|\n", "|-----|-----------|------|-------|\n", "|`'foo'`|`'foo'`|`'foo'`|✔|\n", "\n", "So, the condition\n", "\n", "* becomes True when a double quote is seen\n", "* becomes False (as it should) with single quotes" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "At this point, you should have enough material to solve the problem. How do we have to fix the condition? Here are four alternatives:\n", "\n", "```python\n", "c == \"\" or c == '' and tag # Choice 1\n", "c == '\"' or c == \"'\" and not tag # Choice 2\n", "(c == '\"' or c == \"'\") and tag # Choice 3\n", "... # Something else\n", "```" ] }, { "cell_type": "code", "execution_count": 51, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.342734Z", "iopub.status.busy": "2023-11-12T12:39:31.342623Z", "iopub.status.idle": "2023-11-12T12:39:31.346438Z", "shell.execute_reply": "2023-11-12T12:39:31.346165Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", "
\n", "

Quiz

\n", "

\n", "

How should the condition read?
\n", "

\n", "

\n", "

\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", "
\n", "

\n", " \n", " \n", "
\n", " " ], "text/plain": [ "" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quiz(\"How should the condition read?\",\n", " [\n", " '''`c == \"\" or c == '' and tag` (Choice 1)''',\n", " '''`c == '\"' or c == \"'\" and not tag` (Choice 2)''',\n", " '''`(c == '\"' or c == \"'\") and tag` (Choice 3)''',\n", " \"Something else\"\n", " ],\n", " '399 % 4')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Fixing the Bug" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "So, you have spotted the defect: In Python (and most other languages), `and` takes precedence over `or`, which is why the condition is wrong. It should read:\n", "\n", "```python\n", "(c == '\"' or c == \"'\") and tag\n", "```\n", "\n", "(Actually, good programmers rarely depend on precedence; it is considered good style to use parentheses lavishly.)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "So, our hypothesis now has become\n", "\n", "1. The error is due to the `quote` condition evaluating to True\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Is this our final hypothesis? We can check our earlier examples whether they should now work well:\n", "\n", "\n", "|Input|Expectation|Output|Outcome|\n", "|-----|-----------|------|-------|\n", "|`foo`|`foo`|`foo`|✔|\n", "|`\"foo\"`|`\"foo\"`|`foo`|✘|\n", "|`\"foo\"`|`\"foo\"`|`foo`|✘|\n", "|`foo`|`foo`|`foo`|✔|\n", "|`\"foo\"`|`'foo'`|`foo`|✘|\n", "|`'foo'`|`'foo'`|`'foo'`|✔|\n", "\n", "In all of these examples, the `quote` flag should now be set outside of tags; hence, everything should work as expected." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "In terms of the scientific process, we now have a *theory* – a hypothesis that\n", "\n", "* is consistent with all earlier observations\n", "* predicts future observations (in our case: correct behavior)\n", "\n", "For debugging, our problems are usually too small for a big word like theory, so we use the word *diagnosis* instead. So is our diagnosis sufficient to fix the bug? Let us check." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Checking Diagnoses\n", "\n", "In debugging, you should start to fix your code if and only if you have a diagnosis that shows two things:\n", "\n", "1. **Causality.** Your diagnosis should explain why and how the failure came to be. Hence, it induces a _fix_ that, when applied, should make the failure disappear.\n", "2. **Incorrectness.** Your diagnosis should explain why and how the code is _incorrect_ (which in turn suggests how to _correct_ the code). Hence, the fix it induces not only applies to the given failure, but also to all related failures." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Showing both these aspects requirements – _causality_ and _incorrectness_ – are crucial for a debugging diagnosis:\n", "\n", "* If you find that you can change some location to make the failure go away, but are not sure why this location is wrong, then your \"fix\" may apply only to the symptom rather than the source. Your diagnosis explains _causality_, but not _incorrectness_.\n", "* If you find that there is a defect in some code location, but do not verify whether this defect is related to the failure in question, then your \"fix\" may not address the failure. Your diagnosis addresses _incorrectness_, but not _causality_." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "When you do have a diagnosis that explains both causality (how the failure came to be), and incorrectness (how to correct the code accordingly), then (and only then!) is it time to actually _fix_ the code accordingly. After applying the fix, the failure should be gone, and no other failure should occur. If the failure persists, this should come as a surprise. Obviously, there is some other aspect that you haven't considered yet, so you have to go back to the drawing board and add another failing test case to the set of observations." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Fixing the Code" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "All these things considered, let us go and fix `remove_html_markup()`. We know how the defect _causes_ the failure (by erroneously setting `quote` outside of tags). We know that the line in question is _incorrect_ (as single and double of quotes should be treated similarly). So, our diagnosis shows both causality and incorrectness, and we can go and fix the code accordingly:" ] }, { "cell_type": "code", "execution_count": 52, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.348389Z", "iopub.status.busy": "2023-11-12T12:39:31.348286Z", "iopub.status.idle": "2023-11-12T12:39:31.350622Z", "shell.execute_reply": "2023-11-12T12:39:31.350306Z" }, "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: # <-- FIX\n", " quote = not quote\n", " elif not tag:\n", " out = out + c\n", "\n", " return out" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "We verify that the fix was successful by running our earlier tests. Not only should the previously failing tests now pass, the previously passing tests also should not be affected. Fortunately, all tests now pass:" ] }, { "cell_type": "code", "execution_count": 53, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.352267Z", "iopub.status.busy": "2023-11-12T12:39:31.352169Z", "iopub.status.idle": "2023-11-12T12:39:31.354170Z", "shell.execute_reply": "2023-11-12T12:39:31.353897Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "assert remove_html_markup(\"Here's some strong argument.\") == \\\n", " \"Here's some strong argument.\"\n", "assert remove_html_markup(\n", " '\">') == \"\"\n", "assert remove_html_markup('foo') == 'foo'\n", "assert remove_html_markup('\"foo\"') == '\"foo\"'\n", "assert remove_html_markup('\"foo\"') == '\"foo\"'\n", "assert remove_html_markup('foo') == 'foo'" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "So, our hypothesis _was_ a theory, and our diagnosis was correct. Success!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Alternate Paths\n", "\n", "A defect may have more than one hypothesis, and each diagnosis can be obtained by many ways. We could also have started with our other hypothesis\n", "\n", "2. Tags in double quotes are not stripped\n", "\n", "and by reasoning and experiments, we would have reached the same conclusion that the condition is faulty:\n", "\n", "* To strip tags, the `tag` flag must be set (but it is not).\n", "* To set the `tag` flag, the `quote` variable must not be set (but it is).\n", "* The `quote` flag is set under the given condition (which thus must be faulty).\n", "\n", "This gets us to the same diagnosis as above – and, of course, the same fix." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Homework after the Fix" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "After having successfully validated the fix, we still have some homework to make." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Check for further Defect Occurrences" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "First, we may want to check that the underlying mistake was not made elsewhere, too.\n", "\n", "For an error as with `remove_html_markup()`, it may be wise to check other parts of the code (possibly written by the same programmer) whether Boolean formulas show proper precedence. Consider setting up a static program checker or style checker to catch similar mistakes.\n", "Usually if you code in an IDE specifically designed for language you are coding in, you will get hints on so called _code smells_,\n", "parts of your code that are typically erroneous because of bad style or other typical mistakes." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Check your Tests\n", "\n", "If the defect was not found through testing, now is a good time to make sure it will be found the next time. If you use automated tests, add a test that catches the bug (as well as similar ones), such that you can prevent regressions." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Add Assertions\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "To be 100% sure, we could add an assertion to `remove_html_markup()` that checks the final result for correctness. Unfortunately, writing such an assertion is just as complex as writing the function itself.\n", "\n", "There is one assertion, though, which could be placed in the loop body to catch this kind of errors, and which could remain in the code. Which is it?" ] }, { "cell_type": "code", "execution_count": 54, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.356037Z", "iopub.status.busy": "2023-11-12T12:39:31.355905Z", "iopub.status.idle": "2023-11-12T12:39:31.359417Z", "shell.execute_reply": "2023-11-12T12:39:31.359024Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", "
\n", "

Quiz

\n", "

\n", "

Which assertion would have caught the problem?
\n", "

\n", "

\n", "

\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", "
\n", "

\n", " \n", " \n", "
\n", " " ], "text/plain": [ "" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quiz(\"Which assertion would have caught the problem?\",\n", " [\n", " \"`assert quote and not tag`\",\n", " \"`assert quote or not tag`\",\n", " \"`assert tag or not quote`\",\n", " \"`assert tag and not quote`\"\n", " ], '3270 - 3267')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Indeed, the statement\n", "\n", "```python\n", "assert tag or not quote\n", "```\n", "is correct. This excludes the situation of ¬`tag` ∧ `quote` – that is, the `tag` flag is not set, but the `quote` flag is. If you remember our state machine from above, this is actually a state that should never exist:" ] }, { "cell_type": "code", "execution_count": 55, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.360845Z", "iopub.status.busy": "2023-11-12T12:39:31.360758Z", "iopub.status.idle": "2023-11-12T12:39:31.759904Z", "shell.execute_reply": "2023-11-12T12:39:31.759556Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "Start\n", "\n", "Start\n", "\n", "\n", "\n", "¬ quote\\n¬ tag\n", "\n", "¬ quote\n", "¬ tag\n", "\n", "\n", "\n", "Start->¬ quote\\n¬ tag\n", "\n", "\n", "\n", "\n", "\n", "¬ quote\\n¬ tag->¬ quote\\n¬ tag\n", "\n", "\n", "¬ '<'\n", "add character\n", "\n", "\n", "\n", "¬ quote\\ntag\n", "\n", "¬ quote\n", "tag\n", "\n", "\n", "\n", "¬ quote\\n¬ tag->¬ quote\\ntag\n", "\n", "\n", "'<'\n", "\n", "\n", "\n", "¬ quote\\ntag->¬ quote\\n¬ tag\n", "\n", "\n", "'>'\n", "\n", "\n", "\n", "¬ quote\\ntag->¬ quote\\ntag\n", "\n", "\n", "¬ '"' ∧ ¬ '>'\n", "\n", "\n", "\n", "quote\\ntag\n", "\n", "quote\n", "tag\n", "\n", "\n", "\n", "¬ quote\\ntag->quote\\ntag\n", "\n", "\n", "'"'\n", "\n", "\n", "\n", "quote\\ntag->¬ quote\\ntag\n", "\n", "\n", "'"'\n", "\n", "\n", "\n", "quote\\ntag->quote\\ntag\n", "\n", "\n", "¬ '"'\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# ignore\n", "display(state_machine)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Here's our function in its \"final\" state. As software goes, software is never final – and this may also hold for our function, as there is still room for improvement. For this chapter though, we leave it be." ] }, { "cell_type": "code", "execution_count": 56, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.761943Z", "iopub.status.busy": "2023-11-12T12:39:31.761802Z", "iopub.status.idle": "2023-11-12T12:39:31.764585Z", "shell.execute_reply": "2023-11-12T12:39:31.764149Z" }, "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", " assert tag or not quote\n", "\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": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Commit the Fix" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "It may sound obvious, but your fix is worth nothing if it doesn't go into production. Be sure to commit your change to the code repository, together with your diagnosis. If your fix has to be approved by a third party, a good diagnosis on why and what happened is immensely helpful." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Close the Bug Report\n", "\n", "If you [systematically track bugs](Tracking.ipynb), and your bug is properly tracked, now is the time to mark the issue as \"resolved\". Check for duplicates of the issue and check whether they are resolved, too. And now, you are finally done:\n", "\n", "![](https://media.giphy.com/media/nbJUuYFI6s0w0/giphy.gif)\n", "\n", "Time to relax – and look for the next bug!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Become a Better Debugger\n", "\n", "We have now systematically fixed a bug. In this book, we will explore a number of techniques to make debugging easier – coming up with automated diagnoses, explanations, even automatic repairs, including for our example above. But there are also a number of things _you_ can do to become a better debugger.\n", "\n", "\n", "### Follow the Process\n", "\n", "If you're an experienced programmer, you may have spotted the problem in `remove_html_markup()` immediately, and start fixing the code right away. But this is dangerous and risky.\n", "\n", "Why is this so? Well, because you should first\n", "\n", "* try to understand the problem, and \n", "* have a full diagnosis before starting to fix away.\n", "\n", "You _can_ skip these steps, and jump right to your interactive debugger the very moment you see a failure, happily stepping through their program. This may even work well for simple problems, including this one. The risk, however, is that this narrows your view to just this one execution, which limits your ability to understand _all_ the circumstances of the problem. Even worse: If you start \"fixing\" the bug without exactly understanding the problem, you may end up with an incomplete solution – as illustrated in \"The Devil's Guide to Debugging\", above." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Keep a Log\n", "\n", "A second risk of starting debugging too soon is that it lets you easily deviate from a systematic process. Remember how we wrote down every experiment in a table? How we numbered every hypothesis? This is not just for teaching. Writing these things down explicitly allow you to keep track of all your observations and hypotheses over time.\n", "\n", "|Input|Expectation|Output|Outcome|\n", "|-----|-----------|------|-------|\n", "|`foo`|`foo`|`foo`|✔|\n", "\n", "Every time you come up with a new hypothesis, you can immediately check it against your earlier observations, which will help you to eliminate unlikely ones from the start. This is a bit like in the classic \"Mastermind\" board game, in which you have to guess some secret combination of pins, and in which your opponent gives you hints on whether and how your guesses are correct. At any time, you can see your previous guesses (experiments) and the results (observations) you got; any new guess (hypothesis) has to be consistent with the previous observations and experiments." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "![Master Mind Board Grame](https://upload.wikimedia.org/wikipedia/commons/2/2d/Mastermind.jpg)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Keeping such a log also allows you to interrupt your debugging session at any time. You can be home in time, sleep over the problem, and resume the next morning with a refreshed mind. You can even hand over the log to someone else, stating your findings so far.\n", "\n", "The alternative to having a log is to _keep all in memory_. This only works for short amounts of time, as it puts a higher and higher cognitive load on your memory as you debug along. After some time, you will forget earlier observations, which leads to mistakes. Worst of all, any interruption will break your concentration and make you forget things, so you can't stop debugging until you're done.\n", "\n", "Sure, if you are a real master, you can stay glued to the screen all night. But I'd rather be home in time, thank you." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Rubberducking\n", "\n", "A great technique to revisit your observations and to come up with new hypotheses is to _explain the problem to someone else_. In this process, the \"someone else\" is important, but even more important is that _you are explaining the problem to yourself_! As Kernighan and Pike \\cite{Kernighan1999} put it:\n", "\n", "> Sometimes it takes no more than a few sentences, followed by an embarrassed \"Never mind. I see what's wrong. Sorry to bother you.\"\n", "\n", "The reason why this works is that teaching someone else forces you to take different perspectives, and these help you to resolve the inconsistency between what you assume and what you actually observe.\n", "\n", "Since that \"someone else\" can be totally passive, you can even replace her with an inanimate object to talk to – even a rubber duck. This technique is called *rubber duck debugging* or *rubberducking* – the idea is that you explain your problem to a rubber duck first before interrupting one of your co-workers with the problem. Some programmers, when asked for advice, explicitly request that you \"explain your problem to the duck first\", knowing that this resolves a good fraction of problems." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "![Rubber duck debugging](https://upload.wikimedia.org/wikipedia/commons/d/d5/Rubber_duck_assisting_with_debugging.jpg)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## The Cost of Debugging\n", "\n", "And it's not only that debugging takes time – the worst thing is that it is a search process, which can take anything between a few minutes and several hours, sometimes even days and weeks. But even if you never know how much time a bug will take, it's a bit of blessing to use a process which gradually gets you towards its cause." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Debugging Aftermath\n", "\n", "The fix of a bug may lead to a code construct, a more complex condition or another solution which may look strange on first sight.\n", "Often the initial code was easier to understand but did not catch all cases. After fixing a bug it may be beneficial to\n", "write down why the code now looks like this and what caused the more complex construct. A comment right at the fixed location\n", "will help future programmers to not be confused or even re-introduce the bug while refactoring for better readability.\n", "And of course, helpful comments at complex code locations should even exist before something went wrong with the code -- but\n", "thats a chapter in another book.\n", "\n", "## History of Debugging\n", "\n", "Engineers and programmers have long used the term \"bug\" for faults in their systems – as if it were something that crept into an otherwise flawless program to cause the effects that none could explain. And from a psychological standpoint, it is far easier to blame some \"bug\" rather than taking responsibility ourselves. In the end, though, we have to face the fact: We made the bugs, and they are ours to fix.\n", "\n", "Having said that, there has been one recorded instance where a real bug has crept into a system. That was on September 9, 1947, when a moth got stuck in the relay of a Harvard Mark II machine. This event was logged, and the log book is now on display at the Smithsonian Natural Museum of American History, as \"First actual case of bug being found.\"" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "![First actual case of bug being found](https://upload.wikimedia.org/wikipedia/commons/f/ff/First_Computer_Bug%2C_1945.jpg)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The actual term \"bug\", however, is much older. What do you think is its origin?" ] }, { "cell_type": "code", "execution_count": 57, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.766476Z", "iopub.status.busy": "2023-11-12T12:39:31.766365Z", "iopub.status.idle": "2023-11-12T12:39:31.767996Z", "shell.execute_reply": "2023-11-12T12:39:31.767713Z" }, "ipub": { "ignore": true }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "# ignore\n", "import hashlib" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.769496Z", "iopub.status.busy": "2023-11-12T12:39:31.769378Z", "iopub.status.idle": "2023-11-12T12:39:31.771185Z", "shell.execute_reply": "2023-11-12T12:39:31.770887Z" }, "ipub": { "ignore": true }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "# ignore\n", "bughash = hashlib.md5(b\"debug\").hexdigest()" ] }, { "cell_type": "code", "execution_count": 59, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.772643Z", "iopub.status.busy": "2023-11-12T12:39:31.772516Z", "iopub.status.idle": "2023-11-12T12:39:31.776291Z", "shell.execute_reply": "2023-11-12T12:39:31.776011Z" }, "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", "
\n", "

Quiz

\n", "

\n", "

Where has the name \"bug\" been used to denote disruptive events?
\n", "

\n", "

\n", "

\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", " \n", "
\n", " \n", "
\n", "

\n", " \n", " \n", "
\n", " " ], "text/plain": [ "" ] }, "execution_count": 59, "metadata": {}, "output_type": "execute_result" } ], "source": [ "quiz('Where has the name \"bug\" been used to denote disruptive events?',\n", " [\n", " 'In the early days of Morse telegraphy, referring to a special key '\n", " 'that would send a string of dots',\n", " 'Among radio technicians to describe a device that '\n", " 'converts electromagnetic field variations into acoustic signals',\n", " \"In Shakespeare's \" '\"Henry VI\", referring to a walking spectre',\n", " 'In Middle English, where the word \"bugge\" is the basis for terms '\n", " 'like \"bugbear\" and \"bugaboo\"'\n", " ], [bughash.index(i) for i in \"d42f\"])" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Need help on this quiz? To learn more about the term \"bug\" and its origin, have a look at [the etymology of the word \"bug\"](http://www.catb.org/~esr/jargon/html/B/bug.html) in [The Jargon File](http://www.catb.org/~esr/jargon/). Also check out the [Wikipedia entry on debugging](https://en.wikipedia.org/wiki/Debugging)!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Synopsis" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "In this chapter, we introduce some basics of how failures come to be as well as a general process for debugging." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": true, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Lessons Learned\n", "\n", "1. An _error_ is a deviation from what is correct, right, or true. Specifically,\n", " * A _mistake_ is a human act or decision resulting in an error.\n", " * A _defect_ is an error in the program code. Also called *bug*.\n", " * A _fault_ is an error in the program state. Also called *infection*.\n", " * A _failure_ is an externally visible error in the program behavior. Also called *malfunction*.\n", "2. In a failing program execution, a mistake by the programmer results in a defect in the code, which creates a fault in the state, which propagates until it results in a failure. Tracing back fault propagation allows identifying the defect that causes the failure.\n", "3. In debugging, the _scientific method_ allows systematically identifying failure causes by gradually refining and refuting hypotheses based on experiments and observations.\n", "4. Before fixing the defect, have a complete _diagnosis_ that \n", " * shows _causality_ (how the defect causes the failure)\n", " * shows _incorrectness_ (how the defect is wrong)\n", "5. You can become a better debugger by\n", " * Following a systematic process like the scientific method\n", " * Keeping a log of your observations and hypotheses\n", " * Making your observations and conclusions explicit by telling them somebody (or something)." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Next Steps\n", "\n", "In the next chapters, we will learn how to\n", "\n", "* [trace and observe executions](Tracer.ipynb)\n", "* [build your own interactive debugger](Debugger.ipynb)\n", "* [locate defects automatically by correlating failures and code coverage](StatisticalDebugger.ipynb)\n", "* [identify and simplify failure-inducing inputs](DeltaDebugger.ipynb)\n", "\n", "Enjoy!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Background\n", "\n", "There are several good books on debugging, but these three are especially recommended:\n", "\n", "* _Debugging_ by Agans \\cite{agans2006-debugging} takes a pragmatic approach to debugging, highlighting systematic approaches that help for all kinds of application-specific problems;\n", "* _Why Programs Fail_ by Zeller \\cite{zeller2009-why-programs-fail} takes a more academic approach, creating theories of how failures come to be and systematic debugging processes;\n", "* _Effective Debugging_ by Spinellis \\cite{spinellis2016-effective-debugging} aims for a middle ground between the two, creating general recipes and recommendations that easily instantiate towards specific problems.\n", "\n", "All these books focus on _manual_ debugging and the debugging process, just like this chapter; for _automated_ debugging, simply read on :-)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": true, "run_control": { "read_only": false }, "slideshow": { "slide_type": "slide" } }, "source": [ "## Exercises" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": true, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "### Exercise 1: Get Acquainted with Notebooks and Python\n", "\n", "Your first exercise in this book is to get acquainted with notebooks and Python, such that you can run the code examples in the book – and try out your own. Here are a few tasks to get you started." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": true, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Beginner Level: Run Notebooks in Your Browser\n", "\n", "The easiest way to get access to the code is to run them in your browser.\n", "\n", "1. From the [Web Page](__CHAPTER_HTML__), check out the menu at the top. Select `Resources` $\\rightarrow$ `Edit as Notebook`.\n", "2. After a short waiting time, this will open a Jupyter Notebook right within your browser, containing the current chapter as a notebook.\n", "3. You can again scroll through the material, but you click on any code example to edit and run its code (by entering Shift + Return). You can edit the examples as you please.\n", "4. Note that code examples typically depend on earlier code, so be sure to run the preceding code first.\n", "5. Any changes you make will not be saved (unless you save your notebook to disk).\n", "\n", "For help on Jupyter Notebooks, from the [Web Page](__CHAPTER_HTML__), check out the `Help` menu." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": true, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Advanced Level: Run Python Code on Your Machine\n", "\n", "This is useful if you want to make greater changes, but do not want to work with Jupyter.\n", "\n", "1. From the [Web Page](__CHAPTER_HTML__), check out the menu at the top. Select `Resources` $\\rightarrow$ `Download Code`. \n", "2. This will download the Python code of the chapter as a single Python .py file, which you can save to your computer.\n", "3. You can then open the file, edit it, and run it in your favorite Python environment to re-run the examples.\n", "4. Most importantly, you can [import it](Importing.ipynb) into your own code and reuse functions, classes, and other resources.\n", "\n", "For help on Python, from the [Web Page](__CHAPTER_HTML__), check out the `Help` menu." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "button": false, "new_sheet": true, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Pro Level: Run Notebooks on Your Machine\n", "\n", "This is useful if you want to work with Jupyter on your machine. This will allow you to also run more complex examples, such as those with graphical output.\n", "\n", "\n", "1. From the [Web Page](__CHAPTER_HTML__), check out the menu at the top. Select `Resources` $\\rightarrow$ `All Notebooks`.\n", "2. This will download all Jupyter Notebooks as a collection of .ipynb files, which you can save to your computer.\n", "3. You can then open the notebooks in Jupyter Notebook or Jupyter Lab, edit them, and run them. To navigate across notebooks, open the notebook [`00_Table_of_Contents.ipynb`](00_Table_of_Contents.ipynb).\n", "4. You can also download individual notebooks using Select `Resources` $\\rightarrow$ `Download Notebook`. Running these, however, will require that you have the other notebooks downloaded already.\n", "\n", "For help on Jupyter Notebooks, from the [Web Page](__CHAPTER_HTML__), check out the `Help` menu." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "button": false, "new_sheet": true, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Boss Level: Contribute!\n", "\n", "This is useful if you want to contribute to the book with patches or other material. It also gives you access to the very latest version of the book.\n", "\n", "1. From the [Web Page](__CHAPTER_HTML__), check out the menu at the top. Select `Resources` $\\rightarrow$ `GitHub Repo`.\n", "2. This will get you to the GitHub repository which contains all sources of the book, including the latest notebooks.\n", "3. You can then _clone_ this repository to your disk, such that you get the latest and greatest.\n", "4. You can report issues and suggest pull requests on the GitHub page.\n", "5. Updating the repository with `git pull` will get you updated.\n", "\n", "If you want to contribute code or text, check out the [Guide for Authors](Guide_for_Authors.ipynb)." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" }, "solution2": "hidden", "solution2_first": true }, "source": [ "### Exercise 2: More Bugs!\n", "\n", "You may have noticed that our `remove_html_markup()` function is still not working perfectly under all circumstances. The error has something to do with different quotes occurring in the input." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "subslide" } }, "source": [ "#### Part 1: Find the Problem\n", "\n", "What does the problem look like? Set up a test case that demonstrates the problem." ] }, { "cell_type": "code", "execution_count": 60, "metadata": { "cell_style": "center", "execution": { "iopub.execute_input": "2023-11-12T12:39:31.778289Z", "iopub.status.busy": "2023-11-12T12:39:31.778200Z", "iopub.status.idle": "2023-11-12T12:39:31.779959Z", "shell.execute_reply": "2023-11-12T12:39:31.779661Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "assert(...)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" }, "solution2": "hidden", "solution2_first": true }, "source": [ "Set up additional test cases as useful." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "**Solution.** The remaining problem stems from the fact that in `remove_html_markup()`, we do not differentiate between single and double quotes. Hence, if we have a _quote within a quoted text_, the function may get confused. Notably, a string that begins with a double quote may be interpreted as ending when a single quote is seen, and vice versa. Here's an example of such a string:\n", "\n", "```html\n", "\">foo\n", "```" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "When we remove the HTML markup, the `>` in the string is interpreted as _unquoted_. Hence, it is interpreted as ending the tag, such that the rest of the tag is not removed." ] }, { "cell_type": "code", "execution_count": 61, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.781496Z", "iopub.status.busy": "2023-11-12T12:39:31.781401Z", "iopub.status.idle": "2023-11-12T12:39:31.783621Z", "shell.execute_reply": "2023-11-12T12:39:31.783339Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "'\">foo'" ] }, "execution_count": 61, "metadata": {}, "output_type": "execute_result" } ], "source": [ "s = '\" + '\">foo'\n", "s" ] }, { "cell_type": "code", "execution_count": 62, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.785161Z", "iopub.status.busy": "2023-11-12T12:39:31.785065Z", "iopub.status.idle": "2023-11-12T12:39:31.787536Z", "shell.execute_reply": "2023-11-12T12:39:31.787290Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "data": { "text/plain": [ "'\"foo'" ] }, "execution_count": 62, "metadata": {}, "output_type": "execute_result" } ], "source": [ "remove_html_markup(s)" ] }, { "cell_type": "code", "execution_count": 63, "metadata": { "cell_style": "split", "execution": { "iopub.execute_input": "2023-11-12T12:39:31.788923Z", "iopub.status.busy": "2023-11-12T12:39:31.788840Z", "iopub.status.idle": "2023-11-12T12:39:31.790835Z", "shell.execute_reply": "2023-11-12T12:39:31.790569Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "Traceback (most recent call last):\n", " File \"/var/folders/n2/xd9445p97rb3xh7m1dfx8_4h0006ts/T/ipykernel_20417/2099129847.py\", line 2, in \n", " assert(remove_html_markup(s) == \"foo\")\n", "AssertionError (expected)\n" ] } ], "source": [ "with ExpectError():\n", " assert(remove_html_markup(s) == \"foo\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" }, "solution2": "hidden", "solution2_first": true }, "source": [ "#### Part 2: Identify Extent and Cause\n", "\n", "Using the scientific method, identify the extent and cause of the problem. Write down your hypotheses and log your observations, as in\n", "\n", "|Input|Expectation|Output|Outcome|\n", "|-----|-----------|------|-------|\n", "|(input)|(expectation)|(output)|(outcome)|\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "**Solution.** The first step is obviously\n", "\n", "|Input|Expectation|Output|Outcome|\n", "|-----|-----------|------|-------|\n", "|\">foo|foo|\"foo|✘|\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" }, "solution2": "hidden", "solution2_first": true }, "source": [ "#### Part 3: Fix the Problem\n", "\n", "Design a fix for the problem. Show that it satisfies the earlier tests and does not violate any existing test." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "**Solution**. Here's an improved implementation that actually tracks the opening and closing quote by storing the quoting character in the `quote` variable. (If `quote` is `''`, we are not in a string.)" ] }, { "cell_type": "code", "execution_count": 64, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.792430Z", "iopub.status.busy": "2023-11-12T12:39:31.792336Z", "iopub.status.idle": "2023-11-12T12:39:31.794795Z", "shell.execute_reply": "2023-11-12T12:39:31.794552Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "def remove_html_markup_with_proper_quotes(s): # type: ignore\n", " tag = False\n", " quote = ''\n", " out = \"\"\n", "\n", " for c in s:\n", " assert tag or quote == ''\n", "\n", " if c == '<' and quote == '':\n", " tag = True\n", " elif c == '>' and quote == '':\n", " tag = False\n", " elif (c == '\"' or c == \"'\") and tag and quote == '':\n", " # beginning of string\n", " quote = c\n", " elif c == quote:\n", " # end of string\n", " quote = ''\n", " elif not tag:\n", " out = out + c\n", "\n", " return out" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "Python enthusiasts may note that we could also write `not quote` instead of `quote == ''`, leaving most of the original code untouched. We stick to classic Boolean comparisons here." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "The function now satisfies the earlier failing test:" ] }, { "cell_type": "code", "execution_count": 65, "metadata": { "cell_style": "split", "execution": { "iopub.execute_input": "2023-11-12T12:39:31.796578Z", "iopub.status.busy": "2023-11-12T12:39:31.796465Z", "iopub.status.idle": "2023-11-12T12:39:31.798283Z", "shell.execute_reply": "2023-11-12T12:39:31.797989Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "assert(remove_html_markup_with_proper_quotes(s) == \"foo\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "source": [ "as well as all our earlier tests:" ] }, { "cell_type": "code", "execution_count": 66, "metadata": { "execution": { "iopub.execute_input": "2023-11-12T12:39:31.799830Z", "iopub.status.busy": "2023-11-12T12:39:31.799700Z", "iopub.status.idle": "2023-11-12T12:39:31.801849Z", "shell.execute_reply": "2023-11-12T12:39:31.801511Z" }, "slideshow": { "slide_type": "skip" }, "solution2": "hidden" }, "outputs": [], "source": [ "assert remove_html_markup_with_proper_quotes(\n", " \"Here's some strong argument.\") == \\\n", " \"Here's some strong argument.\"\n", "assert remove_html_markup_with_proper_quotes(\n", " '\">') == \"\"\n", "assert remove_html_markup_with_proper_quotes('foo') == 'foo'\n", "assert remove_html_markup_with_proper_quotes('\"foo\"') == '\"foo\"'\n", "assert remove_html_markup_with_proper_quotes('\"foo\"') == '\"foo\"'\n", "assert remove_html_markup_with_proper_quotes('foo') == 'foo'" ] } ], "metadata": { "ipub": { "bibliography": "fuzzingbook.bib", "toc": true }, "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.10.2" }, "toc": { "base_numbering": 1, "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": true, "title_cell": "", "title_sidebar": "Contents", "toc_cell": false, "toc_position": {}, "toc_section_display": true, "toc_window_display": true }, "toc-autonumbering": false }, "nbformat": 4, "nbformat_minor": 4 }