Workshop Prático: Caça aos Bugs Automatizada com Teste Baseado em Busca (SBST)

# @title Instalação e importação das bibliotecas
!pip install deap numpy matplotlib -q

import random
import numpy as np
import matplotlib.pyplot as plt
from typing import List, Tuple, Set, Any, Callable
import time

from deap import base, creator, tools, algorithms

# Configura a seed para reprodutibilidade
random.seed(42)
np.random.seed(42)

print("✅ Ambiente configurado com sucesso!")

# @title Implementação do Instrumento de Cobertura e da Função-Alvo

class CoverageInstrument:
    """Um decorator para instrumentar uma função e rastrear a cobertura de ramos."""
    def __init__(self):
        self.covered_branches: Set[int] = set()

    def __call__(self, func: Callable) -> Callable:
        """Permite que a instância da classe seja usada como um decorator."""
        self.func = func
        # Injeta a si mesma na função para que ela possa registrar a cobertura
        self.func.instrument = self
        return self.func

    def add(self, branch_id: int):
        """Registra que um ramo foi coberto."""
        self.covered_branches.add(branch_id)

    def reset(self):
        """Limpa o registro de cobertura antes de uma nova execução."""
        self.covered_branches.clear()

    def get_coverage(self) -> Set[int]:
        """Retorna o conjunto de ramos cobertos na última execução."""
        return self.covered_branches

# Instancia nosso instrumento
instrument = CoverageInstrument()

# O número total de ramos que queremos cobrir
TOTAL_BRANCHES = 6

@instrument
def classificador_complexo(x: int, y: int, z: str) -> str:
    """Uma função com lógica complexa para servir de alvo para o SBST."""
    # Acessa o instrumento injetado pelo decorator
    instr = classificador_complexo.instrument

    if x > 50:
        if y < 25 and z == "beta":
            instr.add(1) # Ramo 1
            return "Categoria A"
        else:
            instr.add(2) # Ramo 2
            return "Categoria B"
    else:
        if z == "alpha":
            instr.add(3) # Ramo 3
            return "Categoria C"
        elif y > 75:
            instr.add(4) # Ramo 4
            return "Categoria D"
        # Este é o nosso "beco sem saída", difícil de encontrar
        elif x > 40 and y < 10 and z == "omega":
            instr.add(5) # Ramo 5
            return "Categoria SECRETA"
    
    instr.add(6) # Ramo 6 (Default)
    return "Categoria Padrão"

print(f"🎯 Função 'classificador_complexo' criada com {TOTAL_BRANCHES} ramos lógicos.")

# Exemplo de como obter a cobertura para um caso de teste
instrument.reset()
classificador_complexo(60, 20, "beta")
cobertura = instrument.get_coverage()
print(f"Exemplo: O caso de teste (60, 20, 'beta') cobre os ramos: {cobertura}")

# @title Definição da Estrutura do AG (Fitness, Indivíduo/Suíte e Toolbox)

# Representaremos um indivíduo como uma SUÍTE de testes (vários casos [x, y, z]).
# O fitness mede a cobertura de ramos única alcançada pela suíte inteira (0..6).

# 1. Fitness e Indivíduo
# Protege contra reexecução desta célula em ambientes interativos (DEAP não permite recriar o mesmo tipo)
try:
    creator.FitnessMax
except AttributeError:
    creator.create("FitnessMax", base.Fitness, weights=(1.0,))

try:
    creator.Individual
except AttributeError:
    # Um indivíduo é uma lista de casos de teste (cada caso é [x, y, z]) com um atributo de fitness
    creator.create("Individual", list, fitness=creator.FitnessMax)

# 2. Toolbox (Registro dos Operadores)
toolbox = base.Toolbox()

# Parâmetros da suíte
SUITE_SIZE = 8  # número de casos de teste por indivíduo/suíte

# Domínio de valores para os genes
POSSIBLE_Z_VALUES = ["alpha", "beta", "gamma", "delta", "epsilon", "omega"]
X_RANGE = (-100, 100)
Y_RANGE = (-100, 100)

# Geração de Genes: Funções para criar valores aleatórios para x, y, e z
toolbox.register("attr_x", random.randint, X_RANGE[0], X_RANGE[1])
toolbox.register("attr_y", random.randint, Y_RANGE[0], Y_RANGE[1])
toolbox.register("attr_z", random.choice, POSSIBLE_Z_VALUES)

