Repository: praw-dev/praw
Pull request #1547 (2020-08-09 13:41:06)

Use least-recently-used eviction policy for stream BoundedSet
This PR changes the `BoundedSet` class used for streams to evict its least-recently-used element, rather than its oldest element.

The change includes a unit test where elements are duplicated in the stream. In this test, new items are added and removed from the head of the listing one one at a time. Even though the original items are seen at least every other fetch, the new items end up filling the cache and causing us to forget the old items.

I think I've seen behavior like this in production, though I don't have proof. In a slow-moving subreddit where a lot of submissions get removed, we've seen duplicates in the `submissions` stream. I think this scenario is basically similar to the test case, in that a high proportion of newly-seen items don't remain present in the listing.

It's presumably not possible to completely avoid duplicates when the cache is bounded and items can leave and re-enter the listing (e.g. because of removals). I'm not sure if there are real-world cases where the new behavior is worse.

LilSpazJoekp: Could you squash commits please?
leviroth: Done.
PythonCoderAS: I added a PR (https://github.com/leviroth/praw/pull/1) that will add a few more tests, including a direct test of the LRU property.
LilSpazJoekp: Could you squash your commits?
PythonCoderAS: > Could you squash your commits?

You could just merge and squash, as previously mentioned.
PythonCoderAS: Reading through the initial description, an extra solution is letting the user specify the bound size, so they can set it to 1000 items for example, but leave the default.

Patch:
diff --git a/praw/models/reddit/base.py b/praw/models/reddit/base.py
index bfc42959..b6ebf18d 100644
--- a/praw/models/reddit/base.py
+++ b/praw/models/reddit/base.py
@@ -41,31 +41,14 @@ class RedditBase(PRAWBase):
         """Return the hash of the current instance."""
         return hash(self.__class__.__name__) ^ hash(str(self).lower())
 
-    def __init__(
-        self,
-        reddit: "Reddit",
-        _data: Optional[Dict[str, Any]],
-        _extra_attribute_to_check: Optional[str] = None,
-        _fetched: bool = False,
-        _str_field: bool = True,
-    ):
+    def __init__(self, reddit: "Reddit", _data: Optional[Dict[str, Any]]):
         """Initialize a RedditBase instance (or a subclass).
 
         :param reddit: An instance of :class:`~.Reddit`.
 
         """
         super().__init__(reddit, _data=_data)
-        self._fetched = _fetched
-        if _str_field and self.STR_FIELD not in self.__dict__:
-            if (
-                _extra_attribute_to_check is not None
-                and _extra_attribute_to_check in self.__dict__
-            ):
-                return
-            raise ValueError(
-                f"An invalid value was specified for {self.STR_FIELD}. Check that the "
-                f"argument for the {self.STR_FIELD} parameter is not empty."
-            )
+        self._fetched = False
 
     def __repr__(self) -> str:
         """Return an object initialization representation of the instance."""
diff --git a/praw/models/reddit/collections.py b/praw/models/reddit/collections.py
index 08e0bded..2b3ee1df 100644
--- a/praw/models/reddit/collections.py
+++ b/praw/models/reddit/collections.py
@@ -108,19 +108,19 @@ class Collection(RedditBase):
         :param collection_id: The ID of the Collection (optional).
         :param permalink: The permalink of the Collection (optional).
         """
+        super().__init__(reddit, _data)
+
         if (_data, collection_id, permalink).count(None) != 2:
             raise TypeError(
                 "Exactly one of _data, collection_id, or permalink must be provided."
             )
 
-        if permalink:
+        if permalink is not None:
             collection_id = self._url_parts(permalink)[4]
 
-        if collection_id:
+        if collection_id is not None:
             self.collection_id = collection_id  # set from _data otherwise
 
-        super().__init__(reddit, _data)
-
         self._info_params = {
             "collection_id": self.collection_id,
             "include_links": True,
diff --git a/praw/models/reddit/comment.py b/praw/models/reddit/comment.py
index da4df53c..bcffea5a 100644
--- a/praw/models/reddit/comment.py
+++ b/praw/models/reddit/comment.py
@@ -1,6 +1,10 @@
 """Provide the Comment class."""
 from typing import TYPE_CHECKING, Any, Dict, Optional, Union
 
+from ...const import API_PATH
+from ...exceptions import ClientException, InvalidURL
+from ...util.cache import cachedproperty
+from ..comment_forest import CommentForest
 from .base import RedditBase
 from .mixins import (
     FullnameMixin,
@@ -9,10 +13,6 @@ from .mixins import (
     UserContentMixin,
 )
 from .redditor import Redditor
-from ..comment_forest import CommentForest
-from ...const import API_PATH
-from ...exceptions import ClientException, InvalidURL
-from ...util.cache import cachedproperty
 
 if TYPE_CHECKING:  # pragma: no cover
     from ... import Reddit
@@ -114,7 +114,6 @@ class Comment(InboxableMixin, UserContentMixin, FullnameMixin, RedditBase):
         Sort order and reply limit can be set with the ``reply_sort`` and
         ``reply_limit`` attributes before replies are fetched, including any call to
         :meth:`.refresh`:
-
         .. code-block:: python
 
             comment.reply_sort = "new"
@@ -156,16 +155,15 @@ class Comment(InboxableMixin, UserContentMixin, FullnameMixin, RedditBase):
         """Construct an instance of the Comment object."""
         if (id, url, _data).count(None) != 2:
             raise TypeError("Exactly one of `id`, `url`, or `_data` must be provided.")
-        fetched = False
         self._replies = []
         self._submission = None
+        super().__init__(reddit, _data=_data)
         if id:
             self.id = id
         elif url:
             self.id = self.id_from_url(url)
         else:
-            fetched = True
-        super().__init__(reddit, _data=_data, _fetched=fetched)
+            self._fetched = True
 
     def __setattr__(
         self,
diff --git a/praw/models/reddit/live.py b/praw/models/reddit/live.py
index dae55fa7..486b4ca1 100644
--- a/praw/models/reddit/live.py
+++ b/praw/models/reddit/live.py
@@ -388,11 +388,11 @@ class LiveThread(RedditBase):
         :param id: A live thread ID, e.g., ``"ukaeu1ik4sw5"``
 
         """
-        if (id, _data).count(None) != 1:
+        if bool(id) == bool(_data):
             raise TypeError("Either `id` or `_data` must be provided.")
+        super().__init__(reddit, _data=_data)
         if id:
             self.id = id
-        super().__init__(reddit, _data=_data)
 
     def _fetch_info(self):
         return "liveabout", {"id": self.id}, None
@@ -724,11 +724,12 @@ class LiveUpdate(FullnameMixin, RedditBase):
             # Since _data (part of JSON returned from reddit) have no thread ID,
             # self._thread must be set by the caller of LiveUpdate(). See the code of
             # LiveThread.updates() for example.
-            super().__init__(reddit, _data=_data, _fetched=True)
+            super().__init__(reddit, _data=_data)
+            self._fetched = True
         elif thread_id and update_id:
-            self.id = update_id
             super().__init__(reddit, _data=None)
             self._thread = LiveThread(self._reddit, thread_id)
+            self.id = update_id
         else:
             raise TypeError(
                 "Either `thread_id` and `update_id`, or `_data` must be provided."
diff --git a/praw/models/reddit/message.py b/praw/models/reddit/message.py
index 759d94ce..1a3a08fd 100644
--- a/praw/models/reddit/message.py
+++ b/praw/models/reddit/message.py
@@ -79,7 +79,8 @@ class Message(InboxableMixin, ReplyableMixin, FullnameMixin, RedditBase):
 
     def __init__(self, reddit: "Reddit", _data: Dict[str, Any]):
         """Construct an instance of the Message object."""
-        super().__init__(reddit, _data=_data, _fetched=True)
+        super().__init__(reddit, _data=_data)
+        self._fetched = True
 
     def delete(self):
         """Delete the message.
diff --git a/praw/models/reddit/modmail.py b/praw/models/reddit/modmail.py
index 7017c174..9763ae82 100644
--- a/praw/models/reddit/modmail.py
+++ b/praw/models/reddit/modmail.py
@@ -129,14 +129,13 @@ class ModmailConversation(RedditBase):
         :param mark_read: If True, conversation is marked as read (default: False).
 
         """
+        super().__init__(reddit, _data=_data)
         if bool(id) == bool(_data):
             raise TypeError("Either `id` or `_data` must be provided.")
 
         if id:
             self.id = id
 
-        super().__init__(reddit, _data=_data)
-
         self._info_params = {"markRead": True} if mark_read else None
 
     def _build_conversation_list(self, other_conversations):
diff --git a/praw/models/reddit/redditor.py b/praw/models/reddit/redditor.py
index f23f7ff8..39c73122 100644
--- a/praw/models/reddit/redditor.py
+++ b/praw/models/reddit/redditor.py
@@ -144,12 +144,12 @@ class Redditor(MessageableMixin, RedditorListingMixin, FullnameMixin, RedditBase
             assert (
                 isinstance(_data, dict) and "name" in _data
             ), "Please file a bug with PRAW"
+        super().__init__(reddit, _data=_data)
         self._listing_use_sort = True
         if name:
             self.name = name
         elif fullname:
             self._fullname = fullname
-        super().__init__(reddit, _data=_data, _extra_attribute_to_check="_fullname")
 
     def _fetch_username(self, fullname):
         return self._reddit.get(API_PATH["user_by_fullname"], params={"ids": fullname})[
diff --git a/praw/models/reddit/removal_reasons.py b/praw/models/reddit/removal_reasons.py
index 9dbc1514..b7108ddb 100644
--- a/praw/models/reddit/removal_reasons.py
+++ b/praw/models/reddit/removal_reasons.py
@@ -86,8 +86,7 @@ class RemovalReason(RedditBase):
         if (id, _data).count(None) != 1:
             raise ValueError("Either id or _data needs to be given.")
 
-        if id:
-            self.id = id
+        self.id = id
         self.subreddit = subreddit
         super().__init__(reddit, _data=_data)
 
diff --git a/praw/models/reddit/rules.py b/praw/models/reddit/rules.py
index 5335b4b9..ccaa52e4 100644
--- a/praw/models/reddit/rules.py
+++ b/praw/models/reddit/rules.py
@@ -76,8 +76,7 @@ class Rule(RedditBase):
         """Construct an instance of the Rule object."""
         if (short_name, _data).count(None) != 1:
             raise ValueError("Either short_name or _data needs to be given.")
-        if short_name:
-            self.short_name = short_name
+        self.short_name = short_name
         # Note: The subreddit parameter can be None, because the objector does not know
         # this info. In that case, it is the responsibility of the caller to set the
         # `subreddit` property on the returned value.
diff --git a/praw/models/reddit/submission.py b/praw/models/reddit/submission.py
index 861187de..23acf718 100644
--- a/praw/models/reddit/submission.py
+++ b/praw/models/reddit/submission.py
@@ -531,18 +531,17 @@ class Submission(SubmissionListingMixin, UserContentMixin, FullnameMixin, Reddit
         """
         if (id, url, _data).count(None) != 2:
             raise TypeError("Exactly one of `id`, `url`, or `_data` must be provided.")
+        super().__init__(reddit, _data=_data)
         self.comment_limit = 2048
 
         # Specify the sort order for ``comments``
         self.comment_sort = "confidence"
 
-        if id:
+        if id is not None:
             self.id = id
-        elif url:
+        elif url is not None:
             self.id = self.id_from_url(url)
 
-        super().__init__(reddit, _data=_data)
-
         self._comments_by_id = {}
 
     def __setattr__(self, attribute: str, value: Any):
diff --git a/praw/models/reddit/subreddit.py b/praw/models/reddit/subreddit.py
index 46a32589..b557a777 100644
--- a/praw/models/reddit/subreddit.py
+++ b/praw/models/reddit/subreddit.py
@@ -543,11 +543,11 @@ class Subreddit(MessageableMixin, SubredditListingMixin, FullnameMixin, RedditBa
             via: ``reddit.subreddit("subreddit_name")``
 
         """
-        if (display_name, _data).count(None) != 1:
+        if bool(display_name) == bool(_data):
             raise TypeError("Either `display_name` or `_data` must be provided.")
+        super().__init__(reddit, _data=_data)
         if display_name:
             self.display_name = display_name
-        super().__init__(reddit, _data=_data)
         self._path = API_PATH["subreddit"].format(subreddit=self)
 
     def _convert_to_fancypants(self, markdown_text: str):
@@ -2435,10 +2435,9 @@ class SubredditModerationStream:
             which to fetch conversations (default: None).
         :param sort: Can be one of: mod, recent, unread, user
             (default: recent).
-        :param state: Can be one of: all, appeals, archived, default, highlighted,
-            inbox, inprogress, mod, new, notifications (default: all). "all" does not
-            include mod or archived conversations. "inbox" does not include appeals
-            conversations.
+        :param state: Can be one of: all, archived, highlighted, inprogress,
+            mod, new, notifications, or appeals, (default: all). "all" does not
+            include internal, archived, or appeals conversations.
 
         Keyword arguments are passed to :func:`.stream_generator`.
 
diff --git a/praw/models/reddit/wikipage.py b/praw/models/reddit/wikipage.py
index ae76eb31..4c8bdaf6 100644
--- a/praw/models/reddit/wikipage.py
+++ b/praw/models/reddit/wikipage.py
@@ -175,7 +175,7 @@ class WikiPage(RedditBase):
         self.name = name
         self._revision = revision
         self.subreddit = subreddit
-        super().__init__(reddit, _data=_data, _str_field=False)
+        super().__init__(reddit, _data=_data)
 
     def __repr__(self) -> str:
         """Return an object initialization representation of the instance."""
diff --git a/praw/models/util.py b/praw/models/util.py
index 48560d05..ecbeb313 100644
--- a/praw/models/util.py
+++ b/praw/models/util.py
@@ -1,6 +1,7 @@
 """Provide helper classes used by other models."""
 import random
 import time
+from collections import OrderedDict
 from typing import Any, Callable, Generator, List, Optional, Set
 
 
@@ -13,19 +14,23 @@ class BoundedSet:
     def __init__(self, max_items: int):
         """Construct an instance of the BoundedSet."""
         self.max_items = max_items
-        self._fifo = []
-        self._set = set()
+        self._set = OrderedDict()
 
     def __contains__(self, item: Any) -> bool:
         """Test if the BoundedSet contains item."""
+        self._access(item)
         return item in self._set
 
+    def _access(self, item: Any):
+        if item in self._set:
+            self._set.move_to_end(item)
+
     def add(self, item: Any):
         """Add an item to the set discarding the oldest item if necessary."""
-        if len(self._set) == self.max_items:
-            self._set.remove(self._fifo.pop(0))
-        self._fifo.append(item)
-        self._set.add(item)
+        self._access(item)
+        self._set[item] = None
+        if len(self._set) > self.max_items:
+            self._set.popitem(last=False)
 
 
 class ExponentialCounter:


Test patch:
diff --git a/tests/unit/models/reddit/test_collections.py b/tests/unit/models/reddit/test_collections.py
index ca5a6cec..bbe1ed0c 100644
--- a/tests/unit/models/reddit/test_collections.py
+++ b/tests/unit/models/reddit/test_collections.py
@@ -3,6 +3,7 @@ import pytest
 
 from praw.models import Collection
 from praw.models.reddit.collections import SubredditCollections
+
 from ... import UnitTest
 
 
@@ -10,8 +11,8 @@ class TestCollection(UnitTest):
     def test_eq(self):
         uuid = "fake_uuid"
         permalink = f"https://reddit.com/r/subreddit/collection/{uuid}"
-        collection1 = Collection(self.reddit, collection_id=uuid)
-        collection2 = Collection(self.reddit, permalink=permalink)
+        collection1 = Collection(None, collection_id=uuid)
+        collection2 = Collection(None, permalink=permalink)
         assert collection1 == collection2
         assert collection2 == collection2
         assert collection1 == collection1
@@ -20,17 +21,17 @@ class TestCollection(UnitTest):
 
     def test_init(self):
         uuid = "fake_uuid"
-        assert uuid == Collection(self.reddit, collection_id=uuid).collection_id
+        assert uuid == Collection(None, collection_id=uuid).collection_id
         permalink = f"https://reddit.com/r/subreddit/collection/{uuid}"
-        assert uuid == Collection(self.reddit, permalink=permalink).collection_id
+        assert uuid == Collection(None, permalink=permalink).collection_id
 
     def test_init_bad(self):
         with pytest.raises(TypeError):
-            Collection(self.reddit)
+            Collection(None)
         with pytest.raises(TypeError):
-            Collection(self.reddit, _data=dict(), collection_id="")
+            Collection(None, _data=dict(), collection_id="")
         with pytest.raises(TypeError):
-            Collection(self.reddit, collection_id="fake_uuid", permalink="")
+            Collection(None, collection_id="fake_uuid", permalink="")
         with pytest.raises(TypeError):
             Collection(
                 None,
@@ -38,22 +39,18 @@ class TestCollection(UnitTest):
                 collection_id="fake_uuid",
                 permalink="https://reddit.com/r/sub/collection/fake_uuid",
             )
-        with pytest.raises(ValueError):
-            Collection(self.reddit, collection_id="")
-        with pytest.raises(ValueError):
-            Collection(self.reddit, permalink="")
 
     def test_repr(self):
-        collection = Collection(self.reddit, collection_id="fake_uuid")
+        collection = Collection(None, collection_id="fake_uuid")
         assert "Collection(collection_id='fake_uuid')" == repr(collection)
 
     def test_str(self):
-        collection = Collection(self.reddit, collection_id="fake_uuid")
+        collection = Collection(None, collection_id="fake_uuid")
         assert "fake_uuid" == str(collection)
 
     def test_neq(self):
-        collection1 = Collection(self.reddit, collection_id="1")
-        collection2 = Collection(self.reddit, collection_id="2")
+        collection1 = Collection(None, collection_id="1")
+        collection2 = Collection(None, collection_id="2")
         assert collection1 != collection2
         assert "1" != collection2
         assert "2" != collection1
@@ -61,9 +58,7 @@ class TestCollection(UnitTest):
 
 class TestSubredditCollections(UnitTest):
     def test_call(self):
-        collections = SubredditCollections(
-            self.reddit, self.reddit.subreddit("placeholder")
-        )
+        collections = SubredditCollections(None, None)
         with pytest.raises(TypeError):
             collections()
         with pytest.raises(TypeError):
diff --git a/tests/unit/models/reddit/test_comment.py b/tests/unit/models/reddit/test_comment.py
index c49fb777..8cace566 100644
--- a/tests/unit/models/reddit/test_comment.py
+++ b/tests/unit/models/reddit/test_comment.py
@@ -48,11 +48,6 @@ class TestComment(UnitTest):
             Comment(self.reddit, "dummy", "dummy", {"id": "dummy"})
         assert str(excinfo.value) == message
 
-        with pytest.raises(ValueError):
-            Comment(self.reddit, "")
-        with pytest.raises(ValueError):
-            Comment(self.reddit, url="")
-
     def test_construct_from_url(self):
         url = "https://reddit.com/comments/2gmzqe/_/cklhv0f/"
         assert Comment(self.reddit, url=url) == "cklhv0f"
diff --git a/tests/unit/models/reddit/test_live.py b/tests/unit/models/reddit/test_live.py
index 7fc577c9..5f7a2fe7 100644
--- a/tests/unit/models/reddit/test_live.py
+++ b/tests/unit/models/reddit/test_live.py
@@ -35,9 +35,6 @@ class TestLiveThread(UnitTest):
             LiveThread(self.reddit, id="dummy", _data={"id": "dummy"})
         assert str(excinfo.value) == message
 
-        with pytest.raises(ValueError):
-            LiveThread(self.reddit, "")
-
     def test_contrib(self):
         thread_id = "ukaeu1ik4sw5"
         thread = LiveThread(self.reddit, thread_id)
diff --git a/tests/unit/models/reddit/test_redditor.py b/tests/unit/models/reddit/test_redditor.py
index 7a91881d..6af4d16b 100644
--- a/tests/unit/models/reddit/test_redditor.py
+++ b/tests/unit/models/reddit/test_redditor.py
@@ -50,11 +50,6 @@ class TestRedditor(UnitTest):
         with pytest.raises(AssertionError):
             Redditor(self.reddit, _data={"notname": "dummy"})
 
-        with pytest.raises(ValueError):
-            Redditor(self.reddit, "")
-        with pytest.raises(ValueError):
-            Redditor(self.reddit, fullname="")
-
     def test_fullname(self):
         redditor = Redditor(self.reddit, _data={"name": "name", "id": "dummy"})
         assert redditor.fullname == "t2_dummy"
diff --git a/tests/unit/models/reddit/test_removal_reasons.py b/tests/unit/models/reddit/test_removal_reasons.py
index 48a7c43c..67433221 100644
--- a/tests/unit/models/reddit/test_removal_reasons.py
+++ b/tests/unit/models/reddit/test_removal_reasons.py
@@ -44,12 +44,6 @@ class TestRemovalReason(UnitTest):
                 id="test",
                 _data={},
             )
-        with pytest.raises(ValueError):
-            RemovalReason(self.reddit, subreddit=self.reddit.subreddit("a"), id="")
-        with pytest.raises(ValueError):
-            RemovalReason(
-                self.reddit, subreddit=self.reddit.subreddit("a"), reason_id=""
-            )
 
     def test__get(self):
         subreddit = self.reddit.subreddit("a")
diff --git a/tests/unit/models/reddit/test_rules.py b/tests/unit/models/reddit/test_rules.py
index d1337e74..58507685 100644
--- a/tests/unit/models/reddit/test_rules.py
+++ b/tests/unit/models/reddit/test_rules.py
@@ -1,6 +1,7 @@
 import pytest
 
 from praw.models import Rule
+
 from ... import UnitTest
 
 
@@ -9,10 +10,6 @@ class TestRules(UnitTest):
     def subreddit(self):
         return self.reddit.subreddit(pytest.placeholders.test_subreddit)
 
-    def test_empty_value(self):
-        with pytest.raises(ValueError):
-            Rule(self.reddit, self.subreddit, short_name="")
-
     def test_no_data(self):
         with pytest.raises(ValueError) as excinfo:
             Rule(self.reddit, self.subreddit)
diff --git a/tests/unit/models/reddit/test_submission.py b/tests/unit/models/reddit/test_submission.py
index a8bb205f..75840ab0 100644
--- a/tests/unit/models/reddit/test_submission.py
+++ b/tests/unit/models/reddit/test_submission.py
@@ -44,11 +44,6 @@ class TestSubmission(UnitTest):
             Submission(self.reddit, "dummy", "dummy", {"id": "dummy"})
         assert str(excinfo.value) == message
 
-        with pytest.raises(ValueError):
-            Submission(self.reddit, "")
-        with pytest.raises(ValueError):
-            Submission(self.reddit, url="")
-
     def test_construct_from_url(self):
         assert Submission(self.reddit, url="http://my.it/2gmzqe") == "2gmzqe"
 
diff --git a/tests/unit/models/reddit/test_subreddit.py b/tests/unit/models/reddit/test_subreddit.py
index e17656c2..4f90ae78 100644
--- a/tests/unit/models/reddit/test_subreddit.py
+++ b/tests/unit/models/reddit/test_subreddit.py
@@ -34,9 +34,6 @@ class TestSubreddit(UnitTest):
             Subreddit(self.reddit, "dummy", {"id": "dummy"})
         assert str(excinfo.value) == message
 
-        with pytest.raises(ValueError):
-            Subreddit(self.reddit, "")
-
     def test_fullname(self):
         subreddit = Subreddit(
             self.reddit, _data={"display_name": "name", "id": "dummy"}
diff --git a/tests/unit/models/test_util.py b/tests/unit/models/test_util.py
index e65e5c4c..7fb33ff2 100644
--- a/tests/unit/models/test_util.py
+++ b/tests/unit/models/test_util.py
@@ -1,6 +1,13 @@
 """Test praw.models.util."""
-from praw.models.util import ExponentialCounter, permissions_string
+from collections import namedtuple
+from unittest import mock
 
+from praw.models.util import (
+    ExponentialCounter,
+    permissions_string,
+    stream_generator,
+    BoundedSet,
+)
 from .. import UnitTest
 
 
@@ -38,7 +45,58 @@ class TestExponentialCounter(UnitTest):
             counter.reset()
 
 
-class TestUtil(UnitTest):
+class TestBoundedSet(UnitTest):
+    def test_contains(self):
+        bset = BoundedSet(max_items=10)
+        bset.add(1)
+        assert 1 in bset
+
+    def test_bound(self):
+        bset = BoundedSet(max_items=10)
+        [bset.add(i) for i in range(11)]
+        assert len(bset._set) == 10
+        assert 0 not in bset
+
+    def test_lru_add(self):
+        bset = BoundedSet(max_items=10)
+        [bset.add(i) for i in range(10)]
+        bset.add(0)
+        bset.add(10)
+        assert 0 in bset
+        assert 1 not in bset
+
+    def test_lru_contains(self):
+        bset = BoundedSet(max_items=10)
+        [bset.add(i) for i in range(10)]
+        assert 0 in bset
+        bset.add(10)
+        assert 0 in bset
+        assert 1 not in bset
+
+
+class TestStream(UnitTest):
+    @mock.patch("time.sleep", return_value=None)
+    def test_stream(self, _):
+        Thing = namedtuple("Thing", ["fullname"])
+        initial_things = [Thing(n) for n in reversed(range(100))]
+        counter = 99
+
+        def generate(limit, **kwargs):
+            nonlocal counter
+            counter += 1
+            if counter % 2 == 0:
+                return initial_things
+            return [Thing(counter)] + initial_things[:-1]
+
+        stream = stream_generator(generate)
+        seen = set()
+        for _ in range(400):
+            thing = next(stream)
+            assert thing not in seen
+            seen.add(thing)
+
+
+class TestPermissionsString(UnitTest):
     PERMISSIONS = {"a", "b", "c"}
 
     def test_permissions_string__all_explicit(self):