test_state.py 21 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663
  1. # -*- coding: utf-8 -*-
  2. # Copyright 2014-2016 OpenMarket Ltd
  3. #
  4. # Licensed under the Apache License, Version 2.0 (the "License");
  5. # you may not use this file except in compliance with the License.
  6. # You may obtain a copy of the License at
  7. #
  8. # http://www.apache.org/licenses/LICENSE-2.0
  9. #
  10. # Unless required by applicable law or agreed to in writing, software
  11. # distributed under the License is distributed on an "AS IS" BASIS,
  12. # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13. # See the License for the specific language governing permissions and
  14. # limitations under the License.
  15. from mock import Mock
  16. from twisted.internet import defer
  17. from synapse.api.auth import Auth
  18. from synapse.api.constants import EventTypes, Membership
  19. from synapse.api.room_versions import RoomVersions
  20. from synapse.events import FrozenEvent
  21. from synapse.state import StateHandler, StateResolutionHandler
  22. from tests import unittest
  23. from .utils import MockClock, default_config
  24. _next_event_id = 1000
  25. def create_event(
  26. name=None,
  27. type=None,
  28. state_key=None,
  29. depth=2,
  30. event_id=None,
  31. prev_events=[],
  32. **kwargs
  33. ):
  34. global _next_event_id
  35. if not event_id:
  36. _next_event_id += 1
  37. event_id = "$%s:test" % (_next_event_id,)
  38. if not name:
  39. if state_key is not None:
  40. name = "<%s-%s, %s>" % (type, state_key, event_id)
  41. else:
  42. name = "<%s, %s>" % (type, event_id)
  43. d = {
  44. "event_id": event_id,
  45. "type": type,
  46. "sender": "@user_id:example.com",
  47. "room_id": "!room_id:example.com",
  48. "depth": depth,
  49. "prev_events": prev_events,
  50. }
  51. if state_key is not None:
  52. d["state_key"] = state_key
  53. d.update(kwargs)
  54. event = FrozenEvent(d)
  55. return event
  56. class StateGroupStore(object):
  57. def __init__(self):
  58. self._event_to_state_group = {}
  59. self._group_to_state = {}
  60. self._event_id_to_event = {}
  61. self._next_group = 1
  62. def get_state_groups_ids(self, room_id, event_ids):
  63. groups = {}
  64. for event_id in event_ids:
  65. group = self._event_to_state_group.get(event_id)
  66. if group:
  67. groups[group] = self._group_to_state[group]
  68. return defer.succeed(groups)
  69. def store_state_group(
  70. self, event_id, room_id, prev_group, delta_ids, current_state_ids
  71. ):
  72. state_group = self._next_group
  73. self._next_group += 1
  74. self._group_to_state[state_group] = dict(current_state_ids)
  75. return state_group
  76. def get_events(self, event_ids, **kwargs):
  77. return {
  78. e_id: self._event_id_to_event[e_id]
  79. for e_id in event_ids
  80. if e_id in self._event_id_to_event
  81. }
  82. def get_state_group_delta(self, name):
  83. return None, None
  84. def register_events(self, events):
  85. for e in events:
  86. self._event_id_to_event[e.event_id] = e
  87. def register_event_context(self, event, context):
  88. self._event_to_state_group[event.event_id] = context.state_group
  89. def register_event_id_state_group(self, event_id, state_group):
  90. self._event_to_state_group[event_id] = state_group
  91. def get_room_version(self, room_id):
  92. return RoomVersions.V1.identifier
  93. class DictObj(dict):
  94. def __init__(self, **kwargs):
  95. super(DictObj, self).__init__(kwargs)
  96. self.__dict__ = self
  97. class Graph(object):
  98. def __init__(self, nodes, edges):
  99. events = {}
  100. clobbered = set(events.keys())
  101. for event_id, fields in nodes.items():
  102. refs = edges.get(event_id)
  103. if refs:
  104. clobbered.difference_update(refs)
  105. prev_events = [(r, {}) for r in refs]
  106. else:
  107. prev_events = []
  108. events[event_id] = create_event(
  109. event_id=event_id, prev_events=prev_events, **fields
  110. )
  111. self._leaves = clobbered
  112. self._events = sorted(events.values(), key=lambda e: e.depth)
  113. def walk(self):
  114. return iter(self._events)
  115. def get_leaves(self):
  116. return (self._events[i] for i in self._leaves)
  117. class StateTestCase(unittest.TestCase):
  118. def setUp(self):
  119. self.store = StateGroupStore()
  120. hs = Mock(
  121. spec_set=[
  122. "config",
  123. "get_datastore",
  124. "get_auth",
  125. "get_state_handler",
  126. "get_clock",
  127. "get_state_resolution_handler",
  128. ]
  129. )
  130. hs.config = default_config("tesths", True)
  131. hs.get_datastore.return_value = self.store
  132. hs.get_state_handler.return_value = None
  133. hs.get_clock.return_value = MockClock()
  134. hs.get_auth.return_value = Auth(hs)
  135. hs.get_state_resolution_handler = lambda: StateResolutionHandler(hs)
  136. self.state = StateHandler(hs)
  137. self.event_id = 0
  138. @defer.inlineCallbacks
  139. def test_branch_no_conflict(self):
  140. graph = Graph(
  141. nodes={
  142. "START": DictObj(
  143. type=EventTypes.Create, state_key="", content={}, depth=1
  144. ),
  145. "A": DictObj(type=EventTypes.Message, depth=2),
  146. "B": DictObj(type=EventTypes.Message, depth=3),
  147. "C": DictObj(type=EventTypes.Name, state_key="", depth=3),
  148. "D": DictObj(type=EventTypes.Message, depth=4),
  149. },
  150. edges={"A": ["START"], "B": ["A"], "C": ["A"], "D": ["B", "C"]},
  151. )
  152. self.store.register_events(graph.walk())
  153. context_store = {}
  154. for event in graph.walk():
  155. context = yield self.state.compute_event_context(event)
  156. self.store.register_event_context(event, context)
  157. context_store[event.event_id] = context
  158. prev_state_ids = yield context_store["D"].get_prev_state_ids(self.store)
  159. self.assertEqual(2, len(prev_state_ids))
  160. @defer.inlineCallbacks
  161. def test_branch_basic_conflict(self):
  162. graph = Graph(
  163. nodes={
  164. "START": DictObj(
  165. type=EventTypes.Create,
  166. state_key="",
  167. content={"creator": "@user_id:example.com"},
  168. depth=1,
  169. ),
  170. "A": DictObj(
  171. type=EventTypes.Member,
  172. state_key="@user_id:example.com",
  173. content={"membership": Membership.JOIN},
  174. membership=Membership.JOIN,
  175. depth=2,
  176. ),
  177. "B": DictObj(type=EventTypes.Name, state_key="", depth=3),
  178. "C": DictObj(type=EventTypes.Name, state_key="", depth=4),
  179. "D": DictObj(type=EventTypes.Message, depth=5),
  180. },
  181. edges={"A": ["START"], "B": ["A"], "C": ["A"], "D": ["B", "C"]},
  182. )
  183. self.store.register_events(graph.walk())
  184. context_store = {}
  185. for event in graph.walk():
  186. context = yield self.state.compute_event_context(event)
  187. self.store.register_event_context(event, context)
  188. context_store[event.event_id] = context
  189. prev_state_ids = yield context_store["D"].get_prev_state_ids(self.store)
  190. self.assertSetEqual(
  191. {"START", "A", "C"}, {e_id for e_id in prev_state_ids.values()}
  192. )
  193. @defer.inlineCallbacks
  194. def test_branch_have_banned_conflict(self):
  195. graph = Graph(
  196. nodes={
  197. "START": DictObj(
  198. type=EventTypes.Create,
  199. state_key="",
  200. content={"creator": "@user_id:example.com"},
  201. depth=1,
  202. ),
  203. "A": DictObj(
  204. type=EventTypes.Member,
  205. state_key="@user_id:example.com",
  206. content={"membership": Membership.JOIN},
  207. membership=Membership.JOIN,
  208. depth=2,
  209. ),
  210. "B": DictObj(type=EventTypes.Name, state_key="", depth=3),
  211. "C": DictObj(
  212. type=EventTypes.Member,
  213. state_key="@user_id_2:example.com",
  214. content={"membership": Membership.BAN},
  215. membership=Membership.BAN,
  216. depth=4,
  217. ),
  218. "D": DictObj(
  219. type=EventTypes.Name,
  220. state_key="",
  221. depth=4,
  222. sender="@user_id_2:example.com",
  223. ),
  224. "E": DictObj(type=EventTypes.Message, depth=5),
  225. },
  226. edges={"A": ["START"], "B": ["A"], "C": ["B"], "D": ["B"], "E": ["C", "D"]},
  227. )
  228. self.store.register_events(graph.walk())
  229. context_store = {}
  230. for event in graph.walk():
  231. context = yield self.state.compute_event_context(event)
  232. self.store.register_event_context(event, context)
  233. context_store[event.event_id] = context
  234. prev_state_ids = yield context_store["E"].get_prev_state_ids(self.store)
  235. self.assertSetEqual(
  236. {"START", "A", "B", "C"}, {e for e in prev_state_ids.values()}
  237. )
  238. @defer.inlineCallbacks
  239. def test_branch_have_perms_conflict(self):
  240. userid1 = "@user_id:example.com"
  241. userid2 = "@user_id2:example.com"
  242. nodes = {
  243. "A1": DictObj(
  244. type=EventTypes.Create,
  245. state_key="",
  246. content={"creator": userid1},
  247. depth=1,
  248. ),
  249. "A2": DictObj(
  250. type=EventTypes.Member,
  251. state_key=userid1,
  252. content={"membership": Membership.JOIN},
  253. membership=Membership.JOIN,
  254. ),
  255. "A3": DictObj(
  256. type=EventTypes.Member,
  257. state_key=userid2,
  258. content={"membership": Membership.JOIN},
  259. membership=Membership.JOIN,
  260. ),
  261. "A4": DictObj(
  262. type=EventTypes.PowerLevels,
  263. state_key="",
  264. content={
  265. "events": {"m.room.name": 50},
  266. "users": {userid1: 100, userid2: 60},
  267. },
  268. ),
  269. "A5": DictObj(type=EventTypes.Name, state_key=""),
  270. "B": DictObj(
  271. type=EventTypes.PowerLevels,
  272. state_key="",
  273. content={"events": {"m.room.name": 50}, "users": {userid2: 30}},
  274. ),
  275. "C": DictObj(type=EventTypes.Name, state_key="", sender=userid2),
  276. "D": DictObj(type=EventTypes.Message),
  277. }
  278. edges = {
  279. "A2": ["A1"],
  280. "A3": ["A2"],
  281. "A4": ["A3"],
  282. "A5": ["A4"],
  283. "B": ["A5"],
  284. "C": ["A5"],
  285. "D": ["B", "C"],
  286. }
  287. self._add_depths(nodes, edges)
  288. graph = Graph(nodes, edges)
  289. self.store.register_events(graph.walk())
  290. context_store = {}
  291. for event in graph.walk():
  292. context = yield self.state.compute_event_context(event)
  293. self.store.register_event_context(event, context)
  294. context_store[event.event_id] = context
  295. prev_state_ids = yield context_store["D"].get_prev_state_ids(self.store)
  296. self.assertSetEqual(
  297. {"A1", "A2", "A3", "A5", "B"}, {e for e in prev_state_ids.values()}
  298. )
  299. def _add_depths(self, nodes, edges):
  300. def _get_depth(ev):
  301. node = nodes[ev]
  302. if "depth" not in node:
  303. prevs = edges[ev]
  304. depth = max(_get_depth(prev) for prev in prevs) + 1
  305. node["depth"] = depth
  306. return node["depth"]
  307. for n in nodes:
  308. _get_depth(n)
  309. @defer.inlineCallbacks
  310. def test_annotate_with_old_message(self):
  311. event = create_event(type="test_message", name="event")
  312. old_state = [
  313. create_event(type="test1", state_key="1"),
  314. create_event(type="test1", state_key="2"),
  315. create_event(type="test2", state_key=""),
  316. ]
  317. context = yield self.state.compute_event_context(event, old_state=old_state)
  318. current_state_ids = yield context.get_current_state_ids(self.store)
  319. self.assertEqual(
  320. set(e.event_id for e in old_state), set(current_state_ids.values())
  321. )
  322. self.assertIsNotNone(context.state_group)
  323. @defer.inlineCallbacks
  324. def test_annotate_with_old_state(self):
  325. event = create_event(type="state", state_key="", name="event")
  326. old_state = [
  327. create_event(type="test1", state_key="1"),
  328. create_event(type="test1", state_key="2"),
  329. create_event(type="test2", state_key=""),
  330. ]
  331. context = yield self.state.compute_event_context(event, old_state=old_state)
  332. prev_state_ids = yield context.get_prev_state_ids(self.store)
  333. self.assertEqual(
  334. set(e.event_id for e in old_state), set(prev_state_ids.values())
  335. )
  336. @defer.inlineCallbacks
  337. def test_trivial_annotate_message(self):
  338. prev_event_id = "prev_event_id"
  339. event = create_event(
  340. type="test_message", name="event2", prev_events=[(prev_event_id, {})]
  341. )
  342. old_state = [
  343. create_event(type="test1", state_key="1"),
  344. create_event(type="test1", state_key="2"),
  345. create_event(type="test2", state_key=""),
  346. ]
  347. group_name = self.store.store_state_group(
  348. prev_event_id,
  349. event.room_id,
  350. None,
  351. None,
  352. {(e.type, e.state_key): e.event_id for e in old_state},
  353. )
  354. self.store.register_event_id_state_group(prev_event_id, group_name)
  355. context = yield self.state.compute_event_context(event)
  356. current_state_ids = yield context.get_current_state_ids(self.store)
  357. self.assertEqual(
  358. set([e.event_id for e in old_state]), set(current_state_ids.values())
  359. )
  360. self.assertEqual(group_name, context.state_group)
  361. @defer.inlineCallbacks
  362. def test_trivial_annotate_state(self):
  363. prev_event_id = "prev_event_id"
  364. event = create_event(
  365. type="state", state_key="", name="event2", prev_events=[(prev_event_id, {})]
  366. )
  367. old_state = [
  368. create_event(type="test1", state_key="1"),
  369. create_event(type="test1", state_key="2"),
  370. create_event(type="test2", state_key=""),
  371. ]
  372. group_name = self.store.store_state_group(
  373. prev_event_id,
  374. event.room_id,
  375. None,
  376. None,
  377. {(e.type, e.state_key): e.event_id for e in old_state},
  378. )
  379. self.store.register_event_id_state_group(prev_event_id, group_name)
  380. context = yield self.state.compute_event_context(event)
  381. prev_state_ids = yield context.get_prev_state_ids(self.store)
  382. self.assertEqual(
  383. set([e.event_id for e in old_state]), set(prev_state_ids.values())
  384. )
  385. self.assertIsNotNone(context.state_group)
  386. @defer.inlineCallbacks
  387. def test_resolve_message_conflict(self):
  388. prev_event_id1 = "event_id1"
  389. prev_event_id2 = "event_id2"
  390. event = create_event(
  391. type="test_message",
  392. name="event3",
  393. prev_events=[(prev_event_id1, {}), (prev_event_id2, {})],
  394. )
  395. creation = create_event(type=EventTypes.Create, state_key="")
  396. old_state_1 = [
  397. creation,
  398. create_event(type="test1", state_key="1"),
  399. create_event(type="test1", state_key="2"),
  400. create_event(type="test2", state_key=""),
  401. ]
  402. old_state_2 = [
  403. creation,
  404. create_event(type="test1", state_key="1"),
  405. create_event(type="test3", state_key="2"),
  406. create_event(type="test4", state_key=""),
  407. ]
  408. self.store.register_events(old_state_1)
  409. self.store.register_events(old_state_2)
  410. context = yield self._get_context(
  411. event, prev_event_id1, old_state_1, prev_event_id2, old_state_2
  412. )
  413. current_state_ids = yield context.get_current_state_ids(self.store)
  414. self.assertEqual(len(current_state_ids), 6)
  415. self.assertIsNotNone(context.state_group)
  416. @defer.inlineCallbacks
  417. def test_resolve_state_conflict(self):
  418. prev_event_id1 = "event_id1"
  419. prev_event_id2 = "event_id2"
  420. event = create_event(
  421. type="test4",
  422. state_key="",
  423. name="event",
  424. prev_events=[(prev_event_id1, {}), (prev_event_id2, {})],
  425. )
  426. creation = create_event(type=EventTypes.Create, state_key="")
  427. old_state_1 = [
  428. creation,
  429. create_event(type="test1", state_key="1"),
  430. create_event(type="test1", state_key="2"),
  431. create_event(type="test2", state_key=""),
  432. ]
  433. old_state_2 = [
  434. creation,
  435. create_event(type="test1", state_key="1"),
  436. create_event(type="test3", state_key="2"),
  437. create_event(type="test4", state_key=""),
  438. ]
  439. store = StateGroupStore()
  440. store.register_events(old_state_1)
  441. store.register_events(old_state_2)
  442. self.store.get_events = store.get_events
  443. context = yield self._get_context(
  444. event, prev_event_id1, old_state_1, prev_event_id2, old_state_2
  445. )
  446. current_state_ids = yield context.get_current_state_ids(self.store)
  447. self.assertEqual(len(current_state_ids), 6)
  448. self.assertIsNotNone(context.state_group)
  449. @defer.inlineCallbacks
  450. def test_standard_depth_conflict(self):
  451. prev_event_id1 = "event_id1"
  452. prev_event_id2 = "event_id2"
  453. event = create_event(
  454. type="test4",
  455. name="event",
  456. prev_events=[(prev_event_id1, {}), (prev_event_id2, {})],
  457. )
  458. member_event = create_event(
  459. type=EventTypes.Member,
  460. state_key="@user_id:example.com",
  461. content={"membership": Membership.JOIN},
  462. )
  463. power_levels = create_event(
  464. type=EventTypes.PowerLevels,
  465. state_key="",
  466. content={"users": {"@foo:bar": "100", "@user_id:example.com": "100"}},
  467. )
  468. creation = create_event(
  469. type=EventTypes.Create, state_key="", content={"creator": "@foo:bar"}
  470. )
  471. old_state_1 = [
  472. creation,
  473. power_levels,
  474. member_event,
  475. create_event(type="test1", state_key="1", depth=1),
  476. ]
  477. old_state_2 = [
  478. creation,
  479. power_levels,
  480. member_event,
  481. create_event(type="test1", state_key="1", depth=2),
  482. ]
  483. store = StateGroupStore()
  484. store.register_events(old_state_1)
  485. store.register_events(old_state_2)
  486. self.store.get_events = store.get_events
  487. context = yield self._get_context(
  488. event, prev_event_id1, old_state_1, prev_event_id2, old_state_2
  489. )
  490. current_state_ids = yield context.get_current_state_ids(self.store)
  491. self.assertEqual(old_state_2[3].event_id, current_state_ids[("test1", "1")])
  492. # Reverse the depth to make sure we are actually using the depths
  493. # during state resolution.
  494. old_state_1 = [
  495. creation,
  496. power_levels,
  497. member_event,
  498. create_event(type="test1", state_key="1", depth=2),
  499. ]
  500. old_state_2 = [
  501. creation,
  502. power_levels,
  503. member_event,
  504. create_event(type="test1", state_key="1", depth=1),
  505. ]
  506. store.register_events(old_state_1)
  507. store.register_events(old_state_2)
  508. context = yield self._get_context(
  509. event, prev_event_id1, old_state_1, prev_event_id2, old_state_2
  510. )
  511. current_state_ids = yield context.get_current_state_ids(self.store)
  512. self.assertEqual(old_state_1[3].event_id, current_state_ids[("test1", "1")])
  513. def _get_context(
  514. self, event, prev_event_id_1, old_state_1, prev_event_id_2, old_state_2
  515. ):
  516. sg1 = self.store.store_state_group(
  517. prev_event_id_1,
  518. event.room_id,
  519. None,
  520. None,
  521. {(e.type, e.state_key): e.event_id for e in old_state_1},
  522. )
  523. self.store.register_event_id_state_group(prev_event_id_1, sg1)
  524. sg2 = self.store.store_state_group(
  525. prev_event_id_2,
  526. event.room_id,
  527. None,
  528. None,
  529. {(e.type, e.state_key): e.event_id for e in old_state_2},
  530. )
  531. self.store.register_event_id_state_group(prev_event_id_2, sg2)
  532. return self.state.compute_event_context(event)