# Copyright 2016, VIXL authors
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
#
#   * Redistributions of source code must retain the above copyright notice,
#     this list of conditions and the following disclaimer.
#   * Redistributions in binary form must reproduce the above copyright notice,
#     this list of conditions and the following disclaimer in the documentation
#     and/or other materials provided with the distribution.
#   * Neither the name of ARM Limited nor the names of its contributors may be
#     used to endorse or promote products derived from this software without
#     specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS CONTRIBUTORS "AS IS" AND
# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

import itertools
import random
import os.path
from copy import deepcopy

class OperandList(object):
  """
  Convenience class representing a list of operand objects. It can be viewed is
  an iterator over operand objects.

  Attributes:
    operand_list
  """

  def __init__(self, operand_list):
    self.operand_list = operand_list

  def __iter__(self):
    return iter(self.operand_list)

  def unwrap(self):
    """
    Return a list of `Operand` objects, unwrapping `OperandWrapper` objects into
    `Operand` objects. For example:

    ~~~
    Condition, Register, Operand(Register, Shift, Register)
    ~~~

    Unwraps to:

    ~~~
    Condition, Register, Register, Shift, Register
    ~~~
    """
    return itertools.chain(*self.operand_list)

  def ExcludeVariants(self, type_name, variant_to_exclude):
    """
    Remove variants in `variant_to_exclude` from operands with type `type_name`.
    """
    # Find the list of operand with type `type_name`.
    relevant_operands = filter(lambda operand: operand.type_name == type_name,
                               self)
    for operand in relevant_operands:
      # Remove the intersection of the existing variants and variants we do not
      # want.
      for variant in set(operand.variants) & set(variant_to_exclude):
        operand.variants.remove(variant)

  def GetNames(self):
    """
    Return the list of all `Operand` names, excluding `OperandWrapper` objects.
    """
    return [operand.name for operand in self.unwrap()]


class InputList(object):
  """
  Convevience class representing a list of input objects.

  This class is an iterator over input objects.

  Attributes:
    inputs
  """

  def __init__(self, inputs):
    self.inputs = inputs

  def __iter__(self):
    return iter(self.inputs)

  def GetNames(self):
    """
    Return the list of input names.
    """
    return [input.name for input in self]


