Contract Source Code (Solidity Standard Json-Input format)

IDE

• Blockscan IDE

More Options

• Similar
• Sol2Uml
• Submit Audit
• Compare

// SPDX-License-Identifier: MIT

pragma solidity 0.8.17;

import "./Interfaces/ISortedCdps.sol";
import "./Interfaces/ICdpManager.sol";
import "./Interfaces/IBorrowerOperations.sol";

/*
 * A sorted doubly linked list with nodes sorted in descending order.
 *
 * Nodes map to active Cdps in the system by Id.
 * Nodes are ordered according to their current nominal individual collateral ratio (NICR),
 * which is like the ICR but without the price, i.e., just collateral / debt.
 *
 * The list optionally accepts insert position hints.
 *
 * NICRs are computed dynamically at runtime, and not stored on the Node. This is because NICRs of active Cdps
 * change dynamically as liquidation events occur.
 *
 * The list relies on the fact that liquidation events preserve ordering: a liquidation decreases the NICRs of all active Cdps,
 * but maintains their order. A node inserted based on current NICR will maintain the correct position,
 * relative to it's peers, as rewards accumulate, as long as it's raw collateral and debt have not changed.
 * Thus, Nodes remain sorted by current NICR.
 *
 * Nodes need only be re-inserted upon a CDP operation - when the owner adds or removes collateral or debt
 * to their position.
 *
 * The list is a modification of the following audited SortedDoublyLinkedList:
 * https://github.com/livepeer/protocol/blob/master/contracts/libraries/SortedDoublyLL.sol
 *
 *
 * Changes made in the Liquity implementation:
 *
 * - Keys have been removed from nodes
 *
 * - Ordering checks for insertion are performed by comparing an NICR argument to the current NICR, calculated at runtime.
 *   The list relies on the property that ordering by ICR is maintained as the stETH:BTC price varies.
 *
 * - Public functions with parameters have been made internal to save gas, and given an external wrapper function for external access
 *
 *
 * Changes made in the Ebtc implementation:
 *
 * - Positions are now indexed by Ids, not addresses. Functions to generate Ids are provided.
 *
 * - Added batchRemove functions to optimize redemptions.
 *
 * - Added more O(n) getter functions and pagination-flavor variants, intended for off-chain use.
 */
contract SortedCdps is ISortedCdps {
    string public constant NAME = "SortedCdps";

    address public immutable borrowerOperationsAddress;

    ICdpManager public immutable cdpManager;

    uint256 public immutable maxSize;

    uint256 constant ADDRESS_SHIFT = 96; // 8 * 12; Puts the address at leftmost bytes32 position
    uint256 constant BLOCK_SHIFT = 64; // 8 * 8; Puts the block value after the address

    // Information for a node in the list
    struct Node {
        bytes32 nextId; // Id of next node (smaller NICR) in the list
        bytes32 prevId; // Id of previous node (larger NICR) in the list
    }

    // Information for the list
    struct Data {
        bytes32 head; // Head of the list. Also the node in the list with the largest NICR
        bytes32 tail; // Tail of the list. Also the node in the list with the smallest NICR
        mapping(bytes32 => Node) nodes; // Track the corresponding ids for each node in the list
    }

    uint256 public size; // Current size of the list

    Data public data;

    uint256 public nextCdpNonce;
    bytes32 public constant dummyId =
        0x0000000000000000000000000000000000000000000000000000000000000000;

    /// @notice Constructor
    /// @dev Sets max list size
    /// @param _size Max number of nodes allowed in the list
    /// @param _cdpManagerAddress Address of CdpManager contract
    /// @param _borrowerOperationsAddress Address of BorrowerOperations contract
    constructor(uint256 _size, address _cdpManagerAddress, address _borrowerOperationsAddress) {
        if (_size == 0) {
            _size = type(uint256).max;
        }

        maxSize = _size;

        cdpManager = ICdpManager(_cdpManagerAddress);
        borrowerOperationsAddress = _borrowerOperationsAddress;
    }

    /// @notice Encodes a unique CDP Id from owner, block and nonce
    /// @dev Inspired https://github.com/balancer-labs/balancer-v2-monorepo/blob/18bd5fb5d87b451cc27fbd30b276d1fb2987b529/pkg/vault/contracts/PoolRegistry.sol
    /// @param owner Owner address of the CDP
    /// @param blockHeight Block number when CDP opened
    /// @param nonce Unique nonce for CDP
    /// @return Unique bytes32 CDP Id
    function toCdpId(
        address owner,
        uint256 blockHeight,
        uint256 nonce
    ) public pure returns (bytes32) {
        bytes32 serialized;

        serialized |= bytes32(nonce);
        serialized |= bytes32(blockHeight) << BLOCK_SHIFT; // to accommendate more than 4.2 billion blocks
        serialized |= bytes32(uint256(uint160(owner))) << ADDRESS_SHIFT;

        return serialized;
    }

    /// @notice Get owner address of a given CDP, given CdpId.
    /// @dev The owner address is stored in the first 20 bytes of the CdpId
    /// @param cdpId cdpId of CDP to get owner of
    /// @return owner address of the CDP
    function getOwnerAddress(bytes32 cdpId) public pure override returns (address) {
        uint256 _tmp = uint256(cdpId) >> ADDRESS_SHIFT;
        return address(uint160(_tmp));
    }

    /// @notice Get dummy non-existent CDP Id
    /// @return Dummy non-existent CDP Id
    function nonExistId() public pure override returns (bytes32) {
        return dummyId;
    }

    /// @notice Find a specific CDP for a given owner, indexed by it's place in the linked list relative to other Cdps owned by the same address
    /// @notice Reverts if the index exceeds the number of active Cdps owned by the given owner
    /// @dev Intended for off-chain use, O(n) operation on size of SortedCdps linked list
    /// @param owner address of CDP owner
    /// @param index index of CDP, ordered by position in linked list relative to Cdps of the same owner
    /// @return CDP Id if found
    function cdpOfOwnerByIndex(
        address owner,
        uint256 index
    ) external view override returns (bytes32) {
        (bytes32 _cdpId, ) = _cdpOfOwnerByIndex(owner, index, dummyId, 0);
        return _cdpId;
    }

    /// @dev a pagination-flavor search (from least ICR to biggest ICR) for CDP owned by given owner and specified index (starting at given CDP)
    /// @param owner address of CDP owner
    /// @param index index of CDP, ordered by position in linked list relative to Cdps of the same owner
    /// @param startNodeId the seach traversal will start at this given CDP instead of the tail of the list
    /// @param maxNodes the traversal will go through the list by this given maximum limit of number of Cdps
    /// @return CDP Id if found, else return last seen CDP
    /// @return True if CDP found, false otherwise
    function cdpOfOwnerByIdx(
        address owner,
        uint256 index,
        bytes32 startNodeId,
        uint maxNodes
    ) external view override returns (bytes32, bool) {
        return _cdpOfOwnerByIndex(owner, index, startNodeId, maxNodes);
    }

    /// @notice Get a user CDP by index using pagination
    /// @dev return EITHER the found CDP owned by given owner & index with a true indicator OR
    /// @dev current lastly-visited CDP as the startNode for next pagination with a false indicator
    /// @param owner Owner address to get CDP for
    /// @param index Index of CDP amongst user's Cdps
    /// @param startNodeId Start position CDP Id
    /// @param maxNodes Max number of Cdps to traverse
    /// @return cdpId The CDP Id if found, otherwise return current lastly-visited CDP as the startNode for next pagination
    /// @return found True if the CDP was found, false otherwise
    function _cdpOfOwnerByIndex(
        address owner,
        uint256 index,
        bytes32 startNodeId,
        uint maxNodes
    ) internal view returns (bytes32, bool) {
        // walk the list, until we get to the indexed CDP
        // start at the given node or from the tail of list
        bytes32 _currentCdpId = (startNodeId == dummyId ? data.tail : startNodeId);
        uint _currentIndex = 0;
        uint i;

        while (_currentCdpId != dummyId) {
            // if the current CDP is owned by specified owner
            if (getOwnerAddress(_currentCdpId) == owner) {
                // if the current index of the owner CDP matches specified index
                if (_currentIndex == index) {
                    return (_currentCdpId, true);
                } else {
                    // if not, increment the owner index as we've seen a CDP owned by them
                    _currentIndex = _currentIndex + 1;
                }
            }
            ++i;

            // move to the next CDP in the list
            _currentCdpId = data.nodes[_currentCdpId].prevId;

            // cut the run if we exceed expected iterations through the loop
            if (maxNodes > 0 && i >= maxNodes) {
                break;
            }
        }
        // if we reach maximum iteration or end of list
        // without seeing the specified index for the owner
        // then maybe a new pagination is needed
        return (_currentCdpId, false);
    }

    /// @notice Get active CDP count for an owner address
    /// @dev Intended for off-chain use, O(n) operation on size of linked list
    /// @param owner Owner address to count Cdps for
    /// @return count Number of active Cdps owned by the address
    function cdpCountOf(address owner) external view override returns (uint256) {
        (uint256 _cnt, ) = _cdpCountOf(owner, dummyId, 0);
        return _cnt;
    }

    /// @notice a Pagination-flavor search for the count of Cdps owned by given owner
    /// @notice Starts from a given CdpId in the sorted list, and moves from lowest ICR to highest ICR
    /// @param startNodeId the count traversal will start at this given CDP instead of the tail of the list
    /// @param maxNodes the traversal will go through the list by this given maximum limit of number of Cdps
    /// @return count Number of active Cdps owned by the address in the segment of the list traversed
    /// @return last seen CDP for the startNode for next pagination
    function getCdpCountOf(
        address owner,
        bytes32 startNodeId,
        uint maxNodes
    ) external view override returns (uint256, bytes32) {
        return _cdpCountOf(owner, startNodeId, maxNodes);
    }

    /// @dev return the found CDP count owned by given owner with
    /// @dev current lastly-visited CDP as the startNode for next pagination
    function _cdpCountOf(
        address owner,
        bytes32 startNodeId,
        uint maxNodes
    ) internal view returns (uint256, bytes32) {
        // walk the list, until we get to the count
        // start at the given node or from the tail of list
        bytes32 _currentCdpId = (startNodeId == dummyId ? data.tail : startNodeId);
        uint _ownedCount = 0;
        uint i = 0;

        while (_currentCdpId != dummyId) {
            // if the current CDP is owned by specified owner
            if (getOwnerAddress(_currentCdpId) == owner) {
                _ownedCount = _ownedCount + 1;
            }
            ++i;

            // move to the next CDP in the list
            _currentCdpId = data.nodes[_currentCdpId].prevId;

            // cut the run if we exceed expected iterations through the loop
            if (maxNodes > 0 && i >= maxNodes) {
                break;
            }
        }
        return (_ownedCount, _currentCdpId);
    }

    /// @notice Get all active Cdps for a given address
    /// @dev Intended for off-chain use, O(n) operation on size of linked list
    /// @param owner address of CDP owner
    /// @return cdps all CdpIds of the specified owner
    function getCdpsOf(address owner) external view override returns (bytes32[] memory cdps) {
        // Naive method uses two-pass strategy to determine exactly how many Cdps are owned by owner
        // This roughly halves the amount of Cdps we can process before relying on pagination or off-chain methods
        (uint _ownedCount, ) = _cdpCountOf(owner, dummyId, 0);
        if (_ownedCount > 0) {
            (bytes32[] memory _allCdps, , ) = _getCdpsOf(owner, dummyId, 0, _ownedCount);
            cdps = _allCdps;
        }
    }

    /// @dev a pagination-flavor search retrieval of (from least ICR to biggest ICR) Cdps owned by given owner (starting at given CDP)
    /// @param startNodeId the traversal will start at this given CDP instead of the tail of the list
    /// @param maxNodes the traversal will go through the list by this given maximum limit of number of Cdps
    /// @return all CdpIds of the specified owner found by search starting at the specified startNodeId for the specified maximum iteration count
    /// @return found number of Cdp for the owner
    /// @return starting CdpId for next pagination within current SortedCdps
    function getAllCdpsOf(
        address owner,
        bytes32 startNodeId,
        uint maxNodes
    ) external view override returns (bytes32[] memory, uint256, bytes32) {
        // Naive method uses two-pass strategy to determine exactly how many Cdps are owned by owner
        // This roughly halves the amount of Cdps we can process before relying on pagination or off-chain methods
        (uint _ownedCount, ) = _cdpCountOf(owner, startNodeId, maxNodes);
        return _getCdpsOf(owner, startNodeId, maxNodes, _ownedCount);
    }

    /// @dev return EITHER the found Cdps (also the count) owned by given owner OR empty array with
    /// @dev current lastly-visited CDP as the startNode for next pagination
    function _getCdpsOf(
        address owner,
        bytes32 startNodeId,
        uint maxNodes,
        uint maxArraySize
    ) internal view returns (bytes32[] memory, uint256, bytes32) {
        if (maxArraySize == 0) {
            return (new bytes32[](0), 0, dummyId);
        }

        // Two-pass strategy, halving the amount of Cdps we can process before relying on pagination or off-chain methods
        bytes32[] memory userCdps = new bytes32[](maxArraySize);
        uint i = 0;
        uint _cdpRetrieved;

        // walk the list, until we get to the index
        // start at the given node or from the tail of list
        bytes32 _currentCdpId = (startNodeId == dummyId ? data.tail : startNodeId);

        while (_currentCdpId != dummyId) {
            // if the current CDP is owned by specified owner
            if (getOwnerAddress(_currentCdpId) == owner) {
                userCdps[_cdpRetrieved] = _currentCdpId;
                ++_cdpRetrieved;
            }
            ++i;

            // move to the next CDP in the list
            _currentCdpId = data.nodes[_currentCdpId].prevId;

            // cut the run if we exceed expected iterations through the loop
            if (maxNodes > 0 && i >= maxNodes) {
                break;
            }
        }

        return (userCdps, _cdpRetrieved, _currentCdpId);
    }

    /// @notice Add a node to the list
    /// @param owner CDP owner for corresponding Id
    /// @param _NICR Node's NICR
    /// @param _prevId Id of previous node for the insert position
    /// @param _nextId Id of next node for the insert position
    /// @return _id Id of the new node
    function insert(
        address owner,
        uint256 _NICR,
        bytes32 _prevId,
        bytes32 _nextId
    ) external override returns (bytes32) {
        _requireCallerIsBOorCdpM();
        bytes32 _id = toCdpId(owner, block.number, nextCdpNonce);
        require(cdpManager.getCdpStatus(_id) == 0, "SortedCdps: new id is NOT nonExistent!");

        _insert(_id, _NICR, _prevId, _nextId);

        unchecked {
            ++nextCdpNonce;
        }

        return _id;
    }

    function _insert(bytes32 _id, uint256 _NICR, bytes32 _prevId, bytes32 _nextId) internal {
        // List must not be full
        require(!isFull(), "SortedCdps: List is full");
        // List must not already contain node
        require(!contains(_id), "SortedCdps: List already contains the node");
        // Node id must not be null
        require(_id != dummyId, "SortedCdps: Id cannot be zero");
        // NICR must be non-zero
        require(_NICR > 0, "SortedCdps: NICR must be positive");

        bytes32 prevId = _prevId;
        bytes32 nextId = _nextId;

        if (!_validInsertPosition(_NICR, prevId, nextId)) {
            // Sender's hint was not a valid insert position
            // Use sender's hint to find a valid insert position
            (prevId, nextId) = _findInsertPosition(_NICR, prevId, nextId);
        }

        if (prevId == dummyId && nextId == dummyId) {
            // Insert as head and tail
            data.head = _id;
            data.tail = _id;
        } else if (prevId == dummyId) {
            // Insert before `prevId` as the head
            data.nodes[_id].nextId = data.head;
            data.nodes[data.head].prevId = _id;
            data.head = _id;
        } else if (nextId == dummyId) {
            // Insert after `nextId` as the tail
            data.nodes[_id].prevId = data.tail;
            data.nodes[data.tail].nextId = _id;
            data.tail = _id;
        } else {
            // Insert at insert position between `prevId` and `nextId`
            data.nodes[_id].nextId = nextId;
            data.nodes[_id].prevId = prevId;
            data.nodes[prevId].nextId = _id;
            data.nodes[nextId].prevId = _id;
        }

        size = size + 1;
        emit NodeAdded(_id, _NICR);
    }

    /// @notice Remove a node from the sorted list, by Id
    /// @param _id The CdpId to be removed
    function remove(bytes32 _id) external override {
        _requireCallerIsCdpManager();
        _remove(_id);
    }

    /// @notice Batch a node from the sorted list, by Id
    /// @notice Strong trust assumption that the specified nodes are sorted in the same order as in the input array
    /// @dev Optimization to reduce gas cost for removing multiple nodes on redemption
    /// @param _ids Array of CdpIds to remove
    function batchRemove(bytes32[] memory _ids) external override {
        _requireCallerIsCdpManager();
        uint256 _len = _ids.length;
        require(_len > 1, "SortedCdps: batchRemove() only apply to multiple cdpIds!");

        bytes32 _firstPrev = data.nodes[_ids[0]].prevId;
        bytes32 _lastNext = data.nodes[_ids[_len - 1]].nextId;

        require(
            _firstPrev != dummyId || _lastNext != dummyId,
            "SortedCdps: batchRemove() leave ZERO node left!"
        );

        for (uint256 i = 0; i < _len; ++i) {
            require(contains(_ids[i]), "SortedCdps: List does not contain the id");
        }

        // orphan nodes in between to save gas
        if (_firstPrev != dummyId) {
            data.nodes[_firstPrev].nextId = _lastNext;
        } else {
            data.head = _lastNext;
        }
        if (_lastNext != dummyId) {
            data.nodes[_lastNext].prevId = _firstPrev;
        } else {
            data.tail = _firstPrev;
        }

        // delete node & owner storages to get gas refund
        for (uint i = 0; i < _len; ++i) {
            delete data.nodes[_ids[i]];
            emit NodeRemoved(_ids[i]);
        }
        size = size - _len;
    }

    function _remove(bytes32 _id) internal {
        // List must contain the node
        require(contains(_id), "SortedCdps: List does not contain the id");

        if (size > 1) {
            // List contains more than a single node
            if (_id == data.head) {
                // The removed node is the head
                // Set head to next node
                data.head = data.nodes[_id].nextId;
                // Set prev pointer of new head to null
                data.nodes[data.head].prevId = dummyId;
            } else if (_id == data.tail) {
                // The removed node is the tail
                // Set tail to previous node
                data.tail = data.nodes[_id].prevId;
                // Set next pointer of new tail to null
                data.nodes[data.tail].nextId = dummyId;
            } else {
                // The removed node is neither the head nor the tail
                // Set next pointer of previous node to the next node
                data.nodes[data.nodes[_id].prevId].nextId = data.nodes[_id].nextId;
                // Set prev pointer of next node to the previous node
                data.nodes[data.nodes[_id].nextId].prevId = data.nodes[_id].prevId;
            }
        } else {
            // List contains a single node
            // Set the head and tail to null
            data.head = dummyId;
            data.tail = dummyId;
        }

        delete data.nodes[_id];
        size = size - 1;
        emit NodeRemoved(_id);
    }

    /// @notice Re-insert an existing node at a new position, based on its new NICR
    /// @param _id Node's id
    /// @param _newNICR Node's new NICR
    /// @param _prevId Id of previous node for the new insert position
    /// @param _nextId Id of next node for the new insert position
    function reInsert(
        bytes32 _id,
        uint256 _newNICR,
        bytes32 _prevId,
        bytes32 _nextId
    ) external override {
        _requireCallerIsBOorCdpM();
        // List must contain the node
        require(contains(_id), "SortedCdps: List does not contain the id");
        // NICR must be non-zero
        require(_newNICR > 0, "SortedCdps: NICR must be positive");

        // Remove node from the list
        _remove(_id);

        _insert(_id, _newNICR, _prevId, _nextId);
    }

    /// @dev Checks if the list contains a given node Id
    /// @param _id The Id of the node
    /// @return true if the node exists, false otherwise
    function contains(bytes32 _id) public view override returns (bool) {
        bool _exist = _id != dummyId && (data.head == _id || data.tail == _id);
        if (!_exist) {
            Node memory _node = data.nodes[_id];
            _exist = _id != dummyId && (_node.nextId != dummyId && _node.prevId != dummyId);
        }
        return _exist;
    }

    /// @dev Checks if the list is full
    /// @return true if the list is full, false otherwise
    function isFull() public view override returns (bool) {
        return size == maxSize;
    }

    /// @dev Checks if the list is empty
    /// @return true if the list is empty, false otherwise
    function isEmpty() public view override returns (bool) {
        return size == 0;
    }

    /// @dev Returns the current size of the list
    /// @return The current size of the list
    function getSize() external view override returns (uint256) {
        return size;
    }

    /// @dev Returns the maximum size of the list
    /// @return The maximum size of the list
    function getMaxSize() external view override returns (uint256) {
        return maxSize;
    }

    /// @dev Returns the first node in the list (node with the largest NICR)
    /// @return The Id of the first node
    function getFirst() external view override returns (bytes32) {
        return data.head;
    }

    /// @dev Returns the last node in the list (node with the smallest NICR)
    /// @return The Id of the last node
    function getLast() external view override returns (bytes32) {
        return data.tail;
    }

    /// @dev Returns the next node (with a smaller NICR) in the list for a given node
    /// @param _id The Id of the node
    /// @return The Id of the next node
    function getNext(bytes32 _id) external view override returns (bytes32) {
        return data.nodes[_id].nextId;
    }

    /// @dev Returns the previous node (with a larger NICR) in the list for a given node
    /// @param _id The Id of the node
    /// @return The Id of the previous node
    function getPrev(bytes32 _id) external view override returns (bytes32) {
        return data.nodes[_id].prevId;
    }

    /// @dev Check if a pair of nodes is a valid insertion point for a new node with the given NICR
    /// @param _NICR Node's NICR
    /// @param _prevId Id of previous node for the insert position
    /// @param _nextId Id of next node for the insert position
    /// @return true if the position is valid, false otherwise
    function validInsertPosition(
        uint256 _NICR,
        bytes32 _prevId,
        bytes32 _nextId
    ) external view override returns (bool) {
        return _validInsertPosition(_NICR, _prevId, _nextId);
    }

    function _validInsertPosition(
        uint256 _NICR,
        bytes32 _prevId,
        bytes32 _nextId
    ) internal view returns (bool) {
        if (_prevId == dummyId && _nextId == dummyId) {
            // `(null, null)` is a valid insert position if the list is empty
            return isEmpty();
        } else if (_prevId == dummyId) {
            // `(null, _nextId)` is a valid insert position if `_nextId` is the head of the list
            return data.head == _nextId && _NICR >= cdpManager.getCachedNominalICR(_nextId);
        } else if (_nextId == dummyId) {
            // `(_prevId, null)` is a valid insert position if `_prevId` is the tail of the list
            return data.tail == _prevId && _NICR <= cdpManager.getCachedNominalICR(_prevId);
        } else {
            // `(_prevId, _nextId)` is a valid insert position if they are adjacent nodes and `_NICR` falls between the two nodes' NICRs
            return
                data.nodes[_prevId].nextId == _nextId &&
                cdpManager.getCachedNominalICR(_prevId) >= _NICR &&
                _NICR >= cdpManager.getCachedNominalICR(_nextId);
        }
    }

    /// @dev Descend the list (larger NICRs to smaller NICRs) to find a valid insert position
    /// @param _NICR Node's NICR
    /// @param _startId Id of node to start descending the list from
    /// @return The previous node Id for the inserted node
    /// @return The next node Id for the inserted node
    function _descendList(uint256 _NICR, bytes32 _startId) internal view returns (bytes32, bytes32) {
        // If `_startId` is the head, check if the insert position is before the head
        if (data.head == _startId && _NICR >= cdpManager.getCachedNominalICR(_startId)) {
            return (dummyId, _startId);
        }

        bytes32 prevId = _startId;
        bytes32 nextId = data.nodes[prevId].nextId;

        // Descend the list until we reach the end or until we find a valid insert position
        while (prevId != dummyId && !_validInsertPosition(_NICR, prevId, nextId)) {
            prevId = data.nodes[prevId].nextId;
            nextId = data.nodes[prevId].nextId;
        }

        return (prevId, nextId);
    }

    /// @dev Ascend the list (smaller NICRs to larger NICRs) to find a valid insert position
    /// @param _NICR Node's NICR
    /// @param _startId Id of node to start ascending the list from
    /// @return The previous node Id for the inserted node
    /// @return The next node Id for the inserted node
    function _ascendList(uint256 _NICR, bytes32 _startId) internal view returns (bytes32, bytes32) {
        // If `_startId` is the tail, check if the insert position is after the tail
        if (data.tail == _startId && _NICR <= cdpManager.getCachedNominalICR(_startId)) {
            return (_startId, dummyId);
        }

        bytes32 nextId = _startId;
        bytes32 prevId = data.nodes[nextId].prevId;

        // Ascend the list until we reach the end or until we find a valid insertion point
        while (nextId != dummyId && !_validInsertPosition(_NICR, prevId, nextId)) {
            nextId = data.nodes[nextId].prevId;
            prevId = data.nodes[nextId].prevId;
        }

        return (prevId, nextId);
    }

    /// @dev Find the insert position for a node with the given NICR
    /// @param _NICR Node's NICR
    /// @param _prevId Id of previous node for the insert position
    /// @param _nextId Id of next node for the insert position
    /// @return The previous node Id for the inserted node
    /// @return The next node Id for the inserted node
    function findInsertPosition(
        uint256 _NICR,
        bytes32 _prevId,
        bytes32 _nextId
    ) external view override returns (bytes32, bytes32) {
        return _findInsertPosition(_NICR, _prevId, _nextId);
    }

    function _findInsertPosition(
        uint256 _NICR,
        bytes32 _prevId,
        bytes32 _nextId
    ) internal view returns (bytes32, bytes32) {
        bytes32 prevId = _prevId;
        bytes32 nextId = _nextId;

        if (prevId != dummyId) {
            if (!contains(prevId) || _NICR > cdpManager.getCachedNominalICR(prevId)) {
                // `prevId` does not exist anymore or now has a smaller NICR than the given NICR
                prevId = dummyId;
            }
        }

        if (nextId != dummyId) {
            if (!contains(nextId) || _NICR < cdpManager.getCachedNominalICR(nextId)) {
                // `nextId` does not exist anymore or now has a larger NICR than the given NICR
                nextId = dummyId;
            }
        }

        if (prevId == dummyId && nextId == dummyId) {
            // No hint - descend list starting from head
            return _descendList(_NICR, data.head);
        } else if (prevId == dummyId) {
            // No `prevId` for hint - ascend list starting from `nextId`
            return _ascendList(_NICR, nextId);
        } else if (nextId == dummyId) {
            // No `nextId` for hint - descend list starting from `prevId`
            return _descendList(_NICR, prevId);
        } else {
            // Descend list starting from `prevId`
            return _descendList(_NICR, prevId);
        }
    }

    // === Modifiers ===

    /// @dev Asserts that the caller of the function is the CdpManager
    function _requireCallerIsCdpManager() internal view {
        require(msg.sender == address(cdpManager), "SortedCdps: Caller is not the CdpManager");
    }

    /// @dev Asserts that the caller of the function is either the BorrowerOperations contract or the CdpManager
    function _requireCallerIsBOorCdpM() internal view {
        require(
            msg.sender == borrowerOperationsAddress || msg.sender == address(cdpManager),
            "SortedCdps: Caller is neither BO nor CdpM"
        );
    }
}

