1 ################################################################ 2 # The core state machine 3 ################################################################ 4 # 5 # Rule 1: everything that affects the state machine and state transitions must 6 # live here in this file. As much as possible goes into the table-based 7 # representation, but for the bits that don't quite fit, the actual code and 8 # state must nonetheless live here. 9 # 10 # Rule 2: this file does not know about what role we're playing; it only knows 11 # about HTTP request/response cycles in the abstract. This ensures that we 12 # don't cheat and apply different rules to local and remote parties. 13 # 14 # 15 # Theory of operation 16 # =================== 17 # 18 # Possibly the simplest way to think about this is that we actually have 5 19 # different state machines here. Yes, 5. These are: 20 # 21 # 1) The client state, with its complicated automaton (see the docs) 22 # 2) The server state, with its complicated automaton (see the docs) 23 # 3) The keep-alive state, with possible states {True, False} 24 # 4) The SWITCH_CONNECT state, with possible states {False, True} 25 # 5) The SWITCH_UPGRADE state, with possible states {False, True} 26 # 27 # For (3)-(5), the first state listed is the initial state. 28 # 29 # (1)-(3) are stored explicitly in member variables. The last 30 # two are stored implicitly in the pending_switch_proposals set as: 31 # (state of 4) == (_SWITCH_CONNECT in pending_switch_proposals) 32 # (state of 5) == (_SWITCH_UPGRADE in pending_switch_proposals) 33 # 34 # And each of these machines has two different kinds of transitions: 35 # 36 # a) Event-triggered 37 # b) State-triggered 38 # 39 # Event triggered is the obvious thing that you'd think it is: some event 40 # happens, and if it's the right event at the right time then a transition 41 # happens. But there are somewhat complicated rules for which machines can 42 # "see" which events. (As a rule of thumb, if a machine "sees" an event, this 43 # means two things: the event can affect the machine, and if the machine is 44 # not in a state where it expects that event then it's an error.) These rules 45 # are: 46 # 47 # 1) The client machine sees all h11.events objects emitted by the client. 48 # 49 # 2) The server machine sees all h11.events objects emitted by the server. 50 # 51 # It also sees the client's Request event. 52 # 53 # And sometimes, server events are annotated with a _SWITCH_* event. For 54 # example, we can have a (Response, _SWITCH_CONNECT) event, which is 55 # different from a regular Response event. 56 # 57 # 3) The keep-alive machine sees the process_keep_alive_disabled() event 58 # (which is derived from Request/Response events), and this event 59 # transitions it from True -> False, or from False -> False. There's no way 60 # to transition back. 61 # 62 # 4&5) The _SWITCH_* machines transition from False->True when we get a 63 # Request that proposes the relevant type of switch (via 64 # process_client_switch_proposals), and they go from True->False when we 65 # get a Response that has no _SWITCH_* annotation. 66 # 67 # So that's event-triggered transitions. 68 # 69 # State-triggered transitions are less standard. What they do here is couple 70 # the machines together. The way this works is, when certain *joint* 71 # configurations of states are achieved, then we automatically transition to a 72 # new *joint* state. So, for example, if we're ever in a joint state with 73 # 74 # client: DONE 75 # keep-alive: False 76 # 77 # then the client state immediately transitions to: 78 # 79 # client: MUST_CLOSE 80 # 81 # This is fundamentally different from an event-based transition, because it 82 # doesn't matter how we arrived at the {client: DONE, keep-alive: False} state 83 # -- maybe the client transitioned SEND_BODY -> DONE, or keep-alive 84 # transitioned True -> False. Either way, once this precondition is satisfied, 85 # this transition is immediately triggered. 86 # 87 # What if two conflicting state-based transitions get enabled at the same 88 # time? In practice there's only one case where this arises (client DONE -> 89 # MIGHT_SWITCH_PROTOCOL versus DONE -> MUST_CLOSE), and we resolve it by 90 # explicitly prioritizing the DONE -> MIGHT_SWITCH_PROTOCOL transition. 91 # 92 # Implementation 93 # -------------- 94 # 95 # The event-triggered transitions for the server and client machines are all 96 # stored explicitly in a table. Ditto for the state-triggered transitions that 97 # involve just the server and client state. 98 # 99 # The transitions for the other machines, and the state-triggered transitions 100 # that involve the other machines, are written out as explicit Python code. 101 # 102 # It'd be nice if there were some cleaner way to do all this. This isn't 103 # *too* terrible, but I feel like it could probably be better. 104 # 105 # WARNING 106 # ------- 107 # 108 # The script that generates the state machine diagrams for the docs knows how 109 # to read out the EVENT_TRIGGERED_TRANSITIONS and STATE_TRIGGERED_TRANSITIONS 110 # tables. But it can't automatically read the transitions that are written 111 # directly in Python code. So if you touch those, you need to also update the 112 # script to keep it in sync! 113 from typing import cast, Dict, Optional, Set, Tuple, Type, Union 114 115 from ._events import * 116 from ._util import LocalProtocolError, Sentinel 117 118 # Everything in __all__ gets re-exported as part of the h11 public API. 119 __all__ = [ 120 "CLIENT", 121 "SERVER", 122 "IDLE", 123 "SEND_RESPONSE", 124 "SEND_BODY", 125 "DONE", 126 "MUST_CLOSE", 127 "CLOSED", 128 "MIGHT_SWITCH_PROTOCOL", 129 "SWITCHED_PROTOCOL", 130 "ERROR", 131 ] 132 133 134 class CLIENT(Sentinel, metaclass=Sentinel): 135 pass 136 137 138 class SERVER(Sentinel, metaclass=Sentinel): 139 pass 140 141 142 # States 143 class IDLE(Sentinel, metaclass=Sentinel): 144 pass 145 146 147 class SEND_RESPONSE(Sentinel, metaclass=Sentinel): 148 pass 149 150 151 class SEND_BODY(Sentinel, metaclass=Sentinel): 152 pass 153 154 155 class DONE(Sentinel, metaclass=Sentinel): 156 pass 157 158 159 class MUST_CLOSE(Sentinel, metaclass=Sentinel): 160 pass 161 162 163 class CLOSED(Sentinel, metaclass=Sentinel): 164 pass 165 166 167 class ERROR(Sentinel, metaclass=Sentinel): 168 pass 169 170 171 # Switch types 172 class MIGHT_SWITCH_PROTOCOL(Sentinel, metaclass=Sentinel): 173 pass 174 175 176 class SWITCHED_PROTOCOL(Sentinel, metaclass=Sentinel): 177 pass 178 179 180 class _SWITCH_UPGRADE(Sentinel, metaclass=Sentinel): 181 pass 182 183 184 class _SWITCH_CONNECT(Sentinel, metaclass=Sentinel): 185 pass 186 187 188 EventTransitionType = Dict[ 189 Type[Sentinel], 190 Dict[ 191 Type[Sentinel], 192 Dict[Union[Type[Event], Tuple[Type[Event], Type[Sentinel]]], Type[Sentinel]], 193 ], 194 ] 195 196 EVENT_TRIGGERED_TRANSITIONS: EventTransitionType = { 197 CLIENT: { 198 IDLE: {Request: SEND_BODY, ConnectionClosed: CLOSED}, 199 SEND_BODY: {Data: SEND_BODY, EndOfMessage: DONE}, 200 DONE: {ConnectionClosed: CLOSED}, 201 MUST_CLOSE: {ConnectionClosed: CLOSED}, 202 CLOSED: {ConnectionClosed: CLOSED}, 203 MIGHT_SWITCH_PROTOCOL: {}, 204 SWITCHED_PROTOCOL: {}, 205 ERROR: {}, 206 }, 207 SERVER: { 208 IDLE: { 209 ConnectionClosed: CLOSED, 210 Response: SEND_BODY, 211 # Special case: server sees client Request events, in this form 212 (Request, CLIENT): SEND_RESPONSE, 213 }, 214 SEND_RESPONSE: { 215 InformationalResponse: SEND_RESPONSE, 216 Response: SEND_BODY, 217 (InformationalResponse, _SWITCH_UPGRADE): SWITCHED_PROTOCOL, 218 (Response, _SWITCH_CONNECT): SWITCHED_PROTOCOL, 219 }, 220 SEND_BODY: {Data: SEND_BODY, EndOfMessage: DONE}, 221 DONE: {ConnectionClosed: CLOSED}, 222 MUST_CLOSE: {ConnectionClosed: CLOSED}, 223 CLOSED: {ConnectionClosed: CLOSED}, 224 SWITCHED_PROTOCOL: {}, 225 ERROR: {}, 226 }, 227 } 228 229 StateTransitionType = Dict[ 230 Tuple[Type[Sentinel], Type[Sentinel]], Dict[Type[Sentinel], Type[Sentinel]] 231 ] 232 233 # NB: there are also some special-case state-triggered transitions hard-coded 234 # into _fire_state_triggered_transitions below. 235 STATE_TRIGGERED_TRANSITIONS: StateTransitionType = { 236 # (Client state, Server state) -> new states 237 # Protocol negotiation 238 (MIGHT_SWITCH_PROTOCOL, SWITCHED_PROTOCOL): {CLIENT: SWITCHED_PROTOCOL}, 239 # Socket shutdown 240 (CLOSED, DONE): {SERVER: MUST_CLOSE}, 241 (CLOSED, IDLE): {SERVER: MUST_CLOSE}, 242 (ERROR, DONE): {SERVER: MUST_CLOSE}, 243 (DONE, CLOSED): {CLIENT: MUST_CLOSE}, 244 (IDLE, CLOSED): {CLIENT: MUST_CLOSE}, 245 (DONE, ERROR): {CLIENT: MUST_CLOSE}, 246 } 247 248 249 class ConnectionState: 250 def __init__(self) -> None: 251 # Extra bits of state that don't quite fit into the state model. 252 253 # If this is False then it enables the automatic DONE -> MUST_CLOSE 254 # transition. Don't set this directly; call .keep_alive_disabled() 255 self.keep_alive = True 256 257 # This is a subset of {UPGRADE, CONNECT}, containing the proposals 258 # made by the client for switching protocols. 259 self.pending_switch_proposals: Set[Type[Sentinel]] = set() 260 261 self.states: Dict[Type[Sentinel], Type[Sentinel]] = {CLIENT: IDLE, SERVER: IDLE} 262 263 def process_error(self, role: Type[Sentinel]) -> None: 264 self.states[role] = ERROR 265 self._fire_state_triggered_transitions() 266 267 def process_keep_alive_disabled(self) -> None: 268 self.keep_alive = False 269 self._fire_state_triggered_transitions() 270 271 def process_client_switch_proposal(self, switch_event: Type[Sentinel]) -> None: 272 self.pending_switch_proposals.add(switch_event) 273 self._fire_state_triggered_transitions() 274 275 def process_event( 276 self, 277 role: Type[Sentinel], 278 event_type: Type[Event], 279 server_switch_event: Optional[Type[Sentinel]] = None, 280 ) -> None: 281 _event_type: Union[Type[Event], Tuple[Type[Event], Type[Sentinel]]] = event_type 282 if server_switch_event is not None: 283 assert role is SERVER 284 if server_switch_event not in self.pending_switch_proposals: 285 raise LocalProtocolError( 286 "Received server {} event without a pending proposal".format( 287 server_switch_event 288 ) 289 ) 290 _event_type = (event_type, server_switch_event) 291 if server_switch_event is None and _event_type is Response: 292 self.pending_switch_proposals = set() 293 self._fire_event_triggered_transitions(role, _event_type) 294 # Special case: the server state does get to see Request 295 # events. 296 if _event_type is Request: 297 assert role is CLIENT 298 self._fire_event_triggered_transitions(SERVER, (Request, CLIENT)) 299 self._fire_state_triggered_transitions() 300 301 def _fire_event_triggered_transitions( 302 self, 303 role: Type[Sentinel], 304 event_type: Union[Type[Event], Tuple[Type[Event], Type[Sentinel]]], 305 ) -> None: 306 state = self.states[role] 307 try: 308 new_state = EVENT_TRIGGERED_TRANSITIONS[role][state][event_type] 309 except KeyError: 310 event_type = cast(Type[Event], event_type) 311 raise LocalProtocolError( 312 "can't handle event type {} when role={} and state={}".format( 313 event_type.__name__, role, self.states[role] 314 ) 315 ) from None 316 self.states[role] = new_state 317 318 def _fire_state_triggered_transitions(self) -> None: 319 # We apply these rules repeatedly until converging on a fixed point 320 while True: 321 start_states = dict(self.states) 322 323 # It could happen that both these special-case transitions are 324 # enabled at the same time: 325 # 326 # DONE -> MIGHT_SWITCH_PROTOCOL 327 # DONE -> MUST_CLOSE 328 # 329 # For example, this will always be true of a HTTP/1.0 client 330 # requesting CONNECT. If this happens, the protocol switch takes 331 # priority. From there the client will either go to 332 # SWITCHED_PROTOCOL, in which case it's none of our business when 333 # they close the connection, or else the server will deny the 334 # request, in which case the client will go back to DONE and then 335 # from there to MUST_CLOSE. 336 if self.pending_switch_proposals: 337 if self.states[CLIENT] is DONE: 338 self.states[CLIENT] = MIGHT_SWITCH_PROTOCOL 339 340 if not self.pending_switch_proposals: 341 if self.states[CLIENT] is MIGHT_SWITCH_PROTOCOL: 342 self.states[CLIENT] = DONE 343 344 if not self.keep_alive: 345 for role in (CLIENT, SERVER): 346 if self.states[role] is DONE: 347 self.states[role] = MUST_CLOSE 348 349 # Tabular state-triggered transitions 350 joint_state = (self.states[CLIENT], self.states[SERVER]) 351 changes = STATE_TRIGGERED_TRANSITIONS.get(joint_state, {}) 352 self.states.update(changes) 353 354 if self.states == start_states: 355 # Fixed point reached 356 return 357 358 def start_next_cycle(self) -> None: 359 if self.states != {CLIENT: DONE, SERVER: DONE}: 360 raise LocalProtocolError( 361 "not in a reusable state. self.states={}".format(self.states) 362 ) 363 # Can't reach DONE/DONE with any of these active, but still, let's be 364 # sure. 365 assert self.keep_alive 366 assert not self.pending_switch_proposals 367 self.states = {CLIENT: IDLE, SERVER: IDLE} 368