.. _bot_its_main:

BOT-its Algorithms
==================

In this section we describe all the variants of the *Build One Test - Iterative Test Suite (BOT-its)* greedy MCAC algorithm.
For a more formal description of these algorithms see :cite:p:`DBLP:conf/cp/AnsoteguiOT21`.

In a more recent work (still under review), we extend and improve these algorithms and provide the parallel :ref:`parallel_prbot_its` algorithm.

We will show several simple execution examples for these algorithms.
You can check the :ref:`cli` for a complete description of all the available parameters.

.. _bot_its:

BOT-its
~~~~~~~

``BOT-its`` greedily builds an MCAC one test at a time, trying to maximize the number of covered tuples at each test.
It is based on the work in :cite:p:`Yamada16`.

You can execute ``BOT-its`` with strength 2 for a given instance in *ACTS* format as shown:

.. code-block:: console

    ctlog PRBOT-its sut.acts -t 2

.. _rbot_its:

RBOT-its
~~~~~~~~

``RBOT-its`` is an extension of ``BOT-its`` where we apply MaxSAT refinement techniques to try to improve the final MCAC size.

To activate ``RBOT-its`` instead of ``BOT-its`` you must set a value for the ``--maxsat-timeout`` or ``--intermediate-maxsat-timeout`` parameters, as we show below:

.. code-block:: console

    ctlog PRBOT-its sut.acts -t 2 --maxsat-timeout 30

In this case we are activating ``RBOT-its`` by setting a limit of 30s for each MaxSAT call.

.. _pbot_its:

PBOT-its
~~~~~~~~

``PBOT-its`` is another extension of ``BOT-its`` where we limit the number of simultaneous tuples that are kept in memory.
This algorithm allows building MCAC for higher strengths.

To activate ``PBOT-its`` you must set a limit for the pool, which can be set through the ``--max-pool-size`` in terms of number of tuples or through ``--max-mem-GB`` in terms of maximum pool size in GB.
Only one of these parameters can be set at once.
For example, this command would limit the maximum number of tuples in the pool to 10:

.. code-block:: console

    ctlog PRBOT-its sut.acts -t 2 --max-pool-size 10

.. _prbot_its:

PRBOT-its
~~~~~~~~~

``PRBOT-its`` is the combination of ``RBOT-its`` and ``PBOT-its``.
It tries to obtain smaller MCACs by applying the MaxSAT refinement techniques of ``RBOT-its`` while keeping a limit on the memory consumption as in ``PBOT-its``.

We must activate one of the parameters of ``RBOT-its`` and ``PRBOT-its`` to execute this algorithm (see :ref:`rbot_its` and :ref:`pbot_its`):

.. code-block:: console

    ctlog PRBOT-its sut.acts -t 2 --maxsat-timeout 30 --max-pool-size 10

.. _parallel_prbot_its:

Parallel PRBOT-its
~~~~~~~~~~~~~~~~~~

The ``Parallel PRBOT-its`` splits all the tuples to be covered into different chunks and submits jobs that build test suites for their assigned chunk of tuples in parallel.

To activate the parallel version of ``PRBOT-its`` we must first activate ``PBOT-its`` as shown in the :ref:`pbot_its` section.
Then, we must specify the number of pools that will be assigned to each job by setting the ``--parallel-num-pools`` parameter.
Additionally, we can set the maximum number of parallel jobs by setting the ``--max-parallel-jobs`` parameter.

To submit jobs ``Parallel PRBOT-its`` needs a submitter script that must be specified through the ``--submitter-script`` parameter.
This script receives the job name and logs directory as first and second parameters and the rest of the command to be executed.
The script must submit the command in some sort of job queue system.

The `Task Spooler (tsp) <https://github.com/justanhduc/task-spooler>`_ is a Unix batch system that can be used to enqueue jobs into a local system.
An example submitter script for ``tsp`` is shown below:

.. code-block:: bash

    #!/bin/bash

    job_name=$1
    logs_dir=$2
    shift 2

    output="$logs_dir/$job_name.o"
    err="$logs_dir/$job_name.e"

    EXECUTING_COMMAND="source /path/to/venv/bin/activate && $@ > ${output} 2> ${err}"
    tsp -L $job_name -n -N 1 bash -c "$EXECUTING_COMMAND"

Notice that we must activate the virtual envronment where CTLog is installed (in case we installed CTLog in a virtual environment).
Let this script be ``tsp.sh``, an example execution command for ``Parallel PRBOT-its`` is shown below:

.. code-block:: console

    ctlog PRBOT-its sut.acts -t 2 --max-pool-size 10 --parallel-num-pools 5 --max-parallel-jobs 10 --submitter-script tsp.sh