diff --git a/llvm/utils/TableGen/jupyter/sql_query_backend.ipynb b/llvm/utils/TableGen/jupyter/sql_query_backend.ipynb new file mode 100644 --- /dev/null +++ b/llvm/utils/TableGen/jupyter/sql_query_backend.ipynb @@ -0,0 +1,1102 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "id": "30b1e660", + "metadata": {}, + "source": [ + "# Writing a TableGen Backend in Python" + ] + }, + { + "cell_type": "markdown", + "id": "1f9e9c7f", + "metadata": {}, + "source": [ + "This tutorial is going to walk through creating a TableGen backend using Python.\n", + "\n", + "We are using Python to better fit into a notebook, but backends in LLVM are written in C++. The principles you learn here will still apply and you could port this tutorial to any language that has a JSON parser.\n", + "\n", + "This is the process in LLVM, using a C++ backend:\n", + "```\n", + "TableGen source -> llvm-tblgen -> backend (within llvm-tblgen) -> results\n", + "```\n", + "This is what we will be doing:\n", + "```\n", + "TableGen source -> llvm-tblgen -> JSON -> Python -> results\n", + "```\n", + "\n", + "The backend here is ported from one of several in \"SQLGen\" which was written by Min-Yih Hsu.\n", + "* SQLGen C++ sources - https://github.com/mshockwave/SQLGen\n", + "* LLVM dev presentation - https://www.youtube.com/watch?v=UP-LBRbvI_U\n", + "\n", + "I encourage you to use those resources to supplement this notebook." + ] + }, + { + "cell_type": "markdown", + "id": "3e7fe59c", + "metadata": {}, + "source": [ + "## Compiling TableGen" + ] + }, + { + "cell_type": "markdown", + "id": "691301ba", + "metadata": {}, + "source": [ + "Unlike the other tutorial notebooks we are not using the TableGen kernel. This is an iPython notebook and we're going to run `llvm-tblgen` as a subprocess.\n", + "\n", + "First let's find it, in the same way the TableGen kernel does." + ] + }, + { + "cell_type": "code", + "execution_count": 1, + "id": "d3f6d617", + "metadata": {}, + "outputs": [], + "source": [ + "import os\n", + "import shutil\n", + "\n", + "def find_tblgen():\n", + " path = os.environ.get(\"LLVM_TBLGEN_EXECUTABLE\")\n", + " if path is not None and os.path.isfile(path) and os.access(path, os.X_OK):\n", + " return path\n", + " else:\n", + " path = shutil.which(\"llvm-tblgen\")\n", + " if path is None:\n", + " raise OSError(\"llvm-tblgen not found\")\n", + " return path\n", + " \n", + "_ = find_tblgen()" + ] + }, + { + "cell_type": "markdown", + "id": "6663f383", + "metadata": {}, + "source": [ + "Then we need to compile some TableGen by passing it to `llvm-tblgen`'s stdin. We will be using the option `--dump-json` and returning the JSON as a Python dictionary if the compilation succeeds. If it fails, we raise an exception." + ] + }, + { + "cell_type": "code", + "execution_count": 22, + "id": "16ad161b", + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "{\n", + " \"!instanceof\": {\n", + " \"Foo\": []\n", + " },\n", + " \"!tablegen_json_version\": 1\n", + "}\n" + ] + } + ], + "source": [ + "import subprocess\n", + "import tempfile\n", + "import json\n", + "\n", + "def run_tblgen(src):\n", + " # Passing to stdin requires a file like object.\n", + " with tempfile.TemporaryFile(\"w+\") as f:\n", + " f.write(src)\n", + " f.seek(0)\n", + " got = subprocess.run(\n", + " [find_tblgen(), \"--dump-json\"],\n", + " stdin=f,\n", + " stderr=subprocess.PIPE,\n", + " stdout=subprocess.PIPE,\n", + " universal_newlines=True,\n", + " )\n", + " \n", + " if got.stderr:\n", + " raise RuntimeError(\"llvm-tblgen failed with stderr: \" + got.stderr)\n", + " \n", + " return json.loads(got.stdout)\n", + " \n", + "print(json.dumps(run_tblgen(\"class Foo {}\"), indent=4))" + ] + }, + { + "cell_type": "markdown", + "id": "1cf554d2", + "metadata": {}, + "source": [ + "## Structure of a SQL Query" + ] + }, + { + "cell_type": "markdown", + "id": "eeefca57", + "metadata": {}, + "source": [ + "This backend is going to generate SQL queries. The general form of a SQL query is:\n", + "```\n", + "SELECT FROM \n", + " WHERE \n", + " ORDER BY ;\n", + "```" + ] + }, + { + "cell_type": "markdown", + "id": "71760a38", + "metadata": {}, + "source": [ + "## SQL Query TableGen" + ] + }, + { + "cell_type": "code", + "execution_count": 23, + "id": "2d84b0c8", + "metadata": {}, + "outputs": [], + "source": [ + "query_tblgen = \"\"\"\\\n", + "def all;\n", + "def fields;\n", + "def none;\n", + "\n", + "def eq;\n", + "def ne;\n", + "def gt;\n", + "def ge;\n", + "def and;\n", + "def or;\n", + "\"\"\"" + ] + }, + { + "cell_type": "markdown", + "id": "acfa7e4c", + "metadata": {}, + "source": [ + "Normally you'd write this to a `.td` file but here we have it in a Python string to fit into this notebook. We will add to this string to produce the final source.\n", + "\n", + "This section defines some constants. First are the fields we want to get back from the query:\n", + "* `all` - Return all fields.\n", + "* `fields` - We will provide a list of fields we are interested in.\n", + "\n", + "The second are the logical operators for what will become the `WHERE` clause (called `condition` in the TableGen). These are string versions of various symbols. For example `ne` means `!=`, which in SQL is `<>`.\n", + "\n", + "Finally `none` is used to mean there is no condition to the query (no `WHERE`)." + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "id": "45c00d5e", + "metadata": {}, + "outputs": [], + "source": [ + "query_tblgen += \"\"\"\\\n", + "class Query {\n", + " string TableName = table;\n", + " dag Fields = query_fields;\n", + " dag WhereClause = condition;\n", + " list OrderedBy = [];\n", + "}\n", + "\"\"\"" + ] + }, + { + "cell_type": "markdown", + "id": "3ae4def4", + "metadata": {}, + "source": [ + "Then the Query class. Its arguments are:\n", + "* `table` - The name of the table to query (`FROM
`).\n", + "* `query_fields` - The fields you want returned (`SELECT `).\n", + " * Defaults to `all` meaning return all fields.\n", + "* `condition` - Logic to select entries (`WHERE `).\n", + " * Defaults to `none` meaning there is no condition, or in other words select all entries in the table." + ] + }, + { + "cell_type": "markdown", + "id": "1af40e14", + "metadata": {}, + "source": [ + "## Using The Query Class" + ] + }, + { + "cell_type": "code", + "execution_count": 6, + "id": "9b6ecead", + "metadata": {}, + "outputs": [], + "source": [ + "full_tblgen = query_tblgen + \"\"\"\\\n", + "def : Query<\"Customer\">;\n", + "\n", + "def : Query<\"Orders\", (fields \"Person\", \"Amount\")>;\n", + "\n", + "def : Query<\"Customer\", (fields \"Affiliation\"),\n", + " (eq \"Name\", \"Mary Blackburn\":$str)>;\n", + "\n", + "def : Query<\"Orders\", (fields \"ProductName\"),\n", + " (gt \"Amount\", 8)>;\n", + "\n", + "def : Query<\"Orders\", (fields \"ProductName\":$name, \"Person\"),\n", + " (and (gt \"Amount\", 8), (ne \"Person\", 1))> {\n", + " let OrderedBy = [\"$name\"];\n", + "}\n", + "\"\"\"" + ] + }, + { + "cell_type": "markdown", + "id": "13a17bb9", + "metadata": {}, + "source": [ + "Now we can define some queries. Let's go go over the last one in detail.\n", + "\n", + "```\n", + "def : Query<\"Orders\", (fields \"ProductName\":$name, \"Person\"),\n", + " (and (gt \"Amount\", 8), (ne \"Person\", 1))> {\n", + " let OrderedBy = [\"$name\"];\n", + "}\n", + "```\n", + "\n", + "* It will run on a table called `Orders`.\n", + "* We want to see the fields `ProductName` and `Person`.\n", + "* We have tagged `ProductName` with `$name`.\n", + "* The condition is that `Amount` must be greater than `8` and\n", + " `Person` must not be equal to `1`.\n", + "* The results of this query should be ordered by the field\n", + " tagged `$name`, which is `ProductName`.\n", + " \n", + "The condition being of DAG type (Directed Acyclic Graph) allows us to describe nested conditions. You might write this condition in Python as:\n", + "```\n", + "if (Amount > 8) and (Person != 1):\n", + "```\n", + "Putting that into a graph form:\n", + "```\n", + " |------|and|------|\n", + " | |\n", + "| Amount > 8 | | Person != 1 |\n", + "```\n", + "Which is what we're describing with the DAG in TableGen." + ] + }, + { + "cell_type": "markdown", + "id": "9fdb5130", + "metadata": {}, + "source": [ + "## The JSON format" + ] + }, + { + "cell_type": "code", + "execution_count": 24, + "id": "4a57b3f0", + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "{\n", + " \"!instanceof\": {\n", + " \"Query\": [\n", + " \"anonymous_0\",\n", + " \"anonymous_1\",\n", + " \"anonymous_2\",\n", + " \"anonymous_3\",\n", + " \"anonymous_4\"\n", + " ]\n", + " },\n", + " \"!tablegen_json_version\": 1,\n", + " \"all\": {\n", + " \"!anonymous\": false,\n", + " \"!fields\": [],\n", + " \"!name\": \"all\",\n", + " \"!superclasses\": []\n", + " },\n", + " \"and\": {\n", + " \"!anonymous\": false,\n", + " \"!fields\": [],\n", + " \"!name\": \"and\",\n", + " \"!superclasses\": []\n", + " },\n", + " \"anonymous_0\": {\n", + " \"!anonymous\": true,\n", + " \"!fields\": [],\n", + " \"!name\": \"anonymous_0\",\n", + " \"!superclasses\": [\n", + " \"Query\"\n", + " ],\n", + " \"Fields\": {\n", + " \"args\": [],\n", + " \"kind\": \"dag\",\n", + " \"operator\": {\n", + " \"def\": \"all\",\n", + " \"kind\": \"def\",\n", + " \"printable\": \"all\"\n", + " },\n", + " \"printable\": \"(all)\"\n", + " },\n", + " \"OrderedBy\": [],\n", + " \"TableName\": \"Customer\",\n", + " \"WhereClause\": {\n", + " \"args\": [],\n", + " \"kind\": \"dag\",\n", + " \"operator\": {\n", + " \"def\": \"none\",\n", + " \"kind\": \"def\",\n", + " \"printable\": \"none\"\n", + " },\n", + " \"printable\": \"(none)\"\n", + " }\n", + " },\n", + " \"anonymous_1\": {\n", + " \"!anonymous\": true,\n", + " \"!fields\": [],\n", + " \"!name\": \"anonymous_1\",\n", + " \"!superclasses\": [\n", + " \"Query\"\n", + " ],\n", + " \"Fields\": {\n", + " \"args\": [\n", + " [\n", + " \"Person\",\n", + " null\n", + " ],\n", + " [\n", + " \"Amount\",\n", + " null\n", + " ]\n", + " ],\n", + " \"kind\": \"dag\",\n", + " \"operator\": {\n", + " \"def\": \"fields\",\n", + " \"kind\": \"def\",\n", + " \"printable\": \"fields\"\n", + " },\n", + " \"printable\": \"(fields \\\"Person\\\", \\\"Amount\\\")\"\n", + " },\n", + " \"OrderedBy\": [],\n", + " \"TableName\": \"Orders\",\n", + " \"WhereClause\": {\n", + " \"args\": [],\n", + " \"kind\": \"dag\",\n", + " \"operator\": {\n", + " \"def\": \"none\",\n", + " \"kind\": \"def\",\n", + " \"printable\": \"none\"\n", + " },\n", + " \"printable\": \"(none)\"\n", + " }\n", + " },\n", + " \"anonymous_2\": {\n", + " \"!anonymous\": true,\n", + " \"!fields\": [],\n", + " \"!name\": \"anonymous_2\",\n", + " \"!superclasses\": [\n", + " \"Query\"\n", + " ],\n", + " \"Fields\": {\n", + " \"args\": [\n", + " [\n", + " \"Affiliation\",\n", + " null\n", + " ]\n", + " ],\n", + " \"kind\": \"dag\",\n", + " \"operator\": {\n", + " \"def\": \"fields\",\n", + " \"kind\": \"def\",\n", + " \"printable\": \"fields\"\n", + " },\n", + " \"printable\": \"(fields \\\"Affiliation\\\")\"\n", + " },\n", + " \"OrderedBy\": [],\n", + " \"TableName\": \"Customer\",\n", + " \"WhereClause\": {\n", + " \"args\": [\n", + " [\n", + " \"Name\",\n", + " null\n", + " ],\n", + " [\n", + " \"Mary Blackburn\",\n", + " \"str\"\n", + " ]\n", + " ],\n", + " \"kind\": \"dag\",\n", + " \"operator\": {\n", + " \"def\": \"eq\",\n", + " \"kind\": \"def\",\n", + " \"printable\": \"eq\"\n", + " },\n", + " \"printable\": \"(eq \\\"Name\\\", \\\"Mary Blackburn\\\":$str)\"\n", + " }\n", + " },\n", + " \"anonymous_3\": {\n", + " \"!anonymous\": true,\n", + " \"!fields\": [],\n", + " \"!name\": \"anonymous_3\",\n", + " \"!superclasses\": [\n", + " \"Query\"\n", + " ],\n", + " \"Fields\": {\n", + " \"args\": [\n", + " [\n", + " \"ProductName\",\n", + " null\n", + " ]\n", + " ],\n", + " \"kind\": \"dag\",\n", + " \"operator\": {\n", + " \"def\": \"fields\",\n", + " \"kind\": \"def\",\n", + " \"printable\": \"fields\"\n", + " },\n", + " \"printable\": \"(fields \\\"ProductName\\\")\"\n", + " },\n", + " \"OrderedBy\": [],\n", + " \"TableName\": \"Orders\",\n", + " \"WhereClause\": {\n", + " \"args\": [\n", + " [\n", + " \"Amount\",\n", + " null\n", + " ],\n", + " [\n", + " 8,\n", + " null\n", + " ]\n", + " ],\n", + " \"kind\": \"dag\",\n", + " \"operator\": {\n", + " \"def\": \"gt\",\n", + " \"kind\": \"def\",\n", + " \"printable\": \"gt\"\n", + " },\n", + " \"printable\": \"(gt \\\"Amount\\\", 8)\"\n", + " }\n", + " },\n", + " \"anonymous_4\": {\n", + " \"!anonymous\": true,\n", + " \"!fields\": [],\n", + " \"!name\": \"anonymous_4\",\n", + " \"!superclasses\": [\n", + " \"Query\"\n", + " ],\n", + " \"Fields\": {\n", + " \"args\": [\n", + " [\n", + " \"ProductName\",\n", + " \"name\"\n", + " ],\n", + " [\n", + " \"Person\",\n", + " null\n", + " ]\n", + " ],\n", + " \"kind\": \"dag\",\n", + " \"operator\": {\n", + " \"def\": \"fields\",\n", + " \"kind\": \"def\",\n", + " \"printable\": \"fields\"\n", + " },\n", + " \"printable\": \"(fields \\\"ProductName\\\":$name, \\\"Person\\\")\"\n", + " },\n", + " \"OrderedBy\": [\n", + " \"$name\"\n", + " ],\n", + " \"TableName\": \"Orders\",\n", + " \"WhereClause\": {\n", + " \"args\": [\n", + " [\n", + " {\n", + " \"args\": [\n", + " [\n", + " \"Amount\",\n", + " null\n", + " ],\n", + " [\n", + " 8,\n", + " null\n", + " ]\n", + " ],\n", + " \"kind\": \"dag\",\n", + " \"operator\": {\n", + " \"def\": \"gt\",\n", + " \"kind\": \"def\",\n", + " \"printable\": \"gt\"\n", + " },\n", + " \"printable\": \"(gt \\\"Amount\\\", 8)\"\n", + " },\n", + " null\n", + " ],\n", + " [\n", + " {\n", + " \"args\": [\n", + " [\n", + " \"Person\",\n", + " null\n", + " ],\n", + " [\n", + " 1,\n", + " null\n", + " ]\n", + " ],\n", + " \"kind\": \"dag\",\n", + " \"operator\": {\n", + " \"def\": \"ne\",\n", + " \"kind\": \"def\",\n", + " \"printable\": \"ne\"\n", + " },\n", + " \"printable\": \"(ne \\\"Person\\\", 1)\"\n", + " },\n", + " null\n", + " ]\n", + " ],\n", + " \"kind\": \"dag\",\n", + " \"operator\": {\n", + " \"def\": \"and\",\n", + " \"kind\": \"def\",\n", + " \"printable\": \"and\"\n", + " },\n", + " \"printable\": \"(and (gt \\\"Amount\\\", 8), (ne \\\"Person\\\", 1))\"\n", + " }\n", + " },\n", + " \"eq\": {\n", + " \"!anonymous\": false,\n", + " \"!fields\": [],\n", + " \"!name\": \"eq\",\n", + " \"!superclasses\": []\n", + " },\n", + " \"fields\": {\n", + " \"!anonymous\": false,\n", + " \"!fields\": [],\n", + " \"!name\": \"fields\",\n", + " \"!superclasses\": []\n", + " },\n", + " \"ge\": {\n", + " \"!anonymous\": false,\n", + " \"!fields\": [],\n", + " \"!name\": \"ge\",\n", + " \"!superclasses\": []\n", + " },\n", + " \"gt\": {\n", + " \"!anonymous\": false,\n", + " \"!fields\": [],\n", + " \"!name\": \"gt\",\n", + " \"!superclasses\": []\n", + " },\n", + " \"ne\": {\n", + " \"!anonymous\": false,\n", + " \"!fields\": [],\n", + " \"!name\": \"ne\",\n", + " \"!superclasses\": []\n", + " },\n", + " \"none\": {\n", + " \"!anonymous\": false,\n", + " \"!fields\": [],\n", + " \"!name\": \"none\",\n", + " \"!superclasses\": []\n", + " },\n", + " \"or\": {\n", + " \"!anonymous\": false,\n", + " \"!fields\": [],\n", + " \"!name\": \"or\",\n", + " \"!superclasses\": []\n", + " }\n", + "}\n" + ] + } + ], + "source": [ + "full_json = run_tblgen(full_tblgen)\n", + "print(json.dumps(full_json, indent=4))" + ] + }, + { + "cell_type": "markdown", + "id": "32b24328", + "metadata": {}, + "source": [ + "The backend is going to walk the JSON we decoded. You can see the full output above in case you want to browse but for now don't read the whole thing. We will highlight the key aspects of it as we go along." + ] + }, + { + "cell_type": "code", + "execution_count": 25, + "id": "f2c0966e", + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "{'Query': ['anonymous_0', 'anonymous_1', 'anonymous_2', 'anonymous_3', 'anonymous_4']}\n" + ] + } + ], + "source": [ + "print(full_json[\"!instanceof\"])" + ] + }, + { + "cell_type": "markdown", + "id": "ff9c1374", + "metadata": {}, + "source": [ + "Any key beginning with `!` is some sort of metadata about the other keys. Here this is a list of all instances of certain classes. We just have `Query` which lists all the queries we defined." + ] + }, + { + "cell_type": "code", + "execution_count": 26, + "id": "806e9602", + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "['Query']\n" + ] + } + ], + "source": [ + "print(full_json[\"anonymous_0\"][\"!superclasses\"])" + ] + }, + { + "cell_type": "markdown", + "id": "a7a8e50c", + "metadata": {}, + "source": [ + "On each def there is also a `!superclasses` that gives you the same information. Meaning you could use `!instanceof` to get a list of keys to lookup, or you could walk all keys and check `!superclasses`." + ] + }, + { + "cell_type": "code", + "execution_count": 27, + "id": "9073578b", + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "{'args': [], 'kind': 'dag', 'operator': {'def': 'all', 'kind': 'def', 'printable': 'all'}, 'printable': '(all)'}\n" + ] + } + ], + "source": [ + "print(full_json[\"anonymous_0\"][\"Fields\"])" + ] + }, + { + "cell_type": "markdown", + "id": "994eb9e0", + "metadata": {}, + "source": [ + "From a def object you can find its attributes. Here we have the fields we want the query to show, which is all of them." + ] + }, + { + "cell_type": "markdown", + "id": "f12f52e3", + "metadata": {}, + "source": [ + "# The Backend" + ] + }, + { + "cell_type": "markdown", + "id": "023227c0", + "metadata": {}, + "source": [ + "The core of a backend is looping over all defs of a certain class and outputting some text based on their properties.\n", + "\n", + "Here we're going to loop over all defs of type `Query` and emit SQL queries for them." + ] + }, + { + "cell_type": "code", + "execution_count": 28, + "id": "f2cfda7e", + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "['anonymous_0', 'anonymous_1', 'anonymous_2', 'anonymous_3', 'anonymous_4']\n" + ] + } + ], + "source": [ + "def find_all_queries(j):\n", + " queries = []\n", + " for key in j:\n", + " # ! means it is some metadata, not a def.\n", + " if not key.startswith(\"!\"):\n", + " value = full_json[key]\n", + " # If we inherit from Query.\n", + " if \"Query\" in value[\"!superclasses\"]:\n", + " queries.append(value)\n", + " return queries\n", + "\n", + "queries = find_all_queries(full_json)\n", + " \n", + "print([q[\"!name\"] for q in queries])" + ] + }, + { + "cell_type": "markdown", + "id": "e9c82793", + "metadata": {}, + "source": [ + "Why are the names `anonymous_...`? When we defined them we did `def :` and missed out the name. This is allowed and `llvm-tblgen` just came up with a name for us. For this purpose the names are irrelevant.\n", + "\n", + "Now we have the relevant classes we need to \"emit\" them. Meaning produce something from them, in this case a SQL query." + ] + }, + { + "cell_type": "code", + "execution_count": 29, + "id": "f1b795f9", + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + " AND \n" + ] + } + ], + "source": [ + "def emit_operator(operator):\n", + " return {\n", + " 'gt': ' > ',\n", + " 'ge': ' >= ',\n", + " 'lt': ' < ',\n", + " 'le': ' <= ',\n", + " 'ne': ' <> ',\n", + " 'eq': ' = ',\n", + " 'or': ' OR ',\n", + " 'and': ' AND '\n", + " }[operator]\n", + "\n", + "print(emit_operator('and'))" + ] + }, + { + "cell_type": "markdown", + "id": "2fd3a96f", + "metadata": {}, + "source": [ + "The maps our TableGen constants to the equivalent SQL logical operation." + ] + }, + { + "cell_type": "code", + "execution_count": 30, + "id": "a6fa0c43", + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "Abc, Def\n" + ] + } + ], + "source": [ + "def emit_fields(args):\n", + " # Return a comma separated list of arg names.\n", + " return \", \".join([arg[0] for arg in args])\n", + "\n", + "print(emit_fields([[\"Abc\", None], [\"Def\", None]]))" + ] + }, + { + "cell_type": "markdown", + "id": "43127766", + "metadata": {}, + "source": [ + "This emits the the fields we are selecting. Each field has a name (`arg[0]`) and an optional tag that we will use later." + ] + }, + { + "cell_type": "code", + "execution_count": 31, + "id": "4aa39163", + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "Name = \"Mary Blackburn\"\n" + ] + } + ], + "source": [ + "from collections.abc import Mapping\n", + "\n", + "def emit_where_clause(where_clause):\n", + " output = \"\"\n", + " num_args = len(where_clause[\"args\"])\n", + " \n", + " for idx, arg in enumerate(where_clause[\"args\"]):\n", + " arg_name, arg_type = arg\n", + "\n", + " if isinstance(arg_name, Mapping):\n", + " # This is a nested where clause.\n", + " output += emit_where_clause(arg_name)\n", + " else:\n", + " # This is some condition.\n", + " if arg_type == \"str\":\n", + " # String types must be emitted with \"\" around them.\n", + " output += '\"' + arg_name + '\"'\n", + " else:\n", + " output += str(arg_name)\n", + "\n", + " # If this is not the last arg, emit the condition.\n", + " if idx != (num_args-1):\n", + " output += emit_operator(where_clause[\"operator\"][\"def\"])\n", + " \n", + " return output\n", + "\n", + "print(emit_where_clause({\n", + "\"args\": [[\"Name\",None], \n", + " [\"Mary Blackburn\", \"str\"]],\n", + "\"kind\": \"dag\",\n", + "\"operator\": {\n", + " \"def\": \"eq\",\n", + " \"kind\": \"def\",\n", + " \"printable\": \"eq\"\n", + "}}))" + ] + }, + { + "cell_type": "markdown", + "id": "f8e6a7fe", + "metadata": {}, + "source": [ + "This emits the condition that goes with the `WHERE`. The condition is a DAG, which means that we will find a possible mix of conditions and other DAGS. We recurse to handle the latter case.\n", + "\n", + "For each part of the condition we print the name of the thing you're checking, then the condition (`=`, `<>`, etc.). The value to check against is last and that goes on the end." + ] + }, + { + "cell_type": "code", + "execution_count": 32, + "id": "92eee280", + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\n", + " ORDER BY ABC, DEF\n" + ] + } + ], + "source": [ + "def emit_ordered_by(ordered_by, field_tag_map):\n", + " # No ORDER BY statement to emit.\n", + " if not ordered_by:\n", + " return \"\"\n", + " \n", + " output = \"\\n ORDER BY \"\n", + " num_ordered_by = len(ordered_by)\n", + " \n", + " for idx, field_name in enumerate(ordered_by):\n", + " # If it is a tag\n", + " if field_name.startswith('$'):\n", + " # Find the corresponding field name\n", + " tag_name = field_name[1:]\n", + " field_name = field_tag_map.get(tag_name)\n", + " if field_name is None:\n", + " raise RuntimeError('Unrecognized tag \"{}\"'.format(\n", + " tag_name))\n", + "\n", + " # Separate each tag after the first with \", \".\n", + " if idx != 0:\n", + " output += \", \"\n", + " output += field_name\n", + " \n", + " return output\n", + "\n", + "print(emit_ordered_by([\"$abc\", \"$def\"], {'abc':\"ABC\", 'def':\"DEF\"}))" + ] + }, + { + "cell_type": "markdown", + "id": "8a918b51", + "metadata": {}, + "source": [ + "`emit_ordered_by` produces the `ORDER BY` text. If there is no ordering return nothing, otherwise loop over all the fields we want to order by and emit their names.\n", + "\n", + "We get those names by looking up the tag given in a map to get the real name. Here's how we build that map:" + ] + }, + { + "cell_type": "code", + "execution_count": 33, + "id": "16faaf30", + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "{'abc': 'ABC', 'def': 'DEF'}\n" + ] + } + ], + "source": [ + "def build_tag_map(arguments):\n", + " # Args are [Name, Tag]. Reverse this so we have [Tag, Name].\n", + " # Add each one to a dictionary where Tag is the key and Name is the value.\n", + " return dict([reversed(a) for a in arguments])\n", + "\n", + "print(build_tag_map([[\"ABC\", \"abc\"], [\"DEF\", \"def\"]]))" + ] + }, + { + "cell_type": "code", + "execution_count": 34, + "id": "dcf139f2", + "metadata": {}, + "outputs": [], + "source": [ + "def emit_query(q):\n", + " fields_init = q[\"Fields\"]\n", + " field_op_name = fields_init[\"operator\"][\"def\"]\n", + " if not field_op_name in [\"all\", \"fields\"]:\n", + " raise RuntimeError(\"Invalid dag operator \" + field_op_name)\n", + " \n", + " field_tag_map = build_tag_map(fields_init[\"args\"])\n", + " \n", + " where_clause = q[\"WhereClause\"]\n", + " has_where = where_clause[\"operator\"][\"def\"] != \"none\"\n", + " \n", + " ret = \"SELECT \"\n", + " if field_op_name == \"all\":\n", + " ret += \"*\"\n", + " ret += emit_fields(fields_init[\"args\"])\n", + " ret += \" FROM \" + q[\"TableName\"]\n", + " if has_where:\n", + " ret += \"\\n WHERE \" + emit_where_clause(where_clause)\n", + " ret += emit_ordered_by(q[\"OrderedBy\"], field_tag_map)\n", + " ret += \";\"\n", + " \n", + " return ret" + ] + }, + { + "cell_type": "markdown", + "id": "5acb7290", + "metadata": {}, + "source": [ + "Finally the main function. It emits the skeleton of the query and calls the helpers we defined earlier to fill in the gaps." + ] + }, + { + "cell_type": "markdown", + "id": "661a028b", + "metadata": {}, + "source": [ + "## The Result" + ] + }, + { + "cell_type": "code", + "execution_count": 35, + "id": "0f05368c", + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "SELECT * FROM Customer;\n", + "\n", + "SELECT Person, Amount FROM Orders;\n", + "\n", + "SELECT Affiliation FROM Customer\n", + " WHERE Name = \"Mary Blackburn\";\n", + "\n", + "SELECT ProductName FROM Orders\n", + " WHERE Amount > 8;\n", + "\n", + "SELECT ProductName, Person FROM Orders\n", + " WHERE Amount > 8 AND Person <> 1\n", + " ORDER BY ProductName;\n", + "\n" + ] + } + ], + "source": [ + "for q in queries:\n", + " print(emit_query(q) + \"\\n\")" + ] + }, + { + "cell_type": "markdown", + "id": "56a0f062", + "metadata": {}, + "source": [ + "Now we run `emit_query` and print out the results. There you have it, that's a TableGen backend!\n", + "\n", + "You've seen the core concepts. Loop over all the defs of a certain class and then emit some other structure based on the fields of each one. In this case it was SQL queries. In LLVM it's most often C++ code but it can be anything you want.\n", + "\n", + "If you want to see the same thing done with a C++ backend (meaning, one written in C++), check out the links at the start of this notebook." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "5a37c351", + "metadata": {}, + "outputs": [], + "source": [] + } + ], + "metadata": { + "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.8.10" + } + }, + "nbformat": 4, + "nbformat_minor": 5 +} diff --git a/llvm/utils/TableGen/jupyter/sql_query_backend.md b/llvm/utils/TableGen/jupyter/sql_query_backend.md new file mode 100644 --- /dev/null +++ b/llvm/utils/TableGen/jupyter/sql_query_backend.md @@ -0,0 +1,766 @@ +# Writing a TableGen Backend in Python + +This tutorial is going to walk through creating a TableGen backend using Python. + +We are using Python to better fit into a notebook, but backends in LLVM are written in C++. The principles you learn here will still apply and you could port this tutorial to any language that has a JSON parser. + +This is the process in LLVM, using a C++ backend: +``` +TableGen source -> llvm-tblgen -> backend (within llvm-tblgen) -> results +``` +This is what we will be doing: +``` +TableGen source -> llvm-tblgen -> JSON -> Python -> results +``` + +The backend here is ported from one of several in "SQLGen" which was written by Min-Yih Hsu. +* SQLGen C++ sources - https://github.com/mshockwave/SQLGen +* LLVM dev presentation - https://www.youtube.com/watch?v=UP-LBRbvI_U + +I encourage you to use those resources to supplement this notebook. + +## Compiling TableGen + +Unlike the other tutorial notebooks we are not using the TableGen kernel. This is an iPython notebook and we're going to run `llvm-tblgen` as a subprocess. + +First let's find it, in the same way the TableGen kernel does. + + +```python +import os +import shutil + +def find_tblgen(): + path = os.environ.get("LLVM_TBLGEN_EXECUTABLE") + if path is not None and os.path.isfile(path) and os.access(path, os.X_OK): + return path + else: + path = shutil.which("llvm-tblgen") + if path is None: + raise OSError("llvm-tblgen not found") + return path + +_ = find_tblgen() +``` + +Then we need to compile some TableGen by passing it to `llvm-tblgen`'s stdin. We will be using the option `--dump-json` and returning the JSON as a Python dictionary if the compilation succeeds. If it fails, we raise an exception. + + +```python +import subprocess +import tempfile +import json + +def run_tblgen(src): + # Passing to stdin requires a file like object. + with tempfile.TemporaryFile("w+") as f: + f.write(src) + f.seek(0) + got = subprocess.run( + [find_tblgen(), "--dump-json"], + stdin=f, + stderr=subprocess.PIPE, + stdout=subprocess.PIPE, + universal_newlines=True, + ) + + if got.stderr: + raise RuntimeError("llvm-tblgen failed with stderr: " + got.stderr) + + return json.loads(got.stdout) + +print(json.dumps(run_tblgen("class Foo {}"), indent=4)) +``` + + { + "!instanceof": { + "Foo": [] + }, + "!tablegen_json_version": 1 + } + + +## Structure of a SQL Query + +This backend is going to generate SQL queries. The general form of a SQL query is: +``` +SELECT FROM
+ WHERE + ORDER BY ; +``` + +## SQL Query TableGen + + +```python +query_tblgen = """\ +def all; +def fields; +def none; + +def eq; +def ne; +def gt; +def ge; +def and; +def or; +""" +``` + +Normally you'd write this to a `.td` file but here we have it in a Python string to fit into this notebook. We will add to this string to produce the final source. + +This section defines some constants. First are the fields we want to get back from the query: +* `all` - Return all fields. +* `fields` - We will provide a list of fields we are interested in. + +The second are the logical operators for what will become the `WHERE` clause (called `condition` in the TableGen). These are string versions of various symbols. For example `ne` means `!=`, which in SQL is `<>`. + +Finally `none` is used to mean there is no condition to the query (no `WHERE`). + + +```python +query_tblgen += """\ +class Query { + string TableName = table; + dag Fields = query_fields; + dag WhereClause = condition; + list OrderedBy = []; +} +""" +``` + +Then the Query class. Its arguments are: +* `table` - The name of the table to query (`FROM
`). +* `query_fields` - The fields you want returned (`SELECT `). + * Defaults to `all` meaning return all fields. +* `condition` - Logic to select entries (`WHERE `). + * Defaults to `none` meaning there is no condition, or in other words select all entries in the table. + +## Using The Query Class + + +```python +full_tblgen = query_tblgen + """\ +def : Query<"Customer">; + +def : Query<"Orders", (fields "Person", "Amount")>; + +def : Query<"Customer", (fields "Affiliation"), + (eq "Name", "Mary Blackburn":$str)>; + +def : Query<"Orders", (fields "ProductName"), + (gt "Amount", 8)>; + +def : Query<"Orders", (fields "ProductName":$name, "Person"), + (and (gt "Amount", 8), (ne "Person", 1))> { + let OrderedBy = ["$name"]; +} +""" +``` + +Now we can define some queries. Let's go go over the last one in detail. + +``` +def : Query<"Orders", (fields "ProductName":$name, "Person"), + (and (gt "Amount", 8), (ne "Person", 1))> { + let OrderedBy = ["$name"]; +} +``` + +* It will run on a table called `Orders`. +* We want to see the fields `ProductName` and `Person`. +* We have tagged `ProductName` with `$name`. +* The condition is that `Amount` must be greater than `8` and + `Person` must not be equal to `1`. +* The results of this query should be ordered by the field + tagged `$name`, which is `ProductName`. + +The condition being of DAG type (Directed Acyclic Graph) allows us to describe nested conditions. You might write this condition in Python as: +``` +if (Amount > 8) and (Person != 1): +``` +Putting that into a graph form: +``` + |------|and|------| + | | +| Amount > 8 | | Person != 1 | +``` +Which is what we're describing with the DAG in TableGen. + +## The JSON format + + +```python +full_json = run_tblgen(full_tblgen) +print(json.dumps(full_json, indent=4)) +``` + + { + "!instanceof": { + "Query": [ + "anonymous_0", + "anonymous_1", + "anonymous_2", + "anonymous_3", + "anonymous_4" + ] + }, + "!tablegen_json_version": 1, + "all": { + "!anonymous": false, + "!fields": [], + "!name": "all", + "!superclasses": [] + }, + "and": { + "!anonymous": false, + "!fields": [], + "!name": "and", + "!superclasses": [] + }, + "anonymous_0": { + "!anonymous": true, + "!fields": [], + "!name": "anonymous_0", + "!superclasses": [ + "Query" + ], + "Fields": { + "args": [], + "kind": "dag", + "operator": { + "def": "all", + "kind": "def", + "printable": "all" + }, + "printable": "(all)" + }, + "OrderedBy": [], + "TableName": "Customer", + "WhereClause": { + "args": [], + "kind": "dag", + "operator": { + "def": "none", + "kind": "def", + "printable": "none" + }, + "printable": "(none)" + } + }, + "anonymous_1": { + "!anonymous": true, + "!fields": [], + "!name": "anonymous_1", + "!superclasses": [ + "Query" + ], + "Fields": { + "args": [ + [ + "Person", + null + ], + [ + "Amount", + null + ] + ], + "kind": "dag", + "operator": { + "def": "fields", + "kind": "def", + "printable": "fields" + }, + "printable": "(fields \"Person\", \"Amount\")" + }, + "OrderedBy": [], + "TableName": "Orders", + "WhereClause": { + "args": [], + "kind": "dag", + "operator": { + "def": "none", + "kind": "def", + "printable": "none" + }, + "printable": "(none)" + } + }, + "anonymous_2": { + "!anonymous": true, + "!fields": [], + "!name": "anonymous_2", + "!superclasses": [ + "Query" + ], + "Fields": { + "args": [ + [ + "Affiliation", + null + ] + ], + "kind": "dag", + "operator": { + "def": "fields", + "kind": "def", + "printable": "fields" + }, + "printable": "(fields \"Affiliation\")" + }, + "OrderedBy": [], + "TableName": "Customer", + "WhereClause": { + "args": [ + [ + "Name", + null + ], + [ + "Mary Blackburn", + "str" + ] + ], + "kind": "dag", + "operator": { + "def": "eq", + "kind": "def", + "printable": "eq" + }, + "printable": "(eq \"Name\", \"Mary Blackburn\":$str)" + } + }, + "anonymous_3": { + "!anonymous": true, + "!fields": [], + "!name": "anonymous_3", + "!superclasses": [ + "Query" + ], + "Fields": { + "args": [ + [ + "ProductName", + null + ] + ], + "kind": "dag", + "operator": { + "def": "fields", + "kind": "def", + "printable": "fields" + }, + "printable": "(fields \"ProductName\")" + }, + "OrderedBy": [], + "TableName": "Orders", + "WhereClause": { + "args": [ + [ + "Amount", + null + ], + [ + 8, + null + ] + ], + "kind": "dag", + "operator": { + "def": "gt", + "kind": "def", + "printable": "gt" + }, + "printable": "(gt \"Amount\", 8)" + } + }, + "anonymous_4": { + "!anonymous": true, + "!fields": [], + "!name": "anonymous_4", + "!superclasses": [ + "Query" + ], + "Fields": { + "args": [ + [ + "ProductName", + "name" + ], + [ + "Person", + null + ] + ], + "kind": "dag", + "operator": { + "def": "fields", + "kind": "def", + "printable": "fields" + }, + "printable": "(fields \"ProductName\":$name, \"Person\")" + }, + "OrderedBy": [ + "$name" + ], + "TableName": "Orders", + "WhereClause": { + "args": [ + [ + { + "args": [ + [ + "Amount", + null + ], + [ + 8, + null + ] + ], + "kind": "dag", + "operator": { + "def": "gt", + "kind": "def", + "printable": "gt" + }, + "printable": "(gt \"Amount\", 8)" + }, + null + ], + [ + { + "args": [ + [ + "Person", + null + ], + [ + 1, + null + ] + ], + "kind": "dag", + "operator": { + "def": "ne", + "kind": "def", + "printable": "ne" + }, + "printable": "(ne \"Person\", 1)" + }, + null + ] + ], + "kind": "dag", + "operator": { + "def": "and", + "kind": "def", + "printable": "and" + }, + "printable": "(and (gt \"Amount\", 8), (ne \"Person\", 1))" + } + }, + "eq": { + "!anonymous": false, + "!fields": [], + "!name": "eq", + "!superclasses": [] + }, + "fields": { + "!anonymous": false, + "!fields": [], + "!name": "fields", + "!superclasses": [] + }, + "ge": { + "!anonymous": false, + "!fields": [], + "!name": "ge", + "!superclasses": [] + }, + "gt": { + "!anonymous": false, + "!fields": [], + "!name": "gt", + "!superclasses": [] + }, + "ne": { + "!anonymous": false, + "!fields": [], + "!name": "ne", + "!superclasses": [] + }, + "none": { + "!anonymous": false, + "!fields": [], + "!name": "none", + "!superclasses": [] + }, + "or": { + "!anonymous": false, + "!fields": [], + "!name": "or", + "!superclasses": [] + } + } + + +The backend is going to walk the JSON we decoded. You can see the full output above in case you want to browse but for now don't read the whole thing. We will highlight the key aspects of it as we go along. + + +```python +print(full_json["!instanceof"]) +``` + + {'Query': ['anonymous_0', 'anonymous_1', 'anonymous_2', 'anonymous_3', 'anonymous_4']} + + +Any key beginning with `!` is some sort of metadata about the other keys. Here this is a list of all instances of certain classes. We just have `Query` which lists all the queries we defined. + + +```python +print(full_json["anonymous_0"]["!superclasses"]) +``` + + ['Query'] + + +On each def there is also a `!superclasses` that gives you the same information. Meaning you could use `!instanceof` to get a list of keys to lookup, or you could walk all keys and check `!superclasses`. + + +```python +print(full_json["anonymous_0"]["Fields"]) +``` + + {'args': [], 'kind': 'dag', 'operator': {'def': 'all', 'kind': 'def', 'printable': 'all'}, 'printable': '(all)'} + + +From a def object you can find its attributes. Here we have the fields we want the query to show, which is all of them. + +# The Backend + +The core of a backend is looping over all defs of a certain class and outputting some text based on their properties. + +Here we're going to loop over all defs of type `Query` and emit SQL queries for them. + + +```python +def find_all_queries(j): + queries = [] + for key in j: + # ! means it is some metadata, not a def. + if not key.startswith("!"): + value = full_json[key] + # If we inherit from Query. + if "Query" in value["!superclasses"]: + queries.append(value) + return queries + +queries = find_all_queries(full_json) + +print([q["!name"] for q in queries]) +``` + + ['anonymous_0', 'anonymous_1', 'anonymous_2', 'anonymous_3', 'anonymous_4'] + + +Why are the names `anonymous_...`? When we defined them we did `def :` and missed out the name. This is allowed and `llvm-tblgen` just came up with a name for us. For this purpose the names are irrelevant. + +Now we have the relevant classes we need to "emit" them. Meaning produce something from them, in this case a SQL query. + + +```python +def emit_operator(operator): + return { + 'gt': ' > ', + 'ge': ' >= ', + 'lt': ' < ', + 'le': ' <= ', + 'ne': ' <> ', + 'eq': ' = ', + 'or': ' OR ', + 'and': ' AND ' + }[operator] + +print(emit_operator('and')) +``` + + AND + + +The maps our TableGen constants to the equivalent SQL logical operation. + + +```python +def emit_fields(args): + # Return a comma separated list of arg names. + return ", ".join([arg[0] for arg in args]) + +print(emit_fields([["Abc", None], ["Def", None]])) +``` + + Abc, Def + + +This emits the the fields we are selecting. Each field has a name (`arg[0]`) and an optional tag that we will use later. + + +```python +from collections.abc import Mapping + +def emit_where_clause(where_clause): + output = "" + num_args = len(where_clause["args"]) + + for idx, arg in enumerate(where_clause["args"]): + arg_name, arg_type = arg + + if isinstance(arg_name, Mapping): + # This is a nested where clause. + output += emit_where_clause(arg_name) + else: + # This is some condition. + if arg_type == "str": + # String types must be emitted with "" around them. + output += '"' + arg_name + '"' + else: + output += str(arg_name) + + # If this is not the last arg, emit the condition. + if idx != (num_args-1): + output += emit_operator(where_clause["operator"]["def"]) + + return output + +print(emit_where_clause({ +"args": [["Name",None], + ["Mary Blackburn", "str"]], +"kind": "dag", +"operator": { + "def": "eq", + "kind": "def", + "printable": "eq" +}})) +``` + + Name = "Mary Blackburn" + + +This emits the condition that goes with the `WHERE`. The condition is a DAG, which means that we will find a possible mix of conditions and other DAGS. We recurse to handle the latter case. + +For each part of the condition we print the name of the thing you're checking, then the condition (`=`, `<>`, etc.). The value to check against is last and that goes on the end. + + +```python +def emit_ordered_by(ordered_by, field_tag_map): + # No ORDER BY statement to emit. + if not ordered_by: + return "" + + output = "\n ORDER BY " + num_ordered_by = len(ordered_by) + + for idx, field_name in enumerate(ordered_by): + # If it is a tag + if field_name.startswith('$'): + # Find the corresponding field name + tag_name = field_name[1:] + field_name = field_tag_map.get(tag_name) + if field_name is None: + raise RuntimeError('Unrecognized tag "{}"'.format( + tag_name)) + + # Separate each tag after the first with ", ". + if idx != 0: + output += ", " + output += field_name + + return output + +print(emit_ordered_by(["$abc", "$def"], {'abc':"ABC", 'def':"DEF"})) +``` + + + ORDER BY ABC, DEF + + +`emit_ordered_by` produces the `ORDER BY` text. If there is no ordering return nothing, otherwise loop over all the fields we want to order by and emit their names. + +We get those names by looking up the tag given in a map to get the real name. Here's how we build that map: + + +```python +def build_tag_map(arguments): + # Args are [Name, Tag]. Reverse this so we have [Tag, Name]. + # Add each one to a dictionary where Tag is the key and Name is the value. + return dict([reversed(a) for a in arguments]) + +print(build_tag_map([["ABC", "abc"], ["DEF", "def"]])) +``` + + {'abc': 'ABC', 'def': 'DEF'} + + + +```python +def emit_query(q): + fields_init = q["Fields"] + field_op_name = fields_init["operator"]["def"] + if not field_op_name in ["all", "fields"]: + raise RuntimeError("Invalid dag operator " + field_op_name) + + field_tag_map = build_tag_map(fields_init["args"]) + + where_clause = q["WhereClause"] + has_where = where_clause["operator"]["def"] != "none" + + ret = "SELECT " + if field_op_name == "all": + ret += "*" + ret += emit_fields(fields_init["args"]) + ret += " FROM " + q["TableName"] + if has_where: + ret += "\n WHERE " + emit_where_clause(where_clause) + ret += emit_ordered_by(q["OrderedBy"], field_tag_map) + ret += ";" + + return ret +``` + +Finally the main function. It emits the skeleton of the query and calls the helpers we defined earlier to fill in the gaps. + +## The Result + + +```python +for q in queries: + print(emit_query(q) + "\n") +``` + + SELECT * FROM Customer; + + SELECT Person, Amount FROM Orders; + + SELECT Affiliation FROM Customer + WHERE Name = "Mary Blackburn"; + + SELECT ProductName FROM Orders + WHERE Amount > 8; + + SELECT ProductName, Person FROM Orders + WHERE Amount > 8 AND Person <> 1 + ORDER BY ProductName; + + + +Now we run `emit_query` and print out the results. There you have it, that's a TableGen backend! + +You've seen the core concepts. Loop over all the defs of a certain class and then emit some other structure based on the fields of each one. In this case it was SQL queries. In LLVM it's most often C++ code but it can be anything you want. + +If you want to see the same thing done with a C++ backend (meaning, one written in C++), check out the links at the start of this notebook. + + +```python + +```