# Copyright lowRISC contributors.
# Licensed under the Apache License, Version 2.0, see LICENSE for details.
# SPDX-License-Identifier: Apache-2.0

import random
from typing import Dict, List, Optional, TextIO, Tuple

from shared.insn_yaml import Insn, InsnsFile


class ProgInsn:
    '''An object representing a single instruction in the generated program

    self.insn is the instruction (as defined in insns.yml).

    self.operands has the encoded value for each operand (see the documentation
    for OperandType for more information).

    self.lsu_info is non-None if (and only if) the instruction is an LSU
    instruction. In this case, it's a pair (mem_type, addr). mem_type is the
    memory type (a key for Model._known_mem). addr is the target address of the
    LSU instruction (it's much easier to store it explicitly than to grovel
    around in the model to figure it out again from register values)

    '''
    def __init__(self,
                 insn: Insn,
                 operands: List[int],
                 lsu_info: Optional[Tuple[str, int]]):
        assert len(insn.operands) == len(operands)
        assert (lsu_info is None) is (insn.lsu is None)
        assert insn.syntax is not None

        self.insn = insn
        self.operands = operands
        self.lsu_info = lsu_info

    def to_asm(self, cur_pc: int) -> str:
        '''Return an assembly representation of the instruction'''
        # Build a dictionary from operand name to value from self.operands,
        # which is a list of operand values in the same order as insn.operands.
        op_vals = {}
        assert len(self.insn.operands) == len(self.operands)
        for operand, enc_val in zip(self.insn.operands, self.operands):
            op_val = operand.op_type.enc_val_to_op_val(enc_val, cur_pc)
            assert op_val is not None
            op_vals[operand.name] = op_val

        return self.insn.disassemble(op_vals, 14)

    def to_json(self) -> object:
        '''Serialize to an object that can be written as JSON'''
        return (self.insn.mnemonic, self.operands, self.lsu_info)

    @staticmethod
    def from_json(insns_file: InsnsFile,
                  where: str,
                  json: object) -> 'ProgInsn':
        '''The inverse of to_json.

        where is a textual description of where we are in the file, used in
        error messages.

        '''
        if not (isinstance(json, list) and len(json) == 3):
            raise ValueError('{}, top-level data is not a triple.'
                             .format(where))

        mnemonic, operands, json_lsu_info = json

        if not isinstance(mnemonic, str):
            raise ValueError('{}, mnemonic is {!r}, not a string.'
                             .format(where, mnemonic))

        if not isinstance(operands, list):
            raise ValueError('{}, operands are not represented by a list.'
                             .format(where))
        op_vals = []
        for op_idx, operand in enumerate(operands):
            if not isinstance(operand, int):
                raise ValueError('{}, operand {} is not an integer.'
                                 .format(where, op_idx))
            if operand < 0:
                raise ValueError('{}, operand {} is {}, '
                                 'but should be non-negative.'
                                 .format(where, op_idx, operand))
            op_vals.append(operand)

        lsu_info = None
        if json_lsu_info is not None:
            if not (isinstance(json_lsu_info, list) and
                    len(json_lsu_info) == 2):
                raise ValueError('{}, non-None LSU info is not a pair.'
                                 .format(where))
            mem_type, addr = json_lsu_info

            if not isinstance(mem_type, str):
                raise ValueError('{}, LSU info mem_type is not a string.'
                                 .format(where))
            # These are the memory types in Model._known_regs, but we can't
            # import that without a circular dependency. Rather than being
            # clever, we'll just duplicate them for now.
            if mem_type not in ['dmem', 'csr', 'wsr']:
                raise ValueError('{}, invalid LSU mem_type: {!r}.'
                                 .format(where, mem_type))

            if not isinstance(addr, int):
                raise ValueError('{}, LSU info target addr is not an integer.'
                                 .format(where))
            if addr < 0:
                raise ValueError('{}, LSU info target addr is {}, '
                                 'but should be non-negative.'
                                 .format(where, addr))

            lsu_info = (mem_type, addr)

        insn = insns_file.mnemonic_to_insn.get(mnemonic)
        if insn is None:
            raise ValueError('{}, unknown instruction {!r}.'
                             .format(where, mnemonic))

        if (lsu_info is None) is not (insn.lsu is None):
            raise ValueError('{}, LSU info is {}given, but the {} instruction '
                             '{} it.'
                             .format(where,
                                     'not ' if lsu_info is None else '',
                                     mnemonic,
                                     ("doesn't expect"
                                      if insn.lsu is None else "expects")))
        if len(insn.operands) != len(op_vals):
            raise ValueError('{}, {} instruction has {} operands, but {} '
                             'seen in JSON data.'
                             .format(where, mnemonic,
                                     len(insn.operands), len(op_vals)))
        if insn.syntax is None:
            raise ValueError('{}, {} instruction has no syntax defined.'
                             .format(where, mnemonic))

        return ProgInsn(insn, op_vals, lsu_info)


