Re: Pattern for "make"-like dependencies between objects
alan wrote:
On Nov 24, 11:15 pm, Phil Endecott
<spam_from_usenet_0...@chezphil.org> wrote:
Dear Experts,
Say I have an application with various data inputs (files, network
connections, peripherals etc), various data outputs (files, display
etc.) and various intermediate internal data objects. I would like
changes in the inputs to propogate through to the outputs. In my mind,
I'm imagining the dependencies between the objects like "make" dependencies.
There are various ways of doing this, including "push" and "pull"
methods, with various pros and cons. Is anyone aware of any literature
("patterns") describing something like this?
One thought that has occured to me is that C++ has built-in compile-time
dependency graph logic in the multiple inheritance constructors. So,
say I have these objects:
DataSource src;
InternalObj obj1;
InternalObj obj2;
Display disp;
If obj1 and obj2 get their data from the DataSrc, and the Display gets
its data from obj1 and obj2 (i.e. a diamond-shape dependency graph), and
each object has an "update" method, then I can write:
struct make_src {
make_src() { src.update(); }
};
struct make_obj1: make_src {
make_obj1() { obj1.update(); }
};
struct make_obj2: make_src {
make_obj2() { obj2.update(); }
};
struct make_disp: virtual make_obj1, virtual make_obj2 {
make_disp { disp.update(); }
};
Now, when I want to update the display I can just create a temporary
make_disp object, and all of the update() methods will be called in the
right order. (I think. I'm a bit rusty on what the virtual base
classes do. I hope that src.update() gets called only once.)
I bet I'm not the first one to think of this, but google doesn't find
anything - perhaps because of the zillions of hits for extracting
#include dependencies for make from C++ source.
Any thoughts? What else is needed to make this useful? For example,
what's the best way to tag objects with the equivalent of make's timestamps?
Use a cache with a "dirty" bit to indicate that the cache's contents
are no longer valid. Each object's update() method then checks if the
cache is clean, and if so returns the data in the cache. Otherwise it
calls the data sources' update() functions and performs the
computation for that node, then stores the result in the cache and
cleans the cache.
I don't think that single bits are sufficient in general, e.g. if B
depends on A and C also depends on A, and A changes, and I ask to
re-make B but not C, what happens? I need to record that C is
out-of-date wrt A but B is up-to-date wrt A.
Single timestamps (like make) also don't work in the case where C is
generated from B and B is generated from A, but some changes to A don't
influence B (e.g. B is a sub-set of A). In this case, when I re-make C,
I first re-make B from A; but if B doesn't change I then don't need to
update C. So I need to record that B is update-to-date with the latest
version of A, but has not changed since some previous time. Can this be
solved with just a pair of timestamps, one for "last changed" and one
for "last updated"?
(By timestamp, I really mean some sort of generation number.)
The sourcemost data nodes, of course, will probably have to overload
the operator= or whatever equivalent to dirty itself.
Right, there's a whole issue there about modifying an object to know
when it changes. I've worried about this for implementing copy-on-write
semantics. Most objects have more than just operator= that change them.
Each data node
would then have a dirty() method which not only dirties the cache but
also invokes dirty() for each data sink connected to it (as an
optimization, of course, the if the data node sees it is itself dirty,
then it doesn't have to propagate the call to each data sink).
However this requires pointers both from the data sink to the data
source (so that the sink knows who to query) and a corresponding
pointer from the source to the sink (so that if the source becomes
dirty, it will also dirty each sink).
One interesting feature of the structs that I describe above is that
they're non-intrusive of the objects whose updates they control, which
seems like a nice feature. It's also entirely compile-time.
I'd love to hear some feedback about that idea, by the way.
Phil.