Can not find a way to do this

hello friends, I am new to rust, from a C/C++ background. I am familiar with rusty concepts, from mutability to borrow checker and lifetimes and...
I am developing a TUI to work with our MQTT clients, long story short, I have a Tree-like data structure to represent MQTT topic-tree, much like Cedalo topic-tree, like below:

pub struct TopicTree {
    topic_name: String,
    child: Option<Vec<TopicTree>>,
    data: Option<Vec<String>>
}

if the node represents a leaf in the tree, the child would be None, otherwise, the data would be None, the App struct has a topic_tree_root like below:

pub struct App {
    // root node
    pub topic_tree_root:TopicTree,
} 

and I want to do something like below pseudo-code:

variable curr_node: App.topic_root_tree;
variable found: false;
for text in "/some/topic/name/here".split("/"):
    for item in curr_node.child:
        if item.topic_name == text:   
            curr_node = item;
            found = true;
            break;
    if !found:
        create_a_child_with_text_in_this_level()
        and_create_subsequent_child_in_next_levels()

I just want to create a Tree structure based on the topic, if I have "gps/v1/c/23123" and "gps/v1/l/23232", then I want to have these levels:

level 0: [gps]
    level 1: [v1]
        level2: [c, l] 
            level 3 for parent c: [23123]
            level 3 for parent l: [23232]

I have been trying to do this for 3 days now, tried Box, RefCell, unsafe and every time I had problems with borrow checker or other things.
now I am asking you to give me a solution, any change to the structure is acceptable because it is a learning project, any link to tutorials and useful content, so I can find my problem and find out where are the wholes in my rust knowledge. thank you.

There is nothing wrong with the data structures you are proposing to use. However, "find or create" functions can be tricky to write. Could you share your non-working Rust code, not just the pseudocode? That will give us a better place to start helping.

1 Like

What you want to do sounds similar to the entry(key) method of HashMap in the standard library. You may want to take a look at the source for that (linked from the documentation). Or just look at the api of that method and the struct it returns.

Note that the Entry return value takes an exclusive borrow of the map, but the Entry is generally short-lived.

The main change necessary to make the borrow checker happy is that you should search for an index and then re-access that index starting from curr_node itself, once you commit to updating curr_node. Otherwise you'll easily hit some limitations of the borrow checker around conditionally using a reference for a longer or shorter duration/lifetime that are unfortunately still in place (and might be lifted eventually).

In your pseudo-code, that might look -- roughly -- like

variable curr_node: App.topic_root_tree;
for text in "/some/topic/name/here".split("/"):
    for (ix, item) in curr_node.child.iter().enumerate():
+       variable found_index = None;
        if item.topic_name == text:   
-           curr_node = item;
-           found = true;
+           found_index = Some(i);
            break;
+   match found
+     Some(ix) => curr_node = &mut curr_node.child[ix],
      None =>
-   if !found:
        create_a_child_with_text_in_this_level()
        ...

I haven't quite fully understood the role of data and the relationships with the None's you tried to explain, but here's some code example that should help illustrate the point anyways (admitted, using some more "fancy" way of writing some of the loops, too).

#[derive(Debug)]
pub struct TopicTree {
    topic_name: String,
    children: Vec<TopicTree>,
    data: Option<Vec<String>>,
}

#[derive(Debug)]
pub struct App {
    // root node
    pub topic_tree_root: TopicTree,
}

impl App {
    fn get_path(&mut self, path: &str) -> &mut Vec<String> {
        let mut current_node = &mut self.topic_tree_root;
        for text in path.split('/') {
            current_node = match current_node
                .children
                .iter()
                .enumerate()
                .find(|(_, child)| child.topic_name == text)
            {
                Some((ix, _)) => &mut current_node.children[ix],
                None => {
                    current_node.children.push(TopicTree {
                        topic_name: text.to_owned(),
                        children: Vec::new(),
                        data: None,
                    });
                    current_node.children.last_mut().unwrap()
                }
            }
        }
        current_node.data.get_or_insert(Vec::new())
    }
}