class OpenSection:
    '''A section of instructions that are currently being added to'''
    def __init__(self, insns_left: int, insns: List[ProgInsn]):
        assert insns_left > 0
        self.insns_left = insns_left
        self.insns = insns

    def add_insns(self, insns: List[ProgInsn]) -> None:
        '''Add some instructions to the section'''
        assert self.insns_left >= len(insns)
        self.insns.extend(insns)
        self.insns_left -= len(insns)


class Program:
    '''An object representing the random program that is being generated.

    '''
    # The data for a section we're currently adding to. The tuples are
    # (sec_vma, space_left, insns) where sec_vma is the address of the start of
    # the section, space_left is the number of instructions that can be added
    # to the section before we run out of space and insns is a list of
    # instructions for the section.
    _SecData = Tuple[int, int, List[ProgInsn]]

    def __init__(self, imem_lma: int, imem_size: int) -> None:
        assert imem_size & 3 == 0
        self.imem_lma = imem_lma
        self.imem_size = imem_size

        # A map from base address (VMA) to a list of instructions. Each
        # instruction is 4 bytes long, so a "section" of N instructions has
        # size 4N bytes.
        self._sections = {}  # type: Dict[int, List[ProgInsn]]

        # The current section's address and data, if there is one.
        self._cur_section = None  # type: Optional[Tuple[int, OpenSection]]

    def open_section(self, addr: int) -> None:
        '''Start a new section at addr'''
        assert addr & 3 == 0
        assert addr <= self.imem_size

        # Close any existing section
        self.close_section()

        assert self._cur_section is None

        # This linear search is a bit naff, but I doubt it will have a
        # significant performance impact.
        next_above = self.imem_size
        prev_sec_base = None  # type: Optional[int]
        for section_base in self._sections.keys():
            if addr <= section_base:
                if section_base < next_above:
                    next_above = section_base
            else:
                if prev_sec_base is None or prev_sec_base < section_base:
                    prev_sec_base = section_base

        # At this point, next_above is the base of the first section
        # immediately after addr (or the top of memory if there isn't one).
        # prev_sec_base is None if addr is below all existing sections or is
        # the address of the highest section that starts below addr.
        assert addr < next_above
        insns_left = (next_above - addr) // 4

        if prev_sec_base is not None:
            # If there is a previous section, check there is no overlap.
            prev_sec = self._sections[prev_sec_base]
            prev_sec_top = prev_sec_base + 4 * len(prev_sec)
            assert prev_sec_top <= addr

            # If prev_sec_top *equals* addr, we can merge the sections (neater
            # than generating two adjacent sections).
            if prev_sec_top == addr:
                del self._sections[prev_sec_base]
                self._cur_section = (prev_sec_base, OpenSection(insns_left, prev_sec))
                return

        # If we get here then there either was no previous section, or it
        # didn't butt up against our address. Open a new one.
        self._cur_section = (addr, OpenSection(insns_left, []))

    def close_section(self) -> None:
        '''Finalize any current section'''
        if self._cur_section is None:
            return

        sec_addr, open_section = self._cur_section

        # The "insns_left" tracking in OpenSection should ensure that this
        # section doesn't collide with anything else in self._sections. As a
        # quick sanity check, we make sure the base address isn't duplicated
        # (of course, that's not a full check, but it can't hurt).
        assert sec_addr not in self._sections
        self._sections[sec_addr] = open_section.insns

        self._cur_section = None

    def get_cur_section(self) -> Optional[OpenSection]:
        '''Returns the current section if there is one'''
        return self._cur_section[1] if self._cur_section is not None else None

    def add_insns(self, addr: int, insns: List[ProgInsn]) -> None:
        '''Add a sequence of instructions, starting at addr'''
        self.open_section(addr)
        assert self._cur_section is not None
        self._cur_section[1].add_insns(insns)

    @staticmethod
    def _get_section_comment(idx: int,
                             addr: int,
                             insns: List[ProgInsn]) -> str:
        return ('/* Section {} (addresses [{:#06x}..{:#06x}]) */'
                .format(idx, addr, addr + 4 * len(insns) - 1))

    def dump_asm(self, out_file: TextIO) -> None:
        '''Write an assembly representation of the program to out_file'''
        # Close any existing section, so that we can iterate over all the
        # instructions by iterating over self._sections.
        self.close_section()
        for idx, (addr, insns) in enumerate(sorted(self._sections.items())):
            comment = Program._get_section_comment(idx, addr, insns)
            out_file.write('{}{}\n'.format('\n' if idx else '', comment))
            out_file.write('.section .text.sec{:04}\n'.format(idx))
            for insn_off, pi in enumerate(insns):
                cur_pc = addr + 4 * insn_off
                out_file.write(pi.to_asm(cur_pc) + '\n')

    def dump_linker_script(self, out_file: TextIO) -> None:
        '''Write a linker script to link the program

        This lays out the sections generated in dump_asm().

        '''
        self.close_section()
        out_file.write('SECTIONS\n'
                       '{\n')
        for idx, (addr, insns) in enumerate(sorted(self._sections.items())):
            comment = Program._get_section_comment(idx, addr, insns)
            out_file.write('{}    {}\n'.format('\n' if idx else '', comment))
            sec_name = '.text.sec{:04}'.format(idx)
            lma = addr + self.imem_lma
            out_file.write('    {} {:#x} : AT({:#x})\n'
                           '    {{\n'
                           '        *({})\n'
                           '    }}\n'
                           .format(sec_name, addr, lma, sec_name))
        out_file.write('}\n')

    def pick_branch_targets(self,
                            min_len: int,
                            count: int,
                            tgt_min: Optional[int],
                            tgt_max: Optional[int]) -> Optional[List[int]]:
        '''Pick count random targets for a branch destination

        There is guaranteed to be at least space for min_len instructions at
        each target, but the weighting tries to favour places with some space
        for instruction sequences.

        If tgt_min is not None, the address returned will be at least tgt_min.
        Similarly for tgt_max.

        If we can't find space for the desired branch targets, returns None.

        '''

        # To pick the targets, we start by choosing a "gap" between existing
        # sections in which they should land. To do *that*, we start by making
        # a list of all the gaps between sections in ascending order of base
        # address.
        section_list = list(self._sections.items())
        if self._cur_section is not None:
            cur_base, cur_open_section = self._cur_section
            section_list.append((cur_base, cur_open_section.insns))
        section_list.sort()

        gap_vma = 0
        gap_list = []
        for section_base, section_insns in section_list:
            assert gap_vma <= section_base

            # We only count the gap if it isn't completely below tgt_min and
            # isn't completely above tgt_max.
            if (((tgt_min is None or tgt_min < section_base) and
                 (tgt_max is None or gap_vma <= tgt_max))):
                # The minimum address we can pick is gap_vma, but we might need
                # to bump it up if tgt_min is specified.
                gap_lo = (max(gap_vma, tgt_min)
                          if tgt_min is not None else gap_vma)

                # The maximum address we can pick needs space for min_len
                # instructions before we get to section_base *and* must be at
                # most tgt_max if that is specified.
                gap_hi = section_base - 4 * min_len
                if tgt_max is not None:
                    gap_hi = min(gap_hi, tgt_max)

                # If we have anything to use, add it!
                if gap_lo <= gap_hi:
                    gap_list.append((gap_lo, gap_hi - gap_lo + 1))

            gap_vma = section_base + 4 * len(section_insns)

        # Deal with any final gap above all known sections in the same way as
        # the internal gaps.
        gap_lo = (max(gap_vma, tgt_min)
                  if tgt_min is not None else gap_vma)
        gap_hi = self.imem_size - 4 * min_len
        if tgt_max is not None:
            gap_hi = min(gap_hi, tgt_max)
        if gap_lo <= gap_hi:
            gap_list.append((gap_lo, gap_hi - gap_lo + 1))

        ret = []
        for _ in range(count):

            # gap_list is an ordered list of pairs (addr, len), meaning "there
            # is a range of addresses that we can pick from, starting at
            # address addr and with length len bytes". If there are no gaps
            # left wide enough, gap_list will be empty and we should give up.
            if not gap_list:
                return None

            # Calculate weightings for the gaps. We weight by the extra length,
            # raised to some power (2.0, for now).
            gap_weight_pow = 2.0
            gap_weights = []
            for _, gap_len in gap_list:
                extra_len = gap_len - 4 * min_len
                gap_weights.append(1 + extra_len ** gap_weight_pow)

            idx = random.choices(range(len(gap_list)), weights=gap_weights)[0]

            # Now we have to decide what part of the gap to use. We choose the
            # offset in instructions from the start of the gap. Set
            # max_insn_off to the maximum allowed value.
            gap_vma, gap_len = gap_list[idx]
            max_insn_off = gap_len // 4 - min_len

            # To try to avoid splitting gaps too much, we want to make it more
            # likely that we'll pick stuff "at the edges". Rather than doing
            # clever maths, we split the range into 3 parts:
            #
            #    | low |     middle      | high |
            #
            # where low and high are each 10% of the total range (leaving the
            # other 80% in middle).
            #
            # Pick 0 <= D <= 1 and assign the weight D/2 to each of low and
            # high and 1-D to the middle. Larger values of D mean we favour the
            # edges more.
            D = 0.5
            endpts = [(0, max_insn_off // 10),
                      (max_insn_off // 10, max_insn_off * 9 // 10),
                      (max_insn_off * 9 // 10, max_insn_off)]
            min_insn_off, max_insn_off = \
                random.choices(endpts, weights=[D / 2, 1 - D, D / 2])[0]

            assert min_insn_off <= max_insn_off

            # Now that we've picked a region, we choose an offset uniformly
            # from the range
            rng_len = max_insn_off - min_insn_off
            insn_off = (min_insn_off + int(0.5 + random.random() * rng_len))
            assert min_insn_off <= insn_off <= max_insn_off

            assert 4 * insn_off <= gap_len
            tgt = gap_vma + 4 * insn_off
            ret.append(tgt)

            # The last thing we need to do is update the gap list.
            new_gap_list = []
            for gap_lo, gap_len in gap_list:
                gap_top = gap_lo + gap_len

                # Does this gap give us a gap to the left of the range [tgt,
                # tgt + 4 * min_len]?
                left_top = min(gap_top, tgt - 4 * min_len)
                if gap_lo < left_top:
                    new_gap_list.append((gap_lo, left_top - gap_lo))

                # And how about to the right?
                right_lo = max(gap_lo, tgt + 4 * min_len)
                if right_lo < gap_top:
                    new_gap_list.append((right_lo, gap_top - right_lo))

            gap_list = new_gap_list

        assert len(ret) == count
        return ret

    def pick_branch_target(self,
                           min_len: int,
                           tgt_min: Optional[int],
                           tgt_max: Optional[int]) -> Optional[int]:
        '''Pick a single random target for a branch destination

        A simple wrapper around the more general pick_branch_targets
        function.

        '''
        tgts = self.pick_branch_targets(min_len, 1, tgt_min, tgt_max)
        if tgts is None:
            return None

        assert len(tgts) == 1
        return tgts[0]

    def get_insn_space_at(self, addr: int) -> int:
        '''Return how many instructions there is space for, starting at addr'''
        space = self.imem_size - addr
        if space <= 0:
            return 0

        for sec_start, sec_insns in self._sections.items():
            sec_end = sec_start + 4 * len(sec_insns)
            if addr < sec_end:
                space = min(space, sec_start - addr)
                if space <= 0:
                    return 0

        if self._cur_section is not None:
            sec_start, open_section = self._cur_section
            sec_end = sec_start + 4 * len(open_section.insns)
            if addr < sec_end:
                space = min(space, sec_start - addr)

        return max(0, space // 4)