Handle state with input event as new events (#1415)

* SendEventWithState events as new

* Use cumulative state IDs for final event

* Error wrapping in calculateAndSetState

* Handle overwriting same event type and state key

* Hacky way to spot historical events

* Don't exclude from sync

* Don't generate output events when rewriting forward extremities

* Update output event check

* Historical output events

* Define output room event type

* Notify key changes on state

* Don't send our membership event twice

* Deduplicate state entries

* Tweaks

* Remove unnecessary nolint

* Fix current state upsert in sync API

* Send auth events as outliers, state events as rewrite

* Sync API don't consume state events

* Process events actually

* Improve outlier check

* Fix local room check

* Remove extra room check, it seems to break the whole damn world

* Fix federated join check

* Fix nil pointer exception

* Better comments on DeduplicateStateEntries

* Reflow forced federated joins

* Don't force federated join for possibly even local invites

* Comment SendEventWithState better

* Rewrite room state in sync API storage

* Add TODO

* Clean up all room data when receiving create event

* Don't generate output events for rewrites, but instead notify that state is rewritten on the final new event

* Rename to PurgeRoom

* Exclude backfilled messages from /sync

* Split out rewriting state from updating state from state res

Co-authored-by: Kegan Dougal <kegan@matrix.org>

3 files changed, 119 insertions, 0 deletions

diff --git a/roomserver/api/input.go b/roomserver/api/input.go
index 73c4994a..651c0e9f 100644
--- a/roomserver/api/input.go
+++ b/roomserver/api/input.go
@@ -33,6 +33,10 @@ const (
 	// KindBackfill event extend the contiguous graph going backwards.
 	// They always have state.
 	KindBackfill = 3
+	// KindRewrite events are used when rewriting the head of the room
+	// graph with entirely new state. The output events generated will
+	// be state events rather than timeline events.
+	KindRewrite = 4
 )
 
 // DoNotSendToOtherServers tells us not to send the event to other matrix
diff --git a/roomserver/api/output.go b/roomserver/api/output.go
index 013ebdc8..d57f3b04 100644
--- a/roomserver/api/output.go
+++ b/roomserver/api/output.go
@@ -68,6 +68,17 @@ type OutputEvent struct {
 	NewPeek *OutputNewPeek `json:"new_peek,omitempty"`
 }
 
+// Type of the OutputNewRoomEvent.
+type OutputRoomEventType int
+
+const (
+	// The event is a timeline event and likely just happened.
+	OutputRoomTimeline OutputRoomEventType = iota
+
+	// The event is a state event and quite possibly happened in the past.
+	OutputRoomState
+)
+
 // An OutputNewRoomEvent is written when the roomserver receives a new event.
 // It contains the full matrix room event and enough information for a
 // consumer to construct the current state of the room and the state before the
@@ -80,6 +91,9 @@ type OutputEvent struct {
 type OutputNewRoomEvent struct {
 	// The Event.
 	Event gomatrixserverlib.HeaderedEvent `json:"event"`
+	// Does the event completely rewrite the room state? If so, then AddsStateEventIDs
+	// will contain the entire room state.
+	RewritesState bool `json:"rewrites_state"`
 	// The latest events in the room after this event.
 	// This can be used to set the prev events for new events in the room.
 	// This also can be used to get the full current state after this event.
diff --git a/roomserver/api/wrapper.go b/roomserver/api/wrapper.go
index 82a4a571..e5339311 100644
--- a/roomserver/api/wrapper.go
+++ b/roomserver/api/wrapper.go
@@ -80,6 +80,107 @@ func SendEventWithState(
 	return SendInputRoomEvents(ctx, rsAPI, ires)
 }
 
+// SendEventWithRewrite writes an event with KindNew to the roomserver along
+// with a number of rewrite and outlier events for state and auth events
+// respectively.
+func SendEventWithRewrite(
+	ctx context.Context, rsAPI RoomserverInternalAPI, state *gomatrixserverlib.RespState,
+	event gomatrixserverlib.HeaderedEvent, haveEventIDs map[string]bool,
+) error {
+	isCurrentState := map[string]struct{}{}
+	for _, se := range state.StateEvents {
+		isCurrentState[se.EventID()] = struct{}{}
+	}
+
+	authAndStateEvents, err := state.Events()
+	if err != nil {
+		return err
+	}
+
+	var ires []InputRoomEvent
+	var stateIDs []string
+
+	// This function generates three things:
+	// A - A set of "rewrite" events, which will form the newly rewritten
+	//     state before the event, which includes every rewrite event that
+	//     came before it in its state
+	// B - A set of "outlier" events, which are auth events but not part
+	//     of the rewritten state
+	// C - A "new" event, which include all of the rewrite events in its
+	//     state
+	for _, authOrStateEvent := range authAndStateEvents {
+		if authOrStateEvent.StateKey() == nil {
+			continue
+		}
+		if haveEventIDs[authOrStateEvent.EventID()] {
+			continue
+		}
+		if event.StateKey() == nil {
+			continue
+		}
+
+		// We will handle an event as if it's an outlier if one of the
+		// following conditions is true:
+		storeAsOutlier := false
+		if authOrStateEvent.Type() == event.Type() && *authOrStateEvent.StateKey() == *event.StateKey() {
+			// The event is a state event but the input event is going to
+			// replace it, therefore it can't be added to the state or we'll
+			// get duplicate state keys in the state block. We'll send it
+			// as an outlier because we don't know if something will be
+			// referring to it as an auth event, but need it to be stored
+			// just in case.
+			storeAsOutlier = true
+		} else if _, ok := isCurrentState[authOrStateEvent.EventID()]; !ok {
+			// The event is an auth event and isn't a part of the state set.
+			// We'll send it as an outlier because we need it to be stored
+			// in case something is referring to it as an auth event.
+			storeAsOutlier = true
+		}
+
+		if storeAsOutlier {
+			ires = append(ires, InputRoomEvent{
+				Kind:         KindOutlier,
+				Event:        authOrStateEvent.Headered(event.RoomVersion),
+				AuthEventIDs: authOrStateEvent.AuthEventIDs(),
+			})
+			continue
+		}
+
+		// If the event isn't an outlier then we'll instead send it as a
+		// rewrite event, so that it'll form part of the rewritten state.
+		// These events will go through the membership and latest event
+		// updaters and we will generate output events, but they will be
+		// flagged as non-current (i.e. didn't just happen) events.
+		// Each of these rewrite events includes all of the rewrite events
+		// that came before in their StateEventIDs.
+		ires = append(ires, InputRoomEvent{
+			Kind:          KindRewrite,
+			Event:         authOrStateEvent.Headered(event.RoomVersion),
+			AuthEventIDs:  authOrStateEvent.AuthEventIDs(),
+			HasState:      true,
+			StateEventIDs: stateIDs,
+		})
+
+		// Add the event ID into the StateEventIDs of all subsequent
+		// rewrite events, and the new event.
+		stateIDs = append(stateIDs, authOrStateEvent.EventID())
+	}
+
+	// Send the final event as a new event, which will generate
+	// a timeline output event for it. All of the rewrite events
+	// that came before will be sent as StateEventIDs, forming a
+	// new clean state before the event.
+	ires = append(ires, InputRoomEvent{
+		Kind:          KindNew,
+		Event:         event,
+		AuthEventIDs:  event.AuthEventIDs(),
+		HasState:      true,
+		StateEventIDs: stateIDs,
+	})
+
+	return SendInputRoomEvents(ctx, rsAPI, ires)
+}
+
 // SendInputRoomEvents to the roomserver.
 func SendInputRoomEvents(
 	ctx context.Context, rsAPI RoomserverInternalAPI, ires []InputRoomEvent,