run

#!/usr/bin/env python3
# Builds EqBench programs and compares them,
# returns results how much successful was the comparison.
#
# Requirements: tabulate, progressbar
#
# References:
# - EqBench paper:
#   https://people.ece.ubc.ca/mjulia/publications/EQBench_2021.pdf
# - EqBench benchmarks: https://osf.io/93s5b/
# - EqBench repo: https://github.com/shrBadihi/EqBench
# - useful info from author of EqBench:
#   https://github.com/shrBadihi/EqBench/issues/2
#
# Steps to analyse DiffKemp equivalence checking using an EqBench benchmark:
# 1. download/clone the benchmark (EqBench folder)
#   from https://github.com/shrBadihi/EqBench (contains fixes)
# 2. Run this script:
#   `EqBench-workflow/run <path-to-EqBench>`
#   - it creates snapshots of programs and compares them
#   - the script informs about progress and prints result of analysis.
# 3. Detailed results of the analysis are saved in
#   <output-dir>/eqbench-results.csv (default `output-dir` is EqBench-results),
#   you can filter the result for eg. with `grep`,
#   the file is in csv format with headers
#   `type;benchmark;program;expected;result;correct;changes`
#   - `type`: type of EqBench program
#     - `aggregated`: an aggregated form of all other subfolders for a project
#     - `function-level`: for projects/programs which contains change in
#       a single function the comparison is done on function-level
#       (compared function is the one which contains changes),
#     - `program-level`: for projects/programs which contains change in
#       a single function but the comparison have to be done on program-level
#       (compared function doesn't have changes but calls function which does),
#   - `benchmark`, `program`: represents name of benchmark and program,
#   - `expected`: represents expected result of comparison (Eq/Neq)
#   - `result`: represents result of DiffKemp comparison (Eq/Neq),
#     for aggregated type if comparison was incorrect contains info
#     about which functions were evaluated as Eq and which as Neq,
#   - `correct`: True if evaluation was correct, else False,
#   - `changes`: list of changes which were done in the program.

from argparse import ArgumentParser
from collections import defaultdict
import csv
import tabulate
from pathlib import Path
from progressbar import ProgressBar
import json
import re
import shutil
import subprocess
import sys
import yaml

# regex for getting info from diffkemp report stat
REGEX_TOTAL = re.compile("^Total symbols: *(\\d+)", flags=re.MULTILINE)
REGEX_EQUAL = re.compile("^Equal: *(\\d+)", flags=re.MULTILINE)
REGEX_NEQUAL = re.compile("^Not equal: *(\\d+)", flags=re.MULTILINE)

BENCHMARK_DIR = "benchmarks"
BUILD_DIR = "benchmarks-build"
COMPARE_DIR = "benchmarks-compare"

# Name of file which describes EqBench programs.
DESCRIPTION_FILE_NAME = "C-Desc.json"

# Functions to ignore for aggregated programs because these functions
# have not been changed and does not call function which was changed.
# Dictionary
# - keys being paths to version of program,
# - values being list of functions to ignore
AGGREGATED_FUNS_TO_IGNORE = {
    "ej_hash/ej_hash/Neq": ["constructor"],
    "ej_hash/ej_hash/Eq": ["constructor"],
    "raytrace/raytrace/Neq": ["Vector3DConstructor",
                              "Vector3DConstructor2",
                              "SurfaceConstructor"],
    "raytrace/raytrace/Eq": ["Vector3DConstructor",
                             "Vector3DConstructor2",
                             "SurfaceConstructor"],
    "tcas/tcas/Neq": ["Own_Below_Threat", "Own_Above_Threat",
                      "Inhibit_Biased_Climb", "ALIM"],
    "tcas/tcas/Eq": ["Own_Below_Threat", "Own_Above_Threat",
                     "Inhibit_Biased_Climb", "ALIM"],
    "ell/ellProgram/Neq": ["SQR", "SIGN", "MAX", "MIN"],
    "ell/ellProgram/Eq": ["SQR", "SIGN", "MAX", "MIN"],
    "gam/gam/Neq": ["gammln"],
    "gam/gam/Eq": ["gammln"],
    "frenel/frenelProgram/Neq": ["getreal", "getimag", "constructor",
                                 "constructor2", "assign", "assignObj", "plus",
                                 "minus", "multiply", "divide"],
    "frenel/frenelProgram/Eq": ["getreal", "getimag", "constructor",
                                "constructor2", "assign", "assignObj", "plus",
                                "minus", "multiply", "divide"],
}