// SPDX-License-Identifier: MIT
pragma solidity 0.8.17;

/**
 * Based on the stETH:
 *  -   https://docs.lido.fi/contracts/lido#
 */
interface ICollateralTokenOracle {
    // Return beacon specification data.
    function getBeaconSpec()
        external
        view
        returns (
            uint64 epochsPerFrame,
            uint64 slotsPerEpoch,
            uint64 secondsPerSlot,
            uint64 genesisTime
        );
}

// SPDX-License-Identifier: MIT

pragma solidity 0.8.17;

/**
 * Based on the OpenZeppelin IER20 interface:
 * https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/token/ERC20/IERC20.sol
 *
 * @dev Interface of the ERC20 standard as defined in the EIP.
 */
interface IERC20 {
    /**
     * @dev Returns the amount of tokens in existence.
     */
    function totalSupply() external view returns (uint256);

    /**
     * @dev Returns the amount of tokens owned by `account`.
     */
    function balanceOf(address account) external view returns (uint256);

    /**
     * @dev Moves `amount` tokens from the caller's account to `recipient`.
     *
     * Returns a boolean value indicating whether the operation succeeded.
     *
     * Emits a {Transfer} event.
     */
    function transfer(address recipient, uint256 amount) external returns (bool);

    /**
     * @dev Returns the remaining number of tokens that `spender` will be
     * allowed to spend on behalf of `owner` through {transferFrom}. This is
     * zero by default.
     *
     * This value changes when {approve} or {transferFrom} are called.
     */
    function allowance(address owner, address spender) external view returns (uint256);

    function increaseAllowance(address spender, uint256 addedValue) external returns (bool);

    function decreaseAllowance(address spender, uint256 subtractedValue) external returns (bool);

