Skip to content
Snippets Groups Projects
test_state.py 37.6 KiB
Newer Older
# Copyright 2018-2021 The Matrix.org Foundation C.I.C.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

Matthew Hodgson's avatar
Matthew Hodgson committed
import logging

from frozendict import frozendict

from synapse.api.constants import EventTypes, Membership
from synapse.api.room_versions import RoomVersions
from synapse.storage.state import StateFilter
from synapse.types import RoomID, UserID

from tests.unittest import HomeserverTestCase, TestCase
Matthew Hodgson's avatar
Matthew Hodgson committed
logger = logging.getLogger(__name__)

class StateStoreTestCase(HomeserverTestCase):
    def prepare(self, reactor, clock, hs):
        self.store = hs.get_datastores().main
        self.storage = hs.get_storage_controllers()
        self.state_datastore = self.storage.state.stores.state
        self.event_builder_factory = hs.get_event_builder_factory()
        self.event_creation_handler = hs.get_event_creation_handler()

        self.u_alice = UserID.from_string("@alice:test")
        self.u_bob = UserID.from_string("@bob:test")

        self.room = RoomID.from_string("!abc123:test")

            self.store.store_room(
                self.room.to_string(),
                room_creator_user_id="@creator:text",
                is_public=True,
                room_version=RoomVersions.V1,
            )
        )

    def inject_state_event(self, room, sender, typ, state_key, content):
        builder = self.event_builder_factory.for_room_version(
Erik Johnston's avatar
Erik Johnston committed
            RoomVersions.V1,
black's avatar
black committed
            {
                "type": typ,
                "sender": sender.to_string(),
                "state_key": state_key,
                "room_id": room.to_string(),
                "content": content,
black's avatar
black committed
        )
        event, context = self.get_success(
            self.event_creation_handler.create_new_client_event(builder)
        self.get_success(self.storage.persistence.persist_event(event, context))
        return event
Matthew Hodgson's avatar
Matthew Hodgson committed
    def assertStateMapEqual(self, s1, s2):
        for t in s1:
            # just compare event IDs for simplicity
            self.assertEqual(s1[t].event_id, s2[t].event_id)
        self.assertEqual(len(s1), len(s2))

    def test_get_state_groups_ids(self):
        e1 = self.inject_state_event(self.room, self.u_alice, EventTypes.Create, "", {})
        e2 = self.inject_state_event(
Amber Brown's avatar
Amber Brown committed
            self.room, self.u_alice, EventTypes.Name, "", {"name": "test room"}
        state_group_map = self.get_success(
            self.storage.state.get_state_groups_ids(self.room, [e2.event_id])
        self.assertEqual(len(state_group_map), 1)
        state_map = list(state_group_map.values())[0]
        self.assertDictEqual(
            state_map,
Amber Brown's avatar
Amber Brown committed
            {(EventTypes.Create, ""): e1.event_id, (EventTypes.Name, ""): e2.event_id},
        )

    def test_get_state_groups(self):
        e1 = self.inject_state_event(self.room, self.u_alice, EventTypes.Create, "", {})
        e2 = self.inject_state_event(
Amber Brown's avatar
Amber Brown committed
            self.room, self.u_alice, EventTypes.Name, "", {"name": "test room"}
        state_group_map = self.get_success(
            self.storage.state.get_state_groups(self.room, [e2.event_id])
        self.assertEqual(len(state_group_map), 1)
        state_list = list(state_group_map.values())[0]

        self.assertEqual({ev.event_id for ev in state_list}, {e1.event_id, e2.event_id})
Matthew Hodgson's avatar
Matthew Hodgson committed
    def test_get_state_for_event(self):
        # this defaults to a linear DAG as each new injection defaults to whatever
        # forward extremities are currently in the DB for this room.
        e1 = self.inject_state_event(self.room, self.u_alice, EventTypes.Create, "", {})
        e2 = self.inject_state_event(
Amber Brown's avatar
Amber Brown committed
            self.room, self.u_alice, EventTypes.Name, "", {"name": "test room"}
        e3 = self.inject_state_event(
black's avatar
black committed
            self.room,
            self.u_alice,
            EventTypes.Member,
            self.u_alice.to_string(),
            {"membership": Membership.JOIN},
        e4 = self.inject_state_event(
black's avatar
black committed
            self.room,
            self.u_bob,
            EventTypes.Member,
            self.u_bob.to_string(),
            {"membership": Membership.JOIN},
        e5 = self.inject_state_event(
black's avatar
black committed
            self.room,
            self.u_bob,
            EventTypes.Member,
            self.u_bob.to_string(),
            {"membership": Membership.LEAVE},
        )

        # check we get the full state as of the final event
        state = self.get_success(self.storage.state.get_state_for_event(e5.event_id))
Matthew Hodgson's avatar
Matthew Hodgson committed
        self.assertIsNotNone(e4)

black's avatar
black committed
        self.assertStateMapEqual(
            {
                (e1.type, e1.state_key): e1,
                (e2.type, e2.state_key): e2,
                (e3.type, e3.state_key): e3,
                # e4 is overwritten by e5
                (e5.type, e5.state_key): e5,
            },
            state,
        )

        # check we can filter to the m.room.name event (with a '' state key)
            self.storage.state.get_state_for_event(
                e5.event_id, StateFilter.from_types([(EventTypes.Name, "")])
            )
black's avatar
black committed
        self.assertStateMapEqual({(e2.type, e2.state_key): e2}, state)

        # check we can filter to the m.room.name event (with a wildcard None state key)
            self.storage.state.get_state_for_event(
                e5.event_id, StateFilter.from_types([(EventTypes.Name, None)])
            )
black's avatar
black committed
        self.assertStateMapEqual({(e2.type, e2.state_key): e2}, state)

        # check we can grab the m.room.member events (with a wildcard None state key)
            self.storage.state.get_state_for_event(
                e5.event_id, StateFilter.from_types([(EventTypes.Member, None)])
            )
black's avatar
black committed
        self.assertStateMapEqual(
            {(e3.type, e3.state_key): e3, (e5.type, e5.state_key): e5}, state
        )
        # check we can grab a specific room member without filtering out the
        # other event types
            self.storage.state.get_state_for_event(
                e5.event_id,
                state_filter=StateFilter(
                    types=frozendict(
                        {EventTypes.Member: frozenset({self.u_alice.to_string()})}
                    ),
black's avatar
black committed
        self.assertStateMapEqual(
            {
                (e1.type, e1.state_key): e1,
                (e2.type, e2.state_key): e2,
                (e3.type, e3.state_key): e3,
            },
black's avatar
black committed
            state,
        )
        # check that we can grab everything except members
        state = self.get_success(
            self.storage.state.get_state_for_event(
                e5.event_id,
                state_filter=StateFilter(
                    types=frozendict({EventTypes.Member: frozenset()}),
                    include_others=True,
black's avatar
black committed
        self.assertStateMapEqual(
            {(e1.type, e1.state_key): e1, (e2.type, e2.state_key): e2}, state
        )
Matthew Hodgson's avatar
Matthew Hodgson committed
        #######################################################
        # _get_state_for_group_using_cache tests against a full cache
Matthew Hodgson's avatar
Matthew Hodgson committed
        #######################################################

        room_id = self.room.to_string()
        group_ids = self.get_success(
            self.storage.state.get_state_groups_ids(room_id, [e5.event_id])
        group = list(group_ids.keys())[0]
        # test _get_state_for_group_using_cache correctly filters out members
        # with types=[]
        (state_dict, is_all,) = self.state_datastore._get_state_for_group_using_cache(
Erik Johnston's avatar
Erik Johnston committed
            self.state_datastore._state_group_cache,
            state_filter=StateFilter(
                types=frozendict({EventTypes.Member: frozenset()}), include_others=True
        )

        self.assertEqual(is_all, True)
black's avatar
black committed
        self.assertDictEqual(
            {
                (e1.type, e1.state_key): e1.event_id,
                (e2.type, e2.state_key): e2.event_id,
            },
            state_dict,
        )
        (state_dict, is_all,) = self.state_datastore._get_state_for_group_using_cache(
Erik Johnston's avatar
Erik Johnston committed
            self.state_datastore._state_group_members_cache,
            group,
            state_filter=StateFilter(
                types=frozendict({EventTypes.Member: frozenset()}), include_others=True
        )

        self.assertEqual(is_all, True)
        self.assertDictEqual({}, state_dict)
        # test _get_state_for_group_using_cache correctly filters in members
        # with wildcard types
        (state_dict, is_all,) = self.state_datastore._get_state_for_group_using_cache(
Erik Johnston's avatar
Erik Johnston committed
            self.state_datastore._state_group_cache,
            group,
            state_filter=StateFilter(
                types=frozendict({EventTypes.Member: None}), include_others=True
        )

        self.assertEqual(is_all, True)
black's avatar
black committed
        self.assertDictEqual(
            {
                (e1.type, e1.state_key): e1.event_id,
                (e2.type, e2.state_key): e2.event_id,
        (state_dict, is_all,) = self.state_datastore._get_state_for_group_using_cache(
Erik Johnston's avatar
Erik Johnston committed
            self.state_datastore._state_group_members_cache,
            group,
            state_filter=StateFilter(
                types=frozendict({EventTypes.Member: None}), include_others=True
        )

        self.assertEqual(is_all, True)
        self.assertDictEqual(
            {
black's avatar
black committed
                (e3.type, e3.state_key): e3.event_id,
                # e4 is overwritten by e5
                (e5.type, e5.state_key): e5.event_id,
            },
            state_dict,
        )
        # test _get_state_for_group_using_cache correctly filters in members
        # with specific types
        (state_dict, is_all,) = self.state_datastore._get_state_for_group_using_cache(
Erik Johnston's avatar
Erik Johnston committed
            self.state_datastore._state_group_cache,
black's avatar
black committed
            group,
            state_filter=StateFilter(
                types=frozendict({EventTypes.Member: frozenset({e5.state_key})}),
                include_others=True,
        )

        self.assertEqual(is_all, True)
black's avatar
black committed
        self.assertDictEqual(
            {
                (e1.type, e1.state_key): e1.event_id,
                (e2.type, e2.state_key): e2.event_id,
        (state_dict, is_all,) = self.state_datastore._get_state_for_group_using_cache(
Erik Johnston's avatar
Erik Johnston committed
            self.state_datastore._state_group_members_cache,
            state_filter=StateFilter(
                types=frozendict({EventTypes.Member: frozenset({e5.state_key})}),
                include_others=True,
        )

        self.assertEqual(is_all, True)
        self.assertDictEqual({(e5.type, e5.state_key): e5.event_id}, state_dict)
        # test _get_state_for_group_using_cache correctly filters in members
        # with specific types
        (state_dict, is_all,) = self.state_datastore._get_state_for_group_using_cache(
Erik Johnston's avatar
Erik Johnston committed
            self.state_datastore._state_group_members_cache,
            group,
            state_filter=StateFilter(
                types=frozendict({EventTypes.Member: frozenset({e5.state_key})}),
                include_others=False,
        )

        self.assertEqual(is_all, True)
black's avatar
black committed
        self.assertDictEqual({(e5.type, e5.state_key): e5.event_id}, state_dict)

        #######################################################
        # deliberately remove e2 (room name) from the _state_group_cache

        cache_entry = self.state_datastore._state_group_cache.get(group)
        state_dict_ids = cache_entry.value
        self.assertEqual(cache_entry.full, True)
        self.assertEqual(cache_entry.known_absent, set())
black's avatar
black committed
        self.assertDictEqual(
            state_dict_ids,
            {
                (e1.type, e1.state_key): e1.event_id,
                (e2.type, e2.state_key): e2.event_id,
            },
        )

        state_dict_ids.pop((e2.type, e2.state_key))
Erik Johnston's avatar
Erik Johnston committed
        self.state_datastore._state_group_cache.invalidate(group)
        self.state_datastore._state_group_cache.update(
            sequence=self.state_datastore._state_group_cache.sequence,
            key=group,
            value=state_dict_ids,
            # list fetched keys so it knows it's partial
            fetched_keys=((e1.type, e1.state_key),),
        cache_entry = self.state_datastore._state_group_cache.get(group)
        state_dict_ids = cache_entry.value
        self.assertEqual(cache_entry.full, False)
        self.assertEqual(cache_entry.known_absent, set())
        self.assertDictEqual(state_dict_ids, {})
Matthew Hodgson's avatar
Matthew Hodgson committed
        ############################################
        # test that things work with a partial cache

        # test _get_state_for_group_using_cache correctly filters out members
        # with types=[]
        room_id = self.room.to_string()
        (state_dict, is_all,) = self.state_datastore._get_state_for_group_using_cache(
Erik Johnston's avatar
Erik Johnston committed
            self.state_datastore._state_group_cache,
            state_filter=StateFilter(
                types=frozendict({EventTypes.Member: frozenset()}), include_others=True
        )

        self.assertEqual(is_all, False)
        self.assertDictEqual({}, state_dict)
        room_id = self.room.to_string()
        (state_dict, is_all,) = self.state_datastore._get_state_for_group_using_cache(
Erik Johnston's avatar
Erik Johnston committed
            self.state_datastore._state_group_members_cache,
            group,
            state_filter=StateFilter(
                types=frozendict({EventTypes.Member: frozenset()}), include_others=True
        )

        self.assertEqual(is_all, True)
        self.assertDictEqual({}, state_dict)

        # test _get_state_for_group_using_cache correctly filters in members
        # wildcard types
        (state_dict, is_all,) = self.state_datastore._get_state_for_group_using_cache(
Erik Johnston's avatar
Erik Johnston committed
            self.state_datastore._state_group_cache,
            group,
            state_filter=StateFilter(
                types=frozendict({EventTypes.Member: None}), include_others=True
        )

        self.assertEqual(is_all, False)
        self.assertDictEqual({}, state_dict)
        (state_dict, is_all,) = self.state_datastore._get_state_for_group_using_cache(
Erik Johnston's avatar
Erik Johnston committed
            self.state_datastore._state_group_members_cache,
            group,
            state_filter=StateFilter(
                types=frozendict({EventTypes.Member: None}), include_others=True
        )

        self.assertEqual(is_all, True)
        self.assertDictEqual(
            {
black's avatar
black committed
                (e3.type, e3.state_key): e3.event_id,
                (e5.type, e5.state_key): e5.event_id,
            },
            state_dict,
        )
        # test _get_state_for_group_using_cache correctly filters in members
        # with specific types
        (state_dict, is_all,) = self.state_datastore._get_state_for_group_using_cache(
Erik Johnston's avatar
Erik Johnston committed
            self.state_datastore._state_group_cache,
black's avatar
black committed
            group,
            state_filter=StateFilter(
                types=frozendict({EventTypes.Member: frozenset({e5.state_key})}),
                include_others=True,
        )

        self.assertEqual(is_all, False)
        self.assertDictEqual({}, state_dict)
        (state_dict, is_all,) = self.state_datastore._get_state_for_group_using_cache(
Erik Johnston's avatar
Erik Johnston committed
            self.state_datastore._state_group_members_cache,
            state_filter=StateFilter(
                types=frozendict({EventTypes.Member: frozenset({e5.state_key})}),
                include_others=True,
        )

        self.assertEqual(is_all, True)
        self.assertDictEqual({(e5.type, e5.state_key): e5.event_id}, state_dict)
        # test _get_state_for_group_using_cache correctly filters in members
        # with specific types
        (state_dict, is_all,) = self.state_datastore._get_state_for_group_using_cache(
Erik Johnston's avatar
Erik Johnston committed
            self.state_datastore._state_group_cache,
            group,
            state_filter=StateFilter(
                types=frozendict({EventTypes.Member: frozenset({e5.state_key})}),
                include_others=False,
        )

        self.assertEqual(is_all, False)
        self.assertDictEqual({}, state_dict)

        (state_dict, is_all,) = self.state_datastore._get_state_for_group_using_cache(
Erik Johnston's avatar
Erik Johnston committed
            self.state_datastore._state_group_members_cache,
            group,
            state_filter=StateFilter(
                types=frozendict({EventTypes.Member: frozenset({e5.state_key})}),
                include_others=False,
        )

        self.assertEqual(is_all, True)
        self.assertDictEqual({(e5.type, e5.state_key): e5.event_id}, state_dict)
485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994


class StateFilterDifferenceTestCase(TestCase):
    def assert_difference(
        self, minuend: StateFilter, subtrahend: StateFilter, expected: StateFilter
    ):
        self.assertEqual(
            minuend.approx_difference(subtrahend),
            expected,
            f"StateFilter difference not correct:\n\n\t{minuend!r}\nminus\n\t{subtrahend!r}\nwas\n\t{minuend.approx_difference(subtrahend)}\nexpected\n\t{expected}",
        )

    def test_state_filter_difference_no_include_other_minus_no_include_other(self):
        """
        Tests the StateFilter.approx_difference method
        where, in a.approx_difference(b), both a and b do not have the
        include_others flag set.
        """
        # (wildcard on state keys) - (wildcard on state keys):
        self.assert_difference(
            StateFilter.freeze(
                {EventTypes.Member: None, EventTypes.Create: None},
                include_others=False,
            ),
            StateFilter.freeze(
                {EventTypes.Member: None, EventTypes.CanonicalAlias: None},
                include_others=False,
            ),
            StateFilter.freeze({EventTypes.Create: None}, include_others=False),
        )

        # (wildcard on state keys) - (specific state keys)
        # This one is an over-approximation because we can't represent
        # 'all state keys except a few named examples'
        self.assert_difference(
            StateFilter.freeze({EventTypes.Member: None}, include_others=False),
            StateFilter.freeze(
                {EventTypes.Member: {"@wombat:spqr"}},
                include_others=False,
            ),
            StateFilter.freeze({EventTypes.Member: None}, include_others=False),
        )

        # (wildcard on state keys) - (no state keys)
        self.assert_difference(
            StateFilter.freeze(
                {EventTypes.Member: None},
                include_others=False,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: set(),
                },
                include_others=False,
            ),
            StateFilter.freeze(
                {EventTypes.Member: None},
                include_others=False,
            ),
        )

        # (specific state keys) - (wildcard on state keys):
        self.assert_difference(
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr", "@spqr:spqr"},
                    EventTypes.CanonicalAlias: {""},
                },
                include_others=False,
            ),
            StateFilter.freeze(
                {EventTypes.Member: None},
                include_others=False,
            ),
            StateFilter.freeze(
                {EventTypes.CanonicalAlias: {""}},
                include_others=False,
            ),
        )

        # (specific state keys) - (specific state keys)
        self.assert_difference(
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr", "@spqr:spqr"},
                    EventTypes.CanonicalAlias: {""},
                },
                include_others=False,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr"},
                },
                include_others=False,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@spqr:spqr"},
                    EventTypes.CanonicalAlias: {""},
                },
                include_others=False,
            ),
        )

        # (specific state keys) - (no state keys)
        self.assert_difference(
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr", "@spqr:spqr"},
                    EventTypes.CanonicalAlias: {""},
                },
                include_others=False,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: set(),
                },
                include_others=False,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr", "@spqr:spqr"},
                    EventTypes.CanonicalAlias: {""},
                },
                include_others=False,
            ),
        )

    def test_state_filter_difference_include_other_minus_no_include_other(self):
        """
        Tests the StateFilter.approx_difference method
        where, in a.approx_difference(b), only a has the include_others flag set.
        """
        # (wildcard on state keys) - (wildcard on state keys):
        self.assert_difference(
            StateFilter.freeze(
                {EventTypes.Member: None, EventTypes.Create: None},
                include_others=True,
            ),
            StateFilter.freeze(
                {EventTypes.Member: None, EventTypes.CanonicalAlias: None},
                include_others=False,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Create: None,
                    EventTypes.Member: set(),
                    EventTypes.CanonicalAlias: set(),
                },
                include_others=True,
            ),
        )

        # (wildcard on state keys) - (specific state keys)
        # This one is an over-approximation because we can't represent
        # 'all state keys except a few named examples'
        # This also shows that the resultant state filter is normalised.
        self.assert_difference(
            StateFilter.freeze({EventTypes.Member: None}, include_others=True),
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr"},
                    EventTypes.Create: {""},
                },
                include_others=False,
            ),
            StateFilter(types=frozendict(), include_others=True),
        )

        # (wildcard on state keys) - (no state keys)
        self.assert_difference(
            StateFilter.freeze(
                {EventTypes.Member: None},
                include_others=True,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: set(),
                },
                include_others=False,
            ),
            StateFilter(
                types=frozendict(),
                include_others=True,
            ),
        )

        # (specific state keys) - (wildcard on state keys):
        self.assert_difference(
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr", "@spqr:spqr"},
                    EventTypes.CanonicalAlias: {""},
                },
                include_others=True,
            ),
            StateFilter.freeze(
                {EventTypes.Member: None},
                include_others=False,
            ),
            StateFilter.freeze(
                {
                    EventTypes.CanonicalAlias: {""},
                    EventTypes.Member: set(),
                },
                include_others=True,
            ),
        )

        # (specific state keys) - (specific state keys)
        self.assert_difference(
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr", "@spqr:spqr"},
                    EventTypes.CanonicalAlias: {""},
                },
                include_others=True,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr"},
                },
                include_others=False,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@spqr:spqr"},
                    EventTypes.CanonicalAlias: {""},
                },
                include_others=True,
            ),
        )

        # (specific state keys) - (no state keys)
        self.assert_difference(
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr", "@spqr:spqr"},
                    EventTypes.CanonicalAlias: {""},
                },
                include_others=True,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: set(),
                },
                include_others=False,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr", "@spqr:spqr"},
                    EventTypes.CanonicalAlias: {""},
                },
                include_others=True,
            ),
        )

    def test_state_filter_difference_include_other_minus_include_other(self):
        """
        Tests the StateFilter.approx_difference method
        where, in a.approx_difference(b), both a and b have the include_others
        flag set.
        """
        # (wildcard on state keys) - (wildcard on state keys):
        self.assert_difference(
            StateFilter.freeze(
                {EventTypes.Member: None, EventTypes.Create: None},
                include_others=True,
            ),
            StateFilter.freeze(
                {EventTypes.Member: None, EventTypes.CanonicalAlias: None},
                include_others=True,
            ),
            StateFilter(types=frozendict(), include_others=False),
        )

        # (wildcard on state keys) - (specific state keys)
        # This one is an over-approximation because we can't represent
        # 'all state keys except a few named examples'
        self.assert_difference(
            StateFilter.freeze({EventTypes.Member: None}, include_others=True),
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr"},
                    EventTypes.CanonicalAlias: {""},
                },
                include_others=True,
            ),
            StateFilter.freeze(
                {EventTypes.Member: None, EventTypes.CanonicalAlias: None},
                include_others=False,
            ),
        )

        # (wildcard on state keys) - (no state keys)
        self.assert_difference(
            StateFilter.freeze(
                {EventTypes.Member: None},
                include_others=True,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: set(),
                },
                include_others=True,
            ),
            StateFilter.freeze(
                {EventTypes.Member: None},
                include_others=False,
            ),
        )

        # (specific state keys) - (wildcard on state keys):
        self.assert_difference(
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr", "@spqr:spqr"},
                    EventTypes.CanonicalAlias: {""},
                },
                include_others=True,
            ),
            StateFilter.freeze(
                {EventTypes.Member: None},
                include_others=True,
            ),
            StateFilter(
                types=frozendict(),
                include_others=False,
            ),
        )

        # (specific state keys) - (specific state keys)
        # This one is an over-approximation because we can't represent
        # 'all state keys except a few named examples'
        self.assert_difference(
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr", "@spqr:spqr"},
                    EventTypes.CanonicalAlias: {""},
                    EventTypes.Create: {""},
                },
                include_others=True,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr"},
                    EventTypes.Create: set(),
                },
                include_others=True,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@spqr:spqr"},
                    EventTypes.Create: {""},
                },
                include_others=False,
            ),
        )

        # (specific state keys) - (no state keys)
        self.assert_difference(
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr", "@spqr:spqr"},
                    EventTypes.CanonicalAlias: {""},
                },
                include_others=True,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: set(),
                },
                include_others=True,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr", "@spqr:spqr"},
                },
                include_others=False,
            ),
        )

    def test_state_filter_difference_no_include_other_minus_include_other(self):
        """
        Tests the StateFilter.approx_difference method
        where, in a.approx_difference(b), only b has the include_others flag set.
        """
        # (wildcard on state keys) - (wildcard on state keys):
        self.assert_difference(
            StateFilter.freeze(
                {EventTypes.Member: None, EventTypes.Create: None},
                include_others=False,
            ),
            StateFilter.freeze(
                {EventTypes.Member: None, EventTypes.CanonicalAlias: None},
                include_others=True,
            ),
            StateFilter(types=frozendict(), include_others=False),
        )

        # (wildcard on state keys) - (specific state keys)
        # This one is an over-approximation because we can't represent
        # 'all state keys except a few named examples'
        self.assert_difference(
            StateFilter.freeze({EventTypes.Member: None}, include_others=False),
            StateFilter.freeze(
                {EventTypes.Member: {"@wombat:spqr"}},
                include_others=True,
            ),
            StateFilter.freeze({EventTypes.Member: None}, include_others=False),
        )

        # (wildcard on state keys) - (no state keys)
        self.assert_difference(
            StateFilter.freeze(
                {EventTypes.Member: None},
                include_others=False,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: set(),
                },
                include_others=True,
            ),
            StateFilter.freeze(
                {EventTypes.Member: None},
                include_others=False,
            ),
        )

        # (specific state keys) - (wildcard on state keys):
        self.assert_difference(
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr", "@spqr:spqr"},
                    EventTypes.CanonicalAlias: {""},
                },
                include_others=False,
            ),
            StateFilter.freeze(
                {EventTypes.Member: None},
                include_others=True,
            ),
            StateFilter(
                types=frozendict(),
                include_others=False,
            ),
        )

        # (specific state keys) - (specific state keys)
        # This one is an over-approximation because we can't represent
        # 'all state keys except a few named examples'
        self.assert_difference(
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr", "@spqr:spqr"},
                    EventTypes.CanonicalAlias: {""},
                },
                include_others=False,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr"},
                },
                include_others=True,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@spqr:spqr"},
                },
                include_others=False,
            ),
        )

        # (specific state keys) - (no state keys)
        self.assert_difference(
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr", "@spqr:spqr"},
                    EventTypes.CanonicalAlias: {""},
                },
                include_others=False,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: set(),
                },
                include_others=True,
            ),
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:spqr", "@spqr:spqr"},
                },
                include_others=False,
            ),
        )

    def test_state_filter_difference_simple_cases(self):
        """
        Tests some very simple cases of the StateFilter approx_difference,
        that are not explicitly tested by the more in-depth tests.
        """

        self.assert_difference(StateFilter.all(), StateFilter.all(), StateFilter.none())

        self.assert_difference(
            StateFilter.all(),
            StateFilter.none(),
            StateFilter.all(),
        )


