Semantic: Simplify ancestors iterators #12151
Description
#12087 made Program it's own parent in AstNodes. The only downside of this change is that it complicated the iterators returned by ancestors, ancestor_ids, and ancestor_kinds methods.
I suggest that we change these iterators so the first item they yield is the parent of provided node, not the node itself.
I suspect that most usages of these methods already skip the first yielded item, or if they don't, they should. Why would you want to check something about the original node, as you very likely know what it is already?
Reducing the number of iterations would (slightly) improve performance.
Additionally, this would also allow us to simplify the iterator's implementation. Currently:
pub struct AstNodeIdAncestorsIter<'n> {
next_node_id: Option<NodeId>,
parent_ids: &'n IndexSlice<NodeId, [NodeId]>,
}
impl<'n> AstNodeIdAncestorsIter<'n> {
fn new(node_id: NodeId, nodes: &'n AstNodes<'_>) -> Self {
Self { next_node_id: Some(node_id), parent_ids: nodes.parent_ids.as_slice() }
}
}
impl Iterator for AstNodeIdAncestorsIter<'_> {
type Item = NodeId;
fn next(&mut self) -> Option<Self::Item> {
if let Some(node_id) = self.next_node_id {
// `Program`'s parent is itself, so next node is `None` if this node is `Program`
self.next_node_id =
if node_id == NodeId::ROOT { None } else { Some(self.parent_ids[node_id]) };
Some(node_id)
} else {
None
}
}
}Instead it could be:
pub struct AstNodeIdAncestorsIter<'n> {
current_node_id: NodeId,
parent_ids: &'n IndexSlice<NodeId, [NodeId]>,
}
impl<'n> AstNodeIdAncestorsIter<'n> {
fn new(node_id: NodeId, nodes: &'n AstNodes<'_>) -> Self {
Self { current_node_id: node_id, parent_ids: nodes.parent_ids.as_slice() }
}
}
impl Iterator for AstNodeIdAncestorsIter<'_> {
type Item = NodeId;
fn next(&mut self) -> Option<Self::Item> {
if self.current_node_id == NodeId::ROOT {
return None;
}
self.current_node_id = self.parent_ids[self.current_node_id];
Some(self.current_node_id)
}
}This produces more streamlined assembly - 1 less branch, and 1 less register: https://godbolt.org/z/a9MjoMech
cc @ulrichstark, in case you're interested.