Reconsidering node access and mutation in the consumer crate

[mwcampbell]

I've been thinking about the best way to manage node access and mutation. Here are the goals I want to achieve:

• A single operation on a platform node, e.g. a single UI Automation method call, should have access to a consistent snapshot of the whole tree for the duration of the operation. It would be good if platform accessibility APIs had a way of indicating that a client wanted to work with a consistent snapshot across multiple consecutive requests, but that's not possible, so consistency within a single request is the best we can do.
• Conversely, each request on a platform node should access the latest version of the underlying AccessKit node, because clients may hold onto a particular platform node for a long time.
• Platform nodes are expected to outlive the underlying AccessKit nodes or even the tree itself. When this happens, requests on "zombie" platform nodes should fail cleanly, e.g. with UI Automation's UIA_E_ELEMENTNOTAVAILABLE error.
• Platform nodes have arbitrary lifetimes (defined by the platform's reference counting or garbage collection mechanism), but the tree needs to be updated, so we need interior mutability on the top-level tree.
• It should be possible to access and mutate the tree from arbitrary threads, because modern concurrent software should minimize the number of things that must be done on "the UI thread".

These goals are currently met by using RwLock to implement interior mutability. This solution has two downsides:

• The tree can't be accessed and mutated concurrently. These operations are thread-safe, and multiple reads can be done concurrently, but reads and writes are mutually exclusive.
• The need to hold a lock while reading from the tree adds complexity around borrowing and lifetimes. Thus, for example, the iterators for traversing unignored siblings aren't as efficient as they could be.

My proposed rough solution is to wrap each node in an Arc and store the map from node IDs to nodes in a persistent, copy-on-write map like the ones in the [im crate]https://docs.rs/im/15.0.0/im/). I'd appreciate thoughts on this solution, or other ideas.

[DataTriny]

I have been reading this article which introduce the crossbeam-epoch crate. It allows to create concurrent, lock free data structures. This might be worth investigating.