Plugin system

How would you write a plugin system for an image-processing application where one plugin is "dependant" on another plugin? For example I have an histogram plugin who has to call the grayscale plugin before showing the histogram. I could hard-code the grayscale function but it's ugly and I would have to do the same for a lot of other plugins.

I'm writing this in Qt (Trolltech) and C++, and I use the QLibrary object (not that it really matters...)

You could try some hackery involving the overloaded QLibrary::resolve().

>>2
What I would like is a different kind of "architecture." I already have all the plugins loaded with the constructor and all the pointers I got with resolve() are put in a structure. Everything would be fine if I had no dependencies.

But I don't know how I should react if an important plugin is missing. I can't move these important plugins in the application because there are too many of them. A simple solution would be to ask each plugin what other plugin it needs. This should not be a problem as long as I don't have circular referencies.

What I'm asking for is another way of doing things like this, something simpler.

I guess you could have a list of dependencies for each plugin, and if the complete dependency tree isn't available then you yell at the user or something. And it looks like you do need to handle circular references.

And it looks like you do need to handle circular references.

If you're using a list of dependencies, no you don't.

>>5
yes you do

>>6
No, you don't. You only really need to worry about circular references if you're walking a graph. In this case there's a simple way to handle it:

You keep two lists, A and B. A lists all currently loaded plugins. B lists unchecked dependencies.

Load new plugin, and request dependencies. Add returned dependencies to B.

Pop item off top of B and check if it's in A. If it's in A, drop item and check a new item in list B. If it's not in A, load new plugin, add new plugin to A, and then add new plugin's dependency list to B.

The END. Geez.

For the more rigorous:

A is empty, B is an initial list of plugins.

while B is not empty
  Pop X off B.
  If X exists in A, go to next iteration.
  Load X.
  Append X to A.
  Push X.dependencies to B.

Technically you are walking a graph there, you're just generating the nodes of the graph as you go, like a state space search. But your method should avoid circular dependecies well enough.

Wouldn't you want to load X's dependencies before you load X?  Suppose you have the libraries X and Y where X depends on Y.  Realistically, we don't necessarily *know* that X's dependency on Y isn't due to some initial code that's run when X is loaded.  So, if X depends on Y, we should load Y before we load X. 

I think this is also quite relevant when you take the case of a failure to load Y into account.  We load X and drop its dependency Y into our queue of things that we still need to load.  When Y's turn comes up, though, it fails to load because Y doesn't exist.  Now we've loaded X, X depends on Y, and Y doesn't exist.  That can't be the ideal situation.

I think you'd be better off pushing X onto a stack and trying to load its dependencies first.  Basically traversing the dependency graph from the deepest points and working your way back up to the starting node

The danger of circular dependencies is that if X depends on Y and Y depends on X, you can't deterministically decide which to load first.  Your solution doesn't solve or avoid circular dependencies, it simply dictates an arbitrary order.  Granted, that's what the Windows library loading subsystem does also, and it's widely understood that circular dependencies are the fault of the library developers, but I think it's a misrepresentation to claim that dictating an arbitrary order avoids any problems with circular dependencies.

Wouldn't you want to load X's dependencies before you load X?

If it's a plugin, who cares. The problems only arise once you start making calls that have dependencies. If the person starts using a plugin before all dependencies are solved, that's their fault.

dependency on Y isn't due to some initial code that's run when X is loaded

Then don't run it.

Seriously, mate, if he's building his own plugin architecture, why would he be a major sadist and do it the hard way? I think you're arguing for the sake of arguing.

Now that's uncalled for.  It's just a little bit of trivial recursion in the traditional manner with a "visited" bit tacked on to base-case cycles.  And it allows much more flexibility in where and how the plugins can hook in to each other. 

If the OP wants to sacrifice the potential generality for plugin hooks, then the other algorithm works fine.  If not, a proper graph traversal with cycle detection is the way to go.

