// Copyright 2020 The Matrix.org Foundation C.I.C.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package gomatrixserverlib

import (
	"encoding/json"
	"fmt"
	"slices"

	sets "github.com/hashicorp/go-set/v3"
	"github.com/matrix-org/gomatrixserverlib/spec"
	"github.com/oleiade/lane/v2"
)

// TopologicalOrder represents how to sort a list of events, used primarily in ReverseTopologicalOrdering
type TopologicalOrder int

// Sort events by prev_events or auth_events
const (
	TopologicalOrderByPrevEvents TopologicalOrder = iota + 1
	TopologicalOrderByAuthEvents
)

type stateResolverV2 struct {
	allower                   *allowerContext               // Used to auth and apply events
	authProvider              *AuthEvents                   // Used in the allower
	authEventMap              map[string]PDU                // Map of all provided auth events
	conflictedEventMap        map[string]PDU                // Map of all provided conflicted events
	powerLevelContents        map[string]*PowerLevelContent // A cache of all power level contents
	powerLevelMainlinePos     map[string]int                // Power level event positions in mainline
	resolvedCreate            PDU                           // Resolved create event
	resolvedPowerLevels       PDU                           // Resolved power level event
	resolvedJoinRules         PDU                           // Resolved join rules event
	resolvedThirdPartyInvites map[string]PDU                // Resolved third party invite events
	resolvedMembers           map[spec.SenderID]PDU         // Resolved member events
	resolvedOthers            map[StateKeyTuple]PDU         // Resolved other events
	result                    []PDU                         // Final list of resolved events
	isRejectedFn              IsRejected                    // Check if the given eventID is rejected
	isRejectedCache           map[string]bool               // Events known to be or not be rejected
}

// IsRejected should return if the given eventID is rejected or not.
type IsRejected func(eventID string) bool

// ResolveStateConflicts takes a list of state events with conflicting state
// keys and works out which event should be used for each state event. This
// function returns the resolved state, including unconflicted state events.
//
// DEPRECATED: This function does not accurately determine which events are conflicted.
// Use ResolveStateConflictsV2New instead.
func ResolveStateConflictsV2(
	conflicted, unconflicted,
	authEvents []PDU,
	userIDForSender spec.UserIDForSender,
	isRejectedFn IsRejected,
) []PDU {
	var createEvent PDU
	for _, ev := range authEvents {
		if ev.Type() == spec.MRoomCreate && ev.StateKeyEquals("") {
			createEvent = ev
			break
		}
	}
	if createEvent == nil {
		// FIXME TODO: We previously panicked here but this meant Dendrite would crash on startup.
		// We really need to get our error handling sorted properly when doing state resolution..
		// See https://github.com/element-hq/dendrite/issues/3629
		return nil // we should return an error here :/
	}
	// Prepare the state resolver.
	conflictedControlEvents := make([]PDU, 0, len(conflicted))
	conflictedOthers := make([]PDU, 0, len(conflicted))
	authProvider, _ := NewAuthEvents(nil)
	r := stateResolverV2{
		authEventMap:              eventMapFromEvents(authEvents),
		authProvider:              authProvider,
		conflictedEventMap:        eventMapFromEvents(conflicted),
		powerLevelContents:        make(map[string]*PowerLevelContent),
		powerLevelMainlinePos:     make(map[string]int),
		resolvedThirdPartyInvites: make(map[string]PDU, len(conflicted)),
		resolvedMembers:           make(map[spec.SenderID]PDU, len(conflicted)),
		resolvedOthers:            make(map[StateKeyTuple]PDU, len(conflicted)),
		result:                    make([]PDU, 0, len(conflicted)+len(unconflicted)),
		isRejectedFn:              isRejectedFn,
		isRejectedCache:           make(map[string]bool),
	}
	var roomID *spec.RoomID
	if len(conflicted) > 0 {
		validRoomID := conflicted[0].RoomID()
		roomID = &validRoomID
	}
	if len(unconflicted) > 0 {
		validRoomID := unconflicted[0].RoomID()
		roomID = &validRoomID
	}
	if len(authEvents) > 0 {
		validRoomID := authEvents[0].RoomID()
		roomID = &validRoomID
	}
	// If we still don't have a roomID, we don't have conflicted, unconflicted
	// or any authEvents, which in theory shouldn't happen.
	if roomID == nil {
		return r.result
	}

	r.allower = newAllowerContext(r.authProvider, userIDForSender, *roomID)

	// This is a map to help us determine if an event already belongs to the
	// unconflicted set. If it does then we shouldn't add it back into the
	// conflicted set later.
	isUnconflicted := make(map[string]struct{}, len(unconflicted))
	for _, u := range unconflicted {
		isUnconflicted[u.EventID()] = struct{}{}
	}

	// Get the full conflicted set, that is the conflicted events and the
	// auth difference (events that don't appear in all auth chains).
	fullConflictedSet := append(conflicted, r.calculateAuthDifference()...)

	// The full power set function returns the event and all of its auth
	// events that also happen to appear in the conflicted set. This will
	// effectively allow us to pull in all related events for any control
	// event, even if those related events are themselves not control events.
	visited := make(map[string]struct{}, len(conflicted)+len(authEvents))
	var fullControlSet func(event PDU) []PDU
	fullControlSet = func(event PDU) []PDU {
		events := []PDU{event}
		for _, authEventID := range event.AuthEventIDs() {
			if _, ok := visited[authEventID]; ok {
				continue
			}
			if event, ok := r.conflictedEventMap[authEventID]; ok {
				events = append(events, fullControlSet(event)...)
			}
			visited[authEventID] = struct{}{}
		}
		return events
	}

	// First of all, work through the full conflicted set. Ignoring any
	// events which are unconflicted (from the auth difference, for example),
	// pull in the control events and any events directly related to them.
	conflictedPulledIn := make(map[string]struct{}, len(conflicted)+len(authEvents))
	for _, p := range fullConflictedSet {
		if _, unconflicted := isUnconflicted[p.EventID()]; unconflicted {
			continue
		}
		if isControlEvent(p) {
			relatedEvents := fullControlSet(p)
			for _, event := range relatedEvents {
				conflictedPulledIn[event.EventID()] = struct{}{}
			}
			conflictedControlEvents = append(conflictedControlEvents, relatedEvents...)
		}
	}

	// Then work through the set again, this time looking for any events
	// that were left over from the last loop — that is, events that are
	// either not control events or weren't pulled in to the control set.
	for _, p := range fullConflictedSet {
		eventID := p.EventID()
		if _, unconflicted := isUnconflicted[eventID]; unconflicted || isControlEvent(p) {
			continue
		}
		if _, ok := conflictedPulledIn[eventID]; !ok {
			conflictedOthers = append(conflictedOthers, p)
		}
	}

	// Then process the unconflicted events by authing them.
	// The successfully authed events will form the real initial partial
	// state. We will then keep the successfully authed unconflicted events so that
	// they can be reapplied later.
	r.applyEvents(unconflicted...)

	// Then order the conflicted power level events topologically and then also
	// auth those too. The successfully authed events will be layered on top of
	// the partial state.
	conflictedControlEvents = r.reverseTopologicalOrdering(conflictedControlEvents, TopologicalOrderByAuthEvents)
	r.authAndApplyEvents(conflictedControlEvents...)

	// Then generate the mainline of power level events, order the remaining state
	// events based on the mainline ordering and auth those too. The successfully
	// authed events are also layered on top of the partial state.
	for pos, event := range r.createPowerLevelMainline() {
		r.powerLevelMainlinePos[event.EventID()] = pos
	}
	conflictedOthers = r.mainlineOrdering(conflictedOthers)
	r.authAndApplyEvents(conflictedOthers...)

	// Finally we will reapply the original set of unconflicted events onto the
	// partial state, just in case any of these were overwritten by pulling in
	// auth events in the previous two steps, and that gives us our final resolved
	// state.
	r.applyEvents(unconflicted...)

	// Now that we have our final state, populate the result array with the
	// resolved state and return it.
	if r.resolvedCreate != nil {
		r.result = append(r.result, r.resolvedCreate)
	}
	if r.resolvedJoinRules != nil {
		r.result = append(r.result, r.resolvedJoinRules)
	}
	if r.resolvedPowerLevels != nil {
		r.result = append(r.result, r.resolvedPowerLevels)
	}
	for _, member := range r.resolvedMembers {
		r.result = append(r.result, member)
	}
	for _, invite := range r.resolvedThirdPartyInvites {
		r.result = append(r.result, invite)
	}
	for _, other := range r.resolvedOthers {
		r.result = append(r.result, other)
	}

	return r.result
}

