What pointer lifetime to use when iterating through a tree?

I've created a tree data structure:

struct BKTree:
    var root: Optional[BKTreeNode]

struct BKTreeNode(TestableCollectionElement):
    var text: String
    var parent_distance: Int
    var children: List[BKTreeNode]

struct BKTree:
    var root: Optional[BKTreeNode]

struct BKTreeNode(TestableCollectionElement):
    var text: String
    var parent_distance: Int
    var children: List[BKTreeNode]

which I've added nodes to. I now want to search for a node by iterating over its children:

nodes_to_process = List[UnsafePointer[BKTreeNode]](
    UnsafePointer.address_of(self.root.value())
)

while len(nodes_to_process) > 0:
  current_node_ref = nodes_to_process.pop()
  current_node_distance_to_query = levenshtein_distance(
      current_node_ref[].text, query
  )

  for child in current_node_ref[].children:
      if (within_distance):
          nodes_to_process.append(UnsafePointer.address_of(child[]))

nodes_to_process = List[UnsafePointer[BKTreeNode]](
    UnsafePointer.address_of(self.root.value())
)

while len(nodes_to_process) > 0:
  current_node_ref = nodes_to_process.pop()
  current_node_distance_to_query = levenshtein_distance(
      current_node_ref[].text, query
  )

  for child in current_node_ref[].children:
      if (within_distance):
          nodes_to_process.append(UnsafePointer.address_of(child[]))

As you can see, I'm using UnsafePointer here which I don't really like. I tried to use Pointer, but I can't figure out how to get the lifetime right. If I use:

nodes_to_process = List(Pointer.address_of(self.root.value()))

nodes_to_process = List(Pointer.address_of(self.root.value()))

I get an error at the append call:

invalid call to 'append': method argument #0 cannot be converted from 'Pointer[0, BKTreeNode, self.root._value.children, 0]' to 'Pointer[0, BKTreeNode, self.root._value, 0]'

. Is there an idiomatic way to do this correctly? I've tried Arc but this seems to slow the search down by a lot. I'm using Pointers to avoid copying nodes. Is this the right way to go about this in the first place?

1 Reply

Martin Vuyk•2mo ago

Not sure if you are using nightly or stable. But I'll say origin instead of lifetime since it became the new term (in current stable it's still the __lifetime_of() operator). You are trying to append a child with a different origin than the parent and you declared the list as being a list of pointers to node roots. Unsafe pointer lets you bypass that. Currently Pointer is very limited. You might want to read some of /utils/span.mojo code in the stdlib to see some parametrized origin use. If your child nodes can have the origin of the parent you might avoid the issue. You could also try to force a rebind[Pointer[BKTNode, __origin_of(self.root.value())]](Pointer.address_of(child[])) Play around with those concepts, but don't worry it's mainly issues with the language not being fully fledged yet. And this is a solid use case for Unsafe pointer, where the language doesn't let you go on safe mode, go raw. (UnsafePointer will also be able to carry an origin in the future to be safer, I'm working on a PR for that)

Gaming

Programming

What pointer lifetime to use when iterating through a tree?