Add a general `NestedMap` solution to the sdk

[toger5]

In this PR it became apperant that we do not have a good nested map solution. This comment (by @robintown) proposes a good solution: https://github.com/matrix-org/matrix-js-sdk/pull/5028#discussion_r2409243084

In fact, this pattern of shuffling around nested maps is so common in the JS SDK that I feel like it deserves to be turned into a set of reusable functions. It takes a bit of type magic, but I played around with it a bit and I think something like this would make for a pretty convenient API:

type NestedMap<K extends unknown[], V> = K extends [infer K1, ...infer K_] ? Map<K1, NestedMap<K_, V>> : V

function getNested<K extends [unknown, ...unknown[]], M extends NestedMap<K, unknown>>(map: M, ...keys: K): M extends NestedMap<K, infer V> ? V | undefined : never {
    let result: any = map
    for (const key of keys) result = result?.get(key)
    return result
}

function setNested<K extends [unknown, ...unknown[]], V, M extends NestedMap<K, V>>(map: M, value: V, ...keys: K): void {
    let m: any = map
    for (let i = 0; i < keys.length - 1; i++) {
        let inner = m.get(keys[i])
        if (inner === undefined) {
            inner = new Map()
            m.set(keys[i], inner)
        }
        m = inner
    }
    m.set(keys[keys.length - 1], value)
}

function deleteNested<K extends [unknown, ...unknown[]], M extends NestedMap<K, unknown>>(map: M, ...keys: K): boolean {
    if (keys.length === 1) {
        return map.delete(keys[0])
    } else {
        const inner = map.get(keys[0]) as Map<unknown, unknown> | undefined
        if (inner === undefined) return false
        const [key, ...keys_] = keys
        // @ts-ignore
        const result = deleteNested(inner, ...keys_)
        if (inner.size === 0) map.delete(key)
        return result
    }
}

Usage looks like this:

const myMap = new Map<number, Map<string, number>>()
setNested(myMap, 999, 1, 'foo')
const y = getNested(myMap, 1, 'foo') // y = 999
deleteNested(myMap, 1, 'foo') // now myMap is empty

Then with nested maps of 3+ layers being less painful, this could even help us avoid the ${stickyKey}${sender} hack found in this file.

This change was not added as part of https://github.com/matrix-org/matrix-js-sdk/pull/5028.

This issue tracks adding such a feature and using it in all places of the js-sdk where it is helpful.

[robintown]

Thanks for tracking this. @toger5 and @Half-Shot said they'd prefer a solution in which NestedMap is not a subtype of Map but actually a separate class.

The only real reason I had for preferring functions is that we can manipulate the map with partial keys, as shown below, without trading away nice error messages.

// room ID → user ID → device ID → call membership
const memberships = new Map<string, Map<string, Map<string, CallMembership>>>()
// memberships is simultaneously a NestedMap<[string, string, string], CallMembership> ...
console.log(
  'do we have a membership for Bob's phone?',
  nestedGet(memberships, '!abc:example.org', '@bob:example.org', 'PHONE') !== undefined
)
// ... but also a NestedMap<[string, string], Map<string, CallMembership>>, among other things
const memberships: Map<string, CallMembership> = nestedGet(memberships, '!abc:example.org', '@bob:example.org')
// So pulling out a map of all memberships for a particular room+user - or clearing it - is also quite convenient.
nestedDelete(memberships, '!abc:example.org', '@bob:example.org')

(With this approach, trying to index into the map with nestedGet(memberships, 'test', undefined) will result in a helpful "Type 'string' is not assignable to type 'undefined'" message. With the class approach, either we don't support partial keys, or the .get() method has to indicate a key mismatch by unceremoniously returning never.)

type NestedMapType<K extends unknown[], V> = K extends [infer K1, ...infer K_] ? Map<K1, NestedMapType<K_, V>> : V

class NestedMap<K1, V1> {
    public constructor(public readonly map: Map<K1, V1>) {}

    public get<K extends unknown[]>(...keys: K): Map<K1, V1> extends NestedMapType<K, infer V> ? V | undefined : never {
        /* ... */
    }
}

const myMap = new NestedMap(new Map<string, Map<string, Map<string, CallMembership>>>())
// no type error
const y: never = myMap.get('a', 'b', undefined)