Implement todo features in Inventory.sol

0xnonso commented 1 year ago

Context (Problem, Motivation, Solution)

Prevent cards from being added/removed to/from the inventory during a game
Limit maximum number of card copies in a deck to three

Describe Your Changes

Added a modifier notInGame() to limit players from addding/removing cards to/from the inventory contract while participating in a game
Modify checkDeck() to check if a player possesses more than three copies of a card in a deck

Checklist
[x] I have performed a self-review of my code
[x] I ran make lint and fixed resulting issues
[x] I ran the relevant tests and they all pass
[x] I wrote tests for my new features, or added regression tests for the bug I fixed

Testing

todo

0xnonso commented 1 year ago

I added a very basic test for checkDeck() here. The test reverts fine if card copy is gt MAX_CARD_COPY but foundry's expectRevert() doesn't seem to catch it. 🥲 Might be an issue with the encoding if not then its probably a foundry bug.

norswap commented 1 year ago

Did you figure the testing issue? I had some time on the plane, so I coded up a bubble sort and tried testing with it, the test passed :)

Here's the bubble sort implementation, so you can benchmark which test implem is the most gas efficient:

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.0;

library Utils {
    function sort(uint256[] memory original) pure public returns (uint256[] memory) {
        if (original.length == 0) {
            return original;
        }
        uint256[] memory array = new uint256[](original.length);
        array[0] = original[0];

        // Each iteration inserts item `original[i]` into `array`, whose size is `i` and
        // will be expanded to size `i+1` as a result of the insertion.
        for (uint256 i = 1; i < array.length - 1; ++i) {
            uint256 j;
            // Each iteration will assign the value of `array[j]` based on the value of `array[j-1]
            // and `original[i]`.
            for (j = i; j > 0; --j) {
                if (original[i] > array[j-1]) {
                    array[j] = original[i];
                    break; // value inserted at j, no need to continue
                } else {
                    array[j] = array[j-1];
                }
            }
            // If `j == 0`, `original[i]` wasn't inserted yet
            if (j == 0) {
                array[0] = original[i];
            }
        }
        return array;
    }
}

0xnonso commented 1 year ago

Did you figure the testing issue? I had some time on the plane, so I coded up a bubble sort and tried testing with it, the test passed :)

Here's the bubble sort implementation, so you can benchmark which test implem is the most gas efficient:

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.0;

library Utils {
    function sort(uint256[] memory original) pure public returns (uint256[] memory) {
        if (original.length == 0) {
            return original;
        }
        uint256[] memory array = new uint256[](original.length);
        array[0] = original[0];

        // Each iteration inserts item `original[i]` into `array`, whose size is `i` and
        // will be expanded to size `i+1` as a result of the insertion.
        for (uint256 i = 1; i < array.length - 1; ++i) {
            uint256 j;
            // Each iteration will assign the value of `array[j]` based on the value of `array[j-1]
            // and `original[i]`.
            for (j = i; j > 0; --j) {
                if (original[i] > array[j-1]) {
                    array[j] = original[i];
                    break; // value inserted at j, no need to continue
                } else {
                    array[j] = array[j-1];
                }
            }
            // If `j == 0`, `original[i]` wasn't inserted yet
            if (j == 0) {
                array[0] = original[i];
            }
        }
        return array;
    }
}

yes yes, i figured the testing issues out. It was my fault, didn't realize that foundry was expecting the wrong call to revert!

norswap commented 1 year ago

For easier reviewing, here's a diff view with the linting PR: https://github.com/norswap/0xFable/compare/ns/lint...0xnonso:master

norswap commented 1 year ago

linting PR rebased onto master!

0xnonso commented 1 year ago

Looks pretty good to me! Let me merge the lint PR and we can rebase this on top of master then merge.

Could you check the gas usage between the mergesort and the bubble sort?

sure! seems there is a bug in the bubble sort implementation which always sets the last iteration to zero

0xnonso commented 1 year ago

not decreasing the array length in the initial loop fixes it. so updated code would look like:

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.0;

library Utils {
    function sort(uint256[] memory original) pure public returns (uint256[] memory) {
        if (original.length == 0) {
            return original;
        }
        uint256[] memory array = new uint256[](original.length);
        array[0] = original[0];

        // Each iteration inserts item `original[i]` into `array`, whose size is `i` and
        // will be expanded to size `i+1` as a result of the insertion.
        for (uint256 i = 1; i < array.length; ++i) {
            uint256 j;
            // Each iteration will assign the value of `array[j]` based on the value of `array[j-1]
            // and `original[i]`.
            for (j = i; j > 0; --j) {
                if (original[i] > array[j-1]) {
                    array[j] = original[i];
                    break; // value inserted at j, no need to continue
                } else {
                    array[j] = array[j-1];
                }
            }
            // If `j == 0`, `original[i]` wasn't inserted yet
            if (j == 0) {
                array[0] = original[i];
            }
        }
        return array;
    }
}

0xnonso commented 1 year ago

mergesort implementation is generally cheaper in most cases. this is a gas benchmark using a randomly generated array of length 48.

uint256[] public randomArray = [9, 4, 12, 35, 22, 17, 46, 7, 28, 31, 19, 11, 42, 26, 38, 14, 2, 29, 1, 16, 23, 5, 33, 8, 45, 43, 15, 32, 18, 13, 10, 47, 20, 27, 3, 6, 41, 25, 40, 34, 21, 30, 37, 24, 36, 39, 44, 0];

norswap commented 1 year ago

not decreasing the array length in the initial loop fixes it.

Yes, my bad!

mergesort implementation is generally cheaper in most cases. this is a gas benchmark using a randomly generated array of length 48.

Super interesting, thanks for running the experiment!

norswap commented 1 year ago

I missed something super fundamental in this: we're comparing card IDs, but card IDs are unique (they're NFT IDs). Instead, we need to compare some kind of "card type" identifier. Which we currently don't have, it being a demo and everything.

I think we should add a bogus cardType value in in the Card structure (can be an uint32 for now, we can change later) and perform the check using this value.

0xnonso commented 1 year ago

okok. currently the identifier for inventory cards are based on their tokenId so how would the cardType be determined?

norswap commented 1 year ago

okok. currently the identifier for inventory cards are based on their tokenId so how would the cardType be determined?

This is what I meant above:

I think we should add a bogus cardType value in in the Card structure (can be an uint32 for now, we can change later) and perform the check using this value.

Basically, tokenID is an NFT token ID that can be used in the CardCollection to get the characteristics of the token (where token == unique card, just like a unique physical copy of a card in Magic)

Right now you can use this token to get the name of the card, it's stats, etc ... (the getCard function gets you all of that).

When we have multiple cards in decks at the moment we simply give them the same name and the same stats. This is a bit of a hack.

The proper solution would be to map each card (token ID) in CardCollection to a cardTypeID, then map that cardTypeID to names, stats, etc... In the future, cards may have some features that are not shared between all cards of the same kind. For instance, some cards may be shiny while others are plain, or some cards may get a special illustration, or they're from a different edition, ... but they still count as the same "card type" form a gameplay perspective.

The simplest hacky solution is just to add a cardTypeID field in the Card structure to make this work, but if you feel like it, you can go the extra mile and implement the proper system here.

I think it's probably preferable to just go with a hack and open a new issue + PR for the better system :)

0xFableOrg / 0xFable