Use topological ordering for /messages response (#966)

* Use topological ordering for /messages response

* Update gomatrixserverlib

3 files changed, 8 insertions, 23 deletions

diff --git a/go.mod b/go.mod
index ec8f3eb6..20235ae3 100644
--- a/go.mod
+++ b/go.mod
@@ -17,7 +17,7 @@ require (
 	github.com/matrix-org/go-http-js-libp2p v0.0.0-20200318135427-31631a9ef51f
 	github.com/matrix-org/go-sqlite3-js v0.0.0-20200325174927-327088cdef10
 	github.com/matrix-org/gomatrix v0.0.0-20190528120928-7df988a63f26
-	github.com/matrix-org/gomatrixserverlib v0.0.0-20200409140603-8b9a51fe9b89
+	github.com/matrix-org/gomatrixserverlib v0.0.0-20200415145257-d492cd4be836
 	github.com/matrix-org/naffka v0.0.0-20200127221512-0716baaabaf1
 	github.com/matrix-org/util v0.0.0-20190711121626-527ce5ddefc7
 	github.com/mattn/go-sqlite3 v2.0.3+incompatible
diff --git a/go.sum b/go.sum
index 0d03cd37..5b4579bb 100644
--- a/go.sum
+++ b/go.sum
@@ -362,8 +362,8 @@ github.com/matrix-org/gomatrix v0.0.0-20190528120928-7df988a63f26 h1:Hr3zjRsq2bh
 github.com/matrix-org/gomatrix v0.0.0-20190528120928-7df988a63f26/go.mod h1:3fxX6gUjWyI/2Bt7J1OLhpCzOfO/bB3AiX0cJtEKud0=
 github.com/matrix-org/gomatrixserverlib v0.0.0-20200124100636-0c2ec91d1df5 h1:kmRjpmFOenVpOaV/DRlo9p6z/IbOKlUC+hhKsAAh8Qg=
 github.com/matrix-org/gomatrixserverlib v0.0.0-20200124100636-0c2ec91d1df5/go.mod h1:FsKa2pWE/bpQql9H7U4boOPXFoJX/QcqaZZ6ijLkaZI=
-github.com/matrix-org/gomatrixserverlib v0.0.0-20200409140603-8b9a51fe9b89 h1:YAlUJK/Ty2ZrP/DL41CiR0Cp3pteshnyIS420KVs220=
-github.com/matrix-org/gomatrixserverlib v0.0.0-20200409140603-8b9a51fe9b89/go.mod h1:FsKa2pWE/bpQql9H7U4boOPXFoJX/QcqaZZ6ijLkaZI=
+github.com/matrix-org/gomatrixserverlib v0.0.0-20200415145257-d492cd4be836 h1:YiXBJ/0ZeBzuh9Ym0iYaJgDBlFdz7nIVKArqkkEgPzM=
+github.com/matrix-org/gomatrixserverlib v0.0.0-20200415145257-d492cd4be836/go.mod h1:FsKa2pWE/bpQql9H7U4boOPXFoJX/QcqaZZ6ijLkaZI=
 github.com/matrix-org/naffka v0.0.0-20200127221512-0716baaabaf1 h1:osLoFdOy+ChQqVUn2PeTDETFftVkl4w9t/OW18g3lnk=
 github.com/matrix-org/naffka v0.0.0-20200127221512-0716baaabaf1/go.mod h1:cXoYQIENbdWIQHt1SyCo6Bl3C3raHwJ0wgVrXHSqf+A=
 github.com/matrix-org/util v0.0.0-20171127121716-2e2df66af2f5 h1:W7l5CP4V7wPyPb4tYE11dbmeAOwtFQBTW0rf4OonOS8=
diff --git a/syncapi/routing/messages.go b/syncapi/routing/messages.go
index c9d62477..873ee936 100644
--- a/syncapi/routing/messages.go
+++ b/syncapi/routing/messages.go
@@ -209,18 +209,12 @@ func (r *messagesReq) retrieveEvents() (
 		return []gomatrixserverlib.ClientEvent{}, r.from, r.to, nil
 	}
 
-	// Sort the events to ensure we send them in the right order. We currently
-	// do that based on the event's timestamp.
+	// Sort the events to ensure we send them in the right order.
+	events = gomatrixserverlib.HeaderedReverseTopologicalOrdering(events)
 	if r.backwardOrdering {
-		sort.SliceStable(events, func(i int, j int) bool {
-			// Backward ordering is antichronological (latest event to oldest
-			// one).
-			return sortEvents(&(events[j]), &(events[i]))
-		})
-	} else {
-		sort.SliceStable(events, func(i int, j int) bool {
-			// Forward ordering is chronological (oldest event to latest one).
-			return sortEvents(&(events[i]), &(events[j]))
+		// This reverses the array from old->new to new->old
+		sort.SliceStable(events, func(i, j int) bool {
+			return true
 		})
 	}
 
@@ -493,12 +487,3 @@ func setToDefault(
 
 	return
 }
-
-// sortEvents is a function to give to sort.SliceStable, and compares the
-// timestamp of two Matrix events.
-// Returns true if the first event happened before the second one, false
-// otherwise.
-func sortEvents(e1 *gomatrixserverlib.HeaderedEvent, e2 *gomatrixserverlib.HeaderedEvent) bool {
-	t := e1.OriginServerTS().Time()
-	return e2.OriginServerTS().Time().After(t)
-}