modules page breaks with dependancies on uninstalled modules

This is my first attempt at patching core, so let's see how it goes.

This patch basically creates a recursive function to sort the $enable_modules array() so that dependencies are on the top of the list, and the modules that depend on them are lower down on the list. I've tested it with forum module, as well as checking to make sure the changes are passed through the confirm_form for this page.

I've tried to comment my code clearly so its understandable, please give me constructive feedback on my patch. I'm sure there is some way to do this without creating extra form values, but I didn't see it.

Dave

As we don't have recursive dependencies (ie. we really only check one level of dependency), what about adding the dependent modules to the *beginning* of the modules to enable when the dependency confirmation page is submitted? Any reason this should not be enough? Unfortunately our dependency system is not complete, but I might miss something important.

Shouldn't this be considered as a serious flaw in Drupal core?

Wim: How else could web consider it a serious flaw then marking it a critical bug?

Okay so maybe I'm confused on the issue here.

What this patch does is basically take $enable_modules and checks each module in turn to see if it has any dependencies. If it does, then it checks each of the dependencies in turn to see if they have any dependencies, and so on. If the module does not have any dependencies, then it adds it back to the list of modules to enable. This means that modules are added to the list in the correct order for installation.

What this patch does not do is check to make sure that the list of $enable_modules is correct in the first place, this is presumably handled by previous code.

Suppose I have module A which requires module B, which in turn requires module C. Since module B only requires module C, it will be available to be enabled, and since module A only requires module B, it will be available to be enabled. This patch will make sure that the install hooks are processed in the order C -> B -> A.

I could easily simplify this patch so it just takes any dependencies ands adds them to the beginning of the list, but then the above case might fail once in a while because of the alphabetical ordering of the modules. Suppose the modules are listed in the order C, A, then B. This would correctly enable C, then B, then A even using a flattened algorithm. However if the modules are listed A, B then C, a non-recursive algorithm would enable B first, then A, then C which is not the order we want.

I just tested, and in such a case, you can enable module 3, which will enable module 2, which will leave you unable to enable module 1. This is definitely a problem, so I think we should figure out how to do recursive dependencies.

OK, so let's see what Drupal 6 does. I added A B and C modules to my test system. A depends on B, B depends on C. If I try to enable A, I get a note that I should enable B. I OK the note and then I am left with A and B enabled, but C not. So as I said, recursive dependency checking was never a feature of the dependency checker.

This issue is about the problem that in this case (regardless of whether we have a C at all or not), a_install() runs before b_install() because of the alphabetical ordering, even through A depends on B, so B should be installed first. This is easy to test with a drupal_set_message() in a_install() and b_install().

Attached images of the module screen and the sample modules for your testing.

So what you are saying is that we should make this patch as simple as possible, not worry about any usability enhancements in the dependency checker, and just get the order of the installation correct. I'll work on simplifying my patch to just do this.

Dave

dwees: I don't see that your patch in #1 does anything to solve the dependency deepness missing feature, but the ordering is architected as if this feature would not be missing, so it is definitely overkill as it is. Either recursive (= multi level) dependency checking should be done or your ordering code should be simplified a lot. IMHO this recursive checking is not yet added, because it looked far from trivial.

Gábor: sorry, I misinterpreted your comment.

My recursive version of the patch will handle this fine I think, but I'm having trouble with the non-recursive version. Having found the complicated solution, I'm having trouble with the simple solution.

it isn't the right time now, but i think that the recursive checking patch here is quite elegant and belongs in D7.

I got a chance to do some work on this, and had some code which I thought worked, but unfortunately it didn't work when coming from the confirm form. I'll try and fix it up soon, just giving an update.

Okay I think I have it resolved. This basically sorts the modules so that the enabled modules and the new modules to be enabled are enabled before their dependent modules. It checks one level below, to make sure that any modules which have dependent modules do not themselves have any dependencies, if they do, those dependencies are handled first.

It is not a recursive sorter, which I agree is inappropriate until we have a recursive installer (maybe we'll see this in Drupal 7).

I've also attached an example of 3 modules, t1, t2, and t3 in which t1 depends on t2, which depends on t3.

A quick look at the code reveals that there are some coding style issues:
- Doxygen for the new function is missing
- Comments should be like sentences: start with capital letters, and end them with a period.
- Comments should wrap at col 78. (Or is it 80? I haven't found any official policy on this one yet.)
- I'm not sure that continue statement inside an if is acceptable, nor necessary for legibility.

Okay, I've added the Doxygen comment for the function, cleaned up the other comments, and made my function slightly more general so that is more likely to be able to be reused.

Continue statement is unnecessary, but I've added a comment to keep the nested if instead (since we want to occasionally 'skip' a module, particularly when we have already added it to the top of the list).

Dave

It fails if t1 depends on both t2 and t3, and t2 depends on t3, and there's a fourth module (t4 say) somewhere that depends on t1 - even if t4 is not enabled, t2_install runs before t3_install.

Attached the modified files to illustrate. Try to enable t1, t2, and t3, but not t4.

That seems like an edge case to me but I'll see if there is an easy fix in the code. I'm getting worried that we may still need some sort of recursion here, because we can imagine even more convoluted dependency relationships.

Hah. I just made an exam today that covers this stuff.

Recursive module dependency checking (and installation) is basically an application of graphs. If you solve this problem from that perspective, you can handle any set of dependencies. A solution to this problem is PERT.

This obviously is non-trivial to implement if you haven't learned about this before. Unless somebody can come up with something better, I may give it a shot (but I'm still in my exam period, so time is very sparse).

Ok, I've rewritten the function created by dwees. Now it should work in ANY case.

Here's the patch:

After testing it a bit, I've found some bugs (I don't know if that are cause of 6.x itself, my changes, or the first pacth I applied).