class StateFilterTestCase(TestCase):
    def test_return_expanded(self):
        """
        Tests the behaviour of the return_expanded() function that expands
        StateFilters to include more state types (for the sake of cache hit rate).
        """

        self.assertEqual(StateFilter.all().return_expanded(), StateFilter.all())

        self.assertEqual(StateFilter.none().return_expanded(), StateFilter.none())

        # Concrete-only state filters stay the same
        # (Case: mixed filter)
        self.assertEqual(
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:test", "@alicia:test"},
                    "some.other.state.type": {""},
                },
                include_others=False,
            ).return_expanded(),
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:test", "@alicia:test"},
                    "some.other.state.type": {""},
                },
                include_others=False,
            ),
        )

        # Concrete-only state filters stay the same
        # (Case: non-member-only filter)
        self.assertEqual(
            StateFilter.freeze(
                {"some.other.state.type": {""}}, include_others=False
            ).return_expanded(),
            StateFilter.freeze({"some.other.state.type": {""}}, include_others=False),
        )

        # Concrete-only state filters stay the same
        # (Case: member-only filter)
        self.assertEqual(
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:test", "@alicia:test"},
                },
                include_others=False,
            ).return_expanded(),
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:test", "@alicia:test"},
                },
                include_others=False,
            ),
        )

        # Wildcard member-only state filters stay the same
        self.assertEqual(
            StateFilter.freeze(
                {EventTypes.Member: None},
                include_others=False,
            ).return_expanded(),
            StateFilter.freeze(
                {EventTypes.Member: None},
                include_others=False,
            ),
        )

        # If there is a wildcard in the non-member portion of the filter,
        # it's expanded to include ALL non-member events.
        # (Case: mixed filter)
        self.assertEqual(
            StateFilter.freeze(
                {
                    EventTypes.Member: {"@wombat:test", "@alicia:test"},
                    "some.other.state.type": None,
                },
                include_others=False,
            ).return_expanded(),
            StateFilter.freeze(
                {EventTypes.Member: {"@wombat:test", "@alicia:test"}},
                include_others=True,
            ),
        )

        # If there is a wildcard in the non-member portion of the filter,
        # it's expanded to include ALL non-member events.
        # (Case: non-member-only filter)
        self.assertEqual(
            StateFilter.freeze(
                {
                    "some.other.state.type": None,
                },
                include_others=False,
            ).return_expanded(),
            StateFilter.freeze({EventTypes.Member: set()}, include_others=True),
        )
        self.assertEqual(
            StateFilter.freeze(
                {
                    "some.other.state.type": None,
                    "yet.another.state.type": {"wombat"},
                },
                include_others=False,
            ).return_expanded(),
            StateFilter.freeze({EventTypes.Member: set()}, include_others=True),
        )