Fine Print in Contracts - Contracts - How to Use Objects: Code and Concepts (2016)

How to Use Objects: Code and Concepts (2016)

Part II: Contracts

Chapter 6. Fine Print in Contracts

Contracts form a solid framework for arguing about the correctness ofImage 4 code: Class invariants capture the consistency of the objects’ internal structures, while the pre- and post-conditions of methods describe the objects’ behavior to clients without requiring knowledge of the objects’ internals. Within methods, the workings of the code can be traced in detail, down toImage 4.2.3 formalizing the effects of individual statements.Image 4.7

The presentation so far has established the terminology and common reasoning patterns. However, a number of practically relevant questions have not yet been answered: The discussion was restricted to single objects with no internal helpers, and the interaction with the language constructs of exceptions and inheritance has not been been treated. The purpose of this chapter is to cover further material that is necessary in nearly all practical situations.

Unlike the previous chapter on contracts, this one will not lead up to a formalized treatment, simply because the formulas involved would become too complex to be handled usefully on paper. Instead, we will give miniature examples to establish the concepts, and then revert to the mode of discussing real-world code from Part I.

6.1 Design-by-Contract

Contracts capture the behavior of objects and in this way make precise the API commonly found in documentation. Just as the API is subject to design decisions, so writing down contracts involves decisions and planning. The general guideline for APIs is to start from the clients’ perspective, andImage 1.1 correspondingly the pre-condition availability principle and the reasonableImage 4.2.2 pre-condition principle ensure that clients can understand contracts from an outside point of view. As we shall see now, the precision of contracts also enables detailed considerations about what the “best” API for a given object might be. We will actually approach design-by-contract.Image 182

6.1.1 Contracts First

The central point we will follow up on in this section is this:


Design contracts before writing the methods.


The more detailed presentation of contracts in Sections 4.2 and 4.7 has motivated the need for contracts primarily from the methods’ code that relies on the invariants and pre-conditions for doing its work. While this is a useful device for pedagogical purposes, it is rarely an advisable procedure for introducing contracts in practice: You can easily end up with contracts that reflect a particular implementation, rather than the purpose of a method, and the contract does not help you to understand the demands on the method.

Image 5.2Compare this situation with the advice of test-driven development. There, the main point is to gain a detailed understanding of what a method or class will need to achieve before attempting to actually implement it. Contracts can serve as conceptual test cases: A method’s pre-condition implicitly encompasses all possible tests, since it describes all possible situations in which the method can be called legally. Likewise, the postcondition encompasses all possible assert tests that can be expected to be passed on the method’s result—all tests must be implied by the postcondition.


Use contracts to capture the purpose of methods.


The contracts we gave in Chapter 4 do, in fact, conform to the intuition ofImage 4.1 the methods’ purpose. For instance, the replace method in GapTextStore requires that the replaced text range is contained entirely in the currentImage 4.2 content according to the pre-condition (4.2). Likewise, the next method in ThresholdArrayIterator requires that the sequence is not yet exhausted,Image 4.2.2 which we have specified alternatively by model fields in (4.8) and in the formImage 4.2.5 of the pure method hasNext in (4.13).

6.1.2 Weaker and Stronger Assertions

When designing an API, one often has to strike a balance between the interests of the clients and those of the implementors: Clients want classes that are simple to use and that can be reused flexibly in many situations, while the implementors would rather want to concentrate on a few well-defined, simple tasks that work in restricted scenarios. As an example, suppose you need an analyzer for HTML documents. Clients would like to throw any document they download from the Internet at that analyzer, while the implementors’ lives would be simplified considerably if only valid XML documents needed processing—writing a robust HTML parser is just so much harder than using the SAX parser from the library. In the other direction, a method that generates text for inclusion in an HTML document is easier to use for the client if it already escapes the special characters, while it is easier to implement if escaping is left to the client as a second processing step. Such trade-offs between the responsibilities of the method and those of its callers are the everyday questions confronted by every software designer.

At the core, such decisions boil down to the question of how much is expected at specific points: How much must a client guarantee to be able to call a method and how much must a method guarantee when it finishes? An assertion is called weaker if it requires less; it is called stronger if it requires more than another assertion. We continue by exploring some salient aspects of these terms to illustrate them further.


Clients prefer weaker pre-conditions and stronger post-conditions.


Clients like it if they have to do less work before calling a method and if the method does more for them. The requirement of passing a well-formed XML document is stronger than that of passing a “reasonably well-formed HTML document displayable in a browser.” The requirement of generating text with escaped special characters is stronger than just leaving the original characters in place.


Implementors prefer stronger pre-conditions and weaker post-conditions.


Implementors, in contrast, prefer calls that occur in very specific situations, where they know more about the parameters and the object’s state. Of course, they would also like to do as little work as possible before returning.


Weaker and stronger have precise logical meanings.


The short-hand terms “weaker” and “stronger” can also be defined precisely: An assertion P is stronger than assertion P′ if in all possible program states P logically implies P′. The qualification “in all possible states” refers, of course, to the values of the variables and heap locations referenced within P and P′. Conversely, an assertion P is weaker than an assertion P ′ if in all possible program states P ′ implies P. Two assertions P and P ′ are equivalent if P is both stronger and weaker than P ′ (which is, of course, the same as saying that P ′ is both stronger and weaker than P).


Image Unfortunately, the standard terminology is somewhat odd at this point: “Stronger than” and “weaker than” seem to signify strict relations, while the preceding definition would read the (trivial) implication PP as “P is stronger than P.” From a linguistic point of view, you would expect “at least as strong as” and “at least as weak as.” We prefer here to stick to the introduced terminology.


To illustrate, let us consider a few examples. Obviously, i > 0 implies i ≠ 0, so i > 0 is stronger than i ≠ 0. The assertion “p is a PDF 1.3 document” is stronger than “p is a PDF 1.4 document,” because the PDF format is backward compatible, so that a 1.3 document is also a legal 1.4 document. The assertion “t is a text and the HTML special characters are escaped” is stronger than just “t is a text.”


Methods remain correct with a stronger pre-condition and weaker postcondition.


Suppose we have a method with pre-condition P and post-condition Q and that we have proven that the method is correct. Assuming that the pre-condition holds initially, the code guarantees that the post-condition will hold in the end. Intuitively, the method is entered through P and left through Q, as shown in Fig. 6.1.

Image

Figure 6.1 Weakening of Method Contracts

We now replace P with a stronger pre-condition P′ and Q with a weaker post-condition Q′. Intuitively, we “wrap” the method in a new contract and inform callers only about that contract. Then the method is still correct: Initially, P′ holds, from which we deduce that P holds; since the method was originally correct, we know that Q holds after its execution, from which weImage 6.4 deduce that Q′ also holds. This fundamental reasoning pattern of replacing assertions by variants will reappear when we study the connection between contracts and inheritances later on.

6.1.3 Tolerant and Demanding Style

One of the central questions in designing contracts is this: What does the method expect from its callers? Which requirements does it specify in its pre-condition? As we shall see now, the remaining decisions about the contract largely hinge on this initial choice. We will now introduce the relevantImage 4.2 concepts using the ThresholdArrayIterator and will give illustrative examples of the main conclusion in Section 6.1.4.

For motivation, let us go back to the ThresholdArrayIterator’s method next (see Fig. 4.7 on page 202 for the full code). The original pre-condition (4.8) states that the sequence must not be empty, which is expressed as

pos ≠ seq.length

This condition can, however, be checked only by calling the method has Next(). Suppose clients find this checking too cumbersome. They would like to just call next() in any situation and can live with getting nullImage 4.2.2 when there are no more elements. Their version of an idiomatic loop for accessing all elements looks like this:

thresholditer_tolerant.ThresholdIteratorTest.dump


while ((data = iter.next()) != null) {
// work with data
...
}


Of course, such a variant of next() can be provided easily, by testing whether an element exists right at the start (lines 2–4 in the next code snippet). The original code in lines 5–8 then runs through because the if rule (4.21) guarantees its pre-condition i ≠ a.length in the elseImage4.7.3 branch.

thresholditer_tolerant.ThresholdArrayIterator.next


1 public Integer next() {
2 if (i == a.length) {
3 return null;
4 } else {
5 Integer tmp = a[i];
6 i++;
7 findNext();
8 return tmp;
9 }
10 }


The new pre-condition of this method is true—that is, the method can be called in any situation.


Tolerant methods have weaker pre-conditions.


We said earlier that clients prefer methods that have weaker pre-conditions,Image 6.1.2 because it is easier to call them. In the previous example, clients can still check hasNext() before calling next(), but they do not have to. The precondition true is certainly weaker than the original one.Image6.1.2

Meyer proposes the term tolerant for such methods: They allow more inputs,Image 181 they can cope with more situations, and they are more lenient toward the callers’ possible shortcomings. Choosing the contracts of methods to be tolerant—in other words, aiming at weak pre-conditions—is then called the tolerant style.


Tolerance is a variant of robustness.


A method is robust if it fails gracefully in case its pre-condition is violated. This is especially important on the system boundary, where users, otherImage 4.6 systems, or hardware devices must be expected to misbehave. A tolerant method can be understood to be robust in a special sense: It deliberately requires less than it would do naturally, so as to allow clients some leeway to misbehave. The graceful failure for these cases is incorporated into the contract and comes with special guarantees about the result. In the exampleImage 6.3 of a tolerant next(), the post-condition would be:

Returns the next element in the sequence, or null if the sequence is exhausted.

In other words, if the client checks before the call in the usual way, it will receive an element. If it fails to check and the sequence is empty, the return value will be null.


Tolerance usually leads to weaker guarantees on the result.


There is a downside to choosing a tolerant contract: Because the method has to do something sensible even in border cases, it cannot guarantee to achieve its main purpose in all circumstances allowed by the pre-condition. In the preceding example, returning null, rather than a real result, is a workaround: Because there is no further element and yet something hasImage 1.8.9 to be returned, the method chooses null as the “non-object.” The client gets fewer assurances about the result, so the post-condition is weaker. A further implication in this example is that null cannot occur as an element in the sequence, because clients would not be able to distinguish this case from the end of the sequence.

These examples show that tolerance induces uncertainty about a method’s result. The client has to be aware of the different possible outcomes and must arrange a case distinction accordingly. The overall conclusion is this: A tolerant method is easier to call, but its result is harder to work with.


The tolerant style globally leads to more complex code.


The central insight by Meyer at this point is that, from a global perspective, tolerant methods are not desirable. The method code itself will contain more checks and special cases, and the caller’s code will have to check the result for the various possible outcomes. In both places, the consequence of tolerance is more code that must be developed and maintained. The negative effect is multiplied by the fact that a method usually has several callers.

Not only the code itself, but also the reasoning about method calls becomes more complex. Suppose that, in the previous example, the client does check hasNext() before calling next(). Then it must deduce that the border case of an empty sequence does not apply and that therefore the result will not be null and can consequently be used as a proper object.


Prefer the demanding style.


Image 181Meyer introduces the term demanding as a contrast to tolerant. A method’s contract is written in demanding style if the pre-condition requires everything that the method needs to be implemented straightforwardly and efficiently. The method is not a mere servant who tries to deal with every possible input that callers throw at it—the method, too, has clear preferences and a well defined scope for its contribution, and states these in its pre-condition.

The original specification of method next() is written in demandingImage 4.2.2 style. It is not sensible to require an iterator to produce a next element if the sequence is finished, so the next method states the non-emptiness as a requirement.