I've tested to load a lot of modules, and corrected all bugs I've seen.

Download the new patch.

Wim, we are not about to fix recursive dependency checking here. This issue is about running the install hooks in order of dependency, so modules depending on others can use their API / data when being installed.

It's interesting that we came to the same conclusion. In order to order this properly, we either need a horribly complex linear function, or a relatively simple recursive function.

Can you create a patch which removes the debugging code, clean up the coding standards a bit?

For instance:

if (blah) {

}

etc...

Gábor, I don't see what the difference is between "running the install hooks in order of dependency" and "recursive dependency checking". To do the first in a sensible manner, you need to do it recursively... dwees seems to agree with me.

Is there something I'm missing here, besides the fact that you would rather not introduce such critical new functionality (which can easily be tested thoroughly though) this late in the cycle?

Wim, with only one level of dependencies checked in Drupal 6 (see http://drupal.org/node/194010#comment-635940 above), I don't see why a full recursive check would be needed to order the install hooks properly. Anyway, if that way seems to be easier to you all, then go ahead, feel free to do it. Make sure to think about possible circles in the graph, and any other kind of missing pieces. You'd also need to go in and modify the code which disables checkboxes for modules which does not have their dependency present to go recursive, etc.

See #18: http://drupal.org/node/194010#comment-649407.

While that *is* edge-case-ish, module dependencies is something that is fairly likely to have edge cases I think. And users expect it to "just work".

I'll try to cook up a function that returns valid installation orders tomorrow.

I don't see what's so edge-case-ish about it. It's just three chained dependencies, with extra dependencies added to prevent the situation Gábor described in #6 where B ends up enabled without its dependency.

Well, it doesn't occur very often. That's why I labeled it as "edge-case-ish". But I obviously agree that it should be supported.

Modules being enabled without enabling their dependencies is a separate issue than this one, although I agree we'd be running over the same piece of code.

Basically I feel like the installer needs to be recursive over-all (with checks in place to avoid cyclic recursion and WSODs as a result) but I think we can do this in stages.

First in Drupal 6, we fix the order of the modules bug, with a recursive function, pretty much one of the ones we have described, realizing that it is a bit of overkill for what we need. Then for Drupal 7, we focus on the bigger (and separate) of checking for recursive dependencies. Currently a bug with the installer is that if A needs B and B needs C, and I only try to enable A, then B will be enabled in the confirm form, and C will not be enabled at all. This is a separate issue though, this particular issue is about changing the order of the modules when installed.

Does this make sense? Is it reasonable to use a function in Drupal 6 that we realize will be necessary for Drupal 7?

dwees: As I have said, if it is not easier to solve in Drupal 6 with a Drupal 6 specific solution, the go with a more broader one. Go with what's cleaner to implement.

We do not handle "deep dependency"? I remembered that we do. Ah, my dependency system written in 2005 spring (!) was handling it but not the one we have now. Someone with less perseverance would have simply walked away from core development after that issue. And yet, I am here and probably being masochist I assign myself to fix the original issue and deep dependency in one take today.

This patch uses nothing from the issue but the test modules and even those are amended to use file_put_contents (php5 only) to verify the order as drupal_set_message displays in reversed order than set. The ordering part is quite simple. The deep dependency builder is not complicated either just it needs to protect against circular dependency. The core compatiblity checker was already recursive so that also needs similar protection. I have tested with and without circular dependencies (for with, remove the ; in t3.info).

D'oh. Of course it's not module_enable that needs patching... and then, we should let PHP do the actual movement or it can get ugly. I am fairly sure the weighting algorithm I have implemented can't get into an infinite loop, it can be proven with induction -- exactly because there are no circular dependencies (aka DAGs in the directed dependency graph).

Keeping up with HEAD.

Applying the patch and installing I get the following errors:

* notice: Undefined offset: 0 in /home/balu/projects/drupal/d6-b4/includes/install.inc on line 79.
* notice: Trying to get property of non-object in /home/balu/projects/drupal/d6-b4/includes/module.inc on line 287.

without the patch the installation completes without this error message.

Installing t1, messages (list confirmed from debug file too):
# t3: This module should be installed first
# t2: This module should be installed second
# t1: This module should be installed last

Installing t2 offers to install too t3, so this works as well.
Installing drupal with the patch on works also without the notices.

I modified t3 to depend on t1 hence creating circular dependency, the checkboxes turn unselectable, and a -circular- error flag is appearing at the dependency infos: -circular- (missing).

I also done some testing with the module, and indeed, it nicely detects multiple level dependencies. The only thing I don't like about this is the user experience of a circular dependency. Using -circular- internally is understandable, but exposing this to the user does not help much to the admin wondering what the hell is happening. A friendly error message should be displayed instead about the circular dependency, ie:

"This module is part of a circular dependency, and therefore cannot be enabled. Contact the maintainers of the required modules."

Or something along these lines. (This requires that every other part of the dependency be displayed, except -circular-.)

For reference, here is the current UI, which I commented on.

+ drupal_set_message(t('%module is part of a circular dependency. This is not supported and you will not be able to switch it on.', array('%module' => $file->info['name'])), 'error');

There is the error message already in the patch. Removing all or parts of the -circular- (missing) flag or changing it is IMO a minor follow up patch. It's extremely rare that the user faces this condition.

Hrm, I did not notice these errors popping but, but in a real situation, I'd expect people to load the page and scroll from top, so they will see it.

Anyway, now that the inner workings seem to be fine, I found docs in this patch lacking. I tried to sat down and document myself, but found the difference between _module_build_dependents() and _module_build_dependencies() unnoticeable. Why do these need to be two different functions? (Both are internal/private so API breakage does not come into question here). The module ordering is also without docs. -circular- is used before documented. Marking as CNW for the _module_build_dependents() and _module_build_dependencies() merging(?)

I will add docs in the morning, if you so want. I always find it hard to document stuff like this, explaining graphs in layman terms is no fun but yes I will do it. Why you want to merge? One of them recursively adds an edge to the graph for every path, the other creates another directed graph, just with reversed directions, they have nothing in common. If you want I can rename the function (but to what?) and merge the two into one but honestly I would rather not.

Well, maybe clear documentation on what these do will help me understand why not to merge them. Thanks a lot!

As I am instructed, so I have acted, and have merged the two functions. As the _module_build_dependents became one line of code inside _module_build_dependencies I can see the wisdom of merging despite my grumbling above. Added a heap of comments too.

Great, thanks for coming back with a refined version. This all looks fine to me, tested with the test module set posted above. All is looking fine, so committed!

A little bug I noticed with this when testing other patches: when you enable a module, the page you get back has the circular dependency error messages three times. This is probably due to the multiple requests which the module enable process goes through, so the function is being called multiple times. This should be avoided though.

Did we fix dependencies at uninstall as well? In this case, we need to disable dependants first. Would be nice.

Moshe: since all modules your one depends on have their checkbox fixed (ie you cannot modify them), you cannot disable a module and something else which that module used at once.

Gábor: yet I succeeded in doing so. You're actually 100% right though. How exactly?

(Panels module, Mini Panels module depends on this)

1) Disable the Mini Panels module. Hit save.
2) Disable the Panels module. Hit save.
3) Go to the uninstall tab. Uninstall the Mini Panels module. Hit save. Now you'll get a big fat nice error, because the Mini Panels module depends on the Panels module to uninstall stuff.

The most logical solution is for the Mini Panels module to simply include the panels.module file (or whatever file is necessary). I think this should be documented in the module development section, to avoid confusion for the user.
So this issue is very similar to the hook_update_N() functions relying on old Drupal core functions which may have different signatures, etc.

My conclusion would be: this isn't a bug in the code, but it's a missing piece of documentation.

Yes, we talked about this elsewhere. The actual issue is the order of disable and then uninstall actions. But this is a user driven process, you go disable modules and then uninstall or disable and uninstall one by one. It is not something we can fix in core IMHO. Asking the user to enable some module because it is required to disable something else is not exactly nice, and also disallowing to disable a module because some other module depends on it for uninstall is the same. What if I would not like to uninstall it, just disabled it. Let me disabled the other one too. So how is this done is up to the user, and (contrib) modules can work around possible workflow problems as they are able to.

This commit breaks when a module specifies a dependency on a module that does not exists. Huge screen of warnings, the name of the required module is not shown, and there is a bogus item added at the end of the page. Simply wrapping the meat of the _module_build_dependencies function in an

if (isset($files[$dependency_name])) { 

seems to fix it.

Updating name to reflect current problem. This issue has generated lots of duplicates.

http://drupal.org/node/203794 better fix.

My concern at http://drupal.org/node/194010#comment-657958 above was not fixed yet.

Cleaning up the issue queue.