7

I've got an object with a complex hierarchy, something like:

Document
  Paragraphs
    Paragraph
      Words
        Word

and I need to implement a dirty flag on the Document object. In general, there can be a huge number of Paragraphs and Words, and paragraphs and words have many properties that can be changed. So I'm having trouble figuring out where to capture state change so I know when the document is dirty. I could:

  • Give every single Paragraph a reference back to the Document object, and give every single Word a reference to its containing Paragraph, and then in every property change, walk up the hierarchy and tell the document that it's dirty. But that's a lot of references and hooks on property changes.
  • Find any place in the application that changes any paragraph or word property, and have that code also tell the document that it's dirty. But then it would be hard to know that I had found all such places, and I'd have to make sure that any future document changes also made sure to do this, which seems hard to maintain.
  • Record the initial state and then test the current state against the initial state. But since the number of objects is very large and the hierarchy is somewhat deep and complex, that seems like it would be slow and memory intensive.

Is there a better design pattern for this situation?

13
  • Events or two-way object references are my initial thoughts. Each object triggers an event that it has changed. All objects within the hierarchy subscribe to these events. Or marking a child dirty marks the parent dirty. Or "dirty" is a calculated value based on whether or not I am dirty or any of my descendants are dirty. – Greg Burghardt Apr 19 at 17:01
  • 1
    Why not have a reference from a word to its containing document directly, if all you need it for is for that dirty flag? – Helena Apr 19 at 17:41
  • @GregBurghardt: The uncomfortable thing about the first idea is having the document have to subscribe to events on thousands of its descendants, or that all of those descendants need a link back to the parent document. That's just a lot of references to maintain (and possibly a lot of memory used). – Joshua Frank Apr 19 at 18:13
  • 1
    Your use case is pretty unclear, also the context. For example, when your document is loaded in a word processor, it is pretty trivial to switch a boolean flag to "true" at the document level for any kind of change applied, without ever going through the object hierarchy. In fact, how the document is structured internally is quite unimportant for this. Is that your situation? – Doc Brown Apr 19 at 18:40
  • 1
    @JoshuaFrank: this depends heavily on the architecture of the word processor as a whole, not just the document structure. For example, when all modifying actions are implemented as command objects (because you decided to provide "undo" functionality that way), the commands would be a possible "point of attack" for the "dirty" functionality. Using the document hierarchy, of course, is also a possible option. But don't see why you think propagating a dirty flag from the leafs of the tree to the root is such a problem - your tree seems to be only five levels deep, that's not many. – Doc Brown Apr 19 at 20:05
5

I recommend that you implement the most straightforward approach to this and then look into fancier options only if that doesn't suffice. The simplest answer, IMO, to this problem is the last one in Greg Burghardt's comment: make each object in your hierarchy aware of whether it's data has been changed. Also add an isDirty() method to every object. It returns true if its own data has changed or any of its children's isDirty() method returns true.

This is simple because you don't need make any object aware of any object it isn't already aware of and all the logic is done within the constituent objects. You might be tempted to just update the document because that's all the requirement asks for but that's actually more work for less value. By doing it this way you get the ability to know what has changed at every level 'for free' while implementing the main requirement.

Events are also potentially useful here and if you use an observer to manage the isDirty state of each object, this should be simple to add as well.

3
  • @DocBrown And as I explain in my answer, trying to avoid this is harder. Feel free to challenge that but I already addressed your comment in the answer. – JimmyJames Apr 19 at 21:03
  • @DocBrown I'd say doing more work to achieve less because YAGNI is one of the most insidious ideas in software development. I've never been in a situation where someone really wanted me to bust ass in order to create an inferior solution but perhaps you are seeing this from an angle that I am not. I've had to solve this kind of problem in the past and always ended up back here. It's the simplest approach with the lowest risk and sets you up for more sophisticated implementations. – JimmyJames Apr 19 at 21:30
  • @DocBrown I'm cool, totally cool. While I feel pretty confident about this, I know that I don't know everything. I also left out some details about how this gets done. – JimmyJames Apr 19 at 21:43
