Invalidation Manager

Introduction

Invalidation is a pattern employed to solve problems where updating a model’s data may happen multiple times per frame, but updating the view’s rendering should happen only once. When dependencies exist between multiple models this can get complicated and potentially messy. This article looks at a solution to this mess by unifying invalidation logic into a single manager class.

The purpose of this discussion is not to offer a new class for people to take and use in their libraries so much, though you are welcome, if you should want to. Rather it is to discus a problem and my solution. Hopefully some people will learn something from reading it, and hopefully I will learn something by getting feedback about it!

The Invalidation Pattern

Consider the following simple implementation for drawing a coloured circle:

public class Circle extends Sprite
{

	private var _color:uint;
	private var _radius:Number;

	public function get color():Number { return _color; }
	public function set color(value:Number):void
	{
		_color = value;
		resolve();
	}

	public function get radius():Number { return _radius; }
	public function set radius(value:Number):void
	{
		_radius = value;
		resolve();
	}

	private function resolve():void
	{
		graphics.clear();
		graphics.beginFill(_color);
		graphics.drawCircle(0, 0, _radius);
		graphics.endFill();
	}

}

The problem here is that if in one frame I changed both the radius and the color, the resolve() function would be called twice. Though not a problem in this case, it could be if the resolve() function involved a lot of complex logic.

The invalidation pattern resolves it this way:

public class Circle extends Sprite
{

	private var _color:uint;
	private var _radius:Number;

	public function get color():Number { return _color; }
	public function set color(value:Number):void
	{
		_color = value;
		invalidate();
	}

	public function get radius():Number { return _radius; }
	public function set radius(value:Number):void
	{
		_radius = value;
		invalidate();
	}

	public function invalidate():void
	{
		... at some future point of my choosing, trigger resolve() ...
	}

	public function resolve():void
	{
		graphics.clear();
		graphics.beginFill(_color);
		graphics.drawCircle(0, 0, _radius);
		graphics.endFill();
	}

}

Often in AS3, the invalidate() function looks like this:

public function invalidate():void
{
	addEventListener(Event.ENTER_FRAME, onEnterFrame);
}

private function onEnterFrame(event:Event):void
{
	removeEventListener(Event.ENTER_FRAME, onEnterFrame);
	resolve();
}

It is a good pattern that solves the problem of multiple resolve() calls. The actual mechanism contained inside invalidate() which causes resolve() to be called once at a convenient point is unimportant. For this sort of structure, this simple implementation does the job.

Where The Invalidation Pattern Becomes Complicated

Imagine that you have two classes: a line, and a circle, the intersection of which defines two circular segments. In fact, don’t imagine: look at this:

Both the line and circle implementations consist of two points which, on moving, invalidate the their equations. On resolve() the equations are resolved. The segments depend upon the the line and circle; when the line or circle is invalidated, they should be invalidated also.

A mechanism for the segments to know when their definiens (that which defines them) are resolved is required, suggesting that each element conforms to a common interface:

public interface Invalidates
{

	function invalidate():void;

	function get invalidated():Signal;

	function resolve():void;

}

and an implementation along these lines:

public class Line implements Invalidates
{

	private var _ax:Number;
	private var _ay:Number;
	private var _bx:Number;
	private var _by:Number;

	private var _invalidated:Signal;

	public function Line()
	{
		_invalidated = new Signal(Invalidates);
	}

	public function get ax():Number { return _ax; }
	public function set ax(value:Number):void
	{
		_ax = value;
		invalidate();
	}

	... missing a few uninteresting methods ...

	public function invalidate():void
	{
		_invalidated.dispatch(this);
	}

	public function resolve():void
	{
		... resolve the line ...
	}

}

public class Segment implements Invalidates
{
	private var _line:Line;
	private var _circle:Circle;

	... missing the constructor ...

	public function get line():Line { return _line; }
	public function set line(value:Line):void
	{
		_line = line;
		_line.invalidated.add(onInvalidated);
	}

	... missing a few uninteresting methods ...

	private function onInvalidated(definien:Invalidates):void
	{
		invalidate();
	}

	public function resolve():void
	{
		_line.resolve();
		_circle.resolve();

		... the rest of the resolution ...
	}
}

The problem here is the same problem that led us to consider the Invalidation Pattern in the first place: namely, that the Line’s resolve() method is going to get called a lot. Sure, we can pack the methods with lots if calls like:

private function invalidate():void
{
	if (_isInvalidated)
		return;

	_isInvalidated = true;
	invalidate();
}