// ResolveStateConflictsV2New takes a list of state events with conflicting state
// keys and works out which event should be used for each state event. This
// function returns the resolved state, including unconflicted state events.
// WIP: Untested.
func ResolveStateConflictsV2New(
	stateResAlgo StateResAlgorithm,
	stateSets [][]PDU,
	authEvents []PDU,
	userIDForSender spec.UserIDForSender,
	isRejectedFn IsRejected,
) []PDU {
	if len(stateSets) < 2 {
		panic("must provide at least 2 stateSets to resolve conflicts")
	}
	conflicted, unconflicted := splitConflictedUnconflicted(stateResAlgo, stateSets)
	// Prepare the state resolver.
	conflictedControlEvents := make([]PDU, 0, len(conflicted))
	conflictedOthers := make([]PDU, 0, len(conflicted))
	authProvider, _ := NewAuthEvents(nil)
	r := stateResolverV2{
		authEventMap:              eventMapFromEvents(authEvents),
		authProvider:              authProvider,
		conflictedEventMap:        eventMapFromEvents(conflicted),
		powerLevelContents:        make(map[string]*PowerLevelContent),
		powerLevelMainlinePos:     make(map[string]int),
		resolvedThirdPartyInvites: make(map[string]PDU, len(conflicted)),
		resolvedMembers:           make(map[spec.SenderID]PDU, len(conflicted)),
		resolvedOthers:            make(map[StateKeyTuple]PDU, len(conflicted)),
		result:                    make([]PDU, 0, len(conflicted)+len(unconflicted)),
		isRejectedFn:              isRejectedFn,
		isRejectedCache:           make(map[string]bool),
	}
	var roomID *spec.RoomID
	if len(conflicted) > 0 {
		validRoomID := conflicted[0].RoomID()
		roomID = &validRoomID
	}
	if len(unconflicted) > 0 {
		validRoomID := unconflicted[0].RoomID()
		roomID = &validRoomID
	}
	if len(authEvents) > 0 {
		validRoomID := authEvents[0].RoomID()
		roomID = &validRoomID
	}
	// If we still don't have a roomID, we don't have conflicted, unconflicted
	// or any authEvents, which in theory shouldn't happen.
	if roomID == nil {
		return r.result
	}

	r.allower = newAllowerContext(r.authProvider, userIDForSender, *roomID)

	unconflictedSet := newPDUSet(unconflicted)

	// Get the full conflicted set, that is the conflicted events and the
	// auth difference (events that don't appear in all auth chains).
	fullConflictedSet := append(conflicted, r.calculateAuthDifferenceNew(stateResAlgo, newPDUSet(conflicted), stateSets)...)

	// The full power set function returns the event and all of its auth
	// events that also happen to appear in the conflicted set. This will
	// effectively allow us to pull in all related events for any control
	// event, even if those related events are themselves not control events.
	visited := make(map[string]struct{}, len(conflicted)+len(authEvents))
	var fullControlSet func(event PDU) []PDU
	fullControlSet = func(event PDU) []PDU {
		events := []PDU{event}
		for _, authEventID := range event.AuthEventIDs() {
			if _, ok := visited[authEventID]; ok {
				continue
			}
			if event, ok := r.conflictedEventMap[authEventID]; ok {
				events = append(events, fullControlSet(event)...)
			}
			visited[authEventID] = struct{}{}
		}
		return events
	}

	// First of all, work through the full conflicted set. Ignoring any
	// events which are unconflicted (from the auth difference, for example),
	// pull in the control events and any events directly related to them.
	conflictedPulledIn := make(map[string]struct{}, len(conflicted)+len(authEvents))
	for _, p := range fullConflictedSet {
		if unconflictedSet.Contains(p) {
			continue
		}
		if isControlEvent(p) {
			relatedEvents := fullControlSet(p)
			for _, event := range relatedEvents {
				conflictedPulledIn[event.EventID()] = struct{}{}
			}
			conflictedControlEvents = append(conflictedControlEvents, relatedEvents...)
		}
	}

	// Then work through the set again, this time looking for any events
	// that were left over from the last loop — that is, events that are
	// either not control events or weren't pulled in to the control set.
	for _, p := range fullConflictedSet {
		if unconflictedSet.Contains(p) || isControlEvent(p) {
			continue
		}
		if _, ok := conflictedPulledIn[p.EventID()]; !ok {
			conflictedOthers = append(conflictedOthers, p)
		}
	}

	// Then process the unconflicted events by ordering them topologically.
	// v2.1 starts from the empty set, so only do this for v2.
	if stateResAlgo == StateResV2 {
		unconflicted = r.reverseTopologicalOrdering(unconflicted, TopologicalOrderByAuthEvents)
		r.applyEvents(unconflicted...)
	}

	// Then order the conflicted power level events topologically and then also
	// auth those too. The successfully authed events will be layered on top of
	// the partial state.
	conflictedControlEvents = r.reverseTopologicalOrdering(conflictedControlEvents, TopologicalOrderByAuthEvents)
	r.authAndApplyEvents(conflictedControlEvents...)

	// Then generate the mainline of power level events, order the remaining state
	// events based on the mainline ordering and auth those too. The successfully
	// authed events are also layered on top of the partial state.
	for pos, event := range r.createPowerLevelMainline() {
		r.powerLevelMainlinePos[event.EventID()] = pos
	}
	conflictedOthers = r.mainlineOrdering(conflictedOthers)
	r.authAndApplyEvents(conflictedOthers...)

	// Finally we will reapply the original set of unconflicted events onto the
	// partial state, just in case any of these were overwritten by pulling in
	// auth events in the previous two steps, and that gives us our final resolved
	// state.
	r.applyEvents(unconflicted...)

	// Now that we have our final state, populate the result array with the
	// resolved state and return it.
	if r.resolvedCreate != nil {
		r.result = append(r.result, r.resolvedCreate)
	}
	if r.resolvedJoinRules != nil {
		r.result = append(r.result, r.resolvedJoinRules)
	}
	if r.resolvedPowerLevels != nil {
		r.result = append(r.result, r.resolvedPowerLevels)
	}
	for _, member := range r.resolvedMembers {
		r.result = append(r.result, member)
	}
	for _, invite := range r.resolvedThirdPartyInvites {
		r.result = append(r.result, invite)
	}
	for _, other := range r.resolvedOthers {
		r.result = append(r.result, other)
	}

	return r.result
}