3

Here's what I'd probably do ... "Am I(!) Dirty?"

Easy Way: The innermost section of your code which "first smells the stink" immediately informs its parent, which immediately informs its parent if it has one.

Hard Way: The parent, whenever asked, has to (recursively) ask each of its children, "ewwww, are you dirty?" Stopping, of course, with the very first "yes," and maybe setting a flag within itself so that it doesn't actually need to poll its children next time.

Both approaches are valid, depending on the circumstances.

1
  • 2
    I don't understand why you call the first option 'the easy way'. It requires adding a reference to the parent to every object that can be put below the root and and setting it whenever a node is added or moved. i.e making the tree doubly-linked which creates a significant risk of introducing bugs. What you call the 'hard way' requires no changes to the data structure. What in your mind makes this the 'hard way'? – JimmyJames Apr 20 at 14:34
3

In the question, you did not state the use case and context clearly, but in the comments you mentioned a few parts of it: it seems you are going to implement a word processor. Let me assume you are not loading documents with several millions of words at once, then I think your requirements will look something like this:

  • the object tree is loaded completely into main memory of your application

  • changes causing the "isDirty" state of the document to become true occur frequently during "editing" of a document

  • resetting the "isDirty" flag happens when the document is "saved" (persisted) somewhere.

For this kind of profile, I guess I would combine the ideas of Greg Burkhardt and Jimmy James, giving each node in the tree an isDirty flag as well as a reference to its parent, so in case a node is changed from isDirty==falseto isDirty==true, it can propagate this information to its parent. For each individual change to the document tree, this will require "# of tree levels" propagation steps at maximum (so at most 4 steps in the scetched hierarchy). But since the propagation can stop immediately when it finds a parent which is already "dirty", the amortized performance will be even better. The only step which will become slower is the resetting of the "dirty" state to false, since all nodes in the document wil have to be touched. I guess this does not happen frequently and only during a "persist" operation, so the resetting will be negligible.

And yes, this will require some additional space for the references, but I would be really astonished if this is really a problem (except you are trying to run your program on a small embedded device which is short of memory). For a medium word length of 5 to 6 letters in english language (maybe more in different languages), and 16 bits per character (maybe more if you store color, formatting or font information), plus the overhead for any object in your runtime environment, one additional 64 bit reference plus a boolean flag will require typically less space than the word object itself, so giving you a factor of less than 2 in memory overhead. This should be usually acceptable for most real world cases.