Demanding-style contracts achieve a fair distribution of work between caller and method: The caller provides the method with the essentials it needs, but no less. The method, in return, finishes its work quickly and reliably.


Demanding-style contracts start from the method’s purpose.


The question is, of course, how “demanding” a method can or should get: If it requires too much, all callers, possibly in many different places, will have to perform extra work. If it requires too little, the negative results of tolerance start to emerge.

The solution has already been given in the earlier guideline of derivingImage 6.1.1 a method’s contract from its purpose: If the method is to fulfill a particular purpose, it can clearly ask its clients to provide everything that is necessary toward achieving that goal. This strategy is also in line with the reasonableImage 4.2.2 pre-condition principle, since the clients will understand the justification for the particular demands. It also aligns with the practical goal of designing a method from the clients’ perspective, since the method’s purpose usuallyImage 1.1 answers a specific need of its clients.Image1.4.3


Be demanding and do not check the demands.


A method is designed to be demanding because it requires a certain setup to start working. Only when given that setup can the method get down to its task. The next method’s task, for instance, is to return the current element and to advance the iterator. This is implemented in 4 lines of code (lines 5–8 on page 289). Since the method does state its demands, it should not waste effort in checking that the demands are satisfied afterward; otherwise, it could just as well not have stated them at all. This conclusion is, of course, the same as the non-redundancy principle, which says that methods shouldImage 4.5 in general not check their pre-conditions.

6.1.4 Practical Examples of Demanding Style

Formulating demanding-style contracts is not always a simple matter, because it involves capturing the method’s purpose in succinct assertions orImage 6.1.3 even formulas. As usual with such rather abstract recipies and strategies, it is best to look at a few good examples.

In general, you will find that all methods that “look right” and are “simple to use” conform to the rule. Reading their API with the particular question in mind will clarify matters immediately.

• StringBuilder.append(str,off,len) requires that off ≥ 0 ∧ len ≥ 0 ∧ off + len > str.length. This statement is explicit in the specification of the thrown IndexOutOfBoundsException.

• ZipFile.getEntry(name) requires that the ZIP file is open (i.e., that it has not yet been closed).

• Matcher.getGroup(group) can be applied only to groups that actually exist in the regular expression for which the matcher has been created.

• URI(str) constructs a URI from its given string representation, as specified in RFC 2396 (Uniform Resource Identifiers: Generic Syntax). The string must not be null.

• ServerSocket(port) requires that port is in the allowed range of a 2-byte unsigned value (0–65535).

In all of these examples, the stated restrictions are obviously sensible from what the method seeks to achieve on behalf of its caller.


You can deviate from the demanding style for good reasons.


Of course, software engineering is not an entirely rigorous discipline. As we have seen in many places in Part I, it is often necessary to take guidelines and rules with a grain of salt to improve the resulting code. In just the same way, there are good reasons for not taking the demanding style as a literal law in all situations.

The best reason for being a bit less demanding is the intended usage of a method. For instance, in ZipFile the method getEntry(name) “returns the ZIP file entry for the specified name, or null if not found.” It is therefore a bit tolerant, because it does not require the client to check beforehand—using the collection obtainable by entries(), for example—whether the entry exists at all. The decision can be justified by saying that clients may often be looking for specific entries and would take their own measures if these are not found. It also points out the disadvantage of tolerant contracts: The client has to check that the result is non-null before using it.

Image 1.5.3The decision in getEntry() also links back to the earlier discussion of whether a particular situation is an error or a normal case of program execution. A demanding contract declares anything outside the method’s purpose to be an error that results in an exception. A tolerant contract explicitly includes some of these border cases, thereby turning them into normal cases.

Similarly, established special cases can lead to tolerant contracts. Apart from its main purpose, the method covers several special inputs that lead to well defined results. For instance, the computation of the square root in Math.sqrt(a) intuitively can be applied only to non-negativedouble values. However, the relevant standard IEEE 754 for floating point computations defines special values NaN (not a number) and infinity that cover unavoidable rounding errors in numerical algorithms. Consequently, sqrt must be prepared to take these as arguments and to return something sensible—NaN or infinity, respectively. It also uses NaN as a designated return value for a negative input a.

Discerning the clients’ expectations will usually require some interpretation and application of common sense. For instance, the URI constructor mentioned earlier in general accepts strings of the following format:

