Implement backfill over federation (#938)

* Implement history visibility checks for /backfill

Required for p2p to show history correctly.

* Add sytest

* Logging

* Fix two backfill bugs which prevented backfill from working correctly

- When receiving backfill requests, do not send the event that was in the original request.
- When storing backfill results, correctly update the backwards extremity for the room.

* hack: make backfill work multiple times

* add sqlite impl and remove logging

* Linting

2 files changed, 142 insertions, 17 deletions

diff --git a/roomserver/auth/auth.go b/roomserver/auth/auth.go
index 5ff1fada..615a94b3 100644
--- a/roomserver/auth/auth.go
+++ b/roomserver/auth/auth.go
@@ -12,18 +12,76 @@
 
 package auth
 
-import "github.com/matrix-org/gomatrixserverlib"
+import (
+	"encoding/json"
 
-// IsServerAllowed returns true if there exists a event in authEvents
-// which allows server to view this event. That is true when a client on the server
-// can view the event. Otherwise returns false.
+	"github.com/matrix-org/gomatrixserverlib"
+)
+
+// TODO: This logic should live in gomatrixserverlib
+
+// IsServerAllowed returns true if the server is allowed to see events in the room
+// at this particular state. This function implements https://matrix.org/docs/spec/client_server/r0.6.0#id87
 func IsServerAllowed(
 	serverName gomatrixserverlib.ServerName,
+	serverCurrentlyInRoom bool,
 	authEvents []gomatrixserverlib.Event,
 ) bool {
+	historyVisibility := historyVisibilityForRoom(authEvents)
+
+	// 1. If the history_visibility was set to world_readable, allow.
+	if historyVisibility == "world_readable" {
+		return true
+	}
+	// 2. If the user's membership was join, allow.
+	joinedUserExists := IsAnyUserOnServerWithMembership(serverName, authEvents, gomatrixserverlib.Join)
+	if joinedUserExists {
+		return true
+	}
+	// 3. If history_visibility was set to shared, and the user joined the room at any point after the event was sent, allow.
+	if historyVisibility == "shared" && serverCurrentlyInRoom {
+		return true
+	}
+	// 4. If the user's membership was invite, and the history_visibility was set to invited, allow.
+	invitedUserExists := IsAnyUserOnServerWithMembership(serverName, authEvents, gomatrixserverlib.Invite)
+	if invitedUserExists && historyVisibility == "invited" {
+		return true
+	}
+
+	// 5. Otherwise, deny.
+	return false
+}
+
+func historyVisibilityForRoom(authEvents []gomatrixserverlib.Event) string {
+	// https://matrix.org/docs/spec/client_server/r0.6.0#id87
+	// By default if no history_visibility is set, or if the value is not understood, the visibility is assumed to be shared.
+	visibility := "shared"
+	knownStates := []string{"invited", "joined", "shared", "world_readable"}
+	for _, ev := range authEvents {
+		if ev.Type() != gomatrixserverlib.MRoomHistoryVisibility {
+			continue
+		}
+		// TODO: This should be HistoryVisibilityContent to match things like 'MemberContent'. Do this when moving to GMSL
+		content := struct {
+			HistoryVisibility string `json:"history_visibility"`
+		}{}
+		if err := json.Unmarshal(ev.Content(), &content); err != nil {
+			break // value is not understood
+		}
+		for _, s := range knownStates {
+			if s == content.HistoryVisibility {
+				visibility = s
+				break
+			}
+		}
+	}
+	return visibility
+}
+
+func IsAnyUserOnServerWithMembership(serverName gomatrixserverlib.ServerName, authEvents []gomatrixserverlib.Event, wantMembership string) bool {
 	for _, ev := range authEvents {
 		membership, err := ev.Membership()
-		if err != nil || membership != gomatrixserverlib.Join {
+		if err != nil || membership != wantMembership {
 			continue
 		}
 
@@ -41,7 +99,5 @@ func IsServerAllowed(
 			return true
 		}
 	}
-
-	// TODO: Check if history visibility is shared and if the server is currently in the room
 	return false
 }
diff --git a/roomserver/query/query.go b/roomserver/query/query.go
index 2638919a..7fe9dc98 100644
--- a/roomserver/query/query.go
+++ b/roomserver/query/query.go
@@ -447,14 +447,26 @@ func (r *RoomserverQueryAPI) QueryServerAllowedToSeeEvent(
 	request *api.QueryServerAllowedToSeeEventRequest,
 	response *api.QueryServerAllowedToSeeEventResponse,
 ) (err error) {
+	events, err := r.DB.EventsFromIDs(ctx, []string{request.EventID})
+	if err != nil {
+		return
+	}
+	if len(events) == 0 {
+		response.AllowedToSeeEvent = false // event doesn't exist so not allowed to see
+		return
+	}
+	isServerInRoom, err := r.isServerCurrentlyInRoom(ctx, request.ServerName, events[0].RoomID())
+	if err != nil {
+		return
+	}
 	response.AllowedToSeeEvent, err = r.checkServerAllowedToSeeEvent(
-		ctx, request.EventID, request.ServerName,
+		ctx, request.EventID, request.ServerName, isServerInRoom,
 	)
 	return
 }
 
 func (r *RoomserverQueryAPI) checkServerAllowedToSeeEvent(
-	ctx context.Context, eventID string, serverName gomatrixserverlib.ServerName,
+	ctx context.Context, eventID string, serverName gomatrixserverlib.ServerName, isServerInRoom bool,
 ) (bool, error) {
 	roomState := state.NewStateResolution(r.DB)
 	stateEntries, err := roomState.LoadStateAtEvent(ctx, eventID)
@@ -469,7 +481,7 @@ func (r *RoomserverQueryAPI) checkServerAllowedToSeeEvent(
 		return false, err
 	}
 
-	return auth.IsServerAllowed(serverName, stateAtEvent), nil
+	return auth.IsServerAllowed(serverName, isServerInRoom, stateAtEvent), nil
 }
 
 // QueryMissingEvents implements api.RoomserverQueryAPI
@@ -564,17 +576,55 @@ func (r *RoomserverQueryAPI) QueryBackfill(
 	return err
 }
 
+func (r *RoomserverQueryAPI) isServerCurrentlyInRoom(ctx context.Context, serverName gomatrixserverlib.ServerName, roomID string) (bool, error) {
+	roomNID, err := r.DB.RoomNID(ctx, roomID)
+	if err != nil {
+		return false, err
+	}
+
+	eventNIDs, err := r.DB.GetMembershipEventNIDsForRoom(ctx, roomNID, true)
+	if err != nil {
+		return false, err
+	}
+
+	events, err := r.DB.Events(ctx, eventNIDs)
+	if err != nil {
+		return false, err
+	}
+	gmslEvents := make([]gomatrixserverlib.Event, len(events))
+	for i := range events {
+		gmslEvents[i] = events[i].Event
+	}
+	return auth.IsAnyUserOnServerWithMembership(serverName, gmslEvents, gomatrixserverlib.Join), nil
+}
+
+// TODO: Remove this when we have tests to assert correctness of this function
+// nolint:gocyclo
 func (r *RoomserverQueryAPI) scanEventTree(
 	ctx context.Context, front []string, visited map[string]bool, limit int,
 	serverName gomatrixserverlib.ServerName,
-) (resultNIDs []types.EventNID, err error) {
+) ([]types.EventNID, error) {
+	var resultNIDs []types.EventNID
+	var err error
 	var allowed bool
 	var events []types.Event
 	var next []string
 	var pre string
 
+	// TODO: add tests for this function to ensure it meets the contract that callers expect (and doc what that is supposed to be)
+	// Currently, callers like QueryBackfill will call scanEventTree with a pre-populated `visited` map, assuming that by doing
+	// so means that the events in that map will NOT be returned from this function. That is not currently true, resulting in
+	// duplicate events being sent in response to /backfill requests.
+	initialIgnoreList := make(map[string]bool, len(visited))
+	for k, v := range visited {
+		initialIgnoreList[k] = v
+	}
+
 	resultNIDs = make([]types.EventNID, 0, limit)
 
+	var checkedServerInRoom bool
+	var isServerInRoom bool
+
 	// Loop through the event IDs to retrieve the requested events and go
 	// through the whole tree (up to the provided limit) using the events'
 	// "prev_event" key.
@@ -587,7 +637,18 @@ BFSLoop:
 		// Retrieve the events to process from the database.
 		events, err = r.DB.EventsFromIDs(ctx, front)
 		if err != nil {
-			return
+			return resultNIDs, err
+		}
+
+		if !checkedServerInRoom && len(events) > 0 {
+			// It's nasty that we have to extract the room ID from an event, but many federation requests
+			// only talk in event IDs, no room IDs at all (!!!)
+			ev := events[0]
+			isServerInRoom, err = r.isServerCurrentlyInRoom(ctx, serverName, ev.RoomID())
+			if err != nil {
+				util.GetLogger(ctx).WithError(err).Error("Failed to check if server is currently in room, assuming not.")
+			}
+			checkedServerInRoom = true
 		}
 
 		for _, ev := range events {
@@ -595,17 +656,23 @@ BFSLoop:
 			if len(resultNIDs) == limit {
 				break BFSLoop
 			}
-			// Update the list of events to retrieve.
-			resultNIDs = append(resultNIDs, ev.EventNID)
+
+			if !initialIgnoreList[ev.EventID()] {
+				// Update the list of events to retrieve.
+				resultNIDs = append(resultNIDs, ev.EventNID)
+			}
 			// Loop through the event's parents.
 			for _, pre = range ev.PrevEventIDs() {
 				// Only add an event to the list of next events to process if it
 				// hasn't been seen before.
 				if !visited[pre] {
 					visited[pre] = true
-					allowed, err = r.checkServerAllowedToSeeEvent(ctx, pre, serverName)
+					allowed, err = r.checkServerAllowedToSeeEvent(ctx, pre, serverName, isServerInRoom)
 					if err != nil {
-						return
+						util.GetLogger(ctx).WithField("server", serverName).WithField("event_id", pre).WithError(err).Error(
+							"Error checking if allowed to see event",
+						)
+						return resultNIDs, err
 					}
 
 					// If the event hasn't been seen before and the HS
@@ -613,6 +680,8 @@ BFSLoop:
 					// the list of events to retrieve.
 					if allowed {
 						next = append(next, pre)
+					} else {
+						util.GetLogger(ctx).WithField("server", serverName).WithField("event_id", pre).Info("Not allowed to see event")
 					}
 				}
 			}
@@ -621,7 +690,7 @@ BFSLoop:
 		front = next
 	}
 
-	return
+	return resultNIDs, err
 }
 
 // QueryStateAndAuthChain implements api.RoomserverQueryAPI