contract Governor is MultiRole, Testable {
    using SafeMath for uint;
    using Address for address;

    /****************************************
     *     INTERNAL VARIABLES AND STORAGE   *
     ****************************************/

    enum Roles {
        Owner, // Can set the proposer.
        Proposer // Address that can make proposals.
    }

    struct Transaction {
        address to;
        uint256 value;
        bytes data;
    }

    struct Proposal {
        Transaction[] transactions;
        uint256 requestTime;
    }

    FinderInterface private finder;
    Proposal[] public proposals;

    /****************************************
     *                EVENTS                *
     ****************************************/

    // Emitted when a new proposal is created.
    event NewProposal(uint256 indexed id, Transaction[] transactions);

    // Emitted when an existing proposal is executed.
    event ProposalExecuted(uint256 indexed id, uint256 transactionIndex);

    /**
     * @notice Construct the Governor contract.
     * @param _finderAddress keeps track of all contracts within the system based on their interfaceName.
     * @param _startingId the initial proposal id that the contract will begin incrementing from.
     * @param _timerAddress Contract that stores the current time in a testing environment.
     * Must be set to 0x0 for production environments that use live time.
     */
    constructor(address _finderAddress, uint _startingId, address _timerAddress) public Testable(_timerAddress) {
        finder = FinderInterface(_finderAddress);
        _createExclusiveRole(uint(Roles.Owner), uint(Roles.Owner), msg.sender);
        _createExclusiveRole(uint(Roles.Proposer), uint(Roles.Owner), msg.sender);

        // Ensure the startingId is not set unreasonably high to avoid it being set such that new proposals overwrite
        // other storage slots in the contract.
        uint maxStartingId = 10**18;
        require(_startingId <= maxStartingId, "Cannot set startingId larger than 10^18");

        // This just sets the initial length of the array to the startingId since modifying length directly has been
        // disallowed in solidity 0.6.
        assembly {
            sstore(proposals_slot, _startingId)
        }
    }

    /****************************************
     *          PROPOSAL ACTIONS            *
     ****************************************/

    /**
     * @notice Proposes a new governance action. Can only be called by the holder of the Proposer role.
     * @param transactions list of transactions that are being proposed.
     * @dev You can create the data portion of each transaction by doing the following:
     * ```
     * const truffleContractInstance = await TruffleContract.deployed()
     * const data = truffleContractInstance.methods.methodToCall(arg1, arg2).encodeABI()
     * ```
     * Note: this method must be public because of a solidity limitation that
     * disallows structs arrays to be passed to external functions.
     */
    function propose(Transaction[] memory transactions) public onlyRoleHolder(uint(Roles.Proposer)) {
        uint256 id = proposals.length;
        uint256 time = getCurrentTime();

        // Note: doing all of this array manipulation manually is necessary because directly setting an array of
        // structs in storage to an an array of structs in memory is currently not implemented in solidity :/.

        // Add a zero-initialized element to the proposals array.
        proposals.push();

        // Initialize the new proposal.
        Proposal storage proposal = proposals[id];
        proposal.requestTime = time;

        // Initialize the transaction array.
        for (uint256 i = 0; i < transactions.length; i++) {
            require(transactions[i].to != address(0), "The `to` address cannot be 0x0");
            // If the transaction has any data with it the recipient must be a contract, not an EOA.
            if (transactions[i].data.length > 0) {
                require(transactions[i].to.isContract(), "EOA can't accept tx with data");
            }
            proposal.transactions.push(transactions[i]);
        }

        bytes32 identifier = _constructIdentifier(id);

        // Request a vote on this proposal in the DVM.
        OracleInterface oracle = _getOracle();
        IdentifierWhitelistInterface supportedIdentifiers = _getIdentifierWhitelist();
        supportedIdentifiers.addSupportedIdentifier(identifier);

        oracle.requestPrice(identifier, time);
        supportedIdentifiers.removeSupportedIdentifier(identifier);

        emit NewProposal(id, transactions);
    }

    /**
     * @notice Executes a proposed governance action that has been approved by voters.
     * @dev This can be called by any address. Caller is expected to send enough ETH to execute payable transactions.
     * @param id unique id for the executed proposal.
     * @param transactionIndex unique transaction index for the executed proposal.
     */
    function executeProposal(uint256 id, uint256 transactionIndex) external payable {
        Proposal storage proposal = proposals[id];
        int256 price = _getOracle().getPrice(_constructIdentifier(id), proposal.requestTime);

        Transaction memory transaction = proposal.transactions[transactionIndex];

        require(
            transactionIndex == 0 || proposal.transactions[transactionIndex.sub(1)].to == address(0),
            "Previous tx not yet executed"
        );
        require(transaction.to != address(0), "Tx already executed");
        require(price != 0, "Proposal was rejected");
        require(msg.value == transaction.value, "Must send exact amount of ETH");

        // Delete the transaction before execution to avoid any potential re-entrancy issues.
        delete proposal.transactions[transactionIndex];

        require(_executeCall(transaction.to, transaction.value, transaction.data), "Tx execution failed");

        emit ProposalExecuted(id, transactionIndex);
    }

    /****************************************
     *       GOVERNOR STATE GETTERS         *
     ****************************************/

    /**
     * @notice Gets the total number of proposals (includes executed and non-executed).
     * @return uint256 representing the current number of proposals.
     */
    function numProposals() external view returns (uint) {
        return proposals.length;
    }

    /**
     * @notice Gets the proposal data for a particular id.
     * @dev after a proposal is executed, its data will be zeroed out, except for the request time.
     * @param id uniquely identify the identity of the proposal.
     * @return proposal struct containing transactions[] and requestTime.
     */
    function getProposal(uint256 id) external view returns (Proposal memory) {
        return proposals[id];
    }

    /****************************************
     *      PRIVATE GETTERS AND FUNCTIONS   *
     ****************************************/

    function _executeCall(address to, uint256 value, bytes memory data) private returns (bool) {
        // Mostly copied from:
        // solhint-disable-next-line max-line-length
        // https://github.com/gnosis/safe-contracts/blob/59cfdaebcd8b87a0a32f87b50fead092c10d3a05/contracts/base/Executor.sol#L23-L31
        // solhint-disable-next-line no-inline-assembly

        bool success;
        assembly {
            let inputData := add(data, 0x20)
            let inputDataSize := mload(data)
            success := call(gas(), to, value, inputData, inputDataSize, 0, 0)
        }
        return success;
    }

    function _getOracle() private view returns (OracleInterface) {
        return OracleInterface(finder.getImplementationAddress(OracleInterfaces.Oracle));
    }

    function _getIdentifierWhitelist() private view returns (IdentifierWhitelistInterface supportedIdentifiers) {
        return IdentifierWhitelistInterface(finder.getImplementationAddress(OracleInterfaces.IdentifierWhitelist));
    }

    // Returns a UTF-8 identifier representing a particular admin proposal.
    // The identifier is of the form "Admin n", where n is the proposal id provided.
    function _constructIdentifier(uint256 id) internal pure returns (bytes32) {
        bytes32 bytesId = _uintToUtf8(id);
        return _addPrefix(bytesId, "Admin ", 6);
    }

    // This method converts the integer `v` into a base-10, UTF-8 representation stored in a `bytes32` type.
    // If the input cannot be represented by 32 base-10 digits, it returns only the highest 32 digits.
    // This method is based off of this code: https://ethereum.stackexchange.com/a/6613/47801.
    function _uintToUtf8(uint256 v) internal pure returns (bytes32) {
        bytes32 ret;
        if (v == 0) {
            // Handle 0 case explicitly.
            ret = "0";
        } else {
            // Constants.
            uint256 bitsPerByte = 8;
            uint256 base = 10; // Note: the output should be base-10. The below implementation will not work for bases > 10.
            uint256 utf8NumberOffset = 48;
            while (v > 0) {
                // Downshift the entire bytes32 to allow the new digit to be added at the "front" of the bytes32, which
                // translates to the beginning of the UTF-8 representation.
                ret = ret >> bitsPerByte;

                // Separate the last digit that remains in v by modding by the base of desired output representation.
                uint256 leastSignificantDigit = v % base;

                // Digits 0-9 are represented by 48-57 in UTF-8, so an offset must be added to create the character.
                bytes32 utf8Digit = bytes32(leastSignificantDigit + utf8NumberOffset);

                // The top bit of ret has already been cleared to make room for the new digit.
                // Upshift by 31 bytes to put it in position, and OR it with ret to leave the other characters untouched.
                ret |= utf8Digit << (31 * bitsPerByte);

                // Divide v by the base to remove the digit that was just added.
                v /= base;
            }
        }
        return ret;
    }

    // This method takes two UTF-8 strings represented as bytes32 and outputs one as a prefixed by the other.
    // `input` is the UTF-8 that should have the prefix prepended.
    // `prefix` is the UTF-8 that should be prepended onto input.
    // `prefixLength` is number of UTF-8 characters represented by `prefix`.
    // Notes:
    // 1. If the resulting UTF-8 is larger than 32 characters, then only the first 32 characters will be represented
    //    by the bytes32 output.
    // 2. If `prefix` has more characters than `prefixLength`, the function will produce an invalid result.
    function _addPrefix(bytes32 input, bytes32 prefix, uint256 prefixLength) internal pure returns (bytes32) {
        // Downshift `input` to open space at the "front" of the bytes32
        bytes32 shiftedInput = input >> (prefixLength * 8);
        return shiftedInput | prefix;
    }
}
/**
 * @title Takes proposals for certain governance actions and allows UMA token holders to vote on them.
 */
function _addPrefix(bytes32 input, bytes32 prefix, uint256 prefixLength) internal pure returns (bytes32) {
    // Downshift `input` to open space at the "front" of the bytes32
    bytes32 shiftedInput = input >> (prefixLength * 8);
    return shiftedInput | prefix;
}

// This method takes two UTF-8 strings represented as bytes32 and outputs one as a prefixed by the other.
// `input` is the UTF-8 that should have the prefix prepended.
// `prefix` is the UTF-8 that should be prepended onto input.
// `prefixLength` is number of UTF-8 characters represented by `prefix`.
// Notes:
// 1. If the resulting UTF-8 is larger than 32 characters, then only the first 32 characters will be represented
//    by the bytes32 output.
// 2. If `prefix` has more characters than `prefixLength`, the function will produce an invalid result.