7 Interprocedural Analysis.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "9c55f10a",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Interprocedural Analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b58c88b8",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Control flow"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b65a866b",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We first start by re-defining the already established aspects of our control flow graph. Since our aim is to combine multiple methods, we update our node labels to include the method name, and not just the line number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bd887bb4",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import javalang"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9ef5ce79",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class CFGNode:\n",
    "    def __init__(self, graph, method_name, ast_node):\n",
    "        self.graph = graph\n",
    "        self.method_name = method_name\n",
    "        self.ast_node = ast_node\n",
    "        \n",
    "    def __str__(self):\n",
    "        if type(self.ast_node) == str:\n",
    "            return self.method_name + \"_\" + self.ast_node\n",
    "        else:\n",
    "            return self.method_name + \"_\" + str(self.ast_node.position.line - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "866f7b90",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class StartNode:\n",
    "    \n",
    "    def __init__(self, graph, method_name, ast_node):\n",
    "        self.graph = graph\n",
    "        self.method_name = method_name\n",
    "        self.ast_node = ast_node\n",
    "    \n",
    "    def __str__(self):\n",
    "        return self.method_name + \"_Start\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cd75eda1",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class ProgramGraph:\n",
    "    def __init__(self, graph, start, end):\n",
    "        self.graph = graph\n",
    "        self.start = start\n",
    "        self.end   = end\n",
    "        \n",
    "    def nodes(self):\n",
    "        return self.graph.nodes()\n",
    "    \n",
    "    def edges(self):\n",
    "        return self.graph.edges()\n",
    "    \n",
    "    def successors(self, node):\n",
    "        return self.graph.successors(node)\n",
    "    \n",
    "    def predecessors(self, node):\n",
    "        return self.graph.predecessors(node)\n",
    "    \n",
    "    def reverse(self):\n",
    "        reverse_cfg = self.graph.reverse()\n",
    "        return ProgramGraph(reverse_cfg, self.end, self.start)    \n",
    "    \n",
    "    def plot(self):\n",
    "        pos = nx.nx_agraph.graphviz_layout(self.graph, prog=\"dot\")\n",
    "        nx.draw_networkx_nodes(self.graph, pos=pos, node_size=800, node_color='#FFFFFF', edgecolors='#000000')\n",
    "        nx.draw_networkx_edges(self.graph, pos=pos, connectionstyle=\"arc\", arrowsize=20)\n",
    "        nx.draw_networkx_labels(self.graph, pos=pos)\n",
    "        nx.draw_networkx_edge_labels(self.graph, pos=pos, edge_labels=nx.get_edge_attributes(self.graph,'label'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "917165c8",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ed2282f9",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from functools import singledispatchmethod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9142a09e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class CFGBuilder:\n",
    "    def __init__(self, method_declaration):\n",
    "        # create graph\n",
    "        self.graph = nx.DiGraph()\n",
    "        self.method_name = method_declaration.name\n",
    "        \n",
    "        # create entry/end node\n",
    "        self.start = StartNode(self.graph, self.method_name, method_declaration)\n",
    "        self.end   = CFGNode(self.graph, self.method_name, \"End\")\n",
    "        self.graph.add_node(self.start)\n",
    "        self.graph.add_node(self.end)\n",
    "        \n",
    "        # set entry as current target\n",
    "        self.frontier = [ self.start ]\n",
    "        \n",
    "        for node in method_declaration.body:\n",
    "            self.add_node(node)\n",
    "            \n",
    "        # Add edges from last nodes to end node\n",
    "        for parent in self.frontier:\n",
    "            self.graph.add_edge(parent, self.end)\n",
    "\n",
    "    def create_graph(self):\n",
    "        return ProgramGraph(self.graph, self.start, self.end)\n",
    "    \n",
    "    @singledispatchmethod\n",
    "    def add_node(self, node):\n",
    "        pass\n",
    "    \n",
    "    @add_node.register        \n",
    "    def add_block_node(self, block_node: javalang.tree.BlockStatement):\n",
    "        for node in block_node.statements:\n",
    "            self.add_node(node)            \n",
    "    \n",
    "    @add_node.register\n",
    "    def add_statement_node(self, node: javalang.tree.StatementExpression):\n",
    "        cfg_node = CFGNode(self.graph, self.method_name, node)\n",
    "        self.graph.add_node(cfg_node)\n",
    "        for parent in self.frontier:\n",
    "            self.graph.add_edge(parent, cfg_node)\n",
    "        self.frontier = [ cfg_node ]\n",
    "        \n",
    "    @add_node.register\n",
    "    def add_declaration_node(self, node: javalang.tree.LocalVariableDeclaration):\n",
    "        self.add_statement_node(node)\n",
    "        \n",
    "    @add_node.register\n",
    "    def add_if_node(self, if_node: javalang.tree.IfStatement):\n",
    "        cfg_node = CFGNode(self.graph, self.method_name, if_node)\n",
    "        self.graph.add_node(cfg_node)\n",
    "\n",
    "        for parent in self.frontier:\n",
    "            self.graph.add_edge(parent, cfg_node)\n",
    "        self.frontier = [cfg_node]\n",
    "        self.add_node(if_node.then_statement)\n",
    "        \n",
    "        if if_node.else_statement:\n",
    "            current_frontier = self.frontier[:]\n",
    "            self.frontier = [cfg_node]\n",
    "            self.add_node(if_node.else_statement)\n",
    "            self.frontier.extend(current_frontier)\n",
    "        else:\n",
    "            self.frontier.append(cfg_node)\n",
    "            \n",
    "    @add_node.register\n",
    "    def add_while_node(self, while_node: javalang.tree.WhileStatement):\n",
    "        cfg_node = CFGNode(self.graph, self.method_name, while_node)\n",
    "        self.graph.add_node(cfg_node)\n",
    "        for parent in self.frontier:\n",
    "            self.graph.add_edge(parent, cfg_node)\n",
    "        self.frontier = [cfg_node]\n",
    "        self.add_node(while_node.body)\n",
    "        for parent in self.frontier:\n",
    "            self.graph.add_edge(parent, cfg_node)\n",
    "        self.frontier = [cfg_node]\n",
    "\n",
    "    @add_node.register\n",
    "    def add_return_node(self, return_node: javalang.tree.ReturnStatement):\n",
    "        cfg_node = CFGNode(self.graph, self.method_name, return_node)\n",
    "        self.graph.add_node(cfg_node)\n",
    "        for parent in self.frontier:\n",
    "            self.graph.add_edge(parent, cfg_node)\n",
    "        self.graph.add_edge(cfg_node, self.end)\n",
    "        self.frontier = [] "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1799d80b",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "This time we want to keep track of multiple methods, so we keep track of the known methods with a dictionary `methods`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7c35fb6d",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "methods = {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7214cdb5",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def parse_method(code):\n",
    "    class_code = \"class Dummy {\\n\" + code + \"\\n}\";\n",
    "    tokens = javalang.tokenizer.tokenize(class_code)\n",
    "    parser = javalang.parser.Parser(tokens)\n",
    "    ast = parser.parse()\n",
    "    _, node = list(ast.filter(javalang.tree.MethodDeclaration))[0]\n",
    "    methods[node.name] = node\n",
    "    return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f566765",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "code1 = \"\"\"\n",
    "  public int foo(int x) {\n",
    "    int y = 0;\n",
    "\n",
    "    while (!bar(y)) {\n",
    "        int tmp = x;\n",
    "        if(tmp % 2 == 0)\n",
    "            y = x;\n",
    "        x--;\n",
    "    }\n",
    "\n",
    "    return y;\n",
    "  }\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f56dce74",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code2 = \"\"\"\n",
    "  public boolean bar(int x) {\n",
    "    if (x == 42) {\n",
    "      return true;\n",
    "    } else {\n",
    "      return false;\n",
    "    }\n",
    "  }\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e7ee5051",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "tree1 = parse_method(code1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4784c96c",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "tree2 = parse_method(code2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d4727289",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "cfg1 = CFGBuilder(methods[\"foo\"]).create_graph()\n",
    "cfg2 = CFGBuilder(methods[\"bar\"]).create_graph()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bfd47d06",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "cfg1.plot()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "12706ebe",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "cfg2.plot()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "548772b8",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Super-CFG"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8ff6c58",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Now that we have multiple methods, we can combine them in a super-control flow graph. For this, we need to determine for a given node whether it calls another function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "492e4e89",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def get_children(root):\n",
    "    children = None\n",
    "\n",
    "    if isinstance(root, javalang.tree.Node):\n",
    "        yield root\n",
    "        children = root.children\n",
    "    else:\n",
    "        children = root\n",
    "\n",
    "    for child in children:\n",
    "        if isinstance(child, javalang.tree.Statement):\n",
    "            continue\n",
    "    \n",
    "        if isinstance(child, (javalang.tree.Node, list, tuple)):\n",
    "            for node in get_children(child):\n",
    "                yield node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c940829d",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class CFGNode(CFGNode):\n",
    "    def calls(self):\n",
    "        calls = set()\n",
    "        if not self.ast_node or isinstance(self.ast_node, str):\n",
    "            return calls\n",
    "        \n",
    "        for node in get_children(self.ast_node):\n",
    "            if isinstance(node, javalang.tree.MethodInvocation):\n",
    "                calls.add(node)\n",
    "                \n",
    "        return calls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3ebb0dd3",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class StartNode(StartNode):\n",
    "    def calls(self):\n",
    "        return set()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8e2ef308",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "cfg1 = CFGBuilder(tree1).create_graph()\n",
    "cfg2 = CFGBuilder(tree2).create_graph()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2c175a0d",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for node in cfg1.nodes():\n",
    "    for call in node.calls():\n",
    "        print(f\"Node {node} calls {call.member}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f52ded4",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Now let's define a function that expands a given control flow graph with all the control flow implied by method calls."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "45664ffe",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def build_super_cfg(cfg):\n",
    "    \n",
    "    graph = nx.DiGraph()\n",
    "    \n",
    "    # Copy over original nodes\n",
    "    graph.add_nodes_from(cfg.graph.nodes())\n",
    "    graph.add_edges_from(cfg.graph.edges())        \n",
    "\n",
    "    # Find all method calls\n",
    "    for node in cfg.nodes():\n",
    "        for call in node.calls():\n",
    "            # Retrieve cfg of called method\n",
    "            cfg2 = CFGBuilder(methods[call.member]).create_graph()\n",
    "\n",
    "            # Add all nodes and edges of called method\n",
    "            graph.add_nodes_from(cfg2.graph.nodes())\n",
    "            graph.add_edges_from(cfg2.graph.edges())\n",
    "\n",
    "            # Connect calling node with start/end of new CFG\n",
    "            graph.add_edge(node, cfg2.start)\n",
    "            graph.add_edge(cfg2.end, node)\n",
    "\n",
    "    return ProgramGraph(graph, cfg.start, cfg.end)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9308e7b5",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "scfg = build_super_cfg(cfg1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2050b56a",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "scfg.plot()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf669572",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "There is an issue with this direct integration: It creates possible loops in the method calls, which are not actually feasible. We therefore have to split method calls into call and return site."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4fe138e3",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class CallNode(CFGNode):\n",
    "    def __init__(self, graph, method_name, ast_node, called_cfg):\n",
    "        self.graph = graph\n",
    "        self.method_name = method_name\n",
    "        self.ast_node    = ast_node\n",
    "        self.called_cfg  = called_cfg\n",
    "    \n",
    "    def __str__(self):\n",
    "        return self.method_name + \"_\" + str(self.ast_node.position.line - 1) + \" (Call)\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ae16c850",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class ReturnNode(CFGNode):\n",
    "    \n",
    "    def __init__(self, graph, method_name, ast_node, return_node):\n",
    "        self.graph = graph\n",
    "        self.method_name = method_name\n",
    "        self.ast_node = ast_node\n",
    "        self.return_node = return_node\n",
    "\n",
    "    def __str__(self):\n",
    "        return self.method_name + \"_\" + str(self.ast_node.position.line - 1) + \" (Return)\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "feec76bc",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def build_super_cfg(cfg):\n",
    "    graph = nx.DiGraph()\n",
    "    graph.add_edges_from(cfg.graph.edges())\n",
    "    graph.add_nodes_from(cfg.graph.nodes())\n",
    "\n",
    "    for node in cfg.nodes():\n",
    "        if node.calls():\n",
    "            for call in node.calls():\n",
    "                # Retrieve cfg2\n",
    "                cfg2 = CFGBuilder(methods[call.member]).create_graph()\n",
    "\n",
    "                # Add all nodes and edges\n",
    "                graph.add_nodes_from(cfg2.graph.nodes())\n",
    "                graph.add_edges_from(cfg2.graph.edges())\n",
    "\n",
    "                call_node   = CallNode(graph, node.method_name, node.ast_node, cfg2.start)\n",
    "                return_node = ReturnNode(graph, node.method_name, node.ast_node, cfg2.end)\n",
    "                for p in graph.predecessors(node):                    \n",
    "                    graph.add_edge(p, call_node)\n",
    "                for p in graph.successors(node):                    \n",
    "                    graph.add_edge(return_node, p)\n",
    "                graph.remove_node(node)\n",
    "                \n",
    "                graph.add_edge(call_node, cfg2.start)\n",
    "                graph.add_edge(cfg2.end, return_node)\n",
    "                graph.add_edge(call_node, return_node)\n",
    "\n",
    "    return ProgramGraph(graph, cfg.start, cfg.end)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3bc260f0",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "cfg1 = CFGBuilder(tree1).create_graph()\n",
    "cfg2 = CFGBuilder(tree2).create_graph()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6f8a1dd6",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "cfg1.plot()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bc97db9f",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "cfg2.plot()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "132679bf",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "scfg = build_super_cfg(cfg1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0e976f10",
   "metadata": {
    "scrolled": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "scfg.plot()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1f3e6f1",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Better Plotting"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15777e3b",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "This is a terrible plot. Unfortunately, networkx isn't great for creating a cleaner version, so let's define a version using GraphViz directly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f8e8f789",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from graphviz import Digraph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9071d6d7",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class ProgramGraph(ProgramGraph):\n",
    "    def dot(self):\n",
    "        graph = Digraph(graph_attr = {\"rankdir\" :  \"TB\" })\n",
    "        \n",
    "        methods = set([ node.method_name for node in self.nodes() ] )\n",
    "        clusters = {}\n",
    "        for method in methods:\n",
    "            clusters[method] = Digraph(name = f\"cluster_{method}\")\n",
    "        \n",
    "        clusters[self.start.method_name].node(str(self.start))\n",
    "        clusters[self.start.method_name].node(str(self.end))\n",
    "        \n",
    "        for node in self.nodes():\n",
    "            clusters[node.method_name].node(str(node))\n",
    "        \n",
    "        for subgraph in clusters.values():\n",
    "            graph.subgraph(subgraph)\n",
    "            \n",
    "        for (node1, node2) in self.edges():\n",
    "            graph.edge(str(node1), str(node2))\n",
    "        \n",
    "        return graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4129f717",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "scfg = build_super_cfg(cfg1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a3f89ca1",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "scfg.dot()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a4dbe0c",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Dataflow Analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5ce42e77",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's assume our objective is to apply our zero-analysis to the following code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fb8981bf",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code1 = \"\"\"\n",
    "  public int foo() {\n",
    "\n",
    "    int x = 5;\n",
    "    int y = bar(x);\n",
    "    int z = x/y;\n",
    "\n",
    "    return z;\n",
    "  }\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ce91de4e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code2 = \"\"\"\n",
    "  public int bar(int a) {\n",
    "    return a;\n",
    "  }\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9edc2ccd",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "tree1 = parse_method(code1)\n",
    "tree2 = parse_method(code2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2bb850ee",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "cfg1 = CFGBuilder(tree1).create_graph()\n",
    "cfg2 = CFGBuilder(tree2).create_graph()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3e976b14",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "scfg = build_super_cfg(cfg1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b067f180",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "scfg.dot()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b7059377",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Analysis code"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1af57fe",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We'll need to re-introduce all the analysis code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d55085eb",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class ProgramLattice(object):\n",
    "    def __init__(self, variables, lattice):\n",
    "        self.variables = variables\n",
    "        self.lattice   = lattice\n",
    "        self.values    = {}\n",
    "        for var in variables:\n",
    "            self.values[var] = lattice.bottom\n",
    "\n",
    "    @property\n",
    "    def bottom(self):\n",
    "        new_lattice = ProgramLattice(self.variables, self.lattice)\n",
    "        for var in self.variables:\n",
    "            new_lattice.values[var] = self.lattice.bottom\n",
    "        return new_lattice\n",
    "    \n",
    "    def join(self, other):\n",
    "        new_lattice = ProgramLattice(self.variables, self.lattice)\n",
    "        for var in self.variables:\n",
    "            new_lattice.values[var] = self.lattice.join(self.values[var], other.values[var])\n",
    "        return new_lattice\n",
    "    \n",
    "    def copy(self):\n",
    "        new_lattice = ProgramLattice(self.variables, self.lattice)\n",
    "        new_lattice.values = self.values.copy()\n",
    "        return new_lattice \n",
    "    \n",
    "    def __le__(self, other):\n",
    "        for var in self.variables:\n",
    "            if not (self.values[var] <= other.values[var]):\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n",
    "    def __str__(self):\n",
    "        result = \"\"\n",
    "        for var, value in self.values.items():\n",
    "            result += f\"{var}: {value}\\n\"\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3ba0cf26",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class DataFlowAnalysis:\n",
    "    def __init__(self, cfg, program_lattice, transfer_function, is_backward):\n",
    "        self.cfg = cfg\n",
    "        if is_backward:\n",
    "            self.cfg = cfg.reverse()\n",
    "            \n",
    "        self.transfer_function = transfer_function\n",
    "        self.lattice = program_lattice\n",
    "        \n",
    "        self.facts = {}\n",
    "        \n",
    "        for node in cfg.nodes():\n",
    "            self.facts[node] = program_lattice.bottom    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e6373792",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class DataFlowAnalysis(DataFlowAnalysis):\n",
    "    def apply(self):\n",
    "            \n",
    "        worklist = [(edge[0], edge[1]) for edge in self.cfg.edges()]\n",
    "        while worklist:\n",
    "            node1, node2 = worklist.pop()\n",
    "            result = self.transfer_function(node1, node2, self.facts[node1])\n",
    "            self.facts[node1] = result\n",
    "            if not (result <= self.facts[node2]):\n",
    "                self.facts[node2] = self.facts[node2].join(result)\n",
    "                for successor in self.cfg.successors(node2):\n",
    "                    worklist.append((node2, successor))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "97732289",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def variables(cfg):\n",
    "    # Assumes parameters are used\n",
    "    variables = set()\n",
    "    for node in cfg.nodes():\n",
    "        for child in get_children(node.ast_node):\n",
    "            if isinstance(child, javalang.tree.MemberReference):\n",
    "                variables.add(child.member)\n",
    "    \n",
    "    return variables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9c090b28",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "variables(scfg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd9d14c1",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Zero-Abstraction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b3ac367c",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from enum import Enum\n",
    "class IntegerValue(Enum):\n",
    "    ZERO = 1\n",
    "    NONZERO = 2\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return self.name"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "86fcceb4",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class Lattice(object):\n",
    "    def __init__(self, elements, join_func, meet_func):\n",
    "        self.elements = elements\n",
    "        self.join = join_func\n",
    "        self.meet = meet_func\n",
    "\n",
    "    def wrap(self, object):\n",
    "        return LatticeElement(self, object)\n",
    "\n",
    "    def element_by_index(self, index):\n",
    "        return LatticeElement(self, self.elements[index])\n",
    "\n",
    "    @property\n",
    "    def top(self):\n",
    "        top = self.wrap(self.elements[0])\n",
    "        for element in self.elements[1:]:\n",
    "            top |= self.wrap(element)\n",
    "        return top\n",
    "\n",
    "    @property\n",
    "    def bottom(self):\n",
    "        bottom = self.wrap(self.elements[0])\n",
    "        for element in self.elements[1:]:\n",
    "            bottom &= self.wrap(element)\n",
    "        return bottom"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "41e49fab",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class LatticeElement():\n",
    "    def __init__(self, lattice, element):\n",
    "        if element not in lattice.elements: raise ValueError('The given value is not a lattice element')\n",
    "        self.lattice = lattice\n",
    "        self.index = lattice.elements.index(element)\n",
    "\n",
    "    @property\n",
    "    def unwrap(self):\n",
    "        return self.lattice.elements[self.index]\n",
    "\n",
    "    def __and__(self, b):\n",
    "        # a.__and__(b) <=> a & b <=> meet(a,b)\n",
    "        return LatticeElement(self.lattice, self.lattice.meet(self.unwrap, b.unwrap))\n",
    "\n",
    "    def __or__(self, b):\n",
    "        # a.__or__(b) <=> a | b <=> join(a,b)\n",
    "        return LatticeElement(self.lattice, self.lattice.join(self.unwrap, b.unwrap))\n",
    "\n",
    "    def __eq__(self, b):\n",
    "        # a.__eq__(b) <=> a = b <=> join(a,b)\n",
    "        return self.unwrap == b.unwrap\n",
    "\n",
    "    def __le__(self, b):\n",
    "        # a <= b if and only if a = a & b,\n",
    "        # or\n",
    "        # a <= b if and only if b = a | b,\n",
    "        a = self\n",
    "        return ( a == a & b ) or ( b == a | b )\n",
    "\n",
    "    def __str__(self):\n",
    "        return str(self.unwrap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bcdacf77",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "powerset = [set(), {IntegerValue.ZERO}, {IntegerValue.NONZERO}, {IntegerValue.ZERO, IntegerValue.NONZERO}]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "66b7d541",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def intersection(a, b):\n",
    "    return a & b \n",
    "\n",
    "def union(a, b):\n",
    "    return a | b "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b7b6b757",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "join = union\n",
    "meet = intersection\n",
    "\n",
    "zero_lattice = Lattice(powerset, join, meet)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "40b64b4e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "zero = zero_lattice.wrap({ IntegerValue.ZERO })\n",
    "nonzero =  zero_lattice.wrap({ IntegerValue.NONZERO })\n",
    "maybezero = zero_lattice.wrap({ IntegerValue.ZERO, IntegerValue.NONZERO })"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "27cefedf",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from functools import singledispatch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "13c6067b",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "@singledispatch\n",
    "def alpha(arg):\n",
    "    raise NotImplementedError(f\"Cannot abstract {arg}\") "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dd634bdb",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "@alpha.register(int)\n",
    "def alpha_number(number):\n",
    "    if number == 0:\n",
    "        return zero\n",
    "    else:\n",
    "        return nonzero"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "98014995",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def abstract_addition(op1, op2):\n",
    "    if op1 == zero_lattice.bottom or op2 == zero_lattice.bottom:\n",
    "        return zero_lattice.bottom\n",
    "    elif op1 == zero:\n",
    "        if  op2 == zero:\n",
    "            return zero\n",
    "        elif op2 == nonzero:\n",
    "            return nonzero\n",
    "    elif op2 == zero and op1 == nonzero:\n",
    "            return nonzero\n",
    "    else:\n",
    "        return maybezero"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a8a07503",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "abstract_subtraction = abstract_addition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "01c4493a",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def abstract_multiplication(op1, op2):\n",
    "    if op1 == zero or op2 == zero:\n",
    "        return zero\n",
    "    elif op1 == nonzero and op2 == nonzero:\n",
    "        return nonzero\n",
    "    elif op1 == maybezero and op2 == maybezero:\n",
    "            return maybezero\n",
    "    else:\n",
    "        return zero_lattice.bottom"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "65b6ecc6",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def abstract_division(op1, op2):\n",
    "    if op2 == zero:\n",
    "        return zero_lattice.bottom\n",
    "    elif op1 == zero_lattice.bottom:\n",
    "        return zero_lattice.bottom\n",
    "    elif op1 == zero:\n",
    "        return zero\n",
    "    elif op1 == nonzero and op2 == nonzero:\n",
    "        return nonzero\n",
    "    elif op1 == nonzero and op2 == maybezero:\n",
    "        return nonzero\n",
    "    elif op1 == zero_lattice.bottom:\n",
    "        return zero_lattice.bottom\n",
    "    else:\n",
    "        return maybezero"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c958675c",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Abstract interpretation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "24340d8f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "As a first change to the last chapter, we need to add code to handle method calls. Let's re-introduce our transfer function for the zero analysis. This is identical code to last time, but in preparation for the coming changes we include the CFG node a statement originates from (though we don't make use of this for now)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6bb471d2",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "@singledispatch\n",
    "def alpha(arg, cfg_node, values):\n",
    "    raise NotImplementedError(f\"Cannot abstract {arg}\") "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "16e76392",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "@alpha.register(int)\n",
    "def alpha_number(number, cfg_node, values = {}):\n",
    "    if number == 0:\n",
    "        return zero\n",
    "    else:\n",
    "        return nonzero"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b84b472d",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "@alpha.register(javalang.tree.Literal)\n",
    "def alpha_literal(lit, cfg_node, values):\n",
    "    return alpha(lit.value, cfg_node, values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c93361cd",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "@alpha.register(javalang.tree.MemberReference)\n",
    "def alpha_member(member, cfg_node, values):\n",
    "    if member.member in values:\n",
    "        return values[member.member]\n",
    "    else:\n",
    "        return zero_lattice.bottom"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "60294426",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "@alpha.register(str)\n",
    "def alpha_string(string, context, values):\n",
    "    return alpha_number((int(string)), context, values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "73c80bcf",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "@alpha.register(javalang.tree.Assignment)\n",
    "def alpha_assignment(assignment, cfg_node, values):\n",
    "    if not isinstance(assignment.expressionl, javalang.tree.MemberReference):\n",
    "        raise NotImplementError(f\"Assignment not implemented for {assignment.expressionl}\")\n",
    "\n",
    "    var = assignment.expressionl.member\n",
    "    values[var] = alpha(assignment.value, cfg_node, values)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a251f30c",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "@alpha.register(javalang.tree.BinaryOperation)\n",
    "def alpha_operation(operation, cfg_node, values):\n",
    "    lhs = alpha(operation.operandl, cfg_node, values)\n",
    "    rhs = alpha(operation.operandr, cfg_node, values)\n",
    "    op  = operation.operator\n",
    "    if op == \"+\":\n",
    "        return abstract_addition(lhs, rhs)\n",
    "    elif op == \"-\":\n",
    "        return abstract_subtraction(lhs, rhs)\n",
    "    elif op == \"*\":\n",
    "        return abstract_multiplication(lhs, rhs)\n",
    "    elif op == \"/\":\n",
    "        return abstract_division(lhs, rhs)\n",
    "    else:\n",
    "        raise NotImplementedError(f\"Operator not implemented: {op}\") "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c5aefc93",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "@alpha.register(javalang.tree.LocalVariableDeclaration)\n",
    "def alpha_declaration(declaration, cfg_node, values):\n",
    "    var = declaration.declarators[0].name\n",
    "    value = alpha(declaration.declarators[0].initializer, cfg_node, values)\n",
    "    values[var] = value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e96db95c",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "@alpha.register(javalang.tree.StatementExpression)\n",
    "def alpha_statement(statement, cfg_node, values):\n",
    "    alpha(statement.expression, cfg_node, values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4fe956f8",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "@alpha.register(javalang.tree.WhileStatement)\n",
    "def alpha_while(whilestatement, cfg_node, values):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fa98325b",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "@alpha.register(javalang.tree.ReturnStatement)\n",
    "def alpha_return(statement, cfg_node, values):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2ae62d86",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "@alpha.register(javalang.tree.IfStatement)\n",
    "def alpha_if(statement, cfg_node, values):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d31da051",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "@alpha.register(javalang.tree.MethodDeclaration)\n",
    "def alpha_method(statement, cfg_node, values):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5fbfd639",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Last time we did not support method calls. For starters, we can just assume that anything can happen with a method call."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d19a65b9",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "@alpha.register(javalang.tree.MethodInvocation)\n",
    "def alpha_methodcall(statement, cfg_node, values):\n",
    "    \n",
    "    # Conservative: Can be anything\n",
    "    return maybezero"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8a226899",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def alpha_trans(node, node2, in_facts):\n",
    "    result = in_facts.copy()\n",
    "    alpha(node.ast_node, node, result.values)\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca80108a",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "First, let's apply the analysis directly to the method `foo`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f513aba1",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "P = ProgramLattice(variables(cfg1), zero_lattice)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "34b56497",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "analysis = DataFlowAnalysis(cfg1, P, alpha_trans, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2dcd8b54",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "analysis.apply()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "07547713",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "for node, facts in analysis.facts.items():\n",
    "    print(f\"{node}: {facts}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "249e3f88",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for i, line in enumerate(code1.split('\\n')):\n",
    "    print(str(i + 1).rjust(3, ' '), ':', line)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d78f15e0",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def check_divisionbyzero(cfg):\n",
    "    for node in cfg.nodes():\n",
    "        for ast_node in get_children(node.ast_node):\n",
    "            if isinstance(ast_node, javalang.tree.BinaryOperation):\n",
    "                if ast_node.operator == \"/\" and isinstance(ast_node.operandr, javalang.tree.MemberReference):\n",
    "                    if zero == analysis.facts[node].values[ast_node.operandr.member]:\n",
    "                        print(f\"Division by zero in line {node.ast_node.position.line - 1}\")\n",
    "                    elif zero <= analysis.facts[node].values[ast_node.operandr.member]:\n",
    "                        print(f\"Potential division by zero in line {node.ast_node.position.line - 1}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1d115f89",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "check_divisionbyzero(cfg1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "daa7ae9f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "This analysis assumes that there can be a division by zero exception in our division, since we did not consider what the call to `bar` actually returns and just assumed it can be anything. However, we know this cannot be the case since we pass in a non-zero argument to `bar`, and it just returns its input again."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8900200",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Interprocedural analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7557716",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To generalise this to an interprocedural analysis, we need to relax our assumption that methods return anything, and instead descend into the super-cfg during our analysis."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3b8f0811",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We need some way to pass values through method parameters and return values. For now, we'll just use a dedicated variable to represent the return value of the function; therefore, we need to make sure this is included in our set of variables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f1dc60d",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def variables(cfg):\n",
    "    variables = set()\n",
    "    methods = set()\n",
    "    \n",
    "    for node in cfg.nodes():\n",
    "        methods.add(node.method_name)\n",
    "        for child in get_children(node.ast_node):\n",
    "            if isinstance(child, javalang.tree.MemberReference):\n",
    "                variables.add(child.member)\n",
    "\n",
    "    for method in methods:\n",
    "        variables.add(\"return_\"+method)\n",
    "    \n",
    "    return variables"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c6f006bd",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "This variable is set in return statements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6e5f425d",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "@alpha.register(javalang.tree.ReturnStatement)\n",
    "def alpha_return(statement, cfg_node, values):\n",
    "    values[\"return_\"+cfg_node.method_name] = alpha(statement.expression, cfg_node, values)\n",
    "    return values[\"return_\"+cfg_node.method_name]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d1e55b2",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Method calls are used in variable declarations and assignments, if we encounter a method call we let our abstraction return the return value stored for this call."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b6d66bf0",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "@alpha.register(javalang.tree.MethodInvocation)\n",
    "def alpha_methodcall(statement, cfg_node, values):\n",
    "\n",
    "    ctx = f\"return_{statement.member}\"\n",
    "    if ctx in values:\n",
    "        return values[ctx]\n",
    "    else:\n",
    "        return zero_lattice.bottom"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c173db05",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Our transfer function needs to handle passing the parameters into functions in the call nodes. We just assign the values used to the variables that represent the arguments in the called method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "41099ac0",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def alpha_trans(node, target_node, in_facts):\n",
    "    result = in_facts.copy()\n",
    "    \n",
    "    if isinstance(node, CallNode):\n",
    "        for _, call in node.ast_node.filter(javalang.tree.MethodInvocation):\n",
    "            called_method = methods[call.member]\n",
    "            num_argument = 0\n",
    "            for argument in call.arguments:\n",
    "                var = called_method.parameters[num_argument].name\n",
    "                result.values[var] |= alpha(argument, target_node, result.values)\n",
    "                num_argument += 1\n",
    "    elif node.ast_node == \"End\":\n",
    "        pass\n",
    "    else:    \n",
    "        alpha(node.ast_node, node, result.values)\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "388763b1",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The analysis now has to be applied to the super-CFG:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ea4c474e",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "P = ProgramLattice(variables(scfg), zero_lattice)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "079481b5",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "analysis = DataFlowAnalysis(scfg, P, alpha_trans, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1e704a22",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "analysis.apply()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "84b47808",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "check_divisionbyzero(scfg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3beb4d97",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "No false positive is reported!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66f0222e",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "What if there is an actual division by zero?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "821fa779",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "code1 = \"\"\"\n",
    "  public int foo() {\n",
    "\n",
    "    int x = 0;\n",
    "    int y = bar(x);\n",
    "    int z = x/y;\n",
    "\n",
    "    return z;\n",
    "  }\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b3a92d1f",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "tree1 = parse_method(code1)\n",
    "tree2 = parse_method(code2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2cef11a5",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "cfg1 = CFGBuilder(tree1).create_graph()\n",
    "cfg2 = CFGBuilder(tree2).create_graph()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d243e6f2",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "scfg = build_super_cfg(cfg1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67ab660d",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "analysis = DataFlowAnalysis(scfg, P, alpha_trans, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2ab37baf",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "analysis.apply()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9e0ff062",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "check_divisionbyzero(scfg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c13cab0",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Imprecision of interprocedural analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "359153ef",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's now consider a case where we call the same function twice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "133859dd",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code1 = \"\"\"\n",
    "  public int foo() {\n",
    "\n",
    "    int x = bar(0);\n",
    "    int y = bar(5);\n",
    "    \n",
    "    z = 5/x;\n",
    "    z = 5/y;\n",
    "\n",
    "    return z;\n",
    "  }\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2b52dfa1",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code2 = \"\"\"\n",
    "  public int bar(int a) {\n",
    "    return a;\n",
    "  }\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ee401e25",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "tree1 = parse_method(code1)\n",
    "tree2 = parse_method(code2)\n",
    "\n",
    "cfg1 = CFGBuilder(tree1).create_graph()\n",
    "cfg2 = CFGBuilder(tree2).create_graph()\n",
    "\n",
    "scfg = build_super_cfg(cfg1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c85f91a7",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "scfg.dot()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d76c15b8",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Line 8 does not contain a division by zero exception, while line 7 does. What does our analysis say?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9dfd3bbd",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "P = ProgramLattice(variables(scfg), zero_lattice)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9d663b7d",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "analysis = DataFlowAnalysis(scfg, P, alpha_trans, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "53ac7198",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "analysis.apply()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c7bd706a",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "check_divisionbyzero(scfg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22beb9c1",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "There indeed is a division by zero in line 7, but line 8 is a false positive."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f33f30d8",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Cloning"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f800776",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "There are multiple different strategies to create context-sensitive analyses. One easy approach is to simply clone the called methods."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "849039cf",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def build_super_cfg_clones(cfg):\n",
    "    graph = nx.DiGraph()\n",
    "    graph.add_edges_from(cfg.graph.edges())    \n",
    "    graph.add_nodes_from(cfg.graph.nodes())    \n",
    "    clones = {}  # To count how many clones there are of each method \n",
    "\n",
    "    for node in cfg.nodes():\n",
    "        calls = node.calls()\n",
    "        if node.calls():\n",
    "            for call in node.calls():\n",
    "                # Retrieve cfg2\n",
    "                cfg2 = CFGBuilder(methods[call.member]).create_graph()\n",
    "\n",
    "                num = 1\n",
    "                if call.member in clones:\n",
    "                    num = clones[call.member] + 1\n",
    "                clones[call.member]  = num\n",
    "\n",
    "                # Add all nodes and edges\n",
    "                for nod in cfg2.graph.nodes():\n",
    "                    nod.method_name += f\"_{num}\"\n",
    "                    nod.graph = graph\n",
    "                    graph.add_node(nod)\n",
    "                graph.add_edges_from(cfg2.graph.edges())\n",
    "\n",
    "                call_node = CallNode(graph, node.method_name, node.ast_node, cfg2.start)\n",
    "                return_node = ReturnNode(graph, node.method_name, node.ast_node, cfg2.end)\n",
    "                for p in graph.predecessors(node):                    \n",
    "                    graph.add_edge(p, call_node)\n",
    "                for p in graph.successors(node):\n",
    "                    graph.add_edge(return_node, p)\n",
    "                graph.remove_node(node)\n",
    "\n",
    "                graph.add_edge(call_node, cfg2.start)\n",
    "                graph.add_edge(cfg2.end, return_node)\n",
    "                graph.add_edge(call_node, return_node)\n",
    "\n",
    "    return ProgramGraph(graph, cfg.start, cfg.end)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8f7b2f08",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "scfg_clones = build_super_cfg_clones(cfg1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "49fa6147",
   "metadata": {
    "scrolled": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "scfg_clones.dot()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8902047c",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "@alpha.register(javalang.tree.MethodInvocation)\n",
    "def alpha_methodcall(statement, cfg_node, values):\n",
    "\n",
    "    for s in cfg_node.graph.predecessors(cfg_node):\n",
    "        if str(s).endswith(\"End\"):\n",
    "            ctx = f\"return_{s.method_name}\"\n",
    "            if ctx in values:\n",
    "                return values[ctx]\n",
    "    return zero_lattice.bottom"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "22097704",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def alpha_trans(node, target_node, in_facts):\n",
    "    result = in_facts.copy()\n",
    "    \n",
    "    if isinstance(node, CallNode):   \n",
    "        for _, call in node.ast_node.filter(javalang.tree.MethodInvocation):\n",
    "            called_method = methods[call.member]\n",
    "            num_argument = 0\n",
    "            for argument in call.arguments:\n",
    "                var = called_method.parameters[num_argument].name\n",
    "                # Assign rather than join\n",
    "                result.values[var] = alpha(argument, target_node, result.values)\n",
    "                num_argument += 1\n",
    "    elif node.ast_node == \"End\":\n",
    "        pass\n",
    "    else:    \n",
    "        alpha(node.ast_node, node, result.values)\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3baf1e6e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "variables(scfg_clones)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3ea3f9cc",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "P = ProgramLattice(variables(scfg_clones), zero_lattice)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7c0f5a1d",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "analysis = DataFlowAnalysis(scfg_clones, P, alpha_trans, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "27550b58",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "analysis.apply()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a343d439",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "check_divisionbyzero(scfg_clones)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "918edfec",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Cloning is just one example of how to create a context-sensitive analysis, and as discussed in the lecture there are some limitations to think of (e.g. recursion)."
   ]
  }
 ],
 "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.10.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}