test_v2.py 19 KB

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