{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Mining Input Grammars\n",
"\n",
"So far, the grammars we have seen have been mostly specified manually – that is, you (or the person knowing the input format) had to design and write a grammar in the first place. While the grammars we have seen so far have been rather simple, creating a grammar for complex inputs can involve quite some effort. In this chapter, we therefore introduce techniques that _automatically mine grammars from programs_ – by executing the programs and observing how they process which parts of the input. In conjunction with a grammar fuzzer, this allows us to \n",
"1. take a program, \n",
"2. extract its input grammar, and \n",
"3. fuzz it with high efficiency and effectiveness, using the concepts in this book."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:52.730324Z",
"iopub.status.busy": "2024-01-18T17:19:52.729866Z",
"iopub.status.idle": "2024-01-18T17:19:52.797017Z",
"shell.execute_reply": "2024-01-18T17:19:52.796609Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
" \n",
" "
],
"text/plain": [
""
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from bookutils import YouTubeVideo\n",
"YouTubeVideo(\"ddM1oL2LYDI\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"**Prerequisites**\n",
"\n",
"* You should have read the [chapter on grammars](Grammars.ipynb).\n",
"* The [chapter on configuration fuzzing](ConfigurationFuzzer.ipynb) introduces grammar mining for configuration options, as well as observing variables and values during execution.\n",
"* We use the tracer from the [chapter on coverage](Coverage.ipynb).\n",
"* The concept of parsing from the [chapter on parsers](Parser.ipynb) is also useful."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"## Synopsis\n",
"\n",
"\n",
"To [use the code provided in this chapter](Importing.ipynb), write\n",
"\n",
"```python\n",
">>> from fuzzingbook.GrammarMiner import \n",
"```\n",
"\n",
"and then make use of the following features.\n",
"\n",
"\n",
"This chapter provides a number of classes to mine input grammars from existing programs. The function `recover_grammar()` could be the easiest to use. It takes a function and a set of inputs, and returns a grammar that describes its input language.\n",
"\n",
"We apply `recover_grammar()` on a `url_parse()` function that takes and decomposes URLs:\n",
"\n",
"```python\n",
">>> url_parse('https://www.fuzzingbook.org/')\n",
">>> URLS\n",
"['http://user:pass@www.google.com:80/?q=path#ref',\n",
" 'https://www.cispa.saarland:80/',\n",
" 'http://www.fuzzingbook.org/#News']\n",
"```\n",
"We extract the input grammar for `url_parse()` using `recover_grammar()`:\n",
"\n",
"```python\n",
">>> grammar = recover_grammar(url_parse, URLS, files=['urllib/parse.py'])\n",
">>> grammar\n",
"{'': [''],\n",
" '': [':<_splitnetloc@411:url>'],\n",
" '': ['https', 'http'],\n",
" '<_splitnetloc@411:url>': ['///',\n",
" '//'],\n",
" '': ['user:pass@www.google.com:80',\n",
" 'www.fuzzingbook.org',\n",
" 'www.cispa.saarland:80'],\n",
" '': ['#',\n",
" '/#'],\n",
" '': ['/?'],\n",
" '': ['q=path'],\n",
" '': ['ref', 'News']}\n",
"```\n",
"The names of nonterminals are a bit technical; but the grammar nicely represents the structure of the input; for instance, the different schemes (`\"http\"`, `\"https\"`) are all identified:\n",
"\n",
"```python\n",
">>> syntax_diagram(grammar)\n",
"start\n",
"\n",
"```\n",
"![](PICS/GrammarMiner-synopsis-1.svg)\n",
"```\n",
"urlsplit@437:url\n",
"\n",
"```\n",
"![](PICS/GrammarMiner-synopsis-2.svg)\n",
"```\n",
"urlparse@394:scheme\n",
"\n",
"```\n",
"![](PICS/GrammarMiner-synopsis-3.svg)\n",
"```\n",
"_splitnetloc@411:url\n",
"\n",
"```\n",
"![](PICS/GrammarMiner-synopsis-4.svg)\n",
"```\n",
"urlparse@394:netloc\n",
"\n",
"```\n",
"![](PICS/GrammarMiner-synopsis-5.svg)\n",
"```\n",
"urlsplit@481:url\n",
"\n",
"```\n",
"![](PICS/GrammarMiner-synopsis-6.svg)\n",
"```\n",
"urlsplit@486:url\n",
"\n",
"```\n",
"![](PICS/GrammarMiner-synopsis-7.svg)\n",
"```\n",
"urlparse@394:query\n",
"\n",
"```\n",
"![](PICS/GrammarMiner-synopsis-8.svg)\n",
"```\n",
"urlparse@394:fragment\n",
"\n",
"```\n",
"![](PICS/GrammarMiner-synopsis-9.svg)\n",
"\n",
"The grammar can be immediately used for fuzzing, producing arbitrary combinations of input elements, which are all syntactically valid.\n",
"\n",
"```python\n",
">>> from GrammarCoverageFuzzer import GrammarCoverageFuzzer\n",
">>> fuzzer = GrammarCoverageFuzzer(grammar)\n",
">>> [fuzzer.fuzz() for i in range(5)]\n",
"['https://www.fuzzingbook.org/',\n",
" 'http://user:pass@www.google.com:80/#News',\n",
" 'http://www.cispa.saarland:80/?q=path#ref',\n",
" 'https://user:pass@www.google.com:80/#ref',\n",
" 'https://www.cispa.saarland:80/']\n",
"```\n",
"Being able to automatically extract a grammar and to use this grammar for fuzzing makes for very effective test generation with a minimum of manual work.\n",
"\n"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## A Grammar Challenge\n",
"\n",
"Consider the `process_inventory()` method from the [chapter on parsers](Parser.ipynb):"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:52.820727Z",
"iopub.status.busy": "2024-01-18T17:19:52.820505Z",
"iopub.status.idle": "2024-01-18T17:19:52.823026Z",
"shell.execute_reply": "2024-01-18T17:19:52.822713Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import bookutils.setup"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:52.824965Z",
"iopub.status.busy": "2024-01-18T17:19:52.824826Z",
"iopub.status.idle": "2024-01-18T17:19:52.826647Z",
"shell.execute_reply": "2024-01-18T17:19:52.826358Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from typing import List, Tuple, Callable, Any\n",
"from collections.abc import Iterable"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:52.828309Z",
"iopub.status.busy": "2024-01-18T17:19:52.828171Z",
"iopub.status.idle": "2024-01-18T17:19:53.379184Z",
"shell.execute_reply": "2024-01-18T17:19:53.378754Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from Parser import process_inventory, process_vehicle, process_car, process_van, lr_graph # minor dependency"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"It takes inputs of the following form."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.381966Z",
"iopub.status.busy": "2024-01-18T17:19:53.381582Z",
"iopub.status.idle": "2024-01-18T17:19:53.383611Z",
"shell.execute_reply": "2024-01-18T17:19:53.383321Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"INVENTORY = \"\"\"\\\n",
"1997,van,Ford,E350\n",
"2000,car,Mercury,Cougar\n",
"1999,car,Chevy,Venture\\\n",
"\"\"\""
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.385287Z",
"iopub.status.busy": "2024-01-18T17:19:53.385163Z",
"iopub.status.idle": "2024-01-18T17:19:53.387090Z",
"shell.execute_reply": "2024-01-18T17:19:53.386810Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"We have a Ford E350 van from 1997 vintage.\n",
"It is an old but reliable model!\n",
"We have a Mercury Cougar car from 2000 vintage.\n",
"It is an old but reliable model!\n",
"We have a Chevy Venture car from 1999 vintage.\n",
"It is an old but reliable model!\n"
]
}
],
"source": [
"print(process_inventory(INVENTORY))"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"We found from the [chapter on parsers](Parser.ipynb) that coarse grammars do not work well for fuzzing when the input format includes details expressed only in code. That is, even though we have the formal specification of CSV files ([RFC 4180](https://tools.ietf.org/html/rfc4180)), the inventory system includes further rules as to what is expected at each index of the CSV file. The solution of simply recombining existing inputs, while practical, is incomplete. In particular, it relies on a formal input specification being available in the first place. However, we have no assurance that the program obeys the input specification given."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"One of the ways out of this predicament is to interrogate the program under test as to what its input specification is. That is, if the program under test is written in a style such that specific methods are responsible for handling specific parts of the input, one can recover the parse tree by observing the process of parsing. Further, one can recover a reasonable approximation of the grammar by abstraction from multiple input trees."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
" _We start with the assumption (1) that the program is written in such a fashion that specific methods are responsible for parsing specific fragments of the program -- This includes almost all ad hoc parsers._\n",
"\n",
"The idea is as follows:\n",
"\n",
"* Hook into the Python execution and observe the fragments of input string as they are produced and named in different methods.\n",
"* Stitch the input fragments together in a tree structure to retrieve the **Parse Tree**.\n",
"* Abstract common elements from multiple parse trees to produce the **Context Free Grammar** of the input."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## A Simple Grammar Miner"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Say we want to obtain the input grammar for the function `process_vehicle()`. We first collect the sample inputs for this function."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.388897Z",
"iopub.status.busy": "2024-01-18T17:19:53.388784Z",
"iopub.status.idle": "2024-01-18T17:19:53.390463Z",
"shell.execute_reply": "2024-01-18T17:19:53.390235Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"VEHICLES = INVENTORY.split('\\n')"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The set of methods responsible for processing inventory are the following."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.392018Z",
"iopub.status.busy": "2024-01-18T17:19:53.391906Z",
"iopub.status.idle": "2024-01-18T17:19:53.393543Z",
"shell.execute_reply": "2024-01-18T17:19:53.393228Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"INVENTORY_METHODS = {\n",
" 'process_inventory',\n",
" 'process_vehicle',\n",
" 'process_van',\n",
" 'process_car'}"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"We have seen from the chapter on [configuration fuzzing](ConfigurationFuzzer.ipynb) that one can hook into the Python runtime to observe the arguments to a function and any local variables created. We have also seen that one can obtain the context of execution by inspecting the `frame` argument. Here is a simple tracer that can return the local variables and other contextual information in a traced function. We reuse the `Coverage` tracing class."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Tracer"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.395228Z",
"iopub.status.busy": "2024-01-18T17:19:53.395112Z",
"iopub.status.idle": "2024-01-18T17:19:53.396981Z",
"shell.execute_reply": "2024-01-18T17:19:53.396554Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from Coverage import Coverage"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.398958Z",
"iopub.status.busy": "2024-01-18T17:19:53.398795Z",
"iopub.status.idle": "2024-01-18T17:19:53.400549Z",
"shell.execute_reply": "2024-01-18T17:19:53.400257Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import inspect"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.402038Z",
"iopub.status.busy": "2024-01-18T17:19:53.401930Z",
"iopub.status.idle": "2024-01-18T17:19:53.404269Z",
"shell.execute_reply": "2024-01-18T17:19:53.403977Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class Tracer(Coverage):\n",
" def traceit(self, frame, event, arg):\n",
" method_name = inspect.getframeinfo(frame).function\n",
" if method_name not in INVENTORY_METHODS:\n",
" return\n",
" file_name = inspect.getframeinfo(frame).filename\n",
"\n",
" param_names = inspect.getargvalues(frame).args\n",
" lineno = inspect.getframeinfo(frame).lineno\n",
" local_vars = inspect.getargvalues(frame).locals\n",
" print(event, file_name, lineno, method_name, param_names, local_vars)\n",
" return self.traceit"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"We run the code under trace context."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.405907Z",
"iopub.status.busy": "2024-01-18T17:19:53.405804Z",
"iopub.status.idle": "2024-01-18T17:19:53.456454Z",
"shell.execute_reply": "2024-01-18T17:19:53.456165Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"call /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb 29 process_vehicle ['vehicle'] {'vehicle': '1997,van,Ford,E350'}\n",
"line /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb 30 process_vehicle ['vehicle'] {'vehicle': '1997,van,Ford,E350'}\n",
"line /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb 31 process_vehicle ['vehicle'] {'vehicle': '1997,van,Ford,E350', 'year': '1997', 'kind': 'van', 'company': 'Ford', 'model': 'E350', '_': []}\n",
"line /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb 32 process_vehicle ['vehicle'] {'vehicle': '1997,van,Ford,E350', 'year': '1997', 'kind': 'van', 'company': 'Ford', 'model': 'E350', '_': []}\n",
"call /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb 40 process_van ['year', 'company', 'model'] {'year': '1997', 'company': 'Ford', 'model': 'E350'}\n",
"line /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb 41 process_van ['year', 'company', 'model'] {'year': '1997', 'company': 'Ford', 'model': 'E350'}\n",
"line /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb 42 process_van ['year', 'company', 'model'] {'year': '1997', 'company': 'Ford', 'model': 'E350', 'res': ['We have a Ford E350 van from 1997 vintage.']}\n",
"line /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb 43 process_van ['year', 'company', 'model'] {'year': '1997', 'company': 'Ford', 'model': 'E350', 'res': ['We have a Ford E350 van from 1997 vintage.'], 'iyear': 1997}\n",
"line /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb 46 process_van ['year', 'company', 'model'] {'year': '1997', 'company': 'Ford', 'model': 'E350', 'res': ['We have a Ford E350 van from 1997 vintage.'], 'iyear': 1997}\n",
"line /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb 47 process_van ['year', 'company', 'model'] {'year': '1997', 'company': 'Ford', 'model': 'E350', 'res': ['We have a Ford E350 van from 1997 vintage.', 'It is an old but reliable model!'], 'iyear': 1997}\n",
"return /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb 47 process_van ['year', 'company', 'model'] {'year': '1997', 'company': 'Ford', 'model': 'E350', 'res': ['We have a Ford E350 van from 1997 vintage.', 'It is an old but reliable model!'], 'iyear': 1997}\n",
"return /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb 32 process_vehicle ['vehicle'] {'vehicle': '1997,van,Ford,E350', 'year': '1997', 'kind': 'van', 'company': 'Ford', 'model': 'E350', '_': []}\n"
]
}
],
"source": [
"with Tracer() as tracer:\n",
" process_vehicle(VEHICLES[0])"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The main thing that we want out of tracing is a list of assignments of input fragments to different variables. We can use the tracing facility `settrace()` to get that as we showed above.\n",
"\n",
"However, the `settrace()` function hooks into the Python debugging facility. When it is in operation, no debugger can hook into the program. That is, if there is a problem with our grammar miner, we will not be able to attach a debugger to it to understand what is happening. This is not ideal. Hence, we limit the tracer to the simplest implementation possible, and implement the core of grammar mining in later stages."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The `traceit()` function relies on information from the `frame` variable which exposes Python internals. We define a `context` class that encapsulates the information that we need from the `frame`."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Context\n",
"\n",
"The `Context` class provides easy access to the information such as the current module, and parameter names."
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.458508Z",
"iopub.status.busy": "2024-01-18T17:19:53.458395Z",
"iopub.status.idle": "2024-01-18T17:19:53.461016Z",
"shell.execute_reply": "2024-01-18T17:19:53.460709Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class Context:\n",
" def __init__(self, frame, track_caller=True):\n",
" self.method = inspect.getframeinfo(frame).function\n",
" self.parameter_names = inspect.getargvalues(frame).args\n",
" self.file_name = inspect.getframeinfo(frame).filename\n",
" self.line_no = inspect.getframeinfo(frame).lineno\n",
"\n",
" def _t(self):\n",
" return (self.file_name, self.line_no, self.method,\n",
" ','.join(self.parameter_names))\n",
"\n",
" def __repr__(self):\n",
" return \"%s:%d:%s(%s)\" % self._t()"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Here we add a few convenience methods that operate on the `frame` to `Context`."
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.463101Z",
"iopub.status.busy": "2024-01-18T17:19:53.462932Z",
"iopub.status.idle": "2024-01-18T17:19:53.465678Z",
"shell.execute_reply": "2024-01-18T17:19:53.465331Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class Context(Context):\n",
" def extract_vars(self, frame):\n",
" return inspect.getargvalues(frame).locals\n",
"\n",
" def parameters(self, all_vars):\n",
" return {k: v for k, v in all_vars.items() if k in self.parameter_names}\n",
"\n",
" def qualified(self, all_vars):\n",
" return {\"%s:%s\" % (self.method, k): v for k, v in all_vars.items()}"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"We hook printing the context to our `traceit()` to see it in action. First we define a `log_event()` for displaying events."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.467730Z",
"iopub.status.busy": "2024-01-18T17:19:53.467528Z",
"iopub.status.idle": "2024-01-18T17:19:53.469528Z",
"shell.execute_reply": "2024-01-18T17:19:53.469238Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def log_event(event, var):\n",
" print({'call': '->', 'return': '<-'}.get(event, ' '), var)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"And use the `log_event()` in the `traceit()` function."
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.471544Z",
"iopub.status.busy": "2024-01-18T17:19:53.471369Z",
"iopub.status.idle": "2024-01-18T17:19:53.473421Z",
"shell.execute_reply": "2024-01-18T17:19:53.473152Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class Tracer(Tracer):\n",
" def traceit(self, frame, event, arg):\n",
" log_event(event, Context(frame))\n",
" return self.traceit"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Running `process_vehicle()` under trace prints the contexts encountered."
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.475038Z",
"iopub.status.busy": "2024-01-18T17:19:53.474906Z",
"iopub.status.idle": "2024-01-18T17:19:53.478637Z",
"shell.execute_reply": "2024-01-18T17:19:53.478264Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"-> /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:29:process_vehicle(vehicle)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:30:process_vehicle(vehicle)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:31:process_vehicle(vehicle)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:32:process_vehicle(vehicle)\n",
"-> /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:40:process_van(year,company,model)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:41:process_van(year,company,model)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:42:process_van(year,company,model)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:43:process_van(year,company,model)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:46:process_van(year,company,model)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:47:process_van(year,company,model)\n",
"<- /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:47:process_van(year,company,model)\n",
"<- /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:32:process_vehicle(vehicle)\n",
"-> /Users/zeller/Projects/fuzzingbook/notebooks/Coverage.ipynb:102:__exit__(self,exc_type,exc_value,tb)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Coverage.ipynb:105:__exit__(self,exc_type,exc_value,tb)\n"
]
}
],
"source": [
"with Tracer() as tracer:\n",
" process_vehicle(VEHICLES[0])"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The trace produced by executing any function can get overwhelmingly large. Hence, we need to restrict our attention to specific modules. Further, we also restrict our attention exclusively to `str` variables since these variables are more likely to contain input fragments. (We will show how to deal with complex objects later in exercises.)\n",
"\n",
"The `Context` class we developed earlier is used to decide which modules to monitor, and which variables to trace.\n",
"\n",
"We store the current *input string* so that it can be used to determine if any particular string fragments came from the current input string. Any optional arguments are processed separately."
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.481084Z",
"iopub.status.busy": "2024-01-18T17:19:53.480976Z",
"iopub.status.idle": "2024-01-18T17:19:53.483029Z",
"shell.execute_reply": "2024-01-18T17:19:53.482777Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class Tracer(Tracer):\n",
" def __init__(self, my_input, **kwargs):\n",
" self.options(kwargs)\n",
" self.my_input, self.trace = my_input, []"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"We use an optional argument `files` to indicate the specific source files we are interested in, and `methods` to indicate which specific methods are of interest. Further, we also use `log` to specify whether verbose logging should be enabled during trace. We use the `log_event()` method we defined earlier for logging."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The options processing is as below."
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.484605Z",
"iopub.status.busy": "2024-01-18T17:19:53.484521Z",
"iopub.status.idle": "2024-01-18T17:19:53.486425Z",
"shell.execute_reply": "2024-01-18T17:19:53.486202Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class Tracer(Tracer):\n",
" def options(self, kwargs):\n",
" self.files = kwargs.get('files', [])\n",
" self.methods = kwargs.get('methods', [])\n",
" self.log = log_event if kwargs.get('log') else lambda _evt, _var: None"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The `files` and `methods` are checked to determine, if a particular event should be traced or not"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.488025Z",
"iopub.status.busy": "2024-01-18T17:19:53.487930Z",
"iopub.status.idle": "2024-01-18T17:19:53.490006Z",
"shell.execute_reply": "2024-01-18T17:19:53.489772Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class Tracer(Tracer):\n",
" def tracing_context(self, cxt, event, arg):\n",
" fres = not self.files or any(\n",
" cxt.file_name.endswith(f) for f in self.files)\n",
" mres = not self.methods or any(cxt.method == m for m in self.methods)\n",
" return fres and mres"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Similar to the context of events, we also want to restrict our attention to specific variables. For now, we want to focus only on strings. (See the Exercises at the end of the chapter on how to extend it to other kinds of objects)."
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.491503Z",
"iopub.status.busy": "2024-01-18T17:19:53.491423Z",
"iopub.status.idle": "2024-01-18T17:19:53.493259Z",
"shell.execute_reply": "2024-01-18T17:19:53.492951Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class Tracer(Tracer):\n",
" def tracing_var(self, k, v):\n",
" return isinstance(v, str)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"We modify the `traceit()` to call an `on_event()` function with the context information only on the specific events we are interested in."
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.494975Z",
"iopub.status.busy": "2024-01-18T17:19:53.494863Z",
"iopub.status.idle": "2024-01-18T17:19:53.497896Z",
"shell.execute_reply": "2024-01-18T17:19:53.497584Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class Tracer(Tracer):\n",
" def on_event(self, event, arg, cxt, my_vars):\n",
" self.trace.append((event, arg, cxt, my_vars))\n",
" \n",
" def create_context(self, frame):\n",
" return Context(frame)\n",
"\n",
" def traceit(self, frame, event, arg):\n",
" cxt = self.create_context(frame)\n",
" if not self.tracing_context(cxt, event, arg):\n",
" return self.traceit\n",
" self.log(event, cxt)\n",
"\n",
" my_vars = {\n",
" k: v\n",
" for k, v in cxt.extract_vars(frame).items()\n",
" if self.tracing_var(k, v)\n",
" }\n",
" self.on_event(event, arg, cxt, my_vars)\n",
" return self.traceit"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The `Tracer` class can now focus on specific kinds of events on specific files. Further, it provides a first level filter for variables that we find interesting. For example, we want to focus specifically on variables from `process_*` methods that contain input fragments. Here is how our updated `Tracer` can be used."
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.499521Z",
"iopub.status.busy": "2024-01-18T17:19:53.499408Z",
"iopub.status.idle": "2024-01-18T17:19:53.502685Z",
"shell.execute_reply": "2024-01-18T17:19:53.502380Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"-> /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:29:process_vehicle(vehicle)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:30:process_vehicle(vehicle)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:31:process_vehicle(vehicle)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:32:process_vehicle(vehicle)\n",
"-> /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:40:process_van(year,company,model)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:41:process_van(year,company,model)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:42:process_van(year,company,model)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:43:process_van(year,company,model)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:46:process_van(year,company,model)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:47:process_van(year,company,model)\n",
"<- /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:47:process_van(year,company,model)\n",
"<- /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:32:process_vehicle(vehicle)\n"
]
}
],
"source": [
"with Tracer(VEHICLES[0], methods=INVENTORY_METHODS, log=True) as tracer:\n",
" process_vehicle(VEHICLES[0])"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The execution produced the following trace."
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.504267Z",
"iopub.status.busy": "2024-01-18T17:19:53.504190Z",
"iopub.status.idle": "2024-01-18T17:19:53.506541Z",
"shell.execute_reply": "2024-01-18T17:19:53.506295Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"call process_vehicle {'vehicle': '1997,van,Ford,E350'}\n",
"line process_vehicle {'vehicle': '1997,van,Ford,E350'}\n",
"line process_vehicle {'vehicle': '1997,van,Ford,E350', 'year': '1997', 'kind': 'van', 'company': 'Ford', 'model': 'E350'}\n",
"line process_vehicle {'vehicle': '1997,van,Ford,E350', 'year': '1997', 'kind': 'van', 'company': 'Ford', 'model': 'E350'}\n",
"call process_van {'year': '1997', 'company': 'Ford', 'model': 'E350'}\n",
"line process_van {'year': '1997', 'company': 'Ford', 'model': 'E350'}\n",
"line process_van {'year': '1997', 'company': 'Ford', 'model': 'E350'}\n",
"line process_van {'year': '1997', 'company': 'Ford', 'model': 'E350'}\n",
"line process_van {'year': '1997', 'company': 'Ford', 'model': 'E350'}\n",
"line process_van {'year': '1997', 'company': 'Ford', 'model': 'E350'}\n",
"return process_van {'year': '1997', 'company': 'Ford', 'model': 'E350'}\n",
"return process_vehicle {'vehicle': '1997,van,Ford,E350', 'year': '1997', 'kind': 'van', 'company': 'Ford', 'model': 'E350'}\n"
]
}
],
"source": [
"for t in tracer.trace:\n",
" print(t[0], t[2].method, dict(t[3]))"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Since we are saving the input already in `Tracer`, it is redundant to specify it separately again as an argument."
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.508116Z",
"iopub.status.busy": "2024-01-18T17:19:53.508036Z",
"iopub.status.idle": "2024-01-18T17:19:53.511524Z",
"shell.execute_reply": "2024-01-18T17:19:53.511241Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"-> /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:29:process_vehicle(vehicle)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:30:process_vehicle(vehicle)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:31:process_vehicle(vehicle)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:32:process_vehicle(vehicle)\n",
"-> /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:40:process_van(year,company,model)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:41:process_van(year,company,model)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:42:process_van(year,company,model)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:43:process_van(year,company,model)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:46:process_van(year,company,model)\n",
" /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:47:process_van(year,company,model)\n",
"<- /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:47:process_van(year,company,model)\n",
"<- /Users/zeller/Projects/fuzzingbook/notebooks/Parser.ipynb:32:process_vehicle(vehicle)\n"
]
}
],
"source": [
"with Tracer(VEHICLES[0], methods=INVENTORY_METHODS, log=True) as tracer:\n",
" process_vehicle(tracer.my_input)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### DefineTracker"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"We define a `DefineTracker` class that processes the trace from the `Tracer`. The idea is to store different variable definitions which are input fragments.\n",
"\n",
"The tracker identifies string fragments that are part of the input string, and stores them in a dictionary `my_assignments`. It saves the trace, and the corresponding input for processing. Finally, it calls `process()` to process the `trace` it was given. We will start with a simple tracker that relies on certain assumptions, and later see how these assumptions can be relaxed."
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.513781Z",
"iopub.status.busy": "2024-01-18T17:19:53.513502Z",
"iopub.status.idle": "2024-01-18T17:19:53.515584Z",
"shell.execute_reply": "2024-01-18T17:19:53.515355Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class DefineTracker:\n",
" def __init__(self, my_input, trace, **kwargs):\n",
" self.options(kwargs)\n",
" self.my_input = my_input\n",
" self.trace = trace\n",
" self.my_assignments = {}\n",
" self.process()"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"One of the problems of using substring search is that short string sequences tend to be included in other string sequences even though they may not have come from the original string. That is, say the input fragment is `v`, it could have equally come from either `van` or `chevy`. We rely on being able to predict the exact place in the input where a given fragment occurred. Hence, we define a constant `FRAGMENT_LEN` such that we ignore strings up to that length. We also incorporate a logging facility as before."
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.517382Z",
"iopub.status.busy": "2024-01-18T17:19:53.517057Z",
"iopub.status.idle": "2024-01-18T17:19:53.518851Z",
"shell.execute_reply": "2024-01-18T17:19:53.518616Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"FRAGMENT_LEN = 3"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.520531Z",
"iopub.status.busy": "2024-01-18T17:19:53.520348Z",
"iopub.status.idle": "2024-01-18T17:19:53.522130Z",
"shell.execute_reply": "2024-01-18T17:19:53.521902Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class DefineTracker(DefineTracker):\n",
" def options(self, kwargs):\n",
" self.log = log_event if kwargs.get('log') else lambda _evt, _var: None\n",
" self.fragment_len = kwargs.get('fragment_len', FRAGMENT_LEN)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Our tracer simply records the variable values as they occur. We next need to check if the variables contain values from the **input string**. Common ways to do this is to rely on symbolic execution or at least dynamic tainting, which are powerful, but also complex. However, one can obtain a reasonable approximation by simply relying on substring search. That is, we consider any value produced that is a substring of the original input string to have come from the original input."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"We define an `is_input_fragment()` method that relies on string inclusion to detect if the string came from the input."
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.523651Z",
"iopub.status.busy": "2024-01-18T17:19:53.523492Z",
"iopub.status.idle": "2024-01-18T17:19:53.525342Z",
"shell.execute_reply": "2024-01-18T17:19:53.525111Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class DefineTracker(DefineTracker):\n",
" def is_input_fragment(self, var, value):\n",
" return len(value) >= self.fragment_len and value in self.my_input"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"We can use `is_input_fragment()` to select only a subset of variables defined, as implemented below in `fragments()`."
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.526915Z",
"iopub.status.busy": "2024-01-18T17:19:53.526790Z",
"iopub.status.idle": "2024-01-18T17:19:53.528726Z",
"shell.execute_reply": "2024-01-18T17:19:53.528444Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class DefineTracker(DefineTracker):\n",
" def fragments(self, variables):\n",
" return {k: v for k, v in variables.items(\n",
" ) if self.is_input_fragment(k, v)}"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The tracker processes each event, and at each event, it updates the dictionary `my_assignments` with the current local variables that contain strings that are part of the input. Note that there is a choice here with respect to what happens during reassignment. We can either discard all the reassignments, or keep only the last assignment. Here, we choose the latter. If you want the former behavior, check whether the value exists in `my_assignments` before storing a fragment."
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.530332Z",
"iopub.status.busy": "2024-01-18T17:19:53.530226Z",
"iopub.status.idle": "2024-01-18T17:19:53.532384Z",
"shell.execute_reply": "2024-01-18T17:19:53.532148Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class DefineTracker(DefineTracker):\n",
" def track_event(self, event, arg, cxt, my_vars):\n",
" self.log(event, (cxt.method, my_vars))\n",
" self.my_assignments.update(self.fragments(my_vars))\n",
"\n",
" def process(self):\n",
" for event, arg, cxt, my_vars in self.trace:\n",
" self.track_event(event, arg, cxt, my_vars)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Using the tracker, we can obtain the input fragments. For example, say we are only interested in strings that are at least `5` characters long."
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.533870Z",
"iopub.status.busy": "2024-01-18T17:19:53.533742Z",
"iopub.status.idle": "2024-01-18T17:19:53.535725Z",
"shell.execute_reply": "2024-01-18T17:19:53.535437Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"vehicle = '1997,van,Ford,E350'\n"
]
}
],
"source": [
"tracker = DefineTracker(tracer.my_input, tracer.trace, fragment_len=5)\n",
"for k, v in tracker.my_assignments.items():\n",
" print(k, '=', repr(v))"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Or strings that are `2` characters long (the default)."
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.537282Z",
"iopub.status.busy": "2024-01-18T17:19:53.537179Z",
"iopub.status.idle": "2024-01-18T17:19:53.539147Z",
"shell.execute_reply": "2024-01-18T17:19:53.538874Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"vehicle = '1997,van,Ford,E350'\n",
"year = '1997'\n",
"kind = 'van'\n",
"company = 'Ford'\n",
"model = 'E350'\n"
]
}
],
"source": [
"tracker = DefineTracker(tracer.my_input, tracer.trace)\n",
"for k, v in tracker.my_assignments.items():\n",
" print(k, '=', repr(v))"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.540654Z",
"iopub.status.busy": "2024-01-18T17:19:53.540554Z",
"iopub.status.idle": "2024-01-18T17:19:53.542109Z",
"shell.execute_reply": "2024-01-18T17:19:53.541879Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class DefineTracker(DefineTracker):\n",
" def assignments(self):\n",
" return self.my_assignments.items()"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Assembling a Derivation Tree"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.543626Z",
"iopub.status.busy": "2024-01-18T17:19:53.543530Z",
"iopub.status.idle": "2024-01-18T17:19:53.545303Z",
"shell.execute_reply": "2024-01-18T17:19:53.545019Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from Grammars import START_SYMBOL, syntax_diagram, \\\n",
" is_nonterminal, Grammar"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.546798Z",
"iopub.status.busy": "2024-01-18T17:19:53.546693Z",
"iopub.status.idle": "2024-01-18T17:19:53.548176Z",
"shell.execute_reply": "2024-01-18T17:19:53.547968Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from GrammarFuzzer import GrammarFuzzer, display_tree, \\\n",
" DerivationTree"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The input fragments from the `DefineTracker` only tell half the story. The fragments may be created at different stages of parsing. Hence, we need to assemble the fragments to a derivation tree of the input. The basic idea is as follows:\n",
"\n",
"Our input from the previous step was:\n",
"\n",
"```python\n",
"\"1997,van,Ford,E350\"\n",
"```\n",
"\n",
"We start a derivation tree, and associate it with the start symbol in the grammar."
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.549513Z",
"iopub.status.busy": "2024-01-18T17:19:53.549431Z",
"iopub.status.idle": "2024-01-18T17:19:53.551278Z",
"shell.execute_reply": "2024-01-18T17:19:53.551043Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"derivation_tree: DerivationTree = (START_SYMBOL, [(\"1997,van,Ford,E350\", [])])"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.552672Z",
"iopub.status.busy": "2024-01-18T17:19:53.552592Z",
"iopub.status.idle": "2024-01-18T17:19:53.941286Z",
"shell.execute_reply": "2024-01-18T17:19:53.940918Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"display_tree(derivation_tree)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The next input was:\n",
"```python\n",
"vehicle = \"1997,van,Ford,E350\"\n",
"```\n",
"Since vehicle covers the `` node's value completely, we replace the value with the vehicle node."
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.943292Z",
"iopub.status.busy": "2024-01-18T17:19:53.943133Z",
"iopub.status.idle": "2024-01-18T17:19:53.945280Z",
"shell.execute_reply": "2024-01-18T17:19:53.945017Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"derivation_tree: DerivationTree = (START_SYMBOL, \n",
" [('', [(\"1997,van,Ford,E350\", [])],\n",
" [])])"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:53.946729Z",
"iopub.status.busy": "2024-01-18T17:19:53.946595Z",
"iopub.status.idle": "2024-01-18T17:19:54.324708Z",
"shell.execute_reply": "2024-01-18T17:19:54.324347Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"display_tree(derivation_tree)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The next input was:\n",
"```python\n",
"year = '1997'\n",
"```\n",
"Traversing the derivation tree from ``, we see that it replaces a portion of the `` node's value. Hence we split the `` node's value to two children, where one corresponds to the value `\"1997\"` and the other to `\",van,Ford,E350\"`, and replace the first one with the node ``."
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:54.326610Z",
"iopub.status.busy": "2024-01-18T17:19:54.326450Z",
"iopub.status.idle": "2024-01-18T17:19:54.328785Z",
"shell.execute_reply": "2024-01-18T17:19:54.328486Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"derivation_tree: DerivationTree = (START_SYMBOL, \n",
" [('', [('', [('1997', [])]),\n",
" (\",van,Ford,E350\", [])], [])])"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:54.330321Z",
"iopub.status.busy": "2024-01-18T17:19:54.330188Z",
"iopub.status.idle": "2024-01-18T17:19:54.705251Z",
"shell.execute_reply": "2024-01-18T17:19:54.704909Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"display_tree(derivation_tree)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"We perform similar operations for \n",
"```python\n",
"company = 'Ford'\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:54.707066Z",
"iopub.status.busy": "2024-01-18T17:19:54.706942Z",
"iopub.status.idle": "2024-01-18T17:19:54.709234Z",
"shell.execute_reply": "2024-01-18T17:19:54.708894Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"derivation_tree: DerivationTree = (START_SYMBOL, \n",
" [('', [('', [('1997', [])]),\n",
" (\",van,\", []),\n",
" ('', [('Ford', [])]),\n",
" (\",E350\", [])], [])])"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:54.710840Z",
"iopub.status.busy": "2024-01-18T17:19:54.710714Z",
"iopub.status.idle": "2024-01-18T17:19:55.110981Z",
"shell.execute_reply": "2024-01-18T17:19:55.110562Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"display_tree(derivation_tree)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Similarly for\n",
"```python\n",
"kind = 'van'\n",
"```\n",
"and\n",
"```python\n",
"model = 'E350'\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:55.113465Z",
"iopub.status.busy": "2024-01-18T17:19:55.113132Z",
"iopub.status.idle": "2024-01-18T17:19:55.115850Z",
"shell.execute_reply": "2024-01-18T17:19:55.115580Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"derivation_tree: DerivationTree = (START_SYMBOL, \n",
" [('', [('', [('1997', [])]),\n",
" (\",\", []),\n",
" (\"\", [('van', [])]),\n",
" (\",\", []),\n",
" ('', [('Ford', [])]),\n",
" (\",\", []),\n",
" (\"\", [('E350', [])])\n",
" ], [])])"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:55.117413Z",
"iopub.status.busy": "2024-01-18T17:19:55.117312Z",
"iopub.status.idle": "2024-01-18T17:19:55.494644Z",
"shell.execute_reply": "2024-01-18T17:19:55.494281Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"display_tree(derivation_tree)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"We now develop the complete algorithm with the above described steps.\n",
"The derivation tree `TreeMiner` is initialized with the input string, and the variable assignments, and it converts the assignments to the corresponding derivation tree."
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:55.496327Z",
"iopub.status.busy": "2024-01-18T17:19:55.496217Z",
"iopub.status.idle": "2024-01-18T17:19:55.498847Z",
"shell.execute_reply": "2024-01-18T17:19:55.498489Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class TreeMiner:\n",
" def __init__(self, my_input, my_assignments, **kwargs):\n",
" self.options(kwargs)\n",
" self.my_input = my_input\n",
" self.my_assignments = my_assignments\n",
" self.tree = self.get_derivation_tree()\n",
"\n",
" def options(self, kwargs):\n",
" self.log = log_call if kwargs.get('log') else lambda _i, _v: None\n",
"\n",
" def get_derivation_tree(self):\n",
" return (START_SYMBOL, [])"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The `log_call()` is as follows."
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:55.500651Z",
"iopub.status.busy": "2024-01-18T17:19:55.500531Z",
"iopub.status.idle": "2024-01-18T17:19:55.502233Z",
"shell.execute_reply": "2024-01-18T17:19:55.501934Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def log_call(indent, var):\n",
" print('\\t' * indent, var)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The basic idea is as follows:\n",
"* **For now, we assume that the value assigned to a variable is stable. That is, it is never reassigned. In particular, there are no recursive calls, or multiple calls to the same function from different parts.** (We will show how to overcome this limitation later).\n",
"* For each pair _var_, _value_ found in `my_assignments`:\n",
" 1. We search for occurrences of _value_ `val` in the derivation tree recursively.\n",
" 2. If an occurrence was found as a value `V1` of a node `P1`, we partition the value of the node `P1` into three parts, with the central part matching the _value_ `val`, and the first and last part, the corresponding prefix and suffix in `V1`.\n",
" 3. Reconstitute the node `P1` with three children, where prefix and suffix mentioned earlier are string values, and the matching value `val` is replaced by a node `var` with a single value `val`."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"First, we define a wrapper to generate a nonterminal from a variable name."
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:55.503812Z",
"iopub.status.busy": "2024-01-18T17:19:55.503690Z",
"iopub.status.idle": "2024-01-18T17:19:55.505406Z",
"shell.execute_reply": "2024-01-18T17:19:55.505138Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def to_nonterminal(var):\n",
" return \"<\" + var.lower() + \">\""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The `string_part_of_value()` method checks whether the given `part` value was part of the whole."
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:55.506958Z",
"iopub.status.busy": "2024-01-18T17:19:55.506850Z",
"iopub.status.idle": "2024-01-18T17:19:55.508542Z",
"shell.execute_reply": "2024-01-18T17:19:55.508304Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class TreeMiner(TreeMiner):\n",
" def string_part_of_value(self, part, value):\n",
" return (part in value)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The `partition_by_part()` splits the `value` by the given part if it matches, and returns a list containing the first part, the part that was replaced, and the last part. This is a format that can be used as a part of the list of children."
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:55.510130Z",
"iopub.status.busy": "2024-01-18T17:19:55.510026Z",
"iopub.status.idle": "2024-01-18T17:19:55.511794Z",
"shell.execute_reply": "2024-01-18T17:19:55.511571Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class TreeMiner(TreeMiner):\n",
" def partition(self, part, value):\n",
" return value.partition(part)"
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:55.513175Z",
"iopub.status.busy": "2024-01-18T17:19:55.513056Z",
"iopub.status.idle": "2024-01-18T17:19:55.515093Z",
"shell.execute_reply": "2024-01-18T17:19:55.514843Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class TreeMiner(TreeMiner):\n",
" def partition_by_part(self, pair, value):\n",
" k, part = pair\n",
" prefix_k_suffix = [\n",
" (k, [[part, []]]) if i == 1 else (e, [])\n",
" for i, e in enumerate(self.partition(part, value))\n",
" if e]\n",
" return prefix_k_suffix"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The `insert_into_tree()` method accepts a given tree `tree` and a `(k,v)` pair. It recursively checks whether the given pair can be applied. If the pair can be applied, it applies the pair and returns `True`."
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:55.516820Z",
"iopub.status.busy": "2024-01-18T17:19:55.516708Z",
"iopub.status.idle": "2024-01-18T17:19:55.520155Z",
"shell.execute_reply": "2024-01-18T17:19:55.519840Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class TreeMiner(TreeMiner):\n",
" def insert_into_tree(self, my_tree, pair):\n",
" var, values = my_tree\n",
" k, v = pair\n",
" self.log(1, \"- Node: %s\\t\\t? (%s:%s)\" % (var, k, repr(v)))\n",
" applied = False\n",
" for i, value_ in enumerate(values):\n",
" value, arr = value_\n",
" self.log(2, \"-> [%d] %s\" % (i, repr(value)))\n",
" if is_nonterminal(value):\n",
" applied = self.insert_into_tree(value_, pair)\n",
" if applied:\n",
" break\n",
" elif self.string_part_of_value(v, value):\n",
" prefix_k_suffix = self.partition_by_part(pair, value)\n",
" del values[i]\n",
" for j, rep in enumerate(prefix_k_suffix):\n",
" values.insert(j + i, rep)\n",
" applied = True\n",
"\n",
" self.log(2, \" > %s\" % (repr([i[0] for i in prefix_k_suffix])))\n",
" break\n",
" else:\n",
" continue\n",
" return applied"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Here is how `insert_into_tree()` is used."
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:55.521880Z",
"iopub.status.busy": "2024-01-18T17:19:55.521767Z",
"iopub.status.idle": "2024-01-18T17:19:55.523694Z",
"shell.execute_reply": "2024-01-18T17:19:55.523393Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"tree: DerivationTree = (START_SYMBOL, [(\"1997,van,Ford,E350\", [])])\n",
"m = TreeMiner('', {}, log=True)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"First, we have our input string as the only node."
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:55.525237Z",
"iopub.status.busy": "2024-01-18T17:19:55.525145Z",
"iopub.status.idle": "2024-01-18T17:19:55.929214Z",
"shell.execute_reply": "2024-01-18T17:19:55.928633Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"display_tree(tree)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Inserting the `` node."
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:55.931407Z",
"iopub.status.busy": "2024-01-18T17:19:55.931256Z",
"iopub.status.idle": "2024-01-18T17:19:55.933600Z",
"shell.execute_reply": "2024-01-18T17:19:55.933270Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\t - Node: \t\t? (:'1997,van,Ford,E350')\n",
"\t\t -> [0] '1997,van,Ford,E350'\n",
"\t\t > ['']\n"
]
}
],
"source": [
"v = m.insert_into_tree(tree, ('', \"1997,van,Ford,E350\"))"
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:55.935265Z",
"iopub.status.busy": "2024-01-18T17:19:55.935138Z",
"iopub.status.idle": "2024-01-18T17:19:56.321766Z",
"shell.execute_reply": "2024-01-18T17:19:56.321407Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"display_tree(tree)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Inserting `` node."
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:56.323685Z",
"iopub.status.busy": "2024-01-18T17:19:56.323562Z",
"iopub.status.idle": "2024-01-18T17:19:56.325563Z",
"shell.execute_reply": "2024-01-18T17:19:56.325311Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\t - Node: \t\t? (:'E350')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'E350')\n",
"\t\t -> [0] '1997,van,Ford,E350'\n",
"\t\t > ['1997,van,Ford,', '']\n"
]
}
],
"source": [
"v = m.insert_into_tree(tree, ('', 'E350'))"
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:56.327475Z",
"iopub.status.busy": "2024-01-18T17:19:56.327245Z",
"iopub.status.idle": "2024-01-18T17:19:56.692057Z",
"shell.execute_reply": "2024-01-18T17:19:56.691671Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 59,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"display_tree((tree))"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Inserting ``."
]
},
{
"cell_type": "code",
"execution_count": 60,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:56.694084Z",
"iopub.status.busy": "2024-01-18T17:19:56.693931Z",
"iopub.status.idle": "2024-01-18T17:19:56.696562Z",
"shell.execute_reply": "2024-01-18T17:19:56.696205Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\t - Node: \t\t? (:'Ford')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'Ford')\n",
"\t\t -> [0] '1997,van,Ford,'\n",
"\t\t > ['1997,van,', '', ',']\n"
]
}
],
"source": [
"v = m.insert_into_tree(tree, ('', 'Ford'))"
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:56.698920Z",
"iopub.status.busy": "2024-01-18T17:19:56.698723Z",
"iopub.status.idle": "2024-01-18T17:19:57.088624Z",
"shell.execute_reply": "2024-01-18T17:19:57.088213Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 61,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"display_tree(tree)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Inserting ``."
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:57.090562Z",
"iopub.status.busy": "2024-01-18T17:19:57.090408Z",
"iopub.status.idle": "2024-01-18T17:19:57.092920Z",
"shell.execute_reply": "2024-01-18T17:19:57.092553Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\t - Node: \t\t? (:'van')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'van')\n",
"\t\t -> [0] '1997,van,'\n",
"\t\t > ['1997,', '', ',']\n"
]
}
],
"source": [
"v = m.insert_into_tree(tree, ('', 'van'))"
]
},
{
"cell_type": "code",
"execution_count": 63,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:57.094892Z",
"iopub.status.busy": "2024-01-18T17:19:57.094753Z",
"iopub.status.idle": "2024-01-18T17:19:57.511885Z",
"shell.execute_reply": "2024-01-18T17:19:57.511454Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 63,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"display_tree(tree)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Inserting ``."
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:57.513812Z",
"iopub.status.busy": "2024-01-18T17:19:57.513695Z",
"iopub.status.idle": "2024-01-18T17:19:57.515867Z",
"shell.execute_reply": "2024-01-18T17:19:57.515632Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\t - Node: \t\t? (:'1997')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'1997')\n",
"\t\t -> [0] '1997,'\n",
"\t\t > ['', ',']\n"
]
}
],
"source": [
"v = m.insert_into_tree(tree, ('', '1997'))"
]
},
{
"cell_type": "code",
"execution_count": 65,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:57.517530Z",
"iopub.status.busy": "2024-01-18T17:19:57.517302Z",
"iopub.status.idle": "2024-01-18T17:19:57.919123Z",
"shell.execute_reply": "2024-01-18T17:19:57.918792Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 65,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"display_tree(tree)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"To make life simple, we define a wrapper function `nt_var()` that will convert a token to its corresponding nonterminal symbol."
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:57.920905Z",
"iopub.status.busy": "2024-01-18T17:19:57.920783Z",
"iopub.status.idle": "2024-01-18T17:19:57.922806Z",
"shell.execute_reply": "2024-01-18T17:19:57.922527Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class TreeMiner(TreeMiner):\n",
" def nt_var(self, var):\n",
" return var if is_nonterminal(var) else to_nonterminal(var)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Now, we need to apply a new definition to an entire grammar."
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:57.924261Z",
"iopub.status.busy": "2024-01-18T17:19:57.924152Z",
"iopub.status.idle": "2024-01-18T17:19:57.925967Z",
"shell.execute_reply": "2024-01-18T17:19:57.925682Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class TreeMiner(TreeMiner):\n",
" def apply_new_definition(self, tree, var, value):\n",
" nt_var = self.nt_var(var)\n",
" return self.insert_into_tree(tree, (nt_var, value))"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"This algorithm is implemented as `get_derivation_tree()`. "
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:57.927558Z",
"iopub.status.busy": "2024-01-18T17:19:57.927412Z",
"iopub.status.idle": "2024-01-18T17:19:57.930267Z",
"shell.execute_reply": "2024-01-18T17:19:57.929608Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class TreeMiner(TreeMiner):\n",
" def get_derivation_tree(self):\n",
" tree = (START_SYMBOL, [(self.my_input, [])])\n",
"\n",
" for var, value in self.my_assignments:\n",
" self.log(0, \"%s=%s\" % (var, repr(value)))\n",
" self.apply_new_definition(tree, var, value)\n",
" return tree"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The `TreeMiner` is used as follows:"
]
},
{
"cell_type": "code",
"execution_count": 69,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:57.932420Z",
"iopub.status.busy": "2024-01-18T17:19:57.932277Z",
"iopub.status.idle": "2024-01-18T17:19:57.937492Z",
"shell.execute_reply": "2024-01-18T17:19:57.937256Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" vehicle='1997,van,Ford,E350'\n",
"\t - Node: \t\t? (:'1997,van,Ford,E350')\n",
"\t\t -> [0] '1997,van,Ford,E350'\n",
"\t\t > ['']\n",
" year='1997'\n",
"\t - Node: \t\t? (:'1997')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'1997')\n",
"\t\t -> [0] '1997,van,Ford,E350'\n",
"\t\t > ['', ',van,Ford,E350']\n",
" kind='van'\n",
"\t - Node: \t\t? (:'van')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'van')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'van')\n",
"\t\t -> [0] '1997'\n",
"\t\t -> [1] ',van,Ford,E350'\n",
"\t\t > [',', '', ',Ford,E350']\n",
" company='Ford'\n",
"\t - Node: \t\t? (:'Ford')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'Ford')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'Ford')\n",
"\t\t -> [0] '1997'\n",
"\t\t -> [1] ','\n",
"\t\t -> [2] ''\n",
"\t - Node: \t\t? (:'Ford')\n",
"\t\t -> [0] 'van'\n",
"\t\t -> [3] ',Ford,E350'\n",
"\t\t > [',', '', ',E350']\n",
" model='E350'\n",
"\t - Node: \t\t? (:'E350')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'E350')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'E350')\n",
"\t\t -> [0] '1997'\n",
"\t\t -> [1] ','\n",
"\t\t -> [2] ''\n",
"\t - Node: \t\t? (:'E350')\n",
"\t\t -> [0] 'van'\n",
"\t\t -> [3] ','\n",
"\t\t -> [4] ''\n",
"\t - Node: \t\t? (:'E350')\n",
"\t\t -> [0] 'Ford'\n",
"\t\t -> [5] ',E350'\n",
"\t\t > [',', '']\n"
]
},
{
"data": {
"text/plain": [
"('',\n",
" [('',\n",
" [('', [['1997', []]]),\n",
" (',', []),\n",
" ('', [['van', []]]),\n",
" (',', []),\n",
" ('', [['Ford', []]]),\n",
" (',', []),\n",
" ('', [['E350', []]])])])"
]
},
"execution_count": 69,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"with Tracer(VEHICLES[0]) as tracer:\n",
" process_vehicle(tracer.my_input)\n",
"assignments = DefineTracker(tracer.my_input, tracer.trace).assignments()\n",
"dt = TreeMiner(tracer.my_input, assignments, log=True)\n",
"dt.tree"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The obtained derivation tree is as below."
]
},
{
"cell_type": "code",
"execution_count": 70,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:57.939192Z",
"iopub.status.busy": "2024-01-18T17:19:57.939041Z",
"iopub.status.idle": "2024-01-18T17:19:58.357396Z",
"shell.execute_reply": "2024-01-18T17:19:58.357041Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 70,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"display_tree(TreeMiner(tracer.my_input, assignments).tree)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Combining all the pieces:"
]
},
{
"cell_type": "code",
"execution_count": 71,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.359814Z",
"iopub.status.busy": "2024-01-18T17:19:58.359663Z",
"iopub.status.idle": "2024-01-18T17:19:58.367669Z",
"shell.execute_reply": "2024-01-18T17:19:58.367340Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1997,van,Ford,E350\n",
"vehicle = '1997,van,Ford,E350'\n",
"year = '1997'\n",
"kind = 'van'\n",
"company = 'Ford'\n",
"model = 'E350'\n",
"\n",
"2000,car,Mercury,Cougar\n",
"vehicle = '2000,car,Mercury,Cougar'\n",
"year = '2000'\n",
"kind = 'car'\n",
"company = 'Mercury'\n",
"model = 'Cougar'\n",
"\n",
"1999,car,Chevy,Venture\n",
"vehicle = '1999,car,Chevy,Venture'\n",
"year = '1999'\n",
"kind = 'car'\n",
"company = 'Chevy'\n",
"model = 'Venture'\n",
"\n"
]
}
],
"source": [
"trees = []\n",
"for vehicle in VEHICLES:\n",
" print(vehicle)\n",
" with Tracer(vehicle) as tracer:\n",
" process_vehicle(tracer.my_input)\n",
" assignments = DefineTracker(tracer.my_input, tracer.trace).assignments()\n",
" trees.append((tracer.my_input, assignments))\n",
" for var, val in assignments:\n",
" print(var + \" = \" + repr(val))\n",
" print()"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The corresponding derivation trees are below."
]
},
{
"cell_type": "code",
"execution_count": 72,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.369516Z",
"iopub.status.busy": "2024-01-18T17:19:58.369276Z",
"iopub.status.idle": "2024-01-18T17:19:58.372150Z",
"shell.execute_reply": "2024-01-18T17:19:58.371926Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1997,van,Ford,E350\n",
"2000,car,Mercury,Cougar\n",
"1999,car,Chevy,Venture\n"
]
}
],
"source": [
"csv_dt = []\n",
"for inputstr, assignments in trees:\n",
" print(inputstr)\n",
" dt = TreeMiner(inputstr, assignments)\n",
" csv_dt.append(dt)\n",
" display_tree(dt.tree)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Recovering Grammars from Derivation Trees\n",
"\n",
"We define a class `Miner` that can combine multiple derivation trees to produce the grammar. The initial grammar is empty."
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.373740Z",
"iopub.status.busy": "2024-01-18T17:19:58.373608Z",
"iopub.status.idle": "2024-01-18T17:19:58.375407Z",
"shell.execute_reply": "2024-01-18T17:19:58.375121Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class GrammarMiner:\n",
" def __init__(self):\n",
" self.grammar = {}"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The `tree_to_grammar()` method converts our derivation tree to a grammar by picking one node at a time, and adding it to the grammar. The node name becomes the key, and any list of children it has becomes another alternative for that key."
]
},
{
"cell_type": "code",
"execution_count": 74,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.377024Z",
"iopub.status.busy": "2024-01-18T17:19:58.376896Z",
"iopub.status.idle": "2024-01-18T17:19:58.379838Z",
"shell.execute_reply": "2024-01-18T17:19:58.379474Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class GrammarMiner(GrammarMiner):\n",
" def tree_to_grammar(self, tree):\n",
" node, children = tree\n",
" one_alt = [ck for ck, gc in children]\n",
" hsh = {node: [one_alt] if one_alt else []}\n",
" for child in children:\n",
" if not is_nonterminal(child[0]):\n",
" continue\n",
" chsh = self.tree_to_grammar(child)\n",
" for k in chsh:\n",
" if k not in hsh:\n",
" hsh[k] = chsh[k]\n",
" else:\n",
" hsh[k].extend(chsh[k])\n",
" return hsh"
]
},
{
"cell_type": "code",
"execution_count": 75,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.381919Z",
"iopub.status.busy": "2024-01-18T17:19:58.381737Z",
"iopub.status.idle": "2024-01-18T17:19:58.384699Z",
"shell.execute_reply": "2024-01-18T17:19:58.384364Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"{'': [['']],\n",
" '': [['', ',', '', ',', '', ',', '']],\n",
" '': [['1997']],\n",
" '': [['van']],\n",
" '': [['Ford']],\n",
" '': [['E350']]}"
]
},
"execution_count": 75,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"gm = GrammarMiner()\n",
"gm.tree_to_grammar(csv_dt[0].tree)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The grammar being generated here is `canonical`. We define a function `readable()` that takes in a canonical grammar and returns it in a readable form."
]
},
{
"cell_type": "code",
"execution_count": 76,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.386567Z",
"iopub.status.busy": "2024-01-18T17:19:58.386432Z",
"iopub.status.idle": "2024-01-18T17:19:58.388532Z",
"shell.execute_reply": "2024-01-18T17:19:58.388258Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def readable(grammar):\n",
" def readable_rule(rule):\n",
" return ''.join(rule)\n",
"\n",
" return {k: list(set(readable_rule(a) for a in grammar[k]))\n",
" for k in grammar}"
]
},
{
"cell_type": "code",
"execution_count": 77,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.389987Z",
"iopub.status.busy": "2024-01-18T17:19:58.389888Z",
"iopub.status.idle": "2024-01-18T17:19:58.400955Z",
"shell.execute_reply": "2024-01-18T17:19:58.400691Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"start\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"vehicle\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"year\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"kind\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"company\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"model\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"syntax_diagram(readable(gm.tree_to_grammar(csv_dt[0].tree)))"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The `add_tree()` method gets a combined list of non-terminals from current grammar, and the tree to be added to the grammar, and updates the definitions of each non-terminal."
]
},
{
"cell_type": "code",
"execution_count": 78,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.402661Z",
"iopub.status.busy": "2024-01-18T17:19:58.402507Z",
"iopub.status.idle": "2024-01-18T17:19:58.404217Z",
"shell.execute_reply": "2024-01-18T17:19:58.403948Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import itertools"
]
},
{
"cell_type": "code",
"execution_count": 79,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.405650Z",
"iopub.status.busy": "2024-01-18T17:19:58.405542Z",
"iopub.status.idle": "2024-01-18T17:19:58.407777Z",
"shell.execute_reply": "2024-01-18T17:19:58.407511Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class GrammarMiner(GrammarMiner):\n",
" def add_tree(self, t):\n",
" t_grammar = self.tree_to_grammar(t.tree)\n",
" self.grammar = {\n",
" key: self.grammar.get(key, []) + t_grammar.get(key, [])\n",
" for key in itertools.chain(self.grammar.keys(), t_grammar.keys())\n",
" }"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The `add_tree()` is used as follows:"
]
},
{
"cell_type": "code",
"execution_count": 80,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.409505Z",
"iopub.status.busy": "2024-01-18T17:19:58.409382Z",
"iopub.status.idle": "2024-01-18T17:19:58.411301Z",
"shell.execute_reply": "2024-01-18T17:19:58.410980Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"inventory_grammar_miner = GrammarMiner()\n",
"for dt in csv_dt:\n",
" inventory_grammar_miner.add_tree(dt)"
]
},
{
"cell_type": "code",
"execution_count": 81,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.413262Z",
"iopub.status.busy": "2024-01-18T17:19:58.413133Z",
"iopub.status.idle": "2024-01-18T17:19:58.421756Z",
"shell.execute_reply": "2024-01-18T17:19:58.421511Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"start\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"vehicle\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"year\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"kind\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"company\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"model\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"syntax_diagram(readable(inventory_grammar_miner.grammar))"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Given execution traces from various inputs, one can define `update_grammar()` to obtain the complete grammar from the traces."
]
},
{
"cell_type": "code",
"execution_count": 82,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.423498Z",
"iopub.status.busy": "2024-01-18T17:19:58.423256Z",
"iopub.status.idle": "2024-01-18T17:19:58.425929Z",
"shell.execute_reply": "2024-01-18T17:19:58.425619Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class GrammarMiner(GrammarMiner):\n",
" def update_grammar(self, inputstr, trace):\n",
" at = self.create_tracker(inputstr, trace)\n",
" dt = self.create_tree_miner(inputstr, at.assignments())\n",
" self.add_tree(dt)\n",
" return self.grammar\n",
"\n",
" def create_tracker(self, *args):\n",
" return DefineTracker(*args)\n",
"\n",
" def create_tree_miner(self, *args):\n",
" return TreeMiner(*args)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The complete grammar recovery is implemented in `recover_grammar()`."
]
},
{
"cell_type": "code",
"execution_count": 83,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.427487Z",
"iopub.status.busy": "2024-01-18T17:19:58.427366Z",
"iopub.status.idle": "2024-01-18T17:19:58.429935Z",
"shell.execute_reply": "2024-01-18T17:19:58.429639Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def recover_grammar(fn: Callable, inputs: Iterable[str], \n",
" **kwargs: Any) -> Grammar:\n",
" miner = GrammarMiner()\n",
"\n",
" for inputstr in inputs:\n",
" with Tracer(inputstr, **kwargs) as tracer:\n",
" fn(tracer.my_input)\n",
" miner.update_grammar(tracer.my_input, tracer.trace)\n",
"\n",
" return readable(miner.grammar)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Note that the grammar could have been retrieved directly from the tracker, without the intermediate derivation tree stage. However, going through the derivation tree allows one to inspect the inputs being fragmented and verify that it happens correctly."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### Example 1. Recovering the Inventory Grammar"
]
},
{
"cell_type": "code",
"execution_count": 84,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.431570Z",
"iopub.status.busy": "2024-01-18T17:19:58.431467Z",
"iopub.status.idle": "2024-01-18T17:19:58.435496Z",
"shell.execute_reply": "2024-01-18T17:19:58.435197Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"inventory_grammar = recover_grammar(process_vehicle, VEHICLES)"
]
},
{
"cell_type": "code",
"execution_count": 85,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.436921Z",
"iopub.status.busy": "2024-01-18T17:19:58.436837Z",
"iopub.status.idle": "2024-01-18T17:19:58.439032Z",
"shell.execute_reply": "2024-01-18T17:19:58.438778Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"{'': [''],\n",
" '': [',,,'],\n",
" '': ['2000', '1997', '1999'],\n",
" '': ['car', 'van'],\n",
" '': ['Mercury', 'Chevy', 'Ford'],\n",
" '': ['E350', 'Cougar', 'Venture']}"
]
},
"execution_count": 85,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"inventory_grammar"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### Example 2. Recovering URL Grammar"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Our algorithm is robust enough to recover grammar from real world programs. For example, the `urlparse` function in the Python `urlib` module accepts the following sample URLs."
]
},
{
"cell_type": "code",
"execution_count": 86,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.440492Z",
"iopub.status.busy": "2024-01-18T17:19:58.440415Z",
"iopub.status.idle": "2024-01-18T17:19:58.442141Z",
"shell.execute_reply": "2024-01-18T17:19:58.441876Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"URLS = [\n",
" 'http://user:pass@www.google.com:80/?q=path#ref',\n",
" 'https://www.cispa.saarland:80/',\n",
" 'http://www.fuzzingbook.org/#News',\n",
"]"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The urllib caches its intermediate results for faster access. Hence, we need to disable it using `clear_cache()` after every invocation."
]
},
{
"cell_type": "code",
"execution_count": 87,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.443803Z",
"iopub.status.busy": "2024-01-18T17:19:58.443698Z",
"iopub.status.idle": "2024-01-18T17:19:58.445659Z",
"shell.execute_reply": "2024-01-18T17:19:58.445195Z"
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from urllib.parse import urlparse, clear_cache # type: ignore"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"We use the sample URLs to recover grammar as follows. The `urlparse` function tends to cache its previous parsing results. Hence, we define a new method `url_parse()` that clears the cache before each call."
]
},
{
"cell_type": "code",
"execution_count": 88,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.447293Z",
"iopub.status.busy": "2024-01-18T17:19:58.447203Z",
"iopub.status.idle": "2024-01-18T17:19:58.449050Z",
"shell.execute_reply": "2024-01-18T17:19:58.448762Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def url_parse(url):\n",
" clear_cache()\n",
" urlparse(url)"
]
},
{
"cell_type": "code",
"execution_count": 89,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.450416Z",
"iopub.status.busy": "2024-01-18T17:19:58.450309Z",
"iopub.status.idle": "2024-01-18T17:19:58.571121Z",
"shell.execute_reply": "2024-01-18T17:19:58.570852Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"http://user:pass@www.google.com:80/?q=path#ref\n",
"url = 'http://user:pass@www.google.com:80/?q=path#ref'\n",
"scheme = 'http'\n",
"netloc = 'user:pass@www.google.com:80'\n",
"fragment = 'ref'\n",
"query = 'q=path'\n",
"\n",
"https://www.cispa.saarland:80/\n",
"url = 'https://www.cispa.saarland:80/'\n",
"scheme = 'https'\n",
"netloc = 'www.cispa.saarland:80'\n",
"\n",
"http://www.fuzzingbook.org/#News\n",
"url = 'http://www.fuzzingbook.org/#News'\n",
"scheme = 'http'\n",
"netloc = 'www.fuzzingbook.org'\n",
"fragment = 'News'\n",
"\n",
"http://user:pass@www.google.com:80/?q=path#ref\n",
"https://www.cispa.saarland:80/\n",
"http://www.fuzzingbook.org/#News\n"
]
}
],
"source": [
"trees = []\n",
"for url in URLS:\n",
" print(url)\n",
" with Tracer(url) as tracer:\n",
" url_parse(tracer.my_input)\n",
" assignments = DefineTracker(tracer.my_input, tracer.trace).assignments()\n",
" trees.append((tracer.my_input, assignments))\n",
" for var, val in assignments:\n",
" print(var + \" = \" + repr(val))\n",
" print()\n",
"\n",
"\n",
"url_dt = []\n",
"for inputstr, assignments in trees:\n",
" print(inputstr)\n",
" dt = TreeMiner(inputstr, assignments)\n",
" url_dt.append(dt)\n",
" display_tree(dt.tree)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Let us use `url_parse()` to recover the grammar:"
]
},
{
"cell_type": "code",
"execution_count": 90,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.572786Z",
"iopub.status.busy": "2024-01-18T17:19:58.572672Z",
"iopub.status.idle": "2024-01-18T17:19:58.680929Z",
"shell.execute_reply": "2024-01-18T17:19:58.680621Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"url_grammar = recover_grammar(url_parse, URLS, files=['urllib/parse.py'])"
]
},
{
"cell_type": "code",
"execution_count": 91,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.682698Z",
"iopub.status.busy": "2024-01-18T17:19:58.682602Z",
"iopub.status.idle": "2024-01-18T17:19:58.691799Z",
"shell.execute_reply": "2024-01-18T17:19:58.691473Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"start\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"url\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"scheme\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"netloc\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"query\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"fragment\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"syntax_diagram(url_grammar)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The recovered grammar describes the URL format reasonably well."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Fuzzing"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"We can now use our recovered grammar for fuzzing as follows.\n",
"\n",
"First, the inventory grammar."
]
},
{
"cell_type": "code",
"execution_count": 92,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.693698Z",
"iopub.status.busy": "2024-01-18T17:19:58.693484Z",
"iopub.status.idle": "2024-01-18T17:19:58.696580Z",
"shell.execute_reply": "2024-01-18T17:19:58.696313Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1999,car,Mercury,E350\n",
"1997,car,Chevy,Cougar\n",
"1999,van,Mercury,Venture\n",
"2000,car,Ford,Venture\n",
"1997,car,Mercury,E350\n",
"1997,car,Mercury,Cougar\n",
"1999,car,Chevy,E350\n",
"1999,car,Chevy,E350\n",
"1999,car,Mercury,Cougar\n",
"2000,car,Chevy,E350\n"
]
}
],
"source": [
"f = GrammarFuzzer(inventory_grammar)\n",
"for _ in range(10):\n",
" print(f.fuzz())"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Next, the URL grammar."
]
},
{
"cell_type": "code",
"execution_count": 93,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.698282Z",
"iopub.status.busy": "2024-01-18T17:19:58.698193Z",
"iopub.status.idle": "2024-01-18T17:19:58.700866Z",
"shell.execute_reply": "2024-01-18T17:19:58.700634Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"http://user:pass@www.google.com:80/#News\n",
"http://user:pass@www.google.com:80/\n",
"http://www.cispa.saarland:80/\n",
"https://www.fuzzingbook.org/\n",
"https://www.cispa.saarland:80/?q=path#ref\n",
"http://www.cispa.saarland:80/\n",
"http://www.cispa.saarland:80/?q=path#News\n",
"https://user:pass@www.google.com:80/#ref\n",
"https://user:pass@www.google.com:80/\n",
"https://www.cispa.saarland:80/#News\n"
]
}
],
"source": [
"f = GrammarFuzzer(url_grammar)\n",
"for _ in range(10):\n",
" print(f.fuzz())"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"What this means is that we can now take a program and a few samples, extract its grammar, and then use this very grammar for fuzzing. Now that's quite an opportunity!"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Problems with the Simple Miner"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"One of the problems with our simple grammar miner is the assumption that the values assigned to variables are stable. Unfortunately, that may not hold true in all cases. For example, here is a URL with a slightly different format."
]
},
{
"cell_type": "code",
"execution_count": 94,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.702569Z",
"iopub.status.busy": "2024-01-18T17:19:58.702490Z",
"iopub.status.idle": "2024-01-18T17:19:58.704073Z",
"shell.execute_reply": "2024-01-18T17:19:58.703829Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"URLS_X = URLS + ['ftp://freebsd.org/releases/5.8']"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The grammar generated from this set of samples is not as nice as what we got earlier"
]
},
{
"cell_type": "code",
"execution_count": 95,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.705512Z",
"iopub.status.busy": "2024-01-18T17:19:58.705433Z",
"iopub.status.idle": "2024-01-18T17:19:58.842925Z",
"shell.execute_reply": "2024-01-18T17:19:58.842579Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"url_grammar = recover_grammar(url_parse, URLS_X, files=['urllib/parse.py'])"
]
},
{
"cell_type": "code",
"execution_count": 96,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.845059Z",
"iopub.status.busy": "2024-01-18T17:19:58.844906Z",
"iopub.status.idle": "2024-01-18T17:19:58.856361Z",
"shell.execute_reply": "2024-01-18T17:19:58.856067Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"start\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"url\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"scheme\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"netloc\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"query\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"fragment\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"syntax_diagram(url_grammar)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Clearly, something has gone wrong.\n",
"\n",
"To investigate why the `url` definition has gone wrong, let us inspect the trace for the URL."
]
},
{
"cell_type": "code",
"execution_count": 97,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.858126Z",
"iopub.status.busy": "2024-01-18T17:19:58.858044Z",
"iopub.status.idle": "2024-01-18T17:19:58.886184Z",
"shell.execute_reply": "2024-01-18T17:19:58.885767Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0 372 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': ''},)\n",
"1 392 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': ''},)\n",
"5 124 ({'arg': ''},)\n",
"6 121 ({'arg': ''},)\n",
"7 126 ({'arg': ''},)\n",
"8 127 ({'arg': ''},)\n",
"10 393 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': ''},)\n",
"11 437 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': ''},)\n",
"12 458 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': ''},)\n",
"16 124 ({'arg': ''},)\n",
"17 121 ({'arg': ''},)\n",
"18 126 ({'arg': ''},)\n",
"19 127 ({'arg': ''},)\n",
"21 460 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': ''},)\n",
"22 461 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\t'},)\n",
"23 462 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\t'},)\n",
"24 460 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\t'},)\n",
"25 461 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\r'},)\n",
"26 462 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\r'},)\n",
"27 460 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\r'},)\n",
"28 461 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n'},)\n",
"29 462 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n'},)\n",
"30 460 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n'},)\n",
"31 464 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n'},)\n",
"32 465 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n'},)\n",
"33 466 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n'},)\n",
"34 467 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n'},)\n",
"35 469 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n'},)\n",
"36 471 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n'},)\n",
"37 472 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n', 'netloc': '', 'query': '', 'fragment': ''},)\n",
"38 473 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n', 'netloc': '', 'query': '', 'fragment': ''},)\n",
"39 474 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n', 'netloc': '', 'query': '', 'fragment': ''},)\n",
"40 475 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n', 'netloc': '', 'query': '', 'fragment': '', 'c': 'h'},)\n",
"41 474 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n', 'netloc': '', 'query': '', 'fragment': '', 'c': 'h'},)\n",
"42 475 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n', 'netloc': '', 'query': '', 'fragment': '', 'c': 't'},)\n",
"43 474 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n', 'netloc': '', 'query': '', 'fragment': '', 'c': 't'},)\n",
"44 475 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n', 'netloc': '', 'query': '', 'fragment': '', 'c': 't'},)\n",
"45 474 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n', 'netloc': '', 'query': '', 'fragment': '', 'c': 't'},)\n",
"46 475 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n', 'netloc': '', 'query': '', 'fragment': '', 'c': 'p'},)\n",
"47 474 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n', 'netloc': '', 'query': '', 'fragment': '', 'c': 'p'},)\n",
"48 478 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': '', 'b': '\\n', 'netloc': '', 'query': '', 'fragment': '', 'c': 'p'},)\n",
"49 480 ({'url': '//user:pass@www.google.com:80/?q=path#ref', 'scheme': 'http', 'b': '\\n', 'netloc': '', 'query': '', 'fragment': '', 'c': 'p'},)\n",
"50 481 ({'url': '//user:pass@www.google.com:80/?q=path#ref', 'scheme': 'http', 'b': '\\n', 'netloc': '', 'query': '', 'fragment': '', 'c': 'p'},)\n",
"51 411 ({'url': '//user:pass@www.google.com:80/?q=path#ref'},)\n",
"52 412 ({'url': '//user:pass@www.google.com:80/?q=path#ref'},)\n",
"53 413 ({'url': '//user:pass@www.google.com:80/?q=path#ref'},)\n",
"54 414 ({'url': '//user:pass@www.google.com:80/?q=path#ref', 'c': '/'},)\n",
"55 415 ({'url': '//user:pass@www.google.com:80/?q=path#ref', 'c': '/'},)\n",
"56 416 ({'url': '//user:pass@www.google.com:80/?q=path#ref', 'c': '/'},)\n",
"57 413 ({'url': '//user:pass@www.google.com:80/?q=path#ref', 'c': '/'},)\n",
"58 414 ({'url': '//user:pass@www.google.com:80/?q=path#ref', 'c': '?'},)\n",
"59 415 ({'url': '//user:pass@www.google.com:80/?q=path#ref', 'c': '?'},)\n",
"60 416 ({'url': '//user:pass@www.google.com:80/?q=path#ref', 'c': '?'},)\n",
"61 413 ({'url': '//user:pass@www.google.com:80/?q=path#ref', 'c': '?'},)\n",
"62 414 ({'url': '//user:pass@www.google.com:80/?q=path#ref', 'c': '#'},)\n",
"63 415 ({'url': '//user:pass@www.google.com:80/?q=path#ref', 'c': '#'},)\n",
"64 416 ({'url': '//user:pass@www.google.com:80/?q=path#ref', 'c': '#'},)\n",
"65 413 ({'url': '//user:pass@www.google.com:80/?q=path#ref', 'c': '#'},)\n",
"66 417 ({'url': '//user:pass@www.google.com:80/?q=path#ref', 'c': '#'},)\n",
"68 482 ({'url': '/?q=path#ref', 'scheme': 'http', 'b': '\\n', 'netloc': 'user:pass@www.google.com:80', 'query': '', 'fragment': '', 'c': 'p'},)\n",
"69 483 ({'url': '/?q=path#ref', 'scheme': 'http', 'b': '\\n', 'netloc': 'user:pass@www.google.com:80', 'query': '', 'fragment': '', 'c': 'p'},)\n",
"70 482 ({'url': '/?q=path#ref', 'scheme': 'http', 'b': '\\n', 'netloc': 'user:pass@www.google.com:80', 'query': '', 'fragment': '', 'c': 'p'},)\n",
"71 485 ({'url': '/?q=path#ref', 'scheme': 'http', 'b': '\\n', 'netloc': 'user:pass@www.google.com:80', 'query': '', 'fragment': '', 'c': 'p'},)\n",
"72 486 ({'url': '/?q=path#ref', 'scheme': 'http', 'b': '\\n', 'netloc': 'user:pass@www.google.com:80', 'query': '', 'fragment': '', 'c': 'p'},)\n",
"73 487 ({'url': '/?q=path', 'scheme': 'http', 'b': '\\n', 'netloc': 'user:pass@www.google.com:80', 'query': '', 'fragment': 'ref', 'c': 'p'},)\n",
"74 488 ({'url': '/?q=path', 'scheme': 'http', 'b': '\\n', 'netloc': 'user:pass@www.google.com:80', 'query': '', 'fragment': 'ref', 'c': 'p'},)\n",
"75 489 ({'url': '/', 'scheme': 'http', 'b': '\\n', 'netloc': 'user:pass@www.google.com:80', 'query': 'q=path', 'fragment': 'ref', 'c': 'p'},)\n",
"76 419 ({'netloc': 'user:pass@www.google.com:80'},)\n",
"77 420 ({'netloc': 'user:pass@www.google.com:80'},)\n",
"78 421 ({'netloc': 'user:pass@www.google.com:80'},)\n",
"80 490 ({'url': '/', 'scheme': 'http', 'b': '\\n', 'netloc': 'user:pass@www.google.com:80', 'query': 'q=path', 'fragment': 'ref', 'c': 'p'},)\n",
"84 491 ({'url': '/', 'scheme': 'http', 'b': '\\n', 'netloc': 'user:pass@www.google.com:80', 'query': 'q=path', 'fragment': 'ref', 'c': 'p'},)\n",
"85 492 ({'url': '/', 'scheme': 'http', 'b': '\\n', 'netloc': 'user:pass@www.google.com:80', 'query': 'q=path', 'fragment': 'ref', 'c': 'p'},)\n",
"90 394 ({'url': 'http://user:pass@www.google.com:80/?q=path#ref', 'scheme': ''},)\n",
"91 395 ({'url': '/', 'scheme': 'http', 'netloc': 'user:pass@www.google.com:80', 'query': 'q=path', 'fragment': 'ref'},)\n",
"92 398 ({'url': '/', 'scheme': 'http', 'netloc': 'user:pass@www.google.com:80', 'query': 'q=path', 'fragment': 'ref'},)\n",
"93 399 ({'url': '/', 'scheme': 'http', 'netloc': 'user:pass@www.google.com:80', 'query': 'q=path', 'fragment': 'ref', 'params': ''},)\n",
"97 400 ({'url': '/', 'scheme': 'http', 'netloc': 'user:pass@www.google.com:80', 'query': 'q=path', 'fragment': 'ref', 'params': ''},)\n"
]
}
],
"source": [
"clear_cache()\n",
"with Tracer(URLS_X[0]) as tracer:\n",
" urlparse(tracer.my_input)\n",
"for i, t in enumerate(tracer.trace):\n",
" if t[0] in {'call', 'line'} and 'parse.py' in str(t[2]) and t[3]:\n",
" print(i, t[2]._t()[1], t[3:])"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Notice how the value of `url` changes as the parsing progresses? This violates our assumption that the value assigned to a variable is stable. We next look at how this limitation can be removed."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Grammar Miner with Reassignment"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"One way to uniquely identify different variables is to annotate them with *line numbers* both when they are defined and also when their value changes. Consider the code fragment below"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Tracking variable assignment locations"
]
},
{
"cell_type": "code",
"execution_count": 98,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.888121Z",
"iopub.status.busy": "2024-01-18T17:19:58.888031Z",
"iopub.status.idle": "2024-01-18T17:19:58.889792Z",
"shell.execute_reply": "2024-01-18T17:19:58.889422Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def C(cp_1):\n",
" c_2 = cp_1 + '@2'\n",
" c_3 = c_2 + '@3'\n",
" return c_3"
]
},
{
"cell_type": "code",
"execution_count": 99,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.891450Z",
"iopub.status.busy": "2024-01-18T17:19:58.891362Z",
"iopub.status.idle": "2024-01-18T17:19:58.893276Z",
"shell.execute_reply": "2024-01-18T17:19:58.892870Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def B(bp_7):\n",
" b_8 = bp_7 + '@8'\n",
" return C(b_8)"
]
},
{
"cell_type": "code",
"execution_count": 100,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.895100Z",
"iopub.status.busy": "2024-01-18T17:19:58.895015Z",
"iopub.status.idle": "2024-01-18T17:19:58.897070Z",
"shell.execute_reply": "2024-01-18T17:19:58.896671Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def A(ap_12):\n",
" a_13 = ap_12 + '@13'\n",
" a_14 = B(a_13) + '@14'\n",
" a_14 = a_14 + '@15'\n",
" a_13 = a_14 + '@16'\n",
" a_14 = B(a_13) + '@17'\n",
" a_14 = B(a_13) + '@18'"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Notice how all variables are either named corresponding to either where they are defined, or the value is annotated to indicate that it was changed.\n",
"\n",
"Let us run this under the trace."
]
},
{
"cell_type": "code",
"execution_count": 101,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:58.898636Z",
"iopub.status.busy": "2024-01-18T17:19:58.898562Z",
"iopub.status.idle": "2024-01-18T17:19:59.004165Z",
"shell.execute_reply": "2024-01-18T17:19:59.003805Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"call 1:A {'ap_12': '____'}\n",
"line 2:A {'ap_12': '____'}\n",
"line 3:A {'ap_12': '____', 'a_13': '____@13'}\n",
"call 1:B {'bp_7': '____@13'}\n",
"line 2:B {'bp_7': '____@13'}\n",
"line 3:B {'bp_7': '____@13', 'b_8': '____@13@8'}\n",
"call 1:C {'cp_1': '____@13@8'}\n",
"line 2:C {'cp_1': '____@13@8'}\n",
"line 3:C {'cp_1': '____@13@8', 'c_2': '____@13@8@2'}\n",
"line 4:C {'cp_1': '____@13@8', 'c_2': '____@13@8@2', 'c_3': '____@13@8@2@3'}\n",
"return 4:C {'cp_1': '____@13@8', 'c_2': '____@13@8@2', 'c_3': '____@13@8@2@3'}\n",
"return 3:B {'bp_7': '____@13', 'b_8': '____@13@8'}\n",
"line 4:A {'ap_12': '____', 'a_13': '____@13', 'a_14': '____@13@8@2@3@14'}\n",
"line 5:A {'ap_12': '____', 'a_13': '____@13', 'a_14': '____@13@8@2@3@14@15'}\n",
"line 6:A {'ap_12': '____', 'a_13': '____@13@8@2@3@14@15@16', 'a_14': '____@13@8@2@3@14@15'}\n",
"call 1:B {'bp_7': '____@13@8@2@3@14@15@16'}\n",
"line 2:B {'bp_7': '____@13@8@2@3@14@15@16'}\n",
"line 3:B {'bp_7': '____@13@8@2@3@14@15@16', 'b_8': '____@13@8@2@3@14@15@16@8'}\n",
"call 1:C {'cp_1': '____@13@8@2@3@14@15@16@8'}\n",
"line 2:C {'cp_1': '____@13@8@2@3@14@15@16@8'}\n",
"line 3:C {'cp_1': '____@13@8@2@3@14@15@16@8', 'c_2': '____@13@8@2@3@14@15@16@8@2'}\n",
"line 4:C {'cp_1': '____@13@8@2@3@14@15@16@8', 'c_2': '____@13@8@2@3@14@15@16@8@2', 'c_3': '____@13@8@2@3@14@15@16@8@2@3'}\n",
"return 4:C {'cp_1': '____@13@8@2@3@14@15@16@8', 'c_2': '____@13@8@2@3@14@15@16@8@2', 'c_3': '____@13@8@2@3@14@15@16@8@2@3'}\n",
"return 3:B {'bp_7': '____@13@8@2@3@14@15@16', 'b_8': '____@13@8@2@3@14@15@16@8'}\n",
"line 7:A {'ap_12': '____', 'a_13': '____@13@8@2@3@14@15@16', 'a_14': '____@13@8@2@3@14@15@16@8@2@3@17'}\n",
"call 1:B {'bp_7': '____@13@8@2@3@14@15@16'}\n",
"line 2:B {'bp_7': '____@13@8@2@3@14@15@16'}\n",
"line 3:B {'bp_7': '____@13@8@2@3@14@15@16', 'b_8': '____@13@8@2@3@14@15@16@8'}\n",
"call 1:C {'cp_1': '____@13@8@2@3@14@15@16@8'}\n",
"line 2:C {'cp_1': '____@13@8@2@3@14@15@16@8'}\n",
"line 3:C {'cp_1': '____@13@8@2@3@14@15@16@8', 'c_2': '____@13@8@2@3@14@15@16@8@2'}\n",
"line 4:C {'cp_1': '____@13@8@2@3@14@15@16@8', 'c_2': '____@13@8@2@3@14@15@16@8@2', 'c_3': '____@13@8@2@3@14@15@16@8@2@3'}\n",
"return 4:C {'cp_1': '____@13@8@2@3@14@15@16@8', 'c_2': '____@13@8@2@3@14@15@16@8@2', 'c_3': '____@13@8@2@3@14@15@16@8@2@3'}\n",
"return 3:B {'bp_7': '____@13@8@2@3@14@15@16', 'b_8': '____@13@8@2@3@14@15@16@8'}\n",
"return 7:A {'ap_12': '____', 'a_13': '____@13@8@2@3@14@15@16', 'a_14': '____@13@8@2@3@14@15@16@8@2@3@18'}\n",
"call 102:__exit__ {}\n",
"line 105:__exit__ {}\n"
]
}
],
"source": [
"with Tracer('____') as tracer:\n",
" A(tracer.my_input)\n",
"\n",
"for t in tracer.trace:\n",
" print(t[0], \"%d:%s\" % (t[2].line_no, t[2].method), t[3])"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Each variable was referenced first as follows:\n",
"\n",
"* `cp_1` -- *call* `1:C`\n",
"* `c_2` -- *line* `3:C` (but the previous event was *line* `2:C`)\n",
"* `c_3` -- *line* `4:C` (but the previous event was *line* `3:C`)\n",
"* `bp_7` -- *call* `7:B`\n",
"* `b_8` -- *line* `9:B` (but the previous event was *line* `8:B`)\n",
"* `ap_12` -- *call* `12:A`\n",
"* `a_13` -- *line* `14:A` (but the previous event was *line* `13:A`)\n",
"* `a_14` -- *line* `15:A` (the previous event was *return* `9:B`. However, the previous event in `A()` was *line* `14:A`)\n",
"* reassign `a_14` at *15* -- *line* `16:A` (the previous event was *line* `15:A`)\n",
"* reassign `a_13` at *16* -- *line* `17:A` (the previous event was *line* `16:A`)\n",
"* reassign `a_14` at *17* -- *return* `17:A` (the previous event in `A()` was *line* `17:A`)\n",
"* reassign `a_14` at *18* -- *return* `18:A` (the previous event in `A()` was *line* `18:A`)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"So, our observations are that, if it is a call, the current location is the right one for any new variables being defined. On the other hand, if the variable being referenced for the first time (or reassigned a new value), then the right location to consider is the previous location *in the same method invocation*. Next, let us see how we can incorporate this information into variable naming."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Next, we need a way to track the individual method calls as they are being made. For this we define the class `CallStack`. Each method invocation gets a separate identifier, and when the method call is over, the identifier is reset."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### CallStack"
]
},
{
"cell_type": "code",
"execution_count": 102,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.006198Z",
"iopub.status.busy": "2024-01-18T17:19:59.006073Z",
"iopub.status.idle": "2024-01-18T17:19:59.008910Z",
"shell.execute_reply": "2024-01-18T17:19:59.008593Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class CallStack:\n",
" def __init__(self, **kwargs):\n",
" self.options(kwargs)\n",
" self.method_id = (START_SYMBOL, 0)\n",
" self.method_register = 0\n",
" self.mstack = [self.method_id]\n",
"\n",
" def enter(self, method):\n",
" self.method_register += 1\n",
" self.method_id = (method, self.method_register)\n",
" self.log('call', \"%s%s\" % (self.indent(), str(self)))\n",
" self.mstack.append(self.method_id)\n",
"\n",
" def leave(self):\n",
" self.mstack.pop()\n",
" self.log('return', \"%s%s\" % (self.indent(), str(self)))\n",
" self.method_id = self.mstack[-1]"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"A few extra functions to make life simpler."
]
},
{
"cell_type": "code",
"execution_count": 103,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.010983Z",
"iopub.status.busy": "2024-01-18T17:19:59.010667Z",
"iopub.status.idle": "2024-01-18T17:19:59.014023Z",
"shell.execute_reply": "2024-01-18T17:19:59.013489Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class CallStack(CallStack):\n",
" def options(self, kwargs):\n",
" self.log = log_event if kwargs.get('log') else lambda _evt, _var: None\n",
"\n",
" def indent(self):\n",
" return len(self.mstack) * \"\\t\"\n",
"\n",
" def at(self, n):\n",
" return self.mstack[n]\n",
"\n",
" def __len__(self):\n",
" return len(mstack) - 1\n",
"\n",
" def __str__(self):\n",
" return \"%s:%d\" % self.method_id\n",
"\n",
" def __repr__(self):\n",
" return repr(self.method_id)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"We also define a convenience method to display a given stack."
]
},
{
"cell_type": "code",
"execution_count": 104,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.015903Z",
"iopub.status.busy": "2024-01-18T17:19:59.015814Z",
"iopub.status.idle": "2024-01-18T17:19:59.018205Z",
"shell.execute_reply": "2024-01-18T17:19:59.017908Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def display_stack(istack):\n",
" def stack_to_tree(stack):\n",
" current, *rest = stack\n",
" if not rest:\n",
" return (repr(current), [])\n",
" return (repr(current), [stack_to_tree(rest)])\n",
" display_tree(stack_to_tree(istack.mstack), graph_attr=lr_graph)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Here is how we can use the `CallStack`."
]
},
{
"cell_type": "code",
"execution_count": 105,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.020128Z",
"iopub.status.busy": "2024-01-18T17:19:59.019900Z",
"iopub.status.idle": "2024-01-18T17:19:59.022689Z",
"shell.execute_reply": "2024-01-18T17:19:59.022358Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"('', 0)"
]
},
"execution_count": 105,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"cs = CallStack()\n",
"display_stack(cs)\n",
"cs"
]
},
{
"cell_type": "code",
"execution_count": 106,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.024625Z",
"iopub.status.busy": "2024-01-18T17:19:59.024468Z",
"iopub.status.idle": "2024-01-18T17:19:59.027057Z",
"shell.execute_reply": "2024-01-18T17:19:59.026699Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"('hello', 1)"
]
},
"execution_count": 106,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"cs.enter('hello')\n",
"display_stack(cs)\n",
"cs"
]
},
{
"cell_type": "code",
"execution_count": 107,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.029109Z",
"iopub.status.busy": "2024-01-18T17:19:59.028912Z",
"iopub.status.idle": "2024-01-18T17:19:59.031760Z",
"shell.execute_reply": "2024-01-18T17:19:59.031451Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"('world', 2)"
]
},
"execution_count": 107,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"cs.enter('world')\n",
"display_stack(cs)\n",
"cs"
]
},
{
"cell_type": "code",
"execution_count": 108,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.033438Z",
"iopub.status.busy": "2024-01-18T17:19:59.033307Z",
"iopub.status.idle": "2024-01-18T17:19:59.035811Z",
"shell.execute_reply": "2024-01-18T17:19:59.035468Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"('hello', 1)"
]
},
"execution_count": 108,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"cs.leave()\n",
"display_stack(cs)\n",
"cs"
]
},
{
"cell_type": "code",
"execution_count": 109,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.037668Z",
"iopub.status.busy": "2024-01-18T17:19:59.037525Z",
"iopub.status.idle": "2024-01-18T17:19:59.040053Z",
"shell.execute_reply": "2024-01-18T17:19:59.039707Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"('world', 3)"
]
},
"execution_count": 109,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"cs.enter('world')\n",
"display_stack(cs)\n",
"cs"
]
},
{
"cell_type": "code",
"execution_count": 110,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.041766Z",
"iopub.status.busy": "2024-01-18T17:19:59.041654Z",
"iopub.status.idle": "2024-01-18T17:19:59.044026Z",
"shell.execute_reply": "2024-01-18T17:19:59.043680Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"('hello', 1)"
]
},
"execution_count": 110,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"cs.leave()\n",
"display_stack(cs)\n",
"cs"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"In order to account for variable reassignments, we need to have a more intelligent data structure than a dictionary for storing variables. We first define a simple interface `Vars`. It acts as a container for variables, and is instantiated at `my_assignments`."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Vars"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The `Vars` stores references to variables as they occur during parsing in its internal dictionary `defs`. We initialize the dictionary with the original string."
]
},
{
"cell_type": "code",
"execution_count": 111,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.045922Z",
"iopub.status.busy": "2024-01-18T17:19:59.045805Z",
"iopub.status.idle": "2024-01-18T17:19:59.047812Z",
"shell.execute_reply": "2024-01-18T17:19:59.047456Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class Vars:\n",
" def __init__(self, original):\n",
" self.defs = {}\n",
" self.my_input = original"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The dictionary needs two methods: `update()` that takes a set of key-value pairs to update itself, and `_set_kv()` that updates a particular key-value pair."
]
},
{
"cell_type": "code",
"execution_count": 112,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.049564Z",
"iopub.status.busy": "2024-01-18T17:19:59.049442Z",
"iopub.status.idle": "2024-01-18T17:19:59.051636Z",
"shell.execute_reply": "2024-01-18T17:19:59.051335Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class Vars(Vars):\n",
" def _set_kv(self, k, v):\n",
" self.defs[k] = v\n",
"\n",
" def __setitem__(self, k, v):\n",
" self._set_kv(k, v)\n",
"\n",
" def update(self, v):\n",
" for k, v in v.items():\n",
" self._set_kv(k, v)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The `Vars` is a proxy for the internal dictionary. For example, here is how one can use it."
]
},
{
"cell_type": "code",
"execution_count": 113,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.053792Z",
"iopub.status.busy": "2024-01-18T17:19:59.053672Z",
"iopub.status.idle": "2024-01-18T17:19:59.055951Z",
"shell.execute_reply": "2024-01-18T17:19:59.055624Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"{}"
]
},
"execution_count": 113,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"v = Vars('')\n",
"v.defs"
]
},
{
"cell_type": "code",
"execution_count": 114,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.057629Z",
"iopub.status.busy": "2024-01-18T17:19:59.057529Z",
"iopub.status.idle": "2024-01-18T17:19:59.059718Z",
"shell.execute_reply": "2024-01-18T17:19:59.059370Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"{'x': 'X'}"
]
},
"execution_count": 114,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"v['x'] = 'X'\n",
"v.defs"
]
},
{
"cell_type": "code",
"execution_count": 115,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.061604Z",
"iopub.status.busy": "2024-01-18T17:19:59.061457Z",
"iopub.status.idle": "2024-01-18T17:19:59.063929Z",
"shell.execute_reply": "2024-01-18T17:19:59.063610Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"{'x': 'x', 'y': 'y'}"
]
},
"execution_count": 115,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"v.update({'x': 'x', 'y': 'y'})\n",
"v.defs"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### AssignmentVars"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"We now extend the simple `Vars` to account for variable reassignments. For this, we define `AssignmentVars`.\n",
"\n",
"The idea for detecting reassignments and renaming variables is as follows: We keep track of the previous reassignments to particular variables using `accessed_seq_var`. It contains the last rename of any particular variable as its corresponding value. The `new_vars` contains a list of all new variables that were added on this iteration."
]
},
{
"cell_type": "code",
"execution_count": 116,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.065781Z",
"iopub.status.busy": "2024-01-18T17:19:59.065667Z",
"iopub.status.idle": "2024-01-18T17:19:59.067923Z",
"shell.execute_reply": "2024-01-18T17:19:59.067571Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class AssignmentVars(Vars):\n",
" def __init__(self, original):\n",
" super().__init__(original)\n",
" self.accessed_seq_var = {}\n",
" self.var_def_lines = {}\n",
" self.current_event = None\n",
" self.new_vars = set()\n",
" self.method_init()"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The `method_init()` method takes care of keeping track of method invocations using records saved in the `call_stack`. `event_locations` is for keeping track of the locations accessed *within this method*. This is used for line number tracking of variable definitions."
]
},
{
"cell_type": "code",
"execution_count": 117,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.070258Z",
"iopub.status.busy": "2024-01-18T17:19:59.069903Z",
"iopub.status.idle": "2024-01-18T17:19:59.072414Z",
"shell.execute_reply": "2024-01-18T17:19:59.072059Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class AssignmentVars(AssignmentVars):\n",
" def method_init(self):\n",
" self.call_stack = CallStack()\n",
" self.event_locations = {self.call_stack.method_id: []}"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The `update()` is now modified to track the changed line numbers if any, using `var_location_register()`. We reinitialize the `new_vars` after use for the next event."
]
},
{
"cell_type": "code",
"execution_count": 118,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.074006Z",
"iopub.status.busy": "2024-01-18T17:19:59.073900Z",
"iopub.status.idle": "2024-01-18T17:19:59.075789Z",
"shell.execute_reply": "2024-01-18T17:19:59.075533Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class AssignmentVars(AssignmentVars):\n",
" def update(self, v):\n",
" for k, v in v.items():\n",
" self._set_kv(k, v)\n",
" self.var_location_register(self.new_vars)\n",
" self.new_vars = set()"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The variable name now incorporates an index of how many reassignments it has gone through, effectively making each reassignment a unique variable."
]
},
{
"cell_type": "code",
"execution_count": 119,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.077351Z",
"iopub.status.busy": "2024-01-18T17:19:59.077219Z",
"iopub.status.idle": "2024-01-18T17:19:59.079143Z",
"shell.execute_reply": "2024-01-18T17:19:59.078834Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class AssignmentVars(AssignmentVars):\n",
" def var_name(self, var):\n",
" return (var, self.accessed_seq_var[var])"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"While storing variables, we need to first check whether it was previously known. If it is not, we need to initialize the rename count. This is accomplished by `var_access`."
]
},
{
"cell_type": "code",
"execution_count": 120,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.080816Z",
"iopub.status.busy": "2024-01-18T17:19:59.080683Z",
"iopub.status.idle": "2024-01-18T17:19:59.082639Z",
"shell.execute_reply": "2024-01-18T17:19:59.082359Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class AssignmentVars(AssignmentVars):\n",
" def var_access(self, var):\n",
" if var not in self.accessed_seq_var:\n",
" self.accessed_seq_var[var] = 0\n",
" return self.var_name(var)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"During a variable reassignment, we update the `accessed_seq_var` to reflect the new count."
]
},
{
"cell_type": "code",
"execution_count": 121,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.084238Z",
"iopub.status.busy": "2024-01-18T17:19:59.084067Z",
"iopub.status.idle": "2024-01-18T17:19:59.086170Z",
"shell.execute_reply": "2024-01-18T17:19:59.085893Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class AssignmentVars(AssignmentVars):\n",
" def var_assign(self, var):\n",
" self.accessed_seq_var[var] += 1\n",
" self.new_vars.add(self.var_name(var))\n",
" return self.var_name(var)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"These methods can be used as follows"
]
},
{
"cell_type": "code",
"execution_count": 122,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.087676Z",
"iopub.status.busy": "2024-01-18T17:19:59.087560Z",
"iopub.status.idle": "2024-01-18T17:19:59.089556Z",
"shell.execute_reply": "2024-01-18T17:19:59.089293Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"{}"
]
},
"execution_count": 122,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sav = AssignmentVars('')\n",
"sav.defs"
]
},
{
"cell_type": "code",
"execution_count": 123,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.090958Z",
"iopub.status.busy": "2024-01-18T17:19:59.090864Z",
"iopub.status.idle": "2024-01-18T17:19:59.093004Z",
"shell.execute_reply": "2024-01-18T17:19:59.092665Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"('v1', 0)"
]
},
"execution_count": 123,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sav.var_access('v1')"
]
},
{
"cell_type": "code",
"execution_count": 124,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.094865Z",
"iopub.status.busy": "2024-01-18T17:19:59.094733Z",
"iopub.status.idle": "2024-01-18T17:19:59.096994Z",
"shell.execute_reply": "2024-01-18T17:19:59.096684Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"('v1', 1)"
]
},
"execution_count": 124,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sav.var_assign('v1')"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Assigning to it again increments the counter."
]
},
{
"cell_type": "code",
"execution_count": 125,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.098825Z",
"iopub.status.busy": "2024-01-18T17:19:59.098701Z",
"iopub.status.idle": "2024-01-18T17:19:59.100624Z",
"shell.execute_reply": "2024-01-18T17:19:59.100358Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"('v1', 2)"
]
},
"execution_count": 125,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sav.var_assign('v1')"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The core of the logic is in `_set_kv()`. When a variable is being assigned, we get the sequenced variable name `s_var`. If the sequenced variable name was previously unknown in `defs`, then we have no further concerns. We add the sequenced variable to `defs`.\n",
"\n",
"If the variable is previously known, then it is an indication of a possible reassignment. In this case, we look at the value the variable is holding. We check if the value changed. If it has not, then it is not.\n",
"\n",
"If the value has changed, it is a reassignment. We first increment the variable usage sequence using `var_assign`, retrieve the new name, update the new name in `defs`."
]
},
{
"cell_type": "code",
"execution_count": 126,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.102143Z",
"iopub.status.busy": "2024-01-18T17:19:59.102044Z",
"iopub.status.idle": "2024-01-18T17:19:59.104075Z",
"shell.execute_reply": "2024-01-18T17:19:59.103761Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class AssignmentVars(AssignmentVars):\n",
" def _set_kv(self, var, val):\n",
" s_var = self.var_access(var)\n",
" if s_var in self.defs and self.defs[s_var] == val:\n",
" return\n",
" self.defs[self.var_assign(var)] = val"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Here is how it can be used. Assigning a variable the first time initializes its counter."
]
},
{
"cell_type": "code",
"execution_count": 127,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.105627Z",
"iopub.status.busy": "2024-01-18T17:19:59.105515Z",
"iopub.status.idle": "2024-01-18T17:19:59.107525Z",
"shell.execute_reply": "2024-01-18T17:19:59.107283Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"{('x', 1): 'X'}"
]
},
"execution_count": 127,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sav = AssignmentVars('')\n",
"sav['x'] = 'X'\n",
"sav.defs"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"If the variable is assigned again with the same value, it is probably not a reassignment."
]
},
{
"cell_type": "code",
"execution_count": 128,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.109051Z",
"iopub.status.busy": "2024-01-18T17:19:59.108933Z",
"iopub.status.idle": "2024-01-18T17:19:59.110988Z",
"shell.execute_reply": "2024-01-18T17:19:59.110628Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"{('x', 1): 'X'}"
]
},
"execution_count": 128,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sav['x'] = 'X'\n",
"sav.defs"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"However, if the value changed, it is a reassignment."
]
},
{
"cell_type": "code",
"execution_count": 129,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.112688Z",
"iopub.status.busy": "2024-01-18T17:19:59.112558Z",
"iopub.status.idle": "2024-01-18T17:19:59.115194Z",
"shell.execute_reply": "2024-01-18T17:19:59.114789Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"{('x', 1): 'X', ('x', 2): 'Y'}"
]
},
"execution_count": 129,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sav['x'] = 'Y'\n",
"sav.defs"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"There is a subtlety here. It is possible for a child method to be called from the middle of a parent method, and for both to use the same variable name with different values. In this case, when the child returns, parent will have the old variable with old value in context. With our implementation, we consider this as a reassignment. However, this is OK because adding a new reassignment is harmless, but missing one is not. Further, we will discuss later how this can be avoided."
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"We also define bookkeeping codes for `register_event()` `method_enter()` and `method_exit()` which are the methods responsible for keeping track of the method stack. The basic idea is that, each `method_enter()` represents a new method invocation. Hence, it merits a new method id, which is generated from the `method_register`, and saved in the `method_id`. Since this is a new method, the method stack is extended by one element with this id. In the case of `method_exit()`, we pop the method stack, and reset the current `method_id` to what was below the current one."
]
},
{
"cell_type": "code",
"execution_count": 130,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.116832Z",
"iopub.status.busy": "2024-01-18T17:19:59.116721Z",
"iopub.status.idle": "2024-01-18T17:19:59.119219Z",
"shell.execute_reply": "2024-01-18T17:19:59.118988Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class AssignmentVars(AssignmentVars):\n",
" def method_enter(self, cxt, my_vars):\n",
" self.current_event = 'call'\n",
" self.call_stack.enter(cxt.method)\n",
" self.event_locations[self.call_stack.method_id] = []\n",
" self.register_event(cxt)\n",
" self.update(my_vars)\n",
"\n",
" def method_exit(self, cxt, my_vars):\n",
" self.current_event = 'return'\n",
" self.register_event(cxt)\n",
" self.update(my_vars)\n",
" self.call_stack.leave()\n",
"\n",
" def method_statement(self, cxt, my_vars):\n",
" self.current_event = 'line'\n",
" self.register_event(cxt)\n",
" self.update(my_vars)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"For each of the method events, we also register the event using `register_event()` which keeps track of the line numbers that were referenced in *this* method."
]
},
{
"cell_type": "code",
"execution_count": 131,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.120875Z",
"iopub.status.busy": "2024-01-18T17:19:59.120769Z",
"iopub.status.idle": "2024-01-18T17:19:59.122468Z",
"shell.execute_reply": "2024-01-18T17:19:59.122245Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class AssignmentVars(AssignmentVars):\n",
" def register_event(self, cxt):\n",
" self.event_locations[self.call_stack.method_id].append(cxt.line_no)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The `var_location_register()` keeps the locations of newly added variables. The definition location of variables in a `call` is the *current* location. However, for a `line`, it would be the previous event in the current method."
]
},
{
"cell_type": "code",
"execution_count": 132,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.123998Z",
"iopub.status.busy": "2024-01-18T17:19:59.123895Z",
"iopub.status.idle": "2024-01-18T17:19:59.126215Z",
"shell.execute_reply": "2024-01-18T17:19:59.125957Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class AssignmentVars(AssignmentVars):\n",
" def var_location_register(self, my_vars):\n",
" def loc(mid):\n",
" if self.current_event == 'call':\n",
" return self.event_locations[mid][-1]\n",
" elif self.current_event == 'line':\n",
" return self.event_locations[mid][-2]\n",
" elif self.current_event == 'return':\n",
" return self.event_locations[mid][-2]\n",
" else:\n",
" assert False\n",
"\n",
" my_loc = loc(self.call_stack.method_id)\n",
" for var in my_vars:\n",
" self.var_def_lines[var] = my_loc"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"We define `defined_vars()` which returns the names of variables annotated with the line numbers as below."
]
},
{
"cell_type": "code",
"execution_count": 133,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.127926Z",
"iopub.status.busy": "2024-01-18T17:19:59.127808Z",
"iopub.status.idle": "2024-01-18T17:19:59.130022Z",
"shell.execute_reply": "2024-01-18T17:19:59.129760Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class AssignmentVars(AssignmentVars):\n",
" def defined_vars(self, formatted=True):\n",
" def fmt(k):\n",
" v = (k[0], self.var_def_lines[k])\n",
" return \"%s@%s\" % v if formatted else v\n",
"\n",
" return [(fmt(k), v) for k, v in self.defs.items()]"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Similar to `defined_vars()` we define `seq_vars()` which annotates different variables with the number of times they were used."
]
},
{
"cell_type": "code",
"execution_count": 134,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.131716Z",
"iopub.status.busy": "2024-01-18T17:19:59.131582Z",
"iopub.status.idle": "2024-01-18T17:19:59.133876Z",
"shell.execute_reply": "2024-01-18T17:19:59.133515Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class AssignmentVars(AssignmentVars):\n",
" def seq_vars(self, formatted=True):\n",
" def fmt(k):\n",
" v = (k[0], self.var_def_lines[k], k[1])\n",
" return \"%s@%s:%s\" % v if formatted else v\n",
"\n",
" return {fmt(k): v for k, v in self.defs.items()}"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### AssignmentTracker"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The `AssignmentTracker` keeps the assignment definitions using the `AssignmentVars` we defined previously."
]
},
{
"cell_type": "code",
"execution_count": 135,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.136037Z",
"iopub.status.busy": "2024-01-18T17:19:59.135858Z",
"iopub.status.idle": "2024-01-18T17:19:59.138301Z",
"shell.execute_reply": "2024-01-18T17:19:59.137957Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class AssignmentTracker(DefineTracker):\n",
" def __init__(self, my_input, trace, **kwargs):\n",
" self.options(kwargs)\n",
" self.my_input = my_input\n",
"\n",
" self.my_assignments = self.create_assignments(my_input)\n",
"\n",
" self.trace = trace\n",
" self.process()\n",
"\n",
" def create_assignments(self, *args):\n",
" return AssignmentVars(*args)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"To fine-tune the process, we define an optional parameter called `track_return`. During tracing a method return, Python produces a virtual variable that contains the result of the returned value. If the `track_return` is set, we capture this value as a variable.\n",
"\n",
"* `track_return` -- if true, add a *virtual variable* to the Vars representing the return value"
]
},
{
"cell_type": "code",
"execution_count": 136,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.139926Z",
"iopub.status.busy": "2024-01-18T17:19:59.139813Z",
"iopub.status.idle": "2024-01-18T17:19:59.141684Z",
"shell.execute_reply": "2024-01-18T17:19:59.141437Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class AssignmentTracker(AssignmentTracker):\n",
" def options(self, kwargs):\n",
" self.track_return = kwargs.get('track_return', False)\n",
" super().options(kwargs)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"There can be different kinds of events during a trace, which includes `call` when a function is entered, `return` when the function returns, `exception` when an exception is thrown and `line` when a statement is executed.\n",
"\n",
"The previous `Tracker` was too simplistic in that it did not distinguish between the different events. We rectify that and define `on_call()`, `on_return()`, and `on_line()` respectively, which get called on their corresponding events.\n",
"\n",
"Note that `on_line()` is called also for `on_return()`. The reason is, that Python invokes the trace function *before* the corresponding line is executed. Hence, effectively, the `on_return()` is called with the binding produced by the execution of the previous statement in the environment. Our processing in effect is done on values that were bound by the previous statement. Hence, calling `on_line()` here is appropriate as it provides the event handler a chance to work on the previous binding."
]
},
{
"cell_type": "code",
"execution_count": 137,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.143326Z",
"iopub.status.busy": "2024-01-18T17:19:59.143205Z",
"iopub.status.idle": "2024-01-18T17:19:59.146632Z",
"shell.execute_reply": "2024-01-18T17:19:59.146202Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class AssignmentTracker(AssignmentTracker):\n",
" def on_call(self, arg, cxt, my_vars):\n",
" my_vars = cxt.parameters(my_vars)\n",
" self.my_assignments.method_enter(cxt, self.fragments(my_vars))\n",
"\n",
" def on_line(self, arg, cxt, my_vars):\n",
" self.my_assignments.method_statement(cxt, self.fragments(my_vars))\n",
"\n",
" def on_return(self, arg, cxt, my_vars):\n",
" self.on_line(arg, cxt, my_vars)\n",
" my_vars = {'<-%s' % cxt.method: arg} if self.track_return else {}\n",
" self.my_assignments.method_exit(cxt, my_vars)\n",
"\n",
" def on_exception(self, arg, cxt, my_vara):\n",
" return\n",
"\n",
" def track_event(self, event, arg, cxt, my_vars):\n",
" self.current_event = event\n",
" dispatch = {\n",
" 'call': self.on_call,\n",
" 'return': self.on_return,\n",
" 'line': self.on_line,\n",
" 'exception': self.on_exception\n",
" }\n",
" dispatch[event](arg, cxt, my_vars)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"We can now use `AssignmentTracker` to track the different variables. To verify that our variable line number inference works, we recover definitions from the functions `A()`, `B()` and `C()` (with data annotations removed so that the input fragments are correctly identified). "
]
},
{
"cell_type": "code",
"execution_count": 138,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.148548Z",
"iopub.status.busy": "2024-01-18T17:19:59.148448Z",
"iopub.status.idle": "2024-01-18T17:19:59.150191Z",
"shell.execute_reply": "2024-01-18T17:19:59.149885Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def C(cp_1): # type: ignore\n",
" c_2 = cp_1\n",
" c_3 = c_2\n",
" return c_3"
]
},
{
"cell_type": "code",
"execution_count": 139,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.151764Z",
"iopub.status.busy": "2024-01-18T17:19:59.151666Z",
"iopub.status.idle": "2024-01-18T17:19:59.153361Z",
"shell.execute_reply": "2024-01-18T17:19:59.153063Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def B(bp_7): # type: ignore\n",
" b_8 = bp_7\n",
" return C(b_8)"
]
},
{
"cell_type": "code",
"execution_count": 140,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.154837Z",
"iopub.status.busy": "2024-01-18T17:19:59.154754Z",
"iopub.status.idle": "2024-01-18T17:19:59.156577Z",
"shell.execute_reply": "2024-01-18T17:19:59.156331Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def A(ap_12): # type: ignore\n",
" a_13 = ap_12\n",
" a_14 = B(a_13)\n",
" a_14 = a_14\n",
" a_13 = a_14\n",
" a_14 = B(a_13)\n",
" a_14 = B(a_14)[3:]"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Running `A()` with sufficient input."
]
},
{
"cell_type": "code",
"execution_count": 141,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.158064Z",
"iopub.status.busy": "2024-01-18T17:19:59.157977Z",
"iopub.status.idle": "2024-01-18T17:19:59.262249Z",
"shell.execute_reply": "2024-01-18T17:19:59.261944Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"ap_12@1:1 = '---xxx'\n",
"a_13@2:1 = '---xxx'\n",
"bp_7@1:1 = '---xxx'\n",
"b_8@2:1 = '---xxx'\n",
"cp_1@1:1 = '---xxx'\n",
"c_2@2:1 = '---xxx'\n",
"c_3@3:1 = '---xxx'\n",
"a_14@3:1 = '---xxx'\n",
"a_14@7:2 = 'xxx'\n",
"\n",
"ap_12@1 = '---xxx'\n",
"a_13@2 = '---xxx'\n",
"bp_7@1 = '---xxx'\n",
"b_8@2 = '---xxx'\n",
"cp_1@1 = '---xxx'\n",
"c_2@2 = '---xxx'\n",
"c_3@3 = '---xxx'\n",
"a_14@3 = '---xxx'\n",
"a_14@7 = 'xxx'\n"
]
}
],
"source": [
"with Tracer('---xxx') as tracer:\n",
" A(tracer.my_input)\n",
"tracker = AssignmentTracker(tracer.my_input, tracer.trace, log=True)\n",
"for k, v in tracker.my_assignments.seq_vars().items():\n",
" print(k, '=', repr(v))\n",
"print()\n",
"for k, v in tracker.my_assignments.defined_vars(formatted=True):\n",
" print(k, '=', repr(v))"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"As can be seen, the line numbers are now correctly identified for each variable."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
" Let us try retrieving the assignments for a real world example."
]
},
{
"cell_type": "code",
"execution_count": 142,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.264366Z",
"iopub.status.busy": "2024-01-18T17:19:59.264204Z",
"iopub.status.idle": "2024-01-18T17:19:59.386053Z",
"shell.execute_reply": "2024-01-18T17:19:59.385683Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"url@372 = 'http://user:pass@www.google.com:80/?q=path#ref'\n",
"url@478 = '//user:pass@www.google.com:80/?q=path#ref'\n",
"scheme@478 = 'http'\n",
"url@481 = '/?q=path#ref'\n",
"netloc@481 = 'user:pass@www.google.com:80'\n",
"url@486 = '/?q=path'\n",
"fragment@486 = 'ref'\n",
"query@488 = 'q=path'\n",
"url@393 = 'http://user:pass@www.google.com:80/?q=path#ref'\n",
"\n",
"url@372 = 'https://www.cispa.saarland:80/'\n",
"url@478 = '//www.cispa.saarland:80/'\n",
"scheme@478 = 'https'\n",
"netloc@481 = 'www.cispa.saarland:80'\n",
"url@393 = 'https://www.cispa.saarland:80/'\n",
"\n",
"url@372 = 'http://www.fuzzingbook.org/#News'\n",
"url@478 = '//www.fuzzingbook.org/#News'\n",
"scheme@478 = 'http'\n",
"url@481 = '/#News'\n",
"netloc@481 = 'www.fuzzingbook.org'\n",
"fragment@486 = 'News'\n",
"url@393 = 'http://www.fuzzingbook.org/#News'\n",
"\n",
"url@372 = 'ftp://freebsd.org/releases/5.8'\n",
"url@478 = '//freebsd.org/releases/5.8'\n",
"scheme@478 = 'ftp'\n",
"url@481 = '/releases/5.8'\n",
"netloc@481 = 'freebsd.org'\n",
"url@393 = 'ftp://freebsd.org/releases/5.8'\n",
"url@394 = '/releases/5.8'\n",
"\n"
]
}
],
"source": [
"traces = []\n",
"for inputstr in URLS_X:\n",
" clear_cache()\n",
" with Tracer(inputstr, files=['urllib/parse.py']) as tracer:\n",
" urlparse(tracer.my_input)\n",
" traces.append((tracer.my_input, tracer.trace))\n",
"\n",
" tracker = AssignmentTracker(tracer.my_input, tracer.trace, log=True)\n",
" for k, v in tracker.my_assignments.defined_vars():\n",
" print(k, '=', repr(v))\n",
" print()"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"The line numbers of variables can be verified from the source code of [urllib/parse.py](https://github.com/python/cpython/blob/3.6/Lib/urllib/parse.py)."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Recovering a Derivation Tree"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Does handling variable reassignments help with our URL examples? We look at these next."
]
},
{
"cell_type": "code",
"execution_count": 143,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.388488Z",
"iopub.status.busy": "2024-01-18T17:19:59.388294Z",
"iopub.status.idle": "2024-01-18T17:19:59.390501Z",
"shell.execute_reply": "2024-01-18T17:19:59.390226Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class TreeMiner(TreeMiner):\n",
" def get_derivation_tree(self):\n",
" tree = (START_SYMBOL, [(self.my_input, [])])\n",
" for var, value in self.my_assignments:\n",
" self.log(0, \"%s=%s\" % (var, repr(value)))\n",
" self.apply_new_definition(tree, var, value)\n",
" return tree"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### Example 1: Recovering URL Derivation Tree"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"First we obtain the derivation tree of the URL 1"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"##### URL 1 derivation tree"
]
},
{
"cell_type": "code",
"execution_count": 144,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.392176Z",
"iopub.status.busy": "2024-01-18T17:19:59.392067Z",
"iopub.status.idle": "2024-01-18T17:19:59.818202Z",
"shell.execute_reply": "2024-01-18T17:19:59.817862Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 144,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"clear_cache()\n",
"with Tracer(URLS_X[0], files=['urllib/parse.py']) as tracer:\n",
" urlparse(tracer.my_input)\n",
"sm = AssignmentTracker(tracer.my_input, tracer.trace)\n",
"dt = TreeMiner(tracer.my_input, sm.my_assignments.defined_vars())\n",
"display_tree(dt.tree)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Next, we obtain the derivation tree of URL 4"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"##### URL 4 derivation tree"
]
},
{
"cell_type": "code",
"execution_count": 145,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:19:59.819966Z",
"iopub.status.busy": "2024-01-18T17:19:59.819850Z",
"iopub.status.idle": "2024-01-18T17:20:00.242062Z",
"shell.execute_reply": "2024-01-18T17:20:00.241702Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 145,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"clear_cache()\n",
"with Tracer(URLS_X[-1], files=['urllib/parse.py']) as tracer:\n",
" urlparse(tracer.my_input)\n",
"sm = AssignmentTracker(tracer.my_input, tracer.trace)\n",
"dt = TreeMiner(tracer.my_input, sm.my_assignments.defined_vars())\n",
"display_tree(dt.tree)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The derivation trees seem to belong to the same grammar. Hence, we obtain the grammar for the complete set. First, we update the `recover_grammar()` to use `AssignTracker`."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Recover Grammar"
]
},
{
"cell_type": "code",
"execution_count": 146,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:20:00.244118Z",
"iopub.status.busy": "2024-01-18T17:20:00.243980Z",
"iopub.status.idle": "2024-01-18T17:20:00.246644Z",
"shell.execute_reply": "2024-01-18T17:20:00.246307Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class GrammarMiner(GrammarMiner):\n",
" def update_grammar(self, inputstr, trace):\n",
" at = self.create_tracker(inputstr, trace)\n",
" dt = self.create_tree_miner(inputstr, at.my_assignments.defined_vars())\n",
" self.add_tree(dt)\n",
" return self.grammar\n",
"\n",
" def create_tracker(self, *args):\n",
" return AssignmentTracker(*args)\n",
"\n",
" def create_tree_miner(self, *args):\n",
" return TreeMiner(*args)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Next, we use the modified `recover_grammar()` on derivation trees obtained from URLs."
]
},
{
"cell_type": "code",
"execution_count": 147,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:20:00.248146Z",
"iopub.status.busy": "2024-01-18T17:20:00.248037Z",
"iopub.status.idle": "2024-01-18T17:20:00.389875Z",
"shell.execute_reply": "2024-01-18T17:20:00.389589Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"url_grammar = recover_grammar(url_parse, URLS_X, files=['urllib/parse.py'])"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"The recovered grammar is below."
]
},
{
"cell_type": "code",
"execution_count": 148,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:20:00.391737Z",
"iopub.status.busy": "2024-01-18T17:20:00.391645Z",
"iopub.status.idle": "2024-01-18T17:20:00.406113Z",
"shell.execute_reply": "2024-01-18T17:20:00.405812Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"start\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"url@372\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"scheme@478\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"url@478\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"netloc@481\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"url@481\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"url@486\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"query@488\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"fragment@486\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"url@394\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"syntax_diagram(url_grammar)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Let us fuzz a little to see if the produced values are sane."
]
},
{
"cell_type": "code",
"execution_count": 149,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:20:00.407735Z",
"iopub.status.busy": "2024-01-18T17:20:00.407646Z",
"iopub.status.idle": "2024-01-18T17:20:00.410896Z",
"shell.execute_reply": "2024-01-18T17:20:00.410636Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"http://user:pass@www.google.com:80/#News\n",
"https://freebsd.org/\n",
"ftp://www.fuzzingbook.org/\n",
"https://freebsd.org/\n",
"https://user:pass@www.google.com:80/#ref\n",
"http://user:pass@www.google.com:80/?q=path#News\n",
"http://www.cispa.saarland:80/#ref\n",
"https://www.fuzzingbook.org/#News\n",
"ftp://www.fuzzingbook.org/\n",
"ftp://user:pass@www.google.com:80/#ref\n"
]
}
],
"source": [
"f = GrammarFuzzer(url_grammar)\n",
"for _ in range(10):\n",
" print(f.fuzz())"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Our modifications do seem to help. Next, we check whether we can still retrieve the grammar for inventory."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### Example 2: Recovering Inventory Grammar"
]
},
{
"cell_type": "code",
"execution_count": 150,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:20:00.412640Z",
"iopub.status.busy": "2024-01-18T17:20:00.412511Z",
"iopub.status.idle": "2024-01-18T17:20:00.417833Z",
"shell.execute_reply": "2024-01-18T17:20:00.417601Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"inventory_grammar = recover_grammar(process_vehicle, VEHICLES)"
]
},
{
"cell_type": "code",
"execution_count": 151,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:20:00.419316Z",
"iopub.status.busy": "2024-01-18T17:20:00.419226Z",
"iopub.status.idle": "2024-01-18T17:20:00.428370Z",
"shell.execute_reply": "2024-01-18T17:20:00.428092Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"start\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"vehicle@29\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"year@30\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"kind@30\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"company@30\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"model@30\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"syntax_diagram(inventory_grammar)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Using fuzzing to produce values from the grammar."
]
},
{
"cell_type": "code",
"execution_count": 152,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:20:00.430113Z",
"iopub.status.busy": "2024-01-18T17:20:00.429882Z",
"iopub.status.idle": "2024-01-18T17:20:00.432937Z",
"shell.execute_reply": "2024-01-18T17:20:00.432700Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2000,van,Chevy,Cougar\n",
"2000,van,Ford,Cougar\n",
"1999,van,Chevy,E350\n",
"1997,car,Ford,E350\n",
"2000,van,Mercury,Venture\n",
"1999,car,Ford,E350\n",
"1999,car,Mercury,Venture\n",
"1999,car,Mercury,E350\n",
"1997,van,Mercury,Cougar\n",
"1999,car,Chevy,Venture\n"
]
}
],
"source": [
"f = GrammarFuzzer(inventory_grammar)\n",
"for _ in range(10):\n",
" print(f.fuzz())"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Problems with the Grammar Miner with Reassignment"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"One of the problems with our grammar miner is that it doesn't yet account for the current context. That is, when replacing, a variable can replace tokens that it does not have access to (and hence, it is not a fragment of). Consider this example."
]
},
{
"cell_type": "code",
"execution_count": 153,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:20:00.434672Z",
"iopub.status.busy": "2024-01-18T17:20:00.434585Z",
"iopub.status.idle": "2024-01-18T17:20:00.869062Z",
"shell.execute_reply": "2024-01-18T17:20:00.868626Z"
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 153,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"with Tracer(INVENTORY) as tracer:\n",
" process_inventory(tracer.my_input)\n",
"sm = AssignmentTracker(tracer.my_input, tracer.trace)\n",
"dt = TreeMiner(tracer.my_input, sm.my_assignments.defined_vars())\n",
"display_tree(dt.tree, graph_attr=lr_graph)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"As can be seen, the derivation tree obtained is not quite what we expected. The issue is easily seen if we enable logging in the `TreeMiner`."
]
},
{
"cell_type": "code",
"execution_count": 154,
"metadata": {
"execution": {
"iopub.execute_input": "2024-01-18T17:20:00.870958Z",
"iopub.status.busy": "2024-01-18T17:20:00.870822Z",
"iopub.status.idle": "2024-01-18T17:20:00.878668Z",
"shell.execute_reply": "2024-01-18T17:20:00.878303Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" inventory@22='1997,van,Ford,E350\\n2000,car,Mercury,Cougar\\n1999,car,Chevy,Venture'\n",
"\t - Node: \t\t? (:'1997,van,Ford,E350\\n2000,car,Mercury,Cougar\\n1999,car,Chevy,Venture')\n",
"\t\t -> [0] '1997,van,Ford,E350\\n2000,car,Mercury,Cougar\\n1999,car,Chevy,Venture'\n",
"\t\t > ['']\n",
" vehicle@24='1997,van,Ford,E350'\n",
"\t - Node: \t\t? (:'1997,van,Ford,E350')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'1997,van,Ford,E350')\n",
"\t\t -> [0] '1997,van,Ford,E350\\n2000,car,Mercury,Cougar\\n1999,car,Chevy,Venture'\n",
"\t\t > ['', '\\n2000,car,Mercury,Cougar\\n1999,car,Chevy,Venture']\n",
" year@30='1997'\n",
"\t - Node: \t\t? (:'1997')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'1997')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'1997')\n",
"\t\t -> [0] '1997,van,Ford,E350'\n",
"\t\t > ['', ',van,Ford,E350']\n",
" kind@30='van'\n",
"\t - Node: \t\t? (:'van')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'van')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'van')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'van')\n",
"\t\t -> [0] '1997'\n",
"\t\t -> [1] ',van,Ford,E350'\n",
"\t\t > [',', '', ',Ford,E350']\n",
" company@30='Ford'\n",
"\t - Node: \t\t? (:'Ford')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'Ford')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'Ford')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'Ford')\n",
"\t\t -> [0] '1997'\n",
"\t\t -> [1] ','\n",
"\t\t -> [2] ''\n",
"\t - Node: \t\t? (:'Ford')\n",
"\t\t -> [0] 'van'\n",
"\t\t -> [3] ',Ford,E350'\n",
"\t\t > [',', '', ',E350']\n",
" model@30='E350'\n",
"\t - Node: \t\t? (:'E350')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'E350')\n",
"\t\t -> [0] ''\n",
"\t - Node: \t\t? (:'E350')\n",
"\t\t -> [0] '