[scheme:][//authority][path][?query][#fragment]

The authority here comprises the host, with optional port and user information. However, the documentation of the method states the following explicit exception (among others):

An empty authority component is permitted as long as it is followed by a non-empty path, a query component, or a fragment component. This allows the parsing of URIs such as “file:///foo/bar”, which seems to be the intent of RFC 2396 although the grammar does not permit it.

Even though these examples do show that a bit of tolerance can improve the usage of methods, let us end this section by emphasizing that disregarding the plea for a demanding style throughout the code base will lead to disastrous results: The global effects of tolerance are code bloat andImage6.1.3 complexity.

6.1.5 Stronger and Weaker Class Invariants

If contracts can be tolerant or demanding, and pre- and post-conditions can be weaker or stronger, a natural question is this: Can class invariants also be weaker or stronger? Technically, this is certainly the case, sinceImage 6.1.2 invariants are just assertions and can be implied by other assertions. The question is, however, also relevant in practice, because it links to decisions that software developers face on a daily basis.

The context of the question has been illustrated in Fig. 4.6, which we repeat here for convenience. In this figure, each public method leaves behind the invariant so that the next method call can start from a well-defined object state.

Image


Considerations about the invariant’s strength are always symmetric.


We pointed out earlier that the invariant can be seen as a contract ofImage 4.1 the class developers with themselves: The guarantees of one method are the assumptions of the next. Making that contract stronger or weaker will necessarily influence the complexity of the class.

The case of contracts between methods and their clients was asymmetric:Image 6.1.2 The clients prefer weak pre-conditions and strong post-conditions, while the methods do the reverse. In the case of invariants, the view is symmetric: In the figure, the second method can, by relying on the invariant, save just the work that the first method has put into establishing the invariant.


Invariants can be used to “stash away” work performed internally.


As an example, suppose we write a class IntSet that just maintains a set’s elements in an array. It uses linear search to check whether a value is an element in the set.

invariants.IntSet


public class IntSet {
private int elements[] = new int[0];
public void add(int x) {
if (!contains(x)) {
elements = Arrays.copyOf(elements, elements.length + 1);
elements[elements.length - 1] = x;
}
}
public boolean contains(int x) {
for (int i = 0; i != elements.length; i++) {
if (elements[i] == x)
return true;
}
return false;
}
}


We could now strengthen the invariant by keeping the elements sorted. The method add would have to perform the extra work of finding the suitable insertion point in the first line below.

invariants.IntSetSorted.add


1 int pos = Arrays.binarySearch(elements, x);
2 if (pos < 0) {
3 pos = -(pos + 1); // see API of binarySearch
4 int[] tmp = elements;
5 elements = new int[elements.length + 1];
6 System.arraycopy(tmp, 0, elements, 0, pos);
7 elements[pos] = x;
8 System.arraycopy(tmp, pos, elements, pos + 1,
9 tmp.length - pos);
10 }


That extra work is then “stashed away” in the invariant “the array elements is sorted.” The second method contains can make use of thatImage 72 extra work by answering the question about membership in logarithmic time:

invariants.IntSetSorted.contains


return Arrays.binarySearch(elements, x) >= 0;



Stronger invariants can improve performance guarantees.


The effect of the strengthened invariant of the example can then be summarized as follows: While method add continues to take linear time, with a negligible logarithmic overhead, method contains becomes much faster. Assuming that contains is called very often, the optimization would make sense. If add is called very often, however, it would be advisable to get rid of the linear-time insertion and use an amortized-constant-time variantImage 72 as done in ArrayList. That change cannot be combined with sortedness, which in the worst case still requires linear time for moving elements.

In general, the invariant is a main source for deriving performance benefits. Due to encapsulation, objects can set up and continue to evolve their internal data structures to satisfy service requests more efficiently. SinceImage 1.1 Image 1.3.1 Image 1.4.3 clients do not know about these internals, the invariant is the only place where additional required information can be placed.

Once you start looking, such optimizations by strengthening invariants can be found in many core data structures. Even the simple GapTextStoreImage 4.1 Image 1.3.1 contains an instance. The concern here is that the flat array storing the text (Fig. 4.1, Fig. 4.2) is never cleaned up: When the user inserts a huge chunk of text and then later removes it, an unnecessarily large gap remains behind that might never be filled again—a huge piece of memory just sits there unused.

To mitigate this problem, GapTextStore strengthens the invariant: The current gap is never allowed to grow beyond twice its original size, referring to the size determined when the storage array was last reallocated. To implement this, the class introduces a threshold, the current maximum allowed gap size.

org.eclipse.jface.text.GapTextStore


private int fThreshold= 0;


The additional invariant comes, of course, with extra work for its maintenance. Whenever text gets replaced, the method adjustGap moves the gap to enable the modification to be performed at the start of the gap. The method computes the new gap size (elided) and then checks whether the gap has grown too large (lines 3–4). As a first step toward maintaining the invariant, it triggers a reallocation if this is the case (lines 9–10).

org.eclipse.jface.text.GapTextStore


1 private void adjustGap(int offset, int remove, int add) {
2 ...
3 boolean reuseArray = 0 <= newGapSize &&
4 newGapSize <= fThreshold;
5 ...
6 if (reuseArray)
7 ...
8 else
9 newGapEnd = reallocate(offset,remove,oldGapSize,
10 newGapSize,newGapStart);
11 ...
12 }


The following reallocation routine first determines the new array size byImage 72 an amortized strategy for insertions, similar to the one used by ArrayList (line 5), and computes the new gap size correspondingly (line 6). As the central point toward the new invariant, it then ensures by straightforward comparisons that the gap is never larger than fMaxGapSize (elided, line 8; the parameter defaults to 4kb). Finally, the new reallocation threshold is adjusted to the current gap size (line 9).

org.eclipse.jface.text.GapTextStore


1 private int reallocate(int offset, int remove,
2 final int oldGapSize, int newGapSize,
3 final int newGapStart) {
4 int newLength = fContent.length - newGapSize;
5 int newArraySize = (int) (newLength * fSizeMultiplier);
6 newGapSize = newArraySize - newLength;
7 // keep newGapSize between fMinGapSize and fMaxGapSize
8 ...
9 fThreshold = newGapSize * 2;
10 // perform allocation and copy
11 ...
12 return newGapEnd;
13 }



Caches make for stronger invariants.


One particular case of optimization by stronger invariants is the use ofImage 1.3.6 caches. We have pointed out in the language-level discussion that caches require constant maintenance. Now, we can make that point more precise: The cache contains, by definition, information derived from the remaining data accessible to the object. It therefore has an associated invariant that is basically an equation for that information:

cacheContent = deriveInformation(originalInformation)

Whenever the originalInformation changes, the cache must be updated accordingly to validate this equation. The equation itself becomes part of the class invariant, strengthening that invariant.


Strengthening the invariant has pervasive effects on the class’s code.


The preceding example involving GapTextStore clearly shows a common phenomenon: Invariants are not maintained at single points, but by many different pieces of code that may be scattered throughout the class and still work together toward the common goal of reestablishing the invariant. This observation tallies with the abstract guideline that every single (public) method must contribute its share of work toward maintaining the invariant; necessarily, the code of each such method is concerned with the invariant.

Deciding to maintain a stronger invariant can influence the concrete code rather dramatically, since any piece of code working with the associated data structures must be reviewed and revised. Especially when changing the class invariant after the initial development, you should consider very carefully whether the gain in efficiency is worth the increase in complexity and the risk of introducing bugs.


Make the invariant just strong enough to implement all methods with ease.


We have seen many aspects and results of making a class invariant weaker or stronger. It is useful to sum up these individual points. Specifically, how strong should the class invariant be, and how much knowledge or previous work should it capture and guarantee?

A good guideline is found by starting from the case of contracts between client and caller, where the demanding style invariably leads to leanerImage 6.1.3 code. Since invariants serve as implicit pre-conditions of public methods,Image 4.1 Image 4.4 a demanding style here would suggest that we should make the invariant so strong that all public methods can be implemented straightforwardly. Making it any stronger, however, would burden all methods with extra work that no one ever exploits.

The discussion in this subsection motivates this conclusion further using the resulting concrete code: Any invariant that is introduced must be maintained throughout the class, so it is advisable to choose carefully which constraints are really necessary and which ones are just “nice to have” or “intuitively useful.”

At the same time, the conclusion underlines the earlier guideline toImage 4.2.3 document the chosen invariants carefully: If only one method relies on the invariant, all other methods have to maintain it. It is therefore not possible to introduce an invariant on an ad-hoc basis, just because it would be convenient at the current point of coding. The other team members and later maintenance developers must be made aware of the invariant, since otherwise it will be broken sooner or later somewhere in the code.

6.2 Contracts and Compound Objects

Objects never work in isolation: They employ the services of other objects,Image 1.1 or more generally collaborate with other objects, to achieve the common goal of delivering the application’s functionality. Very often, an object “has”Image 2.2.1 some parts that it uses for its own internal purposes, and the object’s services are really an abstraction over the more basic services of the parts. For instance, ArrayList uses an internal array to store the data and a JFace Document uses a GapTextStore to maintain the raw text efficiently.

In this section, we will approach the question of how to reason aboutImage 2.2.1 such compound objects. As there are many variants and degrees of the “part” relationship between objects, the analysis will have to be precise and careful, to clarify the context in which reasoning patterns apply. Also, there are no simple solutions. Fortunately, the literature on formal verificationImage 21 provides us with a solid foundation that can be translated into practical guidelines.

6.2.1 Basics

Before we investigate the more intricate relationships between a “whole” andImage 2.2 Image 1.3.1 Image 1.1 its “parts,” let us look back at the earlier practical discussions of these relationships. We will first translate them to the setting of design-by-contract.


The knowledge about existing parts is private.


An object usually employs parts in the role of an internal data structure: The current implementation happens to be set up like this, but theImage 4.2.2 implementation is, as usual, hidden from any clients of the object. ClientsImage 12.1.4 of the object must not be able to access the parts [Fig. 6.2(a)]. In particular,Image 1.3.1 Image 1.3.3 the whole object must be careful not to return internal parts from methods inadvertently.

Image

Figure 6.2 Basics of Contracts and Parts

In the context of contracts, these insights translate to the guideline that the parts do not appear in the contracts of the whole object’s methods. InImage 4.2.2 this way, clients cannot gain knowledge about the parts and cannot exploit that knowledge in their own reasoning. Of course, the whole object is stillImage 4.1 free to expose an abstract view on its parts through model fields.


Ownership does not confer additional powers.


The parts of an object are still self-contained objects in their own right. The whole object does not suddenly decide to dig into their internals [Fig. 6.2(b)], just because it happens to own the parts.

From the perspective of contracts, the whole object is a client of its parts, much like any other client in the system. It must work with the specified pre- and post-conditions of the parts’ method and cannot assume additional details about their implementation.


Parts are responsible for their own invariants.


A particular aspect of the parts being self-contained is, of course, the treatment of their invariants: They are a private matter, so the parts areImage 4.1 responsible for maintaining the invariants, just as they would be outside ofImage 4.2.1 Image 4.2.3 the context of the whole object.


Invariants of the whole usually concern its parts.


The whole object employs its parts as an internal data structure, but it does not merely re-export their functionality—otherwise, the clients could just as well work with the parts directly. The contribution of the whole object lies in the combination and coordination of its parts to faciliate the more comprehensive services that it offers to its own clients.

In terms of contracts, this means that the whole will usually establish additional invariants about these parts, just as it would about any internal data structures. As a simple example, an ArrayList has the invariant that its field size is an index into the underlying array store [Fig. 6.3(a)].

Image

Figure 6.3 Invariants in Compound Objects

For a more complex example, we go back to the CCombo implementationImage 2.2.1 of a combo box used in the previous discussion of ownership. The object maintains, among others, two objects list and popup. The list is the widget for displaying the choice of items, the pop-up window contains the list and enables CCombo to place it on top of the current window.

org.eclipse.swt.custom.CCombo


List list;
Shell popup;


The ownership structure is shown in Fig. 6.3(b). The invariant associated with the two owned objects is then “popup has a single child, which is list.” [Note that the children of a widget are a public property, so theImage 7.1 situation does not contradict Fig. 6.2(b).]

It turns out that reasoning about these cross-object invariants is the hardest part of applying contracts to compound objects. We will discuss the conceptual basis in the following section.


The whole object is responsible for maintaining the cross-object invariants.


Image 2.2.1An object creates, maintains, and destroys its owned parts. During their lifetime, the object wires them up to create a data structure to fulfill service requests by its clients. This “wiring up” technically means, of course, to establish and maintain the invariant about the parts and their published model fields. For merely passive parts, this can be done by setting theirImage 6.2.3.5 properties and fields accordingly; for more active parts, it might involveImage 2.1 registering observers on their state to adapt its own fields, as well as other parts, according to state changes in the parts.

6.2.2 Ownership and Invariants

The handling of invariants in connection with ownership and structure sharing requires careful attention. Fig. 6.4 outlines both cases to illustrate their difference. The Whole object owns object O but also holds a reference to an object S shared with object Other. The challenge is, of course, that both Whole and Other can modify S through their respective references.

Image

Figure 6.4 Invariants for Owned and Shared Objects

Image 1.3.1In this context, we have to let “references” include both fields containing data structures and temporary references stored in parameters and local variables. Anything that lets an object’s code access another object constitutes a “reference” to that object.

In this section, we will discuss a solid foundation for delineating ownership from sharing and for reasoning about invariants including owned part objects. We will first establish its elements and then assemble the overall approach. In the end, we will reach an intuition that neatly extends the basic one from Fig. 4.1 to the new challenges and that comes, again, with practical guidelines.


Treat assertions as implicit references.


The main point of the illustration in Fig. 6.4 is the invariant I, which may mention the fields o and s and through them the properties and model fields of objects O and S. These conceptual, implicit references are shown as dashed arrows.


Invariants may reference only owned objects.


The central insight leading to a solution of the previously described challengeImage 21 derives from the introduction of two rules:

• The invariant of an object may reference only owned parts.

• No other object may access the owned parts.

Together, these rules ensure that the invariant of a whole object never gets broken, since no other object can possibly modify its owned parts. We deliberately restrict the objects referenced in the invariant to only the owned objects to make the invariant “safe from destructive side effects.” InFig. 6.4, the reference from I to S is therefore forbidden and crossed out.

One possible precaution for preventing other objects from accessing the owned parts is, of course, to make sure that no one else has any references to these parts in the first place. In the earlier example of theImage 4.2 ThresholdArrayIterator (Fig. 4.7), for instance, the constructor makes a copy of the passed array; otherwise, the situation of Fig 6.4 may have arisen, where the caller could have modified the passed array at some later point. This, however, would have invalidated the entire reasoning about the iterator’s correctness in Section 4.2.


Image The idea of making assertions “safe from destructive side effects” by ownership even supports the much more complex situation of multithreading. There, objects can beImage 8.1 modified not only through all existing references, but also at unpredictable moments in time. For example, an assertion that you knew to hold at some point can be broken evenImage 4.1 before the next statement starts executing, because the scheduler happens to interleave the execution of a different thread in the meantime. The concept of thread confinementImage 148 extends ownership to this challenge: If only the current thread can possibly obtain a reference to a given object, then assertions regarding that object will remain valid regardless of the scheduler’s decisions and the side effects of other threads. In this context, therefore, not only compound objects, but also threads, are said to own objects.


The proposed restriction can be explained and motivated by saying that the owned parts of an object effectively become part of the object’s representation. Since they serve as an internal data structure, it is clearImage 21,193 Image 1.3.1 that the object should be able to state invariants about them.


The guideline introduces a restriction on programming techniques.


Before we progress further, however, it should be clarified that the proposal is, indeed, a restriction. For one thing, other objects cannot even perform read accesses to the owned parts. Here is a practical example of such aImage 214 situation. The standard Figure from the Graphical Editing Framework internally manages its current position and size in a rectangle bounds. The getter for this field actually returns the internal rectangle object, therebyImage 1.3.3 violating the established principles for accessors.

org.eclipse.draw2d.Figure


public Rectangle getBounds() {
return bounds;
}


The API documentation states this violation clearly:

Implementors may return the Rectangle by reference. For this reason, callers of this method must not modify the returned Rectangle.

The reason for deviating from good practice here is efficiency: Most callers simply wish to peek quickly at some property of the bounds—for instance, the width or height. Creating (and later garbage collecting) a new object for each such access is unacceptable.

The second restriction is that the state of object Whole in Fig. 6.4 may actually depend on the state of the shared object S, which intuitively leads to an invariant involving S. Such a dependency, for imaginary fieldsImage 4.1 width and children, might take the form of an invariant such as “the field width is always the number of elements in children of S.” Such dependencies are encountered very frequently in practice. Indeed, they areImage 2.1 the very motivation for the widely used OBSERVER pattern: They make it necessary to synchronize the states of otherwise unconnected collaborators. For the current example, Whole would observe S and adapt its width fieldImage 6.2.3.5 whenever the children in S change. We will later examine such looser kinds of invariants on shared objects in more detail.


The concept of ownership accepts some limitations to obtain simplified reasoning patterns and reduce the risk of bugs.


The question is, of course, Why should we deliberately restrict ourselves in writing code? That is, why should we give up efficient coding practices merely to fit our code into some conceptual framework? The answer is that the context created by the coding restrictions enables self-contained, reliable, and simple arguments about conforming code.

General code, in contrast, requires ad-hoc reasoning steps and easily leads to bugs. To continue the example of Figures, anchors attach connections to figures and keep them attached even when the figures move. Suppose some shape always attaches connections to the right-middle point of its bounding box. The following code seems to compute that point and even correctly reports the coordinates in the global system.1 However, in view of the above documentation of getBounds(), it is wrong, because it implicitly modifies the bounds field of the figure to which the anchor is attached, with the effect that the figure paints itself in the wrong position.

1. The naming of getOwner() here is an unfortunate coincidence: The “owner” of an anchor is the figure to which the anchor is attached. The anchor is not “owned” by the figure in the meaning of the current discussion.

ownership.RightAttachmentAnchor.getLocation


public Point getLocation(Point reference) {
Rectangle b = getOwner().getBounds();
getOwner().translateToAbsolute(b);
return b.getRight();
}



Image The approach of restricting programming patterns with the aim of simplifying the reasoning about the resulting code becomes particularly relevant in the area of formal verification: Formalizing any possible ad-hoc arguments that inventive developers might employ leads to huge and complex formulas and is simply not viable. Also, the ad-hoc arguments used in different parts of the code usually do not combine well, so the overall program cannot be proven correct.

The term methodology refers to a coherent framework (or regime) of programming rules that dictate the usage of certain language features and gives a corresponding set of reasoning patterns that work on the resulting set of programs. The approach by BarnettImage 21 et al. that we are following here is such a methodology. Other examples concern the meaning and use of “abstraction,” the separation logic view that the heap should beImage 155 Image 4.7.4.3 seen as a set of non-overlapping areas, the use of Burstall’s memory model, and a viableImage 38,247,126 explicit encoding of disjointness assertions about heap objects. In all of these cases,Image 58 certain kinds of programming patterns are supported by the reasoning infrastructure,Image 67,102 while ad-hoc deviations can be treated, if at all, only with much more effort.



Ownership is a dynamic property.


We have introduced ownership by saying that the owner determines theImage 2.2.1 lifetime of an owned part object. However, this does not mean that the ownership relation persists throughout that lifetime. An owner can hand on the responsibility for managing one of its parts to a new owner. This happens, for example, with factory methods, where the object containingImage 1.4.12 the factory method very briefly owns the created object, before returning it to the caller.

For instance, an ImageDescriptor in JFace is a lightweight referenceImage 9.3 to some image stored on an external medium. The specific implementation for files creates the actual image using the following method. Just after theImage 2.2.1 FileImageDescriptor has created the new image, it assumes the duties of its owner; for instance, it must dispose of the image when it is no longerImage 7.4.1 required. Immediately afterward, however, it passes these duties, along with the created object, on to its caller.

org.eclipse.jface.resource.FileImageDescriptor


public Image createImage(boolean returnMissingImageOnError,
Device device) {
String path = getFilePath();
...
return new Image(device, path);
...
}



Make ownership itself a proof obligation in establishing the owner’s invariant.


The preceding discussion can be summarized in two points: Invariants can refer to only owned objects and ownership is dynamic. In conclusion, we somehow have to ensure that whenever the invariant on the owner has to be established, the ownership has to be established at the same time; that is, the owner must “be sure of its parts” before it can say anything about its invariant.

Image 21 Image 4.4This is, indeed, the main insight of the approach that we examined earlier: When “packing” the owner, and thereby establishing its invariant, we must fix the ownership of its parts. Fig. 6.5 illustrates this point fromImage 6.2.1 the perspective of the owned part. Since the invariant of that part must be reasoned about independently, the new state chart is an extension of Fig. 4.10, which depicts packing and unpacking of an individual object. Now, we add a new state “committed,” where the local invariant of the part holds and the part is owned by a particular object. The state transition from “valid” (local invariant holds) to “committed” is not triggered by an action on the part, but on its owner.

Image

Figure 6.5 Objects States for Invariants with Ownership

Two observations are necessary to establish that the invariant of whole cannot be violated by side effects after whole has been “packed.” First, the state chart in Fig. 6.5 ensures that each object can have only a single owner at any given time: The first potential owner that “packs” itself to establish its invariant will also “commit” the desired part. The next potential owner that tries to claim the part for itself cannot do so, because Fig. 6.5 does not allow it to “pack up” parts that are already “committed.” Second, other objects are no longer able to invoke methods on the parts because those methods would require the parts to be in state “valid,” instead of the state “committed.” That state “committed” is not a somehow stronger form of “valid,” but rather a completely distinct state.


Invariants with ownership extend the intuition for basic invariants.


In the introduction to contracts, we gave an intuitive illustration of invariantsImage 4.1 by depicting them as thick borders, as opposed to perforated borders when the object was currently working and was possibly violating the invariant (Fig. 4.5).

The extension to the state of objects described in this section also translates to an extension to that intuition. Fig. 6.6 displays how first whole, then its part p, start working. On the left, all objects are “OK”—that is, their invariants hold. Additionally, whole has been able to “lock” its two parts p and q by setting their state to “committed,” so that no other object can incorporate them into its own representation or work with them by calling methods. One step further, a method of whole is invoked and “unpacks” that object. At the same time, it releases the “locks” on the parts by changing their state from “committed” to “valid.” Finally, on the right, a method of p starts working and “unpacks” that object. The reverse direction is executed when those methods finish executing: First p is again “packed”; then whole is “repacked,” which also “locks” its parts.

Image

Figure 6.6 Objects’ States for Invariants with Ownership


The reasoning pattern enables dynamic transfer of ownership.


Although the introduced regime does not enable other objects to access, or even read from, owned objects, it does not forbid other objects to hold references to those parts—just as long as they do not try to work with the parts. In Fig. 6.6, for instance, the whole may hand out a reference to its parts, either before or after “unpacking.” In the middle picture, it may then let go of its own reference to p or q, set the corresponding field to null, and repack itself. Now, another object can claim ownership of the released part.


The introduced reasoning patterns are reliable.


The interesting point about these reasoning patterns is that they are solid enough to satisfy even a theorem prover. By making the state of an object,Image 21 as depicted in Fig. 6.5, into a ghost state, which exists only for proof purposes but not at runtime, the prover can keep track of the overall object population of the program and will guarantee that invariants, including cross-object invariants about owned parts, are never violated.


Mentally tag objects with their current owners.


In all of these proofs, the prover never has to be told explicitly which object really owns a part; it is sufficient that there is no owner in state “valid” and “some owner” in state “committed.” Humans, in contrast, usually have problems with such rather vague statements.

As a practical deduction, we therefore propose to mentally tag each object with its current owner. The owner becomes a pseudo-field (formally, a ghost field) of the object that points to its current owner. An object is in state “committed” exactly if that field is non-null.

Note the switch of perspective induced by this discussion: The important thing is no longer that some objects happen to own some objects that they reference. Rather, the important point is that any object at all can in principle be owned at any given point in time, and must then be immune to modification. If we always track whether this is the case, this approach enables us to ask, for any object at any place in the program,

“Who does currently own that object?”

It turns out that this perspective is, in fact, much more useful than the old one proposed in Section 2.2.1, because it enables you to make decisions that become necessary in the code you are currently working on.

Here is a practical example. The JFace ColorSelector creates a buttonImage 9.3 showing the current color in a filled image; when the user clicks the button, a dialog opens that enables the user to pick a new color. The question in the current context is: Who owns the filled image—the button or the selector? Let us track this through the following constructor. In line 1, the selector creates the image and owns it. Line 3 has the potential for dynamic ownership transfer, since the button obtains a reference to the image. The API of setImage() does not mention ownership, and indeed (under Linux/GTK) the button makes a private copy of the image data in an implementation-level pixel buffer. So in line 4, the selector still owns the image. It therefore remains responsible for freeing the resources when the image is no longer required, and makes the appropriate provisions in lines 4–11: Whenever the button vanishes from the screen, the image can also be destroyed.

org.eclipse.jface.preference.ColorSelector


1 fImage = new Image(parent.getDisplay(), fExtent.x, fExtent.y);
2 ... fill image with current color
3 fButton.setImage(fImage);
4 fButton.addDisposeListener(new DisposeListener() {
5 public void widgetDisposed(DisposeEvent event) {
6 if (fImage != null) {
7 fImage.dispose();
8 fImage = null;
9 }
10 }
11 });



Whenever you establish the invariant of a compound object, mentally check the owner-fields of all parts referenced in the invariant.


This guideline directly translates the formal rule that “packing” the owner requires its parts to be in state “valid” (rather than “committed”; see Fig. 6.5). It is useful because it establishes a warning bell for programming.Image 4.2.4 For instance, constructors have to establish the invariant at theirImage4.2 end. The invariant (4.5) of the ThresholdArrayIterator clearly involves the array a, a separate object:

0 ≤ i ≤ a.length && (i = a.length || a[i] ≤ threshold)

To establish the invariant with this reference to a, we also have to establish that the iterator may own the array a—that is, that it may set its state from “valid” to “committed.” The original code in Fig. 4.7 enables this step by simply making a local copy.

As we have already pointed out, the new reasoning framework is somewhat more liberal, in that it allows others to retain references to the parts, as long as they do not access these parts. Suppose we were to omit the copy and use the following, more efficient code:

ownership.ThresholdArrayIteratorRisky


public ThresholdArrayIteratorRisky(int [] a, int threshold) {
this.a = a;
this.i = 0;
this.threshold = threshold;
findNext();
}


This code is legal, if somewhat risky. We have to add the pre-conditon

a is not “committed”, i.e., has no owner.

and the post-condition

a is “committed” with owner this.

Then, we have to rely on the caller to respect the new state of the passed array, meaning it must no longer access the array. In short, it has transferred ownership to the iterator.

6.2.3 Invariants on Shared Objects

In the previous section, we introduced a methodology for reasoning about invariants that involve owned parts. In essence, whenever the invariant had to be established, the ownership had to be established as well. Furthermore, all other objects had to respect that ownership and were no longer allowed to access the part objects.

Image 1.3.2 Image 11.1 Image 2.2.2Unfortunately, many programming practices do not fit this schema. In fact, object-oriented programming could be said to be all about structure sharing and aliasing: If objects are to form networks of collaborating individuals,Image 1.1 Image 11.1 then naturally these individuals are not always arranged in some artificial ownership hierarchy. Furthermore, the fundamental principle that objects have identity naturally implies that several objects will access the single object representing a particular concept or application-level entity.

As a consequence of the arising nonhierarchical, symmetric, and cyclic relationships, it is very often not even possible to attribute invariants to individual objects, but only to groups of objects. Typical and intuitive examples arise in user interfaces, where fields in dialogs must frequently be linked by some consistency condition. Fig. 6.7 shows such a dialog that converts between dollars and euros, given the current rate. It is available in class CurrencyConverter of the sample code. Whenever one of the fields changes, the others must be updated to reflect, as an invariant, the equation

eur = rate × dollar

Image

Figure 6.7 Currency Converter

This invariant can be established by attaching suitable observers to allImage 6.2.3.5 Image 2.1 fields.

The general situation of object groups linked by invariants is illustrated in Fig. 6.8. Objects a, b, and e access one another cyclically, while b and c share d. The first group synchronizes their states such that I1 holds; the second maintains I2. Let us call such invariants global, because they refer to several objects at once, rather than being attached to a particular object and the objects accessible to it.

Image

Figure 6.8 Global Invariants


Avoid invariants spanning multiple objects.


Reasoning about such situations formally or even precisely involves substantial machinery. Practioners will not find this surprising: Object structures with much sharing and global invariants frequently cause bugs. The first advice is to avoid such invariants if possible. Since this is not always possible, we will discuss some practical approaches to taming the harmful consequences.

6.2.3.1 Immutability

Image 1.8.4We have already discussed the fundamental strategy of using immutable objects that essentially represent values. This approach is especially suitable for sharing potentially large internal representations. The class BigInteger, for instance, uses a sign/magnitude representation, storing the digits in an array. Since that array can be large, operations try to share it as far as possible. Prototypically, the negate operation uses the same array in the result value:

java.math.BigInteger


public BigInteger negate() {
return new BigInteger(this.mag, -this.signum);
}


The constructor called here simply stores the passed array:

java.math.BigInteger


BigInteger(int[] magnitude, int signum) {
this.signum = (magnitude.length == 0 ? 0 : signum);
this.mag = magnitude;
}


In the current context, we can also discuss the invariants expressed in the class’s documentation in some more detail. There, we find the following assertions about fields signum and mag, which serve to make the representation of a given integer value unique.

1. sign is 1, 0, or 1.

2. If the represented value is 0, then signum = 0 and mag.length = 0.

3. Otherwise, mag.length ≠ 0 and mag[0] ≠ 0.

Obviously, maintaining these invariants in the face of structure sharing is possible only if mag is treated as immutable.

6.2.3.2 Copy-on-Write

The core problem of shared objects is that the objects may change “while one is not looking” because someone else performs a modification: While one object describes the current state of the shared part in its invariant, another object modifies the part and breaks the invariant. Immutability of the shared parts is one, perhaps rather ruthless, method of preventing such destructive updates by disallowing updates altogether. Copy-on-write is aImage 1.8.4 somewhat softer form of protecting the invariants of different stakeholders in a shared part.

A typical example occurs with iterators over data structures. In principle, an Iterator must be a lightweight object and iteration must be fast, because it happens very often. The iterator must therefore share the underlying data structure with its container, as shown on the left-hand side of Fig. 6.9.

Image

Figure 6.9 Sharing with Copy-on-Write

A typical example is found in the CopyOnWriteArrayList from the Java concurrency library. Here, the array list just passes on the internal array to the new iterator and the constructor of that iterator stores the reference directly. The next() operation can simply advance the cursor position (with pre-condition hasNext(), as usual) and remains lightweight.2 Image 4.2

2. Readers familiar with concurrency will sense that the access to the array field itself should be protected. Indeed, the field is declared volatile, so that writes and reads on that field occur in a well-defined, although unpredicatable, order under the Java memory model [111, §17.4.4].

java.util.concurrent.CopyOnWriteArrayList


public Iterator<E> iterator() {
return new COWIterator<E>(array, 0);
}


java.util.concurrent.CopyOnWriteArrayList


private static class COWIterator<E> implements ListIterator<E> {
private final Object[] snapshot;
private int cursor;
private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
snapshot = elements;
}
public E next() {
return (E) snapshot[cursor++];
}
... remaining iterator operations
}