    /**
     * @dev Sets `amount` as the allowance of `spender` over the caller's tokens.
     *
     * Returns a boolean value indicating whether the operation succeeded.
     *
     * IMPORTANT: Beware that changing an allowance with this method brings the risk
     * that someone may use both the old and the new allowance by unfortunate
     * transaction ordering. One possible solution to mitigate this race
     * condition is to first reduce the spender's allowance to 0 and set the
     * desired value afterwards:
     * https://github.com/ethereum/EIPs/issues/20#issuecomment-263524729
     *
     * Emits an {Approval} event.
     */
    function approve(address spender, uint256 amount) external returns (bool);

    /**
     * @dev Moves `amount` tokens from `sender` to `recipient` using the
     * allowance mechanism. `amount` is then deducted from the caller's
     * allowance.
     *
     * Returns a boolean value indicating whether the operation succeeded.
     *
     * Emits a {Transfer} event.
     */
    function transferFrom(address sender, address recipient, uint256 amount) external returns (bool);

    function name() external view returns (string memory);

    function symbol() external view returns (string memory);

    function decimals() external view returns (uint8);

    /**
     * @dev Emitted when `value` tokens are moved from one account (`from`) to
     * another (`to`).
     *
     * Note that `value` may be zero.
     */
    event Transfer(address indexed from, address indexed to, uint256 value);

    /**
     * @dev Emitted when the allowance of a `spender` for an `owner` is set by
     * a call to {approve}. `value` is the new allowance.
     */
    event Approval(address indexed owner, address indexed spender, uint256 value);
}

// SPDX-License-Identifier: MIT

pragma solidity 0.8.17;

/**
 * @dev Interface of the ERC2612 standard as defined in the EIP.
 *
 * Adds the {permit} method, which can be used to change one's
 * {IERC20-allowance} without having to send a transaction, by signing a
 * message. This allows users to spend tokens without having to hold Ether.
 *
 * See https://eips.ethereum.org/EIPS/eip-2612.
 *
 * Code adapted from https://github.com/OpenZeppelin/openzeppelin-contracts/pull/2237/
 */
interface IERC2612 {
    /**
     * @dev Sets `amount` as the allowance of `spender` over `owner`'s tokens,
     * given `owner`'s signed approval.
     *
     * IMPORTANT: The same issues {IERC20-approve} has related to transaction
     * ordering also apply here.
     *
     * Emits an {Approval} event.
     *
     * Requirements:
     *
     * - `owner` cannot be the zero address.
     * - `spender` cannot be the zero address.
     * - `deadline` must be a timestamp in the future.
     * - `v`, `r` and `s` must be a valid `secp256k1` signature from `owner`
     * over the EIP712-formatted function arguments.
     * - the signature must use ``owner``'s current nonce (see {nonces}).
     *
     * For more information on the signature format, see the
     * https://eips.ethereum.org/EIPS/eip-2612#specification[relevant EIP
     * section].
     */
    function permit(
        address owner,
        address spender,
        uint256 amount,
        uint256 deadline,
        uint8 v,
        bytes32 r,
        bytes32 s
    ) external;

    /**
     * @dev Returns the current ERC2612 nonce for `owner`. This value must be
     * included whenever a signature is generated for {permit}.
     *
     * Every successful call to {permit} increases `owner`'s nonce by one. This
     * prevents a signature from being used multiple times.
     *
     * `owner` can limit the time a Permit is valid for by setting `deadline` to
     * a value in the near future. The deadline argument can be set to uint256(-1) to
     * create Permits that effectively never expire.
     */
    function nonces(address owner) external view returns (uint256);

    function version() external view returns (string memory);

    function permitTypeHash() external view returns (bytes32);

    function domainSeparator() external view returns (bytes32);
}

// SPDX-License-Identifier: MIT

pragma solidity 0.8.17;

import "./IPool.sol";
import "./ITwapWeightedObserver.sol";

interface IActivePool is IPool, ITwapWeightedObserver {
    // --- Events ---
    event ActivePoolEBTCDebtUpdated(uint256 _EBTCDebt);
    event SystemCollSharesUpdated(uint256 _coll);
    event FeeRecipientClaimableCollSharesIncreased(uint256 _coll, uint256 _fee);
    event FeeRecipientClaimableCollSharesDecreased(uint256 _coll, uint256 _fee);
    event FlashLoanSuccess(
        address indexed _receiver,
        address indexed _token,
        uint256 _amount,
        uint256 _fee
    );
    event SweepTokenSuccess(address indexed _token, uint256 _amount, address indexed _recipient);

    // --- Functions ---
    function transferSystemCollShares(address _account, uint256 _amount) external;

    function increaseSystemCollShares(uint256 _value) external;

    function transferSystemCollSharesAndLiquidatorReward(
        address _account,
        uint256 _shares,
        uint256 _liquidatorRewardShares
    ) external;

    function allocateSystemCollSharesToFeeRecipient(uint256 _shares) external;

    function claimFeeRecipientCollShares(uint256 _shares) external;

    function feeRecipientAddress() external view returns (address);

    function getFeeRecipientClaimableCollShares() external view returns (uint256);
}

// SPDX-License Identifier: MIT
pragma solidity 0.8.17;

interface IBaseTwapWeightedObserver {
    // NOTE: Packing manually is cheaper, but this is simpler to understand and follow
    struct PackedData {
        // Slot 0
        // Seconds in a year: 3.154e+7
        /// @dev Accumulator value recorded for TWAP Observer until last update
        uint128 observerCumuVal; // 3.154e+7 * 80 * 100e27 = 2.5232e+38 | log_2(100e27 * 3.154e+7 * 80) = 127.568522171
        /// @dev Accumulator for TWAP globally
        uint128 accumulator; // 3.154e+7 * 80 * 100e27 = 2.5232e+38 | log_2(100e27 * 3.154e+7 * 80) = 127.568522171
        // NOTE: We can further compress this slot but we will not be able to use only one (see u72 impl)
        /// So what's the point of making the code more complex?

        // Slot 1
        /// @dev last update timestamp for TWAP Observer
        uint64 lastObserved; // Thousands of Years, if we use relative time we can use u32 | Relative to deploy time (as immutable)
        /// @dev last update timestamp for TWAP global track(spot) value
        uint64 lastAccrued; // Thousands of years
        // Expect eBTC debt to never surpass 100e27, which is 100 BILLION eBTC
        // log_2(100e27) = 96.3359147517 | log_2(100e27 / 1e18) = 36.5412090438
        // We could use a u64
        /// @dev average value since last observe
        uint128 lastObservedAverage;
    }
}

// SPDX-License-Identifier: MIT

pragma solidity 0.8.17;
import "./IPositionManagers.sol";

// Common interface for the Cdp Manager.
interface IBorrowerOperations is IPositionManagers {
    // --- Events ---

    event FeeRecipientAddressChanged(address indexed _feeRecipientAddress);
    event FlashLoanSuccess(
        address indexed _receiver,
        address indexed _token,
        uint256 _amount,
        uint256 _fee
    );

    // --- Functions ---

    function openCdp(
        uint256 _EBTCAmount,
        bytes32 _upperHint,
        bytes32 _lowerHint,
        uint256 _stEthBalance
    ) external returns (bytes32);

    function openCdpFor(
        uint _EBTCAmount,
        bytes32 _upperHint,
        bytes32 _lowerHint,
        uint _collAmount,
        address _borrower
    ) external returns (bytes32);

    function addColl(
        bytes32 _cdpId,
        bytes32 _upperHint,
        bytes32 _lowerHint,
        uint256 _stEthBalanceIncrease
    ) external;

    function withdrawColl(
        bytes32 _cdpId,
        uint256 _stEthBalanceDecrease,
        bytes32 _upperHint,
        bytes32 _lowerHint
    ) external;

    function withdrawDebt(
        bytes32 _cdpId,
        uint256 _amount,
        bytes32 _upperHint,
        bytes32 _lowerHint
    ) external;

    function repayDebt(
        bytes32 _cdpId,
        uint256 _amount,
        bytes32 _upperHint,
        bytes32 _lowerHint
    ) external;

    function closeCdp(bytes32 _cdpId) external;

    function adjustCdp(
        bytes32 _cdpId,
        uint256 _stEthBalanceDecrease,
        uint256 _debtChange,
        bool isDebtIncrease,
        bytes32 _upperHint,
        bytes32 _lowerHint
    ) external;

    function adjustCdpWithColl(
        bytes32 _cdpId,
        uint256 _stEthBalanceDecrease,
        uint256 _debtChange,
        bool isDebtIncrease,
        bytes32 _upperHint,
        bytes32 _lowerHint,
        uint256 _stEthBalanceIncrease
    ) external;

    function claimSurplusCollShares() external;

    function feeRecipientAddress() external view returns (address);
}

// SPDX-License-Identifier: MIT

pragma solidity 0.8.17;

import "./IEbtcBase.sol";
import "./ICdpManagerData.sol";

// Common interface for the Cdp Manager.
interface ICdpManager is IEbtcBase, ICdpManagerData {
    // --- Functions ---
    function liquidate(bytes32 _cdpId) external;

    function partiallyLiquidate(
        bytes32 _cdpId,
        uint256 _partialAmount,
        bytes32 _upperPartialHint,
        bytes32 _lowerPartialHint
    ) external;

    function batchLiquidateCdps(bytes32[] calldata _cdpArray) external;

    function redeemCollateral(
        uint256 _EBTCAmount,
        bytes32 _firstRedemptionHint,
        bytes32 _upperPartialRedemptionHint,
        bytes32 _lowerPartialRedemptionHint,
        uint256 _partialRedemptionHintNICR,
        uint256 _maxIterations,
        uint256 _maxFee
    ) external;

    function updateStakeAndTotalStakes(bytes32 _cdpId) external returns (uint256);

    function syncAccounting(bytes32 _cdpId) external;

    function closeCdp(bytes32 _cdpId, address _borrower, uint256 _debt, uint256 _coll) external;

