Documentation
¶
Overview ¶
Package v2 implements the Matrix state resolution algorithm for rooms version 2 and later. It implements both state resolution version 2 (room version 2 through 11) and version 2.1 (room version 12).
Due to limitations with the Mautrix PDU struct, only room version 3 and later is supported.
Example ¶
See: https://codeberg.org/timedout/venator/src/branch/dev/stateres/README.md#example
Index ¶
- Variables
- func AuthChain(ctx context.Context, eventID id.EventID, fetchEvent FetchEventFunc) []id.EventID
- func AuthDifference(ctx context.Context, eventIDs []id.EventID, fetchEvent FetchEventFunc) []id.EventID
- func ConflictedStateSubgraph(ctx context.Context, conflictedStateSet sets.Set[id.EventID], ...) sets.Set[id.EventID]
- func IsPowerEvent(evt *pdu.PDU) bool
- func LexicographicalTopologicalSort(graph map[id.EventID]*pdu.PDU, tree TreeKind) []id.EventID
- func MainlineOrdering(ctx context.Context, eventIDs []id.EventID, powerLevelEvent *pdu.PDU, ...) []id.EventID
- func ReverseTopologicalPowerSort(ctx context.Context, roomVersion id.RoomVersion, eventIDs []id.EventID, ...) []id.EventID
- func ReverseTopologicalSort(graph map[id.EventID]*pdu.PDU, sortWithKey func(a, b id.EventID) int, ...) []id.EventID
- func SplitConflicts(incoming []StateMap) (StateMap, StateSet)
- func TopologicalSort(graph map[id.EventID]*pdu.PDU, sortWithKey func(a, b id.EventID) int, ...) []id.EventID
- type EventMapdeprecated
- type FetchEventFunc
- type ResolveOpts
- type StateMap
- type StateSet
- type TreeKind
Constants ¶
This section is empty.
Variables ¶
var ( ErrInvalidResolutionOptions = errors.New("invalid resolution options") ErrNoCreateEvent = errors.New("room create event did not appear in unconflicted state map") ErrMissingCreateEvent = errors.New("failed to fetch room create event") ErrBadCreateEvent = errors.New("failed to load room create event") )
Functions ¶
func AuthChain ¶
AuthChain recursively calculates the auth chain for a given event (i.e. every auth event leading up to it).
func AuthDifference ¶
func AuthDifference(ctx context.Context, eventIDs []id.EventID, fetchEvent FetchEventFunc) []id.EventID
AuthDifference calculates the difference in auth chains between a set of events.
In essence, this calculates all auth events that aren't mutual to every event in the set. It calculates auth chains concurrently.
func ConflictedStateSubgraph ¶
func ConflictedStateSubgraph( ctx context.Context, conflictedStateSet sets.Set[id.EventID], fetchEvent FetchEventFunc, ) sets.Set[id.EventID]
ConflictedStateSubgraph computes the subgraph of auth events that connect events in the conflicted state set. Starting from an event in the conflicted state set and following auth_events edges may lead to another event in the conflicted state set. The union of all such paths between any pair of events in the conflicted state set (including endpoints) forms a subgraph of the original auth_event graph, called the conflicted state subgraph.
func IsPowerEvent ¶
IsPowerEvent determines whether the given event is a "power event".
The spec defines a power event as any of the following:
- m.room.join_rules
- m.room.power_levels
- m.room.member (where membership is leave or ban, and the sender differs from the state key)
func LexicographicalTopologicalSort ¶
LexicographicalTopologicalSort performs a reverse topological sort with lexicographical ordering. That is, the tie-break is based on solely the event IDs themselves. Most callers will prefer ReverseTopologicalPowerSort, which also accounts for power levels.
func MainlineOrdering ¶
func MainlineOrdering( ctx context.Context, eventIDs []id.EventID, powerLevelEvent *pdu.PDU, opts *ResolveOpts, ) []id.EventID
MainlineOrdering sorts the given slice of event IDs based on their mainline position.
See also: https://spec.matrix.org/v1.17/rooms/v12/#definitions
func ReverseTopologicalPowerSort ¶
func ReverseTopologicalPowerSort( ctx context.Context, roomVersion id.RoomVersion, eventIDs []id.EventID, fullConflictedSet sets.Set[id.EventID], fetchEvent FetchEventFunc, ) []id.EventID
ReverseTopologicalPowerSort sorts the incoming event IDs based on their reversed topological power ordering.
See: https://spec.matrix.org/v1.18/rooms/v12/#definitions
See also (internal): reverseTopologicalSort.
func ReverseTopologicalSort ¶
func ReverseTopologicalSort( graph map[id.EventID]*pdu.PDU, sortWithKey func(a, b id.EventID) int, tree TreeKind, ) []id.EventID
ReverseTopologicalSort performs a reverse topological sort on the given graph (returns dependencies before their dependents).
The graph provided to this function is not mutated. Which tree (auth or prev) is walked can be changed by supplying a different TreeKind.
func SplitConflicts ¶
SplitConflicts separates the conflicting events in the given incoming state maps, returning (non-conflicting, conflicting). See also: StateMap, StateSet.
func TopologicalSort ¶
func TopologicalSort( graph map[id.EventID]*pdu.PDU, sortWithKey func(a, b id.EventID) int, tree TreeKind, ) []id.EventID
TopologicalSort performs a topological sort on the given graph (returns dependants before their dependencies). This literally just calls slices.Reverse on the result of reverseTopologicalSort.
The graph provided to this function is not mutated. Which tree (auth or prev) is walked can be changed by supplying a different TreeKind.
Types ¶
type FetchEventFunc ¶
FetchEventFunc is a generic function signature that is used to fetch events by their ID. If the event cannot be found, nil should be returned. The Context provided is the same one passed to the Resolve function.
Important: the function really should cache its results. The same call may be made potentially hundreds of times per resolve task.
type ResolveOpts ¶
type ResolveOpts struct {
RoomVersion id.RoomVersion
RoomID id.RoomID
FetchEvent FetchEventFunc
FetchSigningKey pdu.GetKeyFunc
}
type StateMap ¶
StateMap is a type alias to a map of {(type, key): V}, where V is the ID of a state event.
func IterativeAuthChecks ¶
func IterativeAuthChecks(ctx context.Context, eventIDs []id.EventID, base StateMap, opts *ResolveOpts) StateMap
IterativeAuthChecks runs a set of events through the iterative auth checks defined in the spec: https://spec.matrix.org/v1.17/rooms/v12/#definitions.
func Resolve ¶
func Resolve(ctx context.Context, incoming []StateMap, opts ResolveOpts) (final StateMap, err error)
Resolve runs the state resolution v2 or v2.1 algorithm against the provided incoming states.
Spec: https://spec.matrix.org/v1.17/rooms/v12/#state-resolution
Errors ¶
Resolve typically doesn't resolve errors unless something is very wrong. Here's an exhaustive list:
ErrInvalidResolutionOptions: An option in `opts` was wrong in some capacity.
ErrNoCreateEvent: There were conflicting events, but `m.room.create` was not present in the unconflicted set.
ErrMissingCreateEvent: The `m.room.create` event could not be fetched by `opts.FetchEvent`.
ErrBadCreateEvent: The `m.room.create` event was catastrophically invalid or malformed somehow.
Logging ¶
Resolve will emit logs via the standard zerolog.Logger returned by zerolog.Ctx on the ctx. All logs will be at debug or trace, and can consequently be used for performance measurements. In production, it is recommended a logger from zerolog.Nop is provided in order to avoid wasting compute cycles waiting for logging to flush.
type StateSet ¶
StateSet represents a map of {(type, key): Set[V]}, where V is a set of event IDs that belong to state events. Generally this is used to represent state keys with multiple, conflicting state events as values.
Each map key should always have more than one entry - otherwise, the sole value should go in a StateMap instead.
Source Files