4 Syntax-based Analysis Part 2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f917932f",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Syntax-based Analysis (Part 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00a535f0",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Generating Parsers"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57780ed7",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In the previous chapter we built a small parser for an example language, extracted parse trees, and used syntax trees to convert source code to a format suitable for machine learning applications. Writing the parser was hard work, even though we only looked at a very simplistic language -- doing the same for \"real\" programming languages would be very cumbersome. Luckily, we don't need to construct parsers by hand, but can resort to compiler construction tools. We will be using [Antlr](https://www.antlr.org/) to have some parsers generated for us."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f99978f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The starting point for a parser generator is a grammar describing the language, as well as lexical information that helps tokenizing raw text. In Antlr, both are specified in the same file; by convention, terminals are named in all caps and specified using regular expressions, while terminals are written in lower case."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75f2343b",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "```\n",
    "grammar Expr1;\n",
    "\n",
    "expr : expr '+' term  |\n",
    "       expr '-' term  |\n",
    "       term;\n",
    "\n",
    "term : DIGIT ;\n",
    "\n",
    "DIGIT : ('0'..'9') ;\n",
    "WS : [ \\t\\r\\n]+ -> skip ;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "593f25a3",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "This grammar tells Antlr to skip whitespacaes (`WS`), to match individual digits (`DIGIT`), and then describes a simple grammar of expressions consisting of addition and subtraction of terms (which are simply individual digits for now)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6b05521",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Antlr will automatically produce a lexer and a parser and some more helpful files for us given such a grammar. To avoid a dependency on Antlr the notebook is not going to call Antlr directly, but we include the files produced by Antlr in the repository directly."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "61d1e995",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "To process the above grammar with Antlr, we would need to save the grammar in a file `Expr1.g4`, and then call Antlr like so:\n",
    "\n",
    "```\n",
    " antlr -Dlanguage=Python3 -visitor Expr1.g4\n",
    "```\n",
    "\n",
    "The `language` option tells Antlr which programming language the parser should be generated in."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a333d3be",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The generated files are included in the `antlr` subdirectory of this notebook's repository."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c21409a6",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "!ls antlr/Expr1*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91a399fc",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "`Expr1Lexer.py` is the tokenizer, `Expr1Parser.py` contains the parser, `Expr1Visitor.py` provides a visitor interface for the parse tree, and `Expr1Listener.py` provides an interface with which we can react to parse events while parsing."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ea0a27d",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Since the generated files are in the `antlr` subdirectory of this notebook's repository, we need to tell Python to include from there."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "17aae5d4",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import sys  \n",
    "sys.path.insert(0, 'antlr')\n",
    "\n",
    "import antlr"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab962340",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We also need to include the Antlr runtime library."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8706a733",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from antlr4 import *"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f38e131",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can now include the generated lexer and parser."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "687845ce",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from Expr1Lexer import Expr1Lexer\n",
    "from Expr1Parser import Expr1Parser"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cd56ca0b",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The pipeline to parse textual input is to (1) generate an input stream based on the text, (2) create a token stream out of the input stream, and (3) invoke the parser to consume the tokens. The parsing is started by invoking the starting rule of the grammar (`expr` in our case)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "79764877",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "input = InputStream('1+2')\n",
    "lexer = Expr1Lexer(input)\n",
    "stream = CommonTokenStream(lexer)\n",
    "parser = Expr1Parser(stream)\n",
    "tree = parser.expr() "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fefc541b",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The result (`tree`) is the parse tree produced by `Expr1Parser`. Antlr provides a helper function to look at the parse tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3a61a20a",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from antlr4.tree.Trees import Trees\n",
    "Trees.toStringTree(tree, None, parser)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b28315b4",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Translating code"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69c25d8a",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can add attributes to the terminals and nonterminals of our grammar in order to store semantic information, and we can interleave code that is executed by the parser during the parsing process. For example, if we want to convert our expressions from infix notation to postfix notation, we can simply add `print` statements at the appropriate locations."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1289e24e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "```\n",
    "grammar Expr2;\n",
    "\n",
    "expr : expr '+' term {print(\"+\")} |\n",
    "       expr '-' term {print(\"-\")} |\n",
    "       term;\n",
    "\n",
    "term : DIGIT {print($DIGIT.text) } ;\n",
    "\n",
    "DIGIT : ('0'..'9') ;\n",
    "WS : [ \\t\\r\\n]+ -> skip ;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf20ebaf",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The resulting lexer and parser are generated by Antlr as usual, and already included in the repository, so we can immediately parse an expression and convert it to postfix notation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "22af819b",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from Expr2Lexer import Expr2Lexer\n",
    "from Expr2Parser import Expr2Parser\n",
    "\n",
    "input = InputStream('1+2+3+4')\n",
    "lexer = Expr2Lexer(input)\n",
    "stream = CommonTokenStream(lexer)\n",
    "parser = Expr2Parser(stream)\n",
    "tree = parser.expr() "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "920c9769",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Changing the language is simply a matter of updating the grammar rules, and rerunning Antlr. For example, if we want to allow our expressions to contain numbers with more than one digit, we could include a new nonterminal `number` that consists of at least one `DIGIT`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0ecc5f56",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "```\n",
    "grammar Expr3;\n",
    "\n",
    "expr : expr '+' term {print(\"+\")} |\n",
    "       expr '-' term {print(\"-\")} |\n",
    "       term;\n",
    "\n",
    "term : number  {print($number.text) } ;\n",
    "\n",
    "number: DIGIT+;\n",
    "\n",
    "DIGIT : ('0'..'9') ;\n",
    "WS : [ \\t\\r\\n]+ -> skip ;\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dc2fa5a7",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from Expr3Lexer import Expr3Lexer\n",
    "from Expr3Parser import Expr3Parser\n",
    "\n",
    "input = InputStream('12+2+443+4')\n",
    "lexer = Expr3Lexer(input)\n",
    "stream = CommonTokenStream(lexer)\n",
    "parser = Expr3Parser(stream)\n",
    "tree = parser.expr() "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dfa133c1",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's make things a bit more challenging and move from these simple expressions to program code. We'll try to parse a simple fictitious language again."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "00349416",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "example = \"\"\"\n",
    "begin\n",
    "  x := 4;\n",
    "  if y > 42 then\n",
    "    x := 10;\n",
    "    while x > 0 do\n",
    "      begin\n",
    "        x := x - 1\n",
    "      end\n",
    "end\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c79e533",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We'll start by defining the grammar for this language."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cb594c98",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "```\n",
    "grammar SimpleProgram;\n",
    "\n",
    "start : statement\n",
    "      ;\n",
    "\n",
    "statement : Identifier ':=' expr        # assignmentStatement\n",
    "          | 'begin' opt_stmts 'end'     # blockStatement\n",
    "          | 'if' expr 'then' statement  # ifStatement\n",
    "          | 'while' expr 'do' statement # whileStatement\n",
    "          ;\n",
    "\n",
    "expr : expr op=('+' | '-' | '>') term  # binaryExpr\n",
    "     | term                      # unaryExpr\n",
    "     ;\n",
    "\n",
    "term : Number\n",
    "     | Identifier\n",
    "     ;\n",
    "\n",
    "opt_stmts : statement ';' opt_stmts\n",
    "          | statement\n",
    "          ;\n",
    "\n",
    "Number : Digit+\n",
    "       ;\n",
    "\n",
    "Identifier : [a-zA-Z_] [a-zA-Z_0-9]*\n",
    "           ;\n",
    "\n",
    "Digit : ('0'..'9') ;\n",
    "WS : [ \\t\\r\\n]+ -> skip ;\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7459079c",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from SimpleProgramLexer import SimpleProgramLexer\n",
    "from SimpleProgramParser import SimpleProgramParser\n",
    "\n",
    "input = InputStream(example)\n",
    "lexer = SimpleProgramLexer(input)\n",
    "stream = CommonTokenStream(lexer)\n",
    "parser = SimpleProgramParser(stream)\n",
    "tree = parser.start() "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "18525203",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "Trees.toStringTree(tree, None, parser)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3372bdb8",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The translation from infix expressions to postfix expressions we did earlier is actually quite similar to the translation from Java source code to Java byte code. Java uses a stack machine, where all operations are performed with regards to an operand stack; thus, similar to a postfix subtraction an operation would take as many operands as it needs from the stack, performs the operation, and pushes the result back on the stack."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a5c1836e",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "To represent our simple program in a bytecode-like notation, we define the following bytecode instructions:\n",
    "- `HALT`: End of execution\n",
    "- `LVALUE`: Load variable onto the stack\n",
    "- `RVALUE`: Store top of stack in a local variable\n",
    "- `LABEL`: Denote a location as jump target\n",
    "- `GOTO`: Unconditional jump to target label\n",
    "- `GOFALSE`: If top of stack represents the value false, then jump to target label\n",
    "- `IADD`: Pop the top two operands from the stack, push result of addition back to stack\n",
    "- `ISUB`: Pop the top two operands from the stack, push result of subtraction back to stack\n",
    "- `CMPGT`: Pop the top two operands from the stack, apply numerical comparison and push integer (0/1) with result back to stack."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe6b0209",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The following annotated version of the grammar prints out a bytecode version of the program, in the same way that our annotated grammar converted infix to postfix notation expressions."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6102319b",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "```\n",
    "grammar Expr4;\n",
    "\n",
    "start : {self.unique_id=10000} statement {\n",
    "print(\"HALT\") }\n",
    "      ;\n",
    "\n",
    "statement : Identifier ':=' expr  {print(\"LVALUE \"+$Identifier.text) }\n",
    "          | 'begin' opt_stmts 'end'\n",
    "          | 'if' expr 'then' {\n",
    "label = str(self.unique_id)\n",
    "self.unique_id += 1\n",
    "print(\"GOFALSE \"+label)\n",
    "          } statement {print(\"LABEL \"+label)\n",
    "          }\n",
    "          | 'while' {\n",
    "label1 = str(self.unique_id)\n",
    "self.unique_id += 1\n",
    "label2 = str(self.unique_id)\n",
    "self.unique_id += 1\n",
    "print(\"LABEL \"+label1)\n",
    "                       }\n",
    "                       expr {\n",
    "print(\"GOFALSE \"+label2)\n",
    "                       }\n",
    "                      'do' statement {\n",
    "print(\"GOTO \"+label1)\n",
    "print(\"LABEL \"+label2)\n",
    "                       }\n",
    "          ;\n",
    "\n",
    "expr : expr '+' term {print(\"IADD\") }\n",
    "     | expr '-' term {print(\"ISUB\") }\n",
    "     | expr '>' term  {print(\"CMPGT\") }\n",
    "     | term\n",
    "     ;\n",
    "     \n",
    "term : Number  {print(\"PUSH \"+$Number.text) }\n",
    "     | Identifier  {print(\"RVALUE \"+$Identifier.text) }\n",
    "     ;\n",
    "\n",
    "opt_stmts : statement ';' opt_stmts\n",
    "          | statement\n",
    "          ;\n",
    "\n",
    "Number : Digit+\n",
    "       ;\n",
    "\n",
    "Identifier : [a-zA-Z_] [a-zA-Z_0-9]*\n",
    "           ;\n",
    "\n",
    "Digit : ('0'..'9') ;\n",
    "WS : [ \\t\\r\\n]+ -> skip ;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0660aea4",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "As in the other cases the result of running Antlr on this grammar are already in the repository, so we can immidately try to parse the `example` code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9eda7b6a",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from Expr4Lexer import Expr4Lexer\n",
    "from Expr4Parser import Expr4Parser\n",
    "\n",
    "input = InputStream(example)\n",
    "lexer = Expr4Lexer(input)\n",
    "stream = CommonTokenStream(lexer)\n",
    "parser = Expr4Parser(stream)\n",
    "tree = parser.start() "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eab59831",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Our goal actually isn't compilation, but we are considering all this to understand where the Abstract Syntax Tree comes from. The datastructure that Antlr gives us is the raw parse tree, which we could interpret as a _concrete_ parse tree. To create an abstract syntax tree, we need to decide on the abstraction, and create a class hierarchy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3496760e",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "node_id = 0\n",
    "\n",
    "class ASTNode:\n",
    "    def __init__(self, name, children = []):\n",
    "        global node_id\n",
    "        self.children = children\n",
    "        self.name = name\n",
    "        self.id = node_id\n",
    "        node_id += 1\n",
    "        \n",
    "    def get_label(self):\n",
    "        return self.name\n",
    "    \n",
    "    def get_id(self):\n",
    "        return str(self.id)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "883df6b8",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We need a unique ID for each node in order to visualize the resulting tree with GraphViz; the graph should show a more readable label for each node (`get_label`). We also need the nodes to be aware of their children, such that we can traverse the tree structure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b80d0bb0",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class Number(ASTNode):\n",
    "    def __init__(self, num):\n",
    "        self.number = num\n",
    "        super().__init__(\"Number\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a9726ed3",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class Identifier(ASTNode):\n",
    "    def __init__(self, name):\n",
    "        self.identifier = name\n",
    "        super().__init__(\"Identifier\")  \n",
    "        \n",
    "    def get_label(self):\n",
    "        return \"Id: \"+str(self.identifier)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "05a8adfd",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class AssignmentStatement(ASTNode):\n",
    "    def __init__(self, identifier, expression):\n",
    "        self.identifier = identifier\n",
    "        self.expression = expression\n",
    "        super().__init__(\"Assignment\", [identifier, expression])        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "de5a134f",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class BlockStatement(ASTNode):\n",
    "    def __init__(self, statements):\n",
    "        self.statements = statements\n",
    "        super().__init__(\"Block\", statements )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d172acf1",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The `BlockStatement` is an example where we are abstracting: The corresponsing node in the concrete syntax tree will be a `Statement` node with three children, the terminals `begin` and `end`, which are irrelevant in our abstraction, and the `opt_stmts`, which is an unnecessary indirection we can avoid by directly adding the statements as children of `BlockStatement`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c0adcec7",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class Expression(ASTNode):\n",
    "    def __init__(self, lhs, rhs, op):\n",
    "        self.lhs = lhs\n",
    "        self.rhs = rhs\n",
    "        self.op  = op\n",
    "        super().__init__(\"Expression\", [lhs, rhs])\n",
    "        \n",
    "    def get_label(self):\n",
    "        return \"Expression: \"+str(self.op)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cbce054f",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class IfStatement(ASTNode):\n",
    "    def __init__(self, expr, then):\n",
    "        self.expr = expr\n",
    "        self.then = then\n",
    "        super().__init__(\"If\", [expr, then])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b0ae65ae",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class WhileStatement(ASTNode):\n",
    "    def __init__(self, expr, body):\n",
    "        self.expr = expr\n",
    "        self.body = body\n",
    "        super().__init__(\"While\", [expr, body])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6181b015",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "One way of creating the AST is by visiting the concrete syntax tree and instantiating appropriate nodes. Antlr has already produced a visitor interface for our `SimpleProgram` grammar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "af1f7765",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from SimpleProgramVisitor import SimpleProgramVisitor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5ca8b4e9",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class ASTBuilder(SimpleProgramVisitor):\n",
    "    def visitStart(self, ctx:SimpleProgramParser.StartContext):\n",
    "        return self.visit(ctx.statement())\n",
    "    \n",
    "    def visitAssignmentStatement(self, ctx):        \n",
    "        return AssignmentStatement(Identifier(ctx.Identifier()), self.visit(ctx.expr()))\n",
    "    \n",
    "    def visitBlockStatement(self, ctx):\n",
    "        return BlockStatement(self.visit(ctx.opt_stmts()))\n",
    "    \n",
    "    def visitIfStatement(self, ctx):\n",
    "        return IfStatement(self.visit(ctx.expr()), self.visit(ctx.statement()))\n",
    "\n",
    "    def visitWhileStatement(self, ctx):\n",
    "        return WhileStatement(self.visit(ctx.expr()), self.visit(ctx.statement()))\n",
    "    \n",
    "    def visitUnaryExpr(self, ctx):\n",
    "        return self.visitTerm(ctx.term())\n",
    "\n",
    "    def visitBinaryExpr(self, ctx):\n",
    "        return Expression(self.visit(ctx.expr()), self.visit(ctx.term()), ctx.op.text)\n",
    "\n",
    "    def visitTerm(self, ctx):\n",
    "        if ctx.getAltNumber() == 0:\n",
    "            return Identifier(ctx.getChild(0).getText())\n",
    "        else:\n",
    "            return Number(ctx.getChild(0).getText())\n",
    "\n",
    "    def visitOpt_stmts(self, ctx):\n",
    "        statements = []\n",
    "        statements.append(self.visit(ctx.statement()))\n",
    "        if ctx.getChildCount() > 1:\n",
    "            remaining_stmts = self.visitOpt_stmts(ctx.opt_stmts())\n",
    "            statements.extend(remaining_stmts)\n",
    "        return statements"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3adf8d50",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's use our non-translating parser for the `SimpleProgram` grammar again."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2b87dcae",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "input = InputStream(example)\n",
    "lexer = SimpleProgramLexer(input)\n",
    "stream = CommonTokenStream(lexer)\n",
    "parser = SimpleProgramParser(stream)\n",
    "tree = parser.start() "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e977c5c",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To create our AST, we just need to apply the visitor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "263a1797",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "builder = ASTBuilder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "effc0ad5",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "tree.accept(builder)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "63a851f9",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "...which of course doesn't tell us anything useful since we have not defined a string representation. Let's rather visualise the tree directly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4b7c7aa6",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from graphviz import Digraph\n",
    "def print_tree(tree, dot = Digraph()):\n",
    "\n",
    "    dot.node(tree.get_id(), tree.get_label())\n",
    "        \n",
    "    for child in tree.children:\n",
    "        dot.edge(tree.get_id(), child.get_id())\n",
    "        print_tree(child, dot)\n",
    "            \n",
    "                 \n",
    "    return dot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aa302c30",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "print_tree(tree.accept(builder))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4c8d87e0",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Of course we could also integrate the AST Node creation directly in the attributed grammar."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bab8ca1f",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "```\n",
    "grammar SimpleProgramAttributed;\n",
    "\n",
    "start returns [node]\n",
    "      : statement {$node = $statement.node }\n",
    "      ;\n",
    "\n",
    "statement returns [node]\n",
    "          : Identifier ':=' expr        {$node = AssignmentStatement(Identifier($Identifier.text), $expr.node) }\n",
    "          | 'begin' opt_stmts 'end'     {$node = BlockStatement($opt_stmts.nodes) }\n",
    "          | 'if' a=expr 'then' statement  {$node = IfStatement($a.node, $statement.node) }\n",
    "          | 'while' a=expr 'do' statement {$node = WhileStatement($a.node, $statement.node) }\n",
    "          ;\n",
    "\n",
    "expr returns [node]\n",
    "     : a=expr op=('+' | '-' | '>') term  {$node = Expression($a.node, $term.node, $op.text) }\n",
    "     | term                            {$node = $term.node }\n",
    "     ;\n",
    "\n",
    "term returns [node]\n",
    "     : Number      {$node = Number($Number.text) }\n",
    "     | Identifier  {$node = Identifier($Identifier.text) }\n",
    "     ;\n",
    "\n",
    "opt_stmts returns [nodes]\n",
    "          : statement ';' opt_stmts  {$nodes = [ $statement.node] + $opt_stmts.nodes }\n",
    "          | statement                {$nodes = [ $statement.node] }\n",
    "          ;\n",
    "\n",
    "Number : Digit+\n",
    "       ;\n",
    "\n",
    "Identifier : [a-zA-Z_] [a-zA-Z_0-9]*\n",
    "           ;\n",
    "\n",
    "Digit : ('0'..'9') ;\n",
    "WS : [ \\t\\r\\n]+ -> skip ;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19b72709",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Linting"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06f2acc4",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The first application of ASTs we looked at last week was to create embeddings from source code. However, the AST is immediately useful also without any machine learning. A common application of ASTs is linting, i.e., checking the AST whether it satisfies certain syntactic rules and whether it matches known patterns of problems. For example, many of the checks that [SpotBugs performs](https://spotbugs.readthedocs.io/en/latest/bugDescriptions.html) are based on the AST."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28710ffa",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's use some Java code snippets for our analysis."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1e183bb2",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code1 = \"\"\"\n",
    "public class Foo {\n",
    "  public void foo(int x) {\n",
    "    System.out.println(\"Hello Clone!\");\n",
    "    int j = 10;\n",
    "    for(int i = 0; i < x; i++) {\n",
    "      System.out.println(\"Another iteration\");\n",
    "    }\n",
    "  }\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ecd87141",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code2 = \"\"\"\n",
    "public class Foo {\n",
    "  public void foo(int x) { System.out.println(\"This is a very long line for the sake of the check\")}\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d4eb9a72",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We'll start by implementing some checks that we can apply directly at the character level. For example, [Checkstyle](https://checkstyle.sourceforge.io/config_sizes.html#FileLength) contains rules to check whether a maximum allowed number of lines is exceeded by a source code file, or if a maximum line length is exceeded."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e4a26c4f",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class FileChecker:\n",
    "    def check(self, code):\n",
    "        lines = code.split('\\n')\n",
    "        return self.checkLines(lines)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f9645d80",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class FileLengthChecker(FileChecker):\n",
    "    def __init__(self):\n",
    "        self.max_length = 6 # Extra small for example\n",
    "        \n",
    "    def checkLines(self, lines):\n",
    "        return len(lines) > self.max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "38685d85",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class LineLengthChecker(FileChecker):\n",
    "    def __init__(self):\n",
    "        self.max_length = 50 # Extra small for example\n",
    "        \n",
    "    def checkLines(self, lines):\n",
    "        long_lines = [line for line in lines if len(line) > self.max_length]\n",
    "        return len(long_lines) > 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe03560b",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The first code example is longer than allowed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "479c191a",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "FileLengthChecker().check(code1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ba0c3187",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The second one isn't."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e7a66e88",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "FileLengthChecker().check(code2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7b51813",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The first contains only short lines."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8b013785",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "LineLengthChecker().check(code1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31ab26bc",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The second one contains a very long line."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5642d619",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "LineLengthChecker().check(code2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1fbdd1f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To extend these basic checks to more complicated syntactical checks, we will use the javalang parser again."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d231bb25",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import javalang"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "526f5124",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class ASTChecker:\n",
    "    def check(self, code):\n",
    "        self.tree = javalang.parse.parse(code)\n",
    "        return self.check_ast(self.tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c379603",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "For example, let's consider the SpotBugs check for [Covariant equals methods](https://spotbugs.readthedocs.io/en/latest/bugDescriptions.html#eq-covariant-equals-method-defined-eq-self-no-object). That is, if there is a method named equals that has a different signature than the one inherited from `java.lang.Object` then this is suspicious code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b72f68e2",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class CovariantEqualsChecker(ASTChecker):\n",
    "    def __init__(self):\n",
    "        self.max_length = 50\n",
    "        \n",
    "    def check_ast(self, ast):\n",
    "        for _, node in ast.filter(javalang.tree.MethodDeclaration):\n",
    "            if node.name == \"equals\":\n",
    "                if len(node.parameters) != 1:\n",
    "                    return True\n",
    "                if node.parameters[0].type.name != \"Object\":\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "08150985",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code3 = \"\"\"\n",
    "public class Foo {\n",
    "  public boolean equals(String str) {\n",
    "    return true;\n",
    "  }\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2f92ddef",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "CovariantEqualsChecker().check(code1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "87c38893",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "CovariantEqualsChecker().check(code3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a06fae8b",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "As another AST example, let's consider the [Format String Newline](https://spotbugs.readthedocs.io/en/latest/bugDescriptions.html#fs-format-string-should-use-n-rather-than-n-va-format-string-uses-newline) check in SpotBugs. The problem matched by this check is whether a formatting string, used in the static method `String.format`, contains an explicit newline character (`\\n`) rather than using the correct newline formatting string (`%n`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4a976a8f",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "code4 = \"\"\"\n",
    "public class Foo {\n",
    "  public void foo(String str) {\n",
    "    String foo = String.format(\"Foo\\n\");\n",
    "    System.out.println(foo);\n",
    "  }\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7718522f",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class FormatStringNewlineChecker(ASTChecker):\n",
    "    def __init__(self):\n",
    "        self.max_length = 50\n",
    "        \n",
    "    def check_ast(self, ast):\n",
    "        for _, node in ast.filter(javalang.tree.MethodInvocation):            \n",
    "            if node.member == \"format\" and \\\n",
    "                len(node.arguments) >= 1 and \\\n",
    "                node.qualifier == \"String\":\n",
    "                if \"\\n\" in node.arguments[0].value:\n",
    "                    return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "59befe8b",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "FormatStringNewlineChecker().check(code1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7126aa11",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "FormatStringNewlineChecker().check(code4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2109b5c3",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "As last example, consider the [Useless control flow](https://spotbugs.readthedocs.io/en/latest/bugDescriptions.html#ucf-useless-control-flow-ucf-useless-control-flow) checker: This describes an if-statement that has no effects since the then-block is empty."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1d7f6f29",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "code5 = \"\"\"\n",
    "public class Foo {\n",
    "  public boolean foo(int x) {\n",
    "    if (x > 0) {\n",
    "    \n",
    "    }\n",
    "    System.out.println(\"Foo\");\n",
    "  }\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3d9b49b9",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class UselessControlFlowChecker(ASTChecker):\n",
    "    def __init__(self):\n",
    "        self.max_length = 50\n",
    "        \n",
    "    def check_ast(self, ast):\n",
    "        for _, node in ast.filter(javalang.tree.IfStatement):\n",
    "            if isinstance(node.then_statement, javalang.tree.BlockStatement):\n",
    "                if not node.then_statement.statements:\n",
    "                    return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67382494",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "UselessControlFlowChecker().check(code1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3587c8d4",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "UselessControlFlowChecker().check(code5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d356c00d",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "code6 = \"\"\"\n",
    "public class Foo {\n",
    "  public Boolean foo(int x) {\n",
    "    return null;\n",
    "  }\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a2b02142",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class BooleanReturnNullChecker(ASTChecker):\n",
    "    def __init__(self):\n",
    "        self.max_length = 50\n",
    "        \n",
    "    def check_ast(self, ast):\n",
    "        for _, node in ast.filter(javalang.tree.MethodDeclaration):\n",
    "            if node.return_type and node.return_type.name == \"Boolean\":\n",
    "                for _, return_stmt in ast.filter(javalang.tree.ReturnStatement):\n",
    "                    expr = return_stmt.expression\n",
    "                    if type(expr) == javalang.tree.Literal and expr.value == \"null\":\n",
    "                            return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "23b70329",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "BooleanReturnNullChecker().check(code1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c31f8806",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "BooleanReturnNullChecker().check(code6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04dc3ea3",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Code2vec"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a9b5fc3",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Although we've already covered the ASTNN approach for creating code embeddings, we will now also consider an alternative approach, which has contributed much to the general idea of code embeddings in the first place:\n",
    "\n",
    "Alon, U., Zilberstein, M., Levy, O., & Yahav, E. (2019). code2vec: Learning distributed representations of code. Proceedings of the ACM on Programming Languages, 3(POPL), 1-29."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ab35341",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We will look at how to embed an individual method using code2vec. For this, let's define a simple helper function that gives us an AST rooted at a method declaration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4c4c50ab",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code = \"\"\"\n",
    "public int sum(int a, int b) {\n",
    "   return a + b + 2;\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "817da8cf",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import javalang"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "356e85bc",
   "metadata": {},
   "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",
    "    return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f5a94576",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "tree = parse_method(code)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "693303ff",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9e1d3a6d",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from graphviz import Digraph\n",
    "def print_tree(tree):\n",
    "    unique_id = 1\n",
    "    dot = Digraph()\n",
    "    for path, node in tree:\n",
    "        dot.node(str(id(node)), str(type(node)))\n",
    "        \n",
    "        for child in node.children:\n",
    "            if isinstance(child, javalang.ast.Node):\n",
    "                dot.edge(str(id(node)), str(id(child)))\n",
    "            elif type(child) == str:\n",
    "                strid = str(unique_id)\n",
    "                unique_id = unique_id + 1\n",
    "                dot.node(strid, child)\n",
    "                dot.edge(str(id(node)), strid)\n",
    "            elif type(child) == list:\n",
    "                for lc in child:\n",
    "                    dot.edge(str(id(node)), str(id(lc)))\n",
    "                 \n",
    "    return dot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c35ad698",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "print_tree(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "887ad650",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In contrast to ASTNN with its statement trees, code2vec looks at the concept of a path context, which is a path between two tokens in the AST.\n",
    "\n",
    "We can easily retrieve a list of all terminals in the AST; for example we could traverse the tree and look for strings or sets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c5c8660d",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "for path, node in tree:\n",
    "    for child in node.children:\n",
    "        if child:\n",
    "            if type(child) is str:\n",
    "                print(\"Terminal: \", child)\n",
    "            elif type(child) is set:\n",
    "                for x in child:\n",
    "                    print(\"Terminal \", x)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f0ca94c8",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's put this into a function that gives us the terminals as well as the corresponding AST nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f99db500",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def get_terminal_nodes(tree):\n",
    "    for path, node in tree:\n",
    "        for child in node.children:\n",
    "            if child:\n",
    "                if type(child) is str and child != \"Dummy\":\n",
    "                    yield(node, child)\n",
    "                elif type(child) is set:\n",
    "                    for x in child:\n",
    "                        yield(node, x)      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d520e745",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "[ terminal for _, terminal in list(get_terminal_nodes(tree))]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c6b24d21",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "A path context is defined as the path between two terminals, so let's pick to two terminals."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d9c833de",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "node1, terminal1 = list(get_terminal_nodes(tree))[-1]\n",
    "node2, terminal2 = list(get_terminal_nodes(tree))[-2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2b59397e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "terminal1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dcde0dda",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "terminal2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d2b40715",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's first construct the path from a root node to a chosen terminal node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1e893f79",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def get_path(tree, node):\n",
    "    if tree == node:\n",
    "        return [tree]\n",
    "    \n",
    "    if type(tree) == list:\n",
    "        for child in tree:\n",
    "            path = get_path(child, node)\n",
    "            if path:\n",
    "                return path  \n",
    "    \n",
    "    if not isinstance(tree, javalang.tree.Node):\n",
    "        return None\n",
    "    \n",
    "    for child in tree.children:\n",
    "        path = get_path(child, node)\n",
    "        if path:\n",
    "            return [tree] + path  \n",
    "    \n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "80a59c6a",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def print_path(path):\n",
    "    result = \"\"\n",
    "    for node in path:\n",
    "        if type(node) == str:\n",
    "            result += node\n",
    "        elif type(node) == list:\n",
    "            result += print_path(node)\n",
    "        else:\n",
    "            result += str(type(node))\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9cf285a6",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "print_path(get_path(tree, node1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0b3c3810",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print_path(get_path(tree, node2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f2949ad0",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "A path context consists of the path up the AST from the first terminal node to the least common ancestor of both terminal nodes, and then down the AST again to the second terminal node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bc0551f2",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def path_context(tree, node1, node2):\n",
    "    path1 = get_path(tree, node2)\n",
    "    path1.reverse()\n",
    "    for i in range(len(path1)):\n",
    "        node = path1[i]\n",
    "        path2 = get_path(node, node1)\n",
    "        if path2:\n",
    "            return (path1[:i], path2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "763e1aa7",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def print_path_context(path_context):\n",
    "    down_path = []\n",
    "    up_path = []\n",
    "    for node in path_context[0]:\n",
    "        if type(node) == str:\n",
    "            up_path.append(node)\n",
    "        else:\n",
    "            up_path.append(node.__class__.__name__)\n",
    "    for node in path_context[1]:\n",
    "        if type(node) == str:\n",
    "            down_path.append(node)\n",
    "        else:\n",
    "            down_path.append(node.__class__.__name__)\n",
    "            \n",
    "    return \"↑\".join(up_path) + \"↑\" + \"↓\".join(down_path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "491f0509",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print_path_context(path_context(tree, node1, node2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4c47aa92",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print_path_context(path_context(tree, node2, node1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9a7591bc",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "terminal1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "31d216d8",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "terminal2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d8fd98d",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To build the embeddings for a method, we next require the path context for every pair of terminal nodes in the AST."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c61df9c6",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "terminals = list(get_terminal_nodes(tree))\n",
    "paths = []\n",
    "for index1 in range(len(terminals)-1):\n",
    "    node1, terminal1 = terminals[index1]\n",
    "    for index2 in range(index1 + 1, len(terminals)):\n",
    "        node2, terminal2 = terminals[index2]\n",
    "        path = path_context(tree, node1, node2)\n",
    "        print(terminal1, \",\", print_path_context(path), \",\", terminal2)\n",
    "        paths.append(path)\n",
    "len(paths)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ff9d5db",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Converting a function to a path context"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "75a873b7",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "method1 = \"\"\"\n",
    "public int sum(int a, int b) {\n",
    "   return a + b + 2;\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6dfab4df",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "method2 = \"\"\"\n",
    "public void printHello(String name) {\n",
    "   System.out.println(\"Hello \" + name +\"! \");\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "88e433a2",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "method3 = \"\"\"\n",
    "public boolean isTheAnswer(int x) {\n",
    "   if (x == 42) {\n",
    "     return true;\n",
    "   } else {\n",
    "     return false;\n",
    "   }\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "32ee9b5e",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def get_method_name(tree):\n",
    "    for _, node in tree.filter(javalang.tree.MethodDeclaration):\n",
    "        return node.name\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8aa73c53",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def get_id(value, dictionary, vocab):\n",
    "    if value in dictionary:\n",
    "        return dictionary[value]\n",
    "    else:\n",
    "        new_id = len(dictionary.keys())\n",
    "        dictionary[value] = new_id\n",
    "        vocab[new_id] = value\n",
    "    return new_id"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e93670de",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from dataclasses import dataclass\n",
    "\n",
    "# collection of all known paths, terminals, and method names in the dataset\n",
    "@dataclass\n",
    "class Vocabulary:\n",
    "    # actual type of the value is not important, put in whatever is best\n",
    "    paths: dict[int, str]\n",
    "    terminals: dict[int, str]\n",
    "    method_names: dict[int, str]\n",
    "\n",
    "vocabulary = Vocabulary({}, {}, {})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "97b68c24",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "train_x = []\n",
    "train_y = []\n",
    "\n",
    "paths = {}\n",
    "method_names = {}\n",
    "terminal_names = {}\n",
    "\n",
    "for method in [method1, method2, method3]:\n",
    "    method_ast = parse_method(method)\n",
    "    name = get_method_name(method_ast)    \n",
    "    method_id = get_id(name, method_names, vocabulary.method_names)\n",
    "    path_contexts = []\n",
    "    \n",
    "    terminals = list(get_terminal_nodes(method_ast))\n",
    "    for index1 in range(len(terminals)-1):\n",
    "        node1, terminal1 = terminals[index1]\n",
    "        terminal1_id = get_id(terminal1, terminal_names, vocabulary.terminals)\n",
    "        for index2 in range(index1 + 1, len(terminals)):\n",
    "            node2, terminal2 = terminals[index2]\n",
    "            terminal2_id = get_id(terminal2, terminal_names, vocabulary.terminals)\n",
    "            path = path_context(method_ast, node1, node2)\n",
    "            path_str = print_path_context(path)\n",
    "            path_id = get_id(path_str, paths, vocabulary.paths)\n",
    "            print(terminal1, \",\", path_str, \",\", terminal2)\n",
    "            print(terminal1_id, \",\", path_id, \",\", terminal2_id)\n",
    "            path_contexts.append((terminal1_id, path_id, terminal2_id))\n",
    "            \n",
    "    train_x.append(path_contexts)\n",
    "    train_y.append(method_id)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5d4ddb86",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "train_x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e16c14b7",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "train_y"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52dc2efb",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "### Representation\n",
    "Each path is represented as a vector $p$ with values that are not known initially. The terminals are each represented by a vector $t$ with unknown elements as well. By concatenating the three parts of a context its representation $c_i = [t_\\mathrm{start}, p, t_\\mathrm{end}]$ is created.\n",
    "To learn how the different parts of $c_i$ relate to each other, a weight matrix $W$ with learnable weights is introduced. The product $\\tilde{c}_i := \\mathrm{tanh}(W \\cdot c_i)$ is then called a *combined context vector* as it now no longer contains just the concatenation of the three separate parts.\n",
    "\n",
    "The whole code snippet/method body is again represented as a single vector $v$. As different contexts of this code snippet are not equally important, the network has to learn which ones actually are. To achieve this, an attention vector that contains a weight $\\alpha_i$ for each context is learned. The code vector $v$ can then be calculated as the weighted sum\n",
    "$$\n",
    "    v := \\sum_{i=1}^{n} \\alpha_i \\cdot \\tilde{c}_i\n",
    "$$\n",
    "\n",
    "\n",
    "Each method name is again represented as a vector $y$ with unknown values. The probability $q(y)$ that a code vector should be associated with this tag is calculated as $q(y) := \\mathrm{softmax}(v^T \\cdot y)$. By performing this calculation for all known tags the one with the highest probability to fit the code can be chosen.\n",
    "\n",
    "### Learned Elements\n",
    "- A vector $c$ as representation for each context as combination of representations $p$ for paths and $t$ for terminals.\n",
    "- A weight matrix $W$ that contains information how the three parts of a context are combined.\n",
    "- An attention weight $\\alpha$ which contains information which contexts in a method are important.\n",
    "- A vector $t$ as representation for each method name."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "14a18d66",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import tensorflow as tf\n",
    "from tensorflow import keras\n",
    "from tensorflow.python.layers.base import Layer\n",
    "from keras import Input, activations, optimizers, losses\n",
    "import keras.backend as kb\n",
    "from keras.layers import Embedding, Concatenate, Dropout, TimeDistributed, Dense\n",
    "\n",
    "# how many paths does the biggest analysed function have\n",
    "MAX_PATHS = 50\n",
    "# length of the vectors that should represent paths and labels (same size for simplicity)\n",
    "EMBEDDING_SIZE = 100\n",
    "# embedding sizes of start, path, end added together\n",
    "CONTEXT_EMBEDDING_SIZE = 3 * EMBEDDING_SIZE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d731da5a",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# Adapted from: https://github.com/tech-srl/code2vec/blob/master/keras_model.py\n",
    "def build_code2vec_model(vocab: Vocabulary):\n",
    "    path_start_token = Input((MAX_PATHS,), dtype=tf.int32)\n",
    "    path_input = Input((MAX_PATHS,), dtype=tf.int32)\n",
    "    path_end_token = Input((MAX_PATHS,), dtype=tf.int32)\n",
    "    # the sets of contexts for each function are padded to contain MAX_PATHS number of paths\n",
    "    context_mask = Input((MAX_PATHS,))\n",
    "\n",
    "    # The elements of the matrix are chosen randomly, as the actual values have to be learned.\n",
    "    paths_embedded = Embedding(len(vocab.paths), EMBEDDING_SIZE,\n",
    "                               name='path_embedding')(path_input)\n",
    "\n",
    "    # Embed terminals the same way as paths.\n",
    "    token_embedding = Embedding(len(vocab.terminals), EMBEDDING_SIZE,\n",
    "                                name='token_embedding')\n",
    "    path_start_token_embedded = token_embedding(path_start_token)\n",
    "    path_end_token_embedded = token_embedding(path_end_token)\n",
    "\n",
    "    # Representation of contexts $c_i$: concatenation of start, path, end\n",
    "    context_embedded = Concatenate()([path_start_token_embedded, paths_embedded, path_end_token_embedded])\n",
    "    # Dropout to prevent overfitting.\n",
    "    context_embedded = Dropout(0.25)(context_embedded)\n",
    "\n",
    "    # $\\tilde{c}_i = tanh(Wc_i)$\n",
    "    # Fully connected layer that learns to combine the three parts of a context.\n",
    "    context_after_dense = TimeDistributed(\n",
    "        Dense(CONTEXT_EMBEDDING_SIZE, use_bias=False,\n",
    "              activation=activations.tanh))(context_embedded)\n",
    "\n",
    "    # AttentionLayer learns which path contexts are the most important.\n",
    "    # A code_vector $v$ now is the final representation for a piece of code.\n",
    "    code_vectors, attention_weights = AttentionLayer(name='attention')([context_after_dense, context_mask])\n",
    "\n",
    "    # $q(y) := softmax(v^T y)$\n",
    "    # Final dense layer: Learn how the method names should be represented.\n",
    "    # For each method name: The probability that a given code vector represents a method name is\n",
    "    # the dot product of those two values after softmax normalisation.\n",
    "    # The target_index is the key of the method name in the vocabulary with the highest probability.\n",
    "    target_index = Dense(len(vocab.method_names), use_bias=False,\n",
    "                         activation=activations.softmax, name='target_index')(\n",
    "        code_vectors)\n",
    "\n",
    "    inputs = [path_start_token, path_input, path_end_token, context_mask]\n",
    "    outputs = [target_index]\n",
    "    return keras.Model(name='code2vec', inputs=inputs, outputs=outputs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b27159fe",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# Learns which of the contexts in the method are the most important.\n",
    "#\n",
    "# Adapted from: https://github.com/tech-srl/code2vec/blob/master/keras_attention_layer.py\n",
    "class AttentionLayer(Layer):\n",
    "    def __init__(self, **kwargs):\n",
    "        super().__init__(**kwargs)\n",
    "\n",
    "    def build(self, inputs_shape):\n",
    "        shape_actual_input = inputs_shape[0]\n",
    "        self.input_length = int(shape_actual_input[1])\n",
    "        self.input_dim = int(shape_actual_input[2])\n",
    "\n",
    "        # The vector that defines how much each context should be weighted.\n",
    "        # Initialized with random values, model learns the actual ones.\n",
    "        attention_param_shape = (self.input_dim, 1)\n",
    "        self.attention_param = self.add_weight(name='attention_param',\n",
    "                                               shape=attention_param_shape,\n",
    "                                               initializer='uniform',\n",
    "                                               trainable=True, dtype=tf.float32)\n",
    "\n",
    "        super(AttentionLayer, self).build(shape_actual_input)\n",
    "\n",
    "    def call(self, inputs, **kwargs):\n",
    "        context = inputs[0]\n",
    "        mask = inputs[1]\n",
    "\n",
    "        # multiply each context with the attention to get the weight it should have in the final code_vector\n",
    "        attention_weights = kb.dot(context, self.attention_param)\n",
    "\n",
    "        if len(mask.shape) == 2:\n",
    "            mask = kb.expand_dims(mask, axis=2)\n",
    "        mask = kb.log(mask)\n",
    "        attention_weights += mask\n",
    "\n",
    "        # normalise weights\n",
    "        attention_weights = kb.softmax(attention_weights, axis=1)\n",
    "        # the code vector is just a weighted sum of contexts\n",
    "        code_vector = kb.sum(context * attention_weights, axis=1)\n",
    "\n",
    "        return code_vector, attention_weights\n",
    "\n",
    "    def compute_output_shape(self, input_shape):\n",
    "        return input_shape[0], input_shape[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2a8ce849",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "model = build_code2vec_model(vocabulary)\n",
    "model.summary()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7c2fdf10",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "model.compile(optimizer=optimizers.adam_v2.Adam(), loss=losses.CategoricalCrossentropy())\n",
    "\n",
    "# TODO: model.fit"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd721441",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Creating Big Code Datasets"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f509f59f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "A prerequisite for all these deep learning applications are large datasets of source code. Let's briefly have a look how these are commonly created."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a3963fb5",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The most common approach is to collect code from GitHub, for which GitHub provides a convenient [API](https://docs.github.com/en/rest)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c19e407d",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import requests"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b4d9ce11",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The question of which repositories to mine (a random set? the most popular ones?) is a tricky one. Let's assume we are interested in the top repositories with the most stars. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6bc8a495",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "url = 'https://api.github.com/search/repositories?q=language:java&sort=stars'\n",
    "response = requests.get(url)\n",
    "\n",
    "response_dict = response.json()\n",
    "\n",
    "print(\"Total repos:\", response_dict['total_count'])\n",
    "repos_dicts = response_dict['items']\n",
    "print(\"Repos found:\", len(repos_dicts))    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67b52ab5",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's have a look what these repositories are, and collect their Git URLs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "63d9e5c4",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "urls = []\n",
    "\n",
    "for repos_dict in repos_dicts:\n",
    "    print('\\nName:', repos_dict['name'])\n",
    "    print('Owner:', repos_dict['owner']['login'])\n",
    "    print('Stars:', repos_dict['stargazers_count'])\n",
    "    print('Repository:', repos_dict['html_url'])\n",
    "    urls.append((repos_dict['name'], repos_dict['html_url'] +\".git\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "761dac9e",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Given our list of Git URLs, the next question is how to extract source code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "455be0be",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from git import Repo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6b749a32",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import tempfile"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "abe2158e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "tmp_dir = tempfile.mkdtemp()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "832a9903",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import itertools # To limit loop iterations\n",
    "\n",
    "for repo_name, repo_url in itertools.islice(urls, 3):\n",
    "    print(\"Current url\", repo_url)\n",
    "    repo = Repo.clone_from(repo_url, tmp_dir +\"/\" + repo_name)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "58b5ff12",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import os\n",
    "\n",
    "java_files = []\n",
    "for root,d_names,f_names in os.walk(tmp_dir):\n",
    "    for f in f_names:\n",
    "        if f.endswith(\".java\"):\n",
    "            java_files.append(os.path.join(root, f))\n",
    "\n",
    "print(len(java_files))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ab538c9",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Mining bugs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98f1450f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Often we are interested in more than just raw source code. For example, many analysis approaches require information about specific bugs -- either because we want to evaluate analysis techniques (how effective is the analysis at finding bugs?), or because we want to train a model to detect bugs."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e199c52f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "A convenient way to investigate Git repositories is offered by [PyDriller](https://github.com/ishepard/pydriller). For example, we can conveniently traverse the commits of a repository."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fb604b77",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from pydriller import Repository\n",
    "\n",
    "\n",
    "example_repo = 'https://github.com/se2p/LitterBox.git'\n",
    "\n",
    "for commit in itertools.islice(Repository(example_repo).traverse_commits(), 1200, 1210):\n",
    "    print('Hash {}, author {}'.format(commit.hash, commit.author.name))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b08de15a",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "Repo.clone_from(example_repo, tmp_dir +\"/litterbox\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cf3c2aad",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "example_git = tmp_dir + \"/litterbox\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "24233456",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Why files were modified in each of the commits?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "55ffbc10",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for commit in itertools.islice(Repository(example_git).traverse_commits(), 1200, 1210):\n",
    "    for file in commit.modified_files:\n",
    "        print('Author {} modified {} in commit {}'.format(commit.author.name, file.filename, commit.hash))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "538eeb4c",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In order to produce data on real bugs, there are two common strategies: The first strategy is to find commits that indicate they are fixing bugs. We then know that the version before that commit contains a bug, whereas the version afterwards does not. \n",
    "\n",
    "A more challenging question is when a bug was introduced. Identifying this is commonly done using the SZZ algorithm, named after the authors:\n",
    "\n",
    "Śliwerski J, Zimmermann T, Zeller A (2005) When do changes induce fixes? In: Proceedings of the\n",
    "2005 International Workshop on Mining Software Repositories, ACM, New York, NY, USA, MSR\n",
    "’05, pp 1–5\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b755d94",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The approach consists of two phases: \n",
    "\n",
    "- In the first phase, bug-fixing commits are identified, often by investigating bug tracker data, or by looking for commit messages that contain the word `fix`, or refer to an issue ID. \n",
    "\n",
    "- In the second phase, for each bug-fixing commit we identify all commits that previously made changes to the same lines of code that were changed in the bug-fixing commit. \n",
    "\n",
    "The latter can be simply done by using `git blame` to identify bug-introducing commit candidates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6b6c0cf9",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "fix_commits = []\n",
    "\n",
    "for commit in Repository(example_git).traverse_commits():\n",
    "    # Exclude merge commits \n",
    "    if commit.merge: \n",
    "        continue\n",
    "    msg = commit.msg.lower()\n",
    "    if \"fix\" in msg:\n",
    "        fix_commits.append(commit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9ec186af",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "len(fix_commits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "61eafc11",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from pydriller import Git\n",
    "\n",
    "git = Git(example_git)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5bc44958",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "commit = git.get_commit(\"cd665cfc27315130102e2cf816a3d58fe82ce77e\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "009497ee",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(f\"Fix Commit {commit.hash}: {commit.msg}\")\n",
    "for file in commit.modified_files:\n",
    "    lines = [line for (line, text) in file.diff_parsed[\"deleted\"]]\n",
    "    print(f\" -> {file.filename}: {lines}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "57f779a2",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "commit.modified_files[0].diff_parsed[\"deleted\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e48df6db",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "commit.modified_files[0].diff_parsed[\"added\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "96887303",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "commit.modified_files[1].diff_parsed[\"added\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "87c94c74",
   "metadata": {
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "bug_changes = git.get_commits_last_modified_lines(commit)\n",
    "bug_changes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a4558771",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "bug_commit_hash = list(bug_changes[list(bug_changes)[0]])[0] # WTF"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b48ba9c2",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "bug_commit = git.get_commit(bug_commit_hash)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "357505ab",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Given the bug commit, we can consider what was the buggy code that was added in this particular version."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c32db8d0",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for file in bug_commit.modified_files:\n",
    "    if file.filename == \"WeightedMethodCount.java\":\n",
    "        print([line for line, text in file.diff_parsed[\"added\"]])"
   ]
  }
 ],
 "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
}