Draft: filtering support

Fixes #1.

Current status

/messages

• rooms/not_rooms filtering
• filter.limit
• per-event filtering
  • contains_url
  • senders/not_senders
  • types/not_types
• total limit on events examined

/sync

• figure out why it seems to be caching responses from requests that used a different filter
• top-level room filtering
• timeline room filtering
• state room filtering
  • get confirmation that filter.room.state does not apply to invite_state 1
• skip left/invited rooms with no updates
• ephemeral room filtering
• timeline per-event filtering
• state per-event filtering
• ephemeral per-event filtering
• limit
  • timeline
  • ephemeral
  • clarification on how it works for other event collections https://matrix.to/#/!jxlRxnrZCsjpjDubDX:matrix.org/$bxxpuNrRigJNBnfw2YA0O_R_aVuhCckv5utVOyIjVz0?via=matrix.org&via=envs.net&via=mozilla.org
• include_leave
• global account_data filtering
• per-room account_data filtering
• double-check that interaction with lazy-loading is correct
• double-check that notification/unread counts are okay
• total limit on timeline events examined
• double-check that state filter applies to the state field in the response (delta between since and prev_batch), not to all state events (including the ones in timeline)
• fix for invalid data served from cache

/rooms/{roomId}/context/{eventId}

• room filtering
• per-event filtering
• total limit on events examined

/search

• fix search in element so that I can test
• rooms (this is partially-implemented already, we likely want to rewrite it)
• per-event filtering
• load_limit > limit (unsure whether this is actually necessary to be honest. It's kinda annoying to do with the current structure).

general

• unit tests
• testing with complement
• profiling

Future work

I don't intend to include these in this MR.

Functionality

• event_fields filter. This one is really tricky to implement with the way ruma is set up.

Performance

• fast path in AllowDenyList for allow-all and skip-all
• fast path in WildcardAllowDenyList for patterns that don't contain wildcards
• fast paths for filters that reject all events with things like
  • types: []
  • not_types: ["*"]
  • senders: []
  • this is especially relevant for presence and global account_data, which can't be rejected using rooms: []
• rooms <- rooms ∩ (timeline.rooms ∪ ephemeral.rooms ∪ state.rooms) optimization
• compiled filter cache