revng-revng/scripts/monotone_framework_lattice.py

#!/usr/bin/env python3

# This script generates C++ classes from a GraphViz file representing a monotone
# framework and a template file.
#
# The graph should meet the same requirements as monotone_framework.py
#

import argparse
import sys
from collections import defaultdict

import importlib
import monotone_framework


def gen_combine_values(lattice, reachability):
    out = ""

    # Emit the combine operator
    out += """LatticeElement combineValues(const LatticeElement &LHS, const LatticeElement &RHS) {
"""

    node_by_index = lambda index: monotone_framework.get_unique(
        [x for x, x_data in lattice.nodes(data=True) if x_data["index"] == str(index)]
    )

    result = defaultdict(lambda: [])
    for v1, v1_data in lattice.nodes(data=True):
        for v2, v2_data in lattice.nodes(data=True):
            if v1 != v2:
                i1 = int(v1_data["index"])
                i2 = int(v2_data["index"])
                nonzero = lambda i: set([x[0] for x in enumerate(reachability[i]) if x[1] != 0])

                output = max(
                    nonzero(i1) & nonzero(i2),
                    key=lambda i: reachability[i1][i] + reachability[i2][i],
                )
                output = node_by_index(output)

                result[output].append((v1, v2))
                assert output in result

    first = True
    for output, pairs in sorted(result.items(), key=lambda x: x[0]):
        if first:
            out += """  if ("""
        else:
            out += """ else if ("""
        conditions = []
        for this, other in sorted(pairs, key=lambda x: (x[0], x[1])):
            condition = "(LHS == LatticeElement::{} && RHS == LatticeElement::{})"
            condition = condition.format(this, other)
            conditions.append(condition)
        conditions[0] = conditions[0].lstrip()
        conditions_string = "\n      || " if first else "\n             || "
        out += conditions_string.join(conditions)
        out += """) {{
    return LatticeElement::{};
  }}""".format(
            output
        )
        first = False

    out += """
  return LHS;
}

"""
    return out


def gen_is_less_or_equal(lattice, reachability):
    out = ""

    # Emit the comparison operator of the lattice
    out += """bool isLessOrEqual(const LatticeElement &LHS, const LatticeElement &RHS) {
  return LHS == RHS
    || """

    result = []
    for v1, v1_data in lattice.nodes(data=True):
        for v2, v2_data in lattice.nodes(data=True):
            if v1 != v2:
                i1 = int(v1_data["index"])
                i2 = int(v2_data["index"])
                if reachability[i1][i2] != 0:
                    condition = """(LHS == LatticeElement::{} && RHS == LatticeElement::{})"""
                    condition = condition.format(v1, v2)
                    result.append(condition)

    out += "\n    || ".join(result)
    out += """;
}

"""
    return out


def gen_transfer_function(tf_names, transfer_functions):
    out = ""

    # Emit the transfer function implementation
    out += """LatticeElement transfer(TransferFunction T, const LatticeElement &E) {
  switch(T) {
"""
    for tf in tf_names:
        out += """  case TransferFunction::{}:
    switch(E) {{
""".format(
            tf
        )
        for edge in transfer_functions[tf]:
            source, destination = edge
            out += """    case LatticeElement::{}:
      return LatticeElement::{};
""".format(
                source, destination
            )
        out += """    default:
      revng_abort("Invalid LatticeElement value found");
    }

"""

    out += """  default:
    return E;
  }
}

"""
    return out


def gen_lattice_element_enum(lattice):
    out = ""

    # Print the enumeration of all the possible lattice values
    out += """enum LatticeElement {
"""

    # Get all the names
    values = [v for v in lattice.nodes()]
    out += "  " + ",\n  ".join(values) + "\n"
    out += """};
"""
    return out


def gen_transfer_function_enum(tf_graph):
    out = ""

    # Print the enumeration of all the possible transfer functions
    out += """enum TransferFunction {
"""

    # Get all the transfer function names
    tfs = [e_data["label"] for _, _, e_data in tf_graph.edges(data=True)]
    out += "  " + ",\n  ".join(sorted(tfs)) + "\n"
    out += """};

"""
    return out