class TestCase(object):
  """
  Object representation of a test case, as described in JSON. This object is
  used to build sets of operands and inputs that will be used by the generator
  to produce C++ arrays.

  Attributes:
    name            Name of the test case, it is used to name the array to
                    produce.
    seed            Seed value to use for reproducable random generation.
    operand_names   List of operand names this test case covers.
    input_names     List of input names this test case covers.
    operand_filter  Python expression as a string to filter out operands.
    input_filter    Python expression as a string to filter out inputs.
    operand_limit   Optional limit of the number of operands to generate.
    input_limit     Optional limit of the number of inputs to generate.
    it_condition    If not None, an IT instruction needs to be generated for the
                    instruction under test to be valid. This member is a string
                    template indicating the name of the condition operand, to be
                    used with "format". For example, it will most likely have
                    the value "{cond}".
  """

  # Declare functions that will be callable from Python expressions in
  # `self.operand_filter`.
  operand_filter_runtime = {
      'register_is_low': lambda register:
          register in ["r0", "r1", "r2", "r3", "r4", "r5", "r6", "r7"]
  }

  def __init__(self, name, seed, operand_names, input_names, operand_filter,
               input_filter, operand_limit, input_limit, it_condition):
    self.name = name
    self.seed = seed
    self.operand_names = operand_names
    self.input_names = input_names
    self.operand_filter = operand_filter
    self.input_filter = input_filter
    self.operand_limit = operand_limit
    self.input_limit = input_limit
    self.it_condition = it_condition

  def GenerateOperands(self, operand_types):
    """
    Generate a list of tuples, each tuple describing what operands to pass to an
    instruction to encode it. We use this to generate operand definitions.

    The algorithm used is a simple product of all operand variants. To limit
    what we generate, we choose to apply the product only on operands with their
    name in the `self.operand_names` list.

    Additionally, we use the Python expression in `self.operand_filter` to
    filter out tuples we do not want.

    Argument:
      operand_types  The `OperandList` object that describe the form of the
                     instruction to generate code for.
    """
    # Build a list of all possible variants as a list of tuples. If the
    # operand's name is not in `self.operand_names`, then we restrict the list
    # to contain default variant. Each tuple in the list has the form
    # `(name, [variant1, variant2, ...])`. For example:
    #
    #   [
    #     ('cond', ['al', 'ne', 'eq', ...]), # All condition variants.
    #     ('rd', ['r0', 'r1', ...]),         # All register variants.
    #     ('rn', ['r0'])                     # Default register variant (r0).
    #     ...
    #   ]
    variants = [
        [(operand_type.name, variant) for variant in operand_type.variants]
            if operand_type.name in self.operand_names
            else [(operand_type.name, operand_type.default)]
        for operand_type in operand_types.unwrap()
    ]
    lambda_string = "lambda {args}: {expression}".format(
        args=",".join(operand_types.GetNames()),
        expression=self.operand_filter)
    filter_lambda = eval(lambda_string, self.operand_filter_runtime)

    def BuildOperandDefinition(operands):
      """
      Take a list of tuples describing the operands and build a definition from
      it. A definition is a tuple with a list of variants and a
      `expect_instruction_before` string.

      For example, we are turning this:

        [
          ('cond', 'ne'),
          ('rd', 'r0'),
          ('rn', 'r1'),
          ('rm', 'r0)
        [

      Into:

        (['ne', 'r0', 'r1', 'r0'], "It ne;")

      """
      return (
        # Build a list of operands by only keeping the second element of each
        # tuple.
        [operand[1] for operand in operands],
        # The next field is a boolean indicating if the test case needs to
        # generate an IT instruction.
        "true" if self.it_condition else "false",
        # If so, what condition should it be?
        self.it_condition.format(**dict(operands)) if self.it_condition else "al"
      )

    # Build and return a list of operand definitions by computing the product of
    # all variants and filtering them with `filter_lambda`.
    #
    # Operand definitions consist of a list with a list of variants and an
    # optional `expect_instruction_before` string. For example:
    #
    #   [
    #     (['al', 'r0', 'r1', 'r2'], ""),
    #     (['ne', 'r0', 'r1', 'r0'], "It ne;"),
    #     ...
    #   ]
    #
    # Here, the filtered product of variants builds a list of lists of tuples, as such:
    #
    #   [
    #     [('cond', 'al'), ('rd', 'r0'), ('rn', 'r1'), ('rn', 'r2')]
    #     [('cond', 'ne'), ('rd', 'r0'), ('rn', 'r1'), ('rn', 'r0')],
    #     ...
    #   ]
    #
    # We then pass them to `BuildOperandDefinition` to produce the expected form
    # out of it.
    result = [
        BuildOperandDefinition(operands)
        for operands in itertools.product(*variants)
        if filter_lambda(**dict(operands))
    ]
    if self.operand_limit is None:
      return result
    else:
      # Use a fixed seed to randomly choose a limited set of operands.
      random.seed(self.seed)
      return random.sample(result, self.operand_limit)

  def GenerateInputs(self, input_types):
    """
    Generate a list of tuples, each tuple describing what input to pass to an
    instruction at runtime. We use this to generate input definitions.

    The algorithm used is a simple product of all input values. To limit what
    we generate, we choose to apply the product only on inputs with their name
    in the `self.input_names` list.

    Additionally, we use the Python expression in `self.input_filter` to filter
    out tuples we do not want.

    Argument:
      input_types  The `InputList` object describing the list of inputs the
                   instruction can take.
    """
    # Build a list of all possible values as a list of lists. If the input's
    # name is not in `self.input_names`, then we restrict the list to the
    # default value.
    values = [
        input_type.values
            if input_type.name in self.input_names else [input_type.default]
        for input_type in input_types
    ]
    lambda_string = "lambda {args}: {expression}".format(
        args=", ".join(input_types.GetNames()),
        expression=self.input_filter)
    filter_lambda = eval(lambda_string)
    # Build and return a list of input definitions, such as
    # [('NoFlag', '0xffffffff', 0xabababab'), ...] for example.
    result = [
        input_definition
        for input_definition in itertools.product(*values)
        if filter_lambda(*input_definition)
    ]
    if self.input_limit is None:
      return result
    else:
      # Use a fixed seed to randomly choose a limited set of inputs.
      random.seed(self.seed)
      return random.sample(result, self.input_limit)


