[LLVM][TableGen] Notebook describing how to write a Python backend

[DavidSpickett]

Summary

This tutorial uses the dump json option to write a backend for
SQL queries.

It is based on the work of Min-Yih Hsu:

• https://github.com/mshockwave/SQLGen
• https://www.youtube.com/watch?v=UP-LBRbvI_U

I hope that having the same concepts in 3 forms will allow people
to choose the style that fits them.

The main drawback here being that it's in Python. C++ can be used
in a notebook (https://github.com/jupyter-xeus/xeus-cling) but I
decided against it for a few reasons:

• Python is the default for Jupyter, no extra installs needed.
• Having the code in a second language may help people who know one or the other.
• There is no upstream example of a JSON powered backend. (and although we would be unlikely to accept one upstream, I think it's a great option for quick development before translating into C++)

[DavidSpickett]

I should note that this does not require the tablegen kernel, it's the default iPython kernel. You will need to tell it how to find llvm-tblgen though.

@myhsu This is what we talked about over email last year.

There is a licensing issue I need you to clarify if you are ok with. Your C++ work is Apache 2.0 and this would be a derivative work of that, licensed the same. Which is a bit awkward to do here, perhaps it would be enough to include a copy of the license at the start of the tutorial, I'd have to check with an expert.

Alternatively, if you are the sole author (and therefore copyright holder) of SQLGen (which is my understanding) you could give me permission to contribute this to llvm. Where it would be under Apache 2.0 with llvm exceptions and the legacy license (as described here https://llvm.org/docs/DeveloperPolicy.html#relicensing).

That probably sounds like a small concern, but I want to do the right thing here. If you have any reservations about that, I will make my own example backend and base the tutorial on that instead, no problem.

llvm/utils/TableGen/jupyter/sql_query_backend.ipynb

100

Note that in Jupyter, this giant output collapses into a smaller panel with scroll bars. So folks can come back to it if they want detail, if not just carry on reading past it.

[myhsu]

In D142364#4073657, @DavidSpickett wrote:

I should note that this does not require the tablegen kernel, it's the default iPython kernel. You will need to tell it how to find llvm-tblgen though.

@myhsu This is what we talked about over email last year.

There is a licensing issue I need you to clarify if you are ok with. Your C++ work is Apache 2.0 and this would be a derivative work of that, licensed the same. Which is a bit awkward to do here, perhaps it would be enough to include a copy of the license at the start of the tutorial, I'd have to check with an expert.

Interesting...I naively thought that since LLVM's license is a special version of Apache 2.0, it should be easy to authorize my work to LLVM.

Alternatively, if you are the sole author (and therefore copyright holder) of SQLGen (which is my understanding) you could give me permission to contribute this to llvm. Where it would be under Apache 2.0 with llvm exceptions and the legacy license (as described here https://llvm.org/docs/DeveloperPolicy.html#relicensing).

This path definitely sounds easier to me :-) And yes, I'm the sole author and copyright holder of SQLGen. How can I give such permission to you? Send an email?

Thanks for noticing this issue!

[myhsu]

LGTM, thank you for creating this tutorial! As I also mentioned in our previous email communication, I think this really helps the broader community including beginners to learn TableGen programming.

llvm/utils/TableGen/jupyter/sql_query_backend.ipynb

4

I think it will be helpful to show the workflow of normal TG backend (TG parser -> C++ TG backend) and the Python TG backend we're developing here (llvm-tblgen -> JSON -> Python backend) side-by-side using one or two sentences.

[DavidSpickett]

This path definitely sounds easier to me :-) And yes, I'm the sole author and copyright holder of SQLGen. How can I give such permission to you? Send an email?

Just needs to be some record of it, so your comments here count for that.

[DavidSpickett]

Add explanation of C++ vs. JSON/Python backend workflow.

[DavidSpickett]

And FYI I tested SQLGen against 15.0.7 and it works out of the box.

[myhsu]

In D142364#4079397, @DavidSpickett wrote:

This path definitely sounds easier to me :-) And yes, I'm the sole author and copyright holder of SQLGen. How can I give such permission to you? Send an email?

Just needs to be some record of it, so your comments here count for that.

Great!
As the sole copyright holder of SQLGen, I give you the permission to contribute this work to LLVM.

[DavidSpickett]

Minor updates to wording. Tell people what to do if they didn't set up the
llvm-tblgen path prior to running the notebook.

llvm/utils/TableGen/jupyter/sql_query_backend.ipynb

+# 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.
+In [1]: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()
+If the above cell raises an exception, either put `llvm-tblgen` on your `PATH` or point to it using the `LLVM_TBLGEN_EXECUTABLE` environment variable. Alternatively, edit the code to use whatever path you want.
+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.
+In [2]: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 <some field names> FROM <table name>
 WHERE <conditions>
 ORDER BY <field tags>;
```
+## SQL Query TableGen
+In [3]: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` - Means that we will provide a list of fields we are interested in.
+The second set 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`).
+In [4]:query_tblgen += """\
+class Query <string table, dag query_fields = (all), dag condition = (none)> {
+  string TableName = table;
+  dag Fields = query_fields;
+  dag WhereClause = condition;
+  list<string> OrderedBy = [];
+}
+"""
+Then the Query class. Its arguments are:
* `table` - The name of the table to query (`FROM <table>`).
* `query_fields` - The fields you want returned (`SELECT <fields>`).
    * Defaults to `all` meaning return all fields.
* `condition` - Logic to select entries (`WHERE <conditions>`).
    * Defaults to `none` meaning there is no condition, or in other words select all entries in the table.
+## Using The Query Class
+In [5]: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
+In [6]: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.
+In [7]: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.
+In [8]: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`.
+In [9]: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.
+In [10]: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.
+In [11]: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.
+In [12]: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.
+In [13]: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.
+In [14]: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.
+If the name is a tag, we look that up in a map to get the real field name. Here's how we build that map:
+In [15]: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'}
+In [16]: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
+In [17]: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 (one written in C++ that is, not producing it), check out the links at the start of this notebook.

llvm/utils/TableGen/jupyter/sql_query_backend.md

+# 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()
+```
+
+If the above cell raises an exception, either put `llvm-tblgen` on your `PATH` or point to it using the `LLVM_TBLGEN_EXECUTABLE` environment variable. Alternatively, edit the code to use whatever path you want.
+
+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 <some field names> FROM <table name>
+ WHERE <conditions>
+ ORDER BY <field tags>;
+```
+
+## 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` - Means that we will provide a list of fields we are interested in.
+
+The second set 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 table, dag query_fields = (all), dag condition = (none)> {
+  string TableName = table;
+  dag Fields = query_fields;
+  dag WhereClause = condition;
+  list<string> OrderedBy = [];
+}
+"""
+```
+
+Then the Query class. Its arguments are:
+* `table` - The name of the table to query (`FROM <table>`).
+* `query_fields` - The fields you want returned (`SELECT <fields>`).
+    * Defaults to `all` meaning return all fields.
+* `condition` - Logic to select entries (`WHERE <conditions>`).
+    * 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.
+
+If the name is a tag, we look that up in a map to get the real field 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 (one written in C++ that is, not producing it), check out the links at the start of this notebook.