def process_graph(path, call_arcs):
    input_graph = monotone_framework.load_graph(path)

    monotone_framework.enumerate_graph(input_graph)

    lattice = monotone_framework.extract_lattice(input_graph)

    # Check that the lattice is valid for a monotone framework
    _ = monotone_framework.check_lattice(lattice)

    reachability = monotone_framework.compute_reachability_matrix(lattice)

    tf_graph = monotone_framework.extract_transfer_function_graph(input_graph, call_arcs)

    transfer_functions = defaultdict(lambda: [])
    for src, dst, edge_data in tf_graph.edges(data=True):
        transfer_functions[edge_data["label"]].append((src, dst))

    # Check the monotonicity of the transfer function
    assert monotone_framework.check_transfer_functions(tf_graph, reachability, transfer_functions)

    tf_names = sorted([edge_data["label"] for _, _, edge_data in tf_graph.edges(data=True)])

    extremal_lattice_element = [
        v for v, v_data in lattice.nodes(data=True) if "peripheries" in v_data
    ][0]

    return {
        "transfer_function_names": tf_names,
        "lattice_name": input_graph.name,
        "lattice_elements_enums": gen_lattice_element_enum(lattice),
        "extremal_lattice_element": extremal_lattice_element,
        "transfer_function_enums": gen_transfer_function_enum(tf_graph),
        "is_less_or_equal_definition": gen_is_less_or_equal(lattice, reachability),
        "combine_values_definition": gen_combine_values(lattice, reachability),
        "transfer_function_definition": gen_transfer_function(tf_names, transfer_functions),
    }


def main():
    parser = argparse.ArgumentParser(
        description="Generate C++ code from dot \
  files representing a monotone framework."
    )
    parser.add_argument("--call-arcs", action="store_true", help="Add call arcs.")
    parser.add_argument(
        "template",
        metavar="TEMPLATE",
        help="""Lattice template file.
                      you can use the keywords:
                      - %LatticeName% the name of the lattice extracted from the graph name
                      - %LatticeElement% the C++ enum definition for the elements in the lattice `enum LatticeElement {...}`
                      - %ExtremalLatticeElement% the name for the default value for a lattice element
                      - %TransferFunction% the C++ enum definition for the possible transfer functions `enum TransferFunction {...}`
                      - %isLessOrEqual% the C++ function with signature `bool isLessOrEqual(const LatticeElement &LHS, const LatticeElement &RHS)`
                      - %combineValues% the C++ function with signature `bool combineValues(const LatticeElement &LHS, const LatticeElement &RHS)`
                      - %transfer% the C++ function with signature `bool transfer(TransferFunction T, const LatticeElement &RHS)`
                      """,
    )
    parser.add_argument("inputs", metavar="GRAPH", nargs="+", help="GraphViz input file.")
    args = parser.parse_args()

    # Print the template file
    with open(args.template) as template_file:
        template = template_file.read()

    # Process each input graph
    all_transfer_functions = set()
    for path in args.inputs:
        generated_code = process_graph(path, args.call_arcs)
        all_transfer_functions |= set(generated_code["transfer_function_names"])

    monotone_framework.out(
        template.replace("%LatticeName%", generated_code["lattice_name"])
        .replace("%LatticeElement%", generated_code["lattice_elements_enums"])
        .replace("%ExtremalLatticeElement%", generated_code["extremal_lattice_element"])
        .replace("%TransferFunction%", generated_code["transfer_function_enums"])
        .replace("%isLessOrEqual%", generated_code["is_less_or_equal_definition"])
        .replace("%combineValues%", generated_code["combine_values_definition"])
        .replace("%transfer%", generated_code["transfer_function_definition"])
        .replace(
            "%GeneratedNotice%",
            "// This file has been automatically generated "
            "from scripts/monotone_framework_lattice.py, "
            "please don't change it",
        )
    )

    return 0


if __name__ == "__main__":
    sys.exit(main())