Merge branch 'develop' of github.com:matrix-org/synapse into registration-api-changes

21 files changed, 457 insertions, 95 deletions

diff --git a/tests/api/test_ratelimiting.py b/tests/api/test_ratelimiting.py
index dc2f83c7eb..dd0bc19ecf 100644
--- a/tests/api/test_ratelimiting.py
+++ b/tests/api/test_ratelimiting.py
@@ -1,6 +1,6 @@
 from synapse.api.ratelimiting import Ratelimiter
 
-import unittest
+from tests import unittest
 
 class TestRatelimiter(unittest.TestCase):
 
diff --git a/tests/events/test_events.py b/tests/events/test_events.py
index 93d5c15c6f..a4b6cb3afd 100644
--- a/tests/events/test_events.py
+++ b/tests/events/test_events.py
@@ -15,7 +15,7 @@
 
 from synapse.api.events import SynapseEvent
 
-import unittest
+from tests import unittest
 
 
 class SynapseTemplateCheckTestCase(unittest.TestCase):
diff --git a/tests/federation/test_federation.py b/tests/federation/test_federation.py
index 0b105fe723..954ccac2a4 100644
--- a/tests/federation/test_federation.py
+++ b/tests/federation/test_federation.py
@@ -14,11 +14,10 @@
 
 # trial imports
 from twisted.internet import defer
-from twisted.trial import unittest
+from tests import unittest
 
 # python imports
 from mock import Mock
-import logging
 
 from ..utils import MockHttpResource, MockClock
 
@@ -28,9 +27,6 @@ from synapse.federation.units import Pdu
 from synapse.storage.pdu import PduTuple, PduEntry
 
 
