summary refs log tree commit diff
path: root/synapse/state.py
blob: e69282860a0ca2567763cf729c50266fa25570bc (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
# -*- 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):
    """ Repsonsible 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 succesfully
            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)

        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)

        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)

    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]

        if n.pdu_id == c.pdu_id and n.origin == c.origin:
            # 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 = self._do_conflict_res(new_branch, current_branch)
        defer.returnValue(result)

    def _do_conflict_res(self, new_branch, current_branch):
        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 = algo(new_branch, current_branch)

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

        raise Exception("Conflict resolution failed.")

    def _do_power_level_conflict_res(self, new_branch, current_branch):
        max_power_new = max(
            new_branch[:-1],
            key=lambda t: t.power_level
        ).power_level

        max_power_current = max(
            current_branch[:-1],
            key=lambda t: t.power_level
        ).power_level

        return (max_power_new, max_power_current)

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

    def _do_hash_conflict_res(self, new_branch, current_branch):
        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()
        )