-
Notifications
You must be signed in to change notification settings - Fork 11.7k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Add an Enumerable Set data structure #1240
Comments
I think we should start by providing the linked list for addresses only (likewise for other data structures). It should cover most use cases. |
I think this is a pretty cool idea. Has anyone worked on this yet? |
Hi guys, I did an implementation for Singly and Doubly Linked Lists, which I would be happy to transfer to your repo. These contracts have been thoroughly tested: https://github.com/HQ20/contracts/tree/dev/contracts/lists I have also an implementation for an Ordered Doubly Linked list in the same directory, but one of the methods is O(N) so it might not be safe enough for normal use. I also have an implementation of a Linked List using OOP principles, with each element in the list being a contract. Nice and clear implementation, with horrid gas costs. I can point you to it as well if you are interested. I'd love to hear your feedback, thanks. |
Interesting, thanks @albertocuestacanada! We've seen many projects roll out their own collections, sometimes with bad results (@ElOpio mind chiming in on this?). About your specific implementation, we'd probably prefer to have the collections be a library that operates on some custom struct, like |
Thank you @albertocuestacanada! We've defined clearer requirements for this feature for whoever wants to open a pull request. The focus of the issue is on building an enumerable set, rather than a generic linked list. The linked list is simply the way the set should be implemented.
|
An enumerable address set implemented as a library was not too far from what I've got already. It's drafted already (I'll need to write tests for two functions). Do I need permissions to create a branch in your repo and push the code? |
Cool! Fork this repo and create a branch in the fork, then open a PR from there. |
Apologies for missing that critical line in CONTRIBUTING.md @frangio Here is the draft of Enumerable.sol. I left it in drafts, not sure where would you prefer to put it. Check if it is what you are after. If so I'll write the tests and have a think about performance. It was developed from a Doubly Linked List, but since you need less features there is probably stuff to optimize. |
@nventuro yes, we have seen many projects copying or reimplementing their own collections. It would be nice to start a do-group to list all of these, maybe in a wiki topic in our forum, to analyze the different approaches and maybe even get people working together. In the ideal case, this would be a push to get generics into the language. About the road forward, I agree with @frangio's approach to start with a set of addresses. This is immediately useful to many use cases, and will teach us about limitations and possible ways to generalize to other types and underlying structures. |
@albertocuestacanada Is it possible to use addresses as ids? I was imagining something much simpler than what you shared, but I don't know if there are reasons why it can't be as simple as a |
Hi @frangio, as long as you use a linked list implementation I don't think that you can use addresses as ids in a meaningful way. addresses as ids In a linked list you need to record at least two data points per element: the data that needs to be stored and some way of retrieving the next element. This usually points to using a struct and mapping like these:
I'm using uint256 because I need ids and to generate them the easiest is to use a counter (I can reuse Counters from your library, btw). complex implementation Using a doubly linked list for an enumerable set might be overkill, since you don't need arbitrary insertion. For the Enumerable Set that you requested, there are two implementations that are simpler.
The implementation also becomes more complex from the requirement of coding it as a library. next steps I think that we need to think a bit on the requirements:
@ElOpio, if you give me some time I'm writing an article comparing the different implementations, it might be useful. I've got already some of the work done. @frangio, also, what do you guys use to deploy contracts and link artifacts in this repo? There is nothing in the migrations or .openzeppelin folders. |
I think @frangio wasn't proposing a regular In this sense, what we aren't building isn't a list, but rather an enumerable set: the list is simply the tool we use to get ordering. This is similar to what you mention here:
Thinking out loud, we may need a sentinel value to handle the Regarding ordering, as far as I know the term enumerable implies sorting, so I'd say yes.
I'm not sure what you mean by deployments: all of OpenZeppelin Contracts |
Ok, I understand how you want to implement the EnumerableSet with We can either have a sentinel value for
An Finally, you can have
It would double the gas cost of My only question at this point would be: Do we use a I can do this next week, no problem. |
It looks good! It's definitely what I had in mind. Keep in mind that library functions should be I have a few items I'd like to discuss though. @nventuro and I have an intuition that the library shouldn't emit any built-in events. Events should be left up to the user of the library. What do you think? I also don't like that Another thing that I think is worth discussing a bit more is whether to make it doubly linked or not. Something interesting about the Gnosis Safe posted in OP is that it is singly linked and Lastly, this one is a bit more radical but there is another pattern for implementing enumerable sets which is using an array |
@frangio, I've corrected the visibility, and also managed to get rid of everything related to the Now enumerate On Apart from that, On this tradeoff I have no opinion, it depends on how you envision double or single linked address[] and address => uint Up to here, it seems to me that it has the same performance and features as the current implementation. A slightly better implementation is using the If you want, I can do an implementation of this pattern as well. It's fun 🤓 |
Great analysis, thank you. I agree that the consideration that We should be clear that for this feature we are only interested in storing unique items, and we are not interested in their ordering in the array. In the alternative implementation, |
@frangio, you should have told me that you were just interested in a canonical implementation of a Set. We would have got here a lot faster :) For an unordered data set using a linked list makes no sense. The approach that you mention: storing values in an array, infilling on remove, and using an index to have O(1) for contains seems the right approach. Besides, it's a very simple implementation, which is always good. |
Awesome. I would say let's put it in |
Done. I've got a linting error: I would think that |
The issue is @frangio do you think its time to graduate this issue into a PR? |
Thanks @nventuro, linting fixed now 👍 |
Yes @albertocuestacanada please submit a PR. |
The OwnerManager contract from Gnosis safe is basically an implementation for a LinkedList with O(1) check for
contains(item)
. It's a mapping with the same type for keys and values (addresses in this case), where each item points to the next one in the mapping.Could be interesting to abstract this and build it into OZ. Note that, given the lack of generics in Solidity, we may need to provide the same contract for different data types.
The text was updated successfully, but these errors were encountered: