Recursive function returns the last received Some value if next one was None

[Dango]

Hi, new rustacean here..
I realize how stupid the title topic sounds believe me, I can't explain this to my self either.

So I'm coming from a high level language and I'm probably missing something specific for low level languages, but since I couldn't find someone else experiencing the same issue nor any logic explanation in either my head or documentation, that's why I decided to ask the experienced.

I'm having impl A and impl B both with methods inside. impl A is calling a method from impl B which is created to iterate over a custom value which is HashMap<String, Value> while Value is a struct of that can hold some other data. In that specific case it holds more HashMap<String, Value>. My iterative method tries to encounter existing keys deep nested into the whole thing which are differently named on each level. The method that's being called to iterate from impl B is recursive for that reason. The recursive method returns Option<&'c Value>, lifetime is chained with the lifetime of the origin hashmap provided at first. So my body looks something like that:

pub fn hash_iterate<'c>(needle: &str, hash: &'c HashMap<String, Value>) -> Option<&'c Value>

The calling impl looks something like that:

impl A {
    fn analyze() {
        B::hash_iterate("needle", hashmap);
    }
}


impl B {
    pub fn hash_iterate<'c>(needle: &str, hash: &'c HashMap<String, Value>) -> Option<&'c Value>
        return match hash.get(needle.to_string()) {
            Some(v) => {
                // I have some complex if condition here that enters recursion
                if complex_condition_true {
                    hash_iterate("new_needle_here", &v.clone().unwrap());
                }
                hash.get(needle.to_string())
            }
            None => None
        }
    }
}

So you can imagine that I'm providing a route which the recursion should go through. However if any of the paths are not found we'd like to return None. If all recursive calls are successful we'd like to return the last value we've encountered.

The paths are like path1.path2.path3 (we iterate over 2 hashmaps in the recursion that way because we'd like to check if path3 exists at all)

What happens with the recursive method is what amazes me. It returns strange results like the following:

1. We search for the whole route and path1 doesn't exist on first hit, it returns None successfully
2. We search for the whole route and path1 exists, so we enter it and search for path2 that doesn't exists the method returns Some(path1) instead of None
3. We search for the whole route and path1 exists, path2 exists, path3 doesn't exists, the method returns Some(path2).

Interesting facts:
When returning, the method goes through None arm match and still returns Some.

Edit: Fixed the code formatting, sorry about that.

[alice]

I notice a few things:

1. You don't need return match like that — the last expression is returned without a return.
2. You don't need .to_string() to look up in the hash map. Just use the &str directly and avoid the clone.
3. It looks like the hash in hash.clone().unwrap() is not the one in your argument? Cloning a hash map does not give you something you can unwrap.

[Dango]

@alice

• You don't need return match like that — the last expression is returned without a return.
• You don't need .to_string() to look up in the hash map. Just use the &str directly and avoid the clone.
• It looks like the hash in hash.clone().unwrap() is not the one in your argument? Cloning a hash map does not give you something you can unwrap.

Replying accordingly:

1. That was a desperate move I initiated.
2. Well it fails to borrow &str, shouldn't I provide the same type value as key search accordingly to the type of HashMap which is defined to have String as key and Value object as value?
3. I will fix the initial post, I've made a typo, I'm actually calling &v.clone().unwrap() - sorry about that (I'm unwrapping Value object which is impl from another crate and that object is actually returning HashMap<String, Value>, thus passing the inner HashMap);

[alice]

The get function on hashmap has the following signature:

pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V> where
    K: Borrow<Q>,
    Q: Hash + Eq, 

Now it turns out that String implements the trait Borrow<str> (see here), so you can indeed choose Q = str when the key is String.

Regarding your clone of the value: something is going on here, and I can't tell what from the snippet, because cloning the hash map will only allow the resulting reference to live as long as that clone, and since the clone is a local variable inside your function, you would not be able to return such a reference.

I guess it's just because you ignore the output of the hash_iterate and go on to return hash.get(needle)?

[Dango]

That's odd, I had to infer type specifically to the needle that it is &str, previously I was getting:

the trait std::borrow::Borrow<&str> is not implemented for std::string::String
and that's why I went with String. At least that's properly fixed for now.

I'll continue searching for an issue related with the unused result of the recursion call.

[alice]

If you got that error, it was because you were trying to index with &&str, not &str.

[Dango]

Funny thing is that I was actually accessing with &str maybe not so little detail is that this string was coming from a slice actually but I didn't describe it like that as I thought it's not important.

However I resolved the matter with different approach. I considered extending the crate implementation with a method that uses their getter method which helps me to find out exactly the same thing without traversing the hashes, borrowing or taking ownerships. Turned out much nicer.

To conclude the awkward behavior, I did set some prints to see how the jump in/out happens exactly and what I noticed was the following

> Level 1 Path 1 (exists)
> > Level 2 Path 2 (exists)
> > > Level 3 Path 3 (not exists)
> > > Returns Level 3 Path 3 Result - None
> > Returns Level 2 Path 2 Result - Some
> Returns Level 1 Path 1 Result - Some
Final return is not where I actually exited the method on level 3 path 3
Instead it goes way back to level 1 and returns that

I didn't notice that it was actually returning the first access all the time of the path and that's why it was working perfectly well for keys on first level paths. I've tried creating a short snippet to reproduce the issue here, however I wasn't able because of the HashMap values specific of the crate I'm using and I couldn't invest more time for that right now.

Thanks anyway for the quick responses.

[Dango]

Although I fixed this matter with another approach, I had to deal with mutating the same struct instead of only reading it, so I had the same issue. So I got back here re-reading every single word your wrote.

@alice

I guess it's just because you ignore the output of the hash_iterate and go on to return hash.get(needle) ?

Turns out you were right, the problem was indeed the fact that i was not using properly the output of the method when I was entering the recursion. Overall said, its like disassembling the whole struct into parts, whenever entering recursion and then returning every modified part afterwards and always mutating the value that you wanted. Thus it would result the same when trying to iterate deeply and want to return the most inner result.

Made me feel stupid in a lot of different ways and I was going crazy at some point, but I guess that's the price I had to pay for learning.

Thanks a lot!