# Um caso de teste é uma tripla [x, y, z]
def _make_case():
    return [toolbox.attr_x(), toolbox.attr_y(), toolbox.attr_z()]

toolbox.register("attr_case", _make_case)

# Geração de Indivíduos (suítes) e População
# Cada indivíduo é uma lista de 'SUITE_SIZE' casos de teste
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_case, n=SUITE_SIZE)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

# Função de Avaliação (Fitness) da suíte
from typing import List, Tuple

def evaluate_coverage_suite(individual: List[List[Any]]) -> Tuple[int,]:
    """Executa a suíte de casos e retorna o número de ramos únicos cobertos (0..TOTAL_BRANCHES)."""
    covered: Set[int] = set()
    for case in individual:
        # Garante formato [x, y, z]
        if not isinstance(case, (list, tuple)) or len(case) != 3:
            continue
        x, y, z = case
        instrument.reset()
        try:
            classificador_complexo(int(x), int(y), str(z))
        except Exception:
            # Casos inválidos simplesmente não contribuem
            continue
        covered.update(instrument.get_coverage())
        # Early stop se já atingimos cobertura total
        if len(covered) == TOTAL_BRANCHES:
            break
    return (len(covered),)

toolbox.register("evaluate", evaluate_coverage_suite)

# Operador de Mutação Customizado para suítes
from typing import Any

def clamp(v: int, lo: int, hi: int) -> int:
    return max(lo, min(hi, v))

def mutate_test_suite(individual: List[List[Any]], indpb: float) -> Tuple[List[List[Any]],]:
    """Aplica mutação em cada caso da suíte e nos genes de cada caso.
    indpb: probabilidade de mutação por gene.
    """
    for case in individual:
        # Mutação para x (inteiro)
        if random.random() < indpb:
            case[0] = clamp(int(case[0]) + int(random.gauss(0, 20)), X_RANGE[0], X_RANGE[1])
        # Mutação para y (inteiro)
        if random.random() < indpb:
            case[1] = clamp(int(case[1]) + int(random.gauss(0, 20)), Y_RANGE[0], Y_RANGE[1])
        # Mutação para z (string)
        if random.random() < indpb:
            case[2] = random.choice(POSSIBLE_Z_VALUES)
    return (individual,)

# Registro dos operadores genéticos padrão
toolbox.register("mate", tools.cxTwoPoint)
# Probabilidade mais baixa por gene, pois há vários genes em uma suíte
toolbox.register("mutate", mutate_test_suite, indpb=0.15)
toolbox.register("select", tools.selTournament, tournsize=3)

print("✅ Toolbox do DEAP configurada para o problema de SBST (indivíduo = suíte de testes).")

# @title Execução do Algoritmo Genético E Coleta de Resultados

def run_sbst_ga():
    """Executa o algoritmo genético para gerar suítes de teste."""
    pop_size = 120
    num_generations = 40
    
    pop = toolbox.population(n=pop_size)
    # HallOfFame armazena as melhores suítes (maior cobertura)
    hof = tools.HallOfFame(min(pop_size, 200))
    
    # Estatísticas para acompanhar a evolução
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", np.mean)
    stats.register("max", np.max)
    
    # Executa o algoritmo evolutivo
    start_time = time.time()
    pop, logbook = algorithms.eaSimple(pop, toolbox, cxpb=0.7, mutpb=0.3,
                                       ngen=num_generations, stats=stats,
                                       halloffame=hof, verbose=True)
    end_time = time.time()
    
    print(f"⏳ Tempo de execução: {end_time - start_time:.2f} segundos")
    return logbook, hof

logbook, hof = run_sbst_ga()

# Saída de Célula Esperada:
# gen\tnevals\tavg \tmax
# 0  \t120   \t2.0 \t3
# ...
# 10 \t...   \t3.5 \t5
# ...
# 25 \t...   \t4.7 \t6  <-- máxima possível (6 ramos)
# 40 \t...   \t~5.0\t6

# @title Análise do Conjunto de Testes Gerado

from typing import Set, List, Dict