// ReverseTopologicalOrdering takes a set of input events and sorts them
// using Kahn's algorithm in order to topologically order them. The
// result array of events will be sorted so that "earlier" events appear
// first.
// FIXME: this function does not sort correctly because it doesn't lookup PL events
// correctly, meaning it will sort incorrectly for PL tiebreaks.
func ReverseTopologicalOrdering(input []PDU, order TopologicalOrder) []PDU {
	r := stateResolverV2{
		resolvedCreate: getCreateEvent(input),
	}
	return r.reverseTopologicalOrdering(input, order)
}

// TODO: Remove this function. Use ReverseTopologicalOrdering.
// HeaderedReverseTopologicalOrdering takes a set of input events and sorts
// them using Kahn's algorithm in order to topologically order them. The
// result array of events will be sorted so that "earlier" events appear
// first.
// FIXME: this function does not sort correctly because it doesn't lookup PL events
// correctly, meaning it will sort incorrectly for PL tiebreaks.
func HeaderedReverseTopologicalOrdering(events []PDU, order TopologicalOrder) []PDU {
	r := stateResolverV2{
		resolvedCreate: getCreateEvent(events),
	}
	input := make([]PDU, len(events))
	for i := range events {
		unwrapped := events[i]
		input[i] = unwrapped
	}
	result := make([]PDU, len(input))
	for i, e := range r.reverseTopologicalOrdering(input, order) {
		result[i] = e
	}
	return result
}

func getCreateEvent(input []PDU) PDU {
	for _, ev := range input {
		if ev.Type() == spec.MRoomCreate && ev.StateKeyEquals("") {
			return ev
		}
	}
	return nil
}