-logging.getLogger().addHandler(logging.NullHandler())
-
-
 def make_pdu(prev_pdus=[], **kwargs):
     """Provide some default fields for making a PduTuple."""
     pdu_fields = {
diff --git a/tests/federation/test_pdu_codec.py b/tests/federation/test_pdu_codec.py
index 9f74ba119f..344e1baf60 100644
--- a/tests/federation/test_pdu_codec.py
+++ b/tests/federation/test_pdu_codec.py
@@ -13,7 +13,7 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
-from twisted.trial import unittest
+from tests import unittest
 
 from synapse.federation.pdu_codec import (
     PduCodec, encode_event_id, decode_event_id
diff --git a/tests/handlers/test_directory.py b/tests/handlers/test_directory.py
index 72a2b1443a..54d6e51f97 100644
--- a/tests/handlers/test_directory.py
+++ b/tests/handlers/test_directory.py
@@ -14,11 +14,10 @@
 # limitations under the License.
 
 
-from twisted.trial import unittest
+from tests import unittest
 from twisted.internet import defer
 
 from mock import Mock
-import logging
 
 from synapse.server import HomeServer
 from synapse.http.client import HttpClient
@@ -26,9 +25,6 @@ from synapse.handlers.directory import DirectoryHandler
 from synapse.storage.directory import RoomAliasMapping
 
 
-logging.getLogger().addHandler(logging.NullHandler())
-
-
 class DirectoryHandlers(object):
     def __init__(self, hs):
         self.directory_handler = DirectoryHandler(hs)
diff --git a/tests/handlers/test_federation.py b/tests/handlers/test_federation.py
index 6fc3d8f7fd..f0308a29d3 100644
--- a/tests/handlers/test_federation.py
+++ b/tests/handlers/test_federation.py
@@ -14,7 +14,7 @@
 
 
 from twisted.internet import defer
-from twisted.trial import unittest
+from tests import unittest
 
 from synapse.api.events.room import (
     InviteJoinEvent, MessageEvent, RoomMemberEvent
@@ -26,12 +26,8 @@ from synapse.federation.units import Pdu
 
 from mock import NonCallableMock, ANY
 
-import logging
-
 from ..utils import get_mock_call_args
 
-logging.getLogger().addHandler(logging.NullHandler())
-
 
 class FederationTestCase(unittest.TestCase):
 
diff --git a/tests/handlers/test_presence.py b/tests/handlers/test_presence.py
index 9eb8b6909f..06f5f9c2ba 100644
--- a/tests/handlers/test_presence.py
+++ b/tests/handlers/test_presence.py
@@ -14,11 +14,10 @@
 # limitations under the License.
 
 
-from twisted.trial import unittest
+from tests import unittest
 from twisted.internet import defer, reactor
 
 from mock import Mock, call, ANY
-import logging
 import json
 
 from ..utils import MockHttpResource, MockClock, DeferredMockCallable
@@ -34,9 +33,6 @@ UNAVAILABLE = PresenceState.UNAVAILABLE
 ONLINE = PresenceState.ONLINE
 
 
-logging.getLogger().addHandler(logging.NullHandler())
-
-
 def _expect_edu(destination, edu_type, content, origin="test"):
     return {
         "origin": origin,
@@ -92,7 +88,6 @@ class PresenceStateTestCase(unittest.TestCase):
         # Mock the RoomMemberHandler
         room_member_handler = Mock(spec=[])
         hs.handlers.room_member_handler = room_member_handler
-        logging.getLogger().debug("Mocking room_member_handler=%r", room_member_handler)
 
         # Some local users to test with
         self.u_apple = hs.parse_userid("@apple:test")
diff --git a/tests/handlers/test_presencelike.py b/tests/handlers/test_presencelike.py
index b35980d948..72c55b3667 100644
--- a/tests/handlers/test_presencelike.py
+++ b/tests/handlers/test_presencelike.py
@@ -16,11 +16,10 @@
 """This file contains tests of the "presence-like" data that is shared between
 presence and profiles; namely, the displayname and avatar_url."""
 
-from twisted.trial import unittest
+from tests import unittest
 from twisted.internet import defer
 
 from mock import Mock, call, ANY
-import logging
 
 from ..utils import MockClock
 
@@ -35,9 +34,6 @@ UNAVAILABLE = PresenceState.UNAVAILABLE
 ONLINE = PresenceState.ONLINE
 
 
-logging.getLogger().addHandler(logging.NullHandler())
-
-
 class MockReplication(object):
     def __init__(self):
         self.edu_handlers = {}
diff --git a/tests/handlers/test_profile.py b/tests/handlers/test_profile.py
index 8e7a89b479..0a5cebb4cc 100644
--- a/tests/handlers/test_profile.py
+++ b/tests/handlers/test_profile.py
@@ -14,20 +14,16 @@
 # limitations under the License.
 
 
-from twisted.trial import unittest
+from tests import unittest
 from twisted.internet import defer
 
 from mock import Mock
-import logging
 
 from synapse.api.errors import AuthError
 from synapse.server import HomeServer
 from synapse.handlers.profile import ProfileHandler
 
 
-logging.getLogger().addHandler(logging.NullHandler())
-
-
 class ProfileHandlers(object):
     def __init__(self, hs):
         self.profile_handler = ProfileHandler(hs)
diff --git a/tests/handlers/test_room.py b/tests/handlers/test_room.py
index 5687bbea0b..a1a2e80492 100644
--- a/tests/handlers/test_room.py
+++ b/tests/handlers/test_room.py
@@ -15,7 +15,7 @@
 
 
 from twisted.internet import defer
-from twisted.trial import unittest
+from tests import unittest
 
 from synapse.api.events.room import (
     InviteJoinEvent, RoomMemberEvent, RoomConfigEvent
@@ -27,10 +27,6 @@ from synapse.server import HomeServer
 
 from mock import Mock, NonCallableMock
 
-import logging
-
-logging.getLogger().addHandler(logging.NullHandler())
-
 
 class RoomMemberHandlerTestCase(unittest.TestCase):
 
diff --git a/tests/handlers/test_typing.py b/tests/handlers/test_typing.py
index 6532ac94a3..ab908cdfc1 100644
--- a/tests/handlers/test_typing.py
+++ b/tests/handlers/test_typing.py
@@ -14,12 +14,11 @@
 # limitations under the License.
 
 
-from twisted.trial import unittest
+from tests import unittest
 from twisted.internet import defer
 
 from mock import Mock, call, ANY
 import json
-import logging
 
 from ..utils import MockHttpResource, MockClock, DeferredMockCallable
 
@@ -27,9 +26,6 @@ from synapse.server import HomeServer
 from synapse.handlers.typing import TypingNotificationHandler
 
 
-logging.getLogger().addHandler(logging.NullHandler())
-
-
 def _expect_edu(destination, edu_type, content, origin="test"):
     return {
         "origin": origin,
diff --git a/tests/rest/test_events.py b/tests/rest/test_events.py
index fd2224f55f..79b371c04d 100644
--- a/tests/rest/test_events.py
+++ b/tests/rest/test_events.py
@@ -14,7 +14,7 @@
 # limitations under the License.
 
 """ Tests REST events for /events paths."""
-from twisted.trial import unittest
+from tests import unittest
 
 # twisted imports
 from twisted.internet import defer
@@ -27,14 +27,12 @@ from synapse.server import HomeServer
 
 # python imports
 import json
-import logging
 
 from ..utils import MockHttpResource, MemoryDataStore
 from .utils import RestTestCase
 
 from mock import Mock, NonCallableMock
 
-logging.getLogger().addHandler(logging.NullHandler())
 
 PATH_PREFIX = "/_matrix/client/api/v1"
 
diff --git a/tests/rest/test_presence.py b/tests/rest/test_presence.py
index a1db0fbcf3..ea3478ac5d 100644
--- a/tests/rest/test_presence.py
+++ b/tests/rest/test_presence.py
@@ -15,11 +15,10 @@
 
 """Tests REST events for /presence paths."""
 
-from twisted.trial import unittest
+from tests import unittest
 from twisted.internet import defer
 
 from mock import Mock
-import logging
 
 from ..utils import MockHttpResource
 
@@ -28,9 +27,6 @@ from synapse.handlers.presence import PresenceHandler
 from synapse.server import HomeServer
 
 
-logging.getLogger().addHandler(logging.NullHandler())
-
-
 OFFLINE = PresenceState.OFFLINE
 UNAVAILABLE = PresenceState.UNAVAILABLE
 ONLINE = PresenceState.ONLINE
diff --git a/tests/rest/test_profile.py b/tests/rest/test_profile.py
index f41810df1f..e6e51f6dd0 100644
--- a/tests/rest/test_profile.py
+++ b/tests/rest/test_profile.py
@@ -15,7 +15,7 @@
 
 """Tests REST events for /profile paths."""
 
-from twisted.trial import unittest
+from tests import unittest
 from twisted.internet import defer
 
 from mock import Mock
@@ -28,6 +28,7 @@ from synapse.server import HomeServer
 myid = "@1234ABCD:test"
 PATH_PREFIX = "/_matrix/client/api/v1"
 
+
 class ProfileTestCase(unittest.TestCase):
     """ Tests profile management. """
 
diff --git a/tests/rest/utils.py b/tests/rest/utils.py
index 77f5ecf0df..ce2e8fd98a 100644
--- a/tests/rest/utils.py
+++ b/tests/rest/utils.py
@@ -17,7 +17,7 @@
 from twisted.internet import defer
 
 # trial imports
-from twisted.trial import unittest
+from tests import unittest
 
 from synapse.api.constants import Membership
 
diff --git a/tests/storage/test_base.py b/tests/storage/test_base.py
index 330311448d..3ad9a4b0c0 100644
--- a/tests/storage/test_base.py
+++ b/tests/storage/test_base.py
@@ -14,7 +14,7 @@
 # limitations under the License.
 
 
-from twisted.trial import unittest
+from tests import unittest
 from twisted.internet import defer
 
 from mock import Mock, call
diff --git a/tests/test_distributor.py b/tests/test_distributor.py
index 04933f0ecf..39c5b8dff2 100644
--- a/tests/test_distributor.py
+++ b/tests/test_distributor.py
@@ -13,8 +13,8 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
+from tests import unittest
 from twisted.internet import defer
-from twisted.trial import unittest
 
 from mock import Mock, patch
 
diff --git a/tests/test_state.py b/tests/test_state.py
index b01496c40f..b1624f0b25 100644
--- a/tests/test_state.py
+++ b/tests/test_state.py
@@ -13,23 +13,32 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
+from tests import unittest
 from twisted.internet import defer
-from twisted.trial import unittest
+from twisted.python.log import PythonLoggingObserver
 
 from synapse.state import StateHandler
 from synapse.storage.pdu import PduEntry
 from synapse.federation.pdu_codec import encode_event_id
+from synapse.federation.units import Pdu
 
 from collections import namedtuple
 
 from mock import Mock
 
+import mock
+
 
 ReturnType = namedtuple(
     "StateReturnType", ["new_branch", "current_branch"]
 )
 
 
+def _gen_get_power_level(power_level_list):
+    def get_power_level(room_id, user_id):
+        return defer.succeed(power_level_list.get(user_id, None))
+    return get_power_level
+
 class StateTestCase(unittest.TestCase):
     def setUp(self):
         self.persistence = Mock(spec=[
@@ -38,6 +47,7 @@ class StateTestCase(unittest.TestCase):
             "get_latest_pdus_in_context",
             "get_current_state_pdu",
             "get_pdu",
+            "get_power_level",
         ])
         self.replication = Mock(spec=["get_pdu"])
 
@@ -51,10 +61,12 @@ class StateTestCase(unittest.TestCase):
     @defer.inlineCallbacks
     def test_new_state_key(self):
         # We've never seen anything for this state before
-        new_pdu = new_fake_pdu_entry("A", "test", "mem", "x", None, 10)
+        new_pdu = new_fake_pdu("A", "test", "mem", "x", None, "u")
+
+        self.persistence.get_power_level.side_effect = _gen_get_power_level({})
 
         self.persistence.get_unresolved_state_tree.return_value = (
-            ReturnType([new_pdu], [])
+            (ReturnType([new_pdu], []), None)
         )
 
         is_new = yield self.state.handle_new_state(new_pdu)
@@ -74,11 +86,44 @@ class StateTestCase(unittest.TestCase):
         # We do a direct overwriting of the old state, i.e., the new state
         # points to the old state.
 
-        old_pdu = new_fake_pdu_entry("A", "test", "mem", "x", None, 10)
-        new_pdu = new_fake_pdu_entry("B", "test", "mem", "x", "A", 5)
+        old_pdu = new_fake_pdu("A", "test", "mem", "x", None, "u1")
+        new_pdu = new_fake_pdu("B", "test", "mem", "x", "A", "u2")
+
+        self.persistence.get_power_level.side_effect = _gen_get_power_level({
+            "u1": 10,
+            "u2": 5,
+        })
 
         self.persistence.get_unresolved_state_tree.return_value = (
-            ReturnType([new_pdu, old_pdu], [old_pdu])
+            (ReturnType([new_pdu, old_pdu], [old_pdu]), None)
+        )
+
+        is_new = yield self.state.handle_new_state(new_pdu)
+
+        self.assertTrue(is_new)
+
+        self.persistence.get_unresolved_state_tree.assert_called_once_with(
+            new_pdu
+        )
+
+        self.assertEqual(1, self.persistence.update_current_state.call_count)
+
+        self.assertFalse(self.replication.get_pdu.called)
+
+    @defer.inlineCallbacks
+    def test_overwrite(self):
+        old_pdu_1 = new_fake_pdu("A", "test", "mem", "x", None, "u1")
+        old_pdu_2 = new_fake_pdu("B", "test", "mem", "x", "A", "u2")
+        new_pdu = new_fake_pdu("C", "test", "mem", "x", "B", "u3")
+
+        self.persistence.get_power_level.side_effect = _gen_get_power_level({
+            "u1": 10,
+            "u2": 5,
+            "u3": 0,
+        })
+
+        self.persistence.get_unresolved_state_tree.return_value = (
+            (ReturnType([new_pdu, old_pdu_2, old_pdu_1], [old_pdu_1]), None)
         )
 
         is_new = yield self.state.handle_new_state(new_pdu)
@@ -98,12 +143,18 @@ class StateTestCase(unittest.TestCase):
         # We try to update the state based on an outdated state, and have a
         # too low power level.
 
-        old_pdu_1 = new_fake_pdu_entry("A", "test", "mem", "x", None, 10)
-        old_pdu_2 = new_fake_pdu_entry("B", "test", "mem", "x", None, 10)
-        new_pdu = new_fake_pdu_entry("C", "test", "mem", "x", "A", 5)
+        old_pdu_1 = new_fake_pdu("A", "test", "mem", "x", None, "u1")
+        old_pdu_2 = new_fake_pdu("B", "test", "mem", "x", None, "u2")
+        new_pdu = new_fake_pdu("C", "test", "mem", "x", "A", "u3")
+
+        self.persistence.get_power_level.side_effect = _gen_get_power_level({
+            "u1": 10,
+            "u2": 10,
+            "u3": 5,
+        })
 
         self.persistence.get_unresolved_state_tree.return_value = (
-            ReturnType([new_pdu, old_pdu_1], [old_pdu_2, old_pdu_1])
+            (ReturnType([new_pdu, old_pdu_1], [old_pdu_2, old_pdu_1]), None)
         )
 
         is_new = yield self.state.handle_new_state(new_pdu)
@@ -123,12 +174,18 @@ class StateTestCase(unittest.TestCase):
         # We try to update the state based on an outdated state, but have
         # sufficient power level to force the update.
 
-        old_pdu_1 = new_fake_pdu_entry("A", "test", "mem", "x", None, 10)
-        old_pdu_2 = new_fake_pdu_entry("B", "test", "mem", "x", None, 10)
-        new_pdu = new_fake_pdu_entry("C", "test", "mem", "x", "A", 15)
+        old_pdu_1 = new_fake_pdu("A", "test", "mem", "x", None, "u1")
+        old_pdu_2 = new_fake_pdu("B", "test", "mem", "x", None, "u2")
+        new_pdu = new_fake_pdu("C", "test", "mem", "x", "A", "u3")
+
+        self.persistence.get_power_level.side_effect = _gen_get_power_level({
+            "u1": 10,
+            "u2": 10,
+            "u3": 15,
+        })
 
         self.persistence.get_unresolved_state_tree.return_value = (
-            ReturnType([new_pdu, old_pdu_1], [old_pdu_2, old_pdu_1])
+            (ReturnType([new_pdu, old_pdu_1], [old_pdu_2, old_pdu_1]), None)
         )
 
         is_new = yield self.state.handle_new_state(new_pdu)
@@ -148,12 +205,18 @@ class StateTestCase(unittest.TestCase):
         # We try to update the state based on an outdated state, the power
         # levels are the same and so are the branch lengths
 
-        old_pdu_1 = new_fake_pdu_entry("A", "test", "mem", "x", None, 10)
-        old_pdu_2 = new_fake_pdu_entry("B", "test", "mem", "x", None, 10)
-        new_pdu = new_fake_pdu_entry("C", "test", "mem", "x", "A", 10)
+        old_pdu_1 = new_fake_pdu("A", "test", "mem", "x", None, "u1")
+        old_pdu_2 = new_fake_pdu("B", "test", "mem", "x", None, "u2")
+        new_pdu = new_fake_pdu("C", "test", "mem", "x", "A", "u3")
+
+        self.persistence.get_power_level.side_effect = _gen_get_power_level({
+            "u1": 10,
+            "u2": 10,
+            "u3": 10,
+        })
 
         self.persistence.get_unresolved_state_tree.return_value = (
-            ReturnType([new_pdu, old_pdu_1], [old_pdu_2, old_pdu_1])
+            (ReturnType([new_pdu, old_pdu_1], [old_pdu_2, old_pdu_1]), None)
         )
 
         is_new = yield self.state.handle_new_state(new_pdu)
@@ -173,13 +236,26 @@ class StateTestCase(unittest.TestCase):
         # We try to update the state based on an outdated state, the power
         # levels are the same but the branch length of the new one is longer.
 
-        old_pdu_1 = new_fake_pdu_entry("A", "test", "mem", "x", None, 10)
-        old_pdu_2 = new_fake_pdu_entry("B", "test", "mem", "x", None, 10)
-        old_pdu_3 = new_fake_pdu_entry("C", "test", "mem", "x", "A", 10)
-        new_pdu = new_fake_pdu_entry("D", "test", "mem", "x", "C", 10)
+        old_pdu_1 = new_fake_pdu("A", "test", "mem", "x", None, "u1")
+        old_pdu_2 = new_fake_pdu("B", "test", "mem", "x", None, "u2")
+        old_pdu_3 = new_fake_pdu("C", "test", "mem", "x", "A", "u3")
+        new_pdu = new_fake_pdu("D", "test", "mem", "x", "C", "u4")
+
+        self.persistence.get_power_level.side_effect = _gen_get_power_level({
+            "u1": 10,
+            "u2": 10,
+            "u3": 10,
+            "u4": 10,
+        })
 
         self.persistence.get_unresolved_state_tree.return_value = (
-            ReturnType([new_pdu, old_pdu_3, old_pdu_1], [old_pdu_2, old_pdu_1])
+            (
+                ReturnType(
+                    [new_pdu, old_pdu_3, old_pdu_1],
+                    [old_pdu_2, old_pdu_1]
+                ),
+                None
+            )
         )
 
         is_new = yield self.state.handle_new_state(new_pdu)
@@ -200,22 +276,38 @@ class StateTestCase(unittest.TestCase):
         # triggering a get_pdu request
 
         # The pdu we haven't seen
-        old_pdu_1 = new_fake_pdu_entry("A", "test", "mem", "x", None, 10)
+        old_pdu_1 = new_fake_pdu(
+            "A", "test", "mem", "x", None, "u1", depth=0
+        )
+
+        old_pdu_2 = new_fake_pdu(
+            "B", "test", "mem", "x", "A", "u2", depth=1
+        )
+        new_pdu = new_fake_pdu(
+            "C", "test", "mem", "x", "A", "u3", depth=2
+        )
 
-        old_pdu_2 = new_fake_pdu_entry("B", "test", "mem", "x", None, 10)
-        new_pdu = new_fake_pdu_entry("C", "test", "mem", "x", "A", 20)
+        self.persistence.get_power_level.side_effect = _gen_get_power_level({
+            "u1": 10,
+            "u2": 10,
+            "u3": 20,
+        })
 
         # The return_value of `get_unresolved_state_tree`, which changes after
         # the call to get_pdu
-        tree_to_return = [ReturnType([new_pdu], [old_pdu_2])]
+        tree_to_return = [(ReturnType([new_pdu], [old_pdu_2]), 0)]
 
         def return_tree(p):
             return tree_to_return[0]
 
-        def set_return_tree(*args, **kwargs):
-            tree_to_return[0] = ReturnType(
-                [new_pdu, old_pdu_1], [old_pdu_2, old_pdu_1]
+        def set_return_tree(destination, pdu_origin, pdu_id, outlier=False):
+            tree_to_return[0] = (
+                ReturnType(
+                    [new_pdu, old_pdu_1], [old_pdu_2, old_pdu_1]
+                ),
+                None
             )
+            return defer.succeed(None)
 
         self.persistence.get_unresolved_state_tree.side_effect = return_tree
 
@@ -227,6 +319,13 @@ class StateTestCase(unittest.TestCase):
 
         self.assertTrue(is_new)
 
+        self.replication.get_pdu.assert_called_with(
+            destination=new_pdu.origin,
+            pdu_origin=old_pdu_1.origin,
+            pdu_id=old_pdu_1.pdu_id,
+            outlier=True
+        )
+
         self.persistence.get_unresolved_state_tree.assert_called_with(
             new_pdu
         )
@@ -238,11 +337,232 @@ class StateTestCase(unittest.TestCase):
         self.assertEqual(1, self.persistence.update_current_state.call_count)
 
     @defer.inlineCallbacks
+    def test_missing_pdu_depth_1(self):
+        # We try to update state against a PDU we haven't yet seen,
+        # triggering a get_pdu request
+
+        # The pdu we haven't seen
+        old_pdu_1 = new_fake_pdu(
+            "A", "test", "mem", "x", None, "u1", depth=0
+        )
+
+        old_pdu_2 = new_fake_pdu(
+            "B", "test", "mem", "x", "A", "u2", depth=2
+        )
+        old_pdu_3 = new_fake_pdu(
+            "C", "test", "mem", "x", "B", "u3", depth=3
+        )
+        new_pdu = new_fake_pdu(
+            "D", "test", "mem", "x", "A", "u4", depth=4
+        )
+
+        self.persistence.get_power_level.side_effect = _gen_get_power_level({
+            "u1": 10,
+            "u2": 10,
+            "u3": 10,
+            "u4": 20,
+        })
+
+        # The return_value of `get_unresolved_state_tree`, which changes after
+        # the call to get_pdu
+        tree_to_return = [
+            (
+                ReturnType([new_pdu], [old_pdu_3]),
+                0
+            ),
+            (
+                ReturnType(
+                    [new_pdu, old_pdu_1], [old_pdu_3]
+                ),
+                1
+            ),
+            (
+                ReturnType(
+                    [new_pdu, old_pdu_1], [old_pdu_3, old_pdu_2, old_pdu_1]
+                ),
+                None
+            ),
+        ]
+
+        to_return = [0]
+
+        def return_tree(p):
+            return tree_to_return[to_return[0]]
+
+        def set_return_tree(destination, pdu_origin, pdu_id, outlier=False):
+            to_return[0] += 1
+            return defer.succeed(None)
+
+        self.persistence.get_unresolved_state_tree.side_effect = return_tree
+
+        self.replication.get_pdu.side_effect = set_return_tree
+
+        self.persistence.get_pdu.return_value = None
+
+        is_new = yield self.state.handle_new_state(new_pdu)
+
+        self.assertTrue(is_new)
+
+        self.assertEqual(2, self.replication.get_pdu.call_count)
+
+        self.replication.get_pdu.assert_has_calls(
+            [
+                mock.call(
+                    destination=new_pdu.origin,
+                    pdu_origin=old_pdu_1.origin,
+                    pdu_id=old_pdu_1.pdu_id,
+                    outlier=True
+                ),
+                mock.call(
+                    destination=old_pdu_3.origin,
+                    pdu_origin=old_pdu_2.origin,
+                    pdu_id=old_pdu_2.pdu_id,
+                    outlier=True
+                ),
+            ]
+        )
+
+        self.persistence.get_unresolved_state_tree.assert_called_with(
+            new_pdu
+        )
+
+        self.assertEquals(
+            3, self.persistence.get_unresolved_state_tree.call_count
+        )
+
+        self.assertEqual(1, self.persistence.update_current_state.call_count)
+
+    @defer.inlineCallbacks
+    def test_missing_pdu_depth_2(self):
+        # We try to update state against a PDU we haven't yet seen,
+        # triggering a get_pdu request
+
+        # The pdu we haven't seen
+        old_pdu_1 = new_fake_pdu(
+            "A", "test", "mem", "x", None, "u1", depth=0
+        )
+
+        old_pdu_2 = new_fake_pdu(
+            "B", "test", "mem", "x", "A", "u2", depth=2
+        )
+        old_pdu_3 = new_fake_pdu(
+            "C", "test", "mem", "x", "B", "u3", depth=3
+        )
+        new_pdu = new_fake_pdu(
+            "D", "test", "mem", "x", "A", "u4", depth=1
+        )
+
+        self.persistence.get_power_level.side_effect = _gen_get_power_level({
+            "u1": 10,
+            "u2": 10,
+            "u3": 10,
+            "u4": 20,
+        })
+
+        # The return_value of `get_unresolved_state_tree`, which changes after
+        # the call to get_pdu
+        tree_to_return = [
+            (
+                ReturnType([new_pdu], [old_pdu_3]),
+                1,
+            ),
+            (
+                ReturnType(
+                    [new_pdu], [old_pdu_3, old_pdu_2]
+                ),
+                0,
+            ),
+            (
+                ReturnType(
+                    [new_pdu, old_pdu_1], [old_pdu_3, old_pdu_2, old_pdu_1]
+                ),
+                None
+            ),
+        ]
+
+        to_return = [0]
+
+        def return_tree(p):
+            return tree_to_return[to_return[0]]
+
+        def set_return_tree(destination, pdu_origin, pdu_id, outlier=False):
+            to_return[0] += 1
+            return defer.succeed(None)
+
+        self.persistence.get_unresolved_state_tree.side_effect = return_tree
+
+        self.replication.get_pdu.side_effect = set_return_tree
+
+        self.persistence.get_pdu.return_value = None
+
+        is_new = yield self.state.handle_new_state(new_pdu)
+
+        self.assertTrue(is_new)
+
+        self.assertEqual(2, self.replication.get_pdu.call_count)
+
+        self.replication.get_pdu.assert_has_calls(
+            [
+                mock.call(
+                    destination=old_pdu_3.origin,
+                    pdu_origin=old_pdu_2.origin,
+                    pdu_id=old_pdu_2.pdu_id,
+                    outlier=True
+                ),
+                mock.call(
+                    destination=new_pdu.origin,
+                    pdu_origin=old_pdu_1.origin,
+                    pdu_id=old_pdu_1.pdu_id,
+                    outlier=True
+                ),
+            ]
+        )
+
+        self.persistence.get_unresolved_state_tree.assert_called_with(
+            new_pdu
+        )
+
+        self.assertEquals(
+            3, self.persistence.get_unresolved_state_tree.call_count
+        )
+
+        self.assertEqual(1, self.persistence.update_current_state.call_count)
+
+    @defer.inlineCallbacks
+    def test_no_common_ancestor(self):
+        # We do a direct overwriting of the old state, i.e., the new state
+        # points to the old state.
+
+        old_pdu = new_fake_pdu("A", "test", "mem", "x", None, "u1")
+        new_pdu = new_fake_pdu("B", "test", "mem", "x", None, "u2")
+
+        self.persistence.get_power_level.side_effect = _gen_get_power_level({
+            "u1": 5,
+            "u2": 10,
+        })
+
+        self.persistence.get_unresolved_state_tree.return_value = (
+            (ReturnType([new_pdu], [old_pdu]), None)
+        )
+
+        is_new = yield self.state.handle_new_state(new_pdu)
+
+        self.assertTrue(is_new)
+
+        self.persistence.get_unresolved_state_tree.assert_called_once_with(
+            new_pdu
+        )
+
+        self.assertEqual(1, self.persistence.update_current_state.call_count)
+
+        self.assertFalse(self.replication.get_pdu.called)
+
+    @defer.inlineCallbacks
     def test_new_event(self):
         event = Mock()
         event.event_id = "12123123@test"
 
-        state_pdu = new_fake_pdu_entry("C", "test", "mem", "x", "A", 20)
+        state_pdu = new_fake_pdu("C", "test", "mem", "x", "A", 20)
 
         snapshot = Mock()
         snapshot.prev_state_pdu = state_pdu
@@ -269,24 +589,25 @@ class StateTestCase(unittest.TestCase):
         )
 
 
-def new_fake_pdu_entry(pdu_id, context, pdu_type, state_key, prev_state_id,
-                 power_level):
-    new_pdu = PduEntry(
+def new_fake_pdu(pdu_id, context, pdu_type, state_key, prev_state_id,
+                 user_id, depth=0):
+    new_pdu = Pdu(
         pdu_id=pdu_id,
         pdu_type=pdu_type,
         state_key=state_key,
-        power_level=power_level,
+        user_id=user_id,
         prev_state_id=prev_state_id,
         origin="example.com",
         context="context",
         ts=1405353060021,
-        depth=0,
+        depth=depth,
         content_json="{}",
         unrecognized_keys="{}",
         outlier=True,
         is_state=True,
         prev_state_origin="example.com",
         have_processed=True,
+        content={},
     )
 
     return new_pdu
diff --git a/tests/test_types.py b/tests/test_types.py
index 571938356c..276ecc91fd 100644
--- a/tests/test_types.py
+++ b/tests/test_types.py
@@ -13,7 +13,7 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
-import unittest
+from tests import unittest
 
 from synapse.server import BaseHomeServer
 from synapse.types import UserID, RoomAlias
diff --git a/tests/unittest.py b/tests/unittest.py
new file mode 100644
index 0000000000..fb97fb1148
--- /dev/null
+++ b/tests/unittest.py
@@ -0,0 +1,79 @@
+# -*- coding: utf-8 -*-
+# Copyright 2014 OpenMarket Ltd
+#
+# 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.
+
+from twisted.trial import unittest
+
+import logging
+
+
+# logging doesn't have a "don't log anything at all EVARRRR setting,
+# but since the highest value is 50, 1000000 should do ;)
+NEVER = 1000000
+
+logging.getLogger().addHandler(logging.StreamHandler())
+logging.getLogger().setLevel(NEVER)
+
+
+def around(target):
+    """A CLOS-style 'around' modifier, which wraps the original method of the
+    given instance with another piece of code.
+
+    @around(self)
+    def method_name(orig, *args, **kwargs):
+        return orig(*args, **kwargs)
+    """
+    def _around(code):
+        name = code.__name__
+        orig = getattr(target, name)
+        def new(*args, **kwargs):
+            return code(orig, *args, **kwargs)
+        setattr(target, name, new)
+    return _around
+
+
+class TestCase(unittest.TestCase):
+    """A subclass of twisted.trial's TestCase which looks for 'loglevel'
+    attributes on both itself and its individual test methods, to override the
+    root logger's logging level while that test (case|method) runs."""
+
+    def __init__(self, methodName, *args, **kwargs):
+        super(TestCase, self).__init__(methodName, *args, **kwargs)
+
+        method = getattr(self, methodName)
+
+        level = getattr(method, "loglevel",
+                    getattr(self, "loglevel",
+                        NEVER))
+
+        @around(self)
+        def setUp(orig):
+            old_level = logging.getLogger().level
+
+            if old_level != level:
+                @around(self)
+                def tearDown(orig):
+                    ret = orig()
+                    logging.getLogger().setLevel(old_level)
+                    return ret
+
+            logging.getLogger().setLevel(level)
+            return orig()
+
+
+def DEBUG(target):
+    """A decorator to set the .loglevel attribute to logging.DEBUG.
+    Can apply to either a TestCase or an individual test method."""
+    target.loglevel = logging.DEBUG
+    return target
diff --git a/tests/util/test_lock.py b/tests/util/test_lock.py
index 5623d78423..6a1e521b1e 100644
--- a/tests/util/test_lock.py
+++ b/tests/util/test_lock.py
@@ -15,7 +15,7 @@
 
 
 from twisted.internet import defer
-from twisted.trial import unittest
+from tests import unittest
 
 from synapse.util.lockutils import LockManager
 
@@ -105,4 +105,4 @@ class LockManagerTestCase(unittest.TestCase):
             pass
 
         with (yield self.lock_manager.lock(key)):
-            pass
\ No newline at end of file
+            pass