In answer to the question, maybe he would do it the "hard way" because he wants a general or extensible solution rather than a limited, quick one.  I think it's pretty clear that I'm taking an approach where the desired solution should be as general as possible.  Let the OP decide whether or not it fits. 

general or extensible solution rather than a limited, quick one.

Oh, oh, do tell!

for plugin hooks

Oh? And where would the recursive algorithm get its data about dependencies? Thin air? Or maybe you intend to keep a seperate list of plugin dependencies? Okay, explain to me why the iterative approach can't do that too?

It's just a little bit of trivial recursion in the traditional manner with a "visited" bit tacked on to base-case cycles.

Have you ever implemented "proper graph transversal" in an iterative style perchance? Or maybe... collapsed a tree onto a stack? Notice something odd here, hmm...?

What you propose is almost identical, except that it's recursive instead of iterative.

You are arguing just for the sake of arguing.

I'd say that iteration is "the hard way" when dealing with trees. Trees are a recursive structure after all.

Wow.  I'm sorely tempted not to reply, there's some obvious trolling and lack of thought going on there.  I'll try one last time, though.

My suggested approach is different because it's bottom-up instead of top-down.  Depth-first instead of breadth-first.  That's all there is to it.  No magic, no condescension, no statement that anyone else is wrong.  Why?  Because the only person with enough info to make that decision is the OP and I ain't him.

And yeah, >>14, I agree.  Iteration does seem to be "the hard way" when dealing with a recursive data structure.  It's unnatural.

posting to maybe fix the tables

Trees are a recursive structure after all.

Fair enough, I won't argue that. The problem itself may not be a tree, however, so recursive isn't a wonderful fit either. That's why you also need hackery with recursion to ensure you haven't visited the same node twice. I mentioned shoving a tree on a queue because recursion naturally fits best on a tree or list, so I'm showing the two approaches are similar.

Depth-first instead of breadth-first.  That's all there is to it.

The pseudocode in >>8 is depth-first. Don't believe me? Draw it out. Nor did >>12 specify what type of searching he was doing, so it's fair to assume it's also depth-first. Where'd you get the breadth-first from? Take your own advice and think.

shoving a tree on a stack

Fixed.

>>17

Still wrong.  It's breadth first:

Sample Run of >>8.  Note that A contains the list of loaded plugins in-order.

L:  W, X
M:  Y
N:  Z
W:  U, V
X:  T
Y:
Z:
U:
V:
T:

B contains [L M N]
A contains [ ]

Pop L
L !in A
Load L
A += L
B += W
B += X

B contains [M N W X]
A contains [L]

Pop M
M !in A
Load M
A += M
B += Y

B contains [N W X Y]
A contains [L M]

Pop N
N !in A
Load N
A += N
B += Z

B contains [W X Y Z]
A contains [L M N]

Pop W
W !in A
Load W
A += W
B += U
B += V

B contains [X Y Z U V]
A contains [L M N W]

Pop X
X !in A
Load X
A += X
B += T

B contains [Y Z U V T]
A contains [L M N W X]

And that's enough to show that we're talking about a typical breadth-first algorithm.  A depth-first algorithm would have a load order going all the way down the first tree first.  (And in fact, the proposed solution in >>10 / >>12 would have the loads occurring as the recursion unwinds.  A classic LRV algorithm, if you will.)  Here we see that the algorithm in >>8 walks the span of the tree prior to its descent to the next level.  Pretty much the definition of breadth-first.

>>17
Yes you're right, I shouldn't have mentioned trees since the possibility of circular dependencies immediately screams "not a tree!"

I'd still rather use recursion though since stacks are so useful in graphical algorithms, and with recursion we get one for free :)

>>21
After a bit of thought I'm inclined to agree with you. The compiler handles the stack instead, and even though >>19 clearly has no idea what he's talking about, he did get one thing right: you can initialize plugins as you return, which isn't as elegant with iteration.

>>22
BUMP!

The drum The optimizing   assembler program and   2 has little   prior exposure to   languages With combination   of these two   attributes I really   liked about PHP   was that I   could borrow plz.

<