On a Drupal site that came up for some minor alterations recently we came across an issue where some menu links disappeared for anonymous users while they appeared normally for the administrative users. On digging further we came across an issue with an implementation of hook_db_rewrite_sql in a contributed module. But along the way we had to debug the full process of generation of primary links and how node level access permissions are checked during this process.
Primary links are inserted into the page template from template_preprocess_page function in theme.inc. From here it calls menu_primary_links from menu.inc which calls menu_navigation_links with menu name as primary-links (unless primary links is configured to use some other menu). Now menu_navigation_links calls menu_tree_page_data to load the menu tree as a nested array for the given menu. By the time this function returns it would already have created the menu after checking access permissions.
menu_tree_page_data builds the nested array for the menu links from menu_links table and creates this hierarchically using two nested while loops to loop through menu_links and their children for the given menu. Once this is retrieved then menu_tree_collect_node_links is called to identify menu_links that are links to node view pages. Then a call to menu_tree_check_access checks for access to the links in the menu for the current user. The access to node_links are checked through a call to db_rewrite_sql to find nodes accessible to the current user given the list of nodes present in the menu_links for the node. Access to other links are checked through the corresponding access callbacks registered for the router items corresponding to the menu links.
Now db_rewrite_sql is not a frequently used db function but it is a powerful tool to check access for nodes when there are node level access restrictions and when you are querying on the node table (or taxonomy or comment) without having to load each node and to filter nodes at the listing level itself. db_rewrite_sql from database.inc calls db_rewrite_sql hook implementations from all modules that implements this hook. The hook allows modules to define a custom join with a custom where condition to filter out results of the original query. The node module offers an implementation that joins the node table with node_access table when custom access rules are enabled i.e. when view_all_nodes is not enabled.
The site we were working on had a db_rewrite_sql implementation in a contrib module that filtered out nodes erroneously that resulted in the corresponding menus vanish for the anonymous user. We fixed the issue in the hook_db_rewrite_sql and presto the vanished menu items appeared back from nowhere.