    function getRedemptionRate() external view returns (uint256);

    function getRedemptionRateWithDecay() external view returns (uint256);

    function getRedemptionFeeWithDecay(uint256 _stETHToRedeem) external view returns (uint256);

    function getCdpStatus(bytes32 _cdpId) external view returns (uint256);

    function getCdpStake(bytes32 _cdpId) external view returns (uint256);

    function getCdpDebt(bytes32 _cdpId) external view returns (uint256);

    function getCdpCollShares(bytes32 _cdpId) external view returns (uint256);

    function getCdpLiquidatorRewardShares(bytes32 _cdpId) external view returns (uint);

    function initializeCdp(
        bytes32 _cdpId,
        uint256 _debt,
        uint256 _coll,
        uint256 _liquidatorRewardShares,
        address _borrower
    ) external;

    function updateCdp(
        bytes32 _cdpId,
        address _borrower,
        uint256 _coll,
        uint256 _debt,
        uint256 _newColl,
        uint256 _newDebt
    ) external;

    function getCachedTCR(uint256 _price) external view returns (uint256);

    function checkRecoveryMode(uint256 _price) external view returns (bool);
}

// SPDX-License-Identifier: MIT

pragma solidity 0.8.17;

import "./ICollSurplusPool.sol";
import "./IEBTCToken.sol";
import "./ISortedCdps.sol";
import "./IActivePool.sol";
import "./IRecoveryModeGracePeriod.sol";
import "../Dependencies/ICollateralTokenOracle.sol";

// Common interface for the Cdp Manager.
interface ICdpManagerData is IRecoveryModeGracePeriod {
    // --- Events ---

    event StakingRewardSplitSet(uint256 _stakingRewardSplit);
    event RedemptionFeeFloorSet(uint256 _redemptionFeeFloor);
    event MinuteDecayFactorSet(uint256 _minuteDecayFactor);
    event BetaSet(uint256 _beta);
    event RedemptionsPaused(bool _paused);

    event Liquidation(uint256 _liquidatedDebt, uint256 _liquidatedColl, uint256 _liqReward);
    event Redemption(
        uint256 _debtToRedeemExpected,
        uint256 _debtToRedeemActual,
        uint256 _collSharesSent,
        uint256 _feeCollShares,
        address indexed _redeemer
    );
    event CdpUpdated(
        bytes32 indexed _cdpId,
        address indexed _borrower,
        address indexed _executor,
        uint256 _oldDebt,
        uint256 _oldCollShares,
        uint256 _debt,
        uint256 _collShares,
        uint256 _stake,
        CdpOperation _operation
    );
    event CdpLiquidated(
        bytes32 indexed _cdpId,
        address indexed _borrower,
        uint _debt,
        uint _collShares,
        CdpOperation _operation,
        address indexed _liquidator,
        uint _premiumToLiquidator
    );
    event CdpPartiallyLiquidated(
        bytes32 indexed _cdpId,
        address indexed _borrower,
        uint256 _debt,
        uint256 _collShares,
        CdpOperation operation,
        address indexed _liquidator,
        uint _premiumToLiquidator
    );
    event BaseRateUpdated(uint256 _baseRate);
    event LastRedemptionTimestampUpdated(uint256 _lastFeeOpTime);
    event TotalStakesUpdated(uint256 _newTotalStakes);
    event SystemSnapshotsUpdated(uint256 _totalStakesSnapshot, uint256 _totalCollateralSnapshot);
    event SystemDebtRedistributionIndexUpdated(uint256 _systemDebtRedistributionIndex);
    event CdpDebtRedistributionIndexUpdated(bytes32 _cdpId, uint256 _cdpDebtRedistributionIndex);
    event CdpArrayIndexUpdated(bytes32 _cdpId, uint256 _newIndex);
    event StEthIndexUpdated(uint256 _oldIndex, uint256 _newIndex, uint256 _updTimestamp);
    event CollateralFeePerUnitUpdated(uint256 _oldPerUnit, uint256 _newPerUnit, uint256 _feeTaken);
    event CdpFeeSplitApplied(
        bytes32 _cdpId,
        uint256 _oldPerUnitCdp,
        uint256 _newPerUnitCdp,
        uint256 _collReduced,
        uint256 _collLeft
    );

    enum CdpOperation {
        openCdp,
        closeCdp,
        adjustCdp,
        syncAccounting,
        liquidateInNormalMode,
        liquidateInRecoveryMode,
        redeemCollateral,
        partiallyLiquidate,
        failedPartialRedemption
    }

    enum Status {
        nonExistent,
        active,
        closedByOwner,
        closedByLiquidation,
        closedByRedemption
    }

    // Store the necessary data for a cdp
    struct Cdp {
        uint256 debt;
        uint256 coll;
        uint256 stake;
        uint128 liquidatorRewardShares;
        Status status;
    }

    /*
     * --- Variable container structs for liquidations ---
     *
     * These structs are used to hold, return and assign variables inside the liquidation functions,
     * in order to avoid the error: "CompilerError: Stack too deep".
     **/

    struct CdpDebtAndCollShares {
        uint256 debt;
        uint256 collShares;
    }

    struct LiquidationLocals {
        bytes32 cdpId;
        uint256 partialAmount; // used only for partial liquidation, default 0 means full liquidation
        uint256 price;
        uint256 ICR;
        bytes32 upperPartialHint;
        bytes32 lowerPartialHint;
        bool recoveryModeAtStart;
        uint256 TCR;
        uint256 totalSurplusCollShares;
        uint256 totalCollSharesToSend;
        uint256 totalDebtToBurn;
        uint256 totalDebtToRedistribute;
        uint256 totalLiquidatorRewardCollShares;
    }

    struct LiquidationRecoveryModeLocals {
        uint256 entireSystemDebt;
        uint256 entireSystemColl;
        uint256 totalDebtToBurn;
        uint256 totalCollSharesToSend;
        uint256 totalSurplusCollShares;
        bytes32 cdpId;
        uint256 price;
        uint256 ICR;
        uint256 totalDebtToRedistribute;
        uint256 totalLiquidatorRewardCollShares;
    }

    struct LocalVariables_OuterLiquidationFunction {
        uint256 price;
        bool recoveryModeAtStart;
        uint256 liquidatedDebt;
        uint256 liquidatedColl;
    }

    struct LocalVariables_LiquidationSequence {
        uint256 i;
        uint256 ICR;
        bytes32 cdpId;
        bool backToNormalMode;
        uint256 entireSystemDebt;
        uint256 entireSystemColl;
        uint256 price;
        uint256 TCR;
    }

    struct SingleRedemptionInputs {
        bytes32 cdpId;
        uint256 maxEBTCamount;
        uint256 price;
        bytes32 upperPartialRedemptionHint;
        bytes32 lowerPartialRedemptionHint;
        uint256 partialRedemptionHintNICR;
    }

    struct LiquidationValues {
        uint256 entireCdpDebt;
        uint256 debtToBurn;
        uint256 totalCollToSendToLiquidator;
        uint256 debtToRedistribute;
        uint256 collSurplus;
        uint256 liquidatorCollSharesReward;
    }

    struct LiquidationTotals {
        uint256 totalDebtInSequence;
        uint256 totalDebtToBurn;
        uint256 totalCollToSendToLiquidator;
        uint256 totalDebtToRedistribute;
        uint256 totalCollSurplus;
        uint256 totalCollReward;
    }

    // --- Variable container structs for redemptions ---

    struct RedemptionTotals {
        uint256 remainingDebtToRedeem;
        uint256 debtToRedeem;
        uint256 collSharesDrawn;
        uint256 totalCollSharesSurplus;
        uint256 feeCollShares;
        uint256 collSharesToRedeemer;
        uint256 decayedBaseRate;
        uint256 price;
        uint256 systemDebtAtStart;
        uint256 twapSystemDebtAtStart;
        uint256 systemCollSharesAtStart;
        uint256 tcrAtStart;
    }

    struct SingleRedemptionValues {
        uint256 debtToRedeem;
        uint256 collSharesDrawn;
        uint256 collSurplus;
        uint256 liquidatorRewardShares;
        bool cancelledPartial;
        bool fullRedemption;
        uint256 newPartialNICR;
    }

    function getActiveCdpsCount() external view returns (uint256);

    function totalStakes() external view returns (uint256);

    function ebtcToken() external view returns (IEBTCToken);

    function systemStEthFeePerUnitIndex() external view returns (uint256);

    function systemStEthFeePerUnitIndexError() external view returns (uint256);

    function stEthIndex() external view returns (uint256);

    function calcFeeUponStakingReward(
        uint256 _newIndex,
        uint256 _prevIndex
    ) external view returns (uint256, uint256, uint256);

    function syncGlobalAccounting() external; // Accrues StEthFeeSplit without influencing Grace Period

    function syncGlobalAccountingAndGracePeriod() external; // Accrues StEthFeeSplit and influences Grace Period

    function getAccumulatedFeeSplitApplied(
        bytes32 _cdpId,
        uint256 _systemStEthFeePerUnitIndex
    ) external view returns (uint256, uint256);

    function getCachedNominalICR(bytes32 _cdpId) external view returns (uint256);

    function getCachedICR(bytes32 _cdpId, uint256 _price) external view returns (uint256);

    function getSyncedCdpDebt(bytes32 _cdpId) external view returns (uint256);

    function getSyncedCdpCollShares(bytes32 _cdpId) external view returns (uint256);

    function getSyncedICR(bytes32 _cdpId, uint256 _price) external view returns (uint256);

    function getSyncedTCR(uint256 _price) external view returns (uint256);

    function getSyncedSystemCollShares() external view returns (uint256);

    function getSyncedNominalICR(bytes32 _cdpId) external view returns (uint256);

    function getPendingRedistributedDebt(bytes32 _cdpId) external view returns (uint256);

    function hasPendingRedistributedDebt(bytes32 _cdpId) external view returns (bool);

