10 Dynamic Analysis.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c1cd2b3e",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Dynamic Analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9d7d536",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In this chapter we consider dynamic analysis, which analyses a program by executing it. A dynamic analysis requires (1) program executions, i.e., tests; (2) program instrumentation that collects information at runtime in execution traces; and (3) an analysis based on the execution traces."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8fedc7c",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Example Task: Analysing Method Calls"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1643f7c",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "As an example, let's assume we want to collect information about methods called at runtime. We consider an example method `foo` which calls two other methods."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7957dfb8",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def foo(x):\n",
    "    if x == 0:\n",
    "        return\n",
    "\n",
    "    if x % 2 == 0:\n",
    "        printEven()\n",
    "    else:\n",
    "        printOdd()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "01cd38de",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def printEven():\n",
    "    print(\"Even\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f9f40fc7",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def printOdd():\n",
    "    print(\"Odd\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "993307f1",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In contrast to previous notebooks, which used Python to analyse Java code, to enable executions in the notebook we are now analysing Python code. Let's have a look at the AST of the program we are analysing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "346409e7",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from graphviz import Digraph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1f6cfdb4",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class AstGraphGenerator(object):\n",
    "\n",
    "    def __init__(self, source):\n",
    "        self.graph = Digraph()\n",
    "        self.source = source.split(\"\\n\")\n",
    "\n",
    "    def __str__(self):\n",
    "        return str(self.graph)\n",
    "\n",
    "    def _getid(self, node):\n",
    "        try:\n",
    "            lineno = node.lineno - 1\n",
    "            return \"%d: %s\" % (lineno, node.__class__.__name__)\n",
    "\n",
    "        except AttributeError:\n",
    "            return str(type(node))\n",
    "\n",
    "    def visit(self, node):\n",
    "        method = 'visit_' + node.__class__.__name__\n",
    "        visitor = getattr(self, method, self.generic_visit)\n",
    "        return visitor(node)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "27a7d302",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "This implementation is crude and simplifies a couple of things, but it's sufficient to demonstrate that the Python AST is similar to the ASTs we have seen so far. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a5651bf2",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class AstGraphGenerator(AstGraphGenerator):\n",
    "    def _getid(self, node):\n",
    "        return str(id(node))\n",
    "        \n",
    "    def _getlabel(self, node):\n",
    "        try:\n",
    "            lineno = node.lineno - 1\n",
    "            return \"%d: %s\" % (lineno, node.__class__.__name__)\n",
    "\n",
    "        except AttributeError:\n",
    "            return str(type(node))\n",
    "\n",
    "        \n",
    "    def generic_visit(self, node):\n",
    "        self.graph.node(name=self._getid(node), label=self._getlabel(node))\n",
    "        for _, value in ast.iter_fields(node):\n",
    "            if isinstance(value, list):\n",
    "                for item in value:\n",
    "                    if isinstance(item, ast.Load):\n",
    "                        continue\n",
    "                    self.graph.node(name=self._getid(item), label=self._getlabel(item))\n",
    "                    self.graph.edge(self._getid(node), self._getid(item))\n",
    "                    if isinstance(item, ast.AST):\n",
    "                        self.visit(item)\n",
    "\n",
    "            elif isinstance(value, ast.AST):\n",
    "                if isinstance(value, ast.Load):\n",
    "                    return\n",
    "                \n",
    "                self.graph.node(name=self._getid(value), label=self._getlabel(value))\n",
    "                self.graph.edge(self._getid(node), self._getid(value))\n",
    "                self.visit(value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7a084036",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import inspect"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "51b83409",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "source = inspect.getsource(foo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "42e25ad3",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(source)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e23a6f92",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "ag = AstGraphGenerator(source)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a9676bb1",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import ast\n",
    "node = ast.parse(source)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d3a6360a",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "ag.visit(node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b323c8bd",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "ag.graph"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86d52740",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Instrumenting the AST"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73dee08c",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Instrumentation is at the core of dynamic analysis, and one way to achieve instrumentation is by modifying the AST, and producing source code from the AST."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "44c4c854",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The Python API provides a visitor interface to manipulate Python ASTs. One way to collect information about method calls is to add instrumentation at method _entry_. We will instrument our AST such that, at the entry of every method declaration, a call to a custom method `trace` with the called method's name is inserted."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e0755f53",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class MethodEntryTransformer(ast.NodeTransformer):\n",
    "\n",
    "    def visit_FunctionDef(self, node):\n",
    "        trace_call = ast.Expr(ast.Call(func=ast.Name(\"trace\", ast.Load()),\n",
    "                        args=[ast.Constant(value=node.name)],\n",
    "                        keywords=[],\n",
    "                        starargs=None,\n",
    "                        kwargs=None))\n",
    "        node.body = [ trace_call ] + node.body\n",
    "        return self.generic_visit(node)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa800e08",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's apply this visitor to our example program to produce a modified AST."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "09864344",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "source = inspect.getsource(printEven)\n",
    "node = ast.parse(source)\n",
    "node = MethodEntryTransformer().visit(node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8e772a8f",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "ag = AstGraphGenerator(source)\n",
    "ag.visit(node)\n",
    "ag.graph"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1dcfd966",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can also produce source code from this AST. Since Python 3.9, the `ast` module provides an `unparse` method which does just that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5db1cf2f",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "print(ast.unparse(node))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9e42fae3",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# For Python versions < 3.9 you will need to use the astor module to produce source code from ASTs\n",
    "#import astor\n",
    "#print(astor.to_source(node))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e5fc31d3",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To run our instrumented code, we need to compile the resulting program, and insert the instrumented version into Python's global map of functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b40b9c28",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import sys"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "55de19ed",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def create_instrumented_function(f):\n",
    "    source = inspect.getsource(f)\n",
    "    node = ast.parse(source)\n",
    "    node = MethodEntryTransformer().visit(node)\n",
    "\n",
    "    # Make sure the line numbers are ok so that it compiles\n",
    "    node = ast.fix_missing_locations(node)\n",
    "\n",
    "    # Compile and add the instrumented function to the current module\n",
    "    current_module = sys.modules[__name__]\n",
    "    code = compile(node, filename=\"<ast>\", mode=\"exec\")\n",
    "    exec(code, current_module.__dict__)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ed24ee3",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's instrument all our example methods."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "184cbad0",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "create_instrumented_function(printEven)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d5dcca42",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "create_instrumented_function(printOdd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "63bd0cce",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "create_instrumented_function(foo)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "088b0930",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The instrumentation attempts to call a `trace` function, so we need to define one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1b1f1d56",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def trace(x):\n",
    "    print(f\"Calling method {x}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a8b4458",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Now we can call our instrumented function and see the instrumentation in action."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1ddd07ff",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "foo(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31c2a908",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Example Analysis: Call Trees and Call Graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "84e256e2",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "As an example analysis, let's assume we are interested in deriving call trees and call graphs from our executions. A call tree is context sensitive; a call graph is a context insensitive version of a call tree."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f695b32d",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "For this analysis, we need to track not only when we enter methods, but also when we leave them. Instrumenting this within a method is not as easy as just instrumenting entry: There can be multiple points of exit, at every return statement and for every possible exception. An alternative might be to instrument _call sites_. Let's do this an wrap each call to a method into calls to `trace_entry` and `trace_exit` functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aba1a30a",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class MethodCallTransformer(ast.NodeTransformer):\n",
    "\n",
    "    def visit_Expr(self, node):\n",
    "        if isinstance(node.value, ast.Call):\n",
    "            method_entry = ast.Expr(ast.Call(func=ast.Name(\"trace_entry\", ast.Load()),\n",
    "                        args=[ast.Constant(value=node.value.func.id)],\n",
    "                        keywords=[],\n",
    "                        starargs=None,\n",
    "                        kwargs=None))\n",
    "            method_exit = ast.Expr(ast.Call(func=ast.Name(\"trace_exit\", ast.Load()),\n",
    "                        args=[ast.Constant(value=node.value.func.id)],\n",
    "                        keywords=[],\n",
    "                        starargs=None,\n",
    "                        kwargs=None))\n",
    "            return [method_entry, node, method_exit]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f8eda7fd",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can again look at the resulting source code."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6aa042c",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Since we replaced our original methods (to keep things brief), we need to redefine our code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e867d0be",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def foo(x):\n",
    "    if x == 0:\n",
    "        return\n",
    "\n",
    "    if x % 2 == 0:\n",
    "        printEven()\n",
    "    else:\n",
    "        printOdd()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "52552a31",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def printEven():\n",
    "    print(\"Even\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1adf2652",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def printOdd():\n",
    "    print(\"Odd\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b6f509d6",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "source = inspect.getsource(foo)\n",
    "node = ast.parse(source)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0f9b7ee5",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "MethodCallTransformer().visit(node)\n",
    "node = ast.fix_missing_locations(node)\n",
    "print(ast.unparse(node))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8e88e51",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We also need to update our instrumentation function to make sure we use the compiled versions of our instrumented code at runtime."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7575682d",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def create_instrumented_function(f):\n",
    "    source = inspect.getsource(f)\n",
    "    node = ast.parse(source)\n",
    "    node = MethodCallTransformer().visit(node)\n",
    "    node = ast.fix_missing_locations(node)\n",
    "    current_module = sys.modules[__name__]\n",
    "    code = compile(node, filename=\"<ast>\", mode=\"exec\")\n",
    "    exec(code, current_module.__dict__)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a8a5a08",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We also need to define our new trace functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8aa7683a",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def trace_entry(method):\n",
    "    print(f\"Entering {method}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f2c879dc",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def trace_exit(method):\n",
    "    print(f\"Leaving {method}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "52533df0",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "create_instrumented_function(foo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8ecd9b42",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "foo(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5049b8fe",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "foo(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e09ce10f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "One thing that's missing here is the call to `foo` itself, since we called it directly rather than from some client code."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f84f8cfd",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can keep this in mind when building a proper tracer that collects the necessary information to build a call tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fdc286c4",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class Tracer:\n",
    "    def __init__(self, entry):\n",
    "        self.graph = Digraph()\n",
    "        self.graph.node(entry + \"_1\", label=entry)\n",
    "        self.call_stack = [ entry + \"_1\" ]\n",
    "        self.call_count = { entry: 1}\n",
    "        \n",
    "    def entry(self, method):\n",
    "        if method in self.call_count:\n",
    "            self.call_count[method] = self.call_count[method] + 1\n",
    "        else:\n",
    "            self.call_count[method] = 1\n",
    "            \n",
    "        node_id = f\"{method}_{self.call_count[method]}\"\n",
    "        current_method = self.call_stack[-1]\n",
    "        self.graph.node(node_id, label=method)\n",
    "        self.graph.edge(current_method, node_id)\n",
    "        self.call_stack.append(node_id)\n",
    "        \n",
    "    def exit(self, method):\n",
    "        self.call_stack.pop()        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c86eb380",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Our current example code does not consist of deeply nested calls, so let's include the example from the lecture slides."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6163c1e8",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def foo(x):\n",
    "    method_a(x)\n",
    "    method_d(x)\n",
    "    method_a(x)\n",
    "    method_d(x)\n",
    "    method_a(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d14145af",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def method_a(x):\n",
    "    method_b(x)\n",
    "    if x == 0:\n",
    "        method_b(x)\n",
    "        \n",
    "    method_c(x)\n",
    "    if x == 0:\n",
    "        method_c(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7f7f1d0c",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def method_b(x):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "030217f8",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def method_c(x):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1bdaac8a",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def method_d(x):\n",
    "    if x == 0:\n",
    "        method_a(x)\n",
    "    else:\n",
    "        method_c(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67370edc",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To keep things simple, we just define a tracer as a global variable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cd63f90b",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "tracer = None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1f01a10",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Our tracing functions now need to make use of the `Tracer`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "40247c63",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def trace_entry(method):\n",
    "    if tracer:\n",
    "        tracer.entry(method)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2192415e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def trace_exit(method):\n",
    "    if tracer:\n",
    "        tracer.exit(method)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f3b1367d",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Again we instrument all functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5a191a64",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "create_instrumented_function(foo)\n",
    "create_instrumented_function(method_a)\n",
    "create_instrumented_function(method_b)\n",
    "create_instrumented_function(method_c)\n",
    "create_instrumented_function(method_d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "692ab26b",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def call_tree(method, arg):\n",
    "    global tracer\n",
    "    tracer = Tracer(method.__name__)\n",
    "    method(arg)\n",
    "    return tracer.graph"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d5c3664",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "This gives us the following call graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "df2ee7d0",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "call_tree(foo, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3018f299",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Simply calling the instrumented `foo` function will now use our tracer."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b1bb4b21",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "A call graph contains the same information, but ignores context."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "008a82c6",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class CallGraphTracer:\n",
    "    def __init__(self, entry):\n",
    "        self.graph = Digraph()\n",
    "        self.edges = set()\n",
    "        self.call_stack = [ entry ]\n",
    "        \n",
    "    def entry(self, method):\n",
    "        current_method = self.call_stack[-1]\n",
    "        if not (current_method, method) in self.edges:\n",
    "            self.graph.edge(current_method, method)\n",
    "            self.edges.add((current_method, method))\n",
    "        self.call_stack.append(method)\n",
    "        \n",
    "    def exit(self, method):\n",
    "        self.call_stack.pop()        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ae639ada",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def call_graph(method, arg):\n",
    "    global tracer\n",
    "    tracer = CallGraphTracer(method.__name__)\n",
    "    method(arg)\n",
    "    return tracer.graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3a151e6d",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "call_graph(foo, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1cea443",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Tracing"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b991ba4",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Python offers a convenient API to trace executions without instrumenting code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "592f7ddb",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "trace = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7d79bf2a",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def trace_call(frame, event, arg):\n",
    "    if event == \"call\" and not \"pyenv\" in frame.f_code.co_filename:\n",
    "        trace.append(frame.f_code.co_name)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "63aed71e",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The trace function can be used with the `sys.settrace` functionality. Let's consider our original example function `foo`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4578bdda",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def foo(x):\n",
    "    if x == 0:\n",
    "        return\n",
    "\n",
    "    if x % 2 == 0:\n",
    "        printEven()\n",
    "    else:\n",
    "        printOdd()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8af21fa4",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can produce a trace by calling the `settrace` function before and after running the actual function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5b362ed6",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def foo_traced(x):\n",
    "    global trace\n",
    "    trace = []\n",
    "    sys.settrace(trace_call)\n",
    "    foo(x)\n",
    "    sys.settrace(None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "16e8d84e",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "foo_traced(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8dda1f13",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Here's the calls that have been traced."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "82d97040",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "trace"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9f2e1c28",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Example: Coverage instrumentation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7599fab",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's now look at an analysis that is more fine grained: line coverage."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5fb01a80",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "coverage = []"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "60390971",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Using Python's tracer API, this is easy to do."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ce725960",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def trace_lines(frame, event, arg):\n",
    "    if event == 'line' and not \"pyenv\" in frame.f_code.co_filename:\n",
    "        global coverage\n",
    "        function_name = frame.f_code.co_name\n",
    "        lineno = frame.f_lineno\n",
    "        coverage.append(function_name +\":\" + str(lineno))\n",
    "\n",
    "    return trace_lines"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ce48dc6",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We'll again need a wrapper function that sets and unsets the tracer function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ec7306e1",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def foo_traced(x):\n",
    "    global coverage\n",
    "    coverage = []\n",
    "    sys.settrace(trace_lines)\n",
    "    foo(x)\n",
    "    sys.settrace(None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f3ecf91",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "foo_traced(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bced39ac",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "coverage"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "550d19d0",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Example: Fault Localisation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d604b84",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Given a test suite with at least one failing and at least one passing test case, the aim of fault localisation is to identify those statements in a program that are likely faulty. Intuitively, statements that are primarily executed by failed test cases are more likely to be faulty than those that are primarily executed by passed test cases. In spectrum-based fault localisation this is done by evaluating the similarity of each statement with the the error vector (i.e. the vector of pass/fail verdicts for each statement). There are many different competeing similarity metrics (which we will consider in more details the Software Analysis course)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87c050cf",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The basis for fault localisation is a coverage matrix in which we have coverage information for each statement and each test case. These matrices serve to calculate several factors for each statement:\n",
    "\n",
    "- $e_f$: Number of times the statement has been executed by failing tests.\n",
    "- $e_p$: Number of times the statement has been executed by passing tests.\n",
    "- $n_f$: Number of times the statement has _not_ been executed by failing tests.\n",
    "- $n_p$: Number of times the statement has _not_ been executed by passing tests.\n",
    "\n",
    "Based on these factors, different metrics to calculate the suspiciousness of a program statement have been defined, e.g.:\n",
    "\n",
    "- Tarantula: $\\frac{\\frac{e_f}{e_f+n_f}}{\\frac{e_p}{e_p+n_p} + \\frac{e_f}{e_f+n_f}}$\n",
    "- Barinel: $1 - \\frac{e_p}{e_f + e_p}$\n",
    "- Ochiai: $\\frac{e_f}{\\sqrt{(e_f + n_f) \\cdot (e_f + e_p)}}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "425d4d48",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The `middle` example function takes three parameters and should return the parameter that is the middle one when ranked by size."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "adeb126c",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def middle(x, y, z):\n",
    "    if y < z:\n",
    "        if x < y:\n",
    "            return y\n",
    "        elif x < z:\n",
    "            return y\n",
    "    else:\n",
    "        if x > y:\n",
    "            return y\n",
    "        elif x > z:\n",
    "            return x\n",
    "    return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9be31708",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "middle(2, 3, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b16b9279",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Our implementation of `middle` is buggy, which we can demonstrate by generating some tests and checking the expected values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1915770f",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "341c261d",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "tests = []\n",
    "\n",
    "for i in range(10):\n",
    "    x = random.randrange(10)\n",
    "    y = random.randrange(10)\n",
    "    z = random.randrange(10)\n",
    "    m = sorted([x,y,z])[1]\n",
    "    tests.append((x,y,z,m))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "333d45ba",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's check if our tests can trigger a fault, otherwise we will need to generate some more:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1cc8df9e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for (x,y,z,m) in tests:\n",
    "    result = middle(x,y,z)\n",
    "    if result != m:\n",
    "        print(f\"Failed test: {x},{y},{z} == {result} but should be {m}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8dd00001",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We will consider the program at the level of its lines:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8aae9e59",
   "metadata": {
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "lines = inspect.getsource(middle).splitlines()\n",
    "for i, line in enumerate(lines):\n",
    "    print(f\"{i}: {line}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "330ef683",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In order to apply fault localisation we need to trace test executions and keep track of which lines were executed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "195c27dc",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "trace = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "292f5e6c",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def trace_lines(frame, event, arg):\n",
    "    if event == 'line' and not \"pyenv\" in frame.f_code.co_filename:\n",
    "        global trace\n",
    "        lineno = frame.f_lineno\n",
    "        trace.append(lineno)\n",
    "\n",
    "    return trace_lines"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "30fea192",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def middle_instrumented(x,y,z):\n",
    "    global trace\n",
    "    sys.settrace(trace_lines)\n",
    "    trace = []\n",
    "    ret = middle(x,y,z)\n",
    "    sys.settrace(None)\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "25a95b5c",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "middle_instrumented(1,2,3)\n",
    "trace"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "85b37d31",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "middle_instrumented(3,4,1)\n",
    "trace"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0997a6b4",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Now we can derive an execution spectrum for the `middle` function using our tests."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "26ad6137",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "76a49bb1",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def get_spectrum(tests, statements):\n",
    "    matrix = []\n",
    "    for (x,y,z,m) in tests:\n",
    "        row = []\n",
    "        result = middle_instrumented(x,y,z)\n",
    "        for lineno in statements:\n",
    "            if lineno in trace:\n",
    "                row.append(1)\n",
    "            else:\n",
    "                row.append(0)\n",
    "        if result == m:\n",
    "            row.append(1)\n",
    "        else:\n",
    "            row.append(0)\n",
    "        matrix.append(row)\n",
    "    \n",
    "    spectrum = pd.DataFrame(matrix, columns=statements + [\"Passed\"])\n",
    "    return spectrum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "506c86a2",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "statements = [i for i in range(len(lines))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8d0c7b11",
   "metadata": {
    "scrolled": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "spectrum = get_spectrum(tests, statements)\n",
    "spectrum"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04043e81",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's calculate Barinel using this spectrum (since it's the simplest formula)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dd28a07f",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def get_suspiciousness(line, spectrum):\n",
    "    \n",
    "    if line not in spectrum.columns:\n",
    "        return 0\n",
    "    \n",
    "    # Number of times the statement has been executed by failing tests.\n",
    "    e_f = spectrum[(spectrum[\"Passed\"] == 0) & (spectrum[line] == 1)].size\n",
    "    \n",
    "    # Number of times the statement has been executed by passing tests.\n",
    "    e_p = spectrum[(spectrum[\"Passed\"] == 1) & (spectrum[line] == 1)].size\n",
    "\n",
    "    if e_p + e_f == 0:\n",
    "        return 0\n",
    "    \n",
    "    suspiciousness = 1 - e_p / (e_p + e_f)\n",
    "        \n",
    "    return suspiciousness"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8645bd68",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's visualise the result by highlighting suspicious lines."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1c189df5",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "lines = inspect.getsource(middle).splitlines()\n",
    "for i in range(len(lines)):\n",
    "    line = lines[i]\n",
    "    suspiciousness = get_suspiciousness(i+1, spectrum)\n",
    "    if suspiciousness > 0.5:\n",
    "        print(\"\\x1b[0;30;41m%2d: %s\\x1b[0m\" % (i, line))\n",
    "    elif suspiciousness > 0.3:\n",
    "        print(\"\\x1b[0;30;43m%2d: %s\\x1b[0m\" % (i, line))\n",
    "    else:\n",
    "        print(\"%2d: %s\" % (i, line))\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c356ff98",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Example: Dynamic Purity Analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4e2f3c8",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Now let's look at an analysis we could also do statically: The aim of purity analysis is to decide whether a given function has side-effects or not. We consider an object-oriented case, and try to find out if individual methods can lead to changes to attributes of the objects (=impure) or do not change the state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f4731be7",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class Example:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.attribute = 0\n",
    "    \n",
    "    def pure_method(self, x):\n",
    "        return x\n",
    "    \n",
    "    def impure_method(self, x):\n",
    "        if x != 0:\n",
    "            self.attribute = x\n",
    "        \n",
    "    def complex_method(self, x):\n",
    "        if x == 0:\n",
    "            self.impure_method(x)\n",
    "        else:\n",
    "            self.pure_method(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1511f645",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Unfortunately we cannot use `inspect` to parse the source code of the class in the Jupyter notebook like we did for methods, so we'll define the source code as a string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "480148fb",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "source =\"\"\"\n",
    "class Example:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.attribute = 0\n",
    "    \n",
    "    def pure_method(self, x):\n",
    "        return x\n",
    "    \n",
    "    def impure_method(self, x):\n",
    "        if x != 0:\n",
    "            self.attribute = x\n",
    "        \n",
    "    def complex_method(self, x):\n",
    "        if x == 0:\n",
    "            self.impure_method(x)\n",
    "        else:\n",
    "            self.pure_method(x)\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d6655a6f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Doesn't work in a Jupyter notebook\n",
    "#source = inspect.getsource(Example.pure_method)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "23186bf3",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "node = ast.parse(source)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "59c8abc0",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can look at the AST of the class as usual."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "64d54d50",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "ag = AstGraphGenerator(source)\n",
    "ag.visit(node)\n",
    "ag.graph"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3f585b9",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "A simple static analysis could decide on purity by determining whether there is a path that reaches an attribute write operation. While this would work well for `pure_method` and `impure_method`, the `complex_method` would statically be declared impure as there is a path from `complex_method` to `impure_method` that can set the attribute. However, it is only called with argument `0` in which case the `impure_method` does _not_ set the attribute!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b69c18b7",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "A simple dynamic analysis would instrument the code to track all write operations on attributes, and then can simply check if any such operations occurred in order to decide whether a function is pure or not."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ec7b1c89",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class PurityTransformer(ast.NodeTransformer):\n",
    "\n",
    "    def visit_Assign(self, node):\n",
    "        assignment_statements = []\n",
    "        for target in node.targets:\n",
    "            if isinstance(target, ast.Attribute) and isinstance(target.ctx, ast.Store):\n",
    "                trace_write = ast.Expr(ast.Call(func=ast.Name(\"trace_write\", ast.Load()),\n",
    "                                args=[ast.Constant(value=target.attr)],\n",
    "                                keywords=[],\n",
    "                                starargs=None,\n",
    "                                kwargs=None))\n",
    "                assignment_statements.append(trace_write)\n",
    "        \n",
    "        return assignment_statements + [node]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db19b60c",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Here's our instrumentation code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aa4d48f1",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def create_instrumented_function(source):\n",
    "    node = ast.parse(source)\n",
    "    node = PurityTransformer().visit(node)\n",
    "\n",
    "    # Make sure the line numbers are ok so that it compiles\n",
    "    node = ast.fix_missing_locations(node)\n",
    "\n",
    "    # Compile and add the instrumented function to the current module\n",
    "    current_module = sys.modules[__name__]\n",
    "    code = compile(node, filename=\"<ast>\", mode=\"exec\")\n",
    "    exec(code, current_module.__dict__)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0594d5e3",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "create_instrumented_function(source)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bd088981",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's first just check if we the instrumentation works."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "facd4350",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def trace_write(x):\n",
    "    print(f\"Writing attribute: {x}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0039ce8a",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "example = Example()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ebdfb0d9",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "example.pure_method(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e9a5feda",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "example.impure_method(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "64fbce25",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "example.complex_method(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "414de289",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "example.complex_method(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cbe135ad",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's now turn this into a full analysis. Our trace function can be as simple as a Boolean that tells us whether a change has happened."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6d4a317c",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "pure = False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8e619a95",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def trace_write(x):\n",
    "    global pure\n",
    "    pure = False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "424bb21d",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The purity analysis consists of running a bunch of tests on each method, and checking this boolean. We will simply generate some random inputs for our program -- we don't need actual tests, just executions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b5d85ccd",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "pure = True\n",
    "for i in range(1000):\n",
    "    x = random.randrange(10)\n",
    "    example.pure_method(x)\n",
    "    if not pure:        \n",
    "        break\n",
    "\n",
    "if pure:\n",
    "    print(f\"Method pure_method is pure\")\n",
    "else:\n",
    "    print(f\"Method pure_method is impure\")    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6030e910",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "pure = True\n",
    "for i in range(1000):\n",
    "    x = random.randrange(10)\n",
    "    example.impure_method(x)\n",
    "    if not pure:        \n",
    "        break\n",
    "\n",
    "if pure:\n",
    "    print(f\"Method impure_method is pure\")\n",
    "else:\n",
    "    print(f\"Method impure_method is impure\")    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9b4abc9e",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "pure = True\n",
    "for i in range(1000):\n",
    "    x = random.randrange(10)\n",
    "    example.complex_method(x)\n",
    "    if not pure:        \n",
    "        break\n",
    "\n",
    "if pure:\n",
    "    print(f\"Method complex_method is pure\")\n",
    "else:\n",
    "    print(f\"Method complex_method is impure\")    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f8c51af",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Delta Debugging"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "584229ba",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Since we have already considered dynamic slicing and spectrum based fault localisation, let's also look at a related automated debugging technique, which originates from Passau: Delta Debugging."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16ea6cf1",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We are going to simulate the challenge of simplifying an HTML test input, based on the Mozilla bug described in the lecture. A real automated test would consist of launching the Mozilla browser and loading a page that checks if the crash still occurs. We simulate this by checking if the HTML page still contains a `<SELECT>` tag."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8073fb4f",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "986fb683",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def test(s):\n",
    "    print(s, len(s))\n",
    "    if re.search(\"<SELECT[^>]*>\", s):\n",
    "        return \"FAIL\"\n",
    "    else:\n",
    "        return \"PASS\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "40834fc5",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Delta debugging is based on a binary search in the input space of our program. A binary search would split the input into two halves, and continue searching in the half that still makes the test fail."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f6d31f37",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def simplify(s):\n",
    "    assert test(s) == \"FAIL\"\n",
    "\n",
    "    print(s, len(s))\n",
    "    split = len(s)//2\n",
    "    s1 = s[:split]\n",
    "    s2 = s[split:]\n",
    "\n",
    "    if test(s1) == \"FAIL\":\n",
    "        return simplify(s1)\n",
    "    if test(s2) == \"FAIL\":\n",
    "        return simplify(s2)\n",
    "    return s"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f01a535c",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Here's how this works."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4ed2dd34",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "simplify('<SELECT><OPTION VALUE=\"simplify\"><OPTION VALUE=\"beautify\"></SELECT>')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a90e45ad",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "But now let's try this example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0c8d1737",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "simplify('<SELECT>foo</SELECT>')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2833bdc9",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "This input is not minimal, since the binary search has reached a point where both halves make the test pass. Delta debugging continues the binary search with increased granularity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0439e003",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def ddmin(s):\n",
    "    assert test(s) == \"FAIL\"\n",
    "\n",
    "    n = 2\n",
    "    while len(s) >= 2:\n",
    "        start = 0\n",
    "        subset_length = len(s) // n\n",
    "        some_complement_is_failing = False\n",
    "\n",
    "        while start < len(s):\n",
    "            complement = s[:start] + s[start + subset_length:]\n",
    "\n",
    "            if test(complement) == \"FAIL\":\n",
    "                s = complement\n",
    "                n = max(n - 1, 2)\n",
    "                some_complement_is_failing = True\n",
    "                break\n",
    "            start += subset_length\n",
    "\n",
    "        if not some_complement_is_failing:\n",
    "            if len(s) == n:\n",
    "                break\n",
    "            n = min(n * 2, len(s))\n",
    "\n",
    "    return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "884d6e8e",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "ddmin('<SELECT><OPTION VALUE=\"simplify\"><OPTION VALUE=\"beautify\"></SELECT>')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a0425fd9",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "ddmin('<SELECT>foo</SELECT>')"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}