summary refs log tree commit diff
path: root/synapse/state.py
blob: 9be6b716e2db8cc416b97c84938d265dac3b1fb8 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
# -*- 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.internet import defer

from synapse.federation.pdu_codec import encode_event_id, decode_event_id
from synapse.util.logutils import log_function

from collections import namedtuple

import logging
import hashlib

logger = logging.getLogger(__name__)


def _get_state_key_from_event(event):
    return event.state_key


KeyStateTuple = namedtuple("KeyStateTuple", ("context", "type", "state_key"))


class StateHandler(object):
    """ Responsible for doing state conflict resolution.
    """

    def __init__(self, hs):
        self.store = hs.get_datastore()
        self._replication = hs.get_replication_layer()
        self.server_name = hs.hostname

    @defer.inlineCallbacks
    @log_function
    def handle_new_event(self, event, snapshot):
        """ Given an event this works out if a) we have sufficient power level
        to update the state and b) works out what the prev_state should be.

        Returns:
            Deferred: Resolved with a boolean indicating if we successfully
            updated the state.

        Raised:
            AuthError
        """
        # This needs to be done in a transaction.

        if not hasattr(event, "state_key"):
            return

        key = KeyStateTuple(
            event.room_id,
            event.type,
            _get_state_key_from_event(event)
        )

        # Now I need to fill out the prev state and work out if it has auth
        # (w.r.t. to power levels)

        snapshot.fill_out_prev_events(event)
        yield self.annotate_state_groups(event)

        event.prev_events = [
            e for e in event.prev_events if e != event.event_id
        ]

        current_state = snapshot.prev_state_pdu

        if current_state:
            event.prev_state = encode_event_id(
                current_state.pdu_id, current_state.origin
            )

        # TODO check current_state to see if the min power level is less
        # than the power level of the user
        # power_level = self._get_power_level_for_event(event)

        pdu_id, origin = decode_event_id(event.event_id, self.server_name)

        yield self.store.update_current_state(
            pdu_id=pdu_id,
            origin=origin,
            context=key.context,
            pdu_type=key.type,
            state_key=key.state_key
        )

        defer.returnValue(True)

    @defer.inlineCallbacks
    @log_function
    def handle_new_state(self, new_pdu):
        """ Apply conflict resolution to `new_pdu`.

        This should be called on every new state pdu, regardless of whether or
        not there is a conflict.

        This function is safe against the race of it getting called with two
        `PDU`s trying to update the same state.
        """

        # This needs to be done in a transaction.

        is_new = yield self._handle_new_state(new_pdu)

        logger.debug("is_new: %s %s %s", is_new, new_pdu.pdu_id, new_pdu.origin)

        if is_new:
            yield self.store.update_current_state(
                pdu_id=new_pdu.pdu_id,
                origin=new_pdu.origin,
                context=new_pdu.context,
                pdu_type=new_pdu.pdu_type,
                state_key=new_pdu.state_key
            )

        defer.returnValue(is_new)

    @defer.inlineCallbacks
    def annotate_state_groups(self, event):
        state_groups = yield self.store.get_state_groups(
            event.prev_events
        )

        state = {}
        state_sets = {}
        for group in state_groups:
            for s in group.state:
                state.setdefault((s.type, s.state_key), []).append(s)

                state_sets.setdefault(
                    (s.type, s.state_key),
                    set()
                ).add(s.event_id)

        unconflicted_state = {
            k: state[k].pop() for k, v in state_sets.items()
            if len(v) == 1
        }

        conflicted_state = {
            k: state[k]
            for k, v in state_sets.items()
            if len(v) > 1
        }

        new_state = {}
        new_state.update(unconflicted_state)
        for key, events in conflicted_state.items():
            new_state[key] = yield self.resolve(events)

        event.old_state_events = new_state

        if hasattr(event, "state_key"):
            new_state[(event.type, event.state_key)] = event

        event.state_group = None
        event.state_events = new_state

    @defer.inlineCallbacks
    def resolve(self, events):
        curr_events = events

        new_powers_deferreds = []
        for e in curr_events:
            new_powers_deferreds.append(
                self.store.get_power_level(e.context, e.user_id)
            )

        new_powers = yield defer.gatherResults(
            new_powers_deferreds,
            consumeErrors=True
        )

        max_power = max([int(p) for p in new_powers])

        curr_events = [
            z[0] for z in zip(curr_events, new_powers)
            if int(z[1]) == max_power
        ]

        if not curr_events:
            raise RuntimeError("Max didn't get a max?")
        elif len(curr_events) == 1:
            defer.returnValue(curr_events[0])

        # TODO: For now, just choose the one with the largest event_id.
        defer.returnValue(
            sorted(
                curr_events,
                key=lambda e: hashlib.sha1(
                    e.event_id + e.user_id + e.room_id + e.type
                ).hexdigest()
            )[0]
        )

    def _get_power_level_for_event(self, event):
        # return self._persistence.get_power_level_for_user(event.room_id,
            # event.sender)
        return event.power_level

    @defer.inlineCallbacks
    @log_function
    def _handle_new_state(self, new_pdu):
        tree, missing_branch = yield self.store.get_unresolved_state_tree(
            new_pdu
        )
        new_branch, current_branch = tree

        logger.debug(
            "_handle_new_state new=%s, current=%s",
            new_branch, current_branch
        )

        if missing_branch is not None:
            # We're missing some PDUs. Fetch them.
            # TODO (erikj): Limit this.
            missing_prev = tree[missing_branch][-1]

            pdu_id = missing_prev.prev_state_id
            origin = missing_prev.prev_state_origin

            is_missing = yield self.store.get_pdu(pdu_id, origin) is None
            if not is_missing:
                raise Exception("Conflict resolution failed")

            yield self._replication.get_pdu(
                destination=missing_prev.origin,
                pdu_origin=origin,
                pdu_id=pdu_id,
                outlier=True
            )

            updated_current = yield self._handle_new_state(new_pdu)
            defer.returnValue(updated_current)

        if not current_branch:
            # There is no current state
            defer.returnValue(True)
            return

        n = new_branch[-1]
        c = current_branch[-1]

        common_ancestor = n.pdu_id == c.pdu_id and n.origin == c.origin

        if common_ancestor:
            # We found a common ancestor!

            if len(current_branch) == 1:
                # This is a direct clobber so we can just...
                defer.returnValue(True)

        else:
            # We didn't find a common ancestor. This is probably fine.
            pass

        result = yield self._do_conflict_res(
            new_branch, current_branch, common_ancestor
        )
        defer.returnValue(result)

    @defer.inlineCallbacks
    def _do_conflict_res(self, new_branch, current_branch, common_ancestor):
        conflict_res = [
            self._do_power_level_conflict_res,
            self._do_chain_length_conflict_res,
            self._do_hash_conflict_res,
        ]

        for algo in conflict_res:
            new_res, curr_res = yield defer.maybeDeferred(
                algo,
                new_branch, current_branch, common_ancestor
            )

            if new_res < curr_res:
                defer.returnValue(False)
            elif new_res > curr_res:
                defer.returnValue(True)

        raise Exception("Conflict resolution failed.")

    @defer.inlineCallbacks
    def _do_power_level_conflict_res(self, new_branch, current_branch,
                                     common_ancestor):
        new_powers_deferreds = []
        for e in new_branch[:-1] if common_ancestor else new_branch:
            if hasattr(e, "user_id"):
                new_powers_deferreds.append(
                    self.store.get_power_level(e.context, e.user_id)
                )

        current_powers_deferreds = []
        for e in current_branch[:-1] if common_ancestor else current_branch:
            if hasattr(e, "user_id"):
                current_powers_deferreds.append(
                    self.store.get_power_level(e.context, e.user_id)
                )

        new_powers = yield defer.gatherResults(
            new_powers_deferreds,
            consumeErrors=True
        )

        current_powers = yield defer.gatherResults(
            current_powers_deferreds,
            consumeErrors=True
        )

        max_power_new = max(new_powers)
        max_power_current = max(current_powers)

        defer.returnValue(
            (max_power_new, max_power_current)
        )

    def _do_chain_length_conflict_res(self, new_branch, current_branch,
                                      common_ancestor):
        return (len(new_branch), len(current_branch))

    def _do_hash_conflict_res(self, new_branch, current_branch,
                              common_ancestor):
        new_str = "".join([p.pdu_id + p.origin for p in new_branch])
        c_str = "".join([p.pdu_id + p.origin for p in current_branch])

        return (
            hashlib.sha1(new_str).hexdigest(),
            hashlib.sha1(c_str).hexdigest()
        )