class Generator(object):
  """
  A `Generator` object contains all information needed to generate a test file.
  Each method will return a string used to fill a variable in a template.


  Attributes:
    test_name  Name of the test inferred from the name of the configuration
               file. It has the following form: `type-op1-op2-op3-isa`.
    test_type  Type of the test, extracted from test_name.
    mnemonics  List of instruction mnemonics.
    operands   `OperandList` object.
    inputs     `InputList` object.
    test_cases  List of `TestCase` objects.
  """

  def __init__(self, test_name, test_isa, test_type, mnemonics, operands,
               inputs, test_cases):
    self.test_name = test_name
    self.test_isa = test_isa
    self.test_type = test_type
    self.mnemonics = mnemonics
    self.inputs = inputs
    self.test_cases = test_cases

    # A simulator test cannot easily make use of the PC and SP registers.
    if self.test_type == "simulator":
      # We need to explicitely create our own deep copy the operands before we
      # can modify them.
      self.operands = deepcopy(operands)
      self.operands.ExcludeVariants("Register", ["r13", "r15"])
    else:
      self.operands = operands

  def MnemonicToMethodName(self, mnemonic):
    if self.test_type in ["simulator", "macro-assembler"]:
      # Return a MacroAssembler method name
      return mnemonic.capitalize()
    else:
      # Return an Assembler method name
      method_name = mnemonic.lower()
      return "and_" if method_name == "and" else method_name

  def InstructionListDeclaration(self):
    """
    ~~~
    M(Adc)  \
    M(Adcs) \
    M(Add)  \
    M(Adds) \
    M(And)  \
    ...
    ~~~
    """
    return "".join([
      "M({}) \\\n".format(self.MnemonicToMethodName(mnemonic))
      for mnemonic in self.mnemonics
    ])

  def OperandDeclarations(self):
    """
    ~~~
    Condition cond;
    Register rd;
    Register rn;
    ...
    ~~~
    """
    return "".join([operand.Declare() for operand in self.operands])

  def InputDeclarations(self):
    """
    ~~~
    uint32_t cond;
    uint32_t rd;
    uint32_t rn;
    ...
    ~~~
    """
    return "".join([input.Declare() for input in self.inputs])

  def InputDefinitions(self):
    """
    ~~~
    static const Inputs kCondition[] = {{...},{...}, ...};
    static const Inputs kRdIsRd[] = {{...},{...}, ...};
    ...
    ~~~
    """
    def InputDefinition(test_input):
      inputs = [
          "{{{}}}".format(",".join(input))
          for input in test_input.GenerateInputs(self.inputs)
      ]

      return """static const Inputs k{name}[] = {{ {input} }};
          """.format(name=test_input.name, input=",".join(inputs))

    return "\n".join(map(InputDefinition, self.test_cases))

  def TestCaseDefinitions(self):
    """
    For simulator tests:
    ~~~
    {{eq, r0, r0, ...},
     "eq r0 r0 ...",
     "Condition_eq_r0_...",
     ARRAY_SIZE(kCondition), kCondition},
    ...
    {{eq, r0, r0, ...},
     "eq r0 r0 ...",
     "RdIsRd_eq_r0_...",
     ARRAY_SIZE(kRdIsRd), kRdIsRn},
    ...
    ~~~

    For assembler tests:
    ~~~
    {{eq, r0, r0, ...},
     "",
     "eq r0 r0 ...",
     "Condition_eq_r0_...",
    ...
    {{eq, r0, r0, ...},
     "",
     "eq r0 r0 ...",
     "RdIsRd_eq_r0_..."}
    ...
    {{eq, r0, r0, ...},
     "It eq",
     "eq r0 r0 ...",
     "RdIsRd_eq_r0_..."}
    ...
    ~~~
    """
    def SimulatorTestCaseDefinition(test_case):
      test_cases = [
          """{{ {{ {operands} }},
             "{operands_description}",
             "{identifier}",
             ARRAY_SIZE(k{test_case_name}),
             k{test_case_name} }}
              """.format(operands=",".join(operand),
                         operands_description=" ".join(operand),
                         identifier=test_case.name + "_" + "_".join(operand),
                         test_case_name=test_case.name)
          for operand, _, _ in test_case.GenerateOperands(self.operands)
      ]
      return ",\n".join(test_cases)

    def AssemblerTestCaseDefinition(test_case):
      test_cases = [
          """{{ {{ {operands} }},
             {in_it_block},
             {it_condition},
             "{operands_description}",
             "{identifier}" }}
              """.format(operands=",".join(operand),
                         in_it_block=in_it_block,
                         it_condition=it_condition,
                         operands_description=" ".join(operand),
                         identifier="_".join(operand))
          for operand, in_it_block, it_condition
              in test_case.GenerateOperands(self.operands)
      ]
      return ",\n".join(test_cases)

    def MacroAssemblerTestCaseDefinition(test_case):
      test_cases = [
          """{{ {{ {operands} }},
             "{operands_description}",
             "{identifier}" }}
              """.format(operands=",".join(operand),
                         operands_description=", ".join(operand),
                         identifier="_".join(operand))
          for operand, _, _ in test_case.GenerateOperands(self.operands)
      ]
      return ",\n".join(test_cases)

    if self.test_type == "simulator":
      return ",\n".join(map(SimulatorTestCaseDefinition, self.test_cases))
    elif self.test_type == "assembler":
      return ",\n".join(map(AssemblerTestCaseDefinition, self.test_cases))
    elif self.test_type == "macro-assembler":
      return ",\n".join(map(MacroAssemblerTestCaseDefinition, self.test_cases))
    else:
      raise Exception("Unrecognized test type \"{}\".".format(self.test_type))

  def IncludeTraceFiles(self):
    """
    ~~~
    #include "aarch32/traces/sim-...-a32.h"
    #include "aarch32/traces/sim-...-a32.h"
    ...
    ~~~
    """
    operands = "-".join(self.operands.GetNames())
    return "".join([
        "#include \"aarch32/traces/" + self.GetTraceFileName(mnemonic) + "\"\n"
        for mnemonic in self.mnemonics
    ])

  def MacroAssemblerMethodArgs(self):
    """
    ~~~
    Condition cond, Register rd, Register rm, const Operand& immediate
    ~~~
    """
    return ", ".join([
        operand.GetArgumentType() + " " + operand.name
        for operand in self.operands
    ])

  def MacroAssemblerSetISA(self):
    """
    Generate code to set the ISA.
    """
    if self.test_isa == "t32":
      return "masm.UseT32();"
    else:
      return "masm.UseA32();"

  def CodeInstantiateOperands(self):
    """
    ~~~
    Condition cond = kTests[i].operands.cond;
    Register rd = kTests[i].operands.rd;
    ...
    ~~~
    """
    code = "".join([operand.Instantiate() for operand in self.operands])
    if self.test_type in ["simulator", "macro-assembler"]:
      # Simulator tests need scratch registers to function and uses
      # `UseScratchRegisterScope` to dynamically allocate them. We need to
      # exclude all register operands from the list of available scratch
      # registers.
      # MacroAssembler test also need to ensure that they don't try to run tests
      # with registers that are scratch registers; the MacroAssembler contains
      # assertions to protect against such usage.
      excluded_registers = [
          "scratch_registers.Exclude({});".format(operand.name)
          for operand in self.operands.unwrap()
          if operand.type_name == "Register"
      ]
      return code + "\n".join(excluded_registers)
    return code

  def CodePrologue(self):
    """
    ~~~
    __ Ldr(rn, MemOperand(input_ptr, offsetof(Inputs, rn)));
    __ Ldr(rm, MemOperand(input_ptr, offsetof(Inputs, rm)));
    ...
    ~~~
    """
    return "".join([input.Prologue() for input in self.inputs])

  def CodeEpilogue(self):
    """
    ~~~
    __ Str(rn, MemOperand(result_ptr, offsetof(Inputs, rn)));
    __ Str(rm, MemOperand(result_ptr, offsetof(Inputs, rm)));
    ...
    ~~~
    """
    return "".join([input.Epilogue() for input in self.inputs])

  def CodeParameterList(self):
    """
    ~~~
    cond, rd, rn, immediate
    ~~~
    """
    return ", ".join([
        operand.name
        for operand in self.operands
    ])

  def TracePrintOutputs(self):
    """
    ~~~
    printf("0x%08" PRIx32, results[i]->outputs[j].cond);
    printf(", ");
    printf("0x%08" PRIx32, results[i]->outputs[j].rd);
    printf(", ");
    ...
    ~~~
    """
    return "printf(\", \");".join(
        [input.PrintOutput() for input in self.inputs])


  def CheckInstantiateResults(self):
    """
    ~~~
    uint32_t cond = results[i]->outputs[j].cond;
    uint32_t rd = results[i]->outputs[j].rd;
    ...
    ~~~
    """
    return "".join([input.InstantiateResult() for input in self.inputs])

  def CheckInstantiateInputs(self):
    """
    ~~~
    uint32_t cond_input = kTests[i].inputs[j].cond;
    uint32_t rd_input = kTests[i].inputs[j].rd;
    ...
    ~~~
    """
    return "".join([input.InstantiateInput("_input") for input in self.inputs])

  def CheckInstantiateReferences(self):
    """
    ~~~
    uint32_t cond_ref = reference[i].outputs[j].cond;
    uint32_t rd_ref = reference[i].outputs[j].rd;
    ...
    ~~~
    """
    return "".join([input.InstantiateReference("_ref") for input in self.inputs])

  def CheckResultsAgainstReferences(self):
    """
    ~~~
    (cond != cond_ref) || (rd != rd_ref) || ...
    ~~~
    """
    return " || ".join([input.Compare("", "!=", "_ref") for input in self.inputs])

  def CheckPrintInput(self):
    """
    ~~~
    printf("0x%08" PRIx32, cond_input);
    printf(", ");
    printf("0x%08" PRIx32, rd_input);
    printf(", ");
    ...
    ~~~
    """
    return "printf(\", \");".join(
        [input.PrintInput("_input") for input in self.inputs])

  def CheckPrintExpected(self):
    """
    ~~~
    printf("0x%08" PRIx32, cond_ref);
    printf(", ");
    printf("0x%08" PRIx32, rd_ref);
    printf(", ");
    ...
    ~~~
    """
    return "printf(\", \");".join(
        [input.PrintInput("_ref") for input in self.inputs])

  def CheckPrintFound(self):
    """
    ~~~
    printf("0x%08" PRIx32, cond);
    printf(", ");
    printf("0x%08" PRIx32, rd);
    printf(", ");
    ...
    ~~~
    """
    return "printf(\", \");".join(
        [input.PrintInput("") for input in self.inputs])

  def TestName(self):
    """
    ~~~
    SIMULATOR_COND_RD_RN_RM_...
    ~~~
    """
    return self.test_type.replace("-", "_").upper() + "_" + \
        self.test_name.replace("-", "_").upper()

  def GetTraceFileName(self, mnemonic):
    """
    Return the name of a trace file for a given mnemonic.
    """
    return self.test_type + "-" + self.test_name + "-" + \
        mnemonic.lower() + ".h"

  def WriteEmptyTraces(self, output_directory):
    """
    Write out empty trace files so we can compile the new test cases.
    """
    for mnemonic in self.mnemonics:
      # The MacroAssembler tests have no traces.
      if self.test_type == "macro-assembler": continue

      with open(os.path.join(output_directory, self.GetTraceFileName(mnemonic)),
                "w") as f:
        code = "static const TestResult *kReference{} = NULL;\n"
        f.write(code.format(self.MnemonicToMethodName(mnemonic)))

  def GetIsaGuard(self):
    """
    This guard ensure the ISA of the test is enabled.
    """
    if 'A32' in self.TestName():
      return 'VIXL_INCLUDE_TARGET_A32'
    else:
      assert 'T32' in self.TestName()
      return 'VIXL_INCLUDE_TARGET_T32'