// isControlEvent returns true if the event meets the criteria for being classed
// as a "control" event for reverse topological sorting. If not then the event
// will be mainline sorted.
func isControlEvent(e PDU) bool {
	switch e.Type() {
	case spec.MRoomPowerLevels:
		// Power level events with an empty state key are control events.
		return e.StateKeyEquals("")
	case spec.MRoomJoinRules:
		// Join rule events with an empty state key are control events.
		return e.StateKeyEquals("")
	case spec.MRoomMember:
		// Membership events must not have an empty state key.
		if e.StateKey() == nil || e.StateKeyEquals("") {
			break
		}
		// Membership events are only control events if the sender does not match
		// the state key, i.e. because the event is caused by an admin or moderator.
		if e.StateKeyEquals(string(e.SenderID())) {
			break
		}
		// Membership events are only control events if the "membership" key in the
		// content is "leave" or "ban" so we need to extract the content.
		var content MemberContent
		if err := json.Unmarshal(e.Content(), &content); err != nil {
			break
		}
		// If the "membership" key is set and is set to either "leave" or "ban" then
		// the event is a control event.
		if content.Membership == spec.Leave || content.Membership == spec.Ban {
			return true
		}
	default:
	}
	// If we have reached this point then we have failed all checks and we don't
	// count the event as a control event.
	return false
}

func (r *stateResolverV2) calculateAuthDifference() []PDU {
	authDifference := make([]PDU, 0, len(r.conflictedEventMap)*3)
	authSets := make(map[string]map[string]PDU, len(r.conflictedEventMap))

	// This function helps us to work out whether an event exists in one of the
	// auth sets.
	isInAuthList := func(k string, event PDU) bool {
		events, ok := authSets[k]
		if !ok {
			return false
		}
		_, ok = events[event.EventID()]
		return ok
	}

	// This function works out if an event exists in all of the auth sets.
	isInAllAuthLists := func(event PDU) bool {
		for k, event := range authSets[event.EventID()] {
			if !isInAuthList(k, event) {
				return false
			}
		}
		return true
	}

	// For each conflicted event, work out the auth chain iteratively.
	var iter func(eventID string, event PDU)
	iter = func(eventID string, event PDU) {
		for _, authEventID := range event.AuthEventIDs() {
			authEvent, ok := r.authEventMap[authEventID]
			if !ok {
				continue
			}
			if _, ok := authSets[eventID]; !ok {
				authSets[eventID] = map[string]PDU{}
			}
			if _, ok := authSets[eventID][authEventID]; ok {
				// Don't repeat work for events we've already iterated on.
				continue
			}
			authSets[eventID][authEventID] = authEvent
			iter(eventID, authEvent)
		}
	}
	for conflictedEventID, conflictedEvent := range r.conflictedEventMap {
		iter(conflictedEventID, conflictedEvent)
	}

	// Look through all of the auth events that we've been given and work out if
	// there are any events which don't appear in all of the auth sets. If they
	// don't then we add them to the auth difference.
	for _, event := range r.authEventMap {
		if !isInAllAuthLists(event) {
			authDifference = append(authDifference, event)
		}
	}

	return authDifference
}

// Calculate the auth difference if algorithm = v2.
// Calculate the auth difference + conflicted subgraph if algorithm = v2.1.
// We combine them so we don't need to perform additional work, since calculating the auth difference
// does the same DFS we need for the conflicted subgraph.
func (r *stateResolverV2) calculateAuthDifferenceNew(
	stateResAlgo StateResAlgorithm, conflictedEvents *sets.HashSet[PDU, string], stateSets [][]PDU,
) []PDU {
	// For each state set, the union of the auth chains for each event in the state set is the full auth chain.
	// In other words, each state set produces one full auth chain by walking back up auth_events.
	//
	// v2.1: calculate the conflicted state subgraph at the same time.
	fullAuthChains := make([]*sets.HashSet[PDU, string], len(stateSets))
	completeConflictedSubgraph := newPDUSet(nil)
	for i, stateEvents := range stateSets {
		fullAuthChain, conflictedSubgraph := r.calculateFullAuthChainAndConflictedSubgraph(stateResAlgo, stateEvents, conflictedEvents)
		fullAuthChains[i] = fullAuthChain
		if stateResAlgo == StateResV2_1 {
			completeConflictedSubgraph.InsertSet(conflictedSubgraph)
		}
	}

	// The auth chain difference is calculated by taking the difference between the union and intersections.
	union := newPDUSet(nil)
	for _, fac := range fullAuthChains {
		union.InsertSet(fac)
	}
	// we asserted that we have at least 2 stateSets before, so we know these index accesses are safe.
	var intersection sets.Collection[PDU] = fullAuthChains[0]
	for _, fac := range fullAuthChains[1:] {
		intersection = intersection.Intersect(fac)
	}

	authDifference := union.Difference(intersection)
	if stateResAlgo == StateResV2 {
		return authDifference.Slice()
	}
	// v2.1 adds more events, the conflicted subgraph.
	return authDifference.Union(completeConflictedSubgraph).Slice()
}

// extract the full auth chain for a given state set
// extract the conflicted subgraph for a given state set
// We do this at the same time because it's more efficient to DFS once, which unfortunately means
// the function name is a bit wonky.
func (r *stateResolverV2) calculateFullAuthChainAndConflictedSubgraph(
	stateResAlgo StateResAlgorithm, stateSet []PDU, conflictedEvents *sets.HashSet[PDU, string],
) (fullAuthChains, conflictedSubgraph *sets.HashSet[PDU, string]) {
	fullAuthChains = newPDUSet(nil)
	conflictedSubgraph = newPDUSet(nil)

	type pduVisitors struct {
		pdu PDU
		// the current exploration path
		visiting []string
		// flag to indicate that the starting node is conflicted.
		// We are only interested in doing the book-keeping for 'visiting' for conflicted events.
		originConflicted bool
	}
	initial := make([]pduVisitors, len(stateSet))
	for i, p := range stateSet {
		initial[i] = pduVisitors{
			pdu: p,
			// we iteratively add event IDs to this as we walk, so we know the path from
			// a conflicted origin event to a potential conflicted event.
			visiting:         nil,
			originConflicted: conflictedEvents.Contains(p),
		}
	}

	// Using a stack ensure that we do DFS walks, which will consume less memory as we can short-circuit
	// earlier when we reach events we've already seen.
	stack := lane.NewStack(initial...)
	for stack.Size() > 0 {
		curr, ok := stack.Pop()
		if !ok {
			break
		}
		// determine if we need to do extra book-keeping on the visiting set
		shouldCalculateConflictedSubgraph := stateResAlgo == StateResV2_1 && curr.originConflicted

		// check if the current node is conflicted. If so, then ta-da, we found
		// a subgraph. This will add single conflicted nodes but shrug.
		if shouldCalculateConflictedSubgraph && conflictedEvents.Contains(curr.pdu) {
			conflictedSubgraphEventIDs := append(slices.Clone(curr.visiting), curr.pdu.EventID())
			fmt.Printf("found conflicted subgraph %v\n", conflictedSubgraphEventIDs)
			for _, eventID := range conflictedSubgraphEventIDs {
				conflictedSubgraph.Insert(r.authEventMap[eventID])
			}
		}

		for _, authEventID := range curr.pdu.AuthEventIDs() {
			authEvent, ok := r.authEventMap[authEventID]
			if !ok {
				// FIXME: we should return an error but prior code silently continued,
				// so match the existing behaviour.
				continue
			}
			// don't walk paths we've already walked
			if fullAuthChains.Contains(authEvent) {
				// ...unless we're tracking conflicted events in which case we need to re-walk:
				//
				// E1 <-- C1 <-- E2 <-- E3 <-- C2       C = conflicted
				//                ^---- E4 <-- E5
				//
				// If we walk E5 -> E1 first then we would never find out that C2 -> C1 as we would
				// have stopped at E2 due to having already walked it.
				if !shouldCalculateConflictedSubgraph {
					continue
				}
			}
			fullAuthChains.Insert(authEvent)

			if !shouldCalculateConflictedSubgraph {
				stack.Push(pduVisitors{
					pdu:      authEvent,
					visiting: nil,
				})
				continue
			}

			// append this node to the visiting set
			newVisiting := append(slices.Clone(curr.visiting), curr.pdu.EventID())
			stack.Push(pduVisitors{
				pdu:              authEvent,
				visiting:         newVisiting,
				originConflicted: curr.originConflicted,
			})
		}
	}
	return fullAuthChains, conflictedSubgraph
}

// createPowerLevelMainline generates the mainline of power level events,
// starting at the currently resolved power level event from the topological
// ordering and working our way back to the room creation. Note that we populate
// the result here in reverse, so that the room creation is at the beginning of
// the list, rather than the end.
func (r *stateResolverV2) createPowerLevelMainline() []PDU {
	var mainline []PDU

	// Define our iterator function.
	var iter func(event PDU)
	iter = func(event PDU) {
		// Append this event to the beginning of the mainline.
		mainline = append(mainline, nil)
		copy(mainline[1:], mainline)
		mainline[0] = event
		// Work through all of the auth event IDs that this event refers to.
		for _, authEventID := range event.AuthEventIDs() {
			// Check that we actually have the auth event in our map - we need this so
			// that we can look up the event type.
			if authEvent, ok := r.authEventMap[authEventID]; ok {
				// Is the event a power event?
				if authEvent.Type() == spec.MRoomPowerLevels && authEvent.StateKeyEquals("") {
					// We found a power level event in the event's auth events - start
					// the iterator from this new event.
					iter(authEvent)
				}
			}
		}
	}

	// Begin the sequence from the currently resolved power level event from the
	// topological ordering.
	if r.resolvedPowerLevels != nil {
		iter(r.resolvedPowerLevels)
	}

	return mainline
}

// getFirstPowerLevelMainlineEvent iteratively steps through the auth events of
// the given event until it finds an event that exists in the mainline. Note
// that for this function to work, you must have first called
// createPowerLevelMainline. This function returns three things: the event that
// was found in the mainline, the position in the mainline of the found event
// and the number of steps it took to reach the mainline.
func (r *stateResolverV2) getFirstPowerLevelMainlineEvent(event PDU) (
	mainlineEvent PDU, mainlinePosition int, steps int,
) {
	// Define a function that the iterator can use to determine whether the event
	// is in the mainline set or not.
	isInMainline := func(searchEvent PDU) (int, bool) {
		// If we already know the mainline position then return it.
		pos, ok := r.powerLevelMainlinePos[searchEvent.EventID()]
		return pos, ok
	}

	// Define our iterator function.
	var iter func(event PDU)
	iter = func(event PDU) {
		// In much the same way as we do in createPowerLevelMainline, we loop
		// through the event's auth events, checking that it exists in our supplied
		// auth event map and finding power level events.
		for _, authEventID := range event.AuthEventIDs() {
			// Check that we actually have the auth event in our map - we need this so
			// that we can look up the event type.
			authEvent, ok := r.authEventMap[authEventID]
			if !ok {
				continue
			}
			// If the event isn't a power level event then we'll ignore it.
			if authEvent.Type() != spec.MRoomPowerLevels || !authEvent.StateKeyEquals("") {
				continue
			}
			// Is the event in the mainline?
			if pos, isIn := isInMainline(authEvent); isIn {
				// It is - take a note of the event and position and stop the
				// iterator from running any further.
				mainlineEvent = authEvent
				mainlinePosition = pos
				// Cache the result so that a future request for this position will
				// be faster.
				r.powerLevelMainlinePos[mainlineEvent.EventID()] = mainlinePosition
				return
			}
			// It isn't - increase the step count and then run the iterator again
			// from the found auth event.
			steps++
			iter(authEvent)
		}
	}

	// Start the iterator with the supplied event.
	iter(event)

	return
}