class ProgramInfo:
    """Information about EqBench program."""
    def __init__(self, src_dir):
        """:param src_dir: Path to EqBench program."""
        with open(Path(src_dir, DESCRIPTION_FILE_NAME), "r") as file:
            info = json.load(file)
        self.fun_to_compare = info["function name"]
        # For some programs (eg programs for CLEVER benchmark)
        # is necessary to do program-level analysis.
        # For these programs the name of function which should be compared
        # is probably specified after a dot in program name.
        self.program_fun = info["program name"].split(".")[1] \
            if len(info["program name"].split(".")) == 2 else None
        self.changes = info["changes"]

    def get_description(self):
        """Returns string containing list of changes."""
        changes_description = []
        for change in self.changes:
            change_description = f"{change['change type']} " + \
                                 f"({change['change operation']})"
            if change_description not in changes_description:
                changes_description.append(change_description)
        return ", ".join(changes_description)

    @staticmethod
    def exists(src_dir):
        """Checks if information about the EqBench program exists.
        If it does not exists than it is program which
        contains aggregation of all programs/changes for the benchmark.
        :param src_dir: Path to EqBench program."""
        return Path(src_dir, DESCRIPTION_FILE_NAME).exists()


class EqBenchRun:
    """
    Class for running analysis of DiffKemp equivalence checking
    using an EqBench benchmark.
    """
    def __init__(self, args):
        self.src_dir = Path(args.source_dir, BENCHMARK_DIR)
        self.output_dir = Path(args.output_dir)
        self.build_dir = Path(args.output_dir, BUILD_DIR)
        self.cmp_dir = Path(args.output_dir, COMPARE_DIR)
        self.only_compare = args.only_compare
        self.disable_patterns = args.disable_patterns
        self.results_file_path = Path(self.output_dir, "eqbench-results.csv")
        self.clang_options = args.add_clang_options
        self.output_src_file_paths = args.output_src_file_paths
        self.no_opt_override = args.no_opt_override
        self.add_custom_llvm_passes = args.add_custom_llvm_passes
        self._run()
        self.report()

    def _run(self):
        # todo parallel run to speed things up?
        if not self.only_compare:
            if self.output_dir.exists():
                shutil.rmtree(self.output_dir)
            # Creating snapshots
            print("1) Creating snapshots:", file=sys.stderr)
            print("\ta) Creating old snapshots:", file=sys.stderr)
            self._create_snapshots(new=False)
            print("\tb) Creating new snapshots:", file=sys.stderr)
            self._create_snapshots(new=True)

        # Comparing snapshots and writing results to file
        print("2) Comparing snapshots", file=sys.stderr)
        if self.cmp_dir.exists():
            shutil.rmtree(self.cmp_dir)
        with open(self.results_file_path, "w") as results_file:
            if self.output_src_file_paths:
                print("type;benchmark;program;expected;result;" +
                      "correct;changes;old_src;new_src",
                      file=results_file)
            else:
                print("type;benchmark;program;expected;result;correct;changes",
                      file=results_file)
            print("\ta) Comparing Eq snapshots", file=sys.stderr)
            self._compare_snapshots(neq=False, results_file=results_file)
            print("\tb) Comparing Neq snapshots", file=sys.stderr)
            self._compare_snapshots(neq=True, results_file=results_file)
        print(f"\n\nResults are written to {str(self.results_file_path)}\n\n")

    def _create_snapshots(self, new):
        """Creates snapshots for benchmarks programs.
        :param new: If true creates snapshots of new versions of programs,
                    else of old versions.
        """
        # some files are name old.c/new.c and some oldV.c/newV.c
        # TODO count of programs specified in paper and located in dir
        # does not match
        name = "old" if not new else "new"
        files = list(Path(self.src_dir).glob(f"**/{name}*.c"))
        progressbar = ProgressBar()
        for file in progressbar(files):
            # getting relative path to program folder
            # (benchmark/program/eq_or_neq)
            rel_path_to_file = file.relative_to(self.src_dir).parent
            output_path = self.build_dir / rel_path_to_file / name
            output_path.mkdir(parents=True, exist_ok=True)
            self._build(str(file), str(output_path))

    def _build(self, file, output_dir):
        """Creates snapshot of C `file` and saves it to `output_dir`."""
        build_command = self.get_build_command()
        build_command.extend([file, output_dir])

        subprocess.check_call(build_command, stdout=subprocess.DEVNULL)

        if self.add_custom_llvm_passes:
            llvm_file_path = str(next(Path(output_dir).glob("*.ll")))
            subprocess.check_call(["opt", llvm_file_path,
                                   f"-passes={self.add_custom_llvm_passes}",
                                   "-S", "-o", llvm_file_path])

    def get_build_command(self):
        """Creates build command, does not include src file and output dir."""
        build_command = [
            "bin/diffkemp",
            "build",
        ]
        for option in self.clang_options:
            build_command.append(f"--clang-append={option.strip()}")
        if self.no_opt_override:
            build_command.append("--no-opt-override")
        return build_command

    def _compare_snapshots(self, neq, results_file):
        """Compares benchmarks snapshots of old and new programs version.
        :param neq: If true compares not equal programs,
                    else compares equal programs.
        :param results_file: FD of file to write results of evaluation.
        """
        expected_result = "Eq" if not neq else "Neq"
        build_dirs = list(Path(self.build_dir).glob(f"**/{expected_result}"))
        progressbar = ProgressBar()
        for build_dir in progressbar(build_dirs):
            self._compare_snapshot(build_dir, expected_result, results_file)

    def _compare_snapshot(self, build_dir, expected_result, results_file):
        """Compares two snapshots (old, new) using DiffKemp
        and writes info about evaluation to `results_file`
        :param build_dir: Path to dir containing old/new subdirs with
                          program snapshots.
        :param expected_result: Expected result - Eq/Neq.
        :param results_file: FD to file to which to write results of eval.
        """
        old_build_dir = build_dir / "old"
        new_build_dir = build_dir / "new"

        src_dir = self.src_dir / build_dir.relative_to(self.build_dir)
        # directory containing result of comparison
        result_dir = self.cmp_dir / build_dir.relative_to(self.build_dir)
        result_dir.parent.mkdir(parents=True, exist_ok=True)

        program_info = ProgramInfo(src_dir) if ProgramInfo.exists(src_dir) \
            else None

        # If EqBench program contains info about program, the program
        # should contain change in only one function,
        # get the name of function from the information about the program
        # and compare only this function.
        function = None
        benchmark_type = "aggregated"
        if program_info:
            # Some functions cannot be compared on function-level but must
            # be compared on program-level to be correctly evaluated.
            if program_info.program_fun:
                benchmark_type = "program-level"
                function = program_info.program_fun
            else:
                benchmark_type = "function-level"
                function = program_info.fun_to_compare

        output = self._compare(str(old_build_dir), str(new_build_dir),
                               str(result_dir), function=function)

        result = AnalysisResult(program_info=program_info,
                                expected_result=expected_result,
                                old_build_dir=old_build_dir,
                                result_dir=result_dir,
                                output=output,
                                benchmark_type=benchmark_type)
        if self.output_src_file_paths:
            result = str(result) + \
                      f";{next(Path.glob(src_dir, 'old*.c'))}" + \
                      f";{next(Path.glob(src_dir, 'new*.c'))}"
        print(str(result), file=results_file)

    def _compare(self, old_build_dir, new_build_dir, output_dir,
                 function=None):
        """Runs `diffkemp compare` command, returns output of the command.
        :param function: Name of function to compare,
                         if it is None than it compares all functions.
        """
        compare_command = self.get_compare_command()
        compare_command.extend([
            old_build_dir, new_build_dir,
            "-o", output_dir,
            "--report-stat",
        ])
        if function is not None:
            compare_command.extend(["--function", function])
        return subprocess.check_output(compare_command).decode("utf-8")

    def get_compare_command(self):
        """Based on program arguments creates compare command."""
        compare_command = [
            "bin/diffkemp", "compare",
        ]
        if self.disable_patterns:
            compare_command.extend(["--disable-all-patterns"])
        return compare_command

    def report(self):
        """Prints results of evaluation."""
        TYPE = 0
        EXPECTED = 3  # Eq/Neq
        CORRECT = 5  # True/False

        header = ["Type",
                  "Eq correct", "Eq not correct",
                  "Neq correct", "Neq not correct"]
        # dict benchmark_type: [eq correct, eq not correct, neq correct,
        #                       neq not correct]
        results = defaultdict(lambda: [0, 0, 0, 0])
        # mapping result (csv fields `expected:correct`)` to index
        # corresponding to header
        mapping = {
            "Eq:True": 0,
            "Eq:False": 1,
            "Neq:True": 2,
            "Neq:False": 3,
        }
        with open(self.results_file_path, "r") as file:
            reader = csv.reader(file, delimiter=";")
            # skipping header
            next(reader)
            for row in reader:
                index = mapping[f"{row[EXPECTED]}:{row[CORRECT]}"]
                benchmark_type = row[TYPE]
                results[benchmark_type][index] += 1
        report = f"""### Results

- snapshots created using: `{" ".join(self.get_build_command())}`
- snapshots compared using: `{" ".join(self.get_compare_command())}`
"""
        if self.add_custom_llvm_passes:
            report += "- + custom passes were run"
        report += tabulate.tabulate(
            [[benchmark_type, *result]
             for benchmark_type, result in results.items()],
            headers=header, tablefmt="pipe")
        print(report)

        # Saving summarisation of results to file
        report += f"\n\n(only-compare: {self.only_compare})\n"
        with open(Path(self.output_dir, "result.md"), "w") as file:
            print(report, file=file)