fn main() {
    let mut app = App {
        topic_tree_root: TopicTree {
            topic_name: String::new(),
            children: Vec::new(),
            data: None,
        }
    };

    let data1 = app.get_path("gps/v1/c/23123");
    data1.extend(["Some", "Data", "Here"].map(<_>::to_owned));

    let data2 = app.get_path("gps/v1/l/23232");
    data2.extend(["Other", "Data", "There"].map(<_>::to_owned));

    dbg!(&app);
}

Rust Playground

Output:
   Compiling playground v0.0.1 (/playground)
    Finished dev [unoptimized + debuginfo] target(s) in 4.75s
     Running `target/debug/playground`
[src/main.rs:54] &app = App {
    topic_tree_root: TopicTree {
        topic_name: "",
        children: [
            TopicTree {
                topic_name: "gps",
                children: [
                    TopicTree {
                        topic_name: "v1",
                        children: [
                            TopicTree {
                                topic_name: "c",
                                children: [
                                    TopicTree {
                                        topic_name: "23123",
                                        children: [],
                                        data: Some(
                                            [
                                                "Some",
                                                "Data",
                                                "Here",
                                            ],
                                        ),
                                    },
                                ],
                                data: None,
                            },
                            TopicTree {
                                topic_name: "l",
                                children: [
                                    TopicTree {
                                        topic_name: "23232",
                                        children: [],
                                        data: Some(
                                            [
                                                "Other",
                                                "Data",
                                                "There",
                                            ],
                                        ),
                                    },
                                ],
                                data: None,
                            },
                        ],
                        data: None,
                    },
                ],
                data: None,
            },
        ],
        data: None,
    },
}
1 Like

Actually, after I sent the question, I figured out a solution but it is inside an unsafe block, and from what I have heard from rust developers, I know there should be a safe solution for this, my code is as below:

pub mod app {
    #[derive(Debug, PartialEq, Eq, Default, Clone)]
    pub struct TopicTree {
        topic_name: String,
        child: Option<Vec<TopicTree>>,
        data: Option<Vec<String>>
    }
impl TopicTree {
    pub fn new(tn: String) -> TopicTree {
        TopicTree {
            topic_name: tn,
            child: Some(vec![]),
            data: None
        }
    }
}


pub struct App {
    // Topic Tree
    pub topic_tree_root:TopicTree,
}

impl App {
    pub fn parse_topic_to_tree(& mut self, topic: &str){
        let mut found = false;
        let mut curr_node = & mut self.topic_tree_root as *mut TopicTree;
        for i in topic.split("/") { 
            unsafe{
                found = false;
                if (*curr_node).topic_name == i {
                    found = true;
                    continue;
                }
                for j in 0..(*curr_node).child.as_ref().unwrap().len() {
                    if (*curr_node).child.as_ref().unwrap()[j].topic_name == i {
                        found = true;
                        curr_node = &mut (*curr_node).child.as_mut().unwrap()[j];
                        break;
                    }
                }
                if !found {
                    println!("here we are at last {}", i);
                    (*curr_node).child.as_mut().unwrap().push(TopicTree::new(i.to_string()));
                    curr_node = &mut (*curr_node).child.as_mut().unwrap()[(*curr_node).child.as_ref().unwrap().len()-1] as *mut TopicTree;
                }
            }
        }
    }
}

}

so I'll be thankful if you can suggest to me a better and also a safe approach.
thank you.

Compiles without unsafe with one minor modification: assign the result of the len() call in the !found case to a separate variable first.

Rust Playground

Of course you could also simply use .last_mut() instead as I did in the code I posted above.

Generally avoid using unsafe if it's not necessary ^^

1 Like

it is interesting how my code doesn't need null pointers and unsafe block at all :smiley:
thank you.

a correct, also clean way, thank you.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.