// authAndApplyEvents iterates through the supplied list of events and auths
// them against the current partial state. If they pass the auth checks then we
// also apply them on top of the partial state. If they fail auth checks then
// the event is ignored and dropped. Returns two lists - the first contains the
// accepted (authed) events and the second contains the rejected events.
func (r *stateResolverV2) authAndApplyEvents(events ...PDU) {
	addFromAuthEventsIfNotRejected := func(event PDU, eventType, stateKey string) {
		for _, authEventID := range event.AuthEventIDs() {
			rejected, ok := r.isRejectedCache[authEventID]
			if !ok {
				rejected = r.isRejectedFn(authEventID)
				r.isRejectedCache[authEventID] = rejected
			}
			if rejected {
				continue
			}
			authEv, ok := r.authEventMap[authEventID]
			if !ok {
				continue
			}
			if authEv.Type() != eventType || !authEv.StateKeyEquals(stateKey) {
				continue
			}
			_ = r.authProvider.AddEvent(event)
		}
	}

	for _, event := range events {
		r.authProvider.Clear()

		// Now layer on the partial state events that we do know. This should
		// mean that we make forward progress.
		needed := StateNeededForAuth([]PDU{event})
		if resolved := r.resolvedCreate; needed.Create {
			if resolved != nil {
				_ = r.authProvider.AddEvent(resolved)
			} else {
				addFromAuthEventsIfNotRejected(event, spec.MRoomCreate, "")
			}
		}
		if resolved := r.resolvedJoinRules; needed.JoinRules {
			if resolved != nil {
				_ = r.authProvider.AddEvent(resolved)
			} else {
				addFromAuthEventsIfNotRejected(event, spec.MRoomJoinRules, "")
			}
		}
		if resolved := r.resolvedPowerLevels; needed.PowerLevels {
			if resolved != nil {
				_ = r.authProvider.AddEvent(resolved)
			} else {
				addFromAuthEventsIfNotRejected(event, spec.MRoomPowerLevels, "")
			}
		}
		for _, needed := range needed.Member {
			if resolved := r.resolvedMembers[spec.SenderID(needed)]; resolved != nil {
				_ = r.authProvider.AddEvent(resolved)
			} else {
				addFromAuthEventsIfNotRejected(event, spec.MRoomMember, needed)
			}
		}
		for _, needed := range needed.ThirdPartyInvite {
			if resolved := r.resolvedThirdPartyInvites[needed]; resolved != nil {
				_ = r.authProvider.AddEvent(resolved)
			} else {
				addFromAuthEventsIfNotRejected(event, spec.MRoomThirdPartyInvite, needed)
			}
		}

		// Check if the event is allowed based on the current partial state.
		r.allower.update(r.authProvider)
		if err := r.allower.allowed(event); err != nil {
			// The event was not allowed by the partial state and/or relevant
			// auth events from the event, so skip it.
			continue
		}
		// Apply the newly authed event to the partial state. We need to do this
		// here so that the next loop will have partial state to auth against.
		r.applyEvents(event)
	}
}

// applyEvents applies the events on top of the partial state.
func (r *stateResolverV2) applyEvents(events ...PDU) {
	for _, event := range events {
		if st, sk := event.Type(), event.StateKey(); sk == nil {
			continue
		} else if *sk == "" {
			// Some events with empty state keys are special,
			// i.e. create events, power level events, join rules.
			// Otherwise, they go in the "others".
			switch st {
			case spec.MRoomCreate:
				r.resolvedCreate = event
			case spec.MRoomPowerLevels:
				r.resolvedPowerLevels = event
			case spec.MRoomJoinRules:
				r.resolvedJoinRules = event
			default:
				r.resolvedOthers[StateKeyTuple{st, *sk}] = event
			}
		} else {
			// Some events with non-empty state keys are special,
			// i.e. membership events and 3PID invites. Otherwise,
			// they go in the "others".
			switch st {
			case spec.MRoomThirdPartyInvite:
				r.resolvedThirdPartyInvites[*sk] = event
			case spec.MRoomMember:
				r.resolvedMembers[spec.SenderID(*sk)] = event
			default:
				r.resolvedOthers[StateKeyTuple{st, *sk}] = event
			}
		}
	}
}

// eventMapFromEvents takes a list of events and returns a map, where the key
// for each value is the event ID.
func eventMapFromEvents(events []PDU) map[string]PDU {
	r := make(map[string]PDU, len(events))
	for _, e := range events {
		if _, ok := r[e.EventID()]; !ok {
			r[e.EventID()] = e
		}
	}
	return r
}

// wrapPowerLevelEventsForSort takes the input power level events and wraps them
// in stateResV2ConflictedPowerLevel structs so that we have the necessary
// information pre-calculated ahead of sorting.
func (r *stateResolverV2) wrapPowerLevelEventsForSort(events []PDU) []*stateResV2ConflictedPowerLevel {
	block := make([]*stateResV2ConflictedPowerLevel, len(events))
	for i, event := range events {
		block[i] = &stateResV2ConflictedPowerLevel{
			powerLevel:     r.getPowerLevelFromAuthEvents(event),
			originServerTS: event.OriginServerTS(),
			eventID:        event.EventID(),
			event:          event,
		}
	}
	return block
}

