time complexity of TSNode::* APIs

[champignoom]

By reading the implementation, I found just recently that the APIs might be more expensive than the names suggest. For example, TSNode::parent() does not just return a cached pointer in O(1) but rather goes from the root all the way down to itself and checks parenthoods on the fly, which costs O(n) in the worst case if I'm not mistaken.

tree-sitter/lib/src/node.c

Lines 461 to 490 in a62bac5

	TSNode ts_node_parent(TSNode self) {
	TSNode node = ts_tree_root_node(self.tree);
	uint32_t end_byte = ts_node_end_byte(self);
	if (node.id == self.id) return ts_node__null();
	TSNode last_visible_node = node;
	bool did_descend = true;
	while (did_descend) {
	did_descend = false;
	TSNode child;
	NodeChildIterator iterator = ts_node_iterate_children(&node);
	while (ts_node_child_iterator_next(&iterator, &child)) {
	if (
	ts_node_start_byte(child) > ts_node_start_byte(self) ||
	child.id == self.id
	) break;
	if (iterator.position.bytes >= end_byte) {
	node = child;
	if (ts_node__is_relevant(child, true)) {
	last_visible_node = node;
	}
	did_descend = true;
	break;
	}
	}
	}
	return last_visible_node;
	}

see also the implementation of TSNode::next_sibling

I'm wondering if there's any possible/planned optimization for this, and if not, will this be documented?

[ahlinc]

It's a known feature and it's a cost of immutable trees with a cheap cloning operation what allows to work with the same trees in parallel from multiple threads. It will be documented.

[ahlinc]

which costs O(n) in the worst case if I'm not mistaken

You're right that it's not O(1) but it does pretty effective stepping down over a tree to a node by using checks of predecessor ranges.