[Feat]: Add a method to get the parent node of a given node

[xFrednet]

Summary

Requesting the parent of a given node, is a fundamental feature required to build context-sensitive lints. It's useful to check the context that an expression occurs in or to adapt the suggestion when required. Rustc provides a find_parent(HirId) function and an iterator function to walk through the parents.

I've already planned a bit for this issue, and it's surprisingly complex. It might take some time to implement it properly and feedback from the community.

[xFrednet]

The new addition of the NodeId struct can be used for the development of this issue.

I still have a tiny hope that I can work on this before v0.3.0, but it's likely that this will be moved to v0.4.0 as major breaking changes are currently taking priority for me.

[xFrednet]

I did some work in preparation for this issue, but it's unlikely that I'll get this done before v0.3. It's free for the taking :)

[Veetaha]

I've been thinking of implementing iterator API for traversing the AST tree. There is a major problem with implementing such API in that the iterator's state needs to have a dynamically allocated data structure (e.g. a stack) to track the position of the cursor inside of the AST. For example, each time the iteration enters a subtree the stack needs to grow and each time it exists the stack shrinks.

This dynamic state is conceptually unavoidable because the cursor needs to know where to return (how to go up in the tree). If there are parent node references it would reduce the number of state needed to implement the iterator API, but still not entirely solve the problem. When we go up in the tree we also need to know where to continue (the index of the child node that was exited in the parent node plus one).

Because rust-analyzer's nodes have references to parents and adjacent nodes it was possible to implement an allocation-free iterator in there. See e.g. the node representation there.

[xFrednet]

We could also consider storing references of the parents in the nodes.

For the iterator, I think it depends on the flexibility we want to provide. If we only allow the traversal upwards, we only need a single ID in the iterator, that is used to request the next parent. If we allow going down, then it will be more complicated, like you described.

In Clippy, we usually only traverse upwards, if needed we might use a visitor to go downwards. I'm not sure if there is a lint, which would require an iterator that is traversable in both directions.