The problematic case occurs, of course, when some client of the array list sets one of the elements. It then depends on the current position of the iterator, and in the case of concurrency also on the unpredictable decisions of the scheduler and the effects of the Java memory model, whether anext() call receives the old value or the new value. This undefinedness is clearly unacceptable.

The solution is shown on the right side of Fig. 6.9: Upon modification of the array, the list allocates a completely new array and leaves the previous, unmodified copy to the iterator to continue its work. The code of set() merely adds the detail of checking whether the write is necessary at all.

java.util.concurrent.CopyOnWriteArrayList


public E set(int index, E element) {
... locking because of concurrency
Object[] elements = getArray();
E oldValue = (E)elements[index];
if (oldValue != element) {
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len);
newElements[index] = element;
array = newElements;
}
... further measures because of concurrency
return oldValue;
}



In copy-on-write, the modifier protects invariants of other stakeholders.


The central idea is that the “perpetrator,” who could possibly break the invariants of other objects by its modification to shared parts, protects those invariants by performing modifications on a private copy only.


Copy-on-write behaves as an optimized variant of immediate copying.


The overall behavior is the same as if each iterator had made its private copy at the start of the iteration: Iterators, once they are created, continue to work on the same, unmodified array.


Copy-on-write works only for internal data structures.


For the strategy to be effective, all participants and possible owners of shared parts must be aware of the copy-on-write policy: Whenever they modify the part, they must first obtain their own copy.