// wrapOtherEventsForSort takes the input non-power level events and wraps them
// in stateResV2ConflictedPowerLevel structs so that we have the necessary
// information pre-calculated ahead of sorting.
func (r *stateResolverV2) wrapOtherEventsForSort(events []PDU) []*stateResV2ConflictedOther {
	block := make([]*stateResV2ConflictedOther, len(events))
	for i, event := range events {
		_, pos, steps := r.getFirstPowerLevelMainlineEvent(event)
		block[i] = &stateResV2ConflictedOther{
			mainlinePosition: pos,
			mainlineSteps:    steps,
			originServerTS:   event.OriginServerTS(),
			eventID:          event.EventID(),
			event:            event,
		}
	}
	return block
}

// reverseTopologicalOrdering takes a set of input events, prepares them using
// wrapPowerLevelEventsForSort and then starts the Kahn's algorithm in order to
// topologically sort them. The result that is returned is correctly ordered.
func (r *stateResolverV2) reverseTopologicalOrdering(events []PDU, order TopologicalOrder) []PDU {
	result := make([]PDU, 0, len(events))
	switch order {
	case TopologicalOrderByAuthEvents:
		block := r.wrapPowerLevelEventsForSort(events)
		for _, s := range kahnsAlgorithmUsingAuthEvents(block) {
			result = append(result, s.event)
		}
	case TopologicalOrderByPrevEvents:
		block := r.wrapOtherEventsForSort(events)
		for _, s := range kahnsAlgorithmUsingPrevEvents(block) {
			result = append(result, s.event)
		}
	default:
		panic(fmt.Sprintf("gomatrixserverlib.reverseTopologicalOrdering unknown Ordering %d", order))
	}
	return result
}

// mainlineOrdering takes a set of input events, prepares them using
// wrapOtherEventsForSort and then sorts them based on mainline ordering. The
// result that is returned is correctly ordered.
func (r *stateResolverV2) mainlineOrdering(events []PDU) []PDU {
	block := r.wrapOtherEventsForSort(events)
	result := make([]PDU, 0, len(block))
	slices.SortStableFunc(block, sortStateResV2ConflictedOtherHeap)
	for _, s := range block {
		result = append(result, s.event)
	}
	return result
}

// getPowerLevelFromAuthEvents tries to determine the effective power level of
// the sender at the time that of the given event, based on the auth events.
// This is used in the Kahn's algorithm tiebreak.
func (r *stateResolverV2) getPowerLevelFromAuthEvents(event PDU) int64 {
	user := event.SenderID()
	verImpl := MustGetRoomVersion(event.Version())
	if verImpl.PrivilegedCreators() {
		// get the create event
		createEvent := r.resolvedCreate
		if createEvent == nil {
			panic("getPowerLevelFromAuthEvents: missing resolved create event, cannot calculate PL of sender!")
		}
		for _, creator := range CreatorsFromCreateEvent(createEvent) {
			if creator == string(user) {
				return CreatorPowerLevel
			}
		}
		// otherwise they aren't a creator, so check the PL event.
	}

	for _, authID := range event.AuthEventIDs() {
		// Then check and see if we have the auth event in the auth map, if not
		// then we cannot deduce the real effective power level.
		authEvent, ok := r.authEventMap[authID]
		if !ok {
			continue
		}

		// Ignore the auth event if it isn't a power level event.
		if authEvent.Type() != spec.MRoomPowerLevels || *authEvent.StateKey() != "" {
			continue
		}

		// See if we have a cached copy of the power level content
		// for this event ID already in memory.
		content, ok := r.powerLevelContents[authID]
		if !ok {
			// Try and parse the content of the event.
			parsed, err := NewPowerLevelContentFromEvent(authEvent)
			if err != nil {
				return 0
			}
			content = &parsed

			// Cache it in memory.
			r.powerLevelContents[authID] = content
		}

		// Look up what the power level should be for this user. If the user is
		// not in the list, the default user power level will be returned instead.
		return content.UserLevel(user)
	}

	return 0
}

