[SERVER-28971] Error in depth_first_search algorithm incorrectly recurses on visited nodes Created: 25/Apr/17  Updated: 30/Oct/23  Resolved: 26/Apr/17

Status: Closed
Project: Core Server
Component/s: Testing Infrastructure
Affects Version/s: 3.5.6
Fix Version/s: 3.4.5, 3.5.7

Type: Bug Priority: Major - P3
Reporter: Eddie Louie Assignee: Eddie Louie
Resolution: Fixed Votes: 0
Labels: bkp
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Backports
Backwards Compatibility: Fully Compatible
Operating System: ALL
Backport Requested:
v3.4
Sprint: TIG 2017-05-08
Participants:

 Description   

In one of our CR for SERVER-28348 we missed this logic bug. The recursion should only happen for nodes that we have not visited yet.

    def depth_first_search(self, node_key, nodes_visited, nodes_in_cycle=[]):
        """
        The nodes_visited is a set of nodes which indicates it has been visited.
        The node_in_cycle is a list of nodes in the potential cycle.
        Returns the list of nodes in the cycle or None.
        """
        nodes_visited.add(node_key)
        nodes_in_cycle.append(node_key)
        for node in self.nodes[node_key]['next_nodes']:
            if node in nodes_in_cycle:
                # The graph cycle starts at the index of node in nodes_in_cycle.
                return nodes_in_cycle[nodes_in_cycle.index(node):]
            if node in nodes_visited:  <<<<------------ Should be "node not in nodes_visited"
                dfs_nodes = self.depth_first_search(node, nodes_visited, nodes_in_cycle)
                if dfs_nodes:
                    return dfs_nodes
 
        # This node_key is not part of the graph cycle.
        nodes_in_cycle.pop()
        return None



 Comments   
Comment by Githook User [ 28/Apr/17 ]

Author:

{u'username': u'elouie99', u'name': u'Eddie Louie', u'email': u'eddie.louie@mongodb.com'}

Message: SERVER-28971 Error in depth_first_search algorithm incorrectly recurses on visited nodes

(cherry picked from commit e2196c8ee508a99c0d9472f061414da2f79c1e50)
Branch: v3.4
https://github.com/mongodb/mongo/commit/70cddc46ab0dee311711bffc16a61d02d413e506

Comment by Githook User [ 25/Apr/17 ]

Author:

{u'username': u'elouie99', u'name': u'Eddie Louie', u'email': u'eddie.louie@mongodb.com'}

Message: SERVER-28971 Error in depth_first_search algorithm incorrectly recurses on visited nodes
Branch: master
https://github.com/mongodb/mongo/commit/e2196c8ee508a99c0d9472f061414da2f79c1e50

Generated at Thu Feb 08 04:19:34 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.