class AnalysisResult:
    """Result of evaluation of DiffKemp comparison of EqBench program."""
    def __init__(self, program_info, expected_result, old_build_dir,
                 result_dir, output, benchmark_type):
        """
        :param program_info: Info about benchmark program if it exists or None.
        :param expected_result: The expected result (Eq/Neq) of the comparison.
        :param old_build_dir: Path to snapshot with old version of the program.
        :param result_dir: Path to dir containing results of the comparison.
        :param output: Stdout output of `diffkemp compare` for the program.
        :param benchmark_type: Type of benchmark "aggregate", "function-level",
                               "program-level".
        """
        self.expected_result = expected_result
        self.program_info = program_info
        self.old_build_dir = old_build_dir
        self.result_dir = result_dir
        self.total_symbols = REGEX_TOTAL.search(output).group(1)
        self.eq_symbols = REGEX_EQUAL.search(output).group(1)
        self.neq_symbols = REGEX_NEQUAL.search(output).group(1)
        self.benchmark_type = benchmark_type
        self.benchmark_name, self.program_name = \
            str(result_dir).split("/")[-3:-1]

    def __str__(self):
        # `function-level` type has only one changed function in the file
        # `aggregated` contains multiple changed functions
        if self.total_symbols == self.eq_symbols:
            result = "Eq"
        elif self.total_symbols == self.neq_symbols:
            result = "Neq"
        else:
            # Some evaluated functions were equal some non-equal
            # (can contains functions which were supposed to be ignored),
            # check eq and non-equal functions
            # (ignore the ones which should not be evaluated).
            neq_functions = self._get_neq_funs()
            all_functions = self._get_all_funs()
            eq_functions = list(filter(
                    lambda fun: fun not in neq_functions, all_functions))
            if len(eq_functions) == len(all_functions):
                # All functions which we do not want to ignore are equal.
                result = "Eq"
            elif len(neq_functions) == len(all_functions):
                # All functions which we do not want to ignore are non-equal.
                result = "Neq"
            else:
                # Still some functions are equal and some non-equal.
                result = f"{len(eq_functions)} Eq {eq_functions}, " + \
                        f"{len(neq_functions)} Neq {neq_functions}"
        correct = str(True if result == self.expected_result else False)
        changes = self.program_info.get_description() if self.program_info \
            else ""
        result_repre = [
            self.benchmark_type,
            self.benchmark_name, self.program_name,
            self.expected_result,
            result, correct,
            changes
        ]
        return ";".join(result_repre)

    def _get_neq_funs(self):
        """
        Returns list of functions which were evaluated by DiffKemp as
        non-equal functions.
        """
        with open(self.result_dir / "diffkemp-out.yaml", "r") as file:
            yaml_result = yaml.safe_load(file)
        fun_list = [
            function["function"] for function in yaml_result["results"]]
        # filter out not changed funs for aggregated programs
        return self._remove_funs_to_ignore(fun_list)

    def _get_all_funs(self):
        """Returns list of all functions for an EqBench program."""
        with open(Path(self.old_build_dir, "snapshot.yaml"), "r") as file:
            snapshot_yaml = yaml.safe_load(file)
        fun_list = [function["name"] for function in snapshot_yaml[0]["list"]]
        return self._remove_funs_to_ignore(fun_list)

    def _remove_funs_to_ignore(self, fun_list):
        """Removes functions from the list which should not be compared."""
        relative_path = "/".join(self.result_dir.parts[-3:])
        if self.benchmark_type == "aggregated" and \
           relative_path in AGGREGATED_FUNS_TO_IGNORE:
            fun_list = [item for item in fun_list if item not in
                        AGGREGATED_FUNS_TO_IGNORE[relative_path]]
        return fun_list


if __name__ == "__main__":
    parser = ArgumentParser(
        description="Builds EqBench programs and compares them, " +
                    "returns results how much successful was the comparison.")
    parser.add_argument("source_dir", nargs="?", default="EqBench",
                        help="EqBench source directory")
    parser.add_argument("-o", "--output-dir", default="EqBench-results",
                        help="output directory for the analysis")
    parser.add_argument("--only-compare", action="store_true",
                        help="only runs comparison, expects that " +
                        "the programs are already build " +
                        "and located in `output_dir`")
    parser.add_argument("--disable-patterns", action="store_true",
                        help="disable all built-in patterns in comparison, " +
                        "default patterns are used by default")
    parser.add_argument("--add-clang-options", action="extend", type=str,
                        default=[], nargs="+",
                        help="adds options to clang when creating snapshots" +
                        "(for options containing dashes insert space before" +
                        "or after option)")
    parser.add_argument("--output-src-file-paths", action="store_true",
                        help="saves src files paths to csv")
    parser.add_argument("--no-opt-override", action="store_true",
                        help="use optimization options provided with " +
                        "--add-clang-options")
    parser.add_argument("--add-custom-llvm-passes",
                        help="specify llvm passes to be added")
    args = parser.parse_args()
    EqBenchRun(args)