    function getSyncedDebtAndCollShares(
        bytes32 _cdpId
    ) external view returns (uint256 debt, uint256 collShares);

    function canLiquidateRecoveryMode(uint256 icr, uint256 tcr) external view returns (bool);

    function totalCollateralSnapshot() external view returns (uint256);

    function totalStakesSnapshot() external view returns (uint256);
}

// SPDX-License-Identifier: MIT

pragma solidity 0.8.17;

interface ICollSurplusPool {
    // --- Events ---

    event SurplusCollSharesAdded(
        bytes32 indexed _cdpId,
        address indexed _account,
        uint256 _claimableSurplusCollShares,
        uint256 _surplusCollSharesAddedFromCollateral,
        uint256 _surplusCollSharesAddedFromLiquidatorReward
    );
    event CollSharesTransferred(address indexed _to, uint256 _amount);

    event SweepTokenSuccess(address indexed _token, uint256 _amount, address indexed _recipient);

    // --- Contract setters ---

    function getTotalSurplusCollShares() external view returns (uint256);

    function getSurplusCollShares(address _account) external view returns (uint256);

    function increaseSurplusCollShares(
        bytes32 _cdpId,
        address _account,
        uint256 _collateralShares,
        uint256 _liquidatorRewardShares
    ) external;

    function claimSurplusCollShares(address _account) external;

    function increaseTotalSurplusCollShares(uint256 _value) external;
}

// SPDX-License-Identifier: MIT

pragma solidity 0.8.17;

import "./IPriceFeed.sol";

interface IEbtcBase {
    function priceFeed() external view returns (IPriceFeed);
}

// SPDX-License-Identifier: MIT

pragma solidity 0.8.17;

import "../Dependencies/IERC20.sol";
import "../Dependencies/IERC2612.sol";

interface IEBTCToken is IERC20, IERC2612 {
    // --- Functions ---

    function mint(address _account, uint256 _amount) external;

    function burn(address _account, uint256 _amount) external;
}

// SPDX-License-Identifier: MIT

pragma solidity 0.8.17;

// Common interface for the Pools.
interface IPool {
    // --- Events ---

    event ETHBalanceUpdated(uint256 _newBalance);
    event EBTCBalanceUpdated(uint256 _newBalance);
    event CollSharesTransferred(address indexed _to, uint256 _amount);

    // --- Functions ---

    function getSystemCollShares() external view returns (uint256);

    function getSystemDebt() external view returns (uint256);

    function increaseSystemDebt(uint256 _amount) external;

    function decreaseSystemDebt(uint256 _amount) external;
}

// SPDX-License-Identifier: MIT

pragma solidity 0.8.17;

interface IPositionManagers {
    enum PositionManagerApproval {
        None,
        OneTime,
        Persistent
    }

    event PositionManagerApprovalSet(
        address indexed _borrower,
        address indexed _positionManager,
        PositionManagerApproval _approval
    );

    function getPositionManagerApproval(
        address _borrower,
        address _positionManager
    ) external view returns (PositionManagerApproval);

    function setPositionManagerApproval(
        address _positionManager,
        PositionManagerApproval _approval
    ) external;

    function revokePositionManagerApproval(address _positionManager) external;

    function renouncePositionManagerApproval(address _borrower) external;

    function permitPositionManagerApproval(
        address _borrower,
        address _positionManager,
        PositionManagerApproval _approval,
        uint _deadline,
        uint8 v,
        bytes32 r,
        bytes32 s
    ) external;

    function version() external view returns (string memory);

    function permitTypeHash() external view returns (bytes32);

    function domainSeparator() external view returns (bytes32);
}

// SPDX-License-Identifier: MIT

pragma solidity 0.8.17;

interface IPriceFeed {
    // --- Events ---
    event LastGoodPriceUpdated(uint256 _lastGoodPrice);
    event PriceFeedStatusChanged(Status newStatus);
    event FallbackCallerChanged(
        address indexed _oldFallbackCaller,
        address indexed _newFallbackCaller
    );
    event UnhealthyFallbackCaller(address indexed _fallbackCaller, uint256 timestamp);
    event CollateralFeedSourceUpdated(address indexed stEthFeed);

    // --- Structs ---

    struct ChainlinkResponse {
        uint80 roundEthBtcId;
        uint80 roundStEthEthId;
        uint256 answer;
        uint256 timestampEthBtc;
        uint256 timestampStEthEth;
        bool success;
    }

    struct FallbackResponse {
        uint256 answer;
        uint256 timestamp;
        bool success;
    }

    // --- Enum ---

    enum Status {
        chainlinkWorking,
        usingFallbackChainlinkUntrusted,
        bothOraclesUntrusted,
        usingFallbackChainlinkFrozen,
        usingChainlinkFallbackUntrusted
    }

    // --- Function ---
    function fetchPrice() external returns (uint256);
}

// SPDX-License-Identifier: MIT
pragma solidity 0.8.17;

// Interface for State Updates that can trigger RM Liquidations
interface IRecoveryModeGracePeriod {
    event TCRNotified(uint256 TCR); /// NOTE: Mostly for debugging to ensure synch

    // NOTE: Ts is implicit in events (it's added by GETH)
    event GracePeriodStart();
    event GracePeriodEnd();
    event GracePeriodDurationSet(uint256 _recoveryModeGracePeriodDuration);

    function notifyStartGracePeriod(uint256 tcr) external;

    function notifyEndGracePeriod(uint256 tcr) external;
}

// SPDX-License-Identifier: MIT

pragma solidity 0.8.17;

// Common interface for the SortedCdps Doubly Linked List.
interface ISortedCdps {
    // --- Events ---

    event NodeAdded(bytes32 _id, uint _NICR);
    event NodeRemoved(bytes32 _id);

    // --- Functions ---

    function remove(bytes32 _id) external;

    function batchRemove(bytes32[] memory _ids) external;

    function reInsert(bytes32 _id, uint256 _newICR, bytes32 _prevId, bytes32 _nextId) external;

    function contains(bytes32 _id) external view returns (bool);

    function isFull() external view returns (bool);

    function isEmpty() external view returns (bool);

    function getSize() external view returns (uint256);

    function getMaxSize() external view returns (uint256);

    function getFirst() external view returns (bytes32);

    function getLast() external view returns (bytes32);

    function getNext(bytes32 _id) external view returns (bytes32);

    function getPrev(bytes32 _id) external view returns (bytes32);

    function validInsertPosition(
        uint256 _ICR,
        bytes32 _prevId,
        bytes32 _nextId
    ) external view returns (bool);

    function findInsertPosition(
        uint256 _ICR,
        bytes32 _prevId,
        bytes32 _nextId
    ) external view returns (bytes32, bytes32);

    function insert(
        address owner,
        uint256 _ICR,
        bytes32 _prevId,
        bytes32 _nextId
    ) external returns (bytes32);

    function getOwnerAddress(bytes32 _id) external pure returns (address);

    function nonExistId() external view returns (bytes32);

    function cdpCountOf(address owner) external view returns (uint256);

    function getCdpCountOf(
        address owner,
        bytes32 startNodeId,
        uint maxNodes
    ) external view returns (uint256, bytes32);

    function getCdpsOf(address owner) external view returns (bytes32[] memory);

    function getAllCdpsOf(
        address owner,
        bytes32 startNodeId,
        uint maxNodes
    ) external view returns (bytes32[] memory, uint256, bytes32);

    function cdpOfOwnerByIndex(address owner, uint256 index) external view returns (bytes32);

    function cdpOfOwnerByIdx(
        address owner,
        uint256 index,
        bytes32 startNodeId,
        uint maxNodes
    ) external view returns (bytes32, bool);

    function toCdpId(
        address owner,
        uint256 blockHeight,
        uint256 nonce
    ) external pure returns (bytes32);

    function nextCdpNonce() external view returns (uint256);
}

// SPDX-License Identifier: MIT
pragma solidity 0.8.17;
import {IBaseTwapWeightedObserver} from "./IBaseTwapWeightedObserver.sol";

interface ITwapWeightedObserver is IBaseTwapWeightedObserver {
    event TwapDisabled();

    function PERIOD() external view returns (uint256);

    function valueToTrack() external view returns (uint128);

    function timeToAccrue() external view returns (uint64);

    function getLatestAccumulator() external view returns (uint128);

    function observe() external returns (uint256);

    function update() external;

    function twapDisabled() external view returns (bool);
}

{
  "optimizer": {
    "enabled": true,
    "runs": 200
  },
  "outputSelection": {
    "*": {
      "*": [
        "evm.bytecode",
        "evm.deployedBytecode",
        "devdoc",
        "userdoc",
        "metadata",
        "abi"
      ]
    }
  },
  "libraries": {}
}

