Moodle
  1. Moodle
  2. MDL-28040

Moodle 2.0 Navigation tree algorithm faulty

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Blocker Blocker
    • Resolution: Fixed
    • Affects Version/s: 2.0.3
    • Fix Version/s: 2.0.4, 2.1.1
    • Component/s: Navigation
    • Labels:
    • Environment:
      Likely to be any, probable to be any database
    • Database:
      Any
    • Testing Instructions:
      Hide
      1. Find a site with lots of courses and real branching series of categories... alternativily create one
      2. Browse to the front page, courses, categories, and modules.
      3. For each check the following:
        • The navigation generates correctly for what you are viewing
        • The navigation generates the surrounding information correctly as well
      Show
      Find a site with lots of courses and real branching series of categories... alternativily create one Browse to the front page, courses, categories, and modules. For each check the following: The navigation generates correctly for what you are viewing The navigation generates the surrounding information correctly as well
    • Workaround:
      Hide

      Replace Line 1270 with:
      $categories = $DB->get_records_select('course_categories', $select, $params, 'depth, sortorder');

      Show
      Replace Line 1270 with: $categories = $DB->get_records_select('course_categories', $select, $params, 'depth, sortorder');
    • Affected Branches:
      MOODLE_20_STABLE
    • Fixed Branches:
      MOODLE_20_STABLE, MOODLE_21_STABLE
    • Pull Master Branch:
      wip-MDL-28040-master
    • Rank:
      17665

      Description

      In Moodle 2.0.3 the navigation tree algorithm is flawed. In all cases where the 'sortorder' field has been variously changed from the default 999 by moving categories around, subcategories are likely to precede their parent categories in the $categories array, thus forcing an error:
      Warning: array_key_exists() expects parameter 2 to be array, null given in .../moodle/lib/navigationlib.php on line 1298
      ...and losing all the sub-categories located above the parent in that array!!
      ...and preventing navigation operating correctly on remaining sub-categories!

      Debugging on. Any case where a sub-category has a lower 'sortorder' value than its parent (which will of course have a lower 'depth' value)!
      But without debugging on you can still see the fault in the resultant tree.

      1. array_key_exists_fault.tiff
        170 kB
        John White
      2. array_key_exists_repair_1.tiff
        145 kB
        John White
      3. load_all_categories.php
        2 kB
        John White

        Issue Links

          Activity

          Hide
          John White added a comment - - edited

          There is a discussion about this error here:
          http://moodle.org/mod/forum/discuss.php?d=177878
          though most of the entries made are only about trying to narrow down the error source.

          Show
          John White added a comment - - edited There is a discussion about this error here: http://moodle.org/mod/forum/discuss.php?d=177878 though most of the entries made are only about trying to narrow down the error source.
          Hide
          John White added a comment -

          A further very careful check of this situation, with the new sort order in place shows that there are still circumstances in which categories can be lost. This is because categories are added to $categories on the fly in the algorithm, and these need not respect the entirety of a 'depth, sortorder' sorting. So sub-sub-categories added above their own parent in the array will not appear in the navigation tree. More is needed.

          Show
          John White added a comment - A further very careful check of this situation, with the new sort order in place shows that there are still circumstances in which categories can be lost . This is because categories are added to $categories on the fly in the algorithm, and these need not respect the entirety of a 'depth, sortorder' sorting. So sub-sub-categories added above their own parent in the array will not appear in the navigation tree. More is needed.
          Hide
          Michael de Raadt added a comment -

          Thanks for reporting this.

          I've put it on our backlog and we'll try to get to it as soon as we can.

          In the meantime, please keep working on this. Adding more information, such as screenshots, replication instructions or more code, will help us and other users.

          Show
          Michael de Raadt added a comment - Thanks for reporting this. I've put it on our backlog and we'll try to get to it as soon as we can. In the meantime, please keep working on this. Adding more information, such as screenshots, replication instructions or more code, will help us and other users.
          Hide
          John White added a comment -

          The fault appears whenever the sortorder value of a sub-category is less than that of the category above it. Then the error occurs and those sub-categories are missed from the nav tree.

          Show
          John White added a comment - The fault appears whenever the sortorder value of a sub-category is less than that of the category above it. Then the error occurs and those sub-categories are missed from the nav tree.
          Hide
          John White added a comment -

          As a first repair I added 'depth ASC' into the sortorder as show above. This has the effect of putting the upper categories ahead of their sub-categories irrespective of their 'sortorder' field, which appears to sort out the problem. There are however, circumstances in which parallel sub-categories can then still lose their sub-sub-categories because they are added into the structure arbitrarily later. The fix is a proper re-write of the algorithm.

          Show
          John White added a comment - As a first repair I added 'depth ASC' into the sortorder as show above. This has the effect of putting the upper categories ahead of their sub-categories irrespective of their 'sortorder' field, which appears to sort out the problem. There are however, circumstances in which parallel sub-categories can then still lose their sub-sub-categories because they are added into the structure arbitrarily later. The fix is a proper re-write of the algorithm.
          Hide
          John White added a comment - - edited

          Consequently, I have a suggested rewrite of the offending function as follows:

          protected function load_all_categories($categoryid=null) {
          global $DB;
          $sortorder = 'depth DESC, sortorder ASC, id ASC';
          $fields = '*';
          if ($categoryid == null)

          { $categories = $DB->get_records('course_categories', array('parent'=>'0'), 'sortorder'); }

          else

          { $category = $DB->get_record('course_categories', array('id'=>$categoryid), $fields, MUST_EXIST); $wantedids = explode('/', trim($category->path, '/')); $root = $wantedids[0]; $select = 'path = "/'.$root.'" OR path LIKE "/'.$root.'/%"'; // this select gets all the categories $root and below (as $root is in path base) $categories = $DB->get_records_select('course_categories', $select, null, $sortorder, $fields); // this now gives ALL the categories from this $root downwards, but depth ordered, not just sortorder-ed }

          $structured = array();
          foreach ($categories as $category) {
          $id = $category->id;
          $parentid = $category->parent;
          $children = array();
          // $structured array takes default entry for this $id in case $id has no children
          $structured[$id] = array('category'=>$category, 'children'=>$children);
          foreach ($structured as $childkey=>$child) {
          if ($child['category']->parent == $id)

          { // all the children of this $id placed in the $children array $children[$childkey] = $child; // then that $child will no longer be needed as a separate $structured entry unset($structured[$childkey]); }

          // $structured array now takes entry with children if there are any ( and the default if there are not)
          $structured[$id] = array('category'=>$category, 'children'=>$children);
          }
          }
          unset($children);

          foreach ($structured as $category)

          { $this->add_category($category, $this->rootnodes['courses']); }

          if ($categoryid !== null && count($wantedids)) {
          foreach ($wantedids as $catid)

          { $this->load_all_courses($catid); }

          }
          }

          This method is more robust because it does not rely on later additions to the $categories array.
          Instead it finds the $root category for the current category i.e. the start of 'path' /?/
          It then determines all the categories with $root in the path base (so that none can be missing),
          taking these in order, deepest first but otherwise in 'sortorder'.
          The algorithm then builds the $structured array from the bottom up enclosing all child categories within the next category up until reaching the root category.

          Show
          John White added a comment - - edited Consequently, I have a suggested rewrite of the offending function as follows: protected function load_all_categories($categoryid=null) { global $DB; $sortorder = 'depth DESC, sortorder ASC, id ASC'; $fields = '*'; if ($categoryid == null) { $categories = $DB->get_records('course_categories', array('parent'=>'0'), 'sortorder'); } else { $category = $DB->get_record('course_categories', array('id'=>$categoryid), $fields, MUST_EXIST); $wantedids = explode('/', trim($category->path, '/')); $root = $wantedids[0]; $select = 'path = "/'.$root.'" OR path LIKE "/'.$root.'/%"'; // this select gets all the categories $root and below (as $root is in path base) $categories = $DB->get_records_select('course_categories', $select, null, $sortorder, $fields); // this now gives ALL the categories from this $root downwards, but depth ordered, not just sortorder-ed } $structured = array(); foreach ($categories as $category) { $id = $category->id; $parentid = $category->parent; $children = array(); // $structured array takes default entry for this $id in case $id has no children $structured [$id] = array('category'=>$category, 'children'=>$children); foreach ($structured as $childkey=>$child) { if ($child ['category'] ->parent == $id) { // all the children of this $id placed in the $children array $children[$childkey] = $child; // then that $child will no longer be needed as a separate $structured entry unset($structured[$childkey]); } // $structured array now takes entry with children if there are any ( and the default if there are not) $structured [$id] = array('category'=>$category, 'children'=>$children); } } unset($children); foreach ($structured as $category) { $this->add_category($category, $this->rootnodes['courses']); } if ($categoryid !== null && count($wantedids)) { foreach ($wantedids as $catid) { $this->load_all_courses($catid); } } } This method is more robust because it does not rely on later additions to the $categories array. Instead it finds the $root category for the current category i.e. the start of 'path' /?/ It then determines all the categories with $root in the path base (so that none can be missing), taking these in order, deepest first but otherwise in 'sortorder'. The algorithm then builds the $structured array from the bottom up enclosing all child categories within the next category up until reaching the root category.
          Hide
          John White added a comment - - edited

          load_all_categories() as attached.

          Show
          John White added a comment - - edited load_all_categories() as attached.
          Hide
          John White added a comment -

          As a further aside, which relates to functionality, but not to this algorithm, I note that whereas Categories 'dimmed' in the Categories block remain dimmed in the Navigation tree, but Courses dimmed in the Categories block do not remain dimmed in the tree. So there is another logic flaw to find here.

          Show
          John White added a comment - As a further aside, which relates to functionality, but not to this algorithm, I note that whereas Categories 'dimmed' in the Categories block remain dimmed in the Navigation tree, but Courses dimmed in the Categories block do not remain dimmed in the tree. So there is another logic flaw to find here.
          Hide
          Sam Hemelryk added a comment -

          Hi John,

          Thanks for the work on this so far.
          I've elevated it to a blocker and added it into our current sprint. This way it will get looked for sure and the end solution included in the next release.

          Cheers
          Sam

          Show
          Sam Hemelryk added a comment - Hi John, Thanks for the work on this so far. I've elevated it to a blocker and added it into our current sprint. This way it will get looked for sure and the end solution included in the next release. Cheers Sam
          Hide
          Sam Hemelryk added a comment -

          Starting development - I picked up a typo breaking the new code in the master branch in the same way!

          Show
          Sam Hemelryk added a comment - Starting development - I picked up a typo breaking the new code in the master branch in the same way!
          Hide
          John White added a comment -

          Sam,
          Sorry that the code I pasted in looks a mess! I realise now this is because I copy-[asted from Smultron/Fraise on iMac and Atlassian (Tracker) expects MS-DOS style line breaks.
          However, the code in the attached file load_all_categories.php does not suffer that problem!
          The algorithm is more deterministic than the one existing in 2.0.3 as it does not have to add categories into the tree after the structure has been set up. Instead, as I said, it builds the entire $structured array from the lowest (and therefore innermost) child upwards towards the top or $root category.
          There are two aspects of this algorithm that I still have unanswered questions about and they are these:

          1. Will the SELECT statement implied in Line 11 of that file:
          $select = 'path = "/'.$root.'" OR path LIKE "/'.$root.'/%"';
          ...parse correctly in all database types?

          2. Does this new algorithm block the arrival of courses in the tree when the user clicks on unexpanded category nodes? I have some concerns about this possibility.

          I would like to ask: Were the lowest category nodes omitted from the $structured array intentionally?
          If so, why was this?

          Regards, John

          Show
          John White added a comment - Sam, Sorry that the code I pasted in looks a mess! I realise now this is because I copy-[asted from Smultron/Fraise on iMac and Atlassian (Tracker) expects MS-DOS style line breaks. However, the code in the attached file load_all_categories.php does not suffer that problem! The algorithm is more deterministic than the one existing in 2.0.3 as it does not have to add categories into the tree after the structure has been set up. Instead, as I said, it builds the entire $structured array from the lowest (and therefore innermost) child upwards towards the top or $root category. There are two aspects of this algorithm that I still have unanswered questions about and they are these: 1. Will the SELECT statement implied in Line 11 of that file: $select = 'path = "/'.$root.'" OR path LIKE "/'.$root.'/%"'; ...parse correctly in all database types? 2. Does this new algorithm block the arrival of courses in the tree when the user clicks on unexpanded category nodes? I have some concerns about this possibility. I would like to ask: Were the lowest category nodes omitted from the $structured array intentionally? If so, why was this? Regards, John
          Hide
          Sam Hemelryk added a comment -

          Hi John,

          Thanks for all the work on this issue so far.
          I've finally found a bit of time to really look into this issue and at your solution.
          First up however in regards to your questions:

          1. In regards to the LIKE statement it is near perfect only one minor thing would need to be changed - the string in SQL should be within single quotes not double quotes.
          2. In regards to the algorithm and AJAX loading on the surface things appear to work fine however there are problems with the algorithm itself (I'll note these below).

          Certainly what you have so far is very close to complete however there is one prominent bug in the way the loading of categories is happening with the load_all_categories function you have, its a fairly buried in the logic of the navigation so bear with me.

          When you are viewing the navigation from the front page of the site or any page within the system context things work perfectly.
          However once you enter into a course and are required to load a categories to display the course + its category a bug becomes apparent.
          The function at the moment is loading all of the categories that share the root category.
          However when loading courses, only courses within the categories along the path of the category being loaded are loaded into the navigation.
          Because we are loading only courses that belong to the specific courses categories there is a good chance that we will load categories without loading their courses. Presently this leads to those courses not being available on the navigation.
          A simple example if we have the following category structure:

          /a
          /a/b
          /a/b/course1
          /a/b/c
          /a/b/c/course2

          Lets say the user is viewing course 1, the load_all_categories method is going to load categories a, b, and c. However it will only call ask navigation to load courses for a, and b. Category c won't have its courses loaded because it isn't part of the path to category b. This renders course 2 unreachable from the navigation.
          The solution to this problem is to load courses for all of the categories that are being loaded by this function.
          However it's not really a practical solution as the algorithm is causing all categories sharing the root category being loaded. Loading categories is pretty easy - one DB call to get them and there is minimal information. But on a site with tens/hundreds of categories and potentially hundreds/thousands of courses having to load categories + all their courses will cause a huge performance hit.
          This really brings to light the nature of the problem, while bulk loading categories is a solution its a potentially flawed solutions - especially on large installations.
          In summary what you have got is close but would need more work to get it working correctly.

          I've been looking closely at the branches MOODLE_20_STABLE, MOODLE_21_STABLE, and master and have found an interesting solution.
          Have you seen MDL-27809? It is an issue that led to performance improvements for the navigation and as part of the changes load_all_categories was re-written. The changes for this issue were applied to MOODLE_21_STABLE and master only as they were for performance mostly.
          Interestingly enough this bug still exists after those changes however it is a simple fix as the bug is in those branches an oversight.
          I've created a fix for those branches two branches you can see here: https://github.com/samhemelryk/moodle/compare/master...wip-MDL-28040-master (noticing I stole you improvements to the ORDER by clause for them )
          Anyway I looked at the changes that were made for MDL-27809 and found that I could backport them from master to MOODLE_20_STABLE, and that I could then apply the patch for master/MOODLE_21_STABLE above to it as well, fixing the problem and boosting the performance of the navigation.

          I've talked to Eloy about the prospect of back porting the MDL-27809 changes and then applying the simple fix to all three branches and he seems happy with it providing its all tested and works well.
          As such I'll put this up for integration now and hopefully this issue will be resolved in the next weekly.

          Cheers
          Sam

          Show
          Sam Hemelryk added a comment - Hi John, Thanks for all the work on this issue so far. I've finally found a bit of time to really look into this issue and at your solution. First up however in regards to your questions: In regards to the LIKE statement it is near perfect only one minor thing would need to be changed - the string in SQL should be within single quotes not double quotes. In regards to the algorithm and AJAX loading on the surface things appear to work fine however there are problems with the algorithm itself (I'll note these below). Certainly what you have so far is very close to complete however there is one prominent bug in the way the loading of categories is happening with the load_all_categories function you have, its a fairly buried in the logic of the navigation so bear with me. When you are viewing the navigation from the front page of the site or any page within the system context things work perfectly. However once you enter into a course and are required to load a categories to display the course + its category a bug becomes apparent. The function at the moment is loading all of the categories that share the root category. However when loading courses, only courses within the categories along the path of the category being loaded are loaded into the navigation. Because we are loading only courses that belong to the specific courses categories there is a good chance that we will load categories without loading their courses. Presently this leads to those courses not being available on the navigation. A simple example if we have the following category structure: /a /a/b /a/b/course1 /a/b/c /a/b/c/course2 Lets say the user is viewing course 1, the load_all_categories method is going to load categories a, b, and c. However it will only call ask navigation to load courses for a, and b. Category c won't have its courses loaded because it isn't part of the path to category b. This renders course 2 unreachable from the navigation. The solution to this problem is to load courses for all of the categories that are being loaded by this function. However it's not really a practical solution as the algorithm is causing all categories sharing the root category being loaded. Loading categories is pretty easy - one DB call to get them and there is minimal information. But on a site with tens/hundreds of categories and potentially hundreds/thousands of courses having to load categories + all their courses will cause a huge performance hit. This really brings to light the nature of the problem, while bulk loading categories is a solution its a potentially flawed solutions - especially on large installations. In summary what you have got is close but would need more work to get it working correctly. I've been looking closely at the branches MOODLE_20_STABLE, MOODLE_21_STABLE, and master and have found an interesting solution. Have you seen MDL-27809 ? It is an issue that led to performance improvements for the navigation and as part of the changes load_all_categories was re-written. The changes for this issue were applied to MOODLE_21_STABLE and master only as they were for performance mostly. Interestingly enough this bug still exists after those changes however it is a simple fix as the bug is in those branches an oversight. I've created a fix for those branches two branches you can see here: https://github.com/samhemelryk/moodle/compare/master...wip-MDL-28040-master (noticing I stole you improvements to the ORDER by clause for them ) Anyway I looked at the changes that were made for MDL-27809 and found that I could backport them from master to MOODLE_20_STABLE, and that I could then apply the patch for master/MOODLE_21_STABLE above to it as well, fixing the problem and boosting the performance of the navigation. I've talked to Eloy about the prospect of back porting the MDL-27809 changes and then applying the simple fix to all three branches and he seems happy with it providing its all tested and works well. As such I'll put this up for integration now and hopefully this issue will be resolved in the next weekly. Cheers Sam
          Hide
          Sam Hemelryk added a comment -

          Up for integration now

          Show
          Sam Hemelryk added a comment - Up for integration now
          Hide
          Sam Hemelryk added a comment -

          Ahh I should add the performance changes cover a pretty wide area of navigation.
          Eloy if this is a problem let me know and I'll create a version that reverts all but the required perf changes of MDL-27809.

          Cheers
          Sam

          Show
          Sam Hemelryk added a comment - Ahh I should add the performance changes cover a pretty wide area of navigation. Eloy if this is a problem let me know and I'll create a version that reverts all but the required perf changes of MDL-27809 . Cheers Sam
          Hide
          John White added a comment -

          Hi Sam,
          Thanks for keeping me abreast of developments. I understand the concern about the performance hit, which could in effect destroy the usefulness of some big sites, and as it is Navigation adds a noticable extra overhead. Thanks for the explanation too... that certainly helps.

          Is there an expectation of when this will appear in a stable 2.0+ ? We are rapidly moving towards converting a second copy of our live data to 2.0., (still not live itself), though I have been working for weeks on sorting out horrendous bugs in the Wiki conversion so that we can do so. Because most of my current work is for a Uni, we get a very narrow window in which to jump to 2.0 this Summer, otherwise we would have to postpone to Christmas at least! Of course, many Schools & Colleges will be in exactly the same boat, and will sensibly postpone for a term or two, but we have several really big developments we want to achieve, and I'm reluctant to write them into 1.9+ and then do it all again in 2!
          Cheers,
          John

          Show
          John White added a comment - Hi Sam, Thanks for keeping me abreast of developments. I understand the concern about the performance hit, which could in effect destroy the usefulness of some big sites, and as it is Navigation adds a noticable extra overhead. Thanks for the explanation too... that certainly helps. Is there an expectation of when this will appear in a stable 2.0+ ? We are rapidly moving towards converting a second copy of our live data to 2.0., (still not live itself), though I have been working for weeks on sorting out horrendous bugs in the Wiki conversion so that we can do so. Because most of my current work is for a Uni, we get a very narrow window in which to jump to 2.0 this Summer, otherwise we would have to postpone to Christmas at least! Of course, many Schools & Colleges will be in exactly the same boat, and will sensibly postpone for a term or two, but we have several really big developments we want to achieve, and I'm reluctant to write them into 1.9+ and then do it all again in 2! Cheers, John
          Hide
          Sam Hemelryk added a comment -

          Hi John,

          No probs, and thank you again for the amazing effort you've put into this.
          The solution is up for integration now, providing no problems are found it should be included in the weekly release on Wednesday, and will be included in the 2.0.4, 2.1.1, and 2.2 releases (plus of course future releases).
          Certainly I don't think those releases will be too far away now hopefully, although not in the next 3 weeks I imagine.

          It is a shame about the wiki issues - however I'd quite believe it as we've seen some fantastic bug reports come through.
          Certainly any bugs you can report (if you haven't already) and any solutions you may have to those bugs would be greatly appreciated if you are able to contribute them!
          As for the deadline - yes again, I think there will be many an institute looking at the practicalities of upgrading for the upcoming semester. Of course we'd love to see you all get onto Moodle 2 however timing is everything, and its got to be right for you.

          Cheers
          Sam

          Show
          Sam Hemelryk added a comment - Hi John, No probs, and thank you again for the amazing effort you've put into this. The solution is up for integration now, providing no problems are found it should be included in the weekly release on Wednesday, and will be included in the 2.0.4, 2.1.1, and 2.2 releases (plus of course future releases). Certainly I don't think those releases will be too far away now hopefully, although not in the next 3 weeks I imagine. It is a shame about the wiki issues - however I'd quite believe it as we've seen some fantastic bug reports come through. Certainly any bugs you can report (if you haven't already) and any solutions you may have to those bugs would be greatly appreciated if you are able to contribute them! As for the deadline - yes again, I think there will be many an institute looking at the practicalities of upgrading for the upcoming semester. Of course we'd love to see you all get onto Moodle 2 however timing is everything, and its got to be right for you. Cheers Sam
          Hide
          Petr Škoda added a comment -

          Integrated, thanks.

          Show
          Petr Škoda added a comment - Integrated, thanks.
          Hide
          Michael de Raadt added a comment -

          Test results: works as expected. Ordering maintained in course list and navigation

          Show
          Michael de Raadt added a comment - Test results: works as expected. Ordering maintained in course list and navigation
          Hide
          Vinayak Naik added a comment -

          I am new here. I have upgraded from 1.9 to 2.1 and seeing this error "Coding error detected, it must be fixed by a programmer: Category path order is incorrect and/or there are missing categories". After debugging, I found out that "Mon Jul 25 13:49:07 2011] [error] [client 192.168.1.50] Default exception handler: Coding error detected, it must be fixed by a programmer: Category path order is incorrect and/or there are missing categories Debug: \n* line 1477 of /lib/navigationlib.php: coding_exception thrown\n* ..."

          I thought that this thread is talking about the same issue. I gather from Sam's comment that the fix will be rolled out soon. Could you please guide me that the aforementioned fix would resolve my issue?

          Show
          Vinayak Naik added a comment - I am new here. I have upgraded from 1.9 to 2.1 and seeing this error "Coding error detected, it must be fixed by a programmer: Category path order is incorrect and/or there are missing categories". After debugging, I found out that "Mon Jul 25 13:49:07 2011] [error] [client 192.168.1.50] Default exception handler: Coding error detected, it must be fixed by a programmer: Category path order is incorrect and/or there are missing categories Debug: \n* line 1477 of /lib/navigationlib.php: coding_exception thrown\n* ..." I thought that this thread is talking about the same issue. I gather from Sam's comment that the fix will be rolled out soon. Could you please guide me that the aforementioned fix would resolve my issue?

            People

            • Votes:
              2 Vote for this issue
              Watchers:
              6 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: