Hierarchical Delta Debugging Framework
Hierarchical Delta Debugging Framework
.. image:: https://img.shields.io/pypi/v/picireny?logo=python&logoColor=white :target: https://pypi.org/project/picireny/ .. image:: https://img.shields.io/pypi/l/picireny?logo=open-source-initiative&logoColor=white :target: https://pypi.org/project/picireny/ .. image:: https://img.shields.io/github/actions/workflow/status/renatahodovan/picireny/main.yml?branch=master&logo=github&logoColor=white :target: https://github.com/renatahodovan/picireny/actions .. image:: https://img.shields.io/coveralls/github/renatahodovan/picireny/master?logo=coveralls&logoColor=white :target: https://coveralls.io/github/renatahodovan/picireny
Picireny is a Python implementation of the Hierarchical Delta Debugging (HDD in short) algorithm adapted to use ANTLR_ v4 for parsing both the input and the grammar(s) describing the format of the input. It relies on Picire_ to provide the implementation of the core Delta Debugging algorithm along with various tweaks like parallelization. Just like the Picire framework, Picireny can also be used either as a command line tool or as a library.
Both Hierarchical Delta Debugging and Delta Debugging automatically reduce "interesting" tests while keeping their "interesting" behaviour. (E.g., "interestingness" may mean failure-inducing input to a system-under-test.) However, HDD is an improvement that tries to investigate less test cases during the reduction process by making use of knowledge on the structure of the input.
The tool (and the algorithm) works iteratively in several ways. As a first step, it splits up the input into tokens and organizes them in a tree structure as defined by a grammar. Then, iteratively, it invokes Delta Debugging on each level of the tree from top to bottom, and DD is an iterative process itself, too. Finally, the nodes kept in the tree are "unparsed" to yield a reduced but still "interesting" output.
.. _ANTLR: http://www.antlr.org .. _Picire: https://github.com/renatahodovan/picire
.. _Python: https://www.python.org .. _Java: https://www.oracle.com/java/
To use Picireny in another project, it can be added to setup.cfg
as an
install requirement (if using setuptools_ with declarative config):
.. code-block:: ini
[options]
install_requires =
picireny
To install Picireny manually, e.g., into a virtual environment, use pip_::
pip install picireny
The above approaches install the latest release of Picireny from PyPI_. Alternatively, for the development version, clone the project and perform a local install::
pip install .
.. _setuptools: https://github.com/pypa/setuptools .. _pip: https://pip.pypa.io .. _PyPI: https://pypi.org/
Picireny uses the same CLI as Picire and hence accepts the same options_. On top of the inherited ones, Picireny accepts several further arguments:
--grammar
(optional): List of grammars describing the input format. (You
can write them by hand or simply download them from the
ANTLR v4 grammars repository
_.)--start
(optional): Name of the start rule (optionally prefixed with a
grammar name) as [grammarname:]rulename
.--replacements
(optional): Json file containing rule names and minimal
replacement strings (otherwise these are calculated automatically) (see
schema__).--format
(optional): Json file describing the input format (see schema__
and example_). This descriptor can incorporate all the above (--grammar
,
--start
and --replacements
) properties, along with the possibility of
island grammar definitions. If both --format
and the aforementioned
arguments are present, then the latter will override the appropriate values of
the format file.--antlr
(optional): Path to the ANTLR tool jar.--parser
(optional): Language of the generated parser. Currently 'python'
(default) and 'java' targets (faster, but needs JDK) are supported.Note: although, all the arguments are optional, the grammar files and the start
rule of the top-level parser must be defined with an arbitrary combination of the
--format
, --grammars
, and --start
arguments.
.. _options: https://github.com/renatahodovan/picire/tree/master/README.rst#usage
.. _ANTLR v4 grammars repository
: https://github.com/antlr/grammars-v4
.. __: schemas/replacements.json
.. __: schemas/format.json
.. _example: tests/resources/inijson.json
Example usage to reduce an HTML file::
picireny --input=<path/to/the/input.html> --test=<path/to/the/tester> \
--grammar HTMLLexer.g4 HTMLParser.g4 --start htmlDocument \
--parallel --subset-iterator=skip --complement-iterator=backward
Picireny was tested on:
Picireny is motivated by the idea of Hierarchical Delta Debugging:
The details of the modernized re-implementation and further improvements are published in:
Licensed under the BSD 3-Clause License_.
.. _License: LICENSE.rst