Reference counting can improve performance.


Reference counting is a standard technique for managing memory objects.Image 133 Each memory object has an attached counter that keeps track of how many pointers to itself currently exist. When the count reaches 0, the memory can be freed and reused.

This technique can also be applied to the copy-on-write policy, as shown in Fig. 6.10. Whenever A or B wishes to modify rep, it checks the current reference count. If it is 1, as shown on the right, then “no one else is looking,” so modifying the representation will not break their invariants and copying can be avoided altogether.

Image

Figure 6.10 Copy-on-Write with Reference Counting

Of course, reference counting requires the active collaboration of the referencing objects, A and B in Fig. 6.10: Whenever their references become obsolete, they must decrease the counter of rep. This is the case, in particular, when their life cycle ends so that they no longer require rep. Unfortunately, Java does not reliably notify objects before their destruction. However, in many cases, the life cycle of objects is well defined byImage 1.6.2 the surrounding framework—for instance, because the management of externalImage 12.3.3.4 Image 7.4.1 resources such as images and fonts for screen display demands an explicit release. When copy-on-write is applied to large shared objects such as styled text documents, these are often associated with similarly “large” objects such as editors, and such parts usually do receive notifications byImage 7.3.2 the framework about their own life cycle.


Image C++ requires all objects to be deallocated explicitly, because there is no garbage collector. For local, stack-allocated objects, this happens when the static block in which they have been created is left; the compiler injects the necessary code automatically. For heap-allocated objects, the application is required to use the delete operator. In each case, the destructor of the destroyed object is called to give it a chance to free any other memory objects and additional resources that it may have allocated. Also, any copy or assigment can be intercepted by overloading the copy constructor and the assignment operator, written in C++ as operator=. These facilities together then enable reference counting: Copies and assignments increment the count, and the destructor decrements the count and frees the referenced memory object if the count reaches 0. Concrete code can be found in the classes string and, of course, shared_ptr in the library.


6.2.3.3 Versioning

The copy-on-write policy in the previous section avoids breaking invariants of sharing owners, but at the cost of permitting a somewhat sloppy 'margin-bottom:6.0pt;text-align:center; line-height:normal;background:#E5E5E5'>

Detect problematic cases instead of avoiding them.


One can do better if instead of avoiding breakage, one can be content with detecting it. In the case of iterators, for instance, clients do not usually iterate through the data and modify it at the same time. In those rare cases where this step is necessary, they would simply have to make anImage 2.1.1explicit copy of the data structure. One such example has been seen in the OBSERVER pattern, where observers may wish to de-register themselves when they receive a change notification—that is, while the traversal of the observer list is in progress.


Inject runtime checks to detect harmful modifications.


In the vast majority of cases, however, that copy can be avoided, while still ensuring the invariants of the owner objects remain intact: The iterator simply has to recognize that a modification has taken place and throw an exception. This exception will alert the developer to a violation of the assumption that the collection remains unmodified throughout the traversal.

Let us look at the example of a HashMap, because it illustrates the point of complex structures better than a simple ArrayList, which applies theImage 72 same scheme. Fig. 6.11 illustrates the hash map’s internal structure: The array table is indexed by (a convolution of) the hash code computed for the key that needs to be found. Since usually several objects have the same hash code, all objects with the same code are kept in the same bucket, which is a linked list of Entrys. An Iterator for the set of entries must then follow that structure, as is indicated by the dotted line. Obviously, that iterator would easily go astray if the hash map was to change during the traversal.

Image

Figure 6.11 Internal Structure of a HashMap

Indeed, the iterator keeps two references into the hash map’s internals: index points to the current bucket, and next is the next entry toImage 4.2 be returned. Note that this description could be connected to model fields sequence and pos to formulate a precise invariant forHashIterator. It is this invariant that we seek to protect.

java.util.HashMap


private abstract class HashIterator<E> implements Iterator<E> {
int index;
Entry<K, V> next;
int expectedModCount;
...
}


The last field in the preceding code snippet, expectedModCount, is the key to the solution. The hash map keeps a similar field modCount, which it increments in put() whenever the structure changes in such a way that an existing iterator’s invariant would be broken (line 7).

java.util.HashMap


transient int modCount;


java.util.HashMap


1 public V put(K key, V value) {
2 ... look up existing entry and update if it exists
3 e.value = value;
4 e.recordAccess(this);
5 return oldValue;
6 ...
7 modCount++;
8 addEntry(hash, key, value, i);
9 return null;
10 }


When the iterator is first created, it remembers the current count:

java.util.HashMap.HashIterator


HashIterator() {
expectedModCount = modCount;
... advance to first entry
}


When next() starts running, it protects the iterator’s invariant by checking whether the shared data structure is still intact. If it is, the iterator proceeds as usual to find the next entry. The code in lines 5–9 clearly relies on the internals being undisturbed from the previous visit, since otherwise both index and next may be pointing to invalid locations. Lines 2–3 signal a broken invariant to the developer.

java.util.HashMap.HashIterator


1 final Entry<K, V> nextEntry() {
2 if (modCount != expectedModCount)
3 throw new ConcurrentModificationException();
4 Entry<K, V> e = next;
5 if ((next = e.next) == null) {
6 Entry[] t = table;
7 while (index < t.length && (next = t[index++]) == null)
8 ;
9 }
10 return e;
11 }


6.2.3.4 Implicit Maintenance

In many situations, cross-object invariants are not as general as made out in the introduction to Section 6.2.3, and in particular Fig. 6.8. Instead, they concern only two objects that work together closely and that can easily negotiate the invariant between themselves.

Image 2.2.1For instance, the parent–child relationship in ownership usually comes with the invariant that the child’s parent pointer refers to the uniquely determined object that currently owns the child. We have already seen theImage 214 example of the Graphical Editing Framework’sFigures, whose method for adding children maintains this invariant implicitly, as a side effect:

org.eclipse.draw2d.Figure.add


if (figure.getParent() != null)
figure.getParent().remove(figure);
children.add(index, figure);
figure.setParent(this);



If you decide on implicit maintenance, do it properly.


However, the example is not perfect, since the invariant is not maintained in the reverse direction: Setting the child’s parent does not add it to the parent’s list of children:

org.eclipse.draw2d.Figure


public void setParent(IFigure p) {
IFigure oldParent = parent;
parent = p;
firePropertyChange("parent", oldParent, p);
}


Of course, such asymmetric behavior is very annoying and easily leads to bugs, since developers constantly have to keep track of which invariants are maintained under which circumstances. Another example will be seen in Section 6.2.3.7, where creating a new edge in a graph establishes some, but not all, necessary connections.

For a positive example, we turn to the concept of opposite references in the Eclipse Modeling Framework. We use a simple model of Nodes andImage 235 Edges, which together form a graph structure. There is, of course, a local invariant that links the outgoing edges of a node to thestart references of all of those edges (and similarly for the end references of incoming edges). EMF generates the following code for Edge.setStart(), which first removes the edge from the node it may have been attached to previously and then adds it to the node it is attached to now. (InvRel, for inverse relationships, is the name of the model; EMF generates several helpers for such a model.)

invrel.Edge


public void setStart(Node newStart) {
if (newStart != start) {
if (start != null)
msgs = ((InternalEObject) start).eInverseRemove(this,
InvrelPackage.NODE__OUTGOING, Node.class, msgs);
if (newStart != null)
msgs = ((InternalEObject) newStart).eInverseAdd(this,
InvrelPackage.NODE__OUTGOING, Node.class, msgs);
this.start = newStart;
}
}


The reverse direction is supported symmetrically: The outgoing edges of a Node are not simply a list, but rather a list that actively maintains the opposite references.

invrel.Node


public EList<Edge> getOutgoing() {
if (outgoing == null) {
outgoing = new EObjectWithInverseResolvingEList<Edge>(
Edge.class, this,
InvrelPackage.NODE__OUTGOING,
InvrelPackage.EDGE__START);
}
return outgoing;
}


Regardless of whether the relationship between an Edge and a Node is established from the Edge’s side or the Node’s side, the local invariant between the two is always maintained.

6.2.3.5 Maintaining Invariants More Loosely

Let us go back to the initial example from Fig. 6.7 on page 309, a simple currency converter between dollars and euros that works in both directions. The conceptual invariant on the three text fields expresses that the computation has always been carried out faithfully so that

eur = rate × dollar