3
  • This works and if you were really concerned about the performance of this check, I would probably do something similar. It seems like a bit of a premature optimization, though. How many thousands (millions?) of nodes would there need to be before the worst case was significant enough to matter? I'd guess there would need to be a lot of nodes. – JimmyJames Apr 20 at 14:51
  • @JimmyJames: with no parent references, a call to "isDirty()" will cause a cascade of calls through the whole document, as long as the tree is not "dirty". The next call again, and again, and again (unless the document becomes dirty, so the cascade can be stopped). With several thousands of words in a document, this might matter (but we actually don't know, since the OP stayed pretty vague about the typical document size and the usage of the "isDirty()" method). – Doc Brown Apr 20 at 21:14
  • 1
    "with no parent references, a call to 'isDirty()' will cause a cascade of calls through the whole document, as long as the tree is not 'dirty'" Good point: the worst case is quite expected; seems obvious now that you point it out. The OP's solution has the same profile and is "incredibly fast". I think checking markers would be faster than calculating all the hashes. In any event, I have great respect for your insights and regret if I've made you think otherwise. – JimmyJames Apr 20 at 21:41
1

Give every single Paragraph a reference back to the Document object, and give every single Word a reference to its containing Paragraph, and then in every property change, walk up the hierarchy and tell the document that it's dirty. But that's a lot of references and hooks on property changes.

If "walking up the hierarchy" is accessing already referenced objects (i.e. not having to dynamically search for them at the time), then the effort of doing so is negligible.

It may be a lot of hooks, but it's the total CPU cost that matters, not the amount of hooks. If you're dealing with a human adjusting text, the computer (and thus your hooks) are many, many orders of magnitude faster than your user will be.

Just don't lift any real weight with it. Don't start writing to log files or such. Keep it light, and you'll probably never even notice that the hooks are being fired anyway.

0

People have provided very helpful ideas, but I found a nice solution that I think is substantially different from them, so I'm going to post this as my own answer.

The main thing I was trying to avoid was having perhaps a dozen classes like this:

public class Word
{
        public string Value { get; set; }
        public float Property1 { get; set; }
        public float Property2 { get; set; }
}

each with a number of properties as shown, each of which would have to be changed from a simple get/set property to one that had the plumbing to know about its containing document and notify it whenever any of them changes.

Plus, there are collection classes for each (e.g. the corresponding Words class), each of which would have to track at least additions and deletions and also notifying of the document. It's not that this would be especially memory or CPU intensive, just that it would be a TON of fiddly, boilerplate code to write and maintain. Maybe this could be handled with code generation, but it was seeming pretty messy to implement.

Since I really only care about a single, boolean answer to the question of "Is the document dirty?", I implemented the following:

public int CalcChecksum(Document d)
{
  var hashCurrent = 0;

  hashCurrent = HashCode.Combine(hashCurrent, d.Property1);
  hashCurrent = HashCode.Combine(hashCurrent, d.Property2);
  ...

  foreach (var p in d.Paragraphs)
  {
    hashCurrent = HashCode.Combine(hashCurrent, p.Property1);
    hashCurrent = HashCode.Combine(hashCurrent, p.Property2);
    hashCurrent = HashCode.Combine(hashCurrent, p.Property3);

    foreach (var w in p.Words)
    {
        hashCurrent = HashCode.Combine(hashCurrent, w.Value);
        hashCurrent = HashCode.Combine(hashCurrent, w.Property1);
        hashCurrent = HashCode.Combine(hashCurrent, w.Property2);
        hashCurrent = HashCode.Combine(hashCurrent, w.Property3);
        ...
    }


    return hashCurrent;
}

In English, what this does is to walk down the document hierarchy, building a hash code that combines the significant fields from each descendant object. That aggregated hash code will change iff and only if any field changes. So I can cache a single int field and call the function again and just compare the two checksums to determine dirtiness.

This function is also incredibly fast, taking less than 1ms in my testing on moderately sized documents.

The one drawback is the annoyance of having to type out all the properties. If that gets too annoying, I would implement some kind of pre-process using reflection to generate the property lists at run time, generate property getters, and use those instead. But so far, this isn't too bad.

7
  • What language is this? If you are going this route, why not just implement the property hashing in each component? Then you don't need to modify this whenever you add a new component or modify properties. – JimmyJames Apr 20 at 16:15
  • c#. I may do that, but for now it's nice to keep all of this logic in one place. If I start needing it to be more granular, or maintainable, I'll do that. – Joshua Frank Apr 20 at 16:39
  • You say you are keeping it in 'one place' but you are actually tightly coupling this function to the structure or a number of other classes so it's really not: it's two places. – JimmyJames Apr 20 at 16:51
  • I understand that. I guess what I mean is that I'm interested in dirty tracking in one place, and all of that stuff is in one place, and dirtiness is not a property of any one object or property, but all of them hashed together. So distributing the hashing to every object doesn't seem so useful here. – Joshua Frank Apr 20 at 17:00
  • If you go that route, you should be a big comment in bold letters on every class that is hashed this way that you need to update this function any time the properties are modified. I don't know what the solution is for new components. That's kind of what interfaces are for but if you don't want to use language features as intended, you'll have to work out a different solution. – JimmyJames Apr 20 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.