public function resolve():void
{
	if (!_isInvalidated)
		return;

	_isInvaldiated = false;
	_line.resolve();
	_circle.resolve();

	... the rest of the resolution ...
}

However, it starts to feel like the classes are consumed with handling the invalidation management, rather than with what should be their single responsibility of properly modelling the geometrical entities for which they are named.

An important feature of this implemenation is that it guarantees that the Line’s and Circle’s resolve() methods are called before the sgement resolves. If B depends on A, then A must resolve before B resolves. This is a key feature of the Invalidation Manager, below.

Managing Invalidation

The current as3geometry library attempts to solve the problem of invalidation using the InvalidationManager.as class.

The Invalidation Manager handles classes that satisfy the Invalidates.as interface. Invalidates objects can be registered to the InvalidationManager, and dependencies can be established. As this happens, objects are categorized into tiers.

Initially, since every object is independent of each other when registered, newly registered elements are considered in tier 0. However, if a dependency is established such that B depends on A, B is put into the tier above A, so if A is in tier 0, B is in tier 1. If then C depends on B, since B is already in tier 1, C goes into tier 2.

The utility of the tiers comes from the fact that all objects in tier 0 are independent of each other and may be resolved in any order. Tiers are resolve in ascending order, ensuring that any object that is depended upon is resolved before any object which depends on it.

The problem with this approach comes when, for example, A depends on B depends on C already so they have the following tiers:

Then, if I have another object D already in tier 3, and define that B depends on D, I must move B to tier 4 and therefore also move C to tier 5.

Circularity presents an interesting problem within this system. If A depends on B depends on C, and then I define that C depends on A, the tier system breaks down. Currently attempting to create a circular reference will fail and an error will be thrown.

In order to keep the InvalidationManager clean, it does not actually handle when it resolves, but instead dispatches a signal when it has elements that require resolution. In the as3geometry implementation the AS3GeometryContext.as wraps the InvalidationManager and hooks it to the player events to so that when invalidation occurs it is resolved in good time.

The Invalidates classes, other than telling the contxt what it has a relationship to and what it does not, no longer contains any code that tries to manage other objects’ invalidations:

public class Line implements Invalidates
{

	private var _ax:Number;
	private var _ay:Number;
	private var _bx:Number;
	private var _by:Number;

	private var _context:InvalidationManagerContext;
	private var _invalidated:Signal;

	public function Line(context:InvalidationManagerContext)
	{
		_invalidated = new Signal(Invalidates);

		// elements that don't depend on other classes  like this don't really need the
		// context stored, but I store it here for consistency, and in case the structure
		// changes
		_context = context;
		context.register(this);
	}

	public function get ax():Number { return _ax; }
	public function set ax(value:Number):void
	{
		_ax = value;
		invalidate();
	}

	... missing a few uninteresting methods ...

	public function invalidate():void
	{
		_invalidated.dispatch(this);
	}

	public function resolve():void
	{
		... resolve the line ...
	}

}

public class Segment implements Invalidates
{
	private var _line:Line;
	private var _circle:Circle;

	private var _context:InvalidationManagerContext;
	private var _invalidated:Signal;

	public function Segment(context:InvalidationManagerContext)
	{
		_invalidated = new Signal(Invalidates);

		_context = context;
		_context.register(this);
	}

	public function get line():Line { return _line; }
	public function set line(value:Line):void
	{
		_line = line;
		_context.addDependency(_line, this);
	}

	... missing a few uninteresting methods ...

	private function onInvalidated(definien:Invalidates):void
	{
		invalidate();
	}

	public function resolve():void
	{
		... just resolve here! this is the big win ...
	}
}

Conclusion

A benefit to this approach is that Invalidates classes need very little boiler-plate code. The author of an Invalidates class need know only that changes should call invalidate() and that all resolution logic happens in resolve(). Responsibilities are extremely well separated.

The as3geometry implementation wraps the InvalidationManager into an AS3GeometryContext.as class that has a little more logic than the InvalidationManager, which does not have a mechanism for actually triggering the mass resolution. While the InvalidationManager handles the internal logic set-out above, the AS3GeometryContext handles hooking up the InvalidationManager to the player events.

There is a downside, of course. Currently in as3geometry, the constructor of every class contains a reference to the AS3GeometryContext, and every class stores a reference to it. It is not clear to me that this approach is avoidable, unless the manager is defined as a singleton. There are lots of good reasons why singletons are bad, not least because I might have good reason to have two parallel geometric contexts in one application.