// kahnsAlgorithmByAuthEvents is, predictably, an implementation of Kahn's
// algorithm that uses auth events to topologically sort the input list of
// events. This works through each event, counting how many incoming auth event
// dependencies it has, and then adding them into the graph as the dependencies
// are resolved.
func kahnsAlgorithmUsingAuthEvents(events []*stateResV2ConflictedPowerLevel) []*stateResV2ConflictedPowerLevel {
	eventMap := make(map[string]*stateResV2ConflictedPowerLevel, len(events))
	graph := make([]*stateResV2ConflictedPowerLevel, 0, len(events))
	inDegree := make(map[string]int, len(events))

	for _, event := range events {
		// For each event that we have been given, add it to the event map so that
		// we can easily refer back to it by event ID later.
		eventMap[event.eventID] = event

		// If we haven't encountered this event ID yet, also start with a zero count
		// of incoming auth event dependencies.
		if _, ok := inDegree[event.eventID]; !ok {
			inDegree[event.eventID] = 0
		}

		// Find each of the auth events that this event depends on and make a note
		// for each auth event that there's an additional incoming dependency.
		for _, auth := range event.event.AuthEventIDs() {
			inDegree[auth]++
		}
	}

	// Now we need to work out which events don't have any incoming auth event
	// dependencies. These will be placed into the graph first. Remove the event
	// from the event map as this prevents us from processing it a second time.
	noIncoming := make(stateResV2ConflictedPowerLevelHeap, 0, len(events))
	for eventID, count := range inDegree {
		if count == 0 {
			noIncoming.Push(eventMap[eventID])
			delete(eventMap, eventID)
		}
	}
	slices.SortStableFunc(noIncoming, sortStateResV2ConflictedPowerLevelHeap)

	for len(noIncoming) > 0 {
		// Pop the first event ID off the list of events which have no incoming
		// auth event dependencies.
		event := noIncoming.Pop()

		// Since there are no incoming dependencies to resolve, we can now add this
		// event into the graph.
		graph = append(graph, nil)
		copy(graph[1:], graph)
		graph[0] = event

		// Now we should look at the outgoing auth dependencies that this event has.
		// Since this event is now in the graph, the event's outgoing auth
		// dependencies are no longer valid - those map to incoming dependencies on
		// the auth events, so let's update those.
		for _, auth := range event.event.AuthEventIDs() {
			inDegree[auth]--

			// If we see, by updating the incoming dependencies, that the auth event
			// no longer has any incoming dependencies, then it should also be added
			// into the graph on the next pass. In turn, this will also mean that we
			// process the outgoing dependencies of this auth event.
			if inDegree[auth] == 0 {
				if _, ok := eventMap[auth]; ok {
					noIncoming.Push(eventMap[auth])
					delete(eventMap, auth)
				}
			}
		}
		slices.SortStableFunc(noIncoming, sortStateResV2ConflictedPowerLevelHeap)
	}

	// If we have stray events left over then add them into the result.
	if len(eventMap) > 0 {
		remaining := make(stateResV2ConflictedPowerLevelHeap, 0, len(events))
		for _, event := range eventMap {
			remaining.Push(event)
		}
		slices.SortStableFunc(remaining, sortStateResV2ConflictedPowerLevelHeap)
		graph = append(remaining, graph...)
	}

	// The graph is complete at this point!
	return graph
}

// kahnsAlgorithmUsingPrevEvents is, predictably, an implementation of Kahn's
// algorithm that uses prev events to topologically sort the input list of
// events. This works through each event, counting how many incoming prev event
// dependencies it has, and then adding them into the graph as the dependencies
// are resolved.
func kahnsAlgorithmUsingPrevEvents(events []*stateResV2ConflictedOther) []*stateResV2ConflictedOther {
	eventMap := make(map[string]*stateResV2ConflictedOther, len(events))
	graph := make([]*stateResV2ConflictedOther, 0, len(events))
	inDegree := make(map[string]int, len(events))

	for _, event := range events {
		// For each event that we have been given, add it to the event map so that
		// we can easily refer back to it by event ID later.
		eventMap[event.eventID] = event

		// If we haven't encountered this event ID yet, also start with a zero count
		// of incoming prev event dependencies.
		if _, ok := inDegree[event.eventID]; !ok {
			inDegree[event.eventID] = 0
		}

		// Find each of the prev events that this event depends on and make a note
		// for each prev event that there's an additional incoming dependency.
		for _, prev := range event.event.PrevEventIDs() {
			inDegree[prev]++
		}
	}

	// Now we need to work out which events don't have any incoming prev event
	// dependencies. These will be placed into the graph first. Remove the event
	// from the event map as this prevents us from processing it a second time.
	noIncoming := make(stateResV2ConflictedOtherHeap, 0, len(events))
	for eventID, count := range inDegree {
		if count == 0 {
			noIncoming.Push(eventMap[eventID])
			delete(eventMap, eventID)
		}
	}
	slices.SortStableFunc(noIncoming, sortStateResV2ConflictedOtherHeap)

	for len(noIncoming) > 0 {
		// Pop the first event ID off the list of events which have no incoming
		// prev event dependencies.
		event := noIncoming.Pop()

		// Since there are no incoming dependencies to resolve, we can now add this
		// event into the graph.
		graph = append(graph, nil)
		copy(graph[1:], graph)
		graph[0] = event

		// Now we should look at the outgoing prev dependencies that this event has.
		// Since this event is now in the graph, the event's outgoing prev
		// dependencies are no longer valid - those map to incoming dependencies on
		// the prev events, so let's update those.
		for _, prev := range event.event.PrevEventIDs() {
			inDegree[prev]--

			// If we see, by updating the incoming dependencies, that the prev event
			// no longer has any incoming dependencies, then it should also be added
			// into the graph on the next pass. In turn, this will also mean that we
			// process the outgoing dependencies of this prev event.
			if inDegree[prev] == 0 {
				if _, ok := eventMap[prev]; ok {
					noIncoming.Push(eventMap[prev])
					delete(eventMap, prev)
				}
			}
		}
		slices.SortStableFunc(noIncoming, sortStateResV2ConflictedOtherHeap)
	}

	// If we have stray events left over then add them into the result.
	if len(eventMap) > 0 {
		remaining := make(stateResV2ConflictedOtherHeap, 0, len(events))
		for _, event := range eventMap {
			remaining = append(remaining, event)
		}
		slices.SortStableFunc(remaining, sortStateResV2ConflictedOtherHeap)
		graph = append(remaining, graph...)
	}
	return graph
}

// Convert a list of PDUs into a set, keyed off the event ID of the PDU
func newPDUSet(pdus []PDU) *sets.HashSet[PDU, string] {
	s := sets.NewHashSetFunc[PDU, string](len(pdus), func(p PDU) string {
		return p.EventID()
	})
	s.InsertSlice(pdus)
	return s
}
