test_v2.py 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636
  1. # -*- coding: utf-8 -*-
  2. # Copyright 2018 New Vector 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. import itertools
  16. from six.moves import zip
  17. import attr
  18. from synapse.api.constants import EventTypes, JoinRules, Membership
  19. from synapse.api.room_versions import RoomVersions
  20. from synapse.event_auth import auth_types_for_event
  21. from synapse.events import FrozenEvent
  22. from synapse.state.v2 import lexicographical_topological_sort, resolve_events_with_store
  23. from synapse.types import EventID
  24. from tests import unittest
  25. ALICE = "@alice:example.com"
  26. BOB = "@bob:example.com"
  27. CHARLIE = "@charlie:example.com"
  28. EVELYN = "@evelyn:example.com"
  29. ZARA = "@zara:example.com"
  30. ROOM_ID = "!test:example.com"
  31. MEMBERSHIP_CONTENT_JOIN = {"membership": Membership.JOIN}
  32. MEMBERSHIP_CONTENT_BAN = {"membership": Membership.BAN}
  33. ORIGIN_SERVER_TS = 0
  34. class FakeEvent(object):
  35. """A fake event we use as a convenience.
  36. NOTE: Again as a convenience we use "node_ids" rather than event_ids to
  37. refer to events. The event_id has node_id as localpart and example.com
  38. as domain.
  39. """
  40. def __init__(self, id, sender, type, state_key, content):
  41. self.node_id = id
  42. self.event_id = EventID(id, "example.com").to_string()
  43. self.sender = sender
  44. self.type = type
  45. self.state_key = state_key
  46. self.content = content
  47. def to_event(self, auth_events, prev_events):
  48. """Given the auth_events and prev_events, convert to a Frozen Event
  49. Args:
  50. auth_events (list[str]): list of event_ids
  51. prev_events (list[str]): list of event_ids
  52. Returns:
  53. FrozenEvent
  54. """
  55. global ORIGIN_SERVER_TS
  56. ts = ORIGIN_SERVER_TS
  57. ORIGIN_SERVER_TS = ORIGIN_SERVER_TS + 1
  58. event_dict = {
  59. "auth_events": [(a, {}) for a in auth_events],
  60. "prev_events": [(p, {}) for p in prev_events],
  61. "event_id": self.node_id,
  62. "sender": self.sender,
  63. "type": self.type,
  64. "content": self.content,
  65. "origin_server_ts": ts,
  66. "room_id": ROOM_ID,
  67. }
  68. if self.state_key is not None:
  69. event_dict["state_key"] = self.state_key
  70. return FrozenEvent(event_dict)
  71. # All graphs start with this set of events
  72. INITIAL_EVENTS = [
  73. FakeEvent(
  74. id="CREATE",
  75. sender=ALICE,
  76. type=EventTypes.Create,
  77. state_key="",
  78. content={"creator": ALICE},
  79. ),
  80. FakeEvent(
  81. id="IMA",
  82. sender=ALICE,
  83. type=EventTypes.Member,
  84. state_key=ALICE,
  85. content=MEMBERSHIP_CONTENT_JOIN,
  86. ),
  87. FakeEvent(
  88. id="IPOWER",
  89. sender=ALICE,
  90. type=EventTypes.PowerLevels,
  91. state_key="",
  92. content={"users": {ALICE: 100}},
  93. ),
  94. FakeEvent(
  95. id="IJR",
  96. sender=ALICE,
  97. type=EventTypes.JoinRules,
  98. state_key="",
  99. content={"join_rule": JoinRules.PUBLIC},
  100. ),
  101. FakeEvent(
  102. id="IMB",
  103. sender=BOB,
  104. type=EventTypes.Member,
  105. state_key=BOB,
  106. content=MEMBERSHIP_CONTENT_JOIN,
  107. ),
  108. FakeEvent(
  109. id="IMC",
  110. sender=CHARLIE,
  111. type=EventTypes.Member,
  112. state_key=CHARLIE,
  113. content=MEMBERSHIP_CONTENT_JOIN,
  114. ),
  115. FakeEvent(
  116. id="IMZ",
  117. sender=ZARA,
  118. type=EventTypes.Member,
  119. state_key=ZARA,
  120. content=MEMBERSHIP_CONTENT_JOIN,
  121. ),
  122. FakeEvent(
  123. id="START", sender=ZARA, type=EventTypes.Message, state_key=None, content={}
  124. ),
  125. FakeEvent(
  126. id="END", sender=ZARA, type=EventTypes.Message, state_key=None, content={}
  127. ),
  128. ]
  129. INITIAL_EDGES = ["START", "IMZ", "IMC", "IMB", "IJR", "IPOWER", "IMA", "CREATE"]
  130. class StateTestCase(unittest.TestCase):
  131. def test_ban_vs_pl(self):
  132. events = [
  133. FakeEvent(
  134. id="PA",
  135. sender=ALICE,
  136. type=EventTypes.PowerLevels,
  137. state_key="",
  138. content={"users": {ALICE: 100, BOB: 50}},
  139. ),
  140. FakeEvent(
  141. id="MA",
  142. sender=ALICE,
  143. type=EventTypes.Member,
  144. state_key=ALICE,
  145. content={"membership": Membership.JOIN},
  146. ),
  147. FakeEvent(
  148. id="MB",
  149. sender=ALICE,
  150. type=EventTypes.Member,
  151. state_key=BOB,
  152. content={"membership": Membership.BAN},
  153. ),
  154. FakeEvent(
  155. id="PB",
  156. sender=BOB,
  157. type=EventTypes.PowerLevels,
  158. state_key="",
  159. content={"users": {ALICE: 100, BOB: 50}},
  160. ),
  161. ]
  162. edges = [["END", "MB", "MA", "PA", "START"], ["END", "PB", "PA"]]
  163. expected_state_ids = ["PA", "MA", "MB"]
  164. self.do_check(events, edges, expected_state_ids)
  165. def test_join_rule_evasion(self):
  166. events = [
  167. FakeEvent(
  168. id="JR",
  169. sender=ALICE,
  170. type=EventTypes.JoinRules,
  171. state_key="",
  172. content={"join_rules": JoinRules.PRIVATE},
  173. ),
  174. FakeEvent(
  175. id="ME",
  176. sender=EVELYN,
  177. type=EventTypes.Member,
  178. state_key=EVELYN,
  179. content={"membership": Membership.JOIN},
  180. ),
  181. ]
  182. edges = [["END", "JR", "START"], ["END", "ME", "START"]]
  183. expected_state_ids = ["JR"]
  184. self.do_check(events, edges, expected_state_ids)
  185. def test_offtopic_pl(self):
  186. events = [
  187. FakeEvent(
  188. id="PA",
  189. sender=ALICE,
  190. type=EventTypes.PowerLevels,
  191. state_key="",
  192. content={"users": {ALICE: 100, BOB: 50}},
  193. ),
  194. FakeEvent(
  195. id="PB",
  196. sender=BOB,
  197. type=EventTypes.PowerLevels,
  198. state_key="",
  199. content={"users": {ALICE: 100, BOB: 50, CHARLIE: 50}},
  200. ),
  201. FakeEvent(
  202. id="PC",
  203. sender=CHARLIE,
  204. type=EventTypes.PowerLevels,
  205. state_key="",
  206. content={"users": {ALICE: 100, BOB: 50, CHARLIE: 0}},
  207. ),
  208. ]
  209. edges = [["END", "PC", "PB", "PA", "START"], ["END", "PA"]]
  210. expected_state_ids = ["PC"]
  211. self.do_check(events, edges, expected_state_ids)
  212. def test_topic_basic(self):
  213. events = [
  214. FakeEvent(
  215. id="T1", sender=ALICE, type=EventTypes.Topic, state_key="", content={}
  216. ),
  217. FakeEvent(
  218. id="PA1",
  219. sender=ALICE,
  220. type=EventTypes.PowerLevels,
  221. state_key="",
  222. content={"users": {ALICE: 100, BOB: 50}},
  223. ),
  224. FakeEvent(
  225. id="T2", sender=ALICE, type=EventTypes.Topic, state_key="", content={}
  226. ),
  227. FakeEvent(
  228. id="PA2",
  229. sender=ALICE,
  230. type=EventTypes.PowerLevels,
  231. state_key="",
  232. content={"users": {ALICE: 100, BOB: 0}},
  233. ),
  234. FakeEvent(
  235. id="PB",
  236. sender=BOB,
  237. type=EventTypes.PowerLevels,
  238. state_key="",
  239. content={"users": {ALICE: 100, BOB: 50}},
  240. ),
  241. FakeEvent(
  242. id="T3", sender=BOB, type=EventTypes.Topic, state_key="", content={}
  243. ),
  244. ]
  245. edges = [["END", "PA2", "T2", "PA1", "T1", "START"], ["END", "T3", "PB", "PA1"]]
  246. expected_state_ids = ["PA2", "T2"]
  247. self.do_check(events, edges, expected_state_ids)
  248. def test_topic_reset(self):
  249. events = [
  250. FakeEvent(
  251. id="T1", sender=ALICE, type=EventTypes.Topic, state_key="", content={}
  252. ),
  253. FakeEvent(
  254. id="PA",
  255. sender=ALICE,
  256. type=EventTypes.PowerLevels,
  257. state_key="",
  258. content={"users": {ALICE: 100, BOB: 50}},
  259. ),
  260. FakeEvent(
  261. id="T2", sender=BOB, type=EventTypes.Topic, state_key="", content={}
  262. ),
  263. FakeEvent(
  264. id="MB",
  265. sender=ALICE,
  266. type=EventTypes.Member,
  267. state_key=BOB,
  268. content={"membership": Membership.BAN},
  269. ),
  270. ]
  271. edges = [["END", "MB", "T2", "PA", "T1", "START"], ["END", "T1"]]
  272. expected_state_ids = ["T1", "MB", "PA"]
  273. self.do_check(events, edges, expected_state_ids)
  274. def test_topic(self):
  275. events = [
  276. FakeEvent(
  277. id="T1", sender=ALICE, type=EventTypes.Topic, state_key="", content={}
  278. ),
  279. FakeEvent(
  280. id="PA1",
  281. sender=ALICE,
  282. type=EventTypes.PowerLevels,
  283. state_key="",
  284. content={"users": {ALICE: 100, BOB: 50}},
  285. ),
  286. FakeEvent(
  287. id="T2", sender=ALICE, type=EventTypes.Topic, state_key="", content={}
  288. ),
  289. FakeEvent(
  290. id="PA2",
  291. sender=ALICE,
  292. type=EventTypes.PowerLevels,
  293. state_key="",
  294. content={"users": {ALICE: 100, BOB: 0}},
  295. ),
  296. FakeEvent(
  297. id="PB",
  298. sender=BOB,
  299. type=EventTypes.PowerLevels,
  300. state_key="",
  301. content={"users": {ALICE: 100, BOB: 50}},
  302. ),
  303. FakeEvent(
  304. id="T3", sender=BOB, type=EventTypes.Topic, state_key="", content={}
  305. ),
  306. FakeEvent(
  307. id="MZ1",
  308. sender=ZARA,
  309. type=EventTypes.Message,
  310. state_key=None,
  311. content={},
  312. ),
  313. FakeEvent(
  314. id="T4", sender=ALICE, type=EventTypes.Topic, state_key="", content={}
  315. ),
  316. ]
  317. edges = [
  318. ["END", "T4", "MZ1", "PA2", "T2", "PA1", "T1", "START"],
  319. ["END", "MZ1", "T3", "PB", "PA1"],
  320. ]
  321. expected_state_ids = ["T4", "PA2"]
  322. self.do_check(events, edges, expected_state_ids)
  323. def do_check(self, events, edges, expected_state_ids):
  324. """Take a list of events and edges and calculate the state of the
  325. graph at END, and asserts it matches `expected_state_ids`
  326. Args:
  327. events (list[FakeEvent])
  328. edges (list[list[str]]): A list of chains of event edges, e.g.
  329. `[[A, B, C]]` are edges A->B and B->C.
  330. expected_state_ids (list[str]): The expected state at END, (excluding
  331. the keys that haven't changed since START).
  332. """
  333. # We want to sort the events into topological order for processing.
  334. graph = {}
  335. # node_id -> FakeEvent
  336. fake_event_map = {}
  337. for ev in itertools.chain(INITIAL_EVENTS, events):
  338. graph[ev.node_id] = set()
  339. fake_event_map[ev.node_id] = ev
  340. for a, b in pairwise(INITIAL_EDGES):
  341. graph[a].add(b)
  342. for edge_list in edges:
  343. for a, b in pairwise(edge_list):
  344. graph[a].add(b)
  345. # event_id -> FrozenEvent
  346. event_map = {}
  347. # node_id -> state
  348. state_at_event = {}
  349. # We copy the map as the sort consumes the graph
  350. graph_copy = {k: set(v) for k, v in graph.items()}
  351. for node_id in lexicographical_topological_sort(graph_copy, key=lambda e: e):
  352. fake_event = fake_event_map[node_id]
  353. event_id = fake_event.event_id
  354. prev_events = list(graph[node_id])
  355. if len(prev_events) == 0:
  356. state_before = {}
  357. elif len(prev_events) == 1:
  358. state_before = dict(state_at_event[prev_events[0]])
  359. else:
  360. state_d = resolve_events_with_store(
  361. RoomVersions.V2.identifier,
  362. [state_at_event[n] for n in prev_events],
  363. event_map=event_map,
  364. state_res_store=TestStateResolutionStore(event_map),
  365. )
  366. state_before = self.successResultOf(state_d)
  367. state_after = dict(state_before)
  368. if fake_event.state_key is not None:
  369. state_after[(fake_event.type, fake_event.state_key)] = event_id
  370. auth_types = set(auth_types_for_event(fake_event))
  371. auth_events = []
  372. for key in auth_types:
  373. if key in state_before:
  374. auth_events.append(state_before[key])
  375. event = fake_event.to_event(auth_events, prev_events)
  376. state_at_event[node_id] = state_after
  377. event_map[event_id] = event
  378. expected_state = {}
  379. for node_id in expected_state_ids:
  380. # expected_state_ids are node IDs rather than event IDs,
  381. # so we have to convert
  382. event_id = EventID(node_id, "example.com").to_string()
  383. event = event_map[event_id]
  384. key = (event.type, event.state_key)
  385. expected_state[key] = event_id
  386. start_state = state_at_event["START"]
  387. end_state = {
  388. key: value
  389. for key, value in state_at_event["END"].items()
  390. if key in expected_state or start_state.get(key) != value
  391. }
  392. self.assertEqual(expected_state, end_state)
  393. class LexicographicalTestCase(unittest.TestCase):
  394. def test_simple(self):
  395. graph = {"l": {"o"}, "m": {"n", "o"}, "n": {"o"}, "o": set(), "p": {"o"}}
  396. res = list(lexicographical_topological_sort(graph, key=lambda x: x))
  397. self.assertEqual(["o", "l", "n", "m", "p"], res)
  398. class SimpleParamStateTestCase(unittest.TestCase):
  399. def setUp(self):
  400. # We build up a simple DAG.
  401. event_map = {}
  402. create_event = FakeEvent(
  403. id="CREATE",
  404. sender=ALICE,
  405. type=EventTypes.Create,
  406. state_key="",
  407. content={"creator": ALICE},
  408. ).to_event([], [])
  409. event_map[create_event.event_id] = create_event
  410. alice_member = FakeEvent(
  411. id="IMA",
  412. sender=ALICE,
  413. type=EventTypes.Member,
  414. state_key=ALICE,
  415. content=MEMBERSHIP_CONTENT_JOIN,
  416. ).to_event([create_event.event_id], [create_event.event_id])
  417. event_map[alice_member.event_id] = alice_member
  418. join_rules = FakeEvent(
  419. id="IJR",
  420. sender=ALICE,
  421. type=EventTypes.JoinRules,
  422. state_key="",
  423. content={"join_rule": JoinRules.PUBLIC},
  424. ).to_event(
  425. auth_events=[create_event.event_id, alice_member.event_id],
  426. prev_events=[alice_member.event_id],
  427. )
  428. event_map[join_rules.event_id] = join_rules
  429. # Bob and Charlie join at the same time, so there is a fork
  430. bob_member = FakeEvent(
  431. id="IMB",
  432. sender=BOB,
  433. type=EventTypes.Member,
  434. state_key=BOB,
  435. content=MEMBERSHIP_CONTENT_JOIN,
  436. ).to_event(
  437. auth_events=[create_event.event_id, join_rules.event_id],
  438. prev_events=[join_rules.event_id],
  439. )
  440. event_map[bob_member.event_id] = bob_member
  441. charlie_member = FakeEvent(
  442. id="IMC",
  443. sender=CHARLIE,
  444. type=EventTypes.Member,
  445. state_key=CHARLIE,
  446. content=MEMBERSHIP_CONTENT_JOIN,
  447. ).to_event(
  448. auth_events=[create_event.event_id, join_rules.event_id],
  449. prev_events=[join_rules.event_id],
  450. )
  451. event_map[charlie_member.event_id] = charlie_member
  452. self.event_map = event_map
  453. self.create_event = create_event
  454. self.alice_member = alice_member
  455. self.join_rules = join_rules
  456. self.bob_member = bob_member
  457. self.charlie_member = charlie_member
  458. self.state_at_bob = {
  459. (e.type, e.state_key): e.event_id
  460. for e in [create_event, alice_member, join_rules, bob_member]
  461. }
  462. self.state_at_charlie = {
  463. (e.type, e.state_key): e.event_id
  464. for e in [create_event, alice_member, join_rules, charlie_member]
  465. }
  466. self.expected_combined_state = {
  467. (e.type, e.state_key): e.event_id
  468. for e in [
  469. create_event,
  470. alice_member,
  471. join_rules,
  472. bob_member,
  473. charlie_member,
  474. ]
  475. }
  476. def test_event_map_none(self):
  477. # Test that we correctly handle passing `None` as the event_map
  478. state_d = resolve_events_with_store(
  479. RoomVersions.V2.identifier,
  480. [self.state_at_bob, self.state_at_charlie],
  481. event_map=None,
  482. state_res_store=TestStateResolutionStore(self.event_map),
  483. )
  484. state = self.successResultOf(state_d)
  485. self.assert_dict(self.expected_combined_state, state)
  486. def pairwise(iterable):
  487. "s -> (s0,s1), (s1,s2), (s2, s3), ..."
  488. a, b = itertools.tee(iterable)
  489. next(b, None)
  490. return zip(a, b)
  491. @attr.s
  492. class TestStateResolutionStore(object):
  493. event_map = attr.ib()
  494. def get_events(self, event_ids, allow_rejected=False):
  495. """Get events from the database
  496. Args:
  497. event_ids (list): The event_ids of the events to fetch
  498. allow_rejected (bool): If True return rejected events.
  499. Returns:
  500. Deferred[dict[str, FrozenEvent]]: Dict from event_id to event.
  501. """
  502. return {eid: self.event_map[eid] for eid in event_ids if eid in self.event_map}
  503. def get_auth_chain(self, event_ids):
  504. """Gets the full auth chain for a set of events (including rejected
  505. events).
  506. Includes the given event IDs in the result.
  507. Note that:
  508. 1. All events must be state events.
  509. 2. For v1 rooms this may not have the full auth chain in the
  510. presence of rejected events
  511. Args:
  512. event_ids (list): The event IDs of the events to fetch the auth
  513. chain for. Must be state events.
  514. Returns:
  515. Deferred[list[str]]: List of event IDs of the auth chain.
  516. """
  517. # Simple DFS for auth chain
  518. result = set()
  519. stack = list(event_ids)
  520. while stack:
  521. event_id = stack.pop()
  522. if event_id in result:
  523. continue
  524. result.add(event_id)
  525. event = self.event_map[event_id]
  526. for aid in event.auth_event_ids():
  527. stack.append(aid)
  528. return list(result)