Federation for v3/v4 rooms (#954)

* Update gomatrixserverlib

* Default to room version 4

* Update gomatrixserverlib

* Limit prev_events and auth_events

* Fix auth_events, prev_events

* Fix linter issues

* Update gomatrixserverlib

* Fix getState

* Update sytest-whitelist

* Squashed commit of the following:

commit 067b87506357c996fd6ddb11271db9469ad4ce80
Author: Neil Alexander <neilalexander@users.noreply.github.com>
Date:   Fri Apr 3 14:29:06 2020 +0100

    Invites v2 endpoint (#952)

    * Start converting v1 invite endpoint to v2

    * Update gomatrixserverlib

    * Early federationsender code for sending invites

    * Sending invites sorta happens now

    * Populate invite request with stripped state

    * Remodel a bit, don't reflect received invites

    * Handle invite_room_state

    * Handle room versions a bit better

    * Update gomatrixserverlib

    * Tweak order in destinationQueue.next

    * Revert check in processMessage

    * Tweak federation sender destination queue code a bit

    * Add comments

commit 955244c09298d0e6c870377dad3af2ffa1f5e578
Author: Ben B <benne@klimlive.de>
Date:   Fri Apr 3 12:40:50 2020 +0200

    use custom http client instead of the http DefaultClient (#823)

    This commit replaces the default client from the http lib with a custom one.
    The previously used default client doesn't come with a timeout. This could cause
    unwanted locks.
    That solution chosen here creates a http client in the base component dendrite
    with a constant timeout of 30 seconds. If it should be necessary to overwrite
    this, we could include the timeout in the dendrite configuration.
    Here it would be a good idea to extend the type "Address" by a timeout and
    create an http client for each service.

    Closes #820

    Signed-off-by: Benedikt Bongartz <benne@klimlive.de>

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

* Update sytest-whitelist, sytest-blacklist

* Update go.mod/go.sum

* Add some error wrapping for debug

* Add a NOTSPEC to common/events.go

* Perform state resolution at send_join

* Set default room version to v2 again

* Tweak GetCapabilities

* Add comments to ResolveConflictsAdhoc

* Update sytest-blacklist

* go mod tidy

* Update sytest-whitelist, sytest-blacklist

* Update versions

* Updates from review comments

* Update sytest-blacklist, sytest-whitelist

* Check room versions compatible at make_join, add some comments, update gomatrixserverlib, other tweaks

* Set default room version back to v2

* Update gomatrixserverlib, sytest-whitelist

4 files changed, 94 insertions, 7 deletions

diff --git a/roomserver/api/query.go b/roomserver/api/query.go
index 9120da4b..5f024d26 100644
--- a/roomserver/api/query.go
+++ b/roomserver/api/query.go
@@ -203,6 +203,9 @@ type QueryStateAndAuthChainRequest struct {
 	PrevEventIDs []string `json:"prev_event_ids"`
 	// The list of auth events for the event. Used to calculate the auth chain
 	AuthEventIDs []string `json:"auth_event_ids"`
+	// Should state resolution be ran on the result events?
+	// TODO: check call sites and remove if we always want to do state res
+	ResolveState bool `json:"resolve_state"`
 }
 
 // QueryStateAndAuthChainResponse is a response to QueryStateAndAuthChain
diff --git a/roomserver/query/query.go b/roomserver/query/query.go
index b7cdf150..7e05fe36 100644
--- a/roomserver/query/query.go
+++ b/roomserver/query/query.go
@@ -132,7 +132,7 @@ func (r *RoomserverQueryAPI) QueryLatestEventsAndState(
 		return err
 	}
 
-	// Look up the currrent state for the requested tuples.
+	// Look up the current state for the requested tuples.
 	stateEntries, err := roomState.LoadStateAtSnapshotForStringTuples(
 		ctx, currentStateSnapshotNID, request.StateToFetch,
 	)
@@ -736,6 +736,14 @@ func (r *RoomserverQueryAPI) QueryStateAndAuthChain(
 		return err
 	}
 
+	if request.ResolveState {
+		if stateEvents, err = state.ResolveConflictsAdhoc(
+			roomVersion, stateEvents, authEvents,
+		); err != nil {
+			return err
+		}
+	}
+
 	for _, event := range stateEvents {
 		response.StateEvents = append(response.StateEvents, event.Headered(roomVersion))
 	}
diff --git a/roomserver/state/state.go b/roomserver/state/state.go
index 94873dbe..3f68e074 100644
--- a/roomserver/state/state.go
+++ b/roomserver/state/state.go
@@ -18,7 +18,6 @@ package state
 
 import (
 	"context"
-	"errors"
 	"fmt"
 	"sort"
 	"time"
@@ -681,6 +680,83 @@ func (v StateResolution) calculateStateAfterManyEvents(
 	return
 }
 
+// ResolveConflictsAdhoc is a helper function to assist the query API in
+// performing state resolution when requested. This is a different code
+// path to the rest of state.go because this assumes you already have
+// gomatrixserverlib.Event objects and not just a bunch of NIDs like
+// elsewhere in the state resolution.
+// TODO: Some of this can possibly be deduplicated
+func ResolveConflictsAdhoc(
+	version gomatrixserverlib.RoomVersion,
+	events []gomatrixserverlib.Event,
+	authEvents []gomatrixserverlib.Event,
+) ([]gomatrixserverlib.Event, error) {
+	type stateKeyTuple struct {
+		Type     string
+		StateKey string
+	}
+
+	// Prepare our data structures.
+	eventMap := make(map[stateKeyTuple][]gomatrixserverlib.Event)
+	var conflicted, notConflicted, resolved []gomatrixserverlib.Event
+
+	// Run through all of the events that we were given and sort them
+	// into a map, sorted by (event_type, state_key) tuple. This means
+	// that we can easily spot events that are "conflicted", e.g.
+	// there are duplicate values for the same tuple key.
+	for _, event := range events {
+		if event.StateKey() == nil {
+			// Ignore events that are not state events.
+			continue
+		}
+		// Append the events if there is already a conflicted list for
+		// this tuple key, create it if not.
+		tuple := stateKeyTuple{event.Type(), *event.StateKey()}
+		if _, ok := eventMap[tuple]; ok {
+			eventMap[tuple] = append(eventMap[tuple], event)
+		} else {
+			eventMap[tuple] = []gomatrixserverlib.Event{event}
+		}
+	}
+
+	// Split out the events in the map into conflicted and unconflicted
+	// buckets. The conflicted events will be ran through state res,
+	// whereas unconfliced events will always going to appear in the
+	// final resolved state.
+	for _, list := range eventMap {
+		if len(list) > 1 {
+			conflicted = append(conflicted, list...)
+		} else {
+			notConflicted = append(notConflicted, list...)
+		}
+	}
+
+	// Work out which state resolution algorithm we want to run for
+	// the room version.
+	stateResAlgo, err := version.StateResAlgorithm()
+	if err != nil {
+		return nil, err
+	}
+	switch stateResAlgo {
+	case gomatrixserverlib.StateResV1:
+		// Currently state res v1 doesn't handle unconflicted events
+		// for us, like state res v2 does, so we will need to add the
+		// unconflicted events into the state ourselves.
+		// TODO: Fix state res v1 so this is handled for the caller.
+		resolved = gomatrixserverlib.ResolveStateConflicts(conflicted, authEvents)
+		resolved = append(resolved, notConflicted...)
+	case gomatrixserverlib.StateResV2:
+		// TODO: auth difference here?
+		resolved = gomatrixserverlib.ResolveStateConflictsV2(conflicted, notConflicted, authEvents, authEvents)
+	default:
+		return nil, fmt.Errorf("unsupported state resolution algorithm %v", stateResAlgo)
+	}
+
+	// Return the final resolved state events, including both the
+	// resolved set of conflicted events, and the unconflicted events.
+	return resolved, nil
+}
+
 func (v StateResolution) resolveConflicts(
 	ctx context.Context, version gomatrixserverlib.RoomVersion,
 	notConflicted, conflicted []types.StateEntry,
@@ -695,7 +771,7 @@ func (v StateResolution) resolveConflicts(
 	case gomatrixserverlib.StateResV2:
 		return v.resolveConflictsV2(ctx, notConflicted, conflicted)
 	}
-	return nil, errors.New("unsupported state resolution algorithm")
+	return nil, fmt.Errorf("unsupported state resolution algorithm %v", stateResAlgo)
 }
 
 // resolveConflicts resolves a list of conflicted state entries. It takes two lists.
diff --git a/roomserver/version/version.go b/roomserver/version/version.go
index ed16ecca..e60b5ef7 100644
--- a/roomserver/version/version.go
+++ b/roomserver/version/version.go
@@ -43,12 +43,12 @@ var roomVersions = map[gomatrixserverlib.RoomVersion]RoomVersionDescription{
 		Stable:    true,
 	},
 	gomatrixserverlib.RoomVersionV3: RoomVersionDescription{
-		Supported: false,
-		Stable:    false,
+		Supported: true,
+		Stable:    true,
 	},
 	gomatrixserverlib.RoomVersionV4: RoomVersionDescription{
-		Supported: false,
-		Stable:    false,
+		Supported: true,
+		Stable:    true,
 	},
 	gomatrixserverlib.RoomVersionV5: RoomVersionDescription{
 		Supported: false,