3 Syntax-based Analysis.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "03d58d98",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Syntax-based Analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2470d602",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Given a token stream produced by a lexer, the objective of a parser is to construct a tree that captures the syntactic relation between the tokens."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5bb7dd4f",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## CCLearner: Deep learning clone detection "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d15ccb4d",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We've already explored different code clone detection techniques, now it's time for yet another:\n",
    "\n",
    "Li, L., Feng, H., Zhuang, W., Meng, N., & Ryder, B. (2017, September). Cclearner: A deep learning-based clone detection approach. In 2017 IEEE International Conference on Software Maintenance and Evolution (ICSME) (pp. 249-260). IEEE."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "55a3efb6",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The idea of CCLearner is to compare code snippets in terms of the token frequencies. For this, the approach distinguishes the following token types:\n",
    "- Reserved words\n",
    "- Operators \n",
    "- Markers\n",
    "- Literals\n",
    "- Type identifiers\n",
    "- Method idenfiers\n",
    "- Qualified names\n",
    "- Variable identifiers"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83e68fd2",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "If you think about our tokenization approach from the last chapter, you'll realize there's a problem here: While we did distinguish between different types of tokens, our tokenizer cannot distinguish between type, method, qualified, and variable identifiers -- this was all just classified as \"identifier\". In order to distinguish these types of tokens we need to consider the syntactic context. This is what a parser does given a token stream."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2029ff2d",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Parsing programs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51c81597",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We will construct a simple parser for a trivial example language that resembles Python. Here's an example program:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7b6b917",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "```\n",
    "def f(a, b)\n",
    "    add(100, add(20, add(a, b)))\n",
    "end\n",
    "\n",
    "print(f(1, 2))\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ca4880f3",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code = \"\"\"def f(a, b)\n",
    "    add(100, add(20, add(a, b)))\n",
    "end\n",
    "\n",
    "print(f(1, 2))\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f0b31a59",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The language contains function definitions, function calls, integer literals, and variable references. It also makes use of two undefined functions `add` and `print` which will be defined later."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2663622b",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Tokenization"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e885b49",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "A prerequisite for a parser is the token stream. We implemented a lexer in the last chapter in a very basic way, and in the end realised that what we had produced was an automaton matching regular expressions. We can thus implement a simpler lexer by defining the token types in terms of regular expressions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f2c0eac0",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from collections import namedtuple\n",
    "import re"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0401470a",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We won't actually need the position so let's just focus on lexemes and token types."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "604c174c",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "Token = namedtuple('Token', 'token_type value')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "429e2119",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "For our example language, we define the following token types:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "16175071",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "TOKEN_TYPES = [\n",
    "    (r'\\bdef\\b',        'def'),\n",
    "    (r'\\bend\\b',        'end'),\n",
    "    (r'\\b[a-zA-Z]+\\b',  'identifier'),\n",
    "    (r'\\b[0-9]+\\b',     'integer'),\n",
    "    (r'\\(',             'oparen'),\n",
    "    (r'\\)',             'cparen'),\n",
    "    (r',',              'comma'),\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "376e910b",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def tokenize(code):\n",
    "    tokens = []\n",
    "    \n",
    "    remaining_code = code\n",
    "    \n",
    "    while remaining_code:\n",
    "        for regex, token_type in TOKEN_TYPES:\n",
    "            match = re.match(regex, remaining_code)\n",
    "            if match:\n",
    "                value = match.group()\n",
    "                remaining_code = remaining_code[len(value):].strip()\n",
    "                tokens.append(Token(token_type, value))\n",
    "    \n",
    "    return tokens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "38f31d7d",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "tokenize(code)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "41e93514",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Parsing"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f298c12",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can now build a parser that constructs a parse tree, thus implicitly defining a grammar for our language. This is slightly more involved, so we will  construct this in an object oriented way."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "32f03131",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class Parser:\n",
    "    def __init__(self, tokens):\n",
    "        self.tokens = list(tokens)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70faa2af",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The parser matches tokens based on a grammar. If the next token does not match a type allowed by the grammar, the parser reports an error."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c6443872",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class Parser(Parser):\n",
    "    def consume(self, expected_type):\n",
    "        token = self.tokens.pop(0)\n",
    "        if token.token_type == expected_type:\n",
    "            return token\n",
    "        else:\n",
    "            raise RuntimeError(\n",
    "                f\"Expected token type {expected_type!r} \"\n",
    "                f\"but got {token.token_type!r}.\"\n",
    "            )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3891d999",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We now implicitly define our grammar by implementing each production as a function. Integer literals simply produce leaf nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6b9b986d",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class Parser(Parser):\n",
    "    def parse_integer(self):\n",
    "        return dict(\n",
    "            node_type='int',\n",
    "            value=int(self.consume('integer').value),\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "52e4bf0e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "example = \"5\"\n",
    "parser = Parser(tokenize(example))\n",
    "parser.parse_integer()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31bc4c80",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Similarly, variable nodes are leaf nodes containing the variable name."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e355981d",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class Parser(Parser):\n",
    "    def parse_var_ref(self):\n",
    "        return dict(\n",
    "            node_type='var',\n",
    "            name=self.consume('identifier').value,\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ae3b651e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "example = \"x\"\n",
    "parser = Parser(tokenize(example))\n",
    "parser.parse_var_ref()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4787f7b0",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Function calls are slightly more involved since they are not just individual tokens. To determine which grammar rule we are matching we sometimes need to look ahead."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4f2986e9",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class Parser(Parser):\n",
    "    def peek(self, expected_type, offset=0):\n",
    "        return self.tokens[offset].token_type == expected_type"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b37fc42",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "A function call consists of a call node that contains the name of the function called, and nodes for the arguments, if there are any."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "75e25fac",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class Parser(Parser):\n",
    "    def parse_call(self):\n",
    "        name = self.consume('identifier').value\n",
    "        arg_exprs = list(self.parse_arg_exprs())\n",
    "        return dict(\n",
    "            node_type='call',\n",
    "            name=name,\n",
    "            arg_exprs=arg_exprs,\\\n",
    "        )\n",
    "\n",
    "    def parse_arg_exprs(self):\n",
    "        self.consume('oparen')\n",
    "        if not self.peek('cparen'):\n",
    "            yield self.parse_expr()\n",
    "            while self.peek('comma'):\n",
    "                self.consume('comma')\n",
    "                yield self.parse_expr()\n",
    "        self.consume('cparen')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e9b5ba41",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class Parser(Parser):\n",
    "    def parse_expr(self):\n",
    "        if self.peek('integer'):\n",
    "            return self.parse_integer()\n",
    "        elif self.peek('identifier') and self.peek('oparen', 1):\n",
    "            return self.parse_call()\n",
    "        else:\n",
    "            return self.parse_var_ref()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bb54ab94",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "example = \"foo(5)\"\n",
    "parser = Parser(tokenize(example))\n",
    "parser.parse_call()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6f3ea151",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class Parser(Parser):\n",
    "    def parse_def(self):\n",
    "        self.consume('def')\n",
    "        name = self.consume('identifier').value\n",
    "        arg_names = list(self.parse_arg_names())\n",
    "        body = self.parse_expr()\n",
    "        self.consume('end')\n",
    "        return dict(\n",
    "            node_type='def',\n",
    "            name=name,\n",
    "            arg_names=arg_names,\n",
    "            body=body,\n",
    "        )\n",
    "\n",
    "    def parse_arg_names(self):\n",
    "        self.consume('oparen')\n",
    "        if self.peek('identifier'):\n",
    "            yield self.consume('identifier').value\n",
    "            while self.peek('comma'):\n",
    "                self.consume('comma')\n",
    "                yield self.consume('identifier').value\n",
    "        self.consume('cparen')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4ebf3675",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "parser = Parser(tokenize(code))\n",
    "parser.parse_def()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d86d13a",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Finally, we need to implement the start rule of our grammar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d11d6545",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class Parser(Parser):\n",
    "    def parse(self):\n",
    "        while self.tokens:\n",
    "            if self.peek('def'):\n",
    "                yield self.parse_def()\n",
    "            else:\n",
    "                yield self.parse_call()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d5b21d8a",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "tree = Parser(tokenize(code)).parse()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2f1c1547",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "list(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "44e099d0",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can visualize the syntax tree using a little helper function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6bc0859f",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from graphviz import Digraph\n",
    "\n",
    "unique_id = 0\n",
    "\n",
    "def print_tree(node):\n",
    "    dot = Digraph()\n",
    "    num = 0\n",
    "    dot.node(\"root\", \"start\")\n",
    "    for child in list(node):\n",
    "        child_id = add_nodes(dot, child, f\"root-{num}\")\n",
    "        dot.edge(\"root\", child_id)\n",
    "        num += 1\n",
    "    return dot\n",
    "\n",
    "def add_nodes(dot, node, name):\n",
    "    global unique_id\n",
    "   \n",
    "    if isinstance(node, dict):\n",
    "        dot.node(str(id(node)), name)\n",
    "        for key, value in node.items():\n",
    "            child_id = add_nodes(dot, value, key)\n",
    "            dot.edge(str(id(node)), child_id)\n",
    "        return str(id(node))\n",
    "                \n",
    "    elif isinstance(node, str):\n",
    "            node_id = unique_id\n",
    "            unique_id += 1\n",
    "            dot.node(str(node_id), node)\n",
    "            return str(node_id)\n",
    "\n",
    "    elif isinstance(node, int):\n",
    "            node_id = unique_id\n",
    "            unique_id += 1\n",
    "            dot.node(str(node_id), str(node))\n",
    "            return str(node_id)\n",
    "\n",
    "    elif isinstance(node, list):\n",
    "        dot.node(str(id(node)), name)\n",
    "        num = 0\n",
    "        for child in node:\n",
    "            child_id = add_nodes(dot, child, f\"{name}-{num}\")\n",
    "            dot.edge(str(id(node)), child_id)\n",
    "            num += 1\n",
    "        return str(id(node))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "842bb381",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "root_nodes = list(Parser(tokenize(code)).parse())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "851e7f85",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print_tree(root_nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12d75f2a",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Note that this is not yet an _abstract_ syntax tree: It is a parse tree, exactly representing the grammar used, including all tokens. In contrast, an abstract syntax tree describes the parse tree logically and does not need to contain all the syntactical constructs. While a parse tree only has non-terminal nodes as non-leaf nodes, an abstract syntax tree can, for example, contain operators as interor nodes, with the operands being leaves."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0520d614",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Revisiting CCLearner"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46d314dc",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "If we want to parse real languages, we'll often find existing parsers. To process Java code in Python, we can use Javalang."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "52554e51",
   "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": "8b5c81fa",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code2 = \"\"\"\n",
    "public class Foo {\n",
    "  private int y = 0;\n",
    "  \n",
    "  public void foo(int x) {\n",
    "    System.out.println(\"Hello Clone!\");\n",
    "    int j = 10 + y;\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": "f4fc19ce",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import javalang"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f3affc90",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "javalang.parse.parse(code2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7bb74b6a",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "It might be helpful to see the tree structure visualised."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b68287ec",
   "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": "4b9886cc",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "tree = javalang.parse.parse(code2)\n",
    "print_tree(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8fbd796",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In contrast to our parse tree shown earlier, this is an actual _abstract_ syntax tree. To construct an AST, one needs to extend the implementations of the different productions to instantiate the appropriate node structures required."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6b04798",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "CCLearner defines eight different types of tokens for the clone analysis."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "929ee953",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "reserved   = {} # C1\n",
    "operators  = {} # C2\n",
    "markers    = {} # C3\n",
    "literals   = {} # C4\n",
    "type_ids   = {} # C5\n",
    "method_ids = {} # C6\n",
    "qualified_ids = {} # C7\n",
    "variable_ids  = {} # C8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4d706a0c",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def increment(dictionary, key):\n",
    "    if key in dictionary:\n",
    "        dictionary[key] += 1\n",
    "    else:\n",
    "        dictionary[key] = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91e07fdc",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The first three types of tokens can easily be extracted using a tokenizer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "36d307bd",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "for token in javalang.tokenizer.tokenize(code2):\n",
    "    # C1\n",
    "    if token.__class__.__name__ == \"Keyword\":\n",
    "        increment(reserved, token.value)\n",
    "\n",
    "    # C2\n",
    "    elif token.__class__.__name__ == \"Operator\":\n",
    "        increment(operators, token.value)\n",
    "    \n",
    "    # C3\n",
    "    elif token.__class__.__name__ == \"Separator\":\n",
    "        increment(markers, token.value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b1ce199e",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Type C4 (Literals) already comes with some challenges. For example, consider the following snippet of code and its tokens:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "590c8b20",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "list(javalang.tokenizer.tokenize(\"int i = -1;\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3347bd2b",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The number `-1` is split into two tokens, but for the sake of CCLearner's analysis it would be preferable to use a single number."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "330960f0",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To extract literals values, we can, however, use the AST:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "52c3c2a8",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "example_tree = javalang.parse.parse(\"class Test {int i = -1;}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "02a7ca9b",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for _, node in example_tree.filter(javalang.tree.Literal):\n",
    "    print(f\"Literal: {node}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e144ebd",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We thus need to prepend the prefix operators when collecting literals."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "db59a8a0",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "for _, node in tree.filter(javalang.tree.Literal):\n",
    "    result = \"\".join(node.prefix_operators) + node.value\n",
    "    # C4\n",
    "    increment(literals, result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0e54101e",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "for _, node in tree.filter(javalang.tree.Type):\n",
    "    # C5\n",
    "    increment(type_ids, node.name)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7cf641ac",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "For C6 we require all method names, which are part of MethodDeclarations and MethodInvocations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b0b2a831",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "for _, node in tree.filter(javalang.tree.MethodInvocation):\n",
    "    # C6\n",
    "    increment(method_ids, node.member)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6aa8a3b8",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for _, node in tree.filter(javalang.tree.MethodDeclaration):\n",
    "    # C6\n",
    "    increment(method_ids, node.name)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec9caafc",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Qualified names (C7 tokens) are explicitly available in the AST."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "638bad9e",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "for _, node in tree.filter(javalang.tree.Primary):\n",
    "    # C7\n",
    "    if node.qualifier:\n",
    "        increment(qualified_ids, node.qualifier)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f3297011",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Variable identifiers (C8 tokens) are slightly more inconvenient to extract than the other tokens because they can occur at multiple different types of locations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "884ec0b9",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "for _, node in tree.filter(javalang.tree.VariableDeclarator):\n",
    "    # C8\n",
    "    increment(variable_ids, node.name)\n",
    "\n",
    "for _, node in tree.filter(javalang.tree.FormalParameter):\n",
    "    # C8\n",
    "    increment(variable_ids, node.name)\n",
    "    \n",
    "for _, node in tree.filter(javalang.tree.MemberReference):\n",
    "    # C8\n",
    "    increment(variable_ids, node.member)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d0ec8754",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "print(reserved)\n",
    "print(operators)\n",
    "print(markers)\n",
    "print(literals)\n",
    "print(type_ids)\n",
    "print(method_ids)\n",
    "print(qualified_ids)\n",
    "print(variable_ids)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ce614571",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Now we can place all the conditions from above into a function that derives the tokens for a given snippet of code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "827076b2",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def get_tokens(code):\n",
    "    \n",
    "    tokens = { \n",
    "        \"reserved\" : {},\n",
    "        \"operators\" : {},\n",
    "        \"markers\" : {},\n",
    "        \"literals\" : {},\n",
    "        \"type_ids\" : {},\n",
    "        \"method_ids\" : {},\n",
    "        \"qualified_ids\" : {},\n",
    "        \"variable_ids\" : {}\n",
    "             }\n",
    "\n",
    "    for token in javalang.tokenizer.tokenize(code):\n",
    "        # C1\n",
    "        if token.__class__.__name__ == \"Keyword\":\n",
    "            increment(tokens[\"reserved\"], token.value)\n",
    "        # C2\n",
    "        elif token.__class__.__name__ == \"Operator\":\n",
    "            increment(tokens[\"operators\"], token.value)    \n",
    "        # C3\n",
    "        elif token.__class__.__name__ == \"Separator\":\n",
    "            increment(tokens[\"markers\"], token.value)\n",
    "\n",
    "    tree = javalang.parse.parse(code)\n",
    "    for _, node in tree.filter(javalang.tree.Literal):\n",
    "        result = \"\".join(node.prefix_operators) + node.value\n",
    "        # C4\n",
    "        increment(tokens[\"literals\"], result)\n",
    "    for _, node in tree.filter(javalang.tree.Type):\n",
    "        # C5\n",
    "        increment(tokens[\"type_ids\"], result)\n",
    "    for _, node in tree.filter(javalang.tree.MethodInvocation):\n",
    "        # C6\n",
    "        increment(tokens[\"method_ids\"], node.member)\n",
    "    for _, node in tree.filter(javalang.tree.MethodDeclaration):\n",
    "        # C6\n",
    "        increment(tokens[\"method_ids\"], node.name)\n",
    "    for _, node in tree.filter(javalang.tree.Primary):\n",
    "        # C7\n",
    "        if node.qualifier:\n",
    "            increment(tokens[\"qualified_ids\"], node.qualifier)\n",
    "    for _, node in tree.filter(javalang.tree.VariableDeclarator):\n",
    "        # C8\n",
    "        increment(tokens[\"variable_ids\"], node.name)\n",
    "    for _, node in tree.filter(javalang.tree.FormalParameter):\n",
    "        # C8\n",
    "        increment(tokens[\"variable_ids\"], node.name)\n",
    "    for _, node in tree.filter(javalang.tree.MemberReference):\n",
    "        increment(tokens[\"variable_ids\"], node.member)\n",
    "        # C8\n",
    "        \n",
    "    return tokens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4e9f430b",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "get_tokens(code1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a4cfbe5",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The similarity for a given cataegory tokens is calculated as 1 minus the difference of token frequencies over the sums of token frequencies."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "08278a8c",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def sim_score(tokens1, tokens2):\n",
    "    if not tokens1 or not tokens2:\n",
    "        return 0.5 # See paper\n",
    "    \n",
    "    tokens = set(tokens1.keys()).union(set(tokens2.keys()))\n",
    "    \n",
    "    diff = 0\n",
    "    summ = 0 \n",
    "    \n",
    "    for token in tokens:\n",
    "        num1 = tokens1[token] if token in tokens1 else 0\n",
    "        num2 = tokens2[token] if token in tokens2 else 0\n",
    "        diff += abs(num1 - num2)\n",
    "        summ += num1 + num2\n",
    "    \n",
    "    return 1.0 - diff / summ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "81cca994",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "code3 = \"\"\"\n",
    "public class Bar {\n",
    "  public void bar(int x) {\n",
    "    System.out.println(\"Completely different text!\");\n",
    "    int j = 200; // completely different numbers\n",
    "    for(int i = 100; i < x; i++) {\n",
    "      System.out.println(\"More complete different text\");\n",
    "    }\n",
    "  }\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "541c4d2c",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code4 = \"\"\"\n",
    "public class Bar {\n",
    "  public void bar(int x) {\n",
    "        MultiLayerNetwork model = new MultiLayerNetwork(conf);\n",
    "        model.init();\n",
    "        model.setListeners(Collections.singletonList((IterationListener) new ScoreIterationListener(10)));\n",
    "\n",
    "\n",
    "        for (int n = 0; n < nEpochs; n++) {\n",
    "            model.fit(trainIter);\n",
    "        }\n",
    "\n",
    "        File model_File = new File(output_dir + \"model.mdl\");\n",
    "  }\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "58c79f80",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "tokens1 = get_tokens(code1)\n",
    "tokens2 = get_tokens(code2)\n",
    "tokens3 = get_tokens(code3)\n",
    "tokens4 = get_tokens(code4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4a03b720",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "sim_score(tokens1[\"markers\"], tokens2[\"markers\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ab6d6ad7",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def feature_vector(tokens1, tokens2):\n",
    "    similarity = []\n",
    "    for key in tokens1.keys():\n",
    "        similarity.append(sim_score(tokens1[key], tokens2[key]))\n",
    "    return similarity"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "11c38985",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The first and second code snippet contain a type 1 clone (there are some minor differences in the classes):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "49ae84d7",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "feature_vector(tokens1, tokens2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e33bb6dd",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The first and third code snippets are type 2 clones that differ in identifier and literal names:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d3eb4105",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "feature_vector(tokens1, tokens3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "676b2fb8",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The first and fourth code snippets contain completely different code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "db38e37f",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "feature_vector(tokens1, tokens4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8f96149",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "While the raw feature vectors may be difficult to interpret, at this point we could train a machine learning model given a labelled dataset of pairs of code snippets. For each pair of code snippets we would calculate the feature vector, and then update train the model based on the label for that pair."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00a535f0",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Generating Parsers"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57780ed7",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Earlier 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 (antlr4-python3-runtime)."
   ]
  },
  {
   "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": [
    "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 another 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": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "UselessControlFlowChecker().check(code5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5f0c666",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "As another example, we consider the [Boolean Returns Null](https://spotbugs.readthedocs.io/en/stable/bugDescriptions.html#np-boolean-return-null) checker, which looks for methods with Boolean return type, explicitly returning null."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "08e093b8",
   "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": "62b43639",
   "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": "954af302",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "BooleanReturnNullChecker().check(code1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0c50b1cb",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "BooleanReturnNullChecker().check(code6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "221f62b6",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "However, when we are not explicitly returning `null`, but the `null` value is produced by some expression and propagated through variables, our simple analysis fails."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7e1a6aca",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code7 = \"\"\"\n",
    "public class Foo {\n",
    "  public Boolean foo(int x) {\n",
    "    Boolean foo = null;\n",
    "    // ...\n",
    "    return foo;\n",
    "  }\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "677ce15b",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "BooleanReturnNullChecker().check(code7)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c59ef16",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To solve this issue, we will consider control and data flow in the following chapters."
   ]
  }
 ],
 "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
}