# Copyright (c) 2018-2022 Renata Hodovan, Akos Kiss.
# Copyright (c) 2021 Daniel Vince
#
# Licensed under the BSD 3-Clause License
# <LICENSE.rst or https://opensource.org/licenses/BSD-3-Clause>.
# This file may not be copied, modified, or distributed except
# according to those terms.

import itertools
import logging

from .prune import prune

logger = logging.getLogger(__name__)


def hddrmin(hdd_tree, *,
            reduce_class, reduce_config, tester_class, tester_config,
            id_prefix=(), cache=None, unparse_with_whitespace=True,
            config_filter=None, transformations=(prune,), hdd_star=True,
            pop_first=False, append_reversed=False):
    """
    Run the recursive variant of the hierarchical delta debugging reduce
    algorithm (a.k.a. HDDr).

    The tree traversal implementation is actually not recursive but an iterative
    queue-based reformulation of HDDr. How tree nodes are popped from the queue
    during the iteration (whether from the beginning or from the end of the
    queue) and how the children of a visited node are appended to the queue
    (whether they are added in forward or reverse order) give rise to different
    variants of HDDr:

        - 'pop first' with 'forward append' gives the classic breadth-first
          traversal,
        - 'pop first' with 'reverse append' gives syntactically reversed
          breadth-first traversal,
        - 'pop last' with 'reverse append' gives the classic depth-first
          traversal,
        - 'pop last' with 'forward append' gives syntactically reversed
          depth-first traversal.

    :param hdd_tree: The root of the tree that the reduce will work with (it's
        the output of create_hdd_tree).
    :param reduce_class: Reference to the reducer class (DD, ParallelDD or
        CombinedParallelDD from the picire module).
    :param reduce_config: Dictionary containing the parameters of the
        reduce_class init function.
    :param tester_class: Reference to a callable class that can decide about the
        interestingness of a test case.
    :param tester_config: Dictionary containing the parameters of the tester
        class init function (except test_builder).
    :param id_prefix: Tuple to prepend to config IDs during tests.
    :param cache: Cache to use.
    :param unparse_with_whitespace: Build test case by adding whitespace between
        nonadjacent tree nodes during unparsing.
    :param config_filter: Filter function from node to boolean, to allow running
        hddmin selectively.
    :param transformations: Iterable of transformations that reduce a
        configuration of nodes.
    :param hdd_star: Boolean to enable the HDD star algorithm.
    :param pop_first: Boolean to control tree traversal (see above for details).
    :param append_reverse: Boolean to control tree traversal (see above for
        details).
    :return: The reduced test case (1-tree-minimal if hdd_star is True and
        config_filter is None).
    """

    for iter_cnt in itertools.count():
        logger.info('Iteration #%d', iter_cnt)

        changed = False
        queue = [hdd_tree]
        for node_cnt in itertools.count():
            if not queue:
                break
            if pop_first:
                queue, node = queue[1:], queue[0]
            else:
                queue, node = queue[:-1], queue[-1]
            if not hasattr(node, 'children') or node.state != node.KEEP:
                continue

            children = [child for child in node.children if child.state == child.KEEP]
            if config_filter:
                children = list(filter(config_filter, children))

            if children:
                logger.info('Checking node #%d ...', node_cnt)

                for trans_cnt, transformation in enumerate(transformations):
                    hdd_tree, transformed = transformation(hdd_tree, children,
                                                           reduce_class=reduce_class, reduce_config=reduce_config,
                                                           tester_class=tester_class, tester_config=tester_config,
                                                           id_prefix=id_prefix + (f'i{iter_cnt}', f'n{node_cnt}', f't{trans_cnt}'),
                                                           cache=cache,
                                                           unparse_with_whitespace=unparse_with_whitespace)

                    changed = changed or transformed

            for child in node.children if not append_reversed else reversed(node.children):
                if child.state == child.KEEP:
                    queue.append(child)

        if not hdd_star or not changed:
            break

    return hdd_tree
