Authorization rules are confusing

[turt2live]

Link to problem area: https://spec.matrix.org/v1.8/rooms/v11/#authorization-rules

Issue

Specifically steps like 5.1 are of concern, as at first glance they can be read to imply that self-unbans are possible. The pseudocode doesn't feel like it's helping throughout the rules, so options may be to fully commit to pseudocode or to get rid of it in favour of descriptive language.

Suggestions (and PRs) are very welcome here.

[richvdh]

Two thoughts:

• As part of the Re-clarify the auth rules around invite->knock transitions #1710 mess, it was proposed that we should not accept any further changes to the auth rules without accompanying test vectors.

• Mermaidjs makes it pretty easy to write flowcharts now. Maybe we should replace the pseudocode with flowcharts?

[turt2live]

+1 to flowcharts. I think the requirement for tests is best discussed on the dedicated MSC: matrix-org/matrix-spec-proposals#4092

[Johennes]

For illustration purposes, this is a sloppy flowchart for steps 1 through 3.

flowchart TD

    start((event)) --> 1
    1{1: *type == m.room.create*?} -->|Yes| 1.1
      1.1{1.1: has any *prev_events*?} -->|Yes| 1_reject((reject))
      1.1 -->|No| 1.2
      1.2{1.2: *room_id* domain != *sender* domain?} -->|Yes| 1_reject
      1.2 -->|No| 1.3
      1.3{1.3: *content.room_version* is present but not a recognised version?} -->|Yes| 1_reject
      1.3 -->|No| 1_allow((allow))
      1 -->|No| 2
    2(2: consider *auth_events*) --> 2.1
      2.1{2.1: duplicate entries for a given *type* and *state_key* pair?} -->|Yes| 2_reject((reject))
      2.1 -->|No| 2.2
      2.2{2.2: Any entries whose type and state_key don't match auth events selection algorithm?} -->|Yes| 2_reject
      2.2 -->|No| 2.3
      2.3{2.3: Any entries which were themselves rejected?} -->|Yes| 2_reject
      2.3 -->|No| 2.4
      2.4{2.4: No *m.room.create* event among entries?} -->|Yes| 2_reject
      2.4 -->|No| 3
    3{3: *m.room.create* event in room state has *m.federate* set to false and the sender domain does not match sender domain of create event?} -->|Yes| 3_reject((reject))
      3 -->|No| 4(4: ...)

Loading

Some questions and observations:

• Given the size of this, I suppose having separate charts per top-level step would be best?
• Some parts would probably be easier to follow if double negation were avoided (see e.g. "No m.room.create event among entries?" --> Yes/No)
• I'm not sure if sharing the terminating "reject" node per top-level step helps or not. It allows putting the final results of the step at the same vertical position but causes quite long vertical lines.

[richvdh]

Oooh this is an interesting start!

Some questions and observations:

* Given the size of this, I suppose having separate charts per top-level step would be best?

Possibly, though that also might be quite confusing. Some of the top-level steps (eg step 1, 4) reach a definite "allow/reject" conclusion, and so would probably be fine as a sub-chart, but most of them just fall through to the next step, so you'd need a top-level chart that calls out to subcharts and subcharts that return to the top-level chart.

But for step 4 (m.room.member) I think having "Yes: go to m.room.member sub-chart" could work quite well.

* Some parts would probably be easier to follow if double negation were avoided (see e.g. "No _m.room.create_ event among entries?" --> Yes/No)

Indeed. Such clarifications could also be beneficial to the text format ("Unless there is an m.room.create event among the entries, reject").

I think we should be wary of changing the format and the wording at the same time.

* I'm not sure if sharing the terminating "reject" node per top-level step helps or not. It allows putting the final results of the step at the same vertical position but causes quite long vertical lines.

I think the shorter edges are more important than lining up the results.

[Johennes]

Possibly, though that also might be quite confusing. Some of the top-level steps (eg step 1, 4) reach a definite "allow/reject" conclusion, and so would probably be fine as a sub-chart, but most of them just fall through to the next step, so you'd need a top-level chart that calls out to subcharts and subcharts that return to the top-level chart.

But for step 4 (m.room.member) I think having "Yes: go to m.room.member sub-chart" could work quite well.

Alternatively (or maybe additionally) we could also use subgraphs to visually group the different top-level steps. Here's a variant with some further steps, subgraphs and shorter edges for "reject" nodes. I also tried coloring the terminating nodes (allow & reject) to call out where and how the flow ends.

Writing the chart has been quite mechanical so far. It might even be possible to just generate it entirely with a small script that parses the auth steps.

flowchart TD

    start((event)) --> 1

    subgraph sg1 [Step 1]
        1{1: *type == m.room.create*?} -->|Yes| 1.1
        1.1{1.1: has any *prev_events*?} -->|Yes| 1.1_reject((reject))
        1.1 -->|No| 1.2
        1.2{1.2: *room_id* domain != *sender* domain?} -->|Yes| 1.2_reject((reject))
        1.2 -->|No| 1.3
        1.3{1.3: *content.room_version* is present but not a recognised version?} -->|Yes| 1.3_reject((reject))
        1.3 -->|No| 1.4_allow((allow))
    end

    subgraph sg2 [Step 2]
        1 -->|No| 2
        2(2: consider *auth_events*) --> 2.1
        2.1{2.1: duplicate entries for a given *type* and *state_key* pair?} -->|Yes| 2.1_reject((reject))
        2.1 -->|No| 2.2
        2.2{2.2: Any entries whose type and state_key don't match auth events selection algorithm?} -->|Yes| 2.2_reject((reject))
        2.2 -->|No| 2.3
        2.3{2.3: Any entries which were themselves rejected?} -->|Yes| 2.3_reject((reject))
        2.3 -->|No| 2.4
        2.4{2.4: No *m.room.create* event among entries?} -->|Yes| 2.4_reject((reject))
    end

    subgraph sg3 [Step 3]
        2.4 -->|No| 3
        3{3: *m.room.create* event in room state has *m.federate* set to false and the sender domain does not match sender domain of create event?} -->|Yes| 3_reject((reject))
    end

    subgraph sg4 [Step 4]
        3 -->|No| 4
        4{4: type == m.room.member?} -->|Yes| 4.1
        4.1{4.1: No state_key property, or no membership property in content?} -->|Yes| 4.1_reject((reject))
        4.1 -->|No| 4.2
        4.2{4.2: content has join_authorised_via_users_server key?} -->|Yes| 4.2.1
        4.2.1{4.2.1: event not validly signed by homeserver of user ID denoted by key?} -->|Yes| 4.2.1_reject((reject))
        4.2.1 -->|No| 4.3
        4.2 -->|No| 4.3
        4.3{4.3: membership == join?} -->|Yes| 4.3.1
        4.3.1{4.3.1: **Changed in this version** only previous event is m.room.create and state_key is sender?} -->|Yes| 4.3.1_allow((allow))
        4.3.1 -->|No| 4.3.2
        4.3.2{4.3.2: sender does not match state_key?} -->|Yes| 4.3.2_reject((reject))
        4.3.2 -->|No| 4.3.3
        4.3.3{4.3.3: sender is banned?} -->|Yes| 4.3.3_reject((reject))
        4.3.3 -->|No| 4.3.4(4.3.4: ...)

        4.3 -->|No| 4.4(4.4: ...)
    end

    subgraph sg5 [Step 5]
        4 -->|No| 5(5: ...)
    end

    classDef reject fill:#fdd;
    class 1.1_reject reject;
    class 1.2_reject reject;
    class 1.3_reject reject;
    class 2.1_reject reject;
    class 2.2_reject reject;
    class 2.3_reject reject;
    class 2.4_reject reject;
    class 3_reject reject;
    class 4.1_reject reject;
    class 4.2.1_reject reject;
    class 4.3.2_reject reject;
    class 4.3.3_reject reject;

    classDef allow fill:#dfd;
    class 1.4_allow allow;
    class 4.3.1_allow allow;

Loading

[Johennes]

Conversing in DM with @clokep he remarked that if we split the diagram into several charts, we could embed HTML links in entry and exit nodes to help navigate back and forth between graphs.

flowchart TD
  4{4: type == m.room.member?} -->|Yes| 4.1{4.1: ...}
  4.1 -->|Yes| 4.1_yes(...)
  4.1 -->|No| 4.1_no(...)
  4 -->|No| 5(<a href='https://spec.matrix.org/v1.11/rooms/v11#auth-chart-step5'>go to 5</a>)

Loading

[Johennes]

Here's a flow chart for the entirety of rules and subcharts broken out for steps 1 through 3, 4 and 5 through 10. I'm not sure if this is actually viable or not because the subcharts are still enormously large. Maybe they could be broken down further into smaller charts but the overall complexity remains.

flowchart TD

    start --> 1{{"`1: {{< changed-in v=11 >}} type is _m.room.create_?`"}}

  subgraph "Step 1"
    1 -->|Yes| 1.1{{"`1.1: It has any _prev_events_?`"}}
    1.1 -->|Yes| 1.1_reject(["`reject`"])
    1.1 -->|No| 1.2{{"`1.2: The domain of the _room_id_ does not match the domain of the _sender_?`"}}
    1.2 -->|Yes| 1.2_reject(["`reject`"])
    1.2 -->|No| 1.3{{"`1.3: _content.room_version_ is present and is not a recognised version?`"}}
    1.3 -->|Yes| 1.3_reject(["`reject`"])
    1.3 -->|No| 1.4(["`allow`"])
  end

  subgraph "Step 2"
    1 -->|No| 2["`2: Considering the event's _auth_events_`"]
    2 --> 2.1{{"`2.1: There are duplicate entries for a given _type_ and _state_key_ pair?`"}}
    2.1 -->|Yes| 2.1_reject(["`reject`"])
    2.1 -->|No| 2.2{{"`2.2: There are entries whose _type_ and _state_key_ don't match those specified by the [auth events selection](/server-server-api#auth-events-selection) algorithm described in the server specification?`"}}
    2.2 -->|Yes| 2.2_reject(["`reject`"])
    2.2 -->|No| 2.3{{"`2.3: There are entries which were themselves rejected under the [checks performed on receipt of a PDU](/server-server-api/#checks-performed-on-receipt-of-a-pdu)?`"}}
    2.3 -->|Yes| 2.3_reject(["`reject`"])
    2.3 -->|No| 2.4{{"`2.4: There is no _m.room.create_ event among the entries?`"}}
    2.4 -->|Yes| 2.4_reject(["`reject`"])
  end

  subgraph "Step 3"
    2.4 -->|No| 3{{"`3: The _content_ of the _m.room.create_ event in the room state has the property _m.federate_ set to _false_, and the _sender_ domain of the event does not match the _sender_ domain of the create event?`"}}
    3 -->|Yes| 3_reject(["`reject`"])
  end

  subgraph "Step 4"
    3 -->|No| 4{{"`4: Type is _m.room.member_?`"}}
    4 -->|Yes| 4.1{{"`4.1: There is no _state_key_ property, or no _membership_ property in _content_?`"}}
    4.1 -->|Yes| 4.1_reject(["`reject`"])
    4.1 -->|No| 4.2{{"`4.2: _content_ has a _join_authorised_via_users_server_ key?`"}}
    4.2 -->|Yes| 4.2.1{{"`4.2.1: The event is not validly signed by the homeserver of the user ID denoted by the key?`"}}
    4.2.1 -->|Yes| 4.2.1_reject(["`reject`"])
    4.2.1 -->|No| 4.3{{"`4.3: _membership_ is _join_?`"}}
    4.2 -->|No| 4.3
    4.3 -->|Yes| 4.3.1{{"`4.3.1: {{< changed-in v=11 >}} the only previous event is an _m.room.create_ and the _state_key_ is the sender?`"}}
    4.3.1 -->|Yes| 4.3.1_allow(["`allow`"])
    4.3.1 -->|No| 4.3.2{{"`4.3.2: The _sender_ does not match _state_key_?`"}}
    4.3.2 -->|Yes| 4.3.2_reject(["`reject`"])
    4.3.2 -->|No| 4.3.3{{"`4.3.3: The _sender_ is banned?`"}}
    4.3.3 -->|Yes| 4.3.3_reject(["`reject`"])
    4.3.3 -->|No| 4.3.4{{"`4.3.4: The _join_rule_ is _invite_ or _knock_ and membership state is _invite_ or _join_?`"}}
    4.3.4 -->|Yes| 4.3.4_allow(["`allow`"])
    4.3.4 -->|No| 4.3.5{{"`4.3.5: The _join_rule_ is _restricted_ or _knock_restricted_?`"}}
    4.3.5 -->|Yes| 4.3.5.1{{"`4.3.5.1: Membership state is _join_ or _invite_?`"}}
    4.3.5.1 -->|Yes| 4.3.5.1_allow(["`allow`"])
    4.3.5.1 -->|No| 4.3.5.2{{"`4.3.5.2: The _join_authorised_via_users_server_ key in _content_ is not a user with sufficient permission to invite other users?`"}}
    4.3.5.2 -->|Yes| 4.3.5.2_reject(["`reject`"])
    4.3.5.2 -->|No| 4.3.5.3(["`allow`"])
    4.3.5 -->|No| 4.3.6{{"`4.3.6: The _join_rule_ is _public_?`"}}
    4.3.6 -->|Yes| 4.3.6_allow(["`allow`"])
    4.3.6 -->|No| 4.3.7(["`reject`"])
    4.3 -->|No| 4.4{{"`4.4: _membership_ is _invite_?`"}}
    4.4 -->|Yes| 4.4.1{{"`4.4.1: _content_ has a _third_party_invite_ property?`"}}
    4.4.1 -->|Yes| 4.4.1.1{{"`4.4.1.1: *target user* is banned?`"}}
    4.4.1.1 -->|Yes| 4.4.1.1_reject(["`reject`"])
    4.4.1.1 -->|No| 4.4.1.2{{"`4.4.1.2: _content.third_party_invite_ does not have a _signed_ property?`"}}
    4.4.1.2 -->|Yes| 4.4.1.2_reject(["`reject`"])
    4.4.1.2 -->|No| 4.4.1.3{{"`4.4.1.3: _signed_ does not have _mxid_ and _token_ properties?`"}}
    4.4.1.3 -->|Yes| 4.4.1.3_reject(["`reject`"])
    4.4.1.3 -->|No| 4.4.1.4{{"`4.4.1.4: _mxid_ does not match _state_key_?`"}}
    4.4.1.4 -->|Yes| 4.4.1.4_reject(["`reject`"])
    4.4.1.4 -->|No| 4.4.1.5{{"`4.4.1.5: There is no _m.room.third_party_invite_ event in the current room state with _state_key_ matching _token_?`"}}
    4.4.1.5 -->|Yes| 4.4.1.5_reject(["`reject`"])
    4.4.1.5 -->|No| 4.4.1.6{{"`4.4.1.6: _sender_ does not match _sender_ of the _m.room.third_party_invite_?`"}}
    4.4.1.6 -->|Yes| 4.4.1.6_reject(["`reject`"])
    4.4.1.6 -->|No| 4.4.1.7{{"`4.4.1.7: Any signature in _signed_ matches any public key in the _m.room.third_party_invite_ event? The public keys are in _content_ of _m.room.third_party_invite_ as: 1.  A single public key in the _public_key_ property. 2.  A list of public keys in the _public_keys_ property.`"}}
    4.4.1.7 -->|Yes| 4.4.1.7_allow(["`allow`"])
    4.4.1.7 -->|No| 4.4.1.8(["`reject`"])
    4.4.1 -->|No| 4.4.2{{"`4.4.2: The _sender_'s current membership state is not _join_?`"}}
    4.4.2 -->|Yes| 4.4.2_reject(["`reject`"])
    4.4.2 -->|No| 4.4.3{{"`4.4.3: *target user*'s current membership state is _join_ or _ban_?`"}}
    4.4.3 -->|Yes| 4.4.3_reject(["`reject`"])
    4.4.3 -->|No| 4.4.4{{"`4.4.4: The _sender_'s power level is greater than or equal to the *invite level*?`"}}
    4.4.4 -->|Yes| 4.4.4_allow(["`allow`"])
    4.4.4 -->|No| 4.4.5(["`reject`"])
    4.4 -->|No| 4.5{{"`4.5: _membership_ is _leave_?`"}}
    4.5 -->|Yes| 4.5.1{{"`4.5.1: The _sender_ matches _state_key_, allow if and only if that user's current membership state is _invite_, _join_, or _knock_?`"}}
    4.5.1 -->|Yes| 4.5.1_allow(["`allow`"])
    4.5.1 -->|No| 4.5.2{{"`4.5.2: The _sender_'s current membership state is not _join_?`"}}
    4.5.2 -->|Yes| 4.5.2_reject(["`reject`"])
    4.5.2 -->|No| 4.5.3{{"`4.5.3: The *target user*'s current membership state is _ban_, and the _sender_'s power level is less than the *ban level*?`"}}
    4.5.3 -->|Yes| 4.5.3_reject(["`reject`"])
    4.5.3 -->|No| 4.5.4{{"`4.5.4: The _sender_'s power level is greater than or equal to the *kick level*, and the *target user*'s power level is less than the _sender_'s power level?`"}}
    4.5.4 -->|Yes| 4.5.4_allow(["`allow`"])
    4.5.4 -->|No| 4.5.5(["`reject`"])
    4.5 -->|No| 4.6{{"`4.6: _membership_ is _ban_?`"}}
    4.6 -->|Yes| 4.6.1{{"`4.6.1: The _sender_'s current membership state is not _join_?`"}}
    4.6.1 -->|Yes| 4.6.1_reject(["`reject`"])
    4.6.1 -->|No| 4.6.2{{"`4.6.2: The _sender_'s power level is greater than or equal to the *ban level*, and the *target user*'s power level is less than the _sender_'s power level?`"}}
    4.6.2 -->|Yes| 4.6.2_allow(["`allow`"])
    4.6.2 -->|No| 4.6.3(["`reject`"])
    4.6 -->|No| 4.7{{"`4.7: _membership_ is _knock_?`"}}
    4.7 -->|Yes| 4.7.1{{"`4.7.1: The _join_rule_ is anything other than _knock_ or _knock_restricted_?`"}}
    4.7.1 -->|Yes| 4.7.1_reject(["`reject`"])
    4.7.1 -->|No| 4.7.2{{"`4.7.2: _sender_ does not match _state_key_?`"}}
    4.7.2 -->|Yes| 4.7.2_reject(["`reject`"])
    4.7.2 -->|No| 4.7.3{{"`4.7.3: The _sender_'s current membership is not _ban_, _invite_, or _join_?`"}}
    4.7.3 -->|Yes| 4.7.3_allow(["`allow`"])
    4.7.3 -->|No| 4.7.4(["`reject`"])
    4.7 -->|No| 4.8(["`Otherwise, the membership is unknown. Reject.`"])
  end

  subgraph "Step 5"
    4 -->|No| 5{{"`5: The _sender_'s current membership state is not _join_?`"}}
    5 -->|Yes| 5_reject(["`reject`"])
  end

  subgraph "Step 6"
    5 -->|No| 6{{"`6: Type is _m.room.third_party_invite_?`"}}
    6 -->|Yes| 6.1{{"`6.1: _sender_'s current power level is greater than or equal to the *invite level*?`"}}
    6.1 -->|Yes| 6.1_allow(["`allow`"])
    6.1 -->|No| 6.1_reject(["`reject`"])
  end

  subgraph "Step 7"
    6 -->|No| 7{{"`7: The event type's *required power level* is greater than the _sender_'s power level?`"}}
    7 -->|Yes| 7_reject(["`reject`"])
  end

  subgraph "Step 8"
    7 -->|No| 8{{"`8: The event has a _state_key_ that starts with an _@_ and does not match the _sender_?`"}}
    8 -->|Yes| 8_reject(["`reject`"])
  end

  subgraph "Step 9"
    8 -->|No| 9{{"`9: Type is _m.room.power_levels_?`"}}
    9 -->|Yes| 9.1{{"`9.1: Any of the properties _users_default_, _events_default_, _state_default_, _ban_, _redact_, _kick_, or _invite_ in _content_ are present and not an integer?`"}}
    9.1 -->|Yes| 9.1_reject(["`reject`"])
    9.1 -->|No| 9.2{{"`9.2: Either of the properties _events_ or _notifications_ in _content_ are present and not an object with values that are integers?`"}}
    9.2 -->|Yes| 9.2_reject(["`reject`"])
    9.2 -->|No| 9.3{{"`9.3: The _users_ property in _content_ is not an object with keys that are valid user IDs with values that are integers?`"}}
    9.3 -->|Yes| 9.3_reject(["`reject`"])
    9.3 -->|No| 9.4{{"`9.4: There is no previous _m.room.power_levels_ event in the room?`"}}
    9.4 -->|Yes| 9.4_allow(["`allow`"])
    9.4 -->|No| 9.5["`9.5: For the properties _users_default_, _events_default_, _state_default_, _ban_, _redact_, _kick_, _invite_ check if they were added, changed or removed. For each found alteration`"]
    9.5 --> 9.5.1{{"`9.5.1: The current value is higher than the _sender_'s current power level?`"}}
    9.5.1 -->|Yes| 9.5.1_reject(["`reject`"])
    9.5.1 -->|No| 9.5.2{{"`9.5.2: The new value is higher than the _sender_'s current power level?`"}}
    9.5.2 -->|Yes| 9.5.2_reject(["`reject`"])
    9.5.2 -->|No| 9.6["`9.6: For each entry being changed in, or removed from, the _events_ or _notifications_ properties`"]
    9.6 --> 9.6.1{{"`9.6.1: The current value is greater than the _sender_'s current power level?`"}}
    9.6.1 -->|Yes| 9.6.1_reject(["`reject`"])
    9.6.1 -->|No| 9.7["`9.7: For each entry being added to, or changed in, the _events_ or _notifications_ properties`"]
    9.7 --> 9.7.1{{"`9.7.1: The new value is greater than the _sender_'s current power level?`"}}
    9.7.1 -->|Yes| 9.7.1_reject(["`reject`"])
    9.7.1 -->|No| 9.8["`9.8: For each entry being changed in, or removed from, the _users_ property, other than the _sender_'s own entry`"]
    9.8 --> 9.8.1{{"`9.8.1: The current value is greater than or equal to the _sender_'s current power level?`"}}
    9.8.1 -->|Yes| 9.8.1_reject(["`reject`"])
    9.8.1 -->|No| 9.9["`9.9: For each entry being added to, or changed in, the _users_ property`"]
    9.9 --> 9.9.1{{"`9.9.1: The new value is greater than the _sender_'s current power level?`"}}
    9.9.1 -->|Yes| 9.9.1_reject(["`reject`"])
    9.9.1 -->|No| 9.10(["`allow`"])
  end

  subgraph "Step 10"
    9 -->|No| 10(["`allow`"])
  end

Loading

flowchart TD

    start --> 1{{"`1: {{< changed-in v=11 >}} Type is _m.room.create_?`"}}

  subgraph "Step 1"
    1 -->|Yes| 1.1{{"`1.1: it has any _prev_events_?}} It has any _prev_events_?`"}}
    1.1 -->|Yes| 1.1_reject(["`reject`"])
    1.1 -->|No| 1.2{{"`1.2: the domain of the _room_id_ does not match the domain of the _sender_?}} The domain of the _room_id_ does not match the domain of the _sender_?`"}}
    1.2 -->|Yes| 1.2_reject(["`reject`"])
    1.2 -->|No| 1.3{{"`1.3: _content.room_version_ is present and is not a recognised version?}} _content.room_version_ is present and is not a recognised version?`"}}
    1.3 -->|Yes| 1.3_reject(["`reject`"])
    1.3 -->|No| 1.4(["`allow`"])
  end

  subgraph "Step 2"
    1 -->|No| 2["`2: Considering the event's _auth_events_`"]
    2 --> 2.1{{"`2.1: there are duplicate entries for a given _type_ and _state_key_ pair?}} There are duplicate entries for a given _type_ and _state_key_ pair?`"}}
    2.1 -->|Yes| 2.1_reject(["`reject`"])
    2.1 -->|No| 2.2{{"`2.2: there are entries whose _type_ and _state_key_ don't match those specified by the [auth events selection](/server-server-api#auth-events-selection) algorithm described in the server specification?}} There are entries whose _type_ and _state_key_ don't match those specified by the [auth events selection](/server-server-api#auth-events-selection) algorithm described in the server specification?`"}}
    2.2 -->|Yes| 2.2_reject(["`reject`"])
    2.2 -->|No| 2.3{{"`2.3: there are entries which were themselves rejected under the [checks performed on receipt of a PDU](/server-server-api/#checks-performed-on-receipt-of-a-pdu)?}} There are entries which were themselves rejected under the [checks performed on receipt of a PDU](/server-server-api/#checks-performed-on-receipt-of-a-pdu)?`"}}
    2.3 -->|Yes| 2.3_reject(["`reject`"])
    2.3 -->|No| 2.4{{"`2.4: there is no _m.room.create_ event among the entries?}} There is no _m.room.create_ event among the entries?`"}}
    2.4 -->|Yes| 2.4_reject(["`reject`"])
  end

  subgraph "Step 3"
    2.4 -->|No| 3{{"`3: the _content_ of the _m.room.create_ event in the room state has the property _m.federate_ set to _false_, and the _sender_ domain of the event does not match the _sender_ domain of the create event?}} The _content_ of the _m.room.create_ event in the room state has the property _m.federate_ set to _false_, and the _sender_ domain of the event does not match the _sender_ domain of the create event?`"}}
    3 -->|Yes| 3_reject(["`reject`"])
  end

    3 -->|No| 4{{"`4`"}}

Loading

flowchart TD

    3 -->|No| 4{{"`4: type is _m.room.member_?}} Type is _m.room.member_?`"}}

  subgraph "Step 4"
    4 -->|Yes| 4.1{{"`4.1: there is no _state_key_ property, or no _membership_ property in _content_?}} There is no _state_key_ property, or no _membership_ property in _content_?`"}}
    4.1 -->|Yes| 4.1_reject(["`reject`"])
    4.1 -->|No| 4.2{{"`4.2: _content_ has a _join_authorised_via_users_server_ key?}} _content_ has a _join_authorised_via_users_server_ key?`"}}
    4.2 -->|Yes| 4.2.1{{"`4.2.1: the event is not validly signed by the homeserver of the user ID denoted by the key?}} The event is not validly signed by the homeserver of the user ID denoted by the key?`"}}
    4.2.1 -->|Yes| 4.2.1_reject(["`reject`"])
    4.2.1 -->|No| 4.3{{"`4.3: _membership_ is _join_?}} _membership_ is _join_?`"}}
    4.2 -->|No| 4.3
    4.3 -->|Yes| 4.3.1{{"`4.3.1: {{< changed-in v=11 >}} The only previous event is an _m.room.create_ and the _state_key_ is the sender?`"}}
    4.3.1 -->|Yes| 4.3.1_allow(["`allow`"])
    4.3.1 -->|No| 4.3.2{{"`4.3.2: the _sender_ does not match _state_key_?}} The _sender_ does not match _state_key_?`"}}
    4.3.2 -->|Yes| 4.3.2_reject(["`reject`"])
    4.3.2 -->|No| 4.3.3{{"`4.3.3: the _sender_ is banned?}} The _sender_ is banned?`"}}
    4.3.3 -->|Yes| 4.3.3_reject(["`reject`"])
    4.3.3 -->|No| 4.3.4{{"`4.3.4: the _join_rule_ is _invite_ or _knock_ and membership state is _invite_ or _join_?}} The _join_rule_ is _invite_ or _knock_ and membership state is _invite_ or _join_?`"}}
    4.3.4 -->|Yes| 4.3.4_allow(["`allow`"])
    4.3.4 -->|No| 4.3.5{{"`4.3.5: the _join_rule_ is _restricted_ or _knock_restricted_?}} The _join_rule_ is _restricted_ or _knock_restricted_?`"}}
    4.3.5 -->|Yes| 4.3.5.1{{"`4.3.5.1: membership state is _join_ or _invite_?}} Membership state is _join_ or _invite_?`"}}
    4.3.5.1 -->|Yes| 4.3.5.1_allow(["`allow`"])
    4.3.5.1 -->|No| 4.3.5.2{{"`4.3.5.2: the _join_authorised_via_users_server_ key in _content_ is not a user with sufficient permission to invite other users?}} The _join_authorised_via_users_server_ key in _content_ is not a user with sufficient permission to invite other users?`"}}
    4.3.5.2 -->|Yes| 4.3.5.2_reject(["`reject`"])
    4.3.5.2 -->|No| 4.3.5.3(["`allow`"])
    4.3.5 -->|No| 4.3.6{{"`4.3.6: the _join_rule_ is _public_?}} The _join_rule_ is _public_?`"}}
    4.3.6 -->|Yes| 4.3.6_allow(["`allow`"])
    4.3.6 -->|No| 4.3.7(["`reject`"])
    4.3 -->|No| 4.4{{"`4.4: _membership_ is _invite_?}} _membership_ is _invite_?`"}}
    4.4 -->|Yes| 4.4.1{{"`4.4.1: _content_ has a _third_party_invite_ property?}} _content_ has a _third_party_invite_ property?`"}}
    4.4.1 -->|Yes| 4.4.1.1{{"`4.4.1.1: *target user* is banned?}} *target user* is banned?`"}}
    4.4.1.1 -->|Yes| 4.4.1.1_reject(["`reject`"])
    4.4.1.1 -->|No| 4.4.1.2{{"`4.4.1.2: _content.third_party_invite_ does not have a _signed_ property?}} _content.third_party_invite_ does not have a _signed_ property?`"}}
    4.4.1.2 -->|Yes| 4.4.1.2_reject(["`reject`"])
    4.4.1.2 -->|No| 4.4.1.3{{"`4.4.1.3: _signed_ does not have _mxid_ and _token_ properties?}} _signed_ does not have _mxid_ and _token_ properties?`"}}
    4.4.1.3 -->|Yes| 4.4.1.3_reject(["`reject`"])
    4.4.1.3 -->|No| 4.4.1.4{{"`4.4.1.4: _mxid_ does not match _state_key_?}} _mxid_ does not match _state_key_?`"}}
    4.4.1.4 -->|Yes| 4.4.1.4_reject(["`reject`"])
    4.4.1.4 -->|No| 4.4.1.5{{"`4.4.1.5: there is no _m.room.third_party_invite_ event in the current room state with _state_key_ matching _token_?}} There is no _m.room.third_party_invite_ event in the current room state with _state_key_ matching _token_?`"}}
    4.4.1.5 -->|Yes| 4.4.1.5_reject(["`reject`"])
    4.4.1.5 -->|No| 4.4.1.6{{"`4.4.1.6: _sender_ does not match _sender_ of the _m.room.third_party_invite_?}} _sender_ does not match _sender_ of the _m.room.third_party_invite_?`"}}
    4.4.1.6 -->|Yes| 4.4.1.6_reject(["`reject`"])
    4.4.1.6 -->|No| 4.4.1.7{{"`4.4.1.7: any signature in _signed_ matches any public key in the _m.room.third_party_invite_ event? The public keys are in _content_ of _m.room.third_party_invite_ as: 1.  A single public key in the _public_key_ property. 2.  A list of public keys in the _public_keys_ property.}} Any signature in _signed_ matches any public key in the _m.room.third_party_invite_ event? The public keys are in _content_ of _m.room.third_party_invite_ as: 1.  A single public key in the _public_key_ property. 2.  A list of public keys in the _public_keys_ property.`"}}
    4.4.1.7 -->|Yes| 4.4.1.7_allow(["`allow`"])
    4.4.1.7 -->|No| 4.4.1.8(["`reject`"])
    4.4.1 -->|No| 4.4.2{{"`4.4.2: the _sender_'s current membership state is not _join_?}} The _sender_'s current membership state is not _join_?`"}}
    4.4.2 -->|Yes| 4.4.2_reject(["`reject`"])
    4.4.2 -->|No| 4.4.3{{"`4.4.3: *target user*'s current membership state is _join_ or _ban_?}} *target user*'s current membership state is _join_ or _ban_?`"}}
    4.4.3 -->|Yes| 4.4.3_reject(["`reject`"])
    4.4.3 -->|No| 4.4.4{{"`4.4.4: the _sender_'s power level is greater than or equal to the *invite level*?}} The _sender_'s power level is greater than or equal to the *invite level*?`"}}
    4.4.4 -->|Yes| 4.4.4_allow(["`allow`"])
    4.4.4 -->|No| 4.4.5(["`reject`"])
    4.4 -->|No| 4.5{{"`4.5: _membership_ is _leave_?}} _membership_ is _leave_?`"}}
    4.5 -->|Yes| 4.5.1{{"`4.5.1: the _sender_ matches _state_key_, allow if and only if that user's current membership state is _invite_, _join_, or _knock_?}} The _sender_ matches _state_key_, allow if and only if that user's current membership state is _invite_, _join_, or _knock_?`"}}
    4.5.1 -->|Yes| 4.5.1_allow(["`allow`"])
    4.5.1 -->|No| 4.5.2{{"`4.5.2: the _sender_'s current membership state is not _join_?}} The _sender_'s current membership state is not _join_?`"}}
    4.5.2 -->|Yes| 4.5.2_reject(["`reject`"])
    4.5.2 -->|No| 4.5.3{{"`4.5.3: the *target user*'s current membership state is _ban_, and the _sender_'s power level is less than the *ban level*?}} The *target user*'s current membership state is _ban_, and the _sender_'s power level is less than the *ban level*?`"}}
    4.5.3 -->|Yes| 4.5.3_reject(["`reject`"])
    4.5.3 -->|No| 4.5.4{{"`4.5.4: the _sender_'s power level is greater than or equal to the *kick level*, and the *target user*'s power level is less than the _sender_'s power level?}} The _sender_'s power level is greater than or equal to the *kick level*, and the *target user*'s power level is less than the _sender_'s power level?`"}}
    4.5.4 -->|Yes| 4.5.4_allow(["`allow`"])
    4.5.4 -->|No| 4.5.5(["`reject`"])
    4.5 -->|No| 4.6{{"`4.6: _membership_ is _ban_?}} _membership_ is _ban_?`"}}
    4.6 -->|Yes| 4.6.1{{"`4.6.1: the _sender_'s current membership state is not _join_?}} The _sender_'s current membership state is not _join_?`"}}
    4.6.1 -->|Yes| 4.6.1_reject(["`reject`"])
    4.6.1 -->|No| 4.6.2{{"`4.6.2: the _sender_'s power level is greater than or equal to the *ban level*, and the *target user*'s power level is less than the _sender_'s power level?}} The _sender_'s power level is greater than or equal to the *ban level*, and the *target user*'s power level is less than the _sender_'s power level?`"}}
    4.6.2 -->|Yes| 4.6.2_allow(["`allow`"])
    4.6.2 -->|No| 4.6.3(["`reject`"])
    4.6 -->|No| 4.7{{"`4.7: _membership_ is _knock_?}} _membership_ is _knock_?`"}}
    4.7 -->|Yes| 4.7.1{{"`4.7.1: the _join_rule_ is anything other than _knock_ or _knock_restricted_?}} The _join_rule_ is anything other than _knock_ or _knock_restricted_?`"}}
    4.7.1 -->|Yes| 4.7.1_reject(["`reject`"])
    4.7.1 -->|No| 4.7.2{{"`4.7.2: _sender_ does not match _state_key_?}} _sender_ does not match _state_key_?`"}}
    4.7.2 -->|Yes| 4.7.2_reject(["`reject`"])
    4.7.2 -->|No| 4.7.3{{"`4.7.3: the _sender_'s current membership is not _ban_, _invite_, or _join_?}} The _sender_'s current membership is not _ban_, _invite_, or _join_?`"}}
    4.7.3 -->|Yes| 4.7.3_allow(["`allow`"])
    4.7.3 -->|No| 4.7.4(["`reject`"])
    4.7 -->|No| 4.8(["`Otherwise, the membership is unknown. Reject.`"])
  end

    4 -->|No| 5{{"`5`"}}

Loading

flowchart TD

    5 -->|No| 6{{"`6: type is _m.room.third_party_invite_?}} Type is _m.room.third_party_invite_?`"}}

  subgraph "Step 6"
    6 -->|Yes| 6.1{{"`6.1: _sender_'s current power level is greater than or equal to the *invite level*?}} _sender_'s current power level is greater than or equal to the *invite level*?`"}}
    6.1 -->|Yes| 6.1_allow(["`allow`"])
    6.1 -->|No| 6.1_reject(["`reject`"])
  end

  subgraph "Step 7"
    6 -->|No| 7{{"`7: the event type's *required power level* is greater than the _sender_'s power level?}} The event type's *required power level* is greater than the _sender_'s power level?`"}}
    7 -->|Yes| 7_reject(["`reject`"])
  end

  subgraph "Step 8"
    7 -->|No| 8{{"`8: the event has a _state_key_ that starts with an _@_ and does not match the _sender_?}} The event has a _state_key_ that starts with an _@_ and does not match the _sender_?`"}}
    8 -->|Yes| 8_reject(["`reject`"])
  end

  subgraph "Step 9"
    8 -->|No| 9{{"`9: type is _m.room.power_levels_?}} Type is _m.room.power_levels_?`"}}
    9 -->|Yes| 9.1{{"`9.1: any of the properties _users_default_, _events_default_, _state_default_, _ban_, _redact_, _kick_, or _invite_ in _content_ are present and not an integer?}} Any of the properties _users_default_, _events_default_, _state_default_, _ban_, _redact_, _kick_, or _invite_ in _content_ are present and not an integer?`"}}
    9.1 -->|Yes| 9.1_reject(["`reject`"])
    9.1 -->|No| 9.2{{"`9.2: either of the properties _events_ or _notifications_ in _content_ are present and not an object with values that are integers?}} Either of the properties _events_ or _notifications_ in _content_ are present and not an object with values that are integers?`"}}
    9.2 -->|Yes| 9.2_reject(["`reject`"])
    9.2 -->|No| 9.3{{"`9.3: the _users_ property in _content_ is not an object with keys that are valid user IDs with values that are integers?}} The _users_ property in _content_ is not an object with keys that are valid user IDs with values that are integers?`"}}
    9.3 -->|Yes| 9.3_reject(["`reject`"])
    9.3 -->|No| 9.4{{"`9.4: there is no previous _m.room.power_levels_ event in the room?}} There is no previous _m.room.power_levels_ event in the room?`"}}
    9.4 -->|Yes| 9.4_allow(["`allow`"])
    9.4 -->|No| 9.5["`9.5: For the properties _users_default_, _events_default_, _state_default_, _ban_, _redact_, _kick_, _invite_ check if they were added, changed or removed. For each found alteration`"]
    9.5 --> 9.5.1{{"`9.5.1: the current value is higher than the _sender_'s current power level?}} The current value is higher than the _sender_'s current power level?`"}}
    9.5.1 -->|Yes| 9.5.1_reject(["`reject`"])
    9.5.1 -->|No| 9.5.2{{"`9.5.2: the new value is higher than the _sender_'s current power level?}} The new value is higher than the _sender_'s current power level?`"}}
    9.5.2 -->|Yes| 9.5.2_reject(["`reject`"])
    9.5.2 -->|No| 9.6["`9.6: For each entry being changed in, or removed from, the _events_ or _notifications_ properties`"]
    9.6 --> 9.6.1{{"`9.6.1: the current value is greater than the _sender_'s current power level?}} The current value is greater than the _sender_'s current power level?`"}}
    9.6.1 -->|Yes| 9.6.1_reject(["`reject`"])
    9.6.1 -->|No| 9.7["`9.7: For each entry being added to, or changed in, the _events_ or _notifications_ properties`"]
    9.7 --> 9.7.1{{"`9.7.1: the new value is greater than the _sender_'s current power level?}} The new value is greater than the _sender_'s current power level?`"}}
    9.7.1 -->|Yes| 9.7.1_reject(["`reject`"])
    9.7.1 -->|No| 9.8["`9.8: For each entry being changed in, or removed from, the _users_ property, other than the _sender_'s own entry`"]
    9.8 --> 9.8.1{{"`9.8.1: the current value is greater than or equal to the _sender_'s current power level?}} The current value is greater than or equal to the _sender_'s current power level?`"}}
    9.8.1 -->|Yes| 9.8.1_reject(["`reject`"])
    9.8.1 -->|No| 9.9["`9.9: For each entry being added to, or changed in, the _users_ property`"]
    9.9 --> 9.9.1{{"`9.9.1: the new value is greater than the _sender_'s current power level?}} The new value is greater than the _sender_'s current power level?`"}}
    9.9.1 -->|Yes| 9.9.1_reject(["`reject`"])
    9.9.1 -->|No| 9.10(["`allow`"])
  end

  subgraph "Step 10"
    9 -->|No| 10(["`allow`"])
  end

Loading

Dumb script used to generate the graphs above

#!/usr/bin/env python3

import re

input = """1.  {{< changed-in v=11 >}}
    If type is `m.room.create`:
    1.  If it has any `prev_events`, reject.
    2.  If the domain of the `room_id` does not match the domain of the
        `sender`, reject.
    3.  If `content.room_version` is present and is not a recognised
        version, reject.
    4.  Otherwise, allow.
2.  Considering the event's `auth_events`:
    1.  If there are duplicate entries for a given `type` and `state_key` pair,
        reject.
    2.  If there are entries whose `type` and `state_key` don't match those
        specified by the [auth events
        selection](/server-server-api#auth-events-selection)
        algorithm described in the server specification, reject.
    3.  If there are entries which were themselves rejected under the [checks
        performed on receipt of a
        PDU](/server-server-api/#checks-performed-on-receipt-of-a-pdu), reject.
    4. If there is no `m.room.create` event among the entries, reject.
3. If the `content` of the `m.room.create` event in the room state has the
   property `m.federate` set to `false`, and the `sender` domain of the event
   does not match the `sender` domain of the create event, reject.
4.  If type is `m.room.member`:
    1.  If there is no `state_key` property, or no `membership` property in
        `content`, reject.
    2.  If `content` has a `join_authorised_via_users_server`
        key:
        1.  If the event is not validly signed by the homeserver of the user ID denoted
            by the key, reject.
    3.  If `membership` is `join`:
        1.  {{< changed-in v=11 >}}
            If the only previous event is an `m.room.create` and the
            `state_key` is the sender, allow.
        2.  If the `sender` does not match `state_key`, reject.
        3.  If the `sender` is banned, reject.
        4.  If the `join_rule` is `invite` or `knock` then allow if
            membership state is `invite` or `join`.
        5.  If the `join_rule` is `restricted` or `knock_restricted`:
            1.  If membership state is `join` or `invite`, allow.
            2.  If the `join_authorised_via_users_server` key in `content`
                is not a user with sufficient permission to invite other
                users, reject.
            3.  Otherwise, allow.
        6.  If the `join_rule` is `public`, allow.
        7.  Otherwise, reject.
    4.  If `membership` is `invite`:
        1.  If `content` has a `third_party_invite` property:
            1.  If *target user* is banned, reject.
            2.  If `content.third_party_invite` does not have a `signed`
                property, reject.
            3.  If `signed` does not have `mxid` and `token` properties,
                reject.
            4.  If `mxid` does not match `state_key`, reject.
            5.  If there is no `m.room.third_party_invite` event in the
                current room state with `state_key` matching `token`,
                reject.
            6.  If `sender` does not match `sender` of the
                `m.room.third_party_invite`, reject.
            7.  If any signature in `signed` matches any public key in
                the `m.room.third_party_invite` event, allow. The public
                keys are in `content` of `m.room.third_party_invite` as:
                1.  A single public key in the `public_key` property.
                2.  A list of public keys in the `public_keys` property.
            8.  Otherwise, reject.
        2.  If the `sender`'s current membership state is not `join`,
            reject.
        3.  If *target user*'s current membership state is `join` or
            `ban`, reject.
        4.  If the `sender`'s power level is greater than or equal to
            the *invite level*, allow.
        5.  Otherwise, reject.
    5.  If `membership` is `leave`:
        1.  If the `sender` matches `state_key`, allow if and only if
            that user's current membership state is `invite`, `join`,
            or `knock`.
        2.  If the `sender`'s current membership state is not `join`,
            reject.
        3.  If the *target user*'s current membership state is `ban`,
            and the `sender`'s power level is less than the *ban level*,
            reject.
        4.  If the `sender`'s power level is greater than or equal to
            the *kick level*, and the *target user*'s power level is
            less than the `sender`'s power level, allow.
        5.  Otherwise, reject.
    6.  If `membership` is `ban`:
        1.  If the `sender`'s current membership state is not `join`,
            reject.
        2.  If the `sender`'s power level is greater than or equal to
            the *ban level*, and the *target user*'s power level is less
            than the `sender`'s power level, allow.
        3.  Otherwise, reject.
    7. If `membership` is `knock`:
        1.  If the `join_rule` is anything other than `knock` or
            `knock_restricted`, reject.
        2.  If `sender` does not match `state_key`, reject.
        3.  If the `sender`'s current membership is not `ban`, `invite`,
            or `join`, allow.
        4.  Otherwise, reject.
    8.  Otherwise, the membership is unknown. Reject.
5.  If the `sender`'s current membership state is not `join`, reject.
6.  If type is `m.room.third_party_invite`:
    1.  Allow if and only if `sender`'s current power level is greater
        than or equal to the *invite level*.
7.  If the event type's *required power level* is greater than the
    `sender`'s power level, reject.
8.  If the event has a `state_key` that starts with an `@` and does not
    match the `sender`, reject.
9. If type is `m.room.power_levels`:
    1.  If any of the properties `users_default`, `events_default`, `state_default`,
        `ban`, `redact`, `kick`, or `invite` in `content` are present and
        not an integer, reject.
    2.  If either of the properties `events` or `notifications` in `content`
        are present and not an object with values that are integers,
        reject.
    3.  If the `users` property in `content` is not an object with keys that
        are valid user IDs with values that are integers, reject.
    4.  If there is no previous `m.room.power_levels` event in the room,
        allow.
    5.  For the properties `users_default`, `events_default`, `state_default`,
        `ban`, `redact`, `kick`, `invite` check if they were added,
        changed or removed. For each found alteration:
        1.  If the current value is higher than the `sender`'s current
            power level, reject.
        2.  If the new value is higher than the `sender`'s current power
            level, reject.
    6.  For each entry being changed in, or removed from, the `events` or
        `notifications` properties:
        1.  If the current value is greater than the `sender`'s current
            power level, reject.
    7.  For each entry being added to, or changed in, the `events` or
        `notifications` properties:
        1.  If the new value is greater than the `sender`'s current power
            level, reject.
    8.  For each entry being changed in, or removed from, the `users` property,
        other than the `sender`'s own entry:
        1.  If the current value is greater than or equal to the `sender`'s
            current power level, reject.
    9.  For each entry being added to, or changed in, the `users` property:
        1.  If the new value is greater than the `sender`'s current power
            level, reject.
    10. Otherwise, allow.
10. Otherwise, allow.
"""

class Item(object):
    def __init__(self, id, level, number, text):
        self.id = id
        self.level = level
        self.number = number
        self.text = text
        self.edges = []
        self.is_if = True if re.match(r"^(If|Allow if and only if)\s+", re.sub(r"^\{\{[^\}]*\}\}\s*", "", text)) else False
        self.is_terminal = True if not self.is_if and re.match(r".*(allow|[Rr]eject)\.?$", text) else False
        self.text_written = False


def parse_line(line, stack):
    remainder = line

    level = len(re.match(r"^(\s*)", remainder).group(1))
    remainder = line.strip()

    number = re.match(r"^(\d*)", remainder).group(1)
    remainder = re.sub(r"^\d*\.?\s*", "", remainder)

    id = ".".join([i.number for i in stack if i.level < level and i.number] + [number])

    return Item(id, level, number, remainder)


def try_add_edge(item_from, item_to, indentation):
    # Cannot connect from allow item
    if item_from.is_terminal:
        return False

    # Connect from unfinished if item
    if item_from.is_if and len(item_from.edges) < 2:
        edge = False if len(item_from.edges) > 0 and item_from.edges[0] == True else True
    # Connect from unfinished step item
    elif not item_from.is_if and len(item_from.edges) < 1:
        edge = None
    # Cannot connect from finished item
    else:
        return False

    add_edge(item_from, item_to, edge, indentation)
    return True


def add_edge(item_from, item_to, edge, indentation):
    label = ""
    if edge == True:
        label = "|Yes|"
    elif edge == False:
        label = "|No|"
    print(f"{" " * indentation}{item_from.id} -->{label} {create_node(item_to)}")
    item_from.edges.append(edge)


def create_node(item):
    braces = ("[", "]")
    prefix = f"{item.id}: " if item.number and not item.is_terminal else ""
    label = item.text.replace("`", "_").rstrip(":")
    if item.is_if:
        label = re.sub(r"If\s*", "", label)
        label = re.sub(r"\s*, reject\.$", "", label)
        label = re.sub(r"\s*, allow\.$", "", label)
        label = re.sub(r"\s*then allow if\s*", " and ", label)
        label = re.sub(r"Allow if and only if\s*", "", label)
        if re.match(r".*,\s*allow\..*", label):
            label = re.sub(r",\s*allow.", "?", label)
        else:
            label = label.rstrip(".") + "?"
        label = label[0].capitalize() + label[1:]
        braces = ("{{", "}}")
    elif re.match(r".*\s+(allow|[Rr]eject)\.?", label) or label == "reject" or not item.number:
        label = re.sub(r"^Otherwise, allow\.$", "allow", label)
        label = re.sub(r"^Otherwise, reject\.$", "reject", label)
        braces = ("([", "])")
    description = f"{braces[0]}\"`{prefix}{label}`\"{braces[1]}" if not item.text_written else ""
    item.text_written = True
    return f"{item.id}{description}"


if __name__ == "__main__":
    lines = []

    # These enumerations are not actually auth rule steps
    non_steps = [
        "1.  A single public key in the `public_key` property.",
        "2.  A list of public keys in the `public_keys` property."
    ]

    # Unwrap lines
    for line in input.splitlines():
        if lines and (not re.match(r"\s*\d+\.", line) or line.strip() in non_steps):
            lines[-1] += " " + line.strip()
        else:
            lines.append(line)

    root = Item("start", -1, None, "event")
    stack = [root]
    subgraph = None

    print("flowchart TD\n")

    indentation = 2

    for line in lines:
        item = parse_line(line, stack)

        # Close / open subgraph
        if item.id.split(".")[0] != subgraph:
            if subgraph:
                indentation -= 2
                print(f"{" " * indentation}end\n")
            subgraph = item.id.split(".")[0]
            print(f"{" " * indentation}subgraph \"Step {subgraph}\"")
            indentation += 2

        # Try connecting from all unfinished previous items up to the current level
        edge_added = False
        for previous in reversed([i for i in stack if i.level >= item.level]):
            edge_added = try_add_edge(previous, item, indentation)

        # If no item connected, try connecting the topmost previous item
        if not edge_added:
            try_add_edge(stack[-1], item, indentation)

        # Pop all previous items up to the current level and push the current item
        while stack[-1].level >= item.level:
            stack.pop()
        stack.append(item)

        # Expand "If ..., reject/allow."
        if item.is_if:
            if item.text.startswith("Allow if and only if"):
                item_to = Item(item.id + "_allow", None, None, "allow")
                add_edge(item, item_to, True, indentation)
                item_to = Item(item.id + "_reject", None, None, "reject")
                add_edge(item, item_to, False, indentation)
            elif item.text.endswith(", reject."):
                item_to = Item(item.id + "_reject", None, None, "reject")
                add_edge(item, item_to, True, indentation)
            elif item.text.endswith(", allow.") or re.match(r".*\s+allow[\s\.].*", item.text):
                item_to = Item(item.id + "_allow", None, None, "allow")
                add_edge(item, item_to, True, indentation)

    # Close last subgraph
    indentation -= 2
    print(f"{" " * indentation}end")

[richvdh]

Yeah, that's not exactly easy to follow 🤔

[Johennes]

Maybe instead of slicing the graph horizontally, we could split it vertically by recursively extracting subgraphs for the larger steps that don't fall through. All the graphs below feel sort of digestible. Just that it's a lot of them.

Top-level chart

flowchart TD

    start --> 1{{"`1: {{< changed-in v=11 >}} type is _m.room.create_?`"}}

  subgraph "Auth rules"
    1 -->|Yes| 1.1["`<a href='#'>Go to 1.1</a>`"]

    1 -->|No| 2["`2: Considering the event's _auth_events_`"]
    2 --> 2.1{{"`2.1: There are duplicate entries for a given _type_ and _state_key_ pair?`"}}
    2.1 -->|Yes| 2.1_reject(["`reject`"])
    2.1 -->|No| 2.2{{"`2.2: There are entries whose _type_ and _state_key_ don't match those specified by the [auth events selection](/server-server-api#auth-events-selection) algorithm described in the server specification?`"}}
    2.2 -->|Yes| 2.2_reject(["`reject`"])
    2.2 -->|No| 2.3{{"`2.3: There are entries which were themselves rejected under the [checks performed on receipt of a PDU](/server-server-api/#checks-performed-on-receipt-of-a-pdu)?`"}}
    2.3 -->|Yes| 2.3_reject(["`reject`"])
    2.3 -->|No| 2.4{{"`2.4: There is no _m.room.create_ event among the entries?`"}}
    2.4 -->|Yes| 2.4_reject(["`reject`"])

    2.4 -->|No| 3{{"`3: The _content_ of the _m.room.create_ event in the room state has the property _m.federate_ set to _false_, and the _sender_ domain of the event does not match the _sender_ domain of the create event?`"}}
    3 -->|Yes| 3_reject(["`reject`"])

    3 -->|No| 4{{"`4: Type is _m.room.member_?`"}}
    4 -->|Yes| 4.1["`<a href='#'>Go to 4.1</a>`"]

    4 -->|No| 5{{"`5: The _sender_'s current membership state is not _join_?`"}}
    5 -->|Yes| 5_reject(["`reject`"])

    5 -->|No| 6{{"`6: Type is _m.room.third_party_invite_?`"}}
    6 -->|Yes| 6.1{{"`6.1: _sender_'s current power level is greater than or equal to the *invite level*?`"}}
    6.1 -->|Yes| 6.1_allow(["`allow`"])
    6.1 -->|No| 6.1_reject(["`reject`"])

    6 -->|No| 7{{"`7: The event type's *required power level* is greater than the _sender_'s power level?`"}}
    7 -->|Yes| 7_reject(["`reject`"])

    7 -->|No| 8{{"`8: The event has a _state_key_ that starts with an _@_ and does not match the _sender_?`"}}
    8 -->|Yes| 8_reject(["`reject`"])

    8 -->|No| 9{{"`9: Type is _m.room.power_levels_?`"}}
    9 -->|Yes| 9.1["`<a href='#'>Go to 9.1</a>`"]

    9 -->|No| 10(["`allow`"])
  end

Loading

Subgraph starting at 1.1

flowchart TD

    1{{"`1: {{< changed-in v=11 >}} type is _m.room.create_?`"}} -->|Yes| 1.1{{"`1.1: It has any _prev_events_?`"}}

  subgraph "Subgraph 1.1"
    1.1 -->|Yes| 1.1_reject(["`reject`"])
    1.1 -->|No| 1.2{{"`1.2: The domain of the _room_id_ does not match the domain of the _sender_?`"}}
    1.2 -->|Yes| 1.2_reject(["`reject`"])
    1.2 -->|No| 1.3{{"`1.3: _content.room_version_ is present and is not a recognised version?`"}}
    1.3 -->|Yes| 1.3_reject(["`reject`"])
    1.3 -->|No| 1.4(["`allow`"])
  end

Loading

Subgraph starting at 4.1

flowchart TD

    4{{"`4: Type is _m.room.member_?`"}} -->|Yes| 4.1{{"`4.1: There is no _state_key_ property, or no _membership_ property in _content_?`"}}

  subgraph "Subgraph 4.1"
    4.1 -->|Yes| 4.1_reject(["`reject`"])
    4.1 -->|No| 4.2{{"`4.2: _content_ has a _join_authorised_via_users_server_ key?`"}}
    4.2 -->|Yes| 4.2.1{{"`4.2.1: The event is not validly signed by the homeserver of the user ID denoted by the key?`"}}
    4.2.1 -->|Yes| 4.2.1_reject(["`reject`"])
    4.2.1 -->|No| 4.3{{"`4.3: _membership_ is _join_?`"}}
    4.2 -->|No| 4.3
    4.3 -->|Yes| 4.3.1["`<a href='#'>Go to 4.3.1</a>`"]
    4.3 -->|No| 4.4{{"`4.4: _membership_ is _invite_?`"}}
    4.4 -->|Yes| 4.4.1["`<a href='#'>Go to 4.4.1</a>`"]
    4.4 -->|No| 4.5{{"`4.5: _membership_ is _leave_?`"}}
    4.5 -->|Yes| 4.5.1["`<a href='#'>Go to 4.5.1</a>`"]
    4.5 -->|No| 4.6{{"`4.6: _membership_ is _ban_?`"}}
    4.6 -->|Yes| 4.6.1["`<a href='#'>Go to 4.6.1</a>`"]
    4.6 -->|No| 4.7{{"`4.7: _membership_ is _knock_?`"}}
    4.7 -->|Yes| 4.7.1["`<a href='#'>Go to 4.7.1</a>`"]
    4.7 -->|No| 4.8(["`Otherwise, the membership is unknown. Reject.`"])
  end

Loading

Subgraph starting at 4.3.1

flowchart TD

    4.3{{"`4.3: _membership_ is _join_?`"}} -->|Yes| 4.3.1{{"`4.3.1: {{< changed-in v=11 >}} the only previous event is an _m.room.create_ and the _state_key_ is the sender?`"}}

  subgraph "Subgraph 4.3.1"
    4.3.1 -->|Yes| 4.3.1_allow(["`allow`"])
    4.3.1 -->|No| 4.3.2{{"`4.3.2: The _sender_ does not match _state_key_?`"}}
    4.3.2 -->|Yes| 4.3.2_reject(["`reject`"])
    4.3.2 -->|No| 4.3.3{{"`4.3.3: The _sender_ is banned?`"}}
    4.3.3 -->|Yes| 4.3.3_reject(["`reject`"])
    4.3.3 -->|No| 4.3.4{{"`4.3.4: The _join_rule_ is _invite_ or _knock_ and membership state is _invite_ or _join_?`"}}
    4.3.4 -->|Yes| 4.3.4_allow(["`allow`"])
    4.3.4 -->|No| 4.3.5{{"`4.3.5: The _join_rule_ is _restricted_ or _knock_restricted_?`"}}
    4.3.5 -->|Yes| 4.3.5.1{{"`4.3.5.1: Membership state is _join_ or _invite_?`"}}
    4.3.5.1 -->|Yes| 4.3.5.1_allow(["`allow`"])
    4.3.5.1 -->|No| 4.3.5.2{{"`4.3.5.2: The _join_authorised_via_users_server_ key in _content_ is not a user with sufficient permission to invite other users?`"}}
    4.3.5.2 -->|Yes| 4.3.5.2_reject(["`reject`"])
    4.3.5.2 -->|No| 4.3.5.3(["`allow`"])
    4.3.5 -->|No| 4.3.6{{"`4.3.6: The _join_rule_ is _public_?`"}}
    4.3.6 -->|Yes| 4.3.6_allow(["`allow`"])
    4.3.6 -->|No| 4.3.7(["`reject`"])
  end

Loading

Subgraph starting at 4.4.1

flowchart TD

    4.4{{"`4.4: _membership_ is _invite_?`"}} -->|Yes| 4.4.1{{"`4.4.1: _content_ has a _third_party_invite_ property?`"}}

  subgraph "Subgraph 4.4.1"
    4.4.1 -->|Yes| 4.4.1.1{{"`4.4.1.1: *target user* is banned?`"}}
    4.4.1.1 -->|Yes| 4.4.1.1_reject(["`reject`"])
    4.4.1.1 -->|No| 4.4.1.2{{"`4.4.1.2: _content.third_party_invite_ does not have a _signed_ property?`"}}
    4.4.1.2 -->|Yes| 4.4.1.2_reject(["`reject`"])
    4.4.1.2 -->|No| 4.4.1.3{{"`4.4.1.3: _signed_ does not have _mxid_ and _token_ properties?`"}}
    4.4.1.3 -->|Yes| 4.4.1.3_reject(["`reject`"])
    4.4.1.3 -->|No| 4.4.1.4{{"`4.4.1.4: _mxid_ does not match _state_key_?`"}}
    4.4.1.4 -->|Yes| 4.4.1.4_reject(["`reject`"])
    4.4.1.4 -->|No| 4.4.1.5{{"`4.4.1.5: There is no _m.room.third_party_invite_ event in the current room state with _state_key_ matching _token_?`"}}
    4.4.1.5 -->|Yes| 4.4.1.5_reject(["`reject`"])
    4.4.1.5 -->|No| 4.4.1.6{{"`4.4.1.6: _sender_ does not match _sender_ of the _m.room.third_party_invite_?`"}}
    4.4.1.6 -->|Yes| 4.4.1.6_reject(["`reject`"])
    4.4.1.6 -->|No| 4.4.1.7{{"`4.4.1.7: Any signature in _signed_ matches any public key in the _m.room.third_party_invite_ event? The public keys are in _content_ of _m.room.third_party_invite_ as: 1.  A single public key in the _public_key_ property. 2.  A list of public keys in the _public_keys_ property.`"}}
    4.4.1.7 -->|Yes| 4.4.1.7_allow(["`allow`"])
    4.4.1.7 -->|No| 4.4.1.8(["`reject`"])
    4.4.1 -->|No| 4.4.2{{"`4.4.2: The _sender_'s current membership state is not _join_?`"}}
    4.4.2 -->|Yes| 4.4.2_reject(["`reject`"])
    4.4.2 -->|No| 4.4.3{{"`4.4.3: *target user*'s current membership state is _join_ or _ban_?`"}}
    4.4.3 -->|Yes| 4.4.3_reject(["`reject`"])
    4.4.3 -->|No| 4.4.4{{"`4.4.4: The _sender_'s power level is greater than or equal to the *invite level*?`"}}
    4.4.4 -->|Yes| 4.4.4_allow(["`allow`"])
    4.4.4 -->|No| 4.4.5(["`reject`"])
  end

Loading

Subgraph starting at 4.5.1

flowchart TD

    4.5{{"`4.5: _membership_ is _leave_?`"}} -->|Yes| 4.5.1{{"`4.5.1: The _sender_ matches _state_key_, allow if and only if that user's current membership state is _invite_, _join_, or _knock_?`"}}

  subgraph "Subgraph 4.5.1"
    4.5.1 -->|Yes| 4.5.1_allow(["`allow`"])
    4.5.1 -->|No| 4.5.2{{"`4.5.2: The _sender_'s current membership state is not _join_?`"}}
    4.5.2 -->|Yes| 4.5.2_reject(["`reject`"])
    4.5.2 -->|No| 4.5.3{{"`4.5.3: The *target user*'s current membership state is _ban_, and the _sender_'s power level is less than the *ban level*?`"}}
    4.5.3 -->|Yes| 4.5.3_reject(["`reject`"])
    4.5.3 -->|No| 4.5.4{{"`4.5.4: The _sender_'s power level is greater than or equal to the *kick level*, and the *target user*'s power level is less than the _sender_'s power level?`"}}
    4.5.4 -->|Yes| 4.5.4_allow(["`allow`"])
    4.5.4 -->|No| 4.5.5(["`reject`"])
  end

Loading

Subgraph starting at 4.6.1

flowchart TD

    4.6{{"`4.6: _membership_ is _ban_?`"}} -->|Yes| 4.6.1{{"`4.6.1: The _sender_'s current membership state is not _join_?`"}}

  subgraph "Subgraph 4.6.1"
    4.6.1 -->|Yes| 4.6.1_reject(["`reject`"])
    4.6.1 -->|No| 4.6.2{{"`4.6.2: The _sender_'s power level is greater than or equal to the *ban level*, and the *target user*'s power level is less than the _sender_'s power level?`"}}
    4.6.2 -->|Yes| 4.6.2_allow(["`allow`"])
    4.6.2 -->|No| 4.6.3(["`reject`"])
  end

Loading

Subgraph starting at 4.7.1

flowchart TD

    4.7{{"`4.7: _membership_ is _knock_?`"}} -->|Yes| 4.7.1{{"`4.7.1: The _join_rule_ is anything other than _knock_ or _knock_restricted_?`"}}

  subgraph "Subgraph 4.7.1"
    4.7.1 -->|Yes| 4.7.1_reject(["`reject`"])
    4.7.1 -->|No| 4.7.2{{"`4.7.2: _sender_ does not match _state_key_?`"}}
    4.7.2 -->|Yes| 4.7.2_reject(["`reject`"])
    4.7.2 -->|No| 4.7.3{{"`4.7.3: The _sender_'s current membership is not _ban_, _invite_, or _join_?`"}}
    4.7.3 -->|Yes| 4.7.3_allow(["`allow`"])
    4.7.3 -->|No| 4.7.4(["`reject`"])
  end

Loading

Subgraph starting at 9.1

flowchart TD

    9{{"`9: Type is _m.room.power_levels_?`"}} -->|Yes| 9.1{{"`9.1: Any of the properties _users_default_, _events_default_, _state_default_, _ban_, _redact_, _kick_, or _invite_ in _content_ are present and not an integer?`"}}

  subgraph "Subgraph 9.1"
    9.1 -->|Yes| 9.1_reject(["`reject`"])
    9.1 -->|No| 9.2{{"`9.2: Either of the properties _events_ or _notifications_ in _content_ are present and not an object with values that are integers?`"}}
    9.2 -->|Yes| 9.2_reject(["`reject`"])
    9.2 -->|No| 9.3{{"`9.3: The _users_ property in _content_ is not an object with keys that are valid user IDs with values that are integers?`"}}
    9.3 -->|Yes| 9.3_reject(["`reject`"])
    9.3 -->|No| 9.4{{"`9.4: There is no previous _m.room.power_levels_ event in the room?`"}}
    9.4 -->|Yes| 9.4_allow(["`allow`"])
    9.4 -->|No| 9.5["`9.5: For the properties _users_default_, _events_default_, _state_default_, _ban_, _redact_, _kick_, _invite_ check if they were added, changed or removed. For each found alteration`"]
    9.5 --> 9.5.1{{"`9.5.1: The current value is higher than the _sender_'s current power level?`"}}
    9.5.1 -->|Yes| 9.5.1_reject(["`reject`"])
    9.5.1 -->|No| 9.5.2{{"`9.5.2: The new value is higher than the _sender_'s current power level?`"}}
    9.5.2 -->|Yes| 9.5.2_reject(["`reject`"])
    9.5.2 -->|No| 9.6["`9.6: For each entry being changed in, or removed from, the _events_ or _notifications_ properties`"]
    9.6 --> 9.6.1{{"`9.6.1: The current value is greater than the _sender_'s current power level?`"}}
    9.6.1 -->|Yes| 9.6.1_reject(["`reject`"])
    9.6.1 -->|No| 9.7["`9.7: For each entry being added to, or changed in, the _events_ or _notifications_ properties`"]
    9.7 --> 9.7.1{{"`9.7.1: The new value is greater than the _sender_'s current power level?`"}}
    9.7.1 -->|Yes| 9.7.1_reject(["`reject`"])
    9.7.1 -->|No| 9.8["`9.8: For each entry being changed in, or removed from, the _users_ property, other than the _sender_'s own entry`"]
    9.8 --> 9.8.1{{"`9.8.1: The current value is greater than or equal to the _sender_'s current power level?`"}}
    9.8.1 -->|Yes| 9.8.1_reject(["`reject`"])
    9.8.1 -->|No| 9.9["`9.9: For each entry being added to, or changed in, the _users_ property`"]
    9.9 --> 9.9.1{{"`9.9.1: The new value is greater than the _sender_'s current power level?`"}}
    9.9.1 -->|Yes| 9.9.1_reject(["`reject`"])
    9.9.1 -->|No| 9.10(["`allow`"])
  end

Loading