[{"inputs":[{"internalType":"uint256","name":"_size","type":"uint256"},{"internalType":"address","name":"_cdpManagerAddress","type":"address"},{"internalType":"address","name":"_borrowerOperationsAddress","type":"address"}],"stateMutability":"nonpayable","type":"constructor"},{"anonymous":false,"inputs":[{"indexed":false,"internalType":"bytes32","name":"_id","type":"bytes32"},{"indexed":false,"internalType":"uint256","name":"_NICR","type":"uint256"}],"name":"NodeAdded","type":"event"},{"anonymous":false,"inputs":[{"indexed":false,"internalType":"bytes32","name":"_id","type":"bytes32"}],"name":"NodeRemoved","type":"event"},{"inputs":[],"name":"NAME","outputs":[{"internalType":"string","name":"","type":"string"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"bytes32[]","name":"_ids","type":"bytes32[]"}],"name":"batchRemove","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[],"name":"borrowerOperationsAddress","outputs":[{"internalType":"address","name":"","type":"address"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"address","name":"owner","type":"address"}],"name":"cdpCountOf","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"cdpManager","outputs":[{"internalType":"contract ICdpManager","name":"","type":"address"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"address","name":"owner","type":"address"},{"internalType":"uint256","name":"index","type":"uint256"},{"internalType":"bytes32","name":"startNodeId","type":"bytes32"},{"internalType":"uint256","name":"maxNodes","type":"uint256"}],"name":"cdpOfOwnerByIdx","outputs":[{"internalType":"bytes32","name":"","type":"bytes32"},{"internalType":"bool","name":"","type":"bool"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"address","name":"owner","type":"address"},{"internalType":"uint256","name":"index","type":"uint256"}],"name":"cdpOfOwnerByIndex","outputs":[{"internalType":"bytes32","name":"","type":"bytes32"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"bytes32","name":"_id","type":"bytes32"}],"name":"contains","outputs":[{"internalType":"bool","name":"","type":"bool"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"data","outputs":[{"internalType":"bytes32","name":"head","type":"bytes32"},{"internalType":"bytes32","name":"tail","type":"bytes32"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"dummyId","outputs":[{"internalType":"bytes32","name":"","type":"bytes32"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"uint256","name":"_NICR","type":"uint256"},{"internalType":"bytes32","name":"_prevId","type":"bytes32"},{"internalType":"bytes32","name":"_nextId","type":"bytes32"}],"name":"findInsertPosition","outputs":[{"internalType":"bytes32","name":"","type":"bytes32"},{"internalType":"bytes32","name":"","type":"bytes32"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"address","name":"owner","type":"address"},{"internalType":"bytes32","name":"startNodeId","type":"bytes32"},{"internalType":"uint256","name":"maxNodes","type":"uint256"}],"name":"getAllCdpsOf","outputs":[{"internalType":"bytes32[]","name":"","type":"bytes32[]"},{"internalType":"uint256","name":"","type":"uint256"},{"internalType":"bytes32","name":"","type":"bytes32"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"address","name":"owner","type":"address"},{"internalType":"bytes32","name":"startNodeId","type":"bytes32"},{"internalType":"uint256","name":"maxNodes","type":"uint256"}],"name":"getCdpCountOf","outputs":[{"internalType":"uint256","name":"","type":"uint256"},{"internalType":"bytes32","name":"","type":"bytes32"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"address","name":"owner","type":"address"}],"name":"getCdpsOf","outputs":[{"internalType":"bytes32[]","name":"cdps","type":"bytes32[]"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"getFirst","outputs":[{"internalType":"bytes32","name":"","type":"bytes32"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"getLast","outputs":[{"internalType":"bytes32","name":"","type":"bytes32"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"getMaxSize","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"bytes32","name":"_id","type":"bytes32"}],"name":"getNext","outputs":[{"internalType":"bytes32","name":"","type":"bytes32"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"bytes32","name":"cdpId","type":"bytes32"}],"name":"getOwnerAddress","outputs":[{"internalType":"address","name":"","type":"address"}],"stateMutability":"pure","type":"function"},{"inputs":[{"internalType":"bytes32","name":"_id","type":"bytes32"}],"name":"getPrev","outputs":[{"internalType":"bytes32","name":"","type":"bytes32"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"getSize","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"address","name":"owner","type":"address"},{"internalType":"uint256","name":"_NICR","type":"uint256"},{"internalType":"bytes32","name":"_prevId","type":"bytes32"},{"internalType":"bytes32","name":"_nextId","type":"bytes32"}],"name":"insert","outputs":[{"internalType":"bytes32","name":"","type":"bytes32"}],"stateMutability":"nonpayable","type":"function"},{"inputs":[],"name":"isEmpty","outputs":[{"internalType":"bool","name":"","type":"bool"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"isFull","outputs":[{"internalType":"bool","name":"","type":"bool"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"maxSize","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"nextCdpNonce","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"nonExistId","outputs":[{"internalType":"bytes32","name":"","type":"bytes32"}],"stateMutability":"pure","type":"function"},{"inputs":[{"internalType":"bytes32","name":"_id","type":"bytes32"},{"internalType":"uint256","name":"_newNICR","type":"uint256"},{"internalType":"bytes32","name":"_prevId","type":"bytes32"},{"internalType":"bytes32","name":"_nextId","type":"bytes32"}],"name":"reInsert","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"bytes32","name":"_id","type":"bytes32"}],"name":"remove","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[],"name":"size","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"address","name":"owner","type":"address"},{"internalType":"uint256","name":"blockHeight","type":"uint256"},{"internalType":"uint256","name":"nonce","type":"uint256"}],"name":"toCdpId","outputs":[{"internalType":"bytes32","name":"","type":"bytes32"}],"stateMutability":"pure","type":"function"},{"inputs":[{"internalType":"uint256","name":"_NICR","type":"uint256"},{"internalType":"bytes32","name":"_prevId","type":"bytes32"},{"internalType":"bytes32","name":"_nextId","type":"bytes32"}],"name":"validInsertPosition","outputs":[{"internalType":"bool","name":"","type":"bool"}],"stateMutability":"view","type":"function"}]

0x608060405234801561001057600080fd5b50600436106101ef5760003560e01c80637c6155cd1161010f578063babd3d9a116100a2578063d168feee11610071578063d168feee146104c6578063de8fa431146104d9578063f44fac8c146104e1578063f7b67d651461050157600080fd5b8063babd3d9a1461044f578063bb038e1514610479578063bff0cecf146104a0578063c01ebf64146104b357600080fd5b8063a3f4df7e116100de578063a3f4df7e146103d8578063b0faee931461040e578063b7f8cf9b14610415578063b8f3857d1461043c57600080fd5b80637c6155cd14610393578063949d225d1461039c57806394dfe33f146103a557806395bc2673146103c557600080fd5b80634d62283111610187578063681fe70c11610156578063681fe70c1461034a578063692376391461035357806373d4a13a1461035b5780637b3011931461037e57600080fd5b80634d622831146102e657806357bdf46f146102ee57806363e1d57c146103015780636808bd581461032757600080fd5b80631e223143116101c35780631e2231431461027c5780632565b159146102845780632f3e9c95146102ab57806346087e37146102d357600080fd5b8062d43ec6146101f45780630aadd87d146102255780631c4b6690146102465780631d1a696d14610259575b600080fd5b610208610202366004611866565b60601c90565b6040516001600160a01b0390911681526020015b60405180910390f35b61023861023336600461189b565b610523565b60405190815260200161021c565b6102386102543660046118ce565b610547565b61026c610267366004611866565b61066b565b604051901515815260200161021c565b600154610238565b6102387fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff81565b6102be6102b93660046118ce565b6106dd565b6040805192835290151560208301520161021c565b6102386102e1366004611907565b6106fa565b600254610238565b61026c6102fc366004611931565b610712565b7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff610238565b610238610335366004611866565b60009081526003602052604090206001015490565b6000541561026c565b610238600081565b600154600254610369919082565b6040805192835260208301919091520161021c565b61039161038c36600461195d565b610727565b005b61023860045481565b61023860005481565b6102386103b3366004611866565b60009081526003602052604090205490565b6103916103d3366004611866565b61078f565b6104016040518060400160405280600a815260200169536f727465644364707360b01b81525081565b60405161021c919061198f565b6000610238565b6102087f00000000000000000000000058aa3de50cfef7450657c52766dd43da8747285e81565b61036961044a366004611931565b6107a3565b6000547fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff1461026c565b6102087f000000000000000000000000e89a0378237c21b94126f77ed5fa0fdd2ede2b3681565b6103916104ae3660046119f3565b6107be565b6103696104c136600461189b565b610a96565b6102386104d4366004611ab1565b610aa4565b600054610238565b6104f46104ef366004611ab1565b610aba565b60405161021c9190611b07565b61051461050f36600461189b565b610aed565b60405161021c93929190611b1a565b6bffffffffffffffffffffffff19606084901b16604083901b8217175b9392505050565b6000610551610b1e565b60006105608643600454610523565b6040516301b7d96360e01b8152600481018290529091507f000000000000000000000000e89a0378237c21b94126f77ed5fa0fdd2ede2b366001600160a01b0316906301b7d96390602401602060405180830381865afa1580156105c8573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906105ec9190611b3f565b1561064d5760405162461bcd60e51b815260206004820152602660248201527f536f72746564436470733a206e6577206964206973204e4f54206e6f6e4578696044820152657374656e742160d01b60648201526084015b60405180910390fd5b61065981868686610bdd565b60048054600101905595945050505050565b60008082158015906106895750600154831480610689575060025483145b9050806106d757600083815260036020908152604091829020825180840190935280548352600101549082015283158015906106d357508051158015906106d35750602081015115155b9150505b92915050565b6000806106ec86868686610e3e565b915091505b94509492505050565b60008061070984848380610e3e565b50949350505050565b600061071f848484610ee8565b949350505050565b61072f610b1e565b6107388461066b565b6107545760405162461bcd60e51b815260040161064490611b58565b600083116107745760405162461bcd60e51b815260040161064490611ba0565b61077d8461114a565b61078984848484610bdd565b50505050565b61079761126a565b6107a08161114a565b50565b6000806107b18585856112f3565b915091505b935093915050565b6107c661126a565b80516001811161083e5760405162461bcd60e51b815260206004820152603860248201527f536f72746564436470733a20626174636852656d6f76652829206f6e6c79206160448201527f70706c7920746f206d756c7469706c65206364704964732100000000000000006064820152608401610644565b6000600160020160008460008151811061085a5761085a611be1565b602002602001015181526020019081526020016000206001015490506000600160020160008560018661088d9190611c0d565b8151811061089d5761089d611be1565b602002602001015181526020019081526020016000206000015490506000801b821415806108ca57508015155b61092e5760405162461bcd60e51b815260206004820152602f60248201527f536f72746564436470733a20626174636852656d6f76652829206c656176652060448201526e5a45524f206e6f6465206c6566742160881b6064820152608401610644565b60005b838110156109875761095b85828151811061094e5761094e611be1565b602002602001015161066b565b6109775760405162461bcd60e51b815260040161064490611b58565b61098081611c20565b9050610931565b5081156109a45760008281526003602052604090208190556109aa565b60018190555b80156109c95760008181526003602052604090206001018290556109cf565b60028290555b60005b83811015610a7e57600160020160008683815181106109f3576109f3611be1565b60200260200101518152602001908152602001600020600080820160009055600182016000905550507f5254e609a97bab37b7cc79fe128f85c097bd6015c6e1624ae0ba392eb9753205858281518110610a4f57610a4f611be1565b6020026020010151604051610a6691815260200190565b60405180910390a1610a7781611c20565b90506109d2565b5082600054610a8d9190611c0d565b60005550505050565b6000806107b18585856114a2565b600080610ab28382806114a2565b509392505050565b60606000610ac98382806114a2565b5090508015610ae7576000610ae084828085611532565b5090935050505b50919050565b60606000806000610aff8787876114a2565b509050610b0e87878784611532565b9350935093505093509350939050565b336001600160a01b037f00000000000000000000000058aa3de50cfef7450657c52766dd43da8747285e161480610b7d5750336001600160a01b037f000000000000000000000000e89a0378237c21b94126f77ed5fa0fdd2ede2b3616145b610bdb5760405162461bcd60e51b815260206004820152602960248201527f536f72746564436470733a2043616c6c6572206973206e65697468657220424f604482015268206e6f72204364704d60b81b6064820152608401610644565b565b6000547fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff03610c4e5760405162461bcd60e51b815260206004820152601860248201527f536f72746564436470733a204c6973742069732066756c6c00000000000000006044820152606401610644565b610c578461066b565b15610cb75760405162461bcd60e51b815260206004820152602a60248201527f536f72746564436470733a204c69737420616c726561647920636f6e7461696e6044820152697320746865206e6f646560b01b6064820152608401610644565b83610d045760405162461bcd60e51b815260206004820152601d60248201527f536f72746564436470733a2049642063616e6e6f74206265207a65726f0000006044820152606401610644565b60008311610d245760405162461bcd60e51b815260040161064490611ba0565b8181610d31858383610ee8565b610d4657610d408583836112f3565b90925090505b81158015610d52575080155b15610d665760018690556002869055610dec565b81610d925760018054600088815260036020526040808220839055918152208101879055869055610dec565b80610dbf576002805460008881526003602052604080822060010183905591815220879055869055610dec565b60008681526003602052604080822083815560019081018590558483528183208990558383529120018690555b600054610dfa906001611c39565b60005560408051878152602081018790527f5bfe8a52ad26ac6ee7b0cd46d2fd92be04735a31c45ef8aa3d4b7ea1b61bbc1f910160405180910390a1505050505050565b600080808415610e4e5784610e52565b6002545b90506000805b8215610ed857886001600160a01b0316610e728460601c90565b6001600160a01b031603610ea457878203610e9657826001945094505050506106f1565b610ea1826001611c39565b91505b610ead81611c20565b600093845260036020526040909320600101549290508515801590610ed25750858110155b15610e58575b5090976000975095505050505050565b600082158015610ef6575081155b15610f0757600054155b9050610540565b82610fac5760015482148015610f005750604051636e2d76d360e01b8152600481018390527f000000000000000000000000e89a0378237c21b94126f77ed5fa0fdd2ede2b366001600160a01b031690636e2d76d3906024015b602060405180830381865afa158015610f7e573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610fa29190611b3f565b8410159050610540565b816110505760025483148015610f005750604051636e2d76d360e01b8152600481018490527f000000000000000000000000e89a0378237c21b94126f77ed5fa0fdd2ede2b366001600160a01b031690636e2d76d390602401602060405180830381865afa158015611022573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906110469190611b3f565b8411159050610540565b600083815260036020526040902054821480156110f65750604051636e2d76d360e01b81526004810184905284907f000000000000000000000000e89a0378237c21b94126f77ed5fa0fdd2ede2b366001600160a01b031690636e2d76d390602401602060405180830381865afa1580156110cf573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906110f39190611b3f565b10155b8015610f005750604051636e2d76d360e01b8152600481018390527f000000000000000000000000e89a0378237c21b94126f77ed5fa0fdd2ede2b366001600160a01b031690636e2d76d390602401610f61565b6111538161066b565b61116f5760405162461bcd60e51b815260040161064490611b58565b600160005411156112015760015481036111a557600081815260036020526040808220546001818155908352908220015561120c565b60025481036111d057600081815260036020526040808220600101546002819055825281205561120c565b600081815260036020526040808220805460019182018054855283852082905554908452919092209091015561120c565b600060018190556002555b6000818152600360205260408120818155600190810182905590546112319190611c0d565b6000556040518181527f5254e609a97bab37b7cc79fe128f85c097bd6015c6e1624ae0ba392eb97532059060200160405180910390a150565b336001600160a01b037f000000000000000000000000e89a0378237c21b94126f77ed5fa0fdd2ede2b361614610bdb5760405162461bcd60e51b815260206004820152602860248201527f536f72746564436470733a2043616c6c6572206973206e6f74207468652043646044820152673826b0b730b3b2b960c11b6064820152608401610644565b600080838381156113a4576113078261066b565b158061139a5750604051636e2d76d360e01b8152600481018390527f000000000000000000000000e89a0378237c21b94126f77ed5fa0fdd2ede2b366001600160a01b031690636e2d76d390602401602060405180830381865afa158015611373573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906113979190611b3f565b87115b156113a457600091505b801561144f576113b38161066b565b15806114465750604051636e2d76d360e01b8152600481018290527f000000000000000000000000e89a0378237c21b94126f77ed5fa0fdd2ede2b366001600160a01b031690636e2d76d390602401602060405180830381865afa15801561141f573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906114439190611b3f565b87105b1561144f575060005b8115801561145b575080155b1561147a5761146f87600160000154611651565b9350935050506107b6565b816114895761146f8782611757565b806114985761146f8783611651565b61146f8783611651565b6000808084156114b257846114b6565b6002545b90506000805b821561152657876001600160a01b03166114d68460601c90565b6001600160a01b0316036114f2576114ef826001611c39565b91505b6114fb81611c20565b6000938452600360205260409093206001015492905085158015906115205750858110155b156114bc575b50969095509350505050565b60606000808360000361155957505060408051600080825260208201909252915080611647565b60008467ffffffffffffffff811115611574576115746119dd565b60405190808252806020026020018201604052801561159d578160200160208202803683370190505b5090506000808089156115b057896115b4565b6002545b90505b801561163d578a6001600160a01b03166115d18260601c90565b6001600160a01b03160361160957808483815181106115f2576115f2611be1565b602090810291909101015261160682611c20565b91505b61161283611c20565b6000918252600360205260409091206001015490925088158015906116375750888310155b156115b7575b9295509350909150505b9450945094915050565b600080826001600001541480156116f05750604051636e2d76d360e01b8152600481018490527f000000000000000000000000e89a0378237c21b94126f77ed5fa0fdd2ede2b366001600160a01b031690636e2d76d390602401602060405180830381865afa1580156116c8573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906116ec9190611b3f565b8410155b1561170057506000905081611750565b60008381526003602052604090205483905b81158015906117295750611727868383610ee8565b155b1561174a575060009081526003602052604080822054808352912054611712565b90925090505b9250929050565b6000808260018001541480156117f55750604051636e2d76d360e01b8152600481018490527f000000000000000000000000e89a0378237c21b94126f77ed5fa0fdd2ede2b366001600160a01b031690636e2d76d390602401602060405180830381865afa1580156117cd573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906117f19190611b3f565b8411155b1561180557508190506000611750565b60008381526003602052604090206001015483905b8115801590611831575061182f868284610ee8565b155b1561185c5750600090815260036020526040808220600190810154808452919092209091015461181a565b9590945092505050565b60006020828403121561187857600080fd5b5035919050565b80356001600160a01b038116811461189657600080fd5b919050565b6000806000606084860312156118b057600080fd5b6118b98461187f565b95602085013595506040909401359392505050565b600080600080608085870312156118e457600080fd5b6118ed8561187f565b966020860135965060408601359560600135945092505050565b6000806040838503121561191a57600080fd5b6119238361187f565b946020939093013593505050565b60008060006060848603121561194657600080fd5b505081359360208301359350604090920135919050565b6000806000806080858703121561197357600080fd5b5050823594602084013594506040840135936060013592509050565b600060208083528351808285015260005b818110156119bc578581018301518582016040015282016119a0565b506000604082860101526040601f19601f8301168501019250505092915050565b634e487b7160e01b600052604160045260246000fd5b60006020808385031215611a0657600080fd5b823567ffffffffffffffff80821115611a1e57600080fd5b818501915085601f830112611a3257600080fd5b813581811115611a4457611a446119dd565b8060051b604051601f19603f83011681018181108582111715611a6957611a696119dd565b604052918252848201925083810185019188831115611a8757600080fd5b938501935b82851015611aa557843584529385019392850192611a8c565b98975050505050505050565b600060208284031215611ac357600080fd5b6105408261187f565b600081518084526020808501945080840160005b83811015611afc57815187529582019590820190600101611ae0565b509495945050505050565b6020815260006105406020830184611acc565b606081526000611b2d6060830186611acc565b60208301949094525060400152919050565b600060208284031215611b5157600080fd5b5051919050565b60208082526028908201527f536f72746564436470733a204c69737420646f6573206e6f7420636f6e7461696040820152671b881d1a19481a5960c21b606082015260800190565b60208082526021908201527f536f72746564436470733a204e494352206d75737420626520706f73697469766040820152606560f81b606082015260800190565b634e487b7160e01b600052603260045260246000fd5b634e487b7160e01b600052601160045260246000fd5b818103818111156106d7576106d7611bf7565b600060018201611c3257611c32611bf7565b5060010190565b808201808211156106d7576106d7611bf756fea2646970667358221220d8738dbe3a4709795f68c52149473eb0d7788c10e54f90b9d30b11a4e0523ddc64736f6c63430008110033