The standard approach to maintaining such interdependencies betweenImage 2.1 dialog fields is to attach observers that propagate changes according to the desired result (Fig. 6.12): Observer (a) takes care of changing dollar entries, (b) takes care of changing rate entries, and finally (c) updates the dollars whenever the euros change. The dotted lines indicate which other value the observers will be using.

Image

Figure 6.12 Updating in the Currency Converter

All three observers work alike: They wait for modifications of a textImage 7.1 field and then change the other fields accordingly. User interface elements in general provide for such observers. To exploit the symmetries betweenImage 3.1.4 the three, we introduce an abstract base class Updater that observes a textImage 1.4.9 field, converts its value to a number, and uses the TEMPLATE METHOD to abstract over the concrete reaction.

globalinv.CurrencyConverter


abstract static class Updater implements ModifyListener {
private static boolean updating;
public void modifyText(ModifyEvent e) {
... break cyclic updates
update(new BigDecimal(
((Text) e.getSource()).getText()));
... take care of format exceptions
}
protected abstract void update(BigDecimal val);
}


As an example, the updater (a) in Fig. 6.12 reuses this infrastructure as follows (getRateValue() converts the entered text into a BigDecimal). Note how the computation in lines 3–4 express precisely the invariant between the fields. Similar observers are attached to the rate and euro fields.

globalinv.CurrencyConverter.createContents


1 txtDollar.addModifyListener(new Updater() {
2 protected void update(BigDecimal val) {
3 txtEur.setText (
4 val.multiply(getRateValue()).toPlainString());
5 }
6 });



Observers maintain invariants by propagating necessary updates.


From the user’s perspective, the dialog now works fine: Whenever the user types into one of the fields, the other dollar or euro field reflects these changes immediately and the display always shows the invariant.


Observers provide loosely coupled dependencies.


The attraction of using observers to establish invariants is their lightweight nature: With a few extra lines of code, you can wire up components that were not built to interact. In the example, the separate text fields do not even hold references to each other; it is only the observers that create their interaction. Components that know very little about each other are called loosely coupled.Image 12.1


Observers establish separation of concerns.


Another nice aspect of this solution is that the aspect of displaying and entering the information is completely separated from the aspect of maintaining the invariants. In the code, these aspects are managed by disjoint parts, which simplifies maintenance because the developers just have to understand the aspect that they are currently concerned with, or that exhibits an undesirable behavior.


Maintaining invariants by observers leaves consistency gaps.


A disadvantage of linking different objects through observers is that the apparent invariants do remain broken for some time, as Fig. 6.13 illustrates. When the user types a character, at some point the current text field will update its content and will notify its observers. The special Updatercan then modify the linked fields correspondingly before all modified fields repaint themselves on the screen.

Image

Figure 6.13 Maintaining Invariants with Observers

In between the update of the edited field and the reaction of the Updater there is, of course, a brief time span in which the invariant is broken. Fortunately, the arrangements of the user interface framework make sure thatImage 7.1 the user cannot become aware of this: Each event-handling cycle processes user input completely before the screen is repainted, so that all fields are up-to-date at the time the results are actually shown to the user.


Other observers can see the broken invariant.


The question is: Does the broken invariant really matter if the user does not become aware of it anyway? The answer: Yes, it does matter, because the software itself can trip over the inconsistency and might make wrongImage 1.5.4 Image 1.5.3 decisions or incur runtime exceptions as a result.

Technically, the sequence of notifications leaves only a very brief time span before the invariant gets repaired (Fig. 6.14). When the first field is set by the user’s typing, it immediately notifies the updater, which in turn sets the dependent field. When the original call setText returns, everything is in order.

Image

Figure 6.14 Method Calls in Observer-Based Invariants

The critical time span, which is shaded in Fig. 6.13, can therefore be defined more precisely: Since the inner execution sequence within the field cannot matter, the time span starts with the first outgoing call by notify and ends with the outgoing call to the updater.

To demonstrate that this is not a theoretical problem, let us write a small runtime checker for the invariant. It observes text changes in the fields, so as to be able to “listen in” on the ongoing update process.

globalinv.CurrencyConverter


