3 Syntax-based Analysis.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "61deb61f",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Syntax-based Analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92e47584",
   "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": "01909fb5",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## CCLearner: Deep learning clone detection "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e239ce07",
   "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": "4557e3c3",
   "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": "e0598280",
   "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": "4bb50df7",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Parsing programs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3969a350",
   "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": "eed7637e",
   "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": 1,
   "id": "54b3d4d4",
   "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": "3324aa30",
   "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": "b2e2fb59",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Tokenization"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b005d40",
   "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": 2,
   "id": "83110599",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from collections import namedtuple\n",
    "import re"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b210fa7e",
   "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": 3,
   "id": "5f6e0103",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "Token = namedtuple('Token', 'token_type value')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6cc79f0",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "For our example language, we define the following token types:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "2a9bad92",
   "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": 5,
   "id": "218f54e6",
   "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": 6,
   "id": "fc036529",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Token(token_type='def', value='def'),\n",
       " Token(token_type='identifier', value='f'),\n",
       " Token(token_type='oparen', value='('),\n",
       " Token(token_type='identifier', value='a'),\n",
       " Token(token_type='comma', value=','),\n",
       " Token(token_type='identifier', value='b'),\n",
       " Token(token_type='cparen', value=')'),\n",
       " Token(token_type='identifier', value='add'),\n",
       " Token(token_type='oparen', value='('),\n",
       " Token(token_type='integer', value='100'),\n",
       " Token(token_type='comma', value=','),\n",
       " Token(token_type='identifier', value='add'),\n",
       " Token(token_type='oparen', value='('),\n",
       " Token(token_type='integer', value='20'),\n",
       " Token(token_type='comma', value=','),\n",
       " Token(token_type='identifier', value='add'),\n",
       " Token(token_type='oparen', value='('),\n",
       " Token(token_type='identifier', value='a'),\n",
       " Token(token_type='comma', value=','),\n",
       " Token(token_type='identifier', value='b'),\n",
       " Token(token_type='cparen', value=')'),\n",
       " Token(token_type='cparen', value=')'),\n",
       " Token(token_type='cparen', value=')'),\n",
       " Token(token_type='end', value='end'),\n",
       " Token(token_type='identifier', value='print'),\n",
       " Token(token_type='oparen', value='('),\n",
       " Token(token_type='identifier', value='f'),\n",
       " Token(token_type='oparen', value='('),\n",
       " Token(token_type='integer', value='1'),\n",
       " Token(token_type='comma', value=','),\n",
       " Token(token_type='integer', value='2'),\n",
       " Token(token_type='cparen', value=')'),\n",
       " Token(token_type='cparen', value=')')]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tokenize(code)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4de150e",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Parsing"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04d9db1c",
   "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": 7,
   "id": "6ed021f1",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class Parser:\n",
    "    def __init__(self, tokens):\n",
    "        self.tokens = list(tokens)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "84446f9d",
   "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": 8,
   "id": "292ef830",
   "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": "d3701987",
   "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": 9,
   "id": "a29266fd",
   "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": 10,
   "id": "3a01229e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'node_type': 'int', 'value': 5}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "example = \"5\"\n",
    "parser = Parser(tokenize(example))\n",
    "parser.parse_integer()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00d0216a",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Similarly, variable nodes are leaf nodes containing the variable name."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "06e2c5e4",
   "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": 12,
   "id": "ee687ef6",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'node_type': 'var', 'name': 'x'}"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "example = \"x\"\n",
    "parser = Parser(tokenize(example))\n",
    "parser.parse_var_ref()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2623aa7b",
   "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": 13,
   "id": "4bd6ab32",
   "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": "d05c5f2b",
   "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": 14,
   "id": "0611cc12",
   "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": 15,
   "id": "de23cbdc",
   "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": 16,
   "id": "f1e0b018",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'node_type': 'call',\n",
       " 'name': 'foo',\n",
       " 'arg_exprs': [{'node_type': 'int', 'value': 5}]}"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "example = \"foo(5)\"\n",
    "parser = Parser(tokenize(example))\n",
    "parser.parse_call()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "71beefe2",
   "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": 18,
   "id": "81d10a29",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'node_type': 'def',\n",
       " 'name': 'f',\n",
       " 'arg_names': ['a', 'b'],\n",
       " 'body': {'node_type': 'call',\n",
       "  'name': 'add',\n",
       "  'arg_exprs': [{'node_type': 'int', 'value': 100},\n",
       "   {'node_type': 'call',\n",
       "    'name': 'add',\n",
       "    'arg_exprs': [{'node_type': 'int', 'value': 20},\n",
       "     {'node_type': 'call',\n",
       "      'name': 'add',\n",
       "      'arg_exprs': [{'node_type': 'var', 'name': 'a'},\n",
       "       {'node_type': 'var', 'name': 'b'}]}]}]}}"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parser = Parser(tokenize(code))\n",
    "parser.parse_def()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57f33d67",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Finally, we need to implement the start rule of our grammar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "8d7cc570",
   "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": 20,
   "id": "efbd8948",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "tree = Parser(tokenize(code)).parse()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "c78127e2",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'node_type': 'def',\n",
       "  'name': 'f',\n",
       "  'arg_names': ['a', 'b'],\n",
       "  'body': {'node_type': 'call',\n",
       "   'name': 'add',\n",
       "   'arg_exprs': [{'node_type': 'int', 'value': 100},\n",
       "    {'node_type': 'call',\n",
       "     'name': 'add',\n",
       "     'arg_exprs': [{'node_type': 'int', 'value': 20},\n",
       "      {'node_type': 'call',\n",
       "       'name': 'add',\n",
       "       'arg_exprs': [{'node_type': 'var', 'name': 'a'},\n",
       "        {'node_type': 'var', 'name': 'b'}]}]}]}},\n",
       " {'node_type': 'call',\n",
       "  'name': 'print',\n",
       "  'arg_exprs': [{'node_type': 'call',\n",
       "    'name': 'f',\n",
       "    'arg_exprs': [{'node_type': 'int', 'value': 1},\n",
       "     {'node_type': 'int', 'value': 2}]}]}]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05ffe8e3",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We can visualize the syntax tree using a little helper function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "aceb91b9",
   "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": 23,
   "id": "fd9bfe2a",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "root_nodes = list(Parser(tokenize(code)).parse())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "524c9265",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 3.0.0 (20220226.1711)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"902pt\" height=\"692pt\"\n",
       " viewBox=\"0.00 0.00 902.00 692.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 688)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-688 898,-688 898,4 -4,4\"/>\n",
       "<!-- root -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>root</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"278\" cy=\"-666\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"278\" y=\"-662.3\" font-family=\"Times,serif\" font-size=\"14.00\">start</text>\n",
       "</g>\n",
       "<!-- 4525515520 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>4525515520</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"193\" cy=\"-594\" rx=\"32.49\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"193\" y=\"-590.3\" font-family=\"Times,serif\" font-size=\"14.00\">root&#45;0</text>\n",
       "</g>\n",
       "<!-- root&#45;&gt;4525515520 -->\n",
       "<g id=\"edge30\" class=\"edge\">\n",
       "<title>root&#45;&gt;4525515520</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M261.61,-651.5C249.35,-641.41 232.36,-627.41 218.35,-615.88\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"220.45,-613.07 210.51,-609.42 216,-618.48 220.45,-613.07\"/>\n",
       "</g>\n",
       "<!-- 4525515456 -->\n",
       "<g id=\"node32\" class=\"node\">\n",
       "<title>4525515456</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"411\" cy=\"-594\" rx=\"32.49\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"411\" y=\"-590.3\" font-family=\"Times,serif\" font-size=\"14.00\">root&#45;1</text>\n",
       "</g>\n",
       "<!-- root&#45;&gt;4525515456 -->\n",
       "<g id=\"edge44\" class=\"edge\">\n",
       "<title>root&#45;&gt;4525515456</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M298.49,-654.22C319.94,-642.93 353.92,-625.04 378.93,-611.88\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"380.81,-614.84 388.03,-607.09 377.55,-608.65 380.81,-614.84\"/>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-522\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-518.3\" font-family=\"Times,serif\" font-size=\"14.00\">def</text>\n",
       "</g>\n",
       "<!-- 4525515520&#45;&gt;0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>4525515520&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M166.93,-582.85C140.56,-572.47 98.7,-555.69 63,-540 61.2,-539.21 59.35,-538.38 57.49,-537.54\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"58.78,-534.28 48.23,-533.26 55.84,-540.63 58.78,-534.28\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-522\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-518.3\" font-family=\"Times,serif\" font-size=\"14.00\">f</text>\n",
       "</g>\n",
       "<!-- 4525515520&#45;&gt;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>4525515520&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.43,-579.17C160.16,-568.55 140.3,-553.76 124.54,-542.02\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"126.38,-539.02 116.26,-535.86 122.19,-544.64 126.38,-539.02\"/>\n",
       "</g>\n",
       "<!-- 4525416128 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4525416128</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"193\" cy=\"-522\" rx=\"49.29\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"193\" y=\"-518.3\" font-family=\"Times,serif\" font-size=\"14.00\">arg_names</text>\n",
       "</g>\n",
       "<!-- 4525515520&#45;&gt;4525416128 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>4525515520&#45;&gt;4525416128</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M193,-575.7C193,-567.98 193,-558.71 193,-550.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"196.5,-550.1 193,-540.1 189.5,-550.1 196.5,-550.1\"/>\n",
       "</g>\n",
       "<!-- 4525415104 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>4525415104</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"297\" cy=\"-522\" rx=\"28.7\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"297\" y=\"-518.3\" font-family=\"Times,serif\" font-size=\"14.00\">body</text>\n",
       "</g>\n",
       "<!-- 4525515520&#45;&gt;4525415104 -->\n",
       "<g id=\"edge29\" class=\"edge\">\n",
       "<title>4525515520&#45;&gt;4525415104</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M213.05,-579.5C229.04,-568.74 251.6,-553.56 269.3,-541.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"271.72,-544.23 278.06,-535.75 267.81,-538.43 271.72,-544.23\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"110\" cy=\"-450\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"110\" y=\"-446.3\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- 4525416128&#45;&gt;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>4525416128&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.17,-505.12C162.32,-495.12 146.91,-482.13 134.17,-471.38\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"136.14,-468.47 126.24,-464.7 131.63,-473.82 136.14,-468.47\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"182\" cy=\"-450\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"182\" y=\"-446.3\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- 4525416128&#45;&gt;3 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>4525416128&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M190.28,-503.7C189.07,-495.98 187.61,-486.71 186.26,-478.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"189.7,-477.44 184.69,-468.1 182.78,-478.53 189.7,-477.44\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"254\" cy=\"-450\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"254\" y=\"-446.3\" font-family=\"Times,serif\" font-size=\"14.00\">call</text>\n",
       "</g>\n",
       "<!-- 4525415104&#45;&gt;4 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>4525415104&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M287.03,-504.76C281.76,-496.19 275.19,-485.49 269.3,-475.9\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"272.14,-473.84 263.92,-467.15 266.17,-477.5 272.14,-473.84\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"326\" cy=\"-450\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"326\" y=\"-446.3\" font-family=\"Times,serif\" font-size=\"14.00\">add</text>\n",
       "</g>\n",
       "<!-- 4525415104&#45;&gt;5 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>4525415104&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M303.87,-504.41C307.27,-496.22 311.44,-486.14 315.25,-476.95\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"318.58,-478.05 319.18,-467.47 312.12,-475.37 318.58,-478.05\"/>\n",
       "</g>\n",
       "<!-- 4525180416 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>4525180416</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"416\" cy=\"-450\" rx=\"45.49\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"416\" y=\"-446.3\" font-family=\"Times,serif\" font-size=\"14.00\">arg_exprs</text>\n",
       "</g>\n",
       "<!-- 4525415104&#45;&gt;4525180416 -->\n",
       "<g id=\"edge28\" class=\"edge\">\n",
       "<title>4525415104&#45;&gt;4525180416</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M317.19,-509.13C335.17,-498.54 361.84,-482.86 382.93,-470.45\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"384.75,-473.44 391.59,-465.36 381.2,-467.41 384.75,-473.44\"/>\n",
       "</g>\n",
       "<!-- 4525182272 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>4525182272</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"278\" cy=\"-378\" rx=\"52.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"278\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">arg_exprs&#45;0</text>\n",
       "</g>\n",
       "<!-- 4525180416&#45;&gt;4525182272 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>4525180416&#45;&gt;4525182272</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M389.06,-435.34C368.01,-424.66 338.52,-409.7 315.21,-397.87\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"316.79,-394.75 306.29,-393.35 313.63,-401 316.79,-394.75\"/>\n",
       "</g>\n",
       "<!-- 4525415168 -->\n",
       "<g id=\"node15\" class=\"node\">\n",
       "<title>4525415168</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"416\" cy=\"-378\" rx=\"52.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"416\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">arg_exprs&#45;1</text>\n",
       "</g>\n",
       "<!-- 4525180416&#45;&gt;4525415168 -->\n",
       "<g id=\"edge27\" class=\"edge\">\n",
       "<title>4525180416&#45;&gt;4525415168</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M416,-431.7C416,-423.98 416,-414.71 416,-406.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"419.5,-406.1 416,-396.1 412.5,-406.1 419.5,-406.1\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node13\" class=\"node\">\n",
       "<title>6</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"206\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"206\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">int</text>\n",
       "</g>\n",
       "<!-- 4525182272&#45;&gt;6 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>4525182272&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M261.3,-360.76C251.41,-351.14 238.75,-338.84 228.04,-328.43\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"230.27,-325.71 220.66,-321.25 225.39,-330.73 230.27,-325.71\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node14\" class=\"node\">\n",
       "<title>7</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"278\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"278\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">100</text>\n",
       "</g>\n",
       "<!-- 4525182272&#45;&gt;7 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>4525182272&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M278,-359.7C278,-351.98 278,-342.71 278,-334.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"281.5,-334.1 278,-324.1 274.5,-334.1 281.5,-334.1\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node16\" class=\"node\">\n",
       "<title>8</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"350\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"350\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">call</text>\n",
       "</g>\n",
       "<!-- 4525415168&#45;&gt;8 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>4525415168&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M400.69,-360.76C391.83,-351.37 380.55,-339.41 370.89,-329.15\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"373.28,-326.59 363.88,-321.72 368.19,-331.39 373.28,-326.59\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node17\" class=\"node\">\n",
       "<title>9</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"422\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"422\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">add</text>\n",
       "</g>\n",
       "<!-- 4525415168&#45;&gt;9 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>4525415168&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M417.48,-359.7C418.14,-351.98 418.94,-342.71 419.68,-334.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"423.17,-334.37 420.53,-324.1 416.19,-333.77 423.17,-334.37\"/>\n",
       "</g>\n",
       "<!-- 4525181632 -->\n",
       "<g id=\"node18\" class=\"node\">\n",
       "<title>4525181632</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"512\" cy=\"-306\" rx=\"45.49\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"512\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">arg_exprs</text>\n",
       "</g>\n",
       "<!-- 4525415168&#45;&gt;4525181632 -->\n",
       "<g id=\"edge26\" class=\"edge\">\n",
       "<title>4525415168&#45;&gt;4525181632</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M437.31,-361.46C450.7,-351.7 468.15,-338.97 482.82,-328.28\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"485.07,-330.97 491.08,-322.25 480.94,-325.31 485.07,-330.97\"/>\n",
       "</g>\n",
       "<!-- 4525181760 -->\n",
       "<g id=\"node19\" class=\"node\">\n",
       "<title>4525181760</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"382\" cy=\"-234\" rx=\"52.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"382\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">arg_exprs&#45;0</text>\n",
       "</g>\n",
       "<!-- 4525181632&#45;&gt;4525181760 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>4525181632&#45;&gt;4525181760</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M486.01,-291C466.55,-280.53 439.71,-266.07 418.17,-254.47\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"419.76,-251.36 409.29,-249.7 416.44,-257.52 419.76,-251.36\"/>\n",
       "</g>\n",
       "<!-- 4525416256 -->\n",
       "<g id=\"node22\" class=\"node\">\n",
       "<title>4525416256</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"515\" cy=\"-234\" rx=\"52.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"515\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">arg_exprs&#45;1</text>\n",
       "</g>\n",
       "<!-- 4525181632&#45;&gt;4525416256 -->\n",
       "<g id=\"edge25\" class=\"edge\">\n",
       "<title>4525181632&#45;&gt;4525416256</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M512.74,-287.7C513.07,-279.98 513.47,-270.71 513.84,-262.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"517.34,-262.25 514.27,-252.1 510.34,-261.95 517.34,-262.25\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node20\" class=\"node\">\n",
       "<title>10</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"310\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"310\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">int</text>\n",
       "</g>\n",
       "<!-- 4525181760&#45;&gt;10 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>4525181760&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M365.3,-216.76C355.41,-207.14 342.75,-194.84 332.04,-184.43\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"334.27,-181.71 324.66,-177.25 329.39,-186.73 334.27,-181.71\"/>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node21\" class=\"node\">\n",
       "<title>11</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"382\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"382\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">20</text>\n",
       "</g>\n",
       "<!-- 4525181760&#45;&gt;11 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>4525181760&#45;&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M382,-215.7C382,-207.98 382,-198.71 382,-190.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"385.5,-190.1 382,-180.1 378.5,-190.1 385.5,-190.1\"/>\n",
       "</g>\n",
       "<!-- 12 -->\n",
       "<g id=\"node23\" class=\"node\">\n",
       "<title>12</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"454\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"454\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">call</text>\n",
       "</g>\n",
       "<!-- 4525416256&#45;&gt;12 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>4525416256&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M500.54,-216.41C492.54,-207.22 482.47,-195.67 473.75,-185.66\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"476.31,-183.28 467.1,-178.04 471.04,-187.88 476.31,-183.28\"/>\n",
       "</g>\n",
       "<!-- 13 -->\n",
       "<g id=\"node24\" class=\"node\">\n",
       "<title>13</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"526\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"526\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">add</text>\n",
       "</g>\n",
       "<!-- 4525416256&#45;&gt;13 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>4525416256&#45;&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M517.72,-215.7C518.93,-207.98 520.39,-198.71 521.74,-190.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"525.22,-190.53 523.31,-180.1 518.3,-189.44 525.22,-190.53\"/>\n",
       "</g>\n",
       "<!-- 4525182848 -->\n",
       "<g id=\"node25\" class=\"node\">\n",
       "<title>4525182848</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"616\" cy=\"-162\" rx=\"45.49\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"616\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">arg_exprs</text>\n",
       "</g>\n",
       "<!-- 4525416256&#45;&gt;4525182848 -->\n",
       "<g id=\"edge24\" class=\"edge\">\n",
       "<title>4525416256&#45;&gt;4525182848</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M537.42,-217.46C551.73,-207.54 570.47,-194.56 586.05,-183.75\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"588.12,-186.58 594.34,-178.01 584.13,-180.83 588.12,-186.58\"/>\n",
       "</g>\n",
       "<!-- 4525182144 -->\n",
       "<g id=\"node26\" class=\"node\">\n",
       "<title>4525182144</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"554\" cy=\"-90\" rx=\"52.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"554\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">arg_exprs&#45;0</text>\n",
       "</g>\n",
       "<!-- 4525182848&#45;&gt;4525182144 -->\n",
       "<g id=\"edge20\" class=\"edge\">\n",
       "<title>4525182848&#45;&gt;4525182144</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M601.62,-144.76C593.83,-135.97 584.05,-124.93 575.38,-115.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"577.98,-112.8 568.73,-107.63 572.74,-117.44 577.98,-112.8\"/>\n",
       "</g>\n",
       "<!-- 4525182336 -->\n",
       "<g id=\"node29\" class=\"node\">\n",
       "<title>4525182336</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"677\" cy=\"-90\" rx=\"52.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"677\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">arg_exprs&#45;1</text>\n",
       "</g>\n",
       "<!-- 4525182848&#45;&gt;4525182336 -->\n",
       "<g id=\"edge23\" class=\"edge\">\n",
       "<title>4525182848&#45;&gt;4525182336</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M630.15,-144.76C637.74,-136.06 647.24,-125.15 655.71,-115.43\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"658.57,-117.47 662.51,-107.63 653.3,-112.87 658.57,-117.47\"/>\n",
       "</g>\n",
       "<!-- 14 -->\n",
       "<g id=\"node27\" class=\"node\">\n",
       "<title>14</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"495\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"495\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">var</text>\n",
       "</g>\n",
       "<!-- 4525182144&#45;&gt;14 -->\n",
       "<g id=\"edge18\" class=\"edge\">\n",
       "<title>4525182144&#45;&gt;14</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M540.02,-72.41C532.35,-63.31 522.73,-51.9 514.35,-41.96\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"516.8,-39.43 507.68,-34.04 511.44,-43.94 516.8,-39.43\"/>\n",
       "</g>\n",
       "<!-- 15 -->\n",
       "<g id=\"node28\" class=\"node\">\n",
       "<title>15</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"567\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"567\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n",
       "</g>\n",
       "<!-- 4525182144&#45;&gt;15 -->\n",
       "<g id=\"edge19\" class=\"edge\">\n",
       "<title>4525182144&#45;&gt;15</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M557.21,-71.7C558.65,-63.98 560.37,-54.71 561.96,-46.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"565.44,-46.58 563.82,-36.1 558.56,-45.3 565.44,-46.58\"/>\n",
       "</g>\n",
       "<!-- 16 -->\n",
       "<g id=\"node30\" class=\"node\">\n",
       "<title>16</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"664\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"664\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">var</text>\n",
       "</g>\n",
       "<!-- 4525182336&#45;&gt;16 -->\n",
       "<g id=\"edge21\" class=\"edge\">\n",
       "<title>4525182336&#45;&gt;16</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M673.79,-71.7C672.35,-63.98 670.63,-54.71 669.04,-46.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"672.44,-45.3 667.18,-36.1 665.56,-46.58 672.44,-45.3\"/>\n",
       "</g>\n",
       "<!-- 17 -->\n",
       "<g id=\"node31\" class=\"node\">\n",
       "<title>17</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"736\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"736\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n",
       "</g>\n",
       "<!-- 4525182336&#45;&gt;17 -->\n",
       "<g id=\"edge22\" class=\"edge\">\n",
       "<title>4525182336&#45;&gt;17</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M690.98,-72.41C698.65,-63.31 708.27,-51.9 716.65,-41.96\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"719.56,-43.94 723.32,-34.04 714.2,-39.43 719.56,-43.94\"/>\n",
       "</g>\n",
       "<!-- 18 -->\n",
       "<g id=\"node33\" class=\"node\">\n",
       "<title>18</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"375\" cy=\"-522\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"375\" y=\"-518.3\" font-family=\"Times,serif\" font-size=\"14.00\">call</text>\n",
       "</g>\n",
       "<!-- 4525515456&#45;&gt;18 -->\n",
       "<g id=\"edge31\" class=\"edge\">\n",
       "<title>4525515456&#45;&gt;18</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M402.47,-576.41C398.16,-568.04 392.85,-557.71 388.05,-548.37\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"391.16,-546.76 383.47,-539.47 384.93,-549.96 391.16,-546.76\"/>\n",
       "</g>\n",
       "<!-- 19 -->\n",
       "<g id=\"node34\" class=\"node\">\n",
       "<title>19</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"447\" cy=\"-522\" rx=\"27.1\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"447\" y=\"-518.3\" font-family=\"Times,serif\" font-size=\"14.00\">print</text>\n",
       "</g>\n",
       "<!-- 4525515456&#45;&gt;19 -->\n",
       "<g id=\"edge32\" class=\"edge\">\n",
       "<title>4525515456&#45;&gt;19</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M419.53,-576.41C423.84,-568.04 429.15,-557.71 433.95,-548.37\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"437.07,-549.96 438.53,-539.47 430.84,-546.76 437.07,-549.96\"/>\n",
       "</g>\n",
       "<!-- 4525515712 -->\n",
       "<g id=\"node35\" class=\"node\">\n",
       "<title>4525515712</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"540\" cy=\"-522\" rx=\"45.49\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"540\" y=\"-518.3\" font-family=\"Times,serif\" font-size=\"14.00\">arg_exprs</text>\n",
       "</g>\n",
       "<!-- 4525515456&#45;&gt;4525515712 -->\n",
       "<g id=\"edge43\" class=\"edge\">\n",
       "<title>4525515456&#45;&gt;4525515712</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M433.47,-580.81C453.26,-570.07 482.41,-554.25 505.22,-541.87\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"507.12,-544.82 514.24,-536.98 503.78,-538.67 507.12,-544.82\"/>\n",
       "</g>\n",
       "<!-- 4525516992 -->\n",
       "<g id=\"node36\" class=\"node\">\n",
       "<title>4525516992</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"550\" cy=\"-450\" rx=\"52.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"550\" y=\"-446.3\" font-family=\"Times,serif\" font-size=\"14.00\">arg_exprs&#45;0</text>\n",
       "</g>\n",
       "<!-- 4525515712&#45;&gt;4525516992 -->\n",
       "<g id=\"edge42\" class=\"edge\">\n",
       "<title>4525515712&#45;&gt;4525516992</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M542.47,-503.7C543.57,-495.98 544.9,-486.71 546.13,-478.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"549.61,-478.5 547.56,-468.1 542.68,-477.51 549.61,-478.5\"/>\n",
       "</g>\n",
       "<!-- 20 -->\n",
       "<g id=\"node37\" class=\"node\">\n",
       "<title>20</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"514\" cy=\"-378\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"514\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">call</text>\n",
       "</g>\n",
       "<!-- 4525516992&#45;&gt;20 -->\n",
       "<g id=\"edge33\" class=\"edge\">\n",
       "<title>4525516992&#45;&gt;20</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M541.29,-432.05C537.02,-423.77 531.8,-413.62 527.08,-404.42\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"530.07,-402.6 522.39,-395.31 523.85,-405.8 530.07,-402.6\"/>\n",
       "</g>\n",
       "<!-- 21 -->\n",
       "<g id=\"node38\" class=\"node\">\n",
       "<title>21</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"586\" cy=\"-378\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"586\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">f</text>\n",
       "</g>\n",
       "<!-- 4525516992&#45;&gt;21 -->\n",
       "<g id=\"edge34\" class=\"edge\">\n",
       "<title>4525516992&#45;&gt;21</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M558.71,-432.05C562.98,-423.77 568.2,-413.62 572.92,-404.42\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"576.15,-405.8 577.61,-395.31 569.93,-402.6 576.15,-405.8\"/>\n",
       "</g>\n",
       "<!-- 4525515776 -->\n",
       "<g id=\"node39\" class=\"node\">\n",
       "<title>4525515776</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"676\" cy=\"-378\" rx=\"45.49\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"676\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">arg_exprs</text>\n",
       "</g>\n",
       "<!-- 4525516992&#45;&gt;4525515776 -->\n",
       "<g id=\"edge41\" class=\"edge\">\n",
       "<title>4525516992&#45;&gt;4525515776</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M576.41,-434.33C595.4,-423.78 621.16,-409.46 641.73,-398.04\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"643.44,-401.09 650.48,-393.18 640.04,-394.97 643.44,-401.09\"/>\n",
       "</g>\n",
       "<!-- 4525515072 -->\n",
       "<g id=\"node40\" class=\"node\">\n",
       "<title>4525515072</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"674\" cy=\"-306\" rx=\"52.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"674\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">arg_exprs&#45;0</text>\n",
       "</g>\n",
       "<!-- 4525515776&#45;&gt;4525515072 -->\n",
       "<g id=\"edge37\" class=\"edge\">\n",
       "<title>4525515776&#45;&gt;4525515072</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M675.51,-359.7C675.29,-351.98 675.02,-342.71 674.77,-334.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"678.27,-334 674.49,-324.1 671.28,-334.2 678.27,-334\"/>\n",
       "</g>\n",
       "<!-- 4525516160 -->\n",
       "<g id=\"node43\" class=\"node\">\n",
       "<title>4525516160</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"797\" cy=\"-306\" rx=\"52.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"797\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">arg_exprs&#45;1</text>\n",
       "</g>\n",
       "<!-- 4525515776&#45;&gt;4525516160 -->\n",
       "<g id=\"edge40\" class=\"edge\">\n",
       "<title>4525515776&#45;&gt;4525516160</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M700.78,-362.67C718.65,-352.33 742.99,-338.25 762.72,-326.83\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"764.52,-329.83 771.42,-321.8 761.01,-323.78 764.52,-329.83\"/>\n",
       "</g>\n",
       "<!-- 22 -->\n",
       "<g id=\"node41\" class=\"node\">\n",
       "<title>22</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"638\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"638\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">int</text>\n",
       "</g>\n",
       "<!-- 4525515072&#45;&gt;22 -->\n",
       "<g id=\"edge35\" class=\"edge\">\n",
       "<title>4525515072&#45;&gt;22</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M665.29,-288.05C661.02,-279.77 655.8,-269.62 651.08,-260.42\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"654.07,-258.6 646.39,-251.31 647.85,-261.8 654.07,-258.6\"/>\n",
       "</g>\n",
       "<!-- 23 -->\n",
       "<g id=\"node42\" class=\"node\">\n",
       "<title>23</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"710\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"710\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 4525515072&#45;&gt;23 -->\n",
       "<g id=\"edge36\" class=\"edge\">\n",
       "<title>4525515072&#45;&gt;23</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M682.71,-288.05C686.98,-279.77 692.2,-269.62 696.92,-260.42\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"700.15,-261.8 701.61,-251.31 693.93,-258.6 700.15,-261.8\"/>\n",
       "</g>\n",
       "<!-- 24 -->\n",
       "<g id=\"node44\" class=\"node\">\n",
       "<title>24</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"795\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"795\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">int</text>\n",
       "</g>\n",
       "<!-- 4525516160&#45;&gt;24 -->\n",
       "<g id=\"edge38\" class=\"edge\">\n",
       "<title>4525516160&#45;&gt;24</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M796.51,-287.7C796.29,-279.98 796.02,-270.71 795.77,-262.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"799.27,-262 795.49,-252.1 792.28,-262.2 799.27,-262\"/>\n",
       "</g>\n",
       "<!-- 25 -->\n",
       "<g id=\"node45\" class=\"node\">\n",
       "<title>25</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"867\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"867\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 4525516160&#45;&gt;25 -->\n",
       "<g id=\"edge39\" class=\"edge\">\n",
       "<title>4525516160&#45;&gt;25</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M813.24,-288.76C822.73,-279.27 834.83,-267.17 845.15,-256.85\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"847.69,-259.26 852.28,-249.72 842.74,-254.31 847.69,-259.26\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x10dbdcc10>"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print_tree(root_nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "84771de7",
   "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": "9e1a4ab2",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Revisiting CCLearner"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e6af0b68",
   "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": 25,
   "id": "0738f522",
   "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": 26,
   "id": "9e1da541",
   "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": 27,
   "id": "bc08e300",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import javalang"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "cd8ef69d",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "CompilationUnit(imports=[], package=None, types=[ClassDeclaration(annotations=[], body=[FieldDeclaration(annotations=[], declarators=[VariableDeclarator(dimensions=[], initializer=Literal(postfix_operators=[], prefix_operators=[], qualifier=None, selectors=[], value=0), name=y)], documentation=None, modifiers={'private'}, type=BasicType(dimensions=[], name=int)), MethodDeclaration(annotations=[], body=[StatementExpression(expression=MethodInvocation(arguments=[Literal(postfix_operators=[], prefix_operators=[], qualifier=None, selectors=[], value=\"Hello Clone!\")], member=println, postfix_operators=[], prefix_operators=[], qualifier=System.out, selectors=[], type_arguments=None), label=None), LocalVariableDeclaration(annotations=[], declarators=[VariableDeclarator(dimensions=[], initializer=BinaryOperation(operandl=Literal(postfix_operators=[], prefix_operators=[], qualifier=None, selectors=[], value=10), operandr=MemberReference(member=y, postfix_operators=[], prefix_operators=[], qualifier=, selectors=[]), operator=+), name=j)], modifiers=set(), type=BasicType(dimensions=[], name=int)), ForStatement(body=BlockStatement(label=None, statements=[StatementExpression(expression=MethodInvocation(arguments=[Literal(postfix_operators=[], prefix_operators=[], qualifier=None, selectors=[], value=\"Another iteration\")], member=println, postfix_operators=[], prefix_operators=[], qualifier=System.out, selectors=[], type_arguments=None), label=None)]), control=ForControl(condition=BinaryOperation(operandl=MemberReference(member=i, postfix_operators=[], prefix_operators=[], qualifier=, selectors=[]), operandr=MemberReference(member=x, postfix_operators=[], prefix_operators=[], qualifier=, selectors=[]), operator=<), init=VariableDeclaration(annotations=[], declarators=[VariableDeclarator(dimensions=None, initializer=Literal(postfix_operators=[], prefix_operators=[], qualifier=None, selectors=[], value=0), name=i)], modifiers=set(), type=BasicType(dimensions=[], name=int)), update=[MemberReference(member=i, postfix_operators=['++'], prefix_operators=[], qualifier=, selectors=[])]), label=None)], documentation=None, modifiers={'public'}, name=foo, parameters=[FormalParameter(annotations=[], modifiers=set(), name=x, type=BasicType(dimensions=[], name=int), varargs=False)], return_type=None, throws=None, type_parameters=None)], documentation=None, extends=None, implements=None, modifiers={'public'}, name=Foo, type_parameters=None)])"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "javalang.parse.parse(code2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "934808be",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "It might be helpful to see the tree structure visualised."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "7a1dc930",
   "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": 30,
   "id": "1624a6d8",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 3.0.0 (20220226.1711)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"3838pt\" height=\"620pt\"\n",
       " viewBox=\"0.00 0.00 3837.74 620.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 616)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-616 3833.74,-616 3833.74,4 -4,4\"/>\n",
       "<!-- 4526234976 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>4526234976</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"402.29\" cy=\"-594\" rx=\"141.07\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"301.79\" y=\"-590.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.CompilationUnit&#39;</text>\n",
       "</g>\n",
       "<!-- 4526234928 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>4526234928</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"402.29\" cy=\"-522\" rx=\"141.07\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"301.79\" y=\"-518.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.ClassDeclaration&#39;</text>\n",
       "</g>\n",
       "<!-- 4526234976&#45;&gt;4526234928 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>4526234976&#45;&gt;4526234928</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M402.29,-575.7C402.29,-567.98 402.29,-558.71 402.29,-550.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"405.79,-550.1 402.29,-540.1 398.79,-550.1 405.79,-550.1\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"217.29\" cy=\"-450\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"217.29\" y=\"-446.3\" font-family=\"Times,serif\" font-size=\"14.00\">Foo</text>\n",
       "</g>\n",
       "<!-- 4526234928&#45;&gt;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>4526234928&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M353.51,-505.02C324.19,-495.07 286.28,-481.62 253.29,-468 251.47,-467.25 249.61,-466.45 247.74,-465.63\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"249.01,-462.37 238.45,-461.42 246.11,-468.74 249.01,-462.37\"/>\n",
       "</g>\n",
       "<!-- 4526233008 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>4526233008</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"402.29\" cy=\"-450\" rx=\"139.98\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"302.79\" y=\"-446.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.FieldDeclaration&#39;</text>\n",
       "</g>\n",
       "<!-- 4526234928&#45;&gt;4526233008 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>4526234928&#45;&gt;4526233008</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M402.29,-503.7C402.29,-495.98 402.29,-486.71 402.29,-478.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"405.79,-478.1 402.29,-468.1 398.79,-478.1 405.79,-478.1\"/>\n",
       "</g>\n",
       "<!-- 4526234832 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4526234832</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"941.29\" cy=\"-450\" rx=\"149.47\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"834.29\" y=\"-446.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.MethodDeclaration&#39;</text>\n",
       "</g>\n",
       "<!-- 4526234928&#45;&gt;4526234832 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>4526234928&#45;&gt;4526234832</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M497.41,-508.65C591.49,-496.43 735.27,-477.76 833.52,-465\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"834.01,-468.46 843.48,-463.7 833.11,-461.52 834.01,-468.46\"/>\n",
       "</g>\n",
       "<!-- 4526232816 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>4526232816</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"118.29\" cy=\"-378\" rx=\"118.08\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"35.29\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.BasicType&#39;</text>\n",
       "</g>\n",
       "<!-- 4526233008&#45;&gt;4526232816 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>4526233008&#45;&gt;4526232816</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M340.67,-433.81C295.58,-422.7 234.39,-407.62 187.6,-396.08\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"188.39,-392.67 177.85,-393.68 186.72,-399.47 188.39,-392.67\"/>\n",
       "</g>\n",
       "<!-- 4526232864 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>4526232864</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"402.29\" cy=\"-378\" rx=\"147.57\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"296.79\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.VariableDeclarator&#39;</text>\n",
       "</g>\n",
       "<!-- 4526233008&#45;&gt;4526232864 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>4526233008&#45;&gt;4526232864</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M402.29,-431.7C402.29,-423.98 402.29,-414.71 402.29,-406.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"405.79,-406.1 402.29,-396.1 398.79,-406.1 405.79,-406.1\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"595.29\" cy=\"-378\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"595.29\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">foo</text>\n",
       "</g>\n",
       "<!-- 4526234832&#45;&gt;5 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>4526234832&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M831.98,-437.68C771.82,-429.63 696.38,-416.51 631.29,-396 629.36,-395.39 627.4,-394.7 625.45,-393.95\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"626.41,-390.56 615.84,-389.88 623.68,-397.01 626.41,-390.56\"/>\n",
       "</g>\n",
       "<!-- 4526233104 -->\n",
       "<g id=\"node13\" class=\"node\">\n",
       "<title>4526233104</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"783.29\" cy=\"-378\" rx=\"142.97\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"681.29\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.FormalParameter&#39;</text>\n",
       "</g>\n",
       "<!-- 4526234832&#45;&gt;4526233104 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>4526234832&#45;&gt;4526233104</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M903.85,-432.41C881.71,-422.6 853.49,-410.1 829.91,-399.66\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"831.03,-396.32 820.46,-395.47 828.19,-402.72 831.03,-396.32\"/>\n",
       "</g>\n",
       "<!-- 4526233728 -->\n",
       "<g id=\"node14\" class=\"node\">\n",
       "<title>4526233728</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1099.29\" cy=\"-378\" rx=\"155.17\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"987.79\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.StatementExpression&#39;</text>\n",
       "</g>\n",
       "<!-- 4526234832&#45;&gt;4526233728 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>4526234832&#45;&gt;4526233728</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M978.73,-432.41C1000.79,-422.64 1028.89,-410.19 1052.41,-399.77\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1054.12,-402.84 1061.84,-395.59 1051.28,-396.44 1054.12,-402.84\"/>\n",
       "</g>\n",
       "<!-- 4526233584 -->\n",
       "<g id=\"node15\" class=\"node\">\n",
       "<title>4526233584</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1443.29\" cy=\"-378\" rx=\"170.87\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"1319.79\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.LocalVariableDeclaration&#39;</text>\n",
       "</g>\n",
       "<!-- 4526234832&#45;&gt;4526233584 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>4526234832&#45;&gt;4526233584</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1034.83,-435.96C1119.77,-424.11 1245.08,-406.64 1334.48,-394.17\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1335.23,-397.6 1344.65,-392.75 1334.26,-390.67 1335.23,-397.6\"/>\n",
       "</g>\n",
       "<!-- 4526234736 -->\n",
       "<g id=\"node16\" class=\"node\">\n",
       "<title>4526234736</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2742.29\" cy=\"-378\" rx=\"128.88\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"2651.29\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.ForStatement&#39;</text>\n",
       "</g>\n",
       "<!-- 4526234832&#45;&gt;4526234736 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>4526234832&#45;&gt;4526234736</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1081.11,-443.57C1419.56,-430.41 2279.29,-397 2609.93,-384.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2610.17,-387.64 2620.03,-383.75 2609.9,-380.64 2610.17,-387.64\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"118.29\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"118.29\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">int</text>\n",
       "</g>\n",
       "<!-- 4526232816&#45;&gt;2 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>4526232816&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M118.29,-359.7C118.29,-351.98 118.29,-342.71 118.29,-334.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"121.79,-334.1 118.29,-324.1 114.79,-334.1 121.79,-334.1\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"265.29\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"265.29\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">y</text>\n",
       "</g>\n",
       "<!-- 4526232864&#45;&gt;3 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>4526232864&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M369.82,-360.41C347.11,-348.81 317.02,-333.43 294.95,-322.16\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"296.53,-319.03 286.03,-317.6 293.34,-325.26 296.53,-319.03\"/>\n",
       "</g>\n",
       "<!-- 4526232960 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>4526232960</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"415.29\" cy=\"-306\" rx=\"104.78\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"342.79\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.Literal&#39;</text>\n",
       "</g>\n",
       "<!-- 4526232864&#45;&gt;4526232960 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>4526232864&#45;&gt;4526232960</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M405.5,-359.7C406.94,-351.98 408.66,-342.71 410.25,-334.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"413.73,-334.58 412.11,-324.1 406.85,-333.3 413.73,-334.58\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"415.29\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"415.29\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- 4526232960&#45;&gt;4 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>4526232960&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M415.29,-287.7C415.29,-279.98 415.29,-270.71 415.29,-262.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"418.79,-262.1 415.29,-252.1 411.79,-262.1 418.79,-262.1\"/>\n",
       "</g>\n",
       "<!-- 4526233152 -->\n",
       "<g id=\"node17\" class=\"node\">\n",
       "<title>4526233152</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"707.29\" cy=\"-306\" rx=\"118.08\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"624.29\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.BasicType&#39;</text>\n",
       "</g>\n",
       "<!-- 4526233104&#45;&gt;4526233152 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>4526233104&#45;&gt;4526233152</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M764.89,-360.05C755.37,-351.28 743.59,-340.43 733.16,-330.83\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"735.24,-327.99 725.52,-323.79 730.5,-333.14 735.24,-327.99\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node18\" class=\"node\">\n",
       "<title>6</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"870.29\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"870.29\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">x</text>\n",
       "</g>\n",
       "<!-- 4526233104&#45;&gt;6 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>4526233104&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M804.35,-360.05C816.81,-350.03 832.65,-337.29 845.68,-326.8\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"848.18,-329.28 853.78,-320.29 843.79,-323.83 848.18,-329.28\"/>\n",
       "</g>\n",
       "<!-- 4526233680 -->\n",
       "<g id=\"node20\" class=\"node\">\n",
       "<title>4526233680</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1086.29\" cy=\"-306\" rx=\"146.47\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"981.79\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.MethodInvocation&#39;</text>\n",
       "</g>\n",
       "<!-- 4526233728&#45;&gt;4526233680 -->\n",
       "<g id=\"edge19\" class=\"edge\">\n",
       "<title>4526233728&#45;&gt;4526233680</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1096.08,-359.7C1094.64,-351.98 1092.92,-342.71 1091.32,-334.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1094.73,-333.3 1089.47,-324.1 1087.85,-334.58 1094.73,-333.3\"/>\n",
       "</g>\n",
       "<!-- 4526233248 -->\n",
       "<g id=\"node25\" class=\"node\">\n",
       "<title>4526233248</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1369.29\" cy=\"-306\" rx=\"118.08\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"1286.29\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.BasicType&#39;</text>\n",
       "</g>\n",
       "<!-- 4526233584&#45;&gt;4526233248 -->\n",
       "<g id=\"edge24\" class=\"edge\">\n",
       "<title>4526233584&#45;&gt;4526233248</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1425.38,-360.05C1416.17,-351.35 1404.8,-340.59 1394.71,-331.04\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1396.96,-328.36 1387.29,-324.03 1392.15,-333.45 1396.96,-328.36\"/>\n",
       "</g>\n",
       "<!-- 4526233536 -->\n",
       "<g id=\"node26\" class=\"node\">\n",
       "<title>4526233536</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1653.29\" cy=\"-306\" rx=\"147.57\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"1547.79\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.VariableDeclarator&#39;</text>\n",
       "</g>\n",
       "<!-- 4526233584&#45;&gt;4526233536 -->\n",
       "<g id=\"edge25\" class=\"edge\">\n",
       "<title>4526233584&#45;&gt;4526233536</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1492.26,-360.68C1523.01,-350.43 1562.84,-337.15 1595.19,-326.37\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1596.59,-329.59 1604.97,-323.11 1594.37,-322.95 1596.59,-329.59\"/>\n",
       "</g>\n",
       "<!-- 4526234496 -->\n",
       "<g id=\"node36\" class=\"node\">\n",
       "<title>4526234496</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2742.29\" cy=\"-306\" rx=\"120.48\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"2657.79\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.ForControl&#39;</text>\n",
       "</g>\n",
       "<!-- 4526234736&#45;&gt;4526234496 -->\n",
       "<g id=\"edge35\" class=\"edge\">\n",
       "<title>4526234736&#45;&gt;4526234496</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2742.29,-359.7C2742.29,-351.98 2742.29,-342.71 2742.29,-334.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2745.79,-334.1 2742.29,-324.1 2738.79,-334.1 2745.79,-334.1\"/>\n",
       "</g>\n",
       "<!-- 4526234544 -->\n",
       "<g id=\"node37\" class=\"node\">\n",
       "<title>4526234544</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"3317.29\" cy=\"-306\" rx=\"137.58\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"3219.29\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.BlockStatement&#39;</text>\n",
       "</g>\n",
       "<!-- 4526234736&#45;&gt;4526234544 -->\n",
       "<g id=\"edge36\" class=\"edge\">\n",
       "<title>4526234736&#45;&gt;4526234544</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2835.95,-365.6C2938.46,-353.12 3102.5,-333.15 3210.07,-320.05\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"3210.8,-323.49 3220.3,-318.81 3209.95,-316.54 3210.8,-323.49\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node19\" class=\"node\">\n",
       "<title>7</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"707.29\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"707.29\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">int</text>\n",
       "</g>\n",
       "<!-- 4526233152&#45;&gt;7 -->\n",
       "<g id=\"edge18\" class=\"edge\">\n",
       "<title>4526233152&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M707.29,-287.7C707.29,-279.98 707.29,-270.71 707.29,-262.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"710.79,-262.1 707.29,-252.1 703.79,-262.1 710.79,-262.1\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node21\" class=\"node\">\n",
       "<title>8</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"913.29\" cy=\"-234\" rx=\"50.89\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"913.29\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">System.out</text>\n",
       "</g>\n",
       "<!-- 4526233680&#45;&gt;8 -->\n",
       "<g id=\"edge20\" class=\"edge\">\n",
       "<title>4526233680&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1045.73,-288.59C1018.39,-277.53 982.43,-262.98 954.88,-251.83\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"956.1,-248.55 945.51,-248.04 953.47,-255.03 956.1,-248.55\"/>\n",
       "</g>\n",
       "<!-- 4526233632 -->\n",
       "<g id=\"node22\" class=\"node\">\n",
       "<title>4526233632</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1086.29\" cy=\"-234\" rx=\"104.78\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"1013.79\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.Literal&#39;</text>\n",
       "</g>\n",
       "<!-- 4526233680&#45;&gt;4526233632 -->\n",
       "<g id=\"edge21\" class=\"edge\">\n",
       "<title>4526233680&#45;&gt;4526233632</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1086.29,-287.7C1086.29,-279.98 1086.29,-270.71 1086.29,-262.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1089.79,-262.1 1086.29,-252.1 1082.79,-262.1 1089.79,-262.1\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node23\" class=\"node\">\n",
       "<title>9</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1243.29\" cy=\"-234\" rx=\"34.39\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"1243.29\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">println</text>\n",
       "</g>\n",
       "<!-- 4526233680&#45;&gt;9 -->\n",
       "<g id=\"edge22\" class=\"edge\">\n",
       "<title>4526233680&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1123.5,-288.41C1149.23,-276.94 1183.23,-261.78 1208.43,-250.54\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1209.92,-253.71 1217.63,-246.44 1207.07,-247.32 1209.92,-253.71\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node24\" class=\"node\">\n",
       "<title>10</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1086.29\" cy=\"-162\" rx=\"64.19\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"1086.29\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">&quot;Hello Clone!&quot;</text>\n",
       "</g>\n",
       "<!-- 4526233632&#45;&gt;10 -->\n",
       "<g id=\"edge23\" class=\"edge\">\n",
       "<title>4526233632&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1086.29,-215.7C1086.29,-207.98 1086.29,-198.71 1086.29,-190.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1089.79,-190.1 1086.29,-180.1 1082.79,-190.1 1089.79,-190.1\"/>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node27\" class=\"node\">\n",
       "<title>11</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1369.29\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"1369.29\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">int</text>\n",
       "</g>\n",
       "<!-- 4526233248&#45;&gt;11 -->\n",
       "<g id=\"edge26\" class=\"edge\">\n",
       "<title>4526233248&#45;&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1369.29,-287.7C1369.29,-279.98 1369.29,-270.71 1369.29,-262.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1372.79,-262.1 1369.29,-252.1 1365.79,-262.1 1372.79,-262.1\"/>\n",
       "</g>\n",
       "<!-- 12 -->\n",
       "<g id=\"node28\" class=\"node\">\n",
       "<title>12</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1468.29\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"1468.29\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">j</text>\n",
       "</g>\n",
       "<!-- 4526233536&#45;&gt;12 -->\n",
       "<g id=\"edge27\" class=\"edge\">\n",
       "<title>4526233536&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1604.17,-288.9C1574.9,-278.97 1537.16,-265.57 1504.29,-252 1502.47,-251.25 1500.61,-250.45 1498.74,-249.63\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1500.01,-246.37 1489.45,-245.42 1497.11,-252.74 1500.01,-246.37\"/>\n",
       "</g>\n",
       "<!-- 4526233488 -->\n",
       "<g id=\"node29\" class=\"node\">\n",
       "<title>4526233488</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1653.29\" cy=\"-234\" rx=\"139.98\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"1553.79\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.BinaryOperation&#39;</text>\n",
       "</g>\n",
       "<!-- 4526233536&#45;&gt;4526233488 -->\n",
       "<g id=\"edge28\" class=\"edge\">\n",
       "<title>4526233536&#45;&gt;4526233488</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1653.29,-287.7C1653.29,-279.98 1653.29,-270.71 1653.29,-262.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1656.79,-262.1 1653.29,-252.1 1649.79,-262.1 1656.79,-262.1\"/>\n",
       "</g>\n",
       "<!-- 13 -->\n",
       "<g id=\"node30\" class=\"node\">\n",
       "<title>13</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1368.29\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"1368.29\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">+</text>\n",
       "</g>\n",
       "<!-- 4526233488&#45;&gt;13 -->\n",
       "<g id=\"edge29\" class=\"edge\">\n",
       "<title>4526233488&#45;&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1567.27,-219.76C1518.68,-211.03 1457.26,-197.88 1404.29,-180 1402.37,-179.35 1400.43,-178.63 1398.48,-177.86\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1399.46,-174.47 1388.89,-173.73 1396.69,-180.9 1399.46,-174.47\"/>\n",
       "</g>\n",
       "<!-- 4526233440 -->\n",
       "<g id=\"node31\" class=\"node\">\n",
       "<title>4526233440</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1518.29\" cy=\"-162\" rx=\"104.78\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"1445.79\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.Literal&#39;</text>\n",
       "</g>\n",
       "<!-- 4526233488&#45;&gt;4526233440 -->\n",
       "<g id=\"edge30\" class=\"edge\">\n",
       "<title>4526233488&#45;&gt;4526233440</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1621.3,-216.41C1602.5,-206.66 1578.57,-194.25 1558.5,-183.85\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1560.08,-180.72 1549.59,-179.23 1556.85,-186.94 1560.08,-180.72\"/>\n",
       "</g>\n",
       "<!-- 4526233344 -->\n",
       "<g id=\"node32\" class=\"node\">\n",
       "<title>4526233344</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1788.29\" cy=\"-162\" rx=\"147.57\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"1682.79\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.MemberReference&#39;</text>\n",
       "</g>\n",
       "<!-- 4526233488&#45;&gt;4526233344 -->\n",
       "<g id=\"edge31\" class=\"edge\">\n",
       "<title>4526233488&#45;&gt;4526233344</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1685.28,-216.41C1703.73,-206.85 1727.11,-194.72 1746.94,-184.44\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1748.79,-187.42 1756.06,-179.71 1745.57,-181.21 1748.79,-187.42\"/>\n",
       "</g>\n",
       "<!-- 14 -->\n",
       "<g id=\"node33\" class=\"node\">\n",
       "<title>14</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1518.29\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"1518.29\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">10</text>\n",
       "</g>\n",
       "<!-- 4526233440&#45;&gt;14 -->\n",
       "<g id=\"edge32\" class=\"edge\">\n",
       "<title>4526233440&#45;&gt;14</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1518.29,-143.7C1518.29,-135.98 1518.29,-126.71 1518.29,-118.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1521.79,-118.1 1518.29,-108.1 1514.79,-118.1 1521.79,-118.1\"/>\n",
       "</g>\n",
       "<!-- 15 -->\n",
       "<g id=\"node34\" class=\"node\">\n",
       "<title>15</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1752.29\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 4526233344&#45;&gt;15 -->\n",
       "<g id=\"edge33\" class=\"edge\">\n",
       "<title>4526233344&#45;&gt;15</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1779.39,-143.7C1775.13,-135.4 1769.94,-125.31 1765.24,-116.19\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1768.28,-114.44 1760.59,-107.14 1762.05,-117.64 1768.28,-114.44\"/>\n",
       "</g>\n",
       "<!-- 16 -->\n",
       "<g id=\"node35\" class=\"node\">\n",
       "<title>16</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1824.29\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"1824.29\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">y</text>\n",
       "</g>\n",
       "<!-- 4526233344&#45;&gt;16 -->\n",
       "<g id=\"edge34\" class=\"edge\">\n",
       "<title>4526233344&#45;&gt;16</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1797.19,-143.7C1801.45,-135.4 1806.64,-125.31 1811.34,-116.19\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1814.53,-117.64 1815.99,-107.14 1808.3,-114.44 1814.53,-117.64\"/>\n",
       "</g>\n",
       "<!-- 4526233776 -->\n",
       "<g id=\"node38\" class=\"node\">\n",
       "<title>4526233776</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2356.29\" cy=\"-234\" rx=\"151.37\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"2247.79\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.VariableDeclaration&#39;</text>\n",
       "</g>\n",
       "<!-- 4526234496&#45;&gt;4526233776 -->\n",
       "<g id=\"edge37\" class=\"edge\">\n",
       "<title>4526234496&#45;&gt;4526233776</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2668.78,-291.67C2605.32,-280.16 2513.45,-263.5 2445.74,-251.22\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2445.97,-247.71 2435.51,-249.37 2444.72,-254.59 2445.97,-247.71\"/>\n",
       "</g>\n",
       "<!-- 4526234400 -->\n",
       "<g id=\"node39\" class=\"node\">\n",
       "<title>4526234400</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2742.29\" cy=\"-234\" rx=\"139.98\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"2642.79\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.BinaryOperation&#39;</text>\n",
       "</g>\n",
       "<!-- 4526234496&#45;&gt;4526234400 -->\n",
       "<g id=\"edge38\" class=\"edge\">\n",
       "<title>4526234496&#45;&gt;4526234400</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2742.29,-287.7C2742.29,-279.98 2742.29,-270.71 2742.29,-262.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2745.79,-262.1 2742.29,-252.1 2738.79,-262.1 2745.79,-262.1\"/>\n",
       "</g>\n",
       "<!-- 4526234448 -->\n",
       "<g id=\"node40\" class=\"node\">\n",
       "<title>4526234448</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"3285.29\" cy=\"-234\" rx=\"147.57\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"3179.79\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.MemberReference&#39;</text>\n",
       "</g>\n",
       "<!-- 4526234496&#45;&gt;4526234448 -->\n",
       "<g id=\"edge39\" class=\"edge\">\n",
       "<title>4526234496&#45;&gt;4526234448</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2830.14,-293.68C2924.98,-281.45 3076.11,-261.97 3177.93,-248.84\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"3178.47,-252.3 3187.94,-247.55 3177.57,-245.36 3178.47,-252.3\"/>\n",
       "</g>\n",
       "<!-- 4526235072 -->\n",
       "<g id=\"node57\" class=\"node\">\n",
       "<title>4526235072</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"3627.29\" cy=\"-234\" rx=\"155.17\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"3515.79\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.StatementExpression&#39;</text>\n",
       "</g>\n",
       "<!-- 4526234544&#45;&gt;4526235072 -->\n",
       "<g id=\"edge56\" class=\"edge\">\n",
       "<title>4526234544&#45;&gt;4526235072</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3383.03,-290.15C3431.77,-279.15 3498.37,-264.11 3549.71,-252.52\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"3550.78,-255.86 3559.77,-250.25 3549.24,-249.04 3550.78,-255.86\"/>\n",
       "</g>\n",
       "<!-- 4526233968 -->\n",
       "<g id=\"node41\" class=\"node\">\n",
       "<title>4526233968</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2072.29\" cy=\"-162\" rx=\"118.08\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"1989.29\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.BasicType&#39;</text>\n",
       "</g>\n",
       "<!-- 4526233776&#45;&gt;4526233968 -->\n",
       "<g id=\"edge40\" class=\"edge\">\n",
       "<title>4526233776&#45;&gt;4526233968</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2293.61,-217.55C2248.72,-206.49 2188.25,-191.58 2141.86,-180.15\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2142.44,-176.69 2131.89,-177.69 2140.76,-183.48 2142.44,-176.69\"/>\n",
       "</g>\n",
       "<!-- 4526234112 -->\n",
       "<g id=\"node42\" class=\"node\">\n",
       "<title>4526234112</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2356.29\" cy=\"-162\" rx=\"147.57\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"2250.79\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.VariableDeclarator&#39;</text>\n",
       "</g>\n",
       "<!-- 4526233776&#45;&gt;4526234112 -->\n",
       "<g id=\"edge41\" class=\"edge\">\n",
       "<title>4526233776&#45;&gt;4526234112</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2356.29,-215.7C2356.29,-207.98 2356.29,-198.71 2356.29,-190.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2359.79,-190.1 2356.29,-180.1 2352.79,-190.1 2359.79,-190.1\"/>\n",
       "</g>\n",
       "<!-- 20 -->\n",
       "<g id=\"node47\" class=\"node\">\n",
       "<title>20</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2549.29\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"2549.29\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">&lt;</text>\n",
       "</g>\n",
       "<!-- 4526234400&#45;&gt;20 -->\n",
       "<g id=\"edge46\" class=\"edge\">\n",
       "<title>4526234400&#45;&gt;20</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2690.48,-217.17C2659.61,-207.33 2619.84,-193.94 2585.29,-180 2583.46,-179.26 2581.6,-178.48 2579.72,-177.67\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2580.98,-174.4 2570.43,-173.48 2578.11,-180.78 2580.98,-174.4\"/>\n",
       "</g>\n",
       "<!-- 4526234256 -->\n",
       "<g id=\"node48\" class=\"node\">\n",
       "<title>4526234256</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2742.29\" cy=\"-162\" rx=\"147.57\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"2636.79\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.MemberReference&#39;</text>\n",
       "</g>\n",
       "<!-- 4526234400&#45;&gt;4526234256 -->\n",
       "<g id=\"edge47\" class=\"edge\">\n",
       "<title>4526234400&#45;&gt;4526234256</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2742.29,-215.7C2742.29,-207.98 2742.29,-198.71 2742.29,-190.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2745.79,-190.1 2742.29,-180.1 2738.79,-190.1 2745.79,-190.1\"/>\n",
       "</g>\n",
       "<!-- 4526234352 -->\n",
       "<g id=\"node49\" class=\"node\">\n",
       "<title>4526234352</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"3055.29\" cy=\"-162\" rx=\"147.57\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"2949.79\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.MemberReference&#39;</text>\n",
       "</g>\n",
       "<!-- 4526234400&#45;&gt;4526234352 -->\n",
       "<g id=\"edge48\" class=\"edge\">\n",
       "<title>4526234400&#45;&gt;4526234352</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2808.67,-218.15C2858.23,-207.07 2926.09,-191.89 2978.08,-180.27\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2978.93,-183.66 2987.93,-178.07 2977.4,-176.83 2978.93,-183.66\"/>\n",
       "</g>\n",
       "<!-- 4526216880 -->\n",
       "<g id=\"node54\" class=\"node\">\n",
       "<title>4526216880</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"3275.29\" cy=\"-162\" rx=\"54.69\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"3275.29\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">4526216880</text>\n",
       "</g>\n",
       "<!-- 4526234448&#45;&gt;4526216880 -->\n",
       "<g id=\"edge53\" class=\"edge\">\n",
       "<title>4526234448&#45;&gt;4526216880</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3282.82,-215.7C3281.72,-207.98 3280.39,-198.71 3279.16,-190.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"3282.61,-189.51 3277.73,-180.1 3275.68,-190.5 3282.61,-189.51\"/>\n",
       "</g>\n",
       "<!-- 25 -->\n",
       "<g id=\"node55\" class=\"node\">\n",
       "<title>25</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"3375.29\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 4526234448&#45;&gt;25 -->\n",
       "<g id=\"edge54\" class=\"edge\">\n",
       "<title>4526234448&#45;&gt;25</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3307.08,-216.05C3320.09,-205.94 3336.66,-193.04 3350.22,-182.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"3352.46,-185.19 3358.21,-176.29 3348.16,-179.66 3352.46,-185.19\"/>\n",
       "</g>\n",
       "<!-- 26 -->\n",
       "<g id=\"node56\" class=\"node\">\n",
       "<title>26</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"3447.29\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"3447.29\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">i</text>\n",
       "</g>\n",
       "<!-- 4526234448&#45;&gt;26 -->\n",
       "<g id=\"edge55\" class=\"edge\">\n",
       "<title>4526234448&#45;&gt;26</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3325.48,-216.61C3350.32,-206.35 3382.79,-192.72 3411.29,-180 3413.09,-179.2 3414.93,-178.36 3416.79,-177.51\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"3418.44,-180.61 3426.04,-173.22 3415.49,-174.26 3418.44,-180.61\"/>\n",
       "</g>\n",
       "<!-- 17 -->\n",
       "<g id=\"node43\" class=\"node\">\n",
       "<title>17</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2072.29\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"2072.29\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">int</text>\n",
       "</g>\n",
       "<!-- 4526233968&#45;&gt;17 -->\n",
       "<g id=\"edge42\" class=\"edge\">\n",
       "<title>4526233968&#45;&gt;17</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2072.29,-143.7C2072.29,-135.98 2072.29,-126.71 2072.29,-118.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2075.79,-118.1 2072.29,-108.1 2068.79,-118.1 2075.79,-118.1\"/>\n",
       "</g>\n",
       "<!-- 18 -->\n",
       "<g id=\"node44\" class=\"node\">\n",
       "<title>18</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2281.29\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"2281.29\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">i</text>\n",
       "</g>\n",
       "<!-- 4526234112&#45;&gt;18 -->\n",
       "<g id=\"edge43\" class=\"edge\">\n",
       "<title>4526234112&#45;&gt;18</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2338.13,-144.05C2327.95,-134.55 2315.14,-122.59 2304.26,-112.44\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2306.44,-109.69 2296.74,-105.42 2301.67,-114.81 2306.44,-109.69\"/>\n",
       "</g>\n",
       "<!-- 4526234160 -->\n",
       "<g id=\"node45\" class=\"node\">\n",
       "<title>4526234160</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2431.29\" cy=\"-90\" rx=\"104.78\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"2358.79\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.Literal&#39;</text>\n",
       "</g>\n",
       "<!-- 4526234112&#45;&gt;4526234160 -->\n",
       "<g id=\"edge44\" class=\"edge\">\n",
       "<title>4526234112&#45;&gt;4526234160</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2374.44,-144.05C2383.84,-135.28 2395.47,-124.43 2405.76,-114.83\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2408.38,-117.17 2413.3,-107.79 2403.6,-112.05 2408.38,-117.17\"/>\n",
       "</g>\n",
       "<!-- 19 -->\n",
       "<g id=\"node46\" class=\"node\">\n",
       "<title>19</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2431.29\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"2431.29\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- 4526234160&#45;&gt;19 -->\n",
       "<g id=\"edge45\" class=\"edge\">\n",
       "<title>4526234160&#45;&gt;19</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2431.29,-71.7C2431.29,-63.98 2431.29,-54.71 2431.29,-46.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2434.79,-46.1 2431.29,-36.1 2427.79,-46.1 2434.79,-46.1\"/>\n",
       "</g>\n",
       "<!-- 21 -->\n",
       "<g id=\"node50\" class=\"node\">\n",
       "<title>21</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2706.29\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 4526234256&#45;&gt;21 -->\n",
       "<g id=\"edge49\" class=\"edge\">\n",
       "<title>4526234256&#45;&gt;21</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2733.39,-143.7C2729.13,-135.4 2723.94,-125.31 2719.24,-116.19\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2722.28,-114.44 2714.59,-107.14 2716.05,-117.64 2722.28,-114.44\"/>\n",
       "</g>\n",
       "<!-- 22 -->\n",
       "<g id=\"node51\" class=\"node\">\n",
       "<title>22</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2778.29\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"2778.29\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">i</text>\n",
       "</g>\n",
       "<!-- 4526234256&#45;&gt;22 -->\n",
       "<g id=\"edge50\" class=\"edge\">\n",
       "<title>4526234256&#45;&gt;22</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2751.19,-143.7C2755.45,-135.4 2760.64,-125.31 2765.34,-116.19\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2768.53,-117.64 2769.99,-107.14 2762.3,-114.44 2768.53,-117.64\"/>\n",
       "</g>\n",
       "<!-- 23 -->\n",
       "<g id=\"node52\" class=\"node\">\n",
       "<title>23</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"3019.29\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "</g>\n",
       "<!-- 4526234352&#45;&gt;23 -->\n",
       "<g id=\"edge51\" class=\"edge\">\n",
       "<title>4526234352&#45;&gt;23</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3046.39,-143.7C3042.13,-135.4 3036.94,-125.31 3032.24,-116.19\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"3035.28,-114.44 3027.59,-107.14 3029.05,-117.64 3035.28,-114.44\"/>\n",
       "</g>\n",
       "<!-- 24 -->\n",
       "<g id=\"node53\" class=\"node\">\n",
       "<title>24</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"3091.29\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"3091.29\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">x</text>\n",
       "</g>\n",
       "<!-- 4526234352&#45;&gt;24 -->\n",
       "<g id=\"edge52\" class=\"edge\">\n",
       "<title>4526234352&#45;&gt;24</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3064.19,-143.7C3068.45,-135.4 3073.64,-125.31 3078.34,-116.19\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"3081.53,-117.64 3082.99,-107.14 3075.3,-114.44 3081.53,-117.64\"/>\n",
       "</g>\n",
       "<!-- 4526235024 -->\n",
       "<g id=\"node58\" class=\"node\">\n",
       "<title>4526235024</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"3638.29\" cy=\"-162\" rx=\"146.47\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"3533.79\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.MethodInvocation&#39;</text>\n",
       "</g>\n",
       "<!-- 4526235072&#45;&gt;4526235024 -->\n",
       "<g id=\"edge57\" class=\"edge\">\n",
       "<title>4526235072&#45;&gt;4526235024</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3630.01,-215.7C3631.22,-207.98 3632.68,-198.71 3634.03,-190.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"3637.51,-190.53 3635.6,-180.1 3630.59,-189.44 3637.51,-190.53\"/>\n",
       "</g>\n",
       "<!-- 27 -->\n",
       "<g id=\"node59\" class=\"node\">\n",
       "<title>27</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"3465.29\" cy=\"-90\" rx=\"50.89\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"3465.29\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">System.out</text>\n",
       "</g>\n",
       "<!-- 4526235024&#45;&gt;27 -->\n",
       "<g id=\"edge58\" class=\"edge\">\n",
       "<title>4526235024&#45;&gt;27</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3597.73,-144.59C3570.39,-133.53 3534.43,-118.98 3506.88,-107.83\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"3508.1,-104.55 3497.51,-104.04 3505.47,-111.03 3508.1,-104.55\"/>\n",
       "</g>\n",
       "<!-- 4526234640 -->\n",
       "<g id=\"node60\" class=\"node\">\n",
       "<title>4526234640</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"3638.29\" cy=\"-90\" rx=\"104.78\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"3565.79\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">class &#39;javalang.tree.Literal&#39;</text>\n",
       "</g>\n",
       "<!-- 4526235024&#45;&gt;4526234640 -->\n",
       "<g id=\"edge59\" class=\"edge\">\n",
       "<title>4526235024&#45;&gt;4526234640</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3638.29,-143.7C3638.29,-135.98 3638.29,-126.71 3638.29,-118.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"3641.79,-118.1 3638.29,-108.1 3634.79,-118.1 3641.79,-118.1\"/>\n",
       "</g>\n",
       "<!-- 28 -->\n",
       "<g id=\"node61\" class=\"node\">\n",
       "<title>28</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"3795.29\" cy=\"-90\" rx=\"34.39\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"3795.29\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">println</text>\n",
       "</g>\n",
       "<!-- 4526235024&#45;&gt;28 -->\n",
       "<g id=\"edge60\" class=\"edge\">\n",
       "<title>4526235024&#45;&gt;28</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3675.5,-144.41C3701.23,-132.94 3735.23,-117.78 3760.43,-106.54\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"3761.92,-109.71 3769.63,-102.44 3759.07,-103.32 3761.92,-109.71\"/>\n",
       "</g>\n",
       "<!-- 29 -->\n",
       "<g id=\"node62\" class=\"node\">\n",
       "<title>29</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"3638.29\" cy=\"-18\" rx=\"79.09\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"3638.29\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">&quot;Another iteration&quot;</text>\n",
       "</g>\n",
       "<!-- 4526234640&#45;&gt;29 -->\n",
       "<g id=\"edge61\" class=\"edge\">\n",
       "<title>4526234640&#45;&gt;29</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3638.29,-71.7C3638.29,-63.98 3638.29,-54.71 3638.29,-46.11\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"3641.79,-46.1 3638.29,-36.1 3634.79,-46.1 3641.79,-46.1\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x10dc26a00>"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = javalang.parse.parse(code2)\n",
    "print_tree(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ff042b56",
   "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": "5983bd5a",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "CCLearner defines eight different types of tokens for the clone analysis."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "bc7c534d",
   "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": 32,
   "id": "30e94232",
   "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": "09cb6679",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The first three types of tokens can easily be extracted using a tokenizer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "46282aa4",
   "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": "ba5d8f4e",
   "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": 34,
   "id": "0b25b832",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[BasicType \"int\" line 1, position 1,\n",
       " Identifier \"i\" line 1, position 5,\n",
       " Operator \"=\" line 1, position 7,\n",
       " Operator \"-\" line 1, position 9,\n",
       " DecimalInteger \"1\" line 1, position 10,\n",
       " Separator \";\" line 1, position 11]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(javalang.tokenizer.tokenize(\"int i = -1;\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5305ad23",
   "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": "ec04ccc2",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To extract literals values, we can, however, use the AST:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "514a5df3",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "example_tree = javalang.parse.parse(\"class Test {int i = -1;}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "a18a7efa",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Literal: Literal(postfix_operators=[], prefix_operators=['-'], qualifier=None, selectors=[], value=1)\n"
     ]
    }
   ],
   "source": [
    "for _, node in example_tree.filter(javalang.tree.Literal):\n",
    "    print(f\"Literal: {node}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7627aa4e",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We thus need to prepend the prefix operators when collecting literals."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "458d84da",
   "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": 38,
   "id": "426f8c2c",
   "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": "961815e9",
   "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": 39,
   "id": "ffd6ea68",
   "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": 40,
   "id": "a4cbfccf",
   "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": "5985a53b",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Qualified names (C7 tokens) are explicitly available in the AST."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "31d0f116",
   "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": "c10998df",
   "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": 42,
   "id": "4d363fba",
   "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": 43,
   "id": "cce3dd3d",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'class': 1, 'void': 1, 'for': 1}\n",
      "{'=': 3, '+': 1, '<': 1, '++': 1}\n",
      "{'{': 3, ';': 6, '(': 4, ')': 4, '.': 4, '}': 3}\n",
      "{'0': 2, '\"Hello Clone!\"': 1, '10': 1, '\"Another iteration\"': 1}\n",
      "{'int': 4}\n",
      "{'println': 2, 'foo': 1}\n",
      "{'System.out': 2}\n",
      "{'y': 2, 'j': 1, 'i': 3, 'x': 2}\n"
     ]
    }
   ],
   "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": "2be95547",
   "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": 44,
   "id": "eb4e7113",
   "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": 45,
   "id": "2419933c",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'reserved': {'class': 1, 'void': 1, 'for': 1},\n",
       " 'operators': {'=': 2, '<': 1, '++': 1},\n",
       " 'markers': {'{': 3, '(': 4, ')': 4, '.': 4, ';': 5, '}': 3},\n",
       " 'literals': {'\"Hello Clone!\"': 1, '10': 1, '0': 1, '\"Another iteration\"': 1},\n",
       " 'type_ids': {'\"Another iteration\"': 3},\n",
       " 'method_ids': {'println': 2, 'foo': 1},\n",
       " 'qualified_ids': {'System.out': 2},\n",
       " 'variable_ids': {'j': 1, 'i': 3, 'x': 2}}"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_tokens(code1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "604293f5",
   "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": 46,
   "id": "4e494bd2",
   "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 = list(tokens1.keys()) + list(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 += num1 - num2\n",
    "        summ += num1 + num2\n",
    "    \n",
    "    return 1.0 - diff / summ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "acd5bcee",
   "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": 48,
   "id": "43dcd70c",
   "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": 49,
   "id": "40d22913",
   "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": 50,
   "id": "11ba6a59",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0212765957446808"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sim_score(tokens1[\"markers\"], tokens2[\"markers\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "3d533708",
   "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": "code",
   "execution_count": 52,
   "id": "5d49646b",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1.0,\n",
       " 1.1578947368421053,\n",
       " 1.0212765957446808,\n",
       " 1.1111111111111112,\n",
       " 1.1428571428571428,\n",
       " 1.0,\n",
       " 1.0,\n",
       " 1.0769230769230769]"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "feature_vector(tokens1, tokens2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "cca17a0e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1.2,\n",
       " 1.1578947368421053,\n",
       " 1.2333333333333334,\n",
       " 0.9090909090909091,\n",
       " 1.4545454545454546,\n",
       " 1.25,\n",
       " 1.3333333333333333,\n",
       " 1.1578947368421053]"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "feature_vector(tokens1, tokens4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5a5bc068",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "At this point, we can 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. However, rather than doing this, we will take our prediction even a step further and use more syntactical information for our prediction."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98e2d40b",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Code Embeddings"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22daed00",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Before moving on to somewhat more classical examples of syntax-based analysis of code, we consider a recent trend: In order to allow machine learning models to make predictions on code, we need to convert the source code to a format that is suitable as input for ML models, i.e., numerical vectors, typically referred to as _embeddings_. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01b80b1d",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "A well-known example of embeddings in a different domain is Word2vec: Word2vec is a two-layer neural net that processes text by “vectorizing” words. Its input is a text corpus and its output is a set of vectors: feature vectors that represent words in that corpus. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6a63033",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The purpose and usefulness of Word2vec is to group the vectors of similar words together in vectorspace. That is, it detects similarities mathematically. Word2vec creates vectors that are distributed numerical representations of word features, features such as the context of individual words."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "89bcb469",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Given enough data, usage and contexts, Word2vec can make highly accurate guesses about a word’s meaning based on past appearances. Those guesses can be used to establish a word’s association with other words (e.g. “man” is to “boy” what “woman” is to “girl”), or cluster documents and classify them by topic. Those clusters can form the basis of search, sentiment analysis and recommendations in such diverse fields as scientific research, legal discovery, e-commerce and customer relationship management."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b39c9ac",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The output of the Word2vec neural net is a vocabulary in which each item has a vector attached to it, which can be fed into a deep-learning net or simply queried to detect relationships between words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "1b894259",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import gensim.downloader\n",
    "glove_vectors = gensim.downloader.load('glove-twitter-25')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "6c6bd4d0",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('facebook', 0.948005199432373),\n",
       " ('tweet', 0.9403423070907593),\n",
       " ('fb', 0.9342358708381653),\n",
       " ('instagram', 0.9104824066162109),\n",
       " ('chat', 0.8964964747428894),\n",
       " ('hashtag', 0.8885937333106995),\n",
       " ('tweets', 0.8878158330917358),\n",
       " ('tl', 0.8778461217880249),\n",
       " ('link', 0.8778210878372192),\n",
       " ('internet', 0.8753897547721863)]"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "glove_vectors.most_similar('twitter')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b999f033",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    },
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# ASTNN"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c87136d4",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Recent work provides the strong evidence that syntactic knowledge contributes more in modeling source code\n",
    "and can obtain better representation than traditional token-based methods. We will consider one example approach to creating code embeddings from syntactic information, ASTNN:\n",
    "\n",
    "Zhang, J., Wang, X., Zhang, H., Sun, H., Wang, K., & Liu, X. (2019, May). A novel neural source code representation based on abstract syntax tree. In 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE) (pp. 783-794). IEEE.\n",
    "\n",
    "ASTNN splits the large AST of one code fragment into a set of small trees at the statement level and performs tree-based neural embeddings on all statement trees. Recurrent Neural Networks (RNNs) are used to encode statements and the sequential dependency between the statements into a vector. These vectors capture the naturalness of source code, and can serve as a neural source code representation.\n",
    "\n",
    "\n",
    "As an example application for these embeddings, we can once again use code clone detection, which boils down to the following:\n",
    "\n",
    "- Compute vector embeddings $e_1$, $e_2 \\in \\mathbb{R}^m$ for two code snippets\n",
    "- The distance between the code snippets is $r = |e_1 - e_2| \\in \\mathbb{R}^m$\n",
    "- This can be reduced to a clone probability using a linear layer with sigmoid activation function $p = \\textrm{sigmoid}(r) \\in [0,1]$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d1d2521",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "## Preprocessing"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "798185ef",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The first step in producing the code embeddings consists of parsing the code, transforming the AST into a sequence of statement trees, and then replacing string labels of the tree nodes with numeric indices."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ee2863c",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We will eventually apply our encoding to a dataset of C programs (using the model trained by the authors of ASTNN), so in the following we will consider the syntax trees of C programs created by Python's C Parser library: [PyCParser](https://github.com/eliben/pycparser)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "c3c19f98",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code = \"\"\"\n",
    "int foo() {}\n",
    "\n",
    "int main(int argc, char** argv) {\n",
    "  if (argc > 0) {\n",
    "      foo();\n",
    "  }\n",
    "  return 0;\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "2452eff4",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "FileAST(ext=[FuncDef(decl=Decl(name='foo',\n",
       "                               quals=[\n",
       "                                     ],\n",
       "                               align=[\n",
       "                                     ],\n",
       "                               storage=[\n",
       "                                       ],\n",
       "                               funcspec=[\n",
       "                                        ],\n",
       "                               type=FuncDecl(args=None,\n",
       "                                             type=TypeDecl(declname='foo',\n",
       "                                                           quals=[\n",
       "                                                                 ],\n",
       "                                                           align=None,\n",
       "                                                           type=IdentifierType(names=['int'\n",
       "                                                                                     ]\n",
       "                                                                               )\n",
       "                                                           )\n",
       "                                             ),\n",
       "                               init=None,\n",
       "                               bitsize=None\n",
       "                               ),\n",
       "                     param_decls=None,\n",
       "                     body=Compound(block_items=None\n",
       "                                   )\n",
       "                     ),\n",
       "             FuncDef(decl=Decl(name='main',\n",
       "                               quals=[\n",
       "                                     ],\n",
       "                               align=[\n",
       "                                     ],\n",
       "                               storage=[\n",
       "                                       ],\n",
       "                               funcspec=[\n",
       "                                        ],\n",
       "                               type=FuncDecl(args=ParamList(params=[Decl(name='argc',\n",
       "                                                                         quals=[\n",
       "                                                                               ],\n",
       "                                                                         align=[\n",
       "                                                                               ],\n",
       "                                                                         storage=[\n",
       "                                                                                 ],\n",
       "                                                                         funcspec=[\n",
       "                                                                                  ],\n",
       "                                                                         type=TypeDecl(declname='argc',\n",
       "                                                                                       quals=[\n",
       "                                                                                             ],\n",
       "                                                                                       align=None,\n",
       "                                                                                       type=IdentifierType(names=['int'\n",
       "                                                                                                                 ]\n",
       "                                                                                                           )\n",
       "                                                                                       ),\n",
       "                                                                         init=None,\n",
       "                                                                         bitsize=None\n",
       "                                                                         ),\n",
       "                                                                    Decl(name='argv',\n",
       "                                                                         quals=[\n",
       "                                                                               ],\n",
       "                                                                         align=[\n",
       "                                                                               ],\n",
       "                                                                         storage=[\n",
       "                                                                                 ],\n",
       "                                                                         funcspec=[\n",
       "                                                                                  ],\n",
       "                                                                         type=PtrDecl(quals=[\n",
       "                                                                                            ],\n",
       "                                                                                      type=PtrDecl(quals=[\n",
       "                                                                                                         ],\n",
       "                                                                                                   type=TypeDecl(declname='argv',\n",
       "                                                                                                                 quals=[\n",
       "                                                                                                                       ],\n",
       "                                                                                                                 align=None,\n",
       "                                                                                                                 type=IdentifierType(names=['char'\n",
       "                                                                                                                                           ]\n",
       "                                                                                                                                     )\n",
       "                                                                                                                 )\n",
       "                                                                                                   )\n",
       "                                                                                      ),\n",
       "                                                                         init=None,\n",
       "                                                                         bitsize=None\n",
       "                                                                         )\n",
       "                                                                   ]\n",
       "                                                            ),\n",
       "                                             type=TypeDecl(declname='main',\n",
       "                                                           quals=[\n",
       "                                                                 ],\n",
       "                                                           align=None,\n",
       "                                                           type=IdentifierType(names=['int'\n",
       "                                                                                     ]\n",
       "                                                                               )\n",
       "                                                           )\n",
       "                                             ),\n",
       "                               init=None,\n",
       "                               bitsize=None\n",
       "                               ),\n",
       "                     param_decls=None,\n",
       "                     body=Compound(block_items=[If(cond=BinaryOp(op='>',\n",
       "                                                                 left=ID(name='argc'\n",
       "                                                                         ),\n",
       "                                                                 right=Constant(type='int',\n",
       "                                                                                value='0'\n",
       "                                                                                )\n",
       "                                                                 ),\n",
       "                                                   iftrue=Compound(block_items=[FuncCall(name=ID(name='foo'\n",
       "                                                                                                 ),\n",
       "                                                                                         args=None\n",
       "                                                                                         )\n",
       "                                                                               ]\n",
       "                                                                   ),\n",
       "                                                   iffalse=None\n",
       "                                                   ),\n",
       "                                                Return(expr=Constant(type='int',\n",
       "                                                                     value='0'\n",
       "                                                                     )\n",
       "                                                       )\n",
       "                                               ]\n",
       "                                   )\n",
       "                     )\n",
       "            ]\n",
       "        )"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import pycparser\n",
    "code_parser = pycparser.c_parser.CParser()\n",
    "\n",
    "ast = code_parser.parse(code)\n",
    "ast"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7539efa",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "At the core of the ASTNN lies the extraction of statement trees from the AST. A statement tree is essentially a substree of the AST for a statement-node, and the list of statement trees is achieved by a preorder traversal of the AST."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "c5e176d9",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current node: FileAST\n",
      "Current node: FuncDef\n",
      "Current node: Decl\n",
      "Current node: FuncDecl\n",
      "Current node: TypeDecl\n",
      "Current node: IdentifierType\n",
      "Current node: Compound\n",
      "Current node: FuncDef\n",
      "Current node: Decl\n",
      "Current node: FuncDecl\n",
      "Current node: ParamList\n",
      "Current node: Decl\n",
      "Current node: TypeDecl\n",
      "Current node: IdentifierType\n",
      "Current node: Decl\n",
      "Current node: PtrDecl\n",
      "Current node: PtrDecl\n",
      "Current node: TypeDecl\n",
      "Current node: IdentifierType\n",
      "Current node: TypeDecl\n",
      "Current node: IdentifierType\n",
      "Current node: Compound\n",
      "Current node: If\n",
      "Current node: BinaryOp\n",
      "Current node: ID\n",
      "Current node: Constant\n",
      "Current node: Compound\n",
      "Current node: FuncCall\n",
      "Current node: ID\n",
      "Current node: Return\n",
      "Current node: Constant\n"
     ]
    }
   ],
   "source": [
    "def get_statements(node):\n",
    "    name = node.__class__.__name__\n",
    "    print(f\"Current node: {name}\")\n",
    "    for _, child in node.children():\n",
    "        get_statements(child)\n",
    "    \n",
    "get_statements(ast)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b4a0a857",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "For our example program, we would like to create statement trees for the if statement (`If`), the function call (`FuncCall`) , and the return statement (`Return`). ASTNN also treats function declarations (`FuncDef`) as special statement nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "492ecfed",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Statement node: FuncDef\n",
      "Statement node: FuncDef\n",
      "Statement node: If\n",
      "Statement node: FuncCall\n",
      "Statement node: Return\n"
     ]
    }
   ],
   "source": [
    "def get_statements(node):\n",
    "    name = node.__class__.__name__\n",
    "    if name in [\"FuncDef\", \"FuncCall\", \"If\", \"Return\"]:\n",
    "        print(f\"Statement node: {name}\")\n",
    "    for _, child in node.children():\n",
    "        get_statements(child)\n",
    "    \n",
    "get_statements(ast)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f0de7ca",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "A statement tree (ST-tree) rooted by the statement node $s \\in S$ is the tree consisting of node s and all of\n",
    "its descendants, but excluding any statements nodes. For example, for a method call statement, all child nodes are in the statement tree, since none of the children are statements. On the other hand, an if-statement consists of an expression as well as the conditionally executed statements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "210d0910",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "FileAST(ext=[FuncDef(decl=Decl(name='main',\n",
       "                               quals=[\n",
       "                                     ],\n",
       "                               align=[\n",
       "                                     ],\n",
       "                               storage=[\n",
       "                                       ],\n",
       "                               funcspec=[\n",
       "                                        ],\n",
       "                               type=FuncDecl(args=None,\n",
       "                                             type=TypeDecl(declname='main',\n",
       "                                                           quals=[\n",
       "                                                                 ],\n",
       "                                                           align=None,\n",
       "                                                           type=IdentifierType(names=['int'\n",
       "                                                                                     ]\n",
       "                                                                               )\n",
       "                                                           )\n",
       "                                             ),\n",
       "                               init=None,\n",
       "                               bitsize=None\n",
       "                               ),\n",
       "                     param_decls=None,\n",
       "                     body=Compound(block_items=[If(cond=BinaryOp(op='>',\n",
       "                                                                 left=Constant(type='int',\n",
       "                                                                               value='42'\n",
       "                                                                               ),\n",
       "                                                                 right=Constant(type='int',\n",
       "                                                                                value='0'\n",
       "                                                                                )\n",
       "                                                                 ),\n",
       "                                                   iftrue=Compound(block_items=[FuncCall(name=ID(name='foo'\n",
       "                                                                                                 ),\n",
       "                                                                                         args=None\n",
       "                                                                                         )\n",
       "                                                                               ]\n",
       "                                                                   ),\n",
       "                                                   iffalse=None\n",
       "                                                   )\n",
       "                                               ]\n",
       "                                   )\n",
       "                     )\n",
       "            ]\n",
       "        )"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "code_parser.parse(\"int main() {if (42 > 0) { foo(); } }\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "890719d0",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Consequently, when creating statement trees, if we encounter a `FuncDef`, `If`, `While`, `DoWhile`, or `Switch` statement, then we only include the first child in the statement tree, and ignore all other children (which are statements)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d2909366",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "A second exception are for-loops, which contain of multiple children: The `init`, `cond`, and `next` children are part of the for-statement itself, while the last child (`stmt`) is a statement and should be excluded."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "45f61d46",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "FileAST(ext=[FuncDef(decl=Decl(name='main',\n",
       "                               quals=[\n",
       "                                     ],\n",
       "                               align=[\n",
       "                                     ],\n",
       "                               storage=[\n",
       "                                       ],\n",
       "                               funcspec=[\n",
       "                                        ],\n",
       "                               type=FuncDecl(args=None,\n",
       "                                             type=TypeDecl(declname='main',\n",
       "                                                           quals=[\n",
       "                                                                 ],\n",
       "                                                           align=None,\n",
       "                                                           type=IdentifierType(names=['int'\n",
       "                                                                                     ]\n",
       "                                                                               )\n",
       "                                                           )\n",
       "                                             ),\n",
       "                               init=None,\n",
       "                               bitsize=None\n",
       "                               ),\n",
       "                     param_decls=None,\n",
       "                     body=Compound(block_items=[For(init=DeclList(decls=[Decl(name='i',\n",
       "                                                                              quals=[\n",
       "                                                                                    ],\n",
       "                                                                              align=[\n",
       "                                                                                    ],\n",
       "                                                                              storage=[\n",
       "                                                                                      ],\n",
       "                                                                              funcspec=[\n",
       "                                                                                       ],\n",
       "                                                                              type=TypeDecl(declname='i',\n",
       "                                                                                            quals=[\n",
       "                                                                                                  ],\n",
       "                                                                                            align=None,\n",
       "                                                                                            type=IdentifierType(names=['int'\n",
       "                                                                                                                      ]\n",
       "                                                                                                                )\n",
       "                                                                                            ),\n",
       "                                                                              init=Constant(type='int',\n",
       "                                                                                            value='0'\n",
       "                                                                                            ),\n",
       "                                                                              bitsize=None\n",
       "                                                                              )\n",
       "                                                                        ]\n",
       "                                                                  ),\n",
       "                                                    cond=BinaryOp(op='<',\n",
       "                                                                  left=ID(name='i'\n",
       "                                                                          ),\n",
       "                                                                  right=Constant(type='int',\n",
       "                                                                                 value='10'\n",
       "                                                                                 )\n",
       "                                                                  ),\n",
       "                                                    next=UnaryOp(op='p++',\n",
       "                                                                 expr=ID(name='i'\n",
       "                                                                         )\n",
       "                                                                 ),\n",
       "                                                    stmt=Compound(block_items=[FuncCall(name=ID(name='foo'\n",
       "                                                                                                ),\n",
       "                                                                                        args=None\n",
       "                                                                                        )\n",
       "                                                                              ]\n",
       "                                                                  )\n",
       "                                                    )\n",
       "                                               ]\n",
       "                                   )\n",
       "                     )\n",
       "            ]\n",
       "        )"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "code_parser.parse(\"int main() {for (int i = 0; i < 10; i++) { foo(); } }\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "191d76fc",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Note that the for-loop (and the other block-constructs we considered previously) define a single statement as child node, but of course it is common that they can contain more complex code blocks. In pycparser, these are are captured by `Compound` nodes."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f04aba7",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "It is also worth noting that pycparser stores nodes as tuples `(str, node)`, so when traversing the AST to create statement trees we need to look at the second entry of such a tuple only. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "c7472b29",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class ASTNode(object):\n",
    "    def __init__(self, node):\n",
    "        self.node = node\n",
    "        self.name = self.node.__class__.__name__\n",
    "        children = node.children()\n",
    "        if self.name in ['FuncDef', 'If', 'While', 'DoWhile', 'Switch']:\n",
    "            self.__children = [ASTNode(children[0][1])]\n",
    "        elif self.name == 'For':\n",
    "            children = node.children()\n",
    "            self.__children = [ASTNode(children[c][1]) for c in range(0, len(children) - 1)]\n",
    "        else:\n",
    "            self.__children = [ASTNode(child) for _, child in node.children()]\n",
    "\n",
    "    def children(self):\n",
    "        return self.__children\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return f\"{self.name}: {self.children()}\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6cbca5d5",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Now that we have a class to capture statement trees, we just need to implement the tree traversal to collect them for the statements we are interested (for the sake of the example for now only `FuncDef`, `FuncCall`, `If`, `Return`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "f6d7e065",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[FuncDef: [Decl: [FuncDecl: [TypeDecl: [IdentifierType: []]]]],\n",
       " FuncDef: [Decl: [FuncDecl: [ParamList: [Decl: [TypeDecl: [IdentifierType: []]], Decl: [PtrDecl: [PtrDecl: [TypeDecl: [IdentifierType: []]]]]], TypeDecl: [IdentifierType: []]]]],\n",
       " If: [BinaryOp: [ID: [], Constant: []]],\n",
       " FuncCall: [ID: []],\n",
       " Return: [Constant: []]]"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def get_statement_trees(node):\n",
    "    name = node.__class__.__name__\n",
    "    trees = []\n",
    "    if name in [\"FuncDef\", \"FuncCall\", \"If\", \"Return\"]:\n",
    "        trees.append(ASTNode(node))\n",
    "\n",
    "    for _, child in node.children():\n",
    "        trees.extend(get_statement_trees(child))\n",
    "    \n",
    "    return trees\n",
    "    \n",
    "get_statement_trees(ast)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3199d470",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Our statement trees currently only describe the syntactic structure, but we have lost the lexical information about the actual tokens used (e.g., which methods were called). We add a `token` to our `ASTNode` class.\n",
    "- If the node is a leaf node (i.e., a variable name or a literal), then we use the actual lexeme.\n",
    "- For type declaration nodes we use the name of the type.\n",
    "- For operators, we use the operator symbol.\n",
    "- In other cases, we use the token type as the name."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "6363c20c",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class ASTNode(ASTNode):\n",
    "    def __init__(self, node):\n",
    "        super().__init__(node)\n",
    "        self.token = self.get_token()\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return f\"{self.token}: {self.children()}\"\n",
    "    \n",
    "    def is_leaf(self):\n",
    "        return len(self.node.children()) == 0    \n",
    "    \n",
    "    def get_token(self, lower=True):\n",
    "        name = self.node.__class__.__name__\n",
    "        token = name\n",
    "\n",
    "        if self.is_leaf():\n",
    "            attr_names = self.node.attr_names\n",
    "            if 'names' in attr_names:\n",
    "                token = self.node.names[0] # Identifiers\n",
    "            elif 'name' in attr_names:\n",
    "                token = self.node.name # ID\n",
    "            else:\n",
    "                token = self.node.value # Constant\n",
    "        else:\n",
    "            if name == 'TypeDecl':\n",
    "                token = self.node.declname\n",
    "            if self.node.attr_names:\n",
    "                attr_names = self.node.attr_names\n",
    "                if 'op' in attr_names:\n",
    "                    token = self.node.op # Binary Op\n",
    "\n",
    "        return token"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "b0460425",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[FuncDef: [Decl: [FuncDecl: [foo: [int: []]]]],\n",
       " FuncDef: [Decl: [FuncDecl: [ParamList: [Decl: [argc: [int: []]], Decl: [PtrDecl: [PtrDecl: [argv: [char: []]]]]], main: [int: []]]]],\n",
       " If: [>: [argc: [], 0: []]],\n",
       " FuncCall: [foo: []],\n",
       " Return: [0: []]]"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_statement_trees(ast)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e4ab761f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Since a neural network cannot process string labels of the trees, we first need to convert these to integers by taking their index in a vocabulary. In ASTNN this is done using a pre-trained word2vec vocabulary. If the label cannot be found, then an out-of-vocabulary index is assigned."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d97cd425",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The word2vec model is trained on the source code corpus; we will simply use the model generated by the ASTNN authors here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "f401eb62",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from gensim.models import Word2Vec\n",
    "w2v = Word2Vec.load(\"data/astnn/w2v_128\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db50f289",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The index of a word can be determined by directly looking the word up in the model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "d50f5767",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def label_to_index(label: str) -> int:\n",
    "    return w2v.wv.get_index(label, default=len(w2v.wv))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1969258e",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To convert the labels of a statement tree to numbers, we apply this to each node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "fd0d57e8",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def tree_to_index(node: ASTNode):\n",
    "    token = node.token\n",
    "    indices = [label_to_index(token)]\n",
    "    for child in node.children():\n",
    "        indices.append(tree_to_index(child))\n",
    "    return indices"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c6a6b0f0",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's have a look at the statement trees for our example snippet."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "b03c8af1",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[33, [2, [30, [9161, [4]]]]]\n",
      "[33, [2, [30, [74, [2, [217, [4]]], [2, [68, [68, [218, [43]]]]]], [40, [4]]]]]\n",
      "[15, [48, [217], [5]]]\n",
      "[11, [9161]]\n",
      "[39, [5]]\n"
     ]
    }
   ],
   "source": [
    "from typing import Any\n",
    "import pycparser\n",
    "\n",
    "for s in get_statement_trees(ast):\n",
    "    print(tree_to_index(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eac6e786",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Our implementation of the AST traversal is limited to our example code snippet, and will not work on more general code snippets. To apply this to any C code snippets, let's use the full version, which mainly differs in which aspects of the AST it takes into consideration. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "855d74a9",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "ast_block_token = ['FuncDef', 'If', 'While', 'DoWhile', 'Switch']\n",
    "\n",
    "\n",
    "class ASTNode(object):\n",
    "    def __init__(self, node, single=False):\n",
    "        self.node = node\n",
    "\n",
    "        self.__is_str = isinstance(self.node, str)\n",
    "        self.token = self.get_token()\n",
    "\n",
    "        if single:\n",
    "            self.__children = []\n",
    "        else:\n",
    "            self.__children = self.add_children()\n",
    "\n",
    "    def is_leaf(self):\n",
    "        if self.__is_str:\n",
    "            return True\n",
    "\n",
    "        return len(self.node.children()) == 0\n",
    "\n",
    "    def add_children(self):\n",
    "        if self.__is_str:\n",
    "            return []\n",
    "        children = self.node.children()\n",
    "        if self.token in ast_block_token:\n",
    "            return [ASTNode(children[0][1])]\n",
    "        elif self.token == 'For':\n",
    "            return [ASTNode(children[c][1]) for c in range(0, len(children) - 1)]\n",
    "        else:\n",
    "            return [ASTNode(child) for _, child in children]\n",
    "\n",
    "    def children(self):\n",
    "        return self.__children"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "645a4f4a",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The retrieval of the right token is also slightly more involved beyond our snippet."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "cc5be34e",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class ASTNode(ASTNode):\n",
    "    def get_token(self, lower=True):\n",
    "        if self.__is_str:\n",
    "            return self.node\n",
    "\n",
    "        name = self.node.__class__.__name__\n",
    "        token = name\n",
    "        is_name = False\n",
    "\n",
    "        if self.is_leaf():\n",
    "            attr_names = self.node.attr_names\n",
    "            if attr_names:\n",
    "                if 'names' in attr_names:\n",
    "                    token = self.node.names[0]\n",
    "                elif 'name' in attr_names:\n",
    "                    token = self.node.name\n",
    "                    is_name = True\n",
    "                else:\n",
    "                    token = self.node.value\n",
    "            else:\n",
    "                token = name\n",
    "        else:\n",
    "            if name == 'TypeDecl':\n",
    "                token = self.node.declname\n",
    "            if self.node.attr_names:\n",
    "                attr_names = self.node.attr_names\n",
    "                if 'op' in attr_names:\n",
    "                    if self.node.op[0] == 'p':\n",
    "                        token = self.node.op[1:]\n",
    "                    else:\n",
    "                        token = self.node.op\n",
    "        if token is None:\n",
    "            token = name\n",
    "        if lower and is_name:\n",
    "            token = token.lower()\n",
    "        return token\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return f\"{self.get_token()}: {self.children()}\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a97769ba",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Finally, our retrieval of statement trees was slightly simplified. For example, the original ASTNN implementation also creates nodes for compound statements, and adds dedicated `End` nodes. These end-nodes do not match lexical tokens but inform the inference algorithm about the indentation of the code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "6d86c464",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def get_statements(node, statement_sequence):\n",
    "    children = node.children()\n",
    "    name = node.__class__.__name__\n",
    "    if name in ['FuncDef', 'If', 'For', 'While', 'DoWhile']:\n",
    "        statement_sequence.append(ASTNode(node))\n",
    "        if name != 'For':\n",
    "            inner_offset = 1\n",
    "        else:\n",
    "            inner_offset = len(children) - 1\n",
    "        for i in range(inner_offset, len(children)):\n",
    "            child = children[i][1]\n",
    "            if child.__class__.__name__ not in ['FuncDef', 'If', 'For', 'While', 'DoWhile', 'Compound']:\n",
    "                statement_sequence.append(ASTNode(child))\n",
    "            get_statements(child, statement_sequence)\n",
    "    elif name == 'Compound':\n",
    "        statement_sequence.append(ASTNode(name))\n",
    "        for _, child in children:\n",
    "            if child.__class__.__name__ not in ['If', 'For', 'While', 'DoWhile']:\n",
    "                statement_sequence.append(ASTNode(child))\n",
    "            get_statements(child, statement_sequence)\n",
    "        statement_sequence.append(ASTNode('End'))\n",
    "    else:\n",
    "        for _, child in children:\n",
    "            get_statements(child, statement_sequence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "bb631cd5",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[FuncDef: [Decl: [FuncDecl: [foo: [int: []]]]],\n",
       " Compound: [],\n",
       " End: [],\n",
       " FuncDef: [Decl: [FuncDecl: [ParamList: [Decl: [argc: [int: []]], Decl: [PtrDecl: [PtrDecl: [argv: [char: []]]]]], main: [int: []]]]],\n",
       " Compound: [],\n",
       " If: [>: [argc: [], 0: []]],\n",
       " Compound: [],\n",
       " FuncCall: [foo: []],\n",
       " End: [],\n",
       " Return: [0: []],\n",
       " End: []]"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "statements = []\n",
    "get_statements(ast, statements)\n",
    "statements"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "04c55c40",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def to_statement_trees(ast) -> list[Any]:\n",
    "    statements = []\n",
    "    get_statements(ast, statements)\n",
    "    tree = []\n",
    "    for s in statements:\n",
    "        tree.append(tree_to_index(s))\n",
    "    return tree"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "962933ff",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    },
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Model"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53216b64",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Given the numeric encoding of tokens in the statement trees, the next step of building the embeddings consists of recursively creating vectors for statement trees."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20d6e9cc",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The lexical vector $v_n$ for a node $n$ is calculated as $v_n = W_e^T x_n$, where $x_n$ is the numerical representation of node $n$ (i.e., the index retrieved from Word2vec)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6692bd8e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The vector representation of a node $n$ is computed by the following equation:\n",
    "\n",
    "$h = \\sigma (W_n^T + \\displaystyle\\sum_{i \\in [1, C]} h_i + b_n)$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5557044f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Here, $W_n \\in \\mathcal{R}^{d \\times k}$ is the weight matrix with encoding dimensions $k$.  $b_n$ is a bias term, $h_i$ is the hidden state for each child $i$, $h$ is the updated hidden state, and $\\sigma$ is the activation function, which in ASTNN is the identity function."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "81b94903",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The final encoding is then sampled with max pooling: $e_t = [max(h_{i1}, \\ldots, max(h_{ik})], i = 1, \\ldots, N$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f3dd06c5",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Dynamic Batching of trees (Algorithm 1, function `DynamicBatch()`)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66f3dad3",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The computation of the vector encoding of a statement tree recursively depends on the vector encoding of its subnodes in the tree. Furthermore, For example, directly calculating $h$ for the two parents in one batch may also be impossible if the number of children of the two parents differs. This means that the computation of $h$ cannot be parallelised, but unfortunately that is exactly what is necessary in order to train a model on a large dataset."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "850f062f",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The authors of ASTNN have developed a batch processing algorithm that allows to encode multiple samples (i.e., code fragments) simultaneously. However, generally batch processing on multiway ST-trees makes it difficult since the number of children nodes varies for the parent nodes in the same position of one batch."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc27788c",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The algorithm batches $L$ samples of statement trees and then breadthfirst traverses them starting from the root nodes. For the current nodes $ns$ in the same position of the batch, the algorithm first calculates $v_n$ in batch, and then group all their children nodes by the node positions. That is, it groups all nodes at the same depth in the statement trees at the same position, such that the calculation of these nodes can be performed in parallel. Based on the grouping, the algorithm recursively performs batch processing on all children nodes. After getting the results of all children nodes, $h$ can be computed in batch, and all node vectors of calculated statement trees are recorded."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "32951f33",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "![Children Batching](figures/5_astnn_children_batching.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "891f0060",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Children batching\n",
    "\n",
    "- $ns$: `nodes`\n",
    "- $C$: `children`\n",
    "- $CI$: `children_index`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3456b84",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Since our focus lies in the program analysis itself more than on the construction of an effective machine learning pipeline, we will present the ML-related code here, but will not go into as much detail as for the previous parts."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "674f8bd4",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The following code sets up the batch tree encoder used by ASTNN, and initially sets up the required datastructures."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "id": "32472a96",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import numpy.typing\n",
    "import tensorflow as tf\n",
    "from tensorflow import keras\n",
    "from typing import Optional, Union\n",
    "\n",
    "\n",
    "class BatchTreeEncoder(tf.Module):\n",
    "    def __init__(\n",
    "        self,\n",
    "        vocab_size: int,\n",
    "        vocab_embedding_dim: int,\n",
    "        encode_dim: int,\n",
    "        batch_size: int = 64,\n",
    "        pretrained_weight: Optional[numpy.typing.ArrayLike] = None,\n",
    "    ):\n",
    "        super().__init__()\n",
    "        self.embedding = keras.layers.Embedding(vocab_size, vocab_embedding_dim)\n",
    "        self.embedding_dim = vocab_embedding_dim\n",
    "        self.encode_dim = encode_dim\n",
    "        self.W_c = keras.layers.Dense(encode_dim, input_shape=(vocab_embedding_dim,))\n",
    "        self.activation = tf.keras.activations.relu\n",
    "        self.batch_size = batch_size\n",
    "        self.node_list: list[tf.Tensor] = []\n",
    "        self.batch_node: Union[list[int], tf.Tensor] = []\n",
    "\n",
    "        # pretrained embedding from word2vec\n",
    "        if pretrained_weight is not None:\n",
    "            self.embedding.build((vocab_size, vocab_embedding_dim))\n",
    "            self.embedding.set_weights([pretrained_weight])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "961baf97",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The actual traversal implements Algorithm 1 from the ASTNN paper. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "54226cc3",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class BatchTreeEncoder(BatchTreeEncoder):\n",
    "    def traverse(self, nodes, batch_index: list[int]) -> Optional[tf.Tensor]:\n",
    "        # Recursively compute embedding of multiple statement trees `nodes`\n",
    "        size = len(nodes)\n",
    "        if not size:\n",
    "            return None\n",
    "\n",
    "        # line 9: create an output placeholder `BC` for the batch input\n",
    "        batch_current = tf.zeros([size, self.embedding_dim], tf.float32)\n",
    "\n",
    "        index: list[int] = []\n",
    "        current_node: list[int] = []\n",
    "        children: list[list[int]] = []\n",
    "        children_index: list[list[int]] = []\n",
    "\n",
    "        for i, n in enumerate(nodes):\n",
    "            index.append(i)\n",
    "            current_node.append(n[0])\n",
    "\n",
    "            for j, child in enumerate(n[1:]):\n",
    "                # check if the children actually has a valid token index\n",
    "                if child[0] == -1:\n",
    "                    continue\n",
    "                # line 14: group children by their position\n",
    "                if len(children_index) <= j:\n",
    "                    children_index.append([i])\n",
    "                    children.append([child])\n",
    "                else:\n",
    "                    children_index[j].append(i)\n",
    "                    children[j].append(child)\n",
    "\n",
    "        index = tf.expand_dims(index, axis=-1)\n",
    "\n",
    "        batch_current = self._recurse(batch_current, batch_index, children, children_index, current_node, index, size, )\n",
    "        self._update_node_list(batch_current, batch_index)\n",
    "\n",
    "        return batch_current"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "c6a3a8ff",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class BatchTreeEncoder(BatchTreeEncoder):\n",
    "    def _recurse(self, batch_current, batch_index, children, children_index, current_node, index, size, ):\n",
    "        # line 10: Equation 1\n",
    "        batch_current = self.W_c(\n",
    "            tf.tensor_scatter_nd_update(batch_current, index, self.embedding(tf.Variable(current_node)))\n",
    "        )\n",
    "\n",
    "        # line 17\n",
    "        for c_idx, child in enumerate(children):\n",
    "            # line 18: `\\tilde{h}`\n",
    "            zeros = tf.zeros([size, self.encode_dim], tf.float32)\n",
    "            batch_children_index = [batch_index[i] for i in children_index[c_idx]]\n",
    "\n",
    "            # line 19: n\n",
    "            # make a recursive call for each child to get the output of shape\n",
    "            # (1 x self.encode_dim)\n",
    "            tree = self.traverse(child, batch_children_index)\n",
    "            if tree is None:\n",
    "                continue\n",
    "\n",
    "            children_index_instance = tf.expand_dims(children_index[c_idx], axis=-1)\n",
    "            indices = tf.Variable(children_index_instance, tf.float32)\n",
    "            batch_current += tf.tensor_scatter_nd_update(zeros, indices, tree)\n",
    "\n",
    "        return batch_current"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "4c7e75f1",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class BatchTreeEncoder(BatchTreeEncoder):\n",
    "    def _update_node_list(self, batch_current, batch_index):\n",
    "        b_in = tf.Variable(batch_index)\n",
    "        b_in = tf.expand_dims(b_in, axis=-1)\n",
    "        self.node_list.append(tf.tensor_scatter_nd_update(self.batch_node, b_in, batch_current))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "db495199",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class BatchTreeEncoder(BatchTreeEncoder):\n",
    "    def __call__(self, inputs, batch_size):\n",
    "        self.batch_size = batch_size\n",
    "        self.node_list = []\n",
    "        self.batch_node = tf.zeros((self.batch_size, self.encode_dim), tf.float32)\n",
    "        self.traverse(inputs, list(range(self.batch_size)))\n",
    "        self.node_list = tf.stack(self.node_list)\n",
    "        return tf.reduce_max(self.node_list, axis=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "37f92a49",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Code clone detection with code embeddings"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21a9ea56",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "As described initially in this section, code clone detection can be implemented by calculating the vector embeddings for two code snippets $r_1$ and $r_2$, then measuring their distance $r = |r_1 - r_2$. A model is then trained for $\\hat{x} = W_o r + b_o$ with output $\\hat{y} = sigmoid(\\hat{x}) \\in [0, 1]$ such that the binary cross-entropy for a labelled dataset of code clones is minimized. The following code implements the model as described in the ASTNN paper."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "4e21a5fc",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from keras.layers import Lambda\n",
    "import tensorflow as tf\n",
    "from typing import Optional\n",
    "import numpy.typing\n",
    "\n",
    "\n",
    "class AstnnCloneDetection(tf.keras.Model):\n",
    "    def __init__(self, vocab_embedding_dim: int, hidden_dim: int, vocab_size: int, encode_dim: int, label_count: int, batch_size: int = 64, pretrained_weight: Optional[numpy.typing.NDArray] = None):\n",
    "        super().__init__()\n",
    "        self.hidden_dim = hidden_dim\n",
    "        self.batch_size = batch_size\n",
    "        self.embedding_dim = vocab_embedding_dim\n",
    "        self.encode_dim = encode_dim\n",
    "        self.label_count = label_count\n",
    "        self.encoder = BatchTreeEncoder(\n",
    "            vocab_size,\n",
    "            self.embedding_dim,\n",
    "            self.encode_dim,\n",
    "            self.batch_size,\n",
    "            pretrained_weight,\n",
    "        )\n",
    "        self.bigru = keras.layers.Bidirectional(keras.layers.GRU(self.hidden_dim, return_sequences=True))\n",
    "        self.hidden_state: list[tf.Tensor] = []\n",
    "\n",
    "        self.l1_layer = Lambda(lambda tensors: tf.abs(tensors[0] - tensors[1]))\n",
    "        self.output_layer = keras.layers.Dense(self.label_count, input_shape=(self.hidden_dim * 2,), activation=keras.activations.sigmoid)\n",
    "\n",
    "        self._reset_RNN_hidden_state()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "e78aded0",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class AstnnCloneDetection(AstnnCloneDetection):\n",
    "    def _reset_RNN_hidden_state(self) -> None:\n",
    "        self.hidden_state = [tf.zeros([self.batch_size, self.hidden_dim]) for _ in range(2)]\n",
    "\n",
    "    def _setup_for_next_batch(self, batch_size: int) -> None:\n",
    "        self.batch_size = batch_size\n",
    "        self._reset_RNN_hidden_state()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a4d451d9",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Representation of a Statement Sequence\n",
    "\n",
    "- $T$ statements of a code snippet given in $x$\n",
    "- each statement is encoded using the `BatchTreeEncoder` and placed on the `result_stack`\n",
    "- Gated Recurrent Unit (GRU) in both directions over encoded statements $e_i$ to learn about relation to statements before and after in the code\n",
    "\n",
    "    - $\\overrightarrow{h_t} = \\overrightarrow{\\text{GRU}}(e_t)$\n",
    "    - $\\overleftarrow{h_t} = \\overleftarrow{\\text{GRU}}(e_t)$\n",
    "    - $h_t := \\overleftarrow{h_t}, \\overrightarrow{h_t}$\n",
    "\n",
    "- reduce vectors to most important features by max pooling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "cbc04b19",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class AstnnCloneDetection(AstnnCloneDetection):\n",
    "    def encode(self, x: tf.Tensor):\n",
    "        lengths = [len(item) for item in x]\n",
    "\n",
    "        # statement trees to encode\n",
    "        encodes = [statement_tree for code in x for statement_tree in code]\n",
    "\n",
    "        # line 4: pass the statement trees to the batch tree encoder\n",
    "        encoded = self.encoder(encodes, sum(lengths))\n",
    "        # line 24: collect onto S\n",
    "        result_stack = self._collect_stack(lengths, encoded)\n",
    "\n",
    "        # line 5: get BV\n",
    "        gru_out = self.bigru(result_stack, self.hidden_state)\n",
    "        gru_out = tf.transpose(gru_out, perm=[0, 2, 1])\n",
    "        gru_out = tf.reduce_max(gru_out, axis=[2], keepdims=True)\n",
    "        gru_out = tf.squeeze(gru_out, 2)\n",
    "\n",
    "        return gru_out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "5a74aca1",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class AstnnCloneDetection(AstnnCloneDetection):\n",
    "    def _collect_stack(self, lengths: list[int], encoded: tf.Tensor) -> tf.Tensor:\n",
    "        max_length = max(lengths)\n",
    "        result_stack_tmp: list[tf.Tensor] = []\n",
    "        start: int = 0\n",
    "        end: int = 0\n",
    "        for length in lengths:\n",
    "            end += length\n",
    "            if max_length - length:\n",
    "                filler = tf.zeros((max_length - length, self.encode_dim))\n",
    "                result_stack_tmp.append(filler)\n",
    "            result_stack_tmp.append(encoded[start:end])\n",
    "            start = end\n",
    "\n",
    "        # reshape the stack S to be usable as input for the GRU\n",
    "        result_stack = tf.concat(result_stack_tmp, axis=0)\n",
    "        return tf.reshape(result_stack, [self.batch_size, max_length, -1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "d206bf41",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "class AstnnCloneDetection(AstnnCloneDetection):\n",
    "    def call(self, inputs, training=None, mask=None, **kwargs):\n",
    "        code1, code2 = inputs\n",
    "        self._setup_for_next_batch(batch_size=1)\n",
    "        vec1, vec2 = self.encode(code1), self.encode(code2)\n",
    "        return self.output_layer(self.l1_layer([vec1, vec2]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6fd6231c",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Making a Prediction"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92ffac7c",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "To see the model in action, of course we need to train it on a large dataset. A labelled dataset of code clones is available  in the [BigCloneBench](https://github.com/clonebench/BigCloneBench) dataset. ASTNN was trained on this dataset, and we will simply load the vocabulary and model trained by the authors of ASTNN."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "id": "7e679ab7",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from gensim.models import Word2Vec\n",
    "\n",
    "w2v = Word2Vec.load(\"data/astnn/w2v_128\")\n",
    "\n",
    "def load_model() -> AstnnCloneDetection:\n",
    "    vocab_size = len(w2v.wv.vectors) + 1\n",
    "    w2v_embeddings = numpy.zeros((vocab_size, w2v.vector_size), dtype=float)\n",
    "    w2v_embeddings[: w2v.wv.vectors.shape[0]] = w2v.wv.vectors\n",
    "    model = AstnnCloneDetection(vocab_embedding_dim=128, hidden_dim=100, vocab_size=vocab_size, encode_dim=128, label_count=1, batch_size=1, pretrained_weight=w2v_embeddings)\n",
    "    dummy = [[[33, [2, [30, [40, [4]]]]]]]\n",
    "    x = model((dummy, dummy)) # Tensorflow lazy init: force initialisation using dummy data\n",
    "    model.load_weights(\"./data/astnn/weights/weights\")\n",
    "    return model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "801b83e9",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "2022-05-11 14:09:41.310982: I tensorflow/core/platform/cpu_feature_guard.cc:151] This TensorFlow binary is optimized with oneAPI Deep Neural Network Library (oneDNN) to use the following CPU instructions in performance-critical operations:  AVX2 FMA\n",
      "To enable them in other operations, rebuild TensorFlow with the appropriate compiler flags.\n"
     ]
    }
   ],
   "source": [
    "model = load_model()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ffd52aed",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "With this model, we can use any new pair of C code snippets and query the predicted label (0 = no clones, 1 = clones)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "8b39b237",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def predict(model: AstnnCloneDetection, code1: str, code2: str) -> float:\n",
    "    code_parser = pycparser.c_parser.CParser()\n",
    "    c1 = code_parser.parse(code1)\n",
    "    c2 = code_parser.parse(code2)\n",
    "\n",
    "    code1, code2 = to_statement_trees(c1), to_statement_trees(c2)\n",
    "    output = model(([code1], [code2]))\n",
    "    return output[-1][-1].numpy()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "697b3369",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Let's define some usual example code snippets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "0efc0e08",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "code1 = \"\"\"\n",
    "int foo(int x) {\n",
    "  if (x > 0) {\n",
    "      printf(\"Hallo\");\n",
    "  } else {\n",
    "      printf(\"Nicht hallo\");  \n",
    "  }\n",
    "  return 0;\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "cd1e841c",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code2 = \"\"\"\n",
    "int bar(int x) {\n",
    "  if (x > 0) {\n",
    "      printf(\"Hallo\");\n",
    "  } else {\n",
    "      printf(\"Nicht hallo\");  \n",
    "  }\n",
    "  return 0;\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "id": "d746d5c7",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "code3 = \"\"\"\n",
    "int bar(int x) {\n",
    "  printf(\"Not a clone\");\n",
    "  return 0;\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53804dac",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "For example, the first and second code snippet are identical except for the function name, so we would expect it to be detected as a clone pair:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "id": "7e54eee7",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.7764541"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "predict(model, code1, code2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "233f34e7",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In contrast, the first and third snippet represent entirely different code and should thus not be detected as a clone pair."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "id": "207c9a31",
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.23175177"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "predict(model, code1, code3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4247656",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The prediction is turned into a label by using a threshold $\\delta$, such that the two code snippets are a clone pair if the prediction $p > \\delta$. For example, the ASTNN experiments set $\\delta = 0.5$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b3219d13",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}