def build_test_suite(hall_of_fame: tools.HallOfFame) -> tuple[Set[int], Dict[int, List[Any]]]:
    """
    Constrói um conjunto de testes mínimo a partir do HallOfFame para cobrir todos os ramos encontrados.
    Cada entrada do HoF é uma SUÍTE; percorremos os casos dentro de cada suíte e mapeamos o primeiro caso que cobre
    cada ramo ainda não coberto.
    """
    final_test_suite: Dict[int, List[Any]] = {}
    overall_covered_branches: Set[int] = set()
    
    # Itera sobre as melhores suítes encontradas
    for suite in hall_of_fame:
        for case in suite:
            instrument.reset()
            try:
                classificador_complexo(*case)
            except Exception:
                continue
            branches_covered_by_case = set(instrument.get_coverage())
            # Verifica se este caso de teste cobre algum ramo NOVO
            newly_covered = branches_covered_by_case - overall_covered_branches
            if newly_covered:
                for branch_id in newly_covered:
                    if branch_id not in final_test_suite:
                        final_test_suite[branch_id] = case
                overall_covered_branches.update(newly_covered)
            
            # Para se já cobrimos todos os ramos possíveis
            if len(overall_covered_branches) == TOTAL_BRANCHES:
                break
        if len(overall_covered_branches) == TOTAL_BRANCHES:
            break
            
    return overall_covered_branches, final_test_suite

total_coverage, test_suite = build_test_suite(hof)

print("--- Análise do Conjunto de Testes Final ---")
print(f"🎯 Cobertura de Ramos Atingida: {len(total_coverage)} de {TOTAL_BRANCHES} ({len(total_coverage)/TOTAL_BRANCHES:.1%})")

print("📜 Casos de Teste Selecionados:")
if not test_suite:
    print("Nenhum caso de teste efetivo foi gerado.")
else:
    for branch, case in sorted(test_suite.items()):
        formatted_case = f"(x={int(case[0])}, y={int(case[1])}, z='{str(case[2])}')"
        print(f"  - Ramo #{branch}: coberto por {formatted_case}")

# Saída de Célula Esperada:
# --- Análise do Conjunto de Testes Final ---
# 🎯 Cobertura de Ramos Atingida: 6 de 6 (100.0%)
# 📜 Casos de Teste Selecionados:
#   - Ramo #1: coberto por (x=52, y=2, z='beta')
#   - Ramo #2: coberto por (x=83, y=68, z='gamma')
#   - Ramo #3: coberto por (x=1, y=60, z='alpha')
#   - Ramo #4: coberto por (x=1, y=80, z='beta')
#   - Ramo #5: coberto por (x=42, y=9, z='omega')
#   - Ramo #6: coberto por (x=1, y=60, z='beta')

# @title Gráfico de Convergência da Cobertura

def plot_coverage_evolution(logbook):
    """Plota a evolução da cobertura máxima e média ao longo das gerações (0..TOTAL_BRANCHES)."""
    gen = logbook.select("gen")
    max_coverage = logbook.select("max")
    avg_coverage = logbook.select("avg")

    fig, ax1 = plt.subplots(figsize=(12, 6))

    # Gráfico da cobertura
    ax1.plot(gen, max_coverage, "b-", label="Cobertura Máxima por Geração")
    ax1.plot(gen, avg_coverage, "g--", label="Cobertura Média da População")
    ax1.set_xlabel("Geração")
    ax1.set_ylabel("Número de Ramos Cobertos", color="b")
    ax1.tick_params(axis='y', labelcolor='b')
    ax1.set_ylim(0, TOTAL_BRANCHES + 1)
    
    # Linha de 100% de cobertura
    ax1.axhline(y=TOTAL_BRANCHES, color='r', linestyle=':', label=f'100% Cobertura ({TOTAL_BRANCHES} ramos)')

    plt.title("Evolução da Cobertura de Ramos ao Longo das Gerações (Suítes)")
    fig.legend(loc="center right", bbox_to_anchor=(0.9, 0.5))
    fig.tight_layout()
    plt.grid(True, linestyle='--', alpha=0.6)
    plt.show()

plot_coverage_evolution(logbook)

# [GRÁFICO MOSTRANDO A LINHA DE COBERTURA MÁXIMA SUBINDO EM DEGRAUS ATÉ ATINGIR O VALOR 6]
# [A LINHA DE COBERTURA MÉDIA SOBE MAIS SUAVEMENTE, MAS TAMBÉM COM TENDÊNCIA DE ALTA]