public class RuntimeChecker implements ModifyListener {
... keep a string tag 'which'
public void modifyText(ModifyEvent e) {
if (!getEurValue().equals(
getDollarValue().multiply(getRateValue()))) {
System.err.println("Invariant violation detected: "
+ which);
}
}


It then remains to attach listeners “around” the actual updater. At runtime, these do, indeed, signal violated invariants.

globalinv.CurrencyConverter.createContents


RuntimeChecker checkA = new RuntimeChecker("A");
txtDollar.addModifyListener(checkA);
... register others
txtDollar.addModifyListener(new Updater() {
...
});
... the two other updaters
RuntimeChecker checkB = new RuntimeChecker("B");
txtDollar.addModifyListener(checkB);
... register others


The phenomenon encountered here can also be seen as a variant of the fundamental principle that objects must be consistent before sendingImage 2.1.2 out their notifications. The only difference in the current case is that the invariant is associated with a group of objects that conceptually, though not technically, are to behave like a single compound object.


Loosely coupled systems are likely to see the broken invariant.


The OBSERVER pattern is usually not applied in isolated spots, but pervasively throughout the system. One of the reasons is that it makes for a neat decoupling of different subsystems, because the fundamental principleImage 12.2.1.8 Image 2.1.2 of designing the observer interface according to the possible changes in the subject, and not the expected concrete observers, makes sure that subjects know next to nothing about their observers.

In such systems, observers often function in cascades: When an observer receives a change notification, it notifies its own observers in turn, and so on. Because the order of observers cannot be influenced in a predictable fashion, this can easily lead to problematic situations, as illustrated in Fig. 6.15: Objects (a) and (b) are linked by an invariant that is maintained by an updater, in the manner seen earlier. Before the update takes place, however, (a) happens to notify (c), which notifies (d) and (e) in return. Now (e) is an object that happens to work with both (a) and (d).

Image

Figure 6.15 Cascading Notifications and Invariants

The sketched problem occurs in systems where observers are used in many places, so that the potential for cycles, where some notified observer gets back to the original source of the cascading changes, becomes more likely.


Debugging with loosely coupled invariants can be cumbersome.


The crucial dilemma here is that each of the observer relationships is set up locally with the best intentions and according to the design goals. It is only in the resulting overall structure that the problem manifests itself. Furthermore, the order of registration can make all the difference: If the updater for (b) happens to run before the notification to (c), all is in order. Since there is no single place in the source code to which the misbehavior can be pinned, it becomes hard to track down and solve the problem.


Weigh the consequences of maintaining invariants by observers.


There are two conclusions to be drawn from the preceding discussion. First, it is very often possible to maintain invariants in a loosely coupled, minimally invasive way by simply attaching appropriate observers to preexisting generic components. The observers can then propagate changes in such a way that the desired invariant holds once all observers have run to completion. Second, one should avoid such “ad-hoc invariants” between different objects, because they are not proper invariants in the strict sense of the word. Since they are broken on principle for short durations of time and since other objects in the system can easily become aware of that fact in practical situations, one would be well advised to avoid the construction altogether.

In the end, it is a question of whether the situation can be kept under control. Especially in the context of user interfaces, where the setupImage 7.1 of the event-processing loop prevents, ultimately, the problematic output (Fig. 6.13), a looser maintenance of invariants can be acceptable. However, one might say the following:


Protect crucial data structures by proper wrapping.


An alternative to the previously described dialog is obtained by taking the invariant between the three values seriously: If it is to be an invariant, we have to create a compound object that maintains it on its internal fields. Creating such a class in the current case is straightforward. The class has three properties (lines 2–4), provides change notifications (lines 5–6, 13) and reestablishes the invariant in every setter (line 12).

globalinv.CurrencyModel


1 public class CurrencyModel {
2 private double dollars;
3 private double rate;
4 private double eur;
5 private PropertyChangeSupport changes =
6 new PropertyChangeSupport(this);
7 public double getDollar() {
8 return dollars;
9 }
10 public void setDollar(double dollars) {
11 this.dollars = dollars;
12 eur = rate * dollars;
13 fireChanged();
14 }
15 ... similarly for rate and eur
16 }


The dialog can then be attached to this core class using data binding, soImage 9.3.3 that the overall effort is not much greater than for direct programming within the dialog.

A distinct advantage of separating out the data in this fashion is that such components can be tested indepedently of the actual user interface. It is, indeed, a common strategy to separate the data and functionality—inImage 9.1 other words, to separate the core business value of the application from its mere display and editing capabilities, which might have to change anyway when porting to a different platform or when users wish for new ways of interaction.

6.2.3.6 Dynamic Checking

Invariants can also be read as constraints. An equation, for instance, constrains the referenced variables to contain values that fulfill the equation. Very often, the constraint is actually a restriction. For instance, all nodes in an XML DOM tree must belong to the top-level document—in other words, you cannot add a node that does not belong to that tree. The following code will therefore throw a DOMException:

globalinv.Constraints.domOwnership


Document docA = docBuilder.newDocument();
Document docB = docBuilder.newDocument();
docA.appendChild(docB.createElement("root"));


Of course, like any expectation, invariants can be checked at runtime,Image 1.5.4 even if the non-redundancy principle decrees that this should not happen,Image 4.5 because invariants, like all assertions, should be derived by logical reasoning rather than by brute-force error detection.

Image 4.5 Image 1.5.4Cross-object invariants can, however, justify a little more runtime checking, by arguments similar to those introduced earlier:

• Cross-object invariants are complex side-conditions that must be observed by different classes and objects. It is therefore likely that they will be broken sooner or later, which will require efforts in debugging. The additional effort of checking will be justified by avoiding the later problems.

• The clients of an object structure may be involved in obeying and maintaining the invariant. In the DOM example, the client is actively involved in composing the object structure, and even straightforwardImage 6.2.3.5 observer relationships might be problematic and therefore need to be restricted.

Such checks can also involve design decisions. Let us look at anotherImage 214 tree structure, the Figure elements of a Draw2D image. On the one hand, they involve the global invariant that the tree never contains any cycles from a child to one of its parents. However, the generic method for adding children to a node can easily be used to create such cycles. Since nearly all processing steps of the Draw2D framework, such as painting, layout, and so on, depend on the absence of cycles for their termination, it is wise to report violations of the restriction as early as possible, rather than having to find out afterward at which point a specific cycle had been introduced. The method add() therefore checks the restriction in the very beginning:

org.eclipse.draw2d.Figure


public void add(IFigure figure, Object constraint, int index) {
...
for (IFigure f = this; f != null; f = f.getParent())
if (figure == f)
throw new IllegalArgumentException(
"Figure being added introduces cycle");
... perform the addition and re-layout
}


Image 2.2.1On the other hand, trees also require that each node has a single parent. This invariant could also be enforced by simply checking. However, the figure elements, like the XML DOM nodes, choose to silently re-parent the new child if necessary.

org.eclipse.draw2d.Figure.add


if (figure.getParent() != null)
figure.getParent().remove(figure);
children.add(index, figure);
figure.setParent(this);


However, this strategy is not the only possible one. The designers of the abstract syntax trees in Eclipse’s Java tooling have decided that a new child is acceptable to an ASTNode only if it does not already have a parent.

org.eclipse.jdt.core.dom.ASTNode.checkNewChild


if (newChild.getParent() != null)
throw new IllegalArgumentException();


Which of the two strategies is more useful depends on the expected needs of the clients: If they frequently move around subfigures, they mayImage 1.1 appreciate the silent re-parenting to maintain the invariants of the tree structure. At the same time, they must be aware of the fact that an existing figure that they insert at one place will suddenly disappear from its previous position in such a case. Since in the JDT case nodes are supposed to represent concrete spans of source code, such a side effect would certainly be rather surprising. Forcing clients to duplicate nodes explicitly, perhaps using ASTNode.copySubtree(), here is the more sensible choice.

6.2.3.7 Reconstruct Rather Than Synchronize

Cross-object invariants link the state of one object with the state of another object. If one of the objects changes, the other has to be adapted correspondingly, for instance using the OBSERVER pattern. In many cases,Image 6.2.3.5 however, the dependency is asymmetric: One object depends on the other, but not the reverse. In such cases, it can be sensible to implement the invariant by recomputing the dependent object’s state whenever its data is required.

As an example, suppose you want to lay out a directed graph displayed on the screen using the layout algorithms from the Graphical EditingImage 214,269 Framework’s Zest component. To accomplish that goal, you have to construct an instance of DirectedGraph that reflects your application-specific graph structure (Fig. 6.16). The nodes and edges in a DirectedGraph contain internal (package-visible) data that enables the layout alorithmsImage 1.7.1 to work efficiently. Technically speaking, it is necessary to create a graph structure that is isomorphic to the original one.

Image

Figure 6.16 Synchronizing Graphs for Layout

Certainly, the task can be solved by observers: Additions and removals ofImage 6.2.3.5 nodes and edges as well as possible reconnect operations on the application graph’s edge can all be reflected faithfully in the DirectedGraph. However, doing so may not be the best choice, since it is easy to make mistakes. The DirectedGraph itself has, of course, internal invariants. For instance, an edge attached to any node must also be listed in the graph’s edge list, as well as in the outgoing list of its source and the incoming list of its target node. Furthermore, some of these points are maintained implicitly, while others are not. For instance, the Edge constructor connects the new edge to its endpoints, but does not add it to the graph itself.

org.eclipse.draw2d.graph.Edge


public Edge(Object data, Node source, Node target) {
this.data = data;
this.source = source;
this.target = target;
source.outgoing.add(this);
target.incoming.add(this);
}



Reconstruct if synchronization is complex and does not save runtime.


The alternative to mastering this mesh of side-conditions is to simplyImage 1.1 rebuild the DirectedGraph for each layout operation, according to Amdahl’s law: The layout algorithms decide on the placement of nodes and routing of edges essentially by solving constraint systems. Such optimizations take so much time that building the graph structure up front hardly matters at all. Just think of all the development time saved at the little expense of a few milliseconds at the beginning of what will be a lengthy computation anyway.


Prefer synchronization to enable incremental updates.


In contrast, the strategy of reconstructing the dependent state should beImage 2.1.3 avoided if that state itself is observable. As we noted in the discussion of the push and pull variants of the OBSERVER pattern, updates usually cascade. As a consequence, it is necessary to send as detailed a change report as possible. The final operations that are triggered by the changes may beImage 9.4.3 expensive, such as repainting parts of the screen, so that it is essential to keep changes focused throughout the chain of notifications.


Reconstruct and compute the difference as a compromise.


When you decide to rebuild a dependent data structure despite the existence of OBSERVER objects, you can still aim at providing detailed change notifications, by comparing the original and the new structure after the new structure has been computed afresh. The usual way to do this is to merge the new structure into the old structure, and to gather changes on the way.

For instance, Eclipse’s Java Model maintains a tree representation of the current Java sources, as well as the meta-structure of packages, archives, projects, and so on. Here, we have a typical cross-object invariant: The Java Model must be kept up-to-date when the sources change. However, incremental parsing is an art, or a complex craft, by itself. The actual updateImage 257,260,108 notifications in the form of IJavaElementChanges are therefore computedImage 2.1.3 through differences. First, the Java Model tree is constructed from a new abstract syntax tree of the source (in CompilationUnit.buildStructure()). The new structure is passed on to a JavaElementDeltaBuilder, which recursively compares the new tree to the previous, cached version to detect the differences. Finally, these differences are sent out by the DeltaProcessor.

6.3 Exceptions and Contracts

Its contract places a method under an obligation: Given that the caller fulfills the pre-condition, the method must fulfill the post-condition—that is, it must provide the promised result. Sometimes, this obligation can beImage 4.1 rather too severe. While technically the method can always be held responsible for failing to establish its post-condition, morally there are situations where it should be exculpated. Suppose, for instance, that we wish to submit mail to the local SMTP daemon for delivery by connecting to its local well-known port. The constructor of Socket certainly cannot be blamed if the administrator failed to start up the daemon and the connection is refused in consequence.

exceptions.SocketConnect.connectToLocalSMTP


Socket s = new Socket((String)null, 587);



Throw an exception to signal that the post-condition cannot be established.


Exceptions signal unexpected circumstances, such as the missing communicationImage 1.5 partner in the preceding example. This general usage coincides with the need for a method to intentionally break its contract because it simply cannot fulfill the post-condition.


Use checked exceptions to signal external reasons for broken postconditions.


We argued earlier that checked exceptions should be used when the reasonImage 1.5.7 for aborting the processing is a problem that could be expected or forseen. This is the case, in particular, when a method needs to interactImage 1.5.2 with the outside world in the form of the network, the hard drive, or the user interface.

The perspective of contracts now adds another piece of support forImage 4.5 that advice. The whole point of contracts, as made explicit in the non-redundancy principle, is trust: A method trusts its caller to establish the pre-condition, and the caller trusts the method in return to establish the post-condition. Now ask yourself: Which kind of business partner would you trust more—one who notifies you at the deadline that unfortunately he did not make it due to unforeseen circumstances, or one who notifies you well in advance of possible reasons for delay?


The checked exceptions become part of the contract.


Declaring a checked exception is like adding an exit clause to a contract. The exception stands for some specific circumstance under which the method can be relieved of fulfilling its promise to always honor the contract.

The API of the Java library contains many examples of such clauses. For instance, the FileInputStream’s constructor states when it will not be able to read the given file:

Throws FileNotFoundException if the file does not exist, is a directory rather than a regular file, or for some other reason cannot be opened for reading.


Declared exceptions can be associated with alternative post-conditions.


Of course, a message that just says, “Sorry, I didn’t make it,” is not very informative. The textual information contained in an exception may be usefulImage 1.5.1 for maintenance purposes, but it does not help in handling the exception and recovering from the error.

Image 23It can therefore be useful to associate alternative post-conditions with the different exceptions a method declares in its header. The client might, in particular, be interested in guarantees about what has not changed, so that it can start again with the same object. Very often, however, such assertionsImage 1.5.6 are left implicit and are understood by a combination of exception safetyImage 4.2.6 and the assumption that model fields not mentioned as being modified are assumed to stay the same.

A common case is to give further information about the conditions under which an exception is thrown in such a way that this information reveals new insights about the object’s state. The additional post-condition is just this gained knowledge about the object’s current state. For instance, the XML DOM API for method appendChild() in class Node says:

NO_MODIFICATION_ALLOWED_ERR: Raised if this node is read-only or if the previous parent of the node being inserted is read-only.

When a client sees this specific exception, it knows not only that the insertion failed, but also that either the new parent or the old parent was read-only, so that the implicit re-parenting has failed. It can then take thisImage 6.2.3.4 information into account when devising recovery strategies.


Use unchecked exceptions for broken invariants and broken pre-conditions.


A second reason why a method might legally fail to establish its postcondition is, of course, that the caller has failed to provide the pre-condition. Although usually a method should not check for this, it might still beImage 4.5 advisable in some situations where the consequences of silent failure wouldImage 1.5.2 Image 1.8.7 be unacceptable. We suggested earlier that unchecked exceptions should be used for this purpose.

Again, this suggestion is backed up by the contracts point of view. When the caller breaks its part of the agreement by letting the method down on the pre-condition, the method can simply refuse to do any work at the earliest possible point. However, this kind of interaction is outside the world of contracts, so the corresponding exceptions should also not be mentioned in the contracts.

Similarly, when an object finds that it has broken its own invariant, this is not something that one would advertise to one’s partners in the contracts. So unchecked exceptions are the right choice here, too.


Strive to maintain invariants despite throwing exceptions.


Once a class invariant gets broken, the corresponding object becomes useless, since the next call to a public method will probably fail and mightImage 4.1 even cause damage to the rest of the system. The contract view on the concept of exception safety is therefore that invariants should be maintainedImage 1.5.6 even if a method throws an exception: The only place where sufficient information for restoring the invariant is available is the place where the exception is thrown, so the object’s internals should be repaired there and then.

6.4 Inheritance and Subtyping

Inheritance and interfaces are central abstraction mechanisms in object-oriented programming, and we have discussed their usage in some detail.Image 3 At the heart, the usage guidelines derive from the Liskov Substitution Principle,Image 3.1.1 which demands that an object of a subtype must be usable wherever an object of a super-type is expected. In this way, the object’s clients can be adapted to new situations by simply substituting the object with collaboratorsImage 1.3.2 Image 1.4.8.3 that exhibit variants of a common abstract behavior. In someImage 1.4.11 cases, the base class might even choose not to implement the behavior atImage 1.4.10 Image 1.4.9 all. Within a class, TEMPLATE METHODS define collaborations of an object with itself that can be adapted by subclassing.

The task in this section is to present a conceptual framework thatImage 4.1 covers these different uses of inheritance, integrates with the fundamental strategies for reasoning about correctness, and can in principle even beImage 4.7 extended to formal reasoning. Before we start, we point out a simplifying observation:


Classes and interfaces behave the same way with respect to contracts.


Contracts specify the behavior of a method that a client can call. It doesImage 1.4.1 not matter how the client knows that the method exists, whether through an interface or through a concrete or abstract class. All that matters is that the client establishes the method’s pre-condition and can expect the method’s post-condition in return. In consequence, we can treat all kinds of subtyping, such as extends and implements for classes and extends for interfaces, simultaneously for the current purposes. To emphasize the commonality, we will speak generically of super-types and subtypes when we mean both interfaces and classes.

The subsequent presentation builds on the practical insights discussed previously and will derive the corresponding formulation from the perspectiveImage 3.1.1 of contracts. We start with the Liskov Substitution Principle, which leads to the concept of contract inheritance. This covers the outside viewImage 3.2.1 of an object and addresses the use of interfaces as abstract specifications of some expected behavior. Then we look at the internal view, which relatesImage 3.1.2 back to defining the interface between a super-class and its subclasses. It involves two aspects: the maintenance of the invariants formulated at different levels of the hierarchy and the contracts of protected methods.

6.4.1 Contracts of Overridden Methods

Image 4.1A method’s contract captures its behavior by specifying the legal calls in theImage 1.4.1 pre-condition and the achieved result in the post-condition. Method overriding on its own can be understood best by considering methods to belong to objects, rather than to classes: Overriding replaces some method entirely with a new implementation, while the object’s clients remain unaware of the substitution. The interaction between these two aspects is clear: The replacement must obey the original contract; otherwise, the new object is not substitutable because it behaves differently and may break the clients’ expectations.


An overriding method inherits the contract of the overridden method.


Image 150,151,89,23This point is really the foundation for treating inheritance in the context of contracts. The conventional term contract inheritance highlights the fact that a subclass inherits from its superclass not only the fields and methods, but also the methods’ specifications. Viewed the other wayImage 3.1.1 around, a behavioral subtype is one that honors the super-type’s contracts. Because of the crucial role of contract inheritance, let us examine this idea a bit more closely.

Suppose a superclass declares a method meth() with pre-conditon Psuper and post-condition Qsuper and publishes this contract to its clients.

inheritance.SuperClass


public class SuperClass {
/**
* PRE Psuper
* POST Qsuper
*/

public int meth(int param) {
...
}
}


Now any client wishing to call that method has to obey the contract. InImage 4.1 other words, it must make sure that Psuper holds before the call and can only assume Qsuper to hold after the call. Its reasoning therefore takes the following shape:

inheritance.DemoClient


public void operation(SuperClass obj) {
...
// Psuper
int res = obj.meth(arg);
// Qsuper
...
}


Now a subclass SubClass might override the method meth(). Because of subtyping, an instance of that class could be passed for obj to the method operation. If the overriding method uses exactly the same contract as the method from the superclass, the client’s reasoning remains valid, and the client code remains correct.

Let us illustrate the point with a tiny standard example. A Cell holds a single value in a field content. It publishes this state in model field content. The pre-condition of both methods get() and set() is true. The post-condition of get() is \return = content, while that of set() is content = \old(c).

inheritance.Cell


public class Cell {
protected int content;
public int get() {
return content;
}
public void set(int c) {
this.content = c;
}
}


The derived class BackupCell extends the behavior by providing a single-slot backup, with field and model field backup. Now the post-condition of set() is content = \old(c) ∧ backup = \old(content).

inheritance.BackupCell


public class BackupCell extends Cell {
private int backup;
public void set(int c) {
backup = content;
super.set(c);
}
public void backup() {
this.content = backup;
}
}


The overridden method set() in particular guarantees the inherited postcondition and therefore honors the inherited contracts. Clients that know a particular object is an instance of the special case BackupCell can also take advantage of the additional knowledge about the backup state.


Overriding methods can weaken the pre-condition and strengthen the postcondition.


The preceding example shows that inherited contracts do not have to be taken as they are. This raises the question of which modifications to the contract are permissible. Let us take a very general view. Suppose the SubClass specifies new pre- and post-conditions Psub and Qsub.

inheritance.SubClass


public class SubClass extends SuperClass {
/**
* PRE Psub
* POST Qsub
*/

public int meth(int param) {
...
}
}


Image 6.1.2To validate the client’s reasoning, we can go back to the idea of stronger and weaker assertions. If Psub is weaker than Psuper, such that the subclass requires less than the superclass, then Psuper implies Psub in all possible program states. Since the client establishes Psuper before the call, it has also established Psub.

Now assume the method in SubClass guarantees to achieve Qsub. As long as Qsub is stronger than Qsuper, meaning the subclass guarantees more than the superclass, it also guarantees Qsuper. In a logical formulation, this could be expressed as

PsuperPsubQsubQsuper

Although this generalization of contract inheritance is logically possible, it seems somewhat irrelevant from a practical perspective: Why should a subclass be content with less if it can get a stronger pre-condition, which means more information that it can work with? Why should it guarantee more than the superclass promises—why should it perform the extra work? The answer is simple: because the new contract captures the subclass’s behavior more naturally.


Subtypes that are special cases do modify the contracts in practice.


A prototypical and small example of such special cases can be found inImage 3.1.5 Image 3.2.3 the JDK’s collection framework. At the base, the interface Collection introduces a method for adding elements.

java.util.Collection


boolean add(E e);


Its documentation states:

Ensures that this collection contains the specified element. Returns true if this collection changed as a result of the call. Returns false if this collection does not permit duplicates and already contains the specified element.

In the derived interface List, the same method is specified as follows:

Appends the specified element to the end of this list.[ ... ] Returns true (as specified by Collection.add(E)).

Both statements are clearly post-conditions, as they describe the methods’ results. The post-condition of the derived method is actually stronger: It augments the assertion “contains” with the guarantee “at the end,” and it does not involve a case distinction, but guarantees to choose the truecase from the super-type’s method.

Similarly, the interface Set states for the same method:

Adds the specified element to this set if it is not already present. [ ... ] If this set already contains the element, the call leaves the set unchanged and returns false.[ ... ] Returns true if this set did not already contain the specified element.

The first sentence is logically the same as the formulation using “ensures” from the super-type. However, the second sentence makes the additional guarantee that the collection will not change if the element is already present. The two statements about the result are, again, equivalent to the original claims, since a Set, according to its documentation, will never contain duplicates.

The documentation of abstract methods hints at the later specialization.Image 7.1 For instance, a Layout in the SWT is responsible for positioning user interface elements. Its abstract method layout is specified as follows:

Lays out the children of the specified composite according to this layout. This method positions and sizes the children of a composite using the layout algorithm encoded by this layout.


Checked exceptions are part of contract inheritance.


Image 6.3Checked exceptions are part of a method’s contract: They announce in advance in which cases the method may not be able to fulfill its promise stated in the post-condition. It is therefore clear that an overriding method may not throw more or different exceptions than the method that it replaces, although it may, of course, throw fewer exceptions or subtypes of the original exceptions. This rule is also enforced by the compiler, in that the throws clause of the subtype must be contained in the throws clause of the super-type.

6.4.2 Invariants and Inheritance

Image 3.1.2In describing typical usage of Java, we have examined the relationship between a base class and its subclasses: Should a base class hide its fields or should it share them with its subclasses? Which of the two should initialize which fields? Is the base class a service provider to the subclass, or is itImage 243(§7.6.3) simply a foundation for building a derived implementation? The insights gained there can be rephrased easily in the language of contracts and invariants,Image 21 where they become more precise and can even be formalized. From a practical perspective, we will gain a snug overview of the earlier discussions and discover new aspects to them. The central point to be observed is this:


Each class chooses and maintains its own invariant about its own fields.


From a technical perspective, inheritance accumulates the fields declared in different classes along the inheritance chain in a single object. Fig. 6.17 shows the case of class C deriving from B, which in turn derives from A. The suggestion of the guideline then is simply to treat the groups of fields, also called class frames in this context, individually. The overall invariant of the entire object is the Boolean conjunction of the three individual invariants: IAIBIC.

Image

Figure 6.17 Invariants and Inheritance

Image 6.1.5The guideline can be justified in several ways. First, we observed earlier that it is complex and error-prone to either weaken or strengthen an existingImage 4.1 Image 4.4 invariant: A stronger invariant requires all public methods suddenly to do more work to maintain it, while a weaker invariant means that all public methods suddenly know less about the object’s fields when they start working. In both cases, the class’s code will need to be revised thoroughly to keep working. It follows for the case of inheritance that a subclass cannot change the invariants of its superclasses, which means that those remain as they were stated in the superclasses. By a switch of perspective, the same argument also explains why a subclass should not be involved in maintaining its superclasses’ invariants: Whenever those invariants changeImage 3.1.11 due to changes in a superclass, such as when its developers discover a more efficient data structure, the code of the subclass is broken.

A second explanation is obtained by starting from the view that a subclass is just a special client of its superclass and that the accesses to thatImage 3.1.2 class should be channeled through a well-defined interface of protected methods. The superclass’s invariant, like every invariant, is private knowledge;Image 4.1 it is a contract of the superclass developers with themselves that no client should be aware of.


Unpack classes along the inheritance chain.


We discovered earlier that it can be useful to make explicit those pointsImage 4.4 Image 6.2.2 where an object’s invariant holds. The intuition was to imagine an object as a package [Fig. 4.10(a) on page 217]: When “packing” the object, the invariant is safely “contained” inside; when “unpacking” the object, we regain that information “stashed away” in the imaginary package.

This idea links nicely with inheritance and the concept of protectedImage 23 interfaces for subclasses (Fig. 6.18). Each class along the inheritance chain only unpacks its own fields, which enables it to work on those fields. This unpacking happens in public methods, as before, or inprotected methods in the context of inheritance. Each use of a superclass’s protected interface unpacks precisely the layer of that class.

Image

Figure 6.18 Unpacking and Packing of Superclass Fields

The unpacking and packing then happens in parallel with the call chain moving up the superclass hierarchy. In consequence, each class becomes responsible for maintaining its own invariants.


protected methods maintain the declaring class’s invariant.


A practical consequence of this explanation is that protected methodsImage 3.1.2 should be treated like public methods with respect to invariants. In otherImage 4.4 words, they can assume the invariant at the beginning and must establish the invariant at the end. The only detail is that “the invariant” refers to an invariant about the current class frame, and implicitly to all those invariants from higher levels in the inheritance chain (Fig. 6.18).

The main challenge and the justification for this structure is that protected methods can be called from any point within the class hierarchy, not only from the subclasses. While many do act as service providers toImage 3.1.4 subclasses, the TEMPLATE METHOD pattern, for instance, explicitly introduces protected methods to be called from the superclass code. A class’s frame must therefore be “in good shape” whenever one of its protected methods is called.


Use private methods for processing steps.


The stronger obligations connected to protected methods also reemphasize the guideline of making mere processing steps, which are intended toImage 1.4.5 Image 1.4.6 be called from within a larger sequence, private. Such private methods can be liberal and flexible with the invariants; they can take their pick ofImage 4.2.3 which parts they assume in the pre-condition and guarantee in their postcondition.


A subclass’s invariants should not reference the inherited fields.


The goal of having each class along the inheritance chain maintain its own invariant can be reached only if those invariants never refer to a superclass’s fields. In the context of invariants and ownership, we have seen thatImage 6.2.2 even such conceptual references, which never occur in the real code, can be problematic. We have also pointed out that they need to be restricted (Fig. 6.4). The same argument applies to invariants of subclasses: As soon as they reference the superclass’s fields, the superclass is no longer free to maintain that invariant in the ways it sees fit and might inadvertently break the subclass’s invariants.

Whenever a subclass invariant does reference a superclass’s field, it is likely that any method modifying that field will need to be overridden in the subclass. To illustrate the point, consider a simple standard example ofImage 185 two versions of a linked list. The size() method in the basic version has to walk the list and therefore is linear in the length of the list.

inheritance.LinkedList


public class LinkedList {
protected class Node {
protected Object data;
protected Node next;
}
protected Node head = null;
public int size() {
... traverse the list starting at head
}
...
}


The following subclass makes the size() function constant time, by adding a cache field size and stating the invariant:

size contains the length of the linked list in head.

Image 1.4.11To maintain that invariant, the subclass also has to extend the behavior of the inherited method add():

inheritance.LinkedListWithSize.add


public void add(int pos, Object elem) {
super.add(pos, elem);
size++;
}



Treat references to superclass model fields as cross-object references.


Such problems are not, unfortunately, restricted to the superclass’s implementation fields, which the subclass should certainly not reference. They also occur with conceptual references to model fields, because those fields always reflect the state of the superclass frame in Fig. 6.17. Any change to the inherited state can modify the model fields derived from that state, so the subclass invariant can be broken even if it relies only on the public model fields.

The remedy is, again, to override superclass methods to adjust the subclass’s fields according to the change. This approach can, however, be understoodImage 6.2.3.5 derstood as a special case of the observer-based maintenance of cross-object invariants: The subclass intercepts all calls to the superclass’s method and thereby receives a “signal” that the method has been called. The code for the linked list with a cached size provides an obvious and small example.

There is, however, one detail that is simpler in the present case. TheImage 6.2.3.5 problem with “looser” invariants was that there were intermittent broken states that were visible to clients (Fig. 6.13) when these were registered as observers as well. When overriding superclass methods to update the subclass fields, in contrast, the control flow stays entirely within the class and clients cannot become aware of the intermediate illegal states. This is,Image 4.1 indeed, only analogous to the principal point that a class usually does break its invariant while it is working.