This chapter presents a complete subsystem that demonstrates all the remaining Gang-of-Four design patterns: a miniature SQL interpreter (and JDBC interface) that you can embed in your applications. This package is not a full-blown database but is a small in-memory database suitable for many client-side applications.

As was the case with the Game of Life game discussed in the previous chapter, I’ve set up a web page at http://www.holub.com/software/holubSQL/ that lists various links to SQL resources and provides an applet that lets you play with the interpreter I’m about to discuss. You can find the most recent version of the source code from this chapter on the same web page.

As was also the case with Life, I’ve opted to present a complete subsystem, so this chapter has a lot of code in it. As before, I don’t expect you to read every line—I’ve called out the important stuff in the text.

With the exception of “The Interpreter Pattern” section, you don’t need to know anything special to read this chapter. That section, which covers how the actual SQL interpreter and the parser that builds it works, is a doozy, though. After a lot of thought, I decided not to turn this chapter into a treatise on compiler writing, simply because the subject rarely comes up in normal programming. Moreover, the Interpreter Pattern section introduces only one design pattern, which is used only to build interpreters. If you’re not going to build an interpreter, you can safely skip it (both the pattern and the section). If you’re bold enough to proceed, however, I’m assuming (in that section only) that you know how write simple SQL statements, you know how to read an LL(1) BNF grammar, and you know how recursive-descent parsing works. The web page I just mentioned has links to SQL and JDBC resources if you need to learn that material, and it also links to a long introduction of formal grammars and recursive-descent parsing.

The Requirements

I originally wrote the small database engine in this chapter to handle the persistence layer for a client-side-only “shrink-wrap” application. My program used only a few tables and did only simple joins, and I didn’t want the size, overhead, and maintenance problems of a “real” database. I also didn’t need full-blown SQL—just a reasonable subset that supports table creation, modification, and simple queries (including joins) was sufficient. I didn’t need views, triggers, functions, and the other niceties of a real database. I did, however, need the tables that comprised the database to be stored in some human-readable ASCII format such as comma-separated values (preferred) or XML, and none of the databases that I could find satisfied this last requirement.

I rolled my own database for other reasons as well. The database needed to be “embedded” into the rest of the program rather than being a stand-alone server. I just didn’t want the hassle of installing (and maintaining) a stand-alone third-party database server that was likely to be an order of magnitude larger than the application itself. I wanted a small, lean implementation.

I wanted to talk to the database using JDBC so that I could replace it with something that was more fully featured if necessary. The database engine had to be written entirely in Java so that it was platform independent.

Finally, several times I’ve wanted to store a small amount of data in a database-like way, but without the overhead of an actual database. For example, it’s handy to put configuration options into a database-like data structure so that you can issue queries against the configuration. Using a database to keep track of ten configuration options was just too much overhead, however. I wanted the data structures that underlie the SQL interpreter to be useable in their own right as a sort of “collection,” but without the SQL.

I checked the web to see if there was anything that would do the job, but I couldn’t find anything at the time, so I rolled up my sleeves and wrote my own. (I’ve subsequently discovered a couple small public-domain SQL interpreters, but that’s life—it took less than two weeks to write the SQL engine you’re about to examine, so I didn’t waste any time.)

The Architecture

I approached the design of my small-database subsystem by breaking it into three distinct layers, each accessed through well-defined interfaces (see Figure 4-1). This use of interfaces to isolate subsystems from each other is a simple reification of the Bridge pattern, which I’ll discuss in greater depth later in the current chapter. The basic idea of Bridge is to separate subsystems with a set of interfaces so you can modify one subsystem without impacting the other.

The data-storage layer manages the actual data that comprises a table and also handles persistence. This layer exposes two interfaces: Table (which defines access to the table itself) and Cursor, which provides an iterator across rows in the table (an object that lets you visit each row of the table in sequence).

The data-storage classes are wrapped in a SQL-engine layer, which implements the SQL interpreter and uses the underlying data-storage classes to manage the actual data. This layer exposes result sets (the set of rows that result from a SQL select operation) as Table objects, and you can examine the result set with a Cursor, so these two interfaces isolate both “faces” of the subsystem. (Like Janus, one face looks backward at the data-storage layer, and the other face looks forward at the JDBC layer.)

Finally, a JDBC-driver layer wraps the SQL engine with classes that implement the various interfaces required by JDBC, so you can access my simple database just like you would any other database. Using the JDBC Bridge also lets you easily replace my simple database with something that’s more fully featured without having to modify your code. The JDBC layer completely hides the underlying Table and Cursor interfaces. (You won’t have to worry about JDBC-related stuff until you get to “The JDBC Layer” section toward the end of this chapter. Everything I discuss up to that point has nothing to do with JDBC. I’ll explain how JDBC works when you get to that section, and when I do get to it, JDBC classes will be clearly indicated by using their fully qualified class names: java.sql.Xxx. If you don’t see the java.sql, then the class is one of mine.)

The messaging between layers is effectively unidirectional. For example, the SQL engine knows about, and send messages to, the data-storage layer, but the data-storage layer knows nothing about the SQL engine and sends no messages to any of the objects that comprise the SQL engine. This one-way communication vastly simplifies maintenance because you know that the effects of a given change are limited. Since these three layers are completely independent of one another, I can also discuss them independently.

Figure 4-1. Database-classes architecture

The Data-Storage Layer

At the core of everything is the Table interface, its implementation (ConcreteTable), and various support classes and interfaces. As I did in the previous chapter, I’ll start with a couple of monstrous figures, which will seem confusing at first but make sense as I discuss the program one bit at a time. Figure 4-2 shows the static structure of the classes that comprise the data-storage layer: the Table interface and all its implementations and supporting classes. Figure 4-3 shows the design patterns. As was the case with Life, there are almost as many patterns as there are classes, which is to say that several classes participate in more than one pattern. You should bookmark these figures so that you can refer to them as I discuss the various patterns.

Figure 4-2. Data-storage layer: static structure

Figure 4-3. Data-storage layer: design patterns

The Table Interface

The Table interface (Listing 4-1) defines the methods you use to talk to a table. I’ve designed the Table so that it (and the underlying implementation) is useful as a data structure in its own right, without needing to wrap it with the SQL-related layers. Sometimes, you just need a searchable table rather than a whole database.

A Table is an in-memory data structure that you can use rather like a Collection. The interface doesn’t extend Collection, however, because a Table is really doing a different thing than a standard Collection—they just both happen to be data structures. There would be no way to implement most of the methods of the Collection interface in the Table. A Table supports the database notion of a column. You can think of a Table as a set of rows, each of which has several columns that are identified by name. It’s like a two-dimensional array, except that it’s searchable and the columns have names, not column indexes. (JDBC lets you specify a column by index, but I don’t do that in my own code, so I haven’t implemented the feature. Index-based access—as compared to named access—has given me grief when I’ve had to add columns to the database and the column indexes have changed as a consequence, so I don’t use them.)

Every cell (the intersection of a column and row) can hold an object. The rows in a Table are not ordered. You find a particular row by searching the table for rows whose columns match certain criteria (which you specify—more in a moment).

Table is an interface, not a class. An interface makes it possible to isolate the parts of the program that use the Table from the parts of the program that implement the Table. I can change everything about the implementation—even the concrete-class name—without any code on the “client” side of the interface changing. The comments in Listing 4-1 describe the various Table operations adequately, and I’ll have more to say about them when I look at the implementations.

The Bridge Pattern

The Table interface is part of the Bridge design pattern mentioned earlier. A Bridge separates subsystems from each other so that they can change independently. Unlike Facade (which you looked at in the previous chapter in the context of the menuing subsystem), a Bridge provides complete isolation between subsystems. Code on one side of the Bridge has no idea what’s on the other side. (Facade, you’ll remember, doesn’t hide the subsystem—it just simplifies access to it.)

I’ll explain Bridge by presenting several examples, shown in Figure 4-4. The top section shows Java’s older AWT subsystem, and though you probably won’t be familiar with it unless you’re doing something such as PalmPilot programming, the architecture is a nice reification of the classic Gang-of-Four Bridge. The “client” classes (the ones that use java.awt.Window) can change completely without impacting the implementation of AWT. By the same token, the classes on the other side of the bridge (various “peer” classes that interface to the operating system’s GUI layer) can change without impacting the client classes. AWT leverages this ability to change in order to make the GUI model platform independent, so your PalmPilot application’s UI may well run on Windows, Linux, or some other operating system without modification.

The peer classes (the classes that implement the xxxPeer interfaces) are created at runtime using an Abstract Factory called java.awt.Toolkit. (Abstract Factory was discussed in Chapter 2, but to refresh your memory, a Collection is an Abstract Factory of Iterator objects. A Concrete Factory [ArrayList, for example] implements the Abstract-Factory interface to produce a Concrete Products [some implementation of Iterator whose class is unknown]. Other implementations of Collection may [or may not—you don’t know or care] produce different Concrete Products that implement the same Iterator interface in a way that makes sense for that particular data structure.) Toolkit is an abstract class used as an interface. (It has to be abstract because it needs to contain a static method.) The Singleton pattern is used to fetch a concrete instance of the Toolkit “interface.” That is, the Toolkit.getDefaultToolkit() method determines the operating environment at runtime (typically, by looking at a system property) and then instantiates a Toolkit implementer appropriate for that environment. I’ve shown the Windows and Motif variants in Figure 4-4, but a Toolkit implementation must exist for every environment on which a particular JVM runs.

The concrete Toolkit object acts as an Abstract Factory of “peer” objects. The peers are system-dependent implementers of various graphical objects. I’ve shown one such peer (the WindowPeer, which implements an unbordered stand-alone window) in Figure 4-4, but 27 peer interfaces exist and create the whole panoply of graphical objects (ButtonPeer, CanvasPeer, CheckboxPeer, and so on). For each of these interfaces, a system-dependent implementation exists that’s manufactured by the system-dependent concrete Toolkit in response to one of its createxxx(...) methods. For example, the Windows Toolkit (sun.awt.windows.WToolkit) will produce a Windows-specific peer (sun.awt.windows.WWindowPeer) when you call Toolkit. createWindow(). The Motif Toolkit (sun.awt.windows.MToolkit) will produce a Motif-specific peer (sun.awt.motif.MWindowPeer) when you call Toolkit.createWindow().

The Abstract Factory I’ve just described is used in concert with the Bridge pattern to isolate the mechanics of switching subsystems. The java.awt.Window class understands Toolkits and peers. When you create a Window, that object creates the appropriate peer. As long as you program in terms of Window objects, you don’t need to know that the peer exists. Consequently, everything on the other side of the bridge (all the peers) can change radically, even at runtime, without your program’s side of the bridge being impacted. By the same token, none of the peer implementations knows or cares how they’re used. Consequently, your program can change radically without the peer implementations knowing or caring.

It is commonplace for Abstract Factory and Bridge to be used together in the way I just described. You will rarely see a Bridge without an Abstract Factory helping to create the Concrete Implementor objects (for example, WWindowPeer and MWindowPeer).

Another example of Singleton, Abstract Factory, and Bridge working together includes the java.text.NumberFormat class, which is used to parse and print numbers in a Locale-specific way. When you call NumberFormat.getInstance(), you’re using Singleton to access an Abstract Factory that creates some subclass of NumberFormat that understands the current Locale. The NumberFormat “interface” serves as a Bridge that isolates your program from the rather complicated subsystem that deals with Locale-specific formatting. That subsystem could change (to support new Locales, for example), and your code wouldn’t know it.

Now let’s apply the notion of Bridge to the current problem. Referring again to Figure 4-4, the Table uses an Abstract-Factory/Bridge strategy much like AWT and NumberFormat, but things are simplified a bit. I’ll cover the Abstract-Factory issues in the next section, but the figure shows a small bridge consisting of the Database class (the core of the SQL engine, which I’ll describe shortly) and the Table interface. If you program in terms of Database objects, you don’t know or care that the Table exists. It’s possible, then, to completely change the underlying table implementation—even at runtime—without your code caring about the change. For example, at some future date I may introduce several kinds of Tables that store the underlying data in a way that’s particularly efficient for a particular data set. The Bridge, however, isolates your code from that change.

I’ll come back to Bridge (and to the third part of Figure 4-4) later in this chapter.

Creating a Table, Abstract Factory

Now let’s look at the Abstract-Factory component of the Table creation process. The following code creates a Table named people whose rows have three columns named last, first, and addrID (for address identifier—not a particularly readable name, but short column names are good because they improve search times):

You can also create a table from data stored on the disk in comma-separated-value (CSV) format. The following call reads a table called address (which must be stored in a file named address) from the specified directory:

The data is stored in CSV format, where every row of the table is on its own line and commas separate the column values from each other. Here’s a short sample:

The first line is the table name, the second line names the columns, and the remaining lines specify the rows.

Figure 4-4. The Bridge Pattern in AWT, com.holub.database, and JDBC

The TableFactory demonstrates the reification of Abstract Factory that I’ve used most often. Unlike the classic reification (as embodied by Collection and Iterator), there’s no interface in the Abstract Factory role of which Collection is an example. (More precisely, the TableFactory class serves as its own interface, as if Collection were an actual class, not an interface). You just have no need to complicate the code with a separate interface. What makes this reification an Abstract Factory is that it satisfies the same “intent” as a classic Abstract Factory: It provides a means of “creating families of related or dependant objects without specifying their concrete classes,” to quote the Gang of Four. TableFactory is another example of how reifications of a particular pattern can differ in form.

This particular Factory creates Table implementers, of which only one is currently present—the ConcreteTable, which I’ll discuss in subsequent sections. This particular reification of Abstract Factory is in some ways just the skeleton of a pattern, put in place primarily so that I can provide alternative Table implementations in the future. That is, this particular Factory isn’t producing a “family” of objects right now but is put into the code to make it easy to increase the size of the “family” to some number greater than 1 if the need arises. Putting a small factory into the code up front has virtually no cost but provides for a lot of down-the-line flexibility, so the potential payback is high. On the other hand, the Factory does add a small amount of extra complexity to the code.

The TableFactory source code is in Listing 4-2. For the most part, its methods do nothing but hide calls to new. The load()method (Listing 4-2, line 57) is interesting in that the method can potentially load a table from various file formats on the disk. I’ll explain the code in the load() method in greater depth in the next section, but let’s look now at what the method does rather than how it does it.

The load() method is passed a filename and location, and it creates a Table from the data it finds in that file. Right now, it examines the filename extension to determine the data format, but it could just as easily examine the contents of the file. It’s a trivial matter to make it load from an XML file rather than a CSV file, for example. It could even be passed a .sql file and load the Table by using the SQL. In other words, the method potentially isolates you completely from the underlying data format. The file read by the load() method may also specify a particular type of Table that could represent the data in a more efficient way than the current Table implementation, and the Factory could produce that specific Concrete Product. Since load() hides the complexity of creating a table, you can also think of TableFactory as a simple Facade |reification.

Creating and Saving a Table: Passive Iterators and Builder

Now let’s move onto the ConcreteTable implementation of Table. You can bring tables into existence in two ways. A run-of-the-mill constructor is passed a table name and an array of strings that define the column names. Here’s an example:

The sources for ConcreteTable up to and including this constructor definition are in Listing 4-3. The ConcreteTable represents the table as a list of arrays of Object (rowSet, line 32). The columnNames array (line 33) is an array of Strings that both define the column names and organize the Object arrays that comprise the rows. A one-to-one relationship exists between the index of a column name in the columnNames table and the index of the associated data in one of the rowSet arrays. If you find the column name X at columnNames[i], then you can find the associated data for column X at the ith position in one of these Object arrays.

The private indexOf method on line 49 is used internally to do this column-name-to-index mapping. It’s passed a column name and returns the associated index.

Note that everything is 0 indexed, which is intuitive to a Java programmer. Unfortunately, SQL is 1 indexed, so you have to be careful if you implement any of the SQL methods that specify column data using indexes. I’ve taken the coward’s way out and have not implemented any of the index-based JDBC methods. Be careful of off-by-one errors if you add these methods to my implementation.

Of the other fields at the top of the class definition, tableName does the obvious, and isDirty is true if the table has been modified. (I use this field to avoid unnecessary writes to disk). I’ll discuss transactionStack soon, when I discuss transaction processing.

The second constructor (shown in Listing 4-4) is more interesting. Here, the constructor is passed an object that implements the Table.Importer interface, defined on line 198 of Listing 4-1. The constructor uses the Importer to import data into an empty table. The source code is in Listing 4-4 (p. 196). As you can see, the constructor just calls the various methods of the Importer in sequence to get table metadata (the table name, column names, and so forth). It then calls loadRow() multiple times to load the rows.

Each call to loadRow() returns a standard java.util.Iterator, which iterates across the data representing a single row in left-to-right order. By using an iterator (rather than an array), I’ve isolated myself completely from the way that the row data is stored internally. The Iterator returned from the Importer could even synthesize the data internally.

The load process finishes up with a call to done().

The CSVImporter class (Listing 4-5) demonstrates how to build an Importer. The following code shows a simplified version of how the TableFactory, discussed earlier, uses the CSVImporter to load a CSV file. The importer is created in the constructor call on the second line of the method. It’s passed a Reader to use for input. The ConcreteTable constructor then calls the various methods of the CSVImporter to initialize the table.

As you can see in Listing 4-5, there’s not that much to building an importer. The startTable() method reads the table name first, and then it reads the metadata (the column names) from the second line and splits them into an array of String objects. The loadRow() method then reads the rows and then splits them. I’ll discuss the ArrayIterator class called on line 30 in a moment.

A more interesting importer is in Listing 4-6. The PeopleImporter loads a Table using the interactive UI pictured in Figure 4-5. You create a table that initializes itself interactively as follows:

My main intent is to illustrate the techniques used, so this class isn’t really production quality, but it demonstrates an effective way to separate a UI from the “business object.” I can completely change the structure of the user interface by changing the definition of the PeopleImporter. The Table implementation is completely unaffected by changes to the UI. In fact, the Table doesn’t even know that it’s being initialized from an interactive user interface.

Looking at the implementation, the getRowDataFromUser() method (Listing 4-6, line 46) creates the user interface, and the button handlers at the bottom of the method transfer the row data from the text-input fields to the rows LinkedList (declared on line 19). The balance of the class works much like the CSVImporter, but it transfers data from the rows array to the Table.

Figure 4-5. The PeopleImporter user interface

The other method of interest in Listing 4-4 is the export() method, which exports the table data similarly to the way the constructor imports the data. The export() method takes a Table.Exporter argument and sends the Exporter the metadata and the rows. (The Exporter interface is also an inner class of Table, defined on line 175 of Listing 4-1.)

As with the Importer constructor, the export() method first asks the Exporter to store the table metadata, and then it passes the Exporter the rows one at a time. As was the case with the Importer constructor, the export() method passes the Exporter a java.util.Iterator across the columns of a row rather than passing an Object array. This way, the Table implementor is not tied into a particular representation of the underlying data. (The ConcreteTable, for example, isn’t giving away the fact that it stores rows as Object arrays.)

The CSVExporter class in Listing 4-7 demonstrates how to build an Exporter. It’s passed a Writer and just writes the table data to that stream.

A more interesting example of an exporter is the JTableExporter in Listing 4-8, which builds the UI in Figure 4-6. The code that created the UI in the Test class is at the bottom of Listing 4-8 (line 45), but here’s the essential stuff:

You pass the Table’s export() method a JTableExporter() rather than a CSVExporter(). The JTableExporter() creates a JTable and populates it from the table data. You then extract the JTable from the exporter with the getJTable() call. (This “get” method is not really an accessor since the whole point of the JTableExporter is to create a JTable—I’m not giving away any surprising implementation details here.)

Figure 4-6. The JTableExporter user interface

The import/export code you’ve just been looking at is an example of the Builder design pattern. The basic idea of Builder is separate the code that creates an object from the object’s internal representation so that the same construction process can be used to create different sorts of representations. Put another way, Builder separates a “business object” (an object that models some domain-level abstraction) from implementation-specific details such as how to display that business object on the screen or put it in a database. Using Builder, a domain-level object can create multiple representations of itself without having to be rewritten. The business object has the role of Director in the pattern, and objects in the role of Concrete-Builder (which implement the Builder interface) create the representation. In the current example, ConcreteTable is the Director, Table.Exporter is the Builder, and CSVExporter is the Concrete Builder.

To my mind Table.Importer is also a Builder (of Table objects) and CSVImporter is the matching Concrete Builder, though this way of looking at things is rather backward since I’m turning multiple representations into a single object rather than the other way around. The implementation is certainly similar, however.

As you saw in the PeopleImporter and JTableExporter classes, Builder nicely solves the object-oriented UI conundrum mentioned way back in Chapter 2. If an object can’t expose implementation details (so you can’t have getter and setter methods), then how do you create a user interface, particularly if an object has to represent itself in different ways to different subsystems? An object could have a method that returns a JComponent representation of itself or of some attribute of itself, but what if you’re building a server-side UI and you need an HTML representation? What if you’re talking to a database and you need an XML or SQL representation? Adding a billion methods to the class, one for each possible representation (getXML(), getJComponent(), getSQL(), getHTML(), and so on) isn’t a viable solution—it’s too much of a maintenance hassle to go into the class definition every time a new business requirement needs a new representation..

As you just saw, however, a Builder is perfectly able to accommodate disparate representations, and adding a new Builder doesn’t require any modifications to the domain-level object at all. Any Table can be represented as a CSV list and also as a JComponent, all without having to modify the Table implementation. In fact, Builder provides a nice way to concentrate all the UI logic in a single place (the Concrete Builder) and to separate the UI logic from the “business logic” (all of which is in the Director).

Using Builder lets me support representations that don’t need to exist when the program is first written. Adding XMLImporter and XMLExporter implementations of Table.Importer and Table.Exporter is an easy matter. Once I create these new classes, a Table can now store itself in XML format and load itself from an XML file. Moreover, I’ve added XML export/import to every Table implementation (all of which have to be Directors), not just ConcreteTable.

The only difficulty with Builder is in the design of the Builder interface itself. This interface has to have methods that accommodate all displayable state information. Consequently, a tight coupling relationship exists between the objects in the Director and Builder roles, simply because the Builder interface has to have methods that are “tuned” for use by the Director. It’s possible that the Director could change in such a way that you would have to modify the Builder interface (and all the Concrete Builders, too) to accommodate the change. This problem is really the getter problem I discussed in Chapter 1. Builder, however, restricts the scope of the problem to a small number of classes (the Concrete Builders). I’d have a much worse situation if I were to put get/set methods in the Director (the Table). Unknown coupling relationships with random classes would be scattered all over the program. In any event, I haven’t often needed to make those sorts of changes in practice.

Populating the Table

The next order of business is to put some data into the table. Several methods are provided for this purpose. The simplest method, shown below, inserts a new row into the table. It’s up to you to assure that the order of array elements matches the order of columns specified when the table was created.

The foregoing method is delicate—it depends on a particular column ordering to work correctly. It’s too easy to get the column ordering wrong. A second overload of insert(...) solves the problem by requiring both column names and their contents. The columns don’t have to be in declaration order, but the two arrays much match. When firstArgument[i] specifies a column, secondArgument[i] must specify that column’s contents. Here’s an example:

Also, Collection versions of both methods exist. The following code creates a row from the Collection elements:

The following codes does the same thing, but with rows specified in an arbitrary order:

This last method seems to be of dubious value, but it turns out that a two-collection variant is quite useful when building the SQL interpreter, as you’ll see later in the chapter.

Finally, I’ve provided a Map version where the keys are the column names and the values are the contents.

The source code for the methods that insert rows is in Listing 4-9. The overloads that don’t take column-name arguments just add a new object array to the rowSet. The other methods go through the column names in sequence, determine the index in the object array associated with that column (using indexOf(...)), and put the appropriate data into the appropriate element of the Object array that represents the row.

The actual inserting of the object array into the list representing the table is done by the doInsert() method (Listing 4-9, line 148). I’ll come back to the registerInsert(...) method that’s called at the top of doInsert() in a moment, when I talk about the undo system. For now, note that all insert operations mark the table as “dirty.” This boolean is initially false; it’s marked true by all operations that modify the table, and it’s reset to false by the export() method discussed earlier. A client class can determine the “dirty” state of the table by calling someTable.isDirty(). The SQL-engine layer uses this mechanism to avoid flushing to disk tables that have been read, but not modified, when you issue a SQL DUMP request.

The isDirty() method, by the way, is not a “get” method of the sort I was railing against in Chapter 1, even though it’s implemented in the simplest possible way to return a private field:

The fact that the “dirty” state is stored in a boolean, and that isDirty() returns that boolean, is just an implementation convenience. I’m not exposing any implementation details (there’s no way that the client can determine how the table decides whether it’s dirty), and since there’s no setDirty(), there’s no way for the “dirty” state to be corrupted from outside. I can change the implementation and represent the “dirty” state in some other way without impacting the interface or the classes that use the interface.

If you find this explanation confusing, think about the design process. I decided at design time that a “dirty” state was necessary, so I provided an isDirty() method in the interface. Later, I added the simplest implementation possible. This way of working is fundamentally different from starting with a isDirty field in the class and then adding getDirty() and setDirty() as a matter of course. It would be a serious error for a setDirty() method to exist because, where that method present, a client object could break a Table object by making the Table think it didn’t need to be flushed to disk when it actually did; setDirty() has no valid use.

Examining a Table: The Iterator Pattern

Now that you’ve populated the table, you may want to examine it. The design pattern is Iterator, of which Java’s java.util.Iterator class is a familiar reification. The basic idea is that Iterator provides a way to access the elements of some aggregate object (some data structure) without exposing the internal representation of the aggregate. Java’s Iterator is just one way to accomplish this end. Any reification that you invent that lets a client object examine an aggregate one element at a time is a reification of Iterator.

Another simple reification of Iterator is the ArrayIterator class, shown in Listing 4-10. This class just wraps an array with a class that implements the java.util.Iterator interface, so you can pass arrays to methods that take Iterator arguments. The ArrayIterator is also an example of the Adapter design pattern that I’ll discuss later. ArrayIterator adapts an array object to implement an interface that an array doesn’t normally implement.

Though most iterators don’t give you control over the order of traversal (the ArrayIterator just goes through the array elements in order), no requirement exists that an iterator visit nodes in any particular order. A ReverseArrayIterator could traverse from high to low indexes, for example. A tree class may have inOrderIterator(), preOrderIterator(), and postOrderIterator() methods, all of which returned objects that implemented the Iterator interface, but those objects would traverse the tree nodes “in order,” root first or depth first. You can define an iterator to handle whatever ordering you like—even random ordering is okay—as long as the ordering is specified in the class contract. Some iterators—such as the tree iterators just discussed—may make requirements on the underlying data structure, however.

Iterators can also modify the underlying data structure. Some of the java.util.Iterator implementers support a remove() operation that lets you remove the current element from the underlying data structure, for example.

Iterator is used all over the ConcreteTable, but most important, it’s used to examine or modify the rows. Listing 4-11 defines the Cursor interface used by the Table, but let’s look at how it’s used before looking at the code. The following method prints all the rows of the Table passed into the method as an argument:

The Cursor knows about columns, so you could print only the first- and last-name fields of some Table as follows:

A Cursor can also update the contents of a row or delete the current row. (You actually modify the underlying table when you use these methods.) The following code changes the names of all people named Smith to Jones. It also deletes all rows representing people named Doe:

This functionality works properly with the transaction system that I’ll discuss later in the chapter, so you can roll back modifications if necessary.

The comments in Listing 4-11 describe the remainder of the methods in the interface adequately, so let’s move onto the implementation in Listing 4-12.

Cursors are extracted from a Table using a classic Gang-of-Four Abstract Factory. The Table interface defines an Abstract Cursor Factory; the ConcreteTable, which implements that interface, is the Concrete Factory; the Cursor interface defines the Abstract Product; the Concrete Product an instance of the Results class on line 161 of Listing 4-12. As you saw in the earlier examples, you get a Cursor by calling rows() (Listing 4-12, line 157), which just instantiates and returns a Results object.

Looking at the implementation, the Results object traverses the List of rows using a standard java.util.Iterator. The advance() method on line 169 of Listing 4-12 just delegates to the Iterator, for example.

The interesting methods are update() and delete(), at the end of the listing. Other than do what their names imply, both methods set the table’s “dirty” flag to indicate that something has changed. They also register the operation with the transaction-processing system (described on p. 226) by calling registerUpdate() or registerDelete().

Passive Iterators

The iterators we’ve been looking at are called external (or active) iterators because they’re separate objects from the data structure they’re traversing.

The storeRow() method of the Builder discussed in the previous section is an example of another sort of Iterator. Rather than creating an iterator object that’s external to the data structure, the export() method effectively implements the traversal mechanism inside the data-structure class (the ConcreteTable). The export() method iterates by calling the Exporter’s storeRow() method multiple times. We’re still visiting every node in turn, so this is still the Iterator pattern, but things are now inside out.

This kind of iterator is known as an internal (or passive) iterator. The idea of a passive iterator is that you provide some data structure with a Command object, one method of which is called repetitively (once for each node) and is passed the “current” node.

Passive iterators are quite useful when the data structure is inherently difficult to traverse. Consider the case of a simple binary tree such as the one shown in Listing 4-13. A passive iterator is a simple recursive function, easy to write. The traverseInOrder method (Listing 4-13, line 31) demonstrates a passive iterator. This textbook recursive-traversal algorithm just passes each node to the Examiner object (declared just above this method, on line 23) in turn. You could print all the nodes of a tree like this:

Now consider the implementation of an active (external) iterator across a tree. The Tree class’s iterator() method (line 49) returns a standard java.util.Iterator that visits every node of the tree in order. My main point in showing you this code is to show you how opaque this code is. The algorithm is short but difficult to both understand and write. (In essence, I use a stack to keep track of parent nodes as I traverse the tree.)

I’m not really done with the Iterator pattern because I haven’t discussed the problems that iterators can cause in mulithreading situations, so I’ll come back to them later in the current chapter. For now, I want to move onto the transaction-support subsystem.

Implementing Transactions (Undo) with the Command Pattern

The next interesting chunk of the ConcreteTable class is the “undo” subsystem that you need to support transactions. The design pattern here is the lowly Command pattern I discussed in Chapter 1. To refresh your memory, a Command object encapsulates knowledge of how to do some unspecified operation. For you C/C++ programmers, it’s the object-oriented equivalent of a “function pointer,” but rather than passing around a function that does something, you pass around an object who knows how to do it. The simplest reification of Command is Java’s Runnable class, which encapsulates knowledge of what to do on a thread. You create a Command object like this:

and then pass it to a Thread object:

You then start up the thread like this:

and the controller asks the Command object to do whatever it does by calling run().

That last statement is key to differentiating the Command pattern from some of the other design patterns that use Command objects (such as Strategy, discussed in Chapter 1 and later in this chapter). In Command, the Invoker (the Thread object) doesn’t actually know what the Concrete Command object (backgroundTask) is going to do.

One of the more interesting uses of the Command pattern is in implementing an undo system. Since I use the Table to implement a database, it must be possible to roll back a transaction at the Table level. (JDBC doesn’t actually require transactions, but I do.) Put another way, a modification to the Table may require several operations (inserts, updates, and so on), any one of which could fail for some reason. This group of logically connected operations forms a single transaction, and if any operation in the transaction fails, they all should fail. If you perform the first two operations of a transaction, for example, and the third operation then fails, then you must be able to undo the effect of the first two operations. This undo to the beginning of the transaction is called a rollback.

The complementary notion to a rollback is a commit. Once a transaction is committed, it becomes permanent. You can’t roll it back anymore. Formally, once you begin a transaction, you can terminate the transaction by issuing a rollback request (which puts the table back into the state it was in when you issued the begin), or you commit the transaction.

The situation is made only marginally more complicated by the notion of nested transactions. Consider the following SQL:

The rollback causes the operations in Operation-group B to be ignored, so the result of the foregoing is to perform the operations in group A and C, but not B. On the other hand, the following SQL does nothing at all since the outermost transaction is rolled back:

Transaction processing can get a lot more complicated than what I’ve just described, but since my database is built on a single-user, single-process model and I’m doing only simple things with it, the transaction system I just described is adequate, so I won’t go further into the topic.

One way to implement commit/rollback is to take a snapshot of the entire table every time you begin a transaction. A rollback restores the previous state from the snapshot. A commit just throws away the snapshot. You can implement nested transactions using a snapshot strategy by pushing a snapshot of the Table onto a stack every time you issue a BEGIN statement. You roll back by restoring the table to whatever state was remembered in the snapshot at the top of the stack. You commit a transaction simply by throwing away the snapshot at the top of the stack.

The main problem with a snapshot strategy for undo is that it’s too inefficient in both time and memory. The other commonplace problem with snapshots (not really an issue here but often an issue in other applications) is that an operation may have side effects, and simply restoring an object or objects to a previous state doesn’t undo the side effects. For example, consider an operation that both changes the internal state of the program but also modifies a database. The matching undo must not only put the program back into its original state, but also put the database back into its original state. A snapshot does only the former.

To your rescue comes a more sophisticated use of the Command pattern than the one I used earlier. I define an interface that a Table can use to request an undo operation (the Undo interface on line 224 of Listing 4-14). I then implement that interface with three separate classes (UndoInsert, UndoDelete, and UndoUpdate on lines 228, 238, and 248 of Listing 4-14). Taking UndoInsert as characteristic, you pass its constructor a reference to the inserted row. When the Table passes an execute() message to this object, it removes that row from the List that represents the table. The Invoker (the ConcreteTable object) doesn’t actually know or care what the Concrete-Command objects (the Undo implementers) actually do, as long as the undo something.

Now that I’ve defined the Command objects, I need to organize them. The Undo stack was defined at the top of the class definition (Listing 4-3, line 37, previously) as follows:

The stack is actually a stack of lists, one list for each transaction level. Consider the following calls (which I’ve indented to show the transaction nesting).

Transactioning is disabled until you issue the outermost begin() call: All operations are effectively committed when executed, and the transactionStack() is empty. Issuing a begin causes an empty list to be pushed onto the stack, and every insert, delete, or update operation will add a corresponding Undo object to the list at top of stack. The transactionStack will look like this just before the commit() on line 9, previously, is issued:

The four objects on the stack are instances of UndoInsert that remember the rows that they inserted. If a rollback() had been issued instead of the commit() on line 9, previously, the ConcreteTable would traverse the list of Undo objects at top of stack, asking each one to execute(), thereby undoing the operation. The list at top of stack is then discarded (so the A and B nodes are still on the stack). The commit() on line 9 doesn’t execute anything, however. Rather, the ConcreteStack concatenates the operations in the list at the top of stack to the list just under it on the stack. After the first commit(), the transactionStack looks like this:

Again, if you issued a rollback at this juncture, the system would traverse the entire list asking each undo object to execute() and then discarding the list. Since this is a commit operation, though, the undo system just discards the list at the top of stack.

The implementation of this system starts on line 265 of Listing 4-14. The begin() method pushes a new list onto the stack. The register methods create the proper sort of undo object and add them to the end of the list at the top of stack. (Note that nothing is added if the stack is empty, because no begin has been issued in that case.) Finally, commit(...) and rollback(...) modify the list and execute Undo objects, as described previously.

Modifying a Table: The Strategy Pattern

Once you’ve built a table, you may want to change it. As you saw earlier, you can use a Cursor for this purpose, but that’s sometimes inconvenient. Consequently, two methods are provided to do updates and deletes without using a Cursor explicitly.

By way of demonstration, the following code deletes everyone named Flintstone from the people table:

The design pattern here is Strategy—introduced in Chapter 2. Pass into the Table an object that knows how to select rows: a Selector (that encapsulates a selection strategy). The delete method calls the Strategy object’s approve() method as many times as there are rows, and approve() must return true if that row should be deleted. The one complication is that approve() is passed an array of Table objects rather than a single Table reference. In the current example, the array has only one Table in it, but you will see situations in a moment where that is not the case.

Update operations are done more-or-less like deletes, but you have to override a modify() method as well as the approve(...) method of the Selector. The following code moves everyone who lives in Arizona to California; it examines the entire “address” table and changes all rows whose “state” columns have the value “AZ” to “CA”: The modify(...) method is passed a cursor that’s prepositioned at the current row, and it updates the row through the cursor.

Astute readers (that’s you, I’m sure) will notice that I extended Selector.Adapter in the earlier example, and I implemented the Selector interface directly in the latter example. Selector.Adapter implements Selector by providing default implementations of its two methods: approve() and modify(). This is the same naming and implementation strategy that’s used by the AWT/Swing event model, which provides default implementations of the listener interfaces. (MouseAdapter implements MouseListener, for example.) This naming convention is unfortunate in that we’re not reifying the Adapter design pattern, in spite of the class name. Don’t get confused.

This code also demonstrates the passive (or internal) variant of the Iterator pattern that I discussed earlier. The approve(...) method of the Selector object is called for every row of the table. Since the traversal algorithm is in the Table, Selector is a passive iterator across Table objects. (I haven’t shown this use of Iterator in Figure 4-2, only because there wasn’t enough room to cram it in.)

The Selector interface is in Listing 4-15. The Selector.Adapter is declared as a static inner class of Selector (on line 49 of Listing 4-15). It approves everything and complains with an exception toss if it’s used in an update() call. From a design point of view, I wrestled with the throw-an-exception strategy that I ended up using. As I mentioned earlier, I really dislike the notion of unsupported operations throwing exceptions because this structure effectively moves a compile-time error into runtime. The alternative was splitting the interface into two single-method interfaces, but I didn’t like this solution any better because it complicates an otherwise trivial system. I wouldn’t argue with you if you said that I made the wrong decision, however.

An instance of Selector.Adapter called ALL is declared at the end of the listing. This instance is used primarily in the “select” operations discussed in the following section, but you could use it as follows to delete all the rows of a table:

The implementations of update(...) and delete(...) are in Listing 4-16. All that these methods do is hide the iteration code and call the Strategy object’s methods where appropriate.

Selection and Joins

The final significant ability of Table is to do a SQL-like “select/join” operation. A simple select extracts from one table only those rows that satisfy some criterion. For example, the following code extracts from the people table those rows whose “lastName” column contains the value “Flintstone” (In SQL: SELECT * FROM people WHERE lastName="Flintstone"):

The select() method returns a Table (typically called a result set) that contains only the selected rows. This table differs from one you may declare in that it’s “unmodifiable.” Attempts to modify it result in an exception toss. You can make the table modifiable like this:

I’ll explain this code further in a moment.

You can also get a result set that contains only specified columns of the selected rows. The following code extracts all people whose last name is Flintstone but includes only the first- and last-name columns in the result set (in SQL: SELECT first,last FROM people WHERE lastName="Flintstone"):

Create a result set that contains selected columns of every row like this:

Finally, the following variant lets you specify the desired columns in a Collection rather than an array:

Though selection is useful in and of itself, an even more powerful variant on selection is a “join” operation. The basic idea is to select simultaneously from multiple tables. The word join comes from the notion that you’re joining multiple tables together to make one big virtual table and then selecting a row from that virtual table. It’s well beyond the scope of this book to describe why joins are useful, but for those of you who know a little database stuff, this SQL

is performed as follows:

The array of Cursor objects passed into approve() is ordered identically to the array of Table objects that you pass into select(...).

Every possible combination of rows from the two tables is considered when the result set is built. (Formally, a result table holding every combination of rows from a set of source tables is said to be the Cartesian product of the source tables.) Given one table with the rows A, B, and C and a second table with the rows D and E, the following calls to approve() are made (where A, B, C, D, and E) are cursors positioned at the appropriate rows:

You can join any number of tables, but bear in mind that every time you add a table, you multiply the amount of work by the number of rows in the added table. (Joining two 5-row tables requires 25 calls to approve() [5×5]; joining three, 5-row tables requires 125 [5×5×5] approvals.) In a real database, you can do some clever work to reduce this overhead, but the number of tables always significantly increases the cost of the join operation.

An overload of this method lets you use Collection objects rather than arrays for the columns and tables arguments.

Listing 4-17 shows the code that implements the various select() overloads. From a design-pattern perspective, there’s nothing interesting here. The select() overloads are just additional reifications of Strategy. From a programming perspective, the selectFromCartesian-Product(...) method on line 437 is worth examining. This is the method that does the actual join. It uses a recursive algorithm to assemble arrays of cursors representing each row of the Cartesian product and then passes that array off to your approve() method. The code is elegant (if I do say so myself), but the recursion makes it somewhat opaque.

Miscellany

The remainder of the ConcreteTable definition is in Listing 4-18. It contains a few housekeeping and workhorse methods (such as toString(), which returns a String representation of all the elements in the table). Listing 4-18 ends with a long unit-test class that has several examples of the calls I’ve been discussing. I like to put my unit tests into inner classes (which I always call Test) so that the test code will be in a separate .class file than the class I’m testing. I don’t ship the test-class files with the product. Run the test using this:

(but omit the backslash if you’re testing from a Windows “DOS box”). Normally, I like test classes such as this to print nothing at all if everything’s okay, and I like to report the number of errors as the test-program’s exit status. This way, I can automate the tests easily, and the result of running the test is a list of what went wrong. If you print too many “this is okay” messages, you’ll lose the error messages in the clutter.

The problem with this approach is that the inner-class unit test has access to parts of the class that a normal “client” wouldn’t be able to see. I am careful, when I use this unit-test strategy, to pretend that I do not have this special access. Of course, you can guarantee that you don’t have access by putting your tests in a separate class in a separate package, but then the test code is in a different directory and is harder to augment if you change the interface to the class.

Having said all that, I haven’t followed my usual testing guidelines in the current situation. I test by redirecting the output of the program to a file and then using the Unix diff utility to compare that output with an expected-output file. I test the class by running the following shell script, which prints the words PASSED or FAILED, depending on whether the actual output matches the expected output:

It’s ugly, but it works.

Variants on the Table: The Decorator Pattern

If you look back at the various select() overrides in Listing 4-17, you’ll notice that they all take the following form:

They create a ConcreteTable, populate it, and then return an UnmodifiableTable that wraps the actual result table. Listing 4-19 shows the UnmodifiableTable class. As you can see, its methods are divided into two categories. The methods that can modify a Table (insert(), update(), delete()) all do nothing but throw an exception if called. The remainder of the methods just delegate to the wrapped table. Finally, the UnmodifiableTable adds an extract() method (Listing 4-19, line 88) that just returns the wrapped Table. (As it says in the comment preceding the method, this last method is somewhat problematic because it provides a way to get around the unmodifiability, but the SQL-engine layer requires it to implement the SELECT INTO request efficiently.)

What I’ve done with UnmodifiableTable is used a wrapping strategy to do something that I could also have done using inheritance. My goal was to change the behavior of several of the methods of ConcreteTable so that the Table was effectively immutable. I was reluctant to put an isImmutable flag into the ConcreteTable and test the flag all over the place—that solution was just too complicated. I could also have derived a class and overridden the methods that modified the table to throw an exception, but that solution introduces a fragile-base scenario. (I could inadvertently add a method to the superclass that modified the table and forget to override that method in the subclass.) Finally, the derivation solution leaves open the potential for hard-to-maintain code that reports errors at runtime that should really be compile-time errors. (If I try to assign a Table to an UnmodifiableTable reference, I’ll get a compile-time error.)

I solved the problem by replacing implementation inheritance with an interface-inheritance/delegation strategy. I implement the same interface as the object that I’m wrapping (the object that would otherwise be the superclass) and delegate to the wrapped object when necessary.

This solution to the fragile-base-class problem, which allows me to change behavior without using extends, is an example of the Decorator pattern.

You’ve seen decorators if you’ve used Java’s I/O classes. For example, if you need to read a compressed stream of bytes efficiently, you use a chain of decorators. Here, Decorator reduces a complex task to a set of simple tasks, each of which is implemented independently. You could implement a massive efficiently-read-a-compressed-stream class, but it’s easier to break the problem into the following three distinct subproblems:

1. Reading bytes.
2. Making reads more efficient with buffering.
3. Decompressing a stream of bytes.

Java solves the first problem with three classes. You start with FileInputStream, instantiated like this:

You then add buffering with a decoration (or wrapping) strategy. You wrap the InputStream object with another InputStream implementer that buffers bytes. You ask the wrapper for a byte; it asks the wrapped stream for many bytes and returns the first one. The decorator wrapping goes like this:

Add decompression with another decorator, like so:

You can add additional filtering by adding additional decorators.

This solution is very flexible. You can mix and match the decorators to get the features you need. More important, each of the decorators is itself relatively simple, because it solves only one problem. Consequently, the decorators are easy to write, debug, and modify without impacting the rest of the system. I could change the buffering algorithm by rewriting BufferedInputStream, for example, and not have to touch any of the other decorators (or any of the code that used them). I could also add new filter functionality simply by implementing a new decorator. (Classes such as CipherInputStream were added to Java in this way.)

Though Decorator can effectively decompose a complex problem into simple pieces, the main intent of Decorator is to provide an alternative to implementation inheritance when you would be tempted to use extends to modify base-class behavior or add a few minor methods. In addition to the fragile-base-class problem discussed in Chapter 2, extends can add a lot of complexity when you need to change a lot of behavior. Consider Java’s collection classes. By design, the collection classes are not thread safe. Collections are not often accessed from nonsynchronized methods, so making them thread safe is just wasting CPU time as the program runs. You do, occasionally, need a thread-safe collection, however. Figure 4-7 shows how you’d have to extend the core collection classes to add thread safety. (The new classes are in gray.) I’ve had to double the number of concrete classes in the system.

Figure 4-7. Using implemenation inheritance to add thread safety to collections

Now what if I want to add unmodifiable collections, perhaps by adding a lock() method that causes all the methods that would normally modify the collection to start throwing exceptions? When I use implementation inheritance for this modification, I have to double the number of concrete classes again. Figure 4-8 shows the result.

Figure 4-8. Using implementation inheritance to add unmodifiability to collections

With an inheritance-based solution, I have to double the number of concrete classes every time I add a new feature, assuming that I want to support every possible combination of features. I can leave off some combinations, of course, but those combinations will probably be the ones I need two weeks from now.

The designers of the Collection classes solved the thread-safety problem with a Decorator. Here’s the code:

The Collections class looks something like this:

Collections is a utility class—a class made up of static “helper” methods that augment some existing class or library. Utilities are not Singletons because utilities don’t behave like objects; they’re just a bag full of functions. In this case, the Collections utility serves as a Concrete Factory of abstract Collection types. The ThreadSafeCollection class both is a Collection and wraps a Collection. The methods of ThreadSafeCollection are synchronized, however. Note that ThreadSafeCollection is private. The user of the Collections knows only that the object returned from unmodifiableCollection(...) implements Collection without allowing modifications to the backing collection. The concrete class name is unknown.

You can provide unmodifiable versions of a Collection with a similar wrapper, just as I did with the UnmodifiableTable class discussed at the beginning of this section.

You can get a synchronized unmodifiable collection with double wrapping, as follows:

The point of using Decorator is that I’ve added a grand total of two classes but accomplished the same thing that required 18 classes in an implementation-inheritance solution.

As I mentioned earlier, Java’s I/O system uses Decorator heavily. Figure 4-9 shows enough of Java’s input system that you can see the general structure. (I’ve left out the Reader classes, and so on.) I’ll discuss the Adapter pattern shown in this figure at the end of the current chapter. For now, I want to focus on Decorator.

Structurally, all the Decorators contain an instance of some class that implements the same interface as the Decorator itself. I think of Decorator as the big-fish/little-fish pattern, as shown here. The big fish (the Decorator) swallows the little fish (the Concrete Component), but they’re both fish (the Component). This is also the Gepetto (or Jonah) school of fish digestion: The little fish swims around happily in the big fish’s stomach until it’s disgorged. If a fisherman had caught the little fish just before it was swallowed (in other words, if you have a reference to a wrapped Component), then the fisherman could talk directly to the little fish by tying a tin can to the end of the fishing line and yelling into the can. (You can talk directly to a LineNumberInputStream that had been wrapped in another Decorator by keeping a reference to it, for example.) Finally, the bigger fish doesn’t know whether it has swallowed a Concrete Component or another Decorator. They’re all fish. Figure 4-10 shows the message flow during a write operation for the objects used in the previous InputStream example. Each of the Decorators gets its input from the wrapped object. This wrapped object could be another decorator or a Concrete Component; the Decorator knows nothing about that wrapped object other than the interface it implements. The order of wrapping is important. If the BufferedInputStream wrapped the PushBackInputStream in the earlier example, then a pushed-back character would effectively move to the end of the current buffer—the pushed-back characters would appear to be pushed back to random places in the input stream. Also note that since the PushBackInputStream wraps the LineNumberInputStream, pushing back a newline does not roll back the line number. On output, you want to compress before encrypting for efficiency reasons (the encryption algorithm is less efficient than the compression algorithm).

Also note that the unread(...) method that’s used to push back characters is not defined in InputStream. Consequently, you can’t access this functionality through an InputStream reference.

We’re now done with the data-storage layer. Whew!

Figure 4-9. The static structure of Decorator

Figure 4-10. The dynamic structure of Decorator

Adding SQL to the Mix

(This is not the dreaded SQL-interpreter section, so don’t skip over it.)

The Table classes are pretty useful in and of themselves. They provide a reasonably lightweight solution to the problem of an embedded database and could be better than something such as JDBC in situations where “lightweight” is mandatory—for database-like storage of configuration information without the overhead of a database, for example.

My main goal was to use a database as a persistence layer, however, and though I wanted the lightest-weight database I could get, I also wanted to be able to swap out that database with a more full-featured version should the need arise, all without having to modify any of my code. If I wrote code directly to the Table interface, then I’d have to modify that code to go to the JDBC interface required by a real database server.

It’s tempting to implement a JDBC layer directly in terms of the Table interface (or, put another way, to implement the SQL interpreter inside the JDBC classes). JDBC has more complexity than I needed for the current application, though, and JDBC imposes a relatively complex structure that I didn’t want to deal with quite yet. Consequently, I opted to go with a three-layer approach and wrap the Table with a simple SQL engine implemented with one primary class. This way I can focus on building the SQL interpreter without the complications of imposing the JDBC structure onto my interpreter. I also end up with a SQL-based table class that’s easier to use than the JDBC classes.

The interpreter itself is good sized (about 50KB of byte code), and it certainly imposes a performance penalty on the system. A SQL where clause has to be reinterpreted with every row of a query, for example, as compared to executing a small Java method (probably inlined by the HotSpot JVM) on every row.

On the other hand, any SQL database will introduce similar inefficiencies. I wasn’t doing all that much database access, and the ability to swap persistence layers without a rewrite was an important requirement.

I should also say that much of the work that I’ve done building the interpreter could be done using one of the Java “compiler-compilers” (such as JavaCUP at http://www.cs.princeton.edu/~appel/modern/java/CUP/ or JavaCC at https://javacc.dev.java.net/). Without getting too much into the technical details, I would certainly use a compiler-compiler for implementing any language that was at all complicated. In the case of the small SQL subset that I’m implementing, the structure of the language lends itself to a parser technology called recursive descent, which can usually be hand built in such a way as to be more efficient than the generic, table-driven parsers created by tools such as CUP. Since the language was small, and minimum size and maximum efficiency were two of my design goals, I opted for a handcrafted approach, thinking that I could do a better job by hand than the tools could do. This may not actually be the case, however. I haven’t implemented the language using a compiler-compiler and benchmarked the results against the hand-built version, so I really don’t know. In any event, the hand-built version provides a few nice examples of design patterns.

So, back to the salt mines.

SQL-Engine Structure

Figure 4-11 and Figure 4-12 show the static structure of (and design patterns used by) the SQL-engine layer. As before, you may want to bookmark these figures so you can refer to them later.

Figure 4-11. SQL engine and JDBC layers: design patterns

Figure 4-12. SQL engine and JDBC layers: static structure

Input Tokenization, Flyweight Revisited, and Chain of Responsibility

One of the requirements for a parser that is also a requirement for virtually any program that has to look at text-based input is input tokenization, or scanning, which is the process of breaking up a long input string into smaller pieces based on the way the input looks, and then representing those smaller strings as well-defined constants so you don’t have to constantly rescan them.

In compilers, a token is the smallest meaningful lexical unit of the input. For example, a keyword such as while is a token, as are each of the various operators. A one-to-one relationship does not necessarily exist between the actual input characters and the token type. Identifiers, for example, are all represented by an IDENTIFIER token, even though the identifiers may consist of different combinations of characters. Sometimes, semantically similar operators are grouped together into a single token. For example, the <, >, <=, ==, and != operators could be grouped together into a single RELATIONAL_OPERATOR token. A scanner inputs a stream of characters and outputs a stream of token objects that represent that input. Put another way, the scanner extracts substrings of the input and translates these substrings into tokens.

The token objects must be unique. Every time the scanner encounters an identifier in the input, for example, it returns the same IDENTIFIER object that it did the last time it encountered an identifier. This way you can tell whether you’ve read an identifier with a simple statement such as this:

An important attribute of the IDENTIFIER object (and of all tokens) is the input string that’s associated with the token, called a lexeme. Once you get an IDENTIFIER token, for example, you can figure out which identifier you just read by examining the associated lexeme.

Given that a scanner always returns the same token object for a given input sequence, the scanner is a good example of a Flyweight-pool manager. The token objects themselves are Flyweights—the lexeme is the extrinsic data—and the scanner repeatedly returns the same token object for a particular input sequence. (I discussed Flyweights in Chapter 4. Go back and read about them if the preceding didn’t make any sense.)

Java has a couple of generic tokenizers: java.util.StringTokenizer and java.io.StreamTokenizer. The former does only half of what a real scanner does: It breaks up the input into meaningful lexemes and return them to you, but it doesn’t translate the lexemes into tokens. The StreamTokenizer does return tokens, but it recognizes only four of them: TT_EOF (end of file), TT_EOL (end of line), TT_NUMBER (a number), and TT_WORD (anything else). TT stands for token type. In the case of TT_NUMBER and TT_WORD, the associated lexemes can be examined via the nval and sval fields of the tokenizer (not a great design decision—public accessors would be better).

The StreamTokenizer is too limited for a compiler application, however. I want unique tokens for every keyword, for example. Lumping all the keywords and identifiers in the input into a single TT_WORD token is too coarse grained to be useful. A real scanner would return IDENTIFIER, WHILE, IF, and ELSE tokens as appropriate.

So, let’s look at the more capable scanner used by the SQL engine. The first order of business is to define a set of tokens for the scanner to use. The individual tokens are responsible for recognizing the associated input lexemes. Tokens are always part of a set, so I didn’t want anyone to create one without connecting it to an associated token set. Consequently, a TokenSet object serves as a Token factory. You create tokens as follows:

The argument to create() is a regular expression that describes the lexeme associated with this token. Surrounding the expression with single-quote marks causes all characters to be treated literally (rather than as regular-expression metacharacters. That is, the specification "'...'" is treated identically to the regular expression "Q...E". The closing quote is optional.

The TokenSet participates in several design patterns, but here it’s in the Concrete Factory role of Abstract Factory. (There is no interface in the Abstract Factory role.) Token is the Abstract-Product interface, and implementers of the Token interface (which we’ll look at shortly) are the Concrete Products.

The client class (the Database) doesn’t know the actual classes of the Concrete Products: the Token objects returned from create(...). Nonetheless, the system supports three distinct Token subclasses that differ only in how efficient they are in processing the input string. That is, it’s the job of each Token object to look at the input stream and tell whether the next few input characters match a lexeme associated with that token.

• A RegexToken uses Java’s regular-expression system to match the input stream against the specification, so it is powerful but relatively inefficient. It is case insensitive.
• A SimpleToken matches tokens for which there is only one possible lexeme. Its recognizer, which just performs a literal match of the pattern against the input string, is by far the most efficient of the three token types. To make it as efficient as possible, the recognizer for a SimpleToken is not case insensitive (unlike the other two Token types). This inconsistency is, in some ways, a design flaw, but I was loath to slow down a recognizer that’s used primarily for finding punctuation and operators. The factory uses a SimpleToken when the specifier passed to create(...) is either surrounded by single quotes or contains no regular-expression metacharacters.
• A WordToken is a SimpleToken that must be terminated at a “word boundary.” (Either it must be followed by a character that’s not legal in a Java identifier or it must be the last token in the input string.) The regular-expression subsystem isn’t used for word tokens. The tokens are recognized in a case-insensitive way.

The TokenSet factory simplifies token creation by deciding which of the three Token implementers to create, based on what the specification looks like. In particular, if the string contains any of the regular-expression metacharacters and isn’t surrounded by single-quote marks, RegexToken objects are created. In the case of quoted strings or strings that don’t contain metacharacters, the factory creates a WordToken if the specification ends in a character that’s legal in a Java identifier; otherwise, it creates a SimpleToken.

Given a conflict in the lexemes (in other words, two Token specifications can match the same input sequence), the token that’s created first takes precedence. In the earlier example, the INPUT token must be created before the IN token or the string "input" will be processed incorrectly. (An IN token will be recognized, and then an IDENTIFIER with the value “put” is recognized.) Similarly, IDENTIFIER has to come last; otherwise, it would suck up all the keywords.

The TokenSet reification of Abstract Factory omits the interface in the Abstract-Factory role. The downside of this incomplete reification is that you have to modify the source code for the TokenSet class if you add a new token type. You can create a token type simply by extending Token, of course, but you won’t be able to create instances of your token via the factory unless you modify the factory as well. My main goal with this particular factory was to simplify the code, however. I just wanted to declare tokens without worrying about which Token subclass was needed for a particular input specification. Since I don’t expect to add new token types, the lack of expansibility isn’t a large concern (famous last words).

Moving onto the code, the Token class is in Listing 4-20, and the three implementations are in Listing 4-21 (SimpleToken.java), Listing 4-22 (WordToken.java), and Listing 4-23 (Regex-Token.java). SimpleToken (Listing 4-21) is the simplest, so let’s start there. The constructor is passed a template input sequence. The match(String input) method returns true if the first characters on the input line match that template. Finally, lexeme() returns the most recently recognized lexeme.

The WordToken class in Listing 4-22 is only marginally more complicated. The match(...) method checks the input against the pattern, but it also looks to make sure that the character that follows couldn’t occur in a Java identifier (in other words, is on a “word” boundary).

The RegexToken class in Listing 4-23 is the most complicated because it uses Java’s regex package. It’s a straightforward use of the Pattern and Matcher classes, but note that the pattern is compiled only once, when the RegexToken is created. As is the case in the other Token implementation, patterns are recognized in a case-insensitive way.

The tokenSet class is in Listing 4-24. Its members field (Listing 4-24, line 8) holds the members of the Flyweight pool (the previously created tokens).

The create(...) method (Listing 4-24, line 39) adds all the tokens that it creates to this collection. It also decides which subclass of Token to create by examining the input specification.

You can get an java.util.Iterator across all the Flyweights in the pool by calling iterator() (Listing 4-24, line 15). Note that this iterator is guaranteed to present the Token objects in the same order that they were added to the pool. This guaranteed ordering will be important when I implement the scanner, shortly.

The Scanner: Chain of Responsibility

The Scanner class (Listing 4-25) uses the TokenSet to implement a scanner. You create a scanner for a particular token set like this:

The Scanner looks for tokens in the specified set, reading characters from the specified Reader. The interface to the Scanner is straightforward, but it may be surprising if you’ve never built a parser. Parsers, in general, are more interested in seeing if the next input token (called the lookahead token) is what they expect than they are in actually reading the next token (removing it from the input). Consequently, the Scanner interface does not have a getToken() method, simply because such a method wouldn’t be used. You use the scanner more or less like this:

The match(...) method just checks to see if the desired token is the next one in the input stream. The advance() method actually reads (and returns) the next input token. This match/advance strategy is much more efficient than reading the token because you’d otherwise have to repetitively push uninteresting tokens back onto the input.

Two convenience methods are provided to simplify scanning: First, matchAdvance(Token) (Listing 4-25, line 111) combines the match and advance operations. If the token argument matches the current token, the scanner advances to the next token and returns the current lexeme. Otherwise, the scanner does nothing and returns null. Second, the required(Token) method (Listing 4-25, line 127) is a more forceful version of matchAdvance(). It throws a ParseFailure exception if the specified token isn’t the current token.

The Scanner is implemented in Listing 4-25. From the design-patterns perspective, the interesting code is the for loop on line 76. I get an iterator across the entire token set and then ask each token in turn whether its lexeme specification matches the current input sequence. The work of detecting the match is delegated to the Token objects, each of which checks for a match in the most efficient way possible.

The design pattern here is Chain of Responsibility (sometimes called Chain of Command). The idea is to handle an event (or in this case, an input sequence) by passing it in turn to a set of Command objects. Those objects that are able to handle the event do so. The object that does the routing can’t predict which handler (some object in the pattern’s Handler role) will handle the event (or input), and usually doesn’t care, as long as that event (or input) gets handled. It’s important to note that the list of handlers is put together at runtime. The Client has no way to know at compile time which handlers will be invoked in which sequence.

This characteristic is important in the current context because the order in which Token objects attempt to match themselves against the input is important. In the SQL engine, for example, you have an IN and also an INPUT token. It’s important that the Scanner looks for a match of IN before it looks for INPUT; otherwise it will never find the latter. Similarly, it’s important that the IDENTIFIER token, which is declared like this:

be at the end of the list of tokens, because the specified regular expression will also match all the keywords. Were IDENTIFIER not declared last, keywords would be incorrectly recognized as identifiers.

The Scanner stops routing the input to Token objects once a Handler (a Token) recognizes an input sequence. The design pattern doesn’t require this behavior, however. Several Handlers could all process all or part of the same event. Similarly, Chain of Responsibility doesn’t require a separate “router” object that controls who gets a crack at the input. A Handler may keep around a pointer to its own successor, for example, and handle the routing locally.

One anti-example of the Chain-of-Responsibility pattern (that is, an example that demonstrates the pattern’s shortcomings) is the Windows event model. A Windows UI is a runtime hierarchy of objects. Consider a typical dialog box with a text field on it. Figure 4-13 shows the associated runtime object hierarchy. Now imagine you’re typing in the text field and accidentally hit a typically easy-to-remember “hot key” such as Ctrl+Alt+Shift+F12. As you can see by following the sequence of arrows, the key-pressed event can go to many potential handlers (from the text control to its parent window (the Dialog Frame) to its parent (the MDI Child) to its parent (the Main Frame) to the menu bar, to each menu on the menu bar to menu item on that menu bar. Finally, when the key-pressed event gets to the last menu item on the last menu on the menu bar, it’s discarded. The same sequence will happen every time the mouse moves one pixel. That’s a lot of motion, but no action. This is one reason why Java abandoned this message-routing mechanism with Java 1.1 in favor of its Observer-based system.

Figure 4-13. Chain of Command in a Windows UI

Java has lots of good examples of Chain of Responsibility. One of the better ones is the servlet filter. A servlet is a small program that’s invoked automatically by the web server in response to an HTTP Post or Get request. Typical servlets are passed data that’s specified in an HTML form, and they create a HTML page that’s displayed on the client-side browser in response to that form submission. Once you’ve written a few servlets, you come to realize that they often duplicate the code of other servlets. For example, authentication is a commonplace activity in a servlet. The servlet may read a username and password from the submitted form data, for example, and refuse to proceed with a transaction if the password isn’t correct. Alternatively, a servlet may check the session data (a packet of information that’s associated with the user) to assure that a given user is indeed logged in. Duplicating this authentication code in every servlet increases the complexity of the system as a whole and also tends to create lack-of-consistency problems in the user interface. (Different servlets may handle the same problem in different ways.) Other common problems include things such as database lookup. That is, the session data may contain a key that you need to use to get additional information out of a server-side database. This lookup may occur in several servlets, which can cause serious maintenance problems if the data dictionary needs to change, for example. By the same token, information in the session data may have to be stored persistently in a database.

Chain of Responsibility, as reified in the servlet filter, solves all these problems. Figure 4-14 shows the general flow of data through a system of servlets and filters as some form is being processed. The first filter does authentication. If the user has logged in, this filter is just a pass through, doing nothing but passing its input to the next filter in the chain. The second filter handles persistent session information—information that resides in a database rather than information that is created during the course of the session—performing all the required database lookup.

You should note two important points: First, the filters are put into place by the web server, not the servlet. As far as the servlet is concerned, the user is authenticated, and the database information is fetched and stored by magic. Second, each filter handles its part of the current operation and then either allows the next object in the chain of responsibility (the next Filter or the servlet itself) to do additional work or short-circuits the process. Runtime configuration and the relative autonomy of the Handlers are both defining characteristics of the Chain of Responsibility.

One other problem I’ve solved with Chain of Responsibility deserves mention: user-input processing. You saw earlier how you can use the Builder pattern to isolate UI generation from the underlying “business object,” but it’s sometimes awkward to use Builder on the input side. For example, you can use Builder to ask an object to build an HTML representation of itself for insertion into a generated page (or build an XML representation of itself that’s passed through a XSLT translator to build the HTML). In fact, several objects may contribute user interfaces to the page in this way. (A UI could be built, in fact, by a series of servlet filters, each of which augments a generated HTML page by adding a UI for a particular object.)

The page is served, the user hits the submit button, and the form data comes back to another servlet, but then what? You don’t really want the servlet to know how to talk to all the objects that contributed to the original page because it’s too much of a maintenance problem. If those objects change their user interfaces in some way, you need to change the servlet as well. These coupling relationships are too tight.

Chain of Responsibility solves the coupling problem. All that the servlet (or some filter) needs to do is keep a list of the objects that contributed to the UI. The servlet passes those objects the complete set of form-input data, and the objects parse out of that list whatever is interesting to them. Since the objects built the form to begin with, the object can generate unique field names on the output side, and the object can search for these same names on the input side. The actual servlet is completely generic with respect to the UI: It just keeps a list of contributing objects, gets HTML from the objects, and routes the form data back to the objects on the list. It has no idea what the objects actually do, and the interface is extremely simple. More important, you can make massive changes to the objects without impacting the code that comprises the servlet at all.

Figure 4-14. Chain of Command in a Windows UI

The ParseFailure Class

Finishing up loose ends before moving onto the SQL interpreter itself, the one class you haven’t looked at yet is the ParseFailure class in Listing 4-26. (I was going to call this class ParserException, but that name was too much like java.text.ParseException.)

Other than the obvious use of having something to throw when a parse error occurs, the ParseFailure object is interesting in the way that I use it to eliminate getter functions from the Scanner class in order to reduce coupling relationships between the Scanner and the rest of the program. Rather than using a getter to find out where on the line that an error occurs, that information is carried around by the exception object itself. This way, you can catch a parse error and print a reasonable error message without having to talk to the Scanner that detected the error at all. The ParseFailure object carries around the input line, line number, and position-on-the-line information, and you can generate a contextual error message that looks like this:

as follows:

I’ve provided no getter methods (in the sense of methods that access internal state data such as the line number or offset to the error position), simply because they aren’t required. Remember the golden rule of implementation hiding: don’t ask for the information that you need to do the work; rather, ask the object that has the information to do the work for you.

One final issue exists: Not only is it reasonable for a Scanner to throw ParseFailure objects, but it’s reasonable for the parser that uses the scanner to throw them as well. The scanner throws a ParseFailure if the input sequence matches no known token, for example. The parser needs to throw a ParseFailure if it finds malformed SQL.

Since the ParseFailure object contains information that’s provided by the scanner (the line number and input position), then it makes sense for Scanner objects to act as ParseFailure factories. Rather than having the parser extract line number and position information from the Scanner in order to create a parser-related error message, the parser requests a ParseFailure object that encapsulates that information.

The Scanner, then, is a ParseFailure Factory. When the parser encounters an error at the language (as compared to the lexical-analysis) level, it can throw a ParseFailure object that indicates where the error occurred with code like the following:

The Database Class

The Database encapsulates the SQL interpreter. Its main job is to transform a set of SQL statements into calls that a Table understands. By introducing SQL into the mix, however, you free the program from needing to know anything about Table objects.

Using the Database

You can use a Database in one of two ways: as a stand-alone class that represents a SQL database or as a Decorator that wraps a com.holub.database.Table temporarily so that you can access the table using SQL. The only difference between these two uses is the constructor you use. Open a stand-alone database like this:

The (optional) argument specifies the path to a directory that represents the database itself. (Tables are stored as individual files.) Convenience constructors let you specify the path with a File or URI object instead of a String. Also, you do not have a no-arg constructor that just puts tables into the current directory. A SQL USE DATABASE directoryName request causes the Database to use the named directory instead of the one specified in the constructor.

To use the Database as a Decorator of an existing table (or set of tables), use the following alternative constructor:

This isn’t a full-blown Gang-of-Four Decorator since Database doesn’t implement the Table interface. It does satisfy the intent of the pattern, however, in that it allows you to augment the Table interface by adding SQL support.

Once you’ve created the database, you talk to it using a single method that takes a String argument that specifies a single SQL command. For example, the following code (taken from the Database class’s unit test) reads a series of SQL statements from a file and executes them:

Listing 4-27 shows the SQL that the test-script uses, but it’s pretty standard stuff.

Though you can do everything through the execute(...) method, Database provides a few additional methods that let you create, load, and drop tables; dump tables to disk; and manage transactions. I’ve listed these methods in Table 4-1. An exception toss that occurs when processing a SQL expression submitted to execute() causes an automatic rollback as a side effect. This automatic-rollback behavior is not implemented by the methods in Table 4-1, however. If you use these methods, you’ll have to catch any exceptions manually and call rollback(...) or commit(...) explicitly.

Table 4-1. Methods of the Database Class

Method	Description
int affectedRows()	Returns the number of rows that were affected by the most recent execute(java.lang.String) call.
void begin()	Begins a transaction.
void commit(boolean checkForMatchingBegin)	Commits a transaction.
void createDatabase(String name)	Creates a database by opening the indicated directory.
void createTable(String name, List columns)	Creates a new table.
void dropTable(String name)	Destroys both internal and external (on the disk) versions of the specified table.
void dump()	Flushes to the persistent store (for example, disk) all tables that are “dirty” (which have been modified since the database was last committed).
Table execute(String expression)	Executes a SQL statement.
void rollback(boolean checkForMatchingBegin)	Rolls back a transaction.
void useDatabase(File path)	Uses an existing “database.”

The Proxy Pattern

The first part of the Database class is in Listing 4-28. Of the fields at the top of the listing, the tables Map (line 41) holds the tables that comprise the database. They’re indexed by table name. tables is declared as a Map, but it actually holds a specialization of HashMap (TableMap, declared on line 52).

This specialization adds table-specific behavior to a standard HashMap. First, the get() override uses lazy instantiation: When a specific table is first requested, it’s loaded from the disk using the CSV Builder. Database methods can act as if all the tables were preloaded into a standard Map, but the tables are actually loaded when they’re requested for the first time.

The other modification to the standard HashMap is a put() override, which handles a transaction-related problem that’s a side effect of lazy instantiation. The current transaction-nesting level is stored in transactionLevel field declared on line 46. It’s incremented by a BEGIN operation and decremented by a COMMIT or ROLLBACK. The code that does the commit/rollback assumes that all the tables in the Map are at the same transaction level. That is, it just commits or rolls back all of them, all at once. If you begin a transaction and then use a table that you haven’t used before, that table will not have had a begin() issued against it, yet. The loop in put() solves the problem by issuing begin() requests against the newly loaded table.

Since I don’t use it and didn’t want to rewrite it, I also overloaded putAll() to throw an UnsupportedOperationException(). I’m playing pretty fast and loose with the class contract here. I wouldn’t argue if someone flagged this change as a defect in a code review and forced me to provide a putAll(), but the TableMap is a private inner class—so it can’t be extended or used from outside the class definition—I decided that the deviation from the contract was acceptable. I would not make a change of this magnitude if the class were globally accessible.

The remainder of the methods in the Map interface just map through to the contained Map object.

The code at which we’ve been looking—which creates expensive objects on demand—is an example of the Proxy design pattern. (The earlier design-patterns diagram (Figure 4-11) had no space for these classes, so I’ve sketched it out in Figure 4-15.) A proxy is a surrogate or placeholder for another object, a reference to which is typically contained in the proxy. The TableMap serves as a proxy for the realMap object that it contains. The main idea is that it’s convenient, sometimes, to talk to some object (called the Real Subject) through an intermediary (called a Proxy) that implements the same interface as the Real Subject. This intermediary can do things such as lazy instantiation (loading expensive fields on demand).

Figure 4-15. The Proxy pattern

The Gang-of-Four book mentions the following types of proxies:

• A remote proxy exists on one side of a network connection and implements the same interface as does another object on the other side of the network connection. You talk to the proxy, and it talks across the network to the real object. For all practical purposes, the client thinks that the proxy is the remote object because all communication with the remote object is transparent. Java RMI, CORBA, and XML/SOAP are remote-proxy architectures.
• The TableMap is an example of a virtual proxy, a proxy that creates expensive objects on demand. This particular implementation is not “pure” in the sense that the underlying HashMap is not created on demand, but rather the HashMap is populated on demand. A “purer” example of a virtual proxy is the java.awt.Image class, which serves as a proxy for the real image as it’s being loaded. That is, Runtime.getImage() immediately returns a proxy for the real image, which is being downloaded across the network by a background thread. You can use the proxy (the Image returned by getImage()) before the real image arrives, however getImage() returns the real image, not the proxy, if it has already downloaded the image.
• A protection proxy controls access to an underlying object. For example, the Collection implementations returned from Collections.synchronizedCollection(...) and Collections.unmodifiableCollection(...) are protection proxies.
• A smart reference replaces a bare reference in a way that adds additional functionality. Java’s “weak reference” mechanism, as is used by a java.util.WeakHashMap, is one example of this kind of proxy; the C++ SmartPointer is another.

Virtual proxies are particularly useful in database applications because you can delay a query until you actually need the data. Consider an application where you needed to choose one of 10,000 Employee objects and then do something with that object. You could go out to the database and fully create all 10,000 Employee objects, but that’s really a waste of time. It would be better to put the employee names into a single table and then create proxies for the real Employee objects. (The proxies would hold the name, but nothing else.) When you called some method of the proxy that used some field other than the name, the proxy would go out to the database and get the required data for that Employee only (or perhaps fully populate a full-blown Employee from the database).

One significant source of confusion amongst people learning the Proxy pattern is the difference between Proxies and Decorators. The point of a Decorator is to add or modify the behavior of an object. The point of Proxy is to control access to another object. They’re structurally identical; thus, confusion exists.

The Token Set and Other Constants

The Database definition continues in Listing 4-29 with the token-set definition (lines 128 to 172) As I mentioned earlier, tokens are created in search order, so it’s important that the keyword tokens are created before the IDENTIFIER token. Listing 4-29 finishes up with two enumerated-type declarations. I’ve used Bloch’s typesafe-enum idiom, discussed in Chapter 1, to define two enumerations. (This idiom gives me both type safety and also a guaranteed constraint on the possible values—a static final int does neither.) The RelationalOperator objects are used to identify which relational operator is being processed. MathOperator is the same but for arithmetic operators.

The next chunk of the Database definition is in Listing 4-30. The constructors—which are pretty self-explanatory—come first, followed by a few private workhorse functions that are used elsewhere in the class. The error(...) method (line 247) is called when a parse error occurs. It’s interesting to see how I’ve used delegation to avoid accessor methods. Since the Scanner already knows how to create a ParseError object that contains a context-sensitive error message, I delegate the creation of the error object to the Scanner object. This way I don’t have to extract anything from the scanner to create a sensible error message.

The rest of Listing 4-30 defines most of the convenience methods discussed in Table 4-1. The only interesting method is dump() on line 327, which flushes to disk those tables in the tables Map that have been modified (isDirty() returns true). The design issue here is whether the isDirty() method is needed at all—it is exposing an implementation detail. I could, for example, add an exportIfDirty() method to the Table and dispense with isDirty() altogether. You can see why I opted for the isDirty() solution by looking at the code. I just didn’t want to create (and open) a FileWriter if I wasn’t going to use it.

Another alternative that I also rejected was adding a writeAsCsvIfDirty() method to the Table. The whole point of using the Builder pattern to export data was to avoid exactly that sort of method.

One solution has none of these problems, but it does introduce a bit of extra complexity. You could introduce a Proxy for the Writer called a DelayedWriter. The DelayedWriter would work exactly like a FileWriter from the outside. Inside, it would create a FileWriter to actually do the output as a side effect of requesting the first write operation. This way, the file wouldn’t be opened unless you actually wrote to it. If you implement an exportIfDirty(Exporter builder) method in the Table, and pass it a CSVExporter that uses a DelayedWriter, the file would never be opened if the Table wasn’t dirty because the exporter would never write to it. Though the DelayedWriter Proxy would eliminate the need for isDirty(), I eventually decided that it wasn’t worth adding the extra complexity, so I didn’t implement it.

Transaction processing (Listing 4-31) comes next. Most of the work is done in the Table class, which manages undo operations on a specific table, and the TableMap class you just saw. The methods in Listing 4-31 do little more than delegate the begin, commit, and rollback requests to the various Table objects in the tables Map.

From a design point of view, it’s difficult to decide where these three methods actually belong. Since the TableMap is doing a lot of the work surrounding transactions, it makes sense to do the rest of the transaction-related work there. On the other hand, it’s nice to make the TableMap a “pure” proxy that is just a Map implementation. It’s just cleaner not to add additional methods to the Map methods. (Doing so, of course, would make the TableMap both a Decorator and a Proxy.) I decided to leave the methods where they are, primarily because I consider transactions to be operations on a database, not a Map.

The Interpreter Pattern

Okay, you’ve arrived at the dreaded SQL-engine section. This section discusses only one design pattern: Interpreter. Interpreter is one of the more complicated patterns and assumes that you know a lot about how compilers work. The odds of your needing to use Interpreter are not high (unless you’re building a compiler or interpreter), so feel free to skip forward to “The JDBC Layer” section on page 325.

Supported SQL

The Database class implements a small SQL-subset database that provides a SQL front end to the Table classes. My intent is to do simple things, only. But you can do everything you need to do in most small database applications. SELECT statements, for example, support FROM and WHERE clauses, but nothing else. (DISTINCT, ORDEREDBY, and so on, aren’t supported; neither are subqueries, outer joins, and so on.) You can join an arbitrary number of tables in a SELECT, however. A few operators (BETWEEN, IN) aren’t supported. Any Java/Perl regular expression can be used as an argument to LIKE, and for SQL compatibility, a % wildcard is automatically mapped to "." The main issue is that you’ll have to escape characters that are used as regular-expression metacharacters. All the usual relational and arithmetic operators are supported in a SELECT, and you can SELECT on a formula (SELECT columns WHERE (foo*2) < (bar+1)), but functions are not supported.

Selecting “into” another table works, but bear in mind that the actual data is shared between tables. Since everything in the table is a String, this strategy works fine unless you use the Table object that’s returned from execute(...) to add non-String objects directly to the Table. Don’t do that.

The Database class uses the file system to store the database itself. A database is effectively a directory, and a table is effectively a file in the directory. The argument to USE DATABASE specifies the path to that directory. The modified database is not stored to disk until a DUMP is issued. (In the JDBC wrapper, an automatic DUMP occurs when you close the connection.)

The SQL parser recognizes types (so you can use them in the SQL), but they are ignored. That is, everything is stored in the underlying database as a String. You can’t store a boolean value as such, but if you decide on some string such as "true" and "false" as meaningful, and use it consistently, then comparisons and assignments of boolean values will work fine. Null is supported. Strings that represent numbers (that can be parsed successfully by java.text.NumberFormat in the default Locale) can be used in arithmetic expressions, however. You can use the types in Table 4-2 in your table definitions.

Reasonable defaults are used if an argument is missing. You can also specify a PRIMARY KEY(identifier) in the table definition, but it’s ignored, too.

Identifiers follow slightly nonstandard rules. Because the database name is the same as a directory name, I’ve allowed database names to contain characters that would normally go in a path (/, , :, ~, and _), but I haven’t allowed them to contain a dot or dash. Identifiers can’t contain spaces, and they cannot start with digits.

Numbers, on the other hand, must begin with a digit (.10 doesn’t work, but 0.10 does), and decimal fractions less than 1.0E-20 are assumed to be 0. (That is, 1.000000000000000000001 is rounded down to 1.0 and will be put into the table as the integer 1.)

Table 4-2. SQL Types Recognized (But Ignored) by the Parser

Types	Description
integer(maxDigits) int(maxDigits) smallint(maxDigits) bigint(maxDigits) tinyint(size)	Integers.
decimal(l,r) real(l,r) double(l,r) numeric(l,r)	Floating point. l and r specify the maximum number of digits to the left and right of the decimal.
char(length)	Fixed-length string.
varchar(maximum_length)	Variable-length string.
date(format)	Date in the Gregorian calendar with optional format.

Transactions are supported, and transactions nest properly, but the transaction model is very simple. (For you database folks, the only part of the ACID test that I’ve supported is the A—Atomicity. Consistency checks are not made [everything’s stored as a String]. The database is not thread safe, so multiple transactions won’t work, and there’s no Isolation. The database is flushed to disk only when you execute a flush() or close the connection, so there’s no Durability at the transaction level. You could fix the latter by flushing after every transaction, but I opted not to do so.)

Initially, no transaction is active, and all SQL requests are effectively committed immediately on execution. This auto-commit mode is superseded once you issue a BEGIN but is reinstated as soon as the matching COMMIT or ROLLBACK is encountered. All requests that occur between the BEGIN and COMMIT are treated as a single unit. The begin(...), commit(...), and rollback(...) methods of the Database class have the same effect as issuing the equivalent SQL requests and are sometimes more convenient to use.

The SQL-subset grammar I’ve implemented is as follows. Since the Database uses a recursive-descent parser, I’ve used a strict LL(1) grammar, with the following abbreviations in the terminal-symbol names: “expr”=expression, “id”=identifier, “opt”=optional. I’ve also used brackets to identify an optional subproduction.

statement	::=	INSERT INTO IDENTIFIER [LP idList RP] VALUES LP exprList RP
	|	CREATE DATABASE IDENTIFIER
	|	CREATE TABLE IDENTIFIER LP declarations RP
	|	DROP TABLE IDENTIFIER
	|	BEGIN [WORK | TRAN[SACTION]]
	|	COMMIT [WORK | TRAN[SACTION]]
	|	ROLLBACK [WORK | TRAN[SACTION]]
	|	DUMP
	|	USE DATABASE IDENTIFIER
	|	UPDATE IDENTIFIER SET IDENTIFIER EQUAL expr WHERE expr
	|	DELETE FROM IDENTIFIER WHERE expr
	|	SELECT [INTO identifier] idList FROM idList [WHERE expr]
idList	::=	IDENTIFIER idList' | STAR
idList’	::=	COMMA IDENTIFIER idList'
	|	ε
declarations	::=	IDENTIFIER [type] [NOT [NULL]] declaration'
declarations’	::=	COMMA IDENTIFIER [type] declarations'
	|	COMMA PRIMARY KEY LP IDENTIFIER RP
	|	ε
type	::=	INTEGER [ LP expr RP ]
	|	CHAR [ LP expr RP ]
	|	NUMERIC [ LP expr COMMA expr RP ]
	|	DATE
exprList	::=	expr exprList'
exprList’	::=	COMMA expr exprList'
	|	ε
expr	::=	andExpr expr'
expr’	::=	OR andExpr expr'
	|	ε
andExpr	::=	relationalExpr andExpr'
andExpr’	::=	AND relationalExpr andExpr'
	|	ε
relationalExpr	::=	additiveExpr relationalExpr'
relationalExpr'	::=	RELOP additiveExpr relationalExpr'
	|	EQUAL additiveExpr relationalExpr'
	|	LIKE additiveExpr relationalExpr'
	|	ε
additiveExpr	::=	multiplicativeExpr additiveExpr'
additiveExpr'	::=	ADDITIVE multiplicativeExpr additiveExpr'
	|	ε
multiplicativeExpr	::=	term multiplicativeExpr'
multiplicativeExpr’	::=	STAR term multiplicativeExpr'
	|	SLASH term multiplicativeExpr'
	|	ε
term	::=	NOT factor
	|	LP expr RP
	|	factor
factor	::=	compoundId | STRING | NUMBER | NULL
compoundId	::=	IDENTIFIER compoundId'
compoundId'	::=	DOT IDENTIFIER
	|	ε

Finally, we’ve arrived at the actual interpreter.

Consider the following (deliberately complex) SQL statement:

The WHERE clause of this expression can be represented by the abstract-syntax tree in Figure 4-16.

Figure 4-16. An abstract-syntax tree

Your first task in implementing a SQL interpreter is to build a parser that creates this abstract-syntax tree as a physical tree in memory. Nodes in the physical tree are all objects of a class that implements the Expression interface. You’ll look at all of these subclasses of Expression momentarily, but Figure 4-17 shows which classes are represented in which places in the physical tree that the parser builds from the earlier SQL expression. The main common characteristic of the Expression objects is that they contain references to the objects below them in the tree so can communicate with these descendants. Also note two categories of Expression objects exist: Terminal nodes have no children—they’re at the ends of the branches. Nonterminal nodes are all interior nodes, and all have at least one child. In addition to the children, each object remembers information specific to the input. The RelationalExpression objects remember the operator, for example. AtomicExpression objects contain a Value (more on this in a moment) that represents either a constant value or the table-and-column reference, and so forth. I’ll come back to this figure later in this section.

Listing 4-32 shows the actual parser, which interestingly, is not part of the Interpreter pattern itself. This parser is a straightforward recursive-descent parser that directly implements the grammar shown previously. The only deviation from the grammar itself is the elimination of tail recursion (situations where the last thing that a recursive method does is call itself) with a loop. For example, these two productions:

Figure 4-17. The physical representation of the abstract-syntax tree

idList	::=	IDENTIFIER idList'
	|	STAR
idList'	::=	COMMA IDENTIFIER idList'
	|	ε

would be implemented naïvely like this (I’ve stripped out nonessential code):

You can improve this code in two steps. First, eliminate the tail recursion in idListPrime() as follows:

Now that idListPrime() is no longer recursive, you can hand-inline the method, replacing the single call to it in idList() with the method body, like so:

If you look at the real implementation of idList() (Listing 4-32, line 579), you’ll see that it follows the foregoing structure. The only addition I’ve added in the real code is that idList() assembles (and returns) a List of the identifiers that it recognizes.

I’ve deliberately not cluttered up the parser with code that manipulates the underlying Table objects—all that code is relegated to private methods I’ll discuss shortly. The only real work that the parser does is build a tree of Expression objects (objects whose classes implement Expression) that directly reflects the structure of the abstract-syntax tree. That is, most of the methods that comprise the parser collect Expression objects that are created at levels below the current one and then assemble another Expression object that represents the current operation in the syntax tree (typically passing the constructor to the new Expression references to the objects representing the subexpressions). The method then returns the Expression that represents the current operation.

Taking multiplicativeExpr() (Listing 4-32, line 748, and reproduced next) as characteristic, the calls to term() return an Expression object that represents the subexpression tree. The method creates an ArithmeticExpression to represent itself, passing the ArithmeticExpression constructor the two Expression objects returned from the two term() calls. The method then returns the ArithmeticExpression.

The balance of the parser is similarly straightforward and should provide no difficulty to you (provided you’ve seen a recursive descent parser before).

Now that you’ve looked at how the tree is built, you can look at the Interpreter design pattern—the pattern actually has nothing to say about how you could bring an expression tree into existence. You could use a parser, but you could also hand-code the tree.

The basic notion of the Interpreter pattern is to implement an interpreter by traversing a physical tree of Command objects that represents the abstract-syntax tree for an expression in some grammar. Each node in the tree performs the operation that it represents syntactically. For example, the execute() method of the ArithmeticExpression node that was created in the parser’s multiplicativeExpression() method performs a single arithmetic operation and returns an object (of class Value) that represents the result of the operation. The tree is traversed in a depth-first fashion. The first thing that a parent-node execute() method does is call the execute() methods of the children, all of which return Value objects to their parents.

The Expression interface and its implementations are all in Listing 4-33. The Expression interface defines only one method: evaluate(...), which causes the Expression object to do whatever it does to evaluate itself and to return a Value that represents the result.

Taking ArithmeticExpression (on line 833) as characteristic, the constructor stores away Expression objects representing the two subexpressions and the operation to perform (operator). The evaluate method gets the values associated with the left and right subexpressions (and stores them in leftValue and rightValue). It then checks that the subexpressions returned values of the correct type. As you can see from the class diagram in Figure 4-12, on page 261, Value is itself an interface, and several implementations represent particular types. A NumericValue represents a number, a StringValue represents a string, and so on. ArithmeticExpression’s evaluate() method requires the Values returned from the subexpressions to be NumericValue objects. Finally, evaluate() extracts the actual values (as doubles), performs the arithmetic, and creates a NumericValue to hold the result.

The Value interface and its implementations are in Listing 4-34, and NumericValue is defined on line 1048. This class is little more than a container for a double. In fact, I could have used the introspection classes such as java.lang.Double for values, were it not for the fact that I needed a few operations that the introspection classes don’t support and I needed the objects that represent return values to implement a common interface. (Double implements Number, but String does not. NumericValue and StringValue both implement Value, however.)

So far, you’ve just looked at the Expression objects in the Nonterminal-Expression role (Expression objects that represent interior nodes in the syntax tree). One other sort of Expression exists: an AtomicExpression that is used in the Terminal-Expression role—it represents a leaf of the tree, an object that has no subexpressions (a numeric constant, a string constant, a reference to a cell in a table, or a SQL null). AtomicExpression is at the end of Listing 4-33 (page 314) on line 1003. The only real difference between this Terminal Expression and the Nonterminal Expressions is the absence of subexpressions and their associated evaluate() calls. The AtomicExpression contains a Value, not a pair of Expression objects representing the subexpressions. AtomicExpression objects are created in only one place: in factor(...) (Listing 4-32, line 783). The factor(...) method creates a Value object, the type of which is determined by the input, and then returns an AtomicExpression that wraps that Value.

Returning back to the values in Listing 4-34, with one exception, these classes all just act as containers for the actual value. NumericValue contains a double, StringValue contains a String, BooleanValue contains a boolean, and so forth.

The only interesting Value class is the IdValue (Listing 4-34, line 1068), which represents a reference to a row/column intersection (a cell) in a Table. The IdValue’s fields are the table and column names. The work of fetching the value for a particular row in that table happens in the toString() method on line 1082, which is passed an array of Cursor objects. (Typically, this array has only one element in it, but in the case of a join, it will have as many elements as there are tables in the join.) The toString() method finds the cursor that’s traversing the table whose name it has stored (in tableName) and then extracts the required column from the table using that Cursor. It returns the cell’s contents as a String. The value() method in the IdValue (on line 1119) examines the String returned from the toString() override and does a type conversion by creating an appropriate Value type, based on the String’s contents.

The important fact to note here is that the value of a cell is not fetched when the interpreter tree is built; rather, it’s fetched when the tree is evaluated. At build time, the AtomicExpression stores away the information it needs to access the proper cell at evaluation time. The toString() call, which actually fetches the value of the cell, is made by some Expression object’s evaluate() method. The Terminal Expression (the IdValue) accesses the Context (one of the Tables) at expression-evaluation time.

The Table class has the roll of Context in the design pattern. The Context is any data structure that holds the values of variables that are accessed from the interpreted expressions.

Watching the Interpreter in Action

The final piece of the Database class pulls together everything I’ve discussed in this chapter. The methods in Listing 4-35 are the workhorse methods that are called from the parser to execute SQL statements.

Let’s start with SELECT, at the top of Listing 4-35. I’ll demonstrate how the interpreter works by tracing through the code as it traverses the interpreter tree in Figure 4-17, evaluating the following SQL statement:

Here’s the parser code (from Listing 4-32) that’s executed when a SELECT is encountered:

The first call to idList() parses the list of columns and returns a java.util.List that contains the two strings "first" and "last". (The idList() method is on line 579 of Listing 4-32.) The second call to idList() does the same thing, but with tables listed in the FROM clause. The call to expr() (Listing 4-32, line 676) builds the tree of Expression objects shown in Figure 4-17, previously. The expr() method returns the RelationalExpression object at the root of the tree.

All this information is then passed to doSelect() (Listing 4-35, line 1137). This method first converts the table names to actual tables by looking up the names in the tables map. It then creates a Strategy object that the Table’s select() method can use to select rows and passes it into the primary table. Here’s the code for the Strategy object (from Listing 4-32, line -1):

As the Table processes the select() statement, it calls approve() for every row, which causes the anonymous Selector.Adapter to ask the root node in the expression tree to evaluate itself. (This ConcreteTable code is way back in Listing 4-17, line 384.)

The topmost node in the expression tree is a RelationalExpression, and the first thing that its evaluate(...) method (Listing 4-33, line 922) does is evaluate the subexpressions.

All of the Nonterminal Expressions start this way, in fact. In the current case, the left child of the root node is itself a RelationalExpression, so you’ll traverse the tree recursively down to the AtomicExpression at the far left.

The AtomicExpression’s evaluate(...) method (Listing 4-33, line 1008) just delegates to the contained Value, in this case an IdValue, so go to its value(...) method (Listing 4-34, line 1119). This method looks up the value of the last column on the current row of the people table and returns its value as a StringValue (shown in Figure 4-17 as an upward-pointing error on the edge leading into the AtomicExpression node). The RelationalExpression object that called the AtomicExpression’s evaluate(...) method now calls evaluate on its right child and gets back a StringValue that holds the String "Flintstone". It compares the two strings and creates a BooleanValue object that holds the result of the comparison and then returns that BooleanValue object. The code looks like this:

The remainder of the RelationalExpression’s evaluate() method doesn’t come into play in this scenario, but it handles the evaluation of relational operators that have numeric or null operands.

The remainder of the expression evaluation proceeds in the same fashion. The evaluate() call gets Value objects from the child nodes, evaluates those values appropriately, and returns a Value that holds the result. By the time you finish with the evaluate() method of the root node, you will have evaluated the entire expression.

The select() method is the most complex of the methods in Listing 4-35. The others work in pretty much the same way, however. They create a Selector that invokes the execute(...) method of the root node of the WHERE-clause expression tree, and the Selector approves or rejects rows by running the interpreter. The remainder of Listing 4-35 is a small unit-test class that runs the SQL script in Listing 4-27.

One other aspect of the doSelect(...) method at the top of Listing 4-35 (p. 316) bears mentioning. Here’s a stripped-down version of the call to the Table’s select() method with the interesting code in bold:

What’s that ThrowableContainer doing? The interface defined by Table and Selector is very generic by necessity. The approve() method, for example, is not declared as throwing any sort of exception because it’s impossible to predict what that exception may be.

The evaluate() method called in approve() throws a ParseFailure object, and ParseFailure is a checked exception—I have to deal with it. I want that exception toss to propagate out of approve(...), but to do that, I’d have to add a throws ParseFailure to the approve(...) declaration. The compiler will then (quite rightly) complain, because the definition of approve() in the Selector interface is not declared as throwing any sort of exception at all. I don’t want to append a throws ParseFailure the approve() definition in the Selector, however. A ParseFailure exception is used by the current parser only; it is irrelevant to all other implementers of Selector, and I don’t want to couple the Table/Selector interfaces to the SQL-interpreter layer.

I’ve solved the problem with the ThrowableContainer class in Listing 4-36. This class is quite simple; it’s nothing but a RuntimeException subclass that holds a Throwable object. The approve(...) method packages the ParseFailure exception into the container and then throws the container. The catch clause that surrounds the select(...) call (which calls approve(...)) catches the container, unpacks the contained ParseException object, and then throws the ParseException object.

The ThrowableContainer is effectively performing what I think of as a lateral type conversion—sideways in the class hierarchy—not to a subclass or superclass type, but to a sibling type. It’s as if I have converted an ArrayList to a LinkedList.

The obvious downside of this wrapping strategy is that it subverts the type-safety system. For example, if doSelect(...) were behaving badly, it could just let the ThrowableContainer propagate out to the calling method rather than catching the container and throwing the contained object. The calling method wouldn’t have a clue what to do with the ThrowableContainer, however. Also on the downside is that I’ve converted a checked-exception object into a RuntimeException that is not checked, which defeats the whole purpose of checked exceptions. It would be a serious problem, in other words, if I didn’t convert the exception object back to its original type by unwrapping it.

These negatives are pretty severe. I’m willing to put up with them in the current code because the packaging and unpackaging operations all occur within a few lines of each other in the source code, so the code remains reasonably maintainable.

The JDBC Layer

You’ll be happy to hear that the hard part is over (whew!). All that’s left is writing a JDBC driver, which turns out to be a trivial enterprise. A few interesting applications of design patterns exist in the JDBC-driver code, however.

Most of the classes in the following discussion are mine. To make the discussion clear, however, I’ve set off any classes or interfaces that are part of Java by using their fully qualified class name (java.sql.Xxx). If you don’t see the (java.sql), then the class is one of mine.

Figure 4-18 shows the structure and patterns for the JDBC layer, and I’ll explain this diagram in depth over the course of this section.

Figure 4-18. The structure and patterns of the JDBC layer

If you’ve never used JDBC, the easiest way to learn it is to look at a simple application. Listing 4-37 is a small test program that’s a minor adaptation of the example in Sun’s JDBC documentation. I’ll explain this listing throughout the rest of this section.

Probably the most confusing part of using JDBC is the driver-management mechanism. The problem Sun is trying to solve is a single program that needs to talk to a heterogeneous set of databases. That is, you need to talk to Oracle, Sybase, and SQL Server in a single program, and each database has a different driver.

Sun’s solution is a little odd, however. The java.sql.DriverManager class is an everything-is-static Singleton whose job is, not surprisingly, to manage a set of JDBC drivers. Before you can use the java.sql.DriverManager, however, you have to bring the vendor-specific drivers into existence. These drivers typically register themselves with the java.sql.DriverManager when they’re loaded (code in the driver’s static initializer block does the registration). So you have to load the class files for all the JDBC drivers that you need to use before you use the java.sql.DriverManager. That loading is done by the forName() call at the top of main() (Listing 4-37, line 15), which loads the class file and brings an instance into existence, causing the static-initializer block to execute as a side effect.

The JDBC driver for the current implementation is the JDBCDriver class in Listing 4-38. There’s not much to it. The static-initializer block that registers the driver object with the java.sql.DriverManager is on line 18. The jdbcCompliant() override (Listing 4-38, line 43) is small but important. By returning false it tells the users of this driver that the driver is not fully JDBC compliant. In other words, it’s perfectly okay for a JDBC implementation to be minimal, as long as it announces this to the world. As you’ll see in a moment, attempts to call unsupported methods in this minimal implementation result in an exception toss. Unfortunately, there’s no standard for “minimal,” so every driver has to document operations it supports. No “introspection” mechanism exists that you can use to find this information at runtime.

The other critical method is the acceptsURL(...) method on line 27 of Listing 4-38. To see why, go back to line 21 of Listing 4-37, reproduced here:

All calls to a database start out by getting a java.sql.Connection to that database from the java.sql.DriverManager—you can’t talk to the database at all without a connection to it. To get a java.sql.Connection object that represents the connection, you call DriverManager.getConnection() with three arguments: a URL that typically specifies both the database type (MySQL, PostgreSQL, and so on) and the name of the database, along with a username and password. My code just uses a simple “file:” URL with no database-identifying prefix, but a more realistic example may look like this:

Everything between the first colon and the equals sign specifies what sort of driver to use; the remainder of the URL identifies the server and port number on which the database resides and the name of the database itself.

The java.sql.DriverManager chooses the correct driver using the Chain-of-Responsibility pattern. It keeps a list of registered drivers, and when you request a connection, it passes each driver in the list an acceptsURL(...) message. As you can see in the version in Listing 4-38 (line 27), all this method typically does is examine the first part of the URL and report true if the current database is described. The PostgreSQL driver probably implements the method as follows:

Once the java.sql.DriverManager has identified the correct driver, it requests a connection by calling the driver’s connect() method. The current implementation is on line 31 of Listing 4-38. As you can see from Figure 4-18 (on p. 326), the JDBCDriver (up at the top of the picture) is both an Abstract java.sql.Connection Factory and a Chain-of-Responsibility Handler.

The next step in the JDBC process is to create a java.sql.Statement object that encapsulates the SQL processing. You get a java.sql.Statement from a java.sql.Connection and then use the java.sql.Statement to issue a SQL request like this:

A java.sql.Connection is an Abstract java.sql.Statement Factory, which is interesting because the single class serves in different roles in two separate reifications of Abstract Factory. JDBConnection is a Concrete Product (created by the JDBCDriver factory) in one reification and a Concrete Factory (of java.sql.Statement objects) in the other. Looking at Figure 4-11, you’ll see that the same dual participation occurs with several other JDBC classes as well. A JDBCDriver is a factory of JDBCConnection objects, which are, in turn, JDBCStatement factories, which are themselves JDBCResultSet factories.

The JDBCConnection class that I’ll describe in the following section (in Listing 4-40) implements the java.sql.Connection interface, but it does so indirectly. JDBCConnection extends com.holub.database.jdbc.adapters.ConnectionAdapter (in Listing 4-39), which implements java.sql.Connection. The ConnectionAdapter class implements all the interface methods with versions that throw exceptions. It provides a way of not cluttering up the real code with methods that aren’t implemented. I’ve used the same strategy to handle unsupported methods in the java.sql.ResultSet, java.sql.ResultSetMetaData, and java.sql.Statement interfaces. The ResultSetAdapter, ResultSetMetaDataAdapter, and StatementAdapter classes implement the matching interface with methods that do nothing but throw an exception. I haven’t bothered to provide listings for these classes here, but they’re in the source code on the web site.

The State Pattern and JDBCConnection

The JDBCConnection class (Listing 4-40) serves as a wrapper for the Database class. It implements that part of the JDBC bridge that represents the database itself. The Database object is created by the JDBCConnection constructors, and the database contents are dumped to disk when the connection is closed.

Most of the methods of JDBCConnection implement JDBC’s rather odd (to me) transaction mechanism: When you set auto-commit mode off by calling setAutoCommit(false), the system issues a BEGIN request. Subsequent calls to commit() or rollback() issue the matching SQL and then issue another BEGIN request. No begin() method exists. If you never call setAutoCommit(false), then every SQL request you issue is treated as a transaction and cannot be rolled back. JDBC does not support nested transactions. Nonetheless, you can ignore all the methods I’ve just been discussing and do transactions using executeUpdate(...) to issue BEGIN, COMMIT, and ROLLBACK requests at the SQL level.

I’ve implemented the auto-commit behavior using the Gang-of-Four State pattern, pictured in Figure 4-19. The State pattern provides a way of organizing a class whose objects change behavior when they change state. In the current example, the behavior of four methods (close(), commit(), rollback(), and setAutoCommit(...)) changes, depending on whether the connection is in the auto-commit-enabled state.

The naïve way to implement behavior that changes with state is to put a field in the class that indicates the current state and then put a switch statement or equivalent in every method, with the state-related behavior put into the case statements. Here’s a simplistic example:

Figure 4-19. The State pattern in com.holub.database.jdbc.JDBCConnection

This approach has two problems. First, all those switch statements add a lot of clutter to the code and make it hard to read. Second, the code is inherently difficult to maintain since the behavior associated with a given state is scattered all over the class definition. Changing the underlying state machine (the rules that determine how you get from one state to another and definitions of the behavior associated with each state) is particularly difficult.

The State pattern solves both problems. Here’s the structure:

First create an interface that contains definitions for those methods whose behavior changes with state. I’ve done that in Listing 4-40 with the AutoCommitBehavior interface on line 104. In the State pattern, this interface has the role of State.

Next, implement that interface as many times as there are states. Each implementation defines the behavior associated with one and only one state. In Listing 4-40, the auto-commit-enabled behavior is defined in the anonymous inner class assigned to enabled on line 111; the auto-commit-disabled behavior is defined in the anonymous inner class assigned to disabled on line 124. In the State pattern, these implementers of the State have the role of Concrete State.

Next, define a variable that points at an object representing the behavior associated with the current state. I’ve done that with the autoCommitState field declared on line 165 in Listing 4-40.

Finally, in the methods whose behavior changes with state, you delegate to the object that represents the current-state’s behavior. For example, rollback() (on line 143 of Listing 4-40) just calls autoCommitState.rollback(). The class that uses the State objects (the JDBCConnection) has the role of Context in the pattern.

In the current implementation, state changes are accomplished by the setAutoCommit() calls in the Concrete State objects. The pattern does not require that you change state in this particular way, however.

As a final observation on State, you often find State and Proxy combined. Consider a proxy for a slowly loading object such as Java’s Image class. (To remind you, the getImage() method returns a proxy for the real image that is being downloaded slowly in the background. You can use the Image proxy even before the entire actual image has been pulled across the network.) This sort of Proxy can be in two states (Real Subject available and Real Subject unavailable), and you can use the State pattern for the code that handles these states.

Statements

As you saw earlier, you issue a SQL request through a java.sql.Statement object that is manufactured by the java.sql.Connection’s createStatement() call. (The version on line 64 of Listing 4-41, discussed next, just hides a call to new.)

The JDBCStatment class (my implementation of java.sql.Statement) is laid out in Listing 4-41. There’s not much to it. The executeUpdate(...) method is used for all SQL statements that don’t return a value (everything except a SELECT); executeQuery(...) is used for SELECT. Both methods just delegate to the underlying Database object, though executeQuery(...) wraps in a java.sql.ResultSet object the Cursor across the rows of the Table object that holds the query results.

The Adapter Pattern (Result Sets)

The only Gang-of-Four design pattern I haven’t yet covered is Adapter, and the JDBCResultSet class has an example of it (Listing 4-42). Figure 4-20 shows the generalized form of the pattern.

Figure 4-20. Object and class forms of Adapter

The term Adapter stems from an electrical adapter. You want to plug your 110v-60Hz-3-prong-plug radio into a European 220v-70Hz-2-cylindrical-prong outlet, so you use an adapter. This way, your radio’s interface to the power system appears to be the interface that the power system expects. Adapting this notion to software (so to speak), an Adapter makes an existing object of some class appear to implement an interface that it doesn’t actually implement (a “foreign” interface).

In the current situation, no difference really exists at all between a Cursor and a java.sql.ResultSet, at least in terms of core functionality. The JDBCResultSet class wraps a Cursor object so that the Cursor object can appear to implement the JDBCResultSet interface. The JDBCResultSet is an Adapter that makes a Cursor (the Adaptee) implement a foreign (or Target) interface (the java.sql.ResultSet).

Another example of Adapter is the ArrayIterator class (in Listing 4-10) you saw earlier. This Adapter lets you access an array as if it implements the Iterator interface.

The flavor of Adapter characterized by JDBCResultSet—which uses a wrapping strategy—is called an Object Adapter. Adapter has two other flavors, one identified by the Gang of Four and another that they don’t talk about but is worth examining. A Class Adapter uses extends relationships rather than wrapping.

If the Results class (the Concrete Class implemented by the Cursor returned from the ConcreteTable) was public, I could implement a Class-Adapter version of JDBCResultSet like this:

Class Adapters do have the advantage of simultaneously being the Adapter and Adaptee. (I could pass a ClassAdapterResultSet object to a method that took a Result or Cursor argument, and I could also pass it to a method that took a ResultSet argument.) Nonetheless, I haven’t used them much in practice, primarily because of the overhead of creating one. That is, if you have a Cursor in hand, and you need a JDBCResultSet, you must copy all the state data from the Cursor object to the JDBCResultSet object if it’s a class adapter. This copying also usually mandates a tight coupling relationship that makes me uncomfortable.

A third possibility would work just fine in the current context. I think of it as an Interface Adapter (not a Gang-of-Four variant of Adapter). Since the Results object implements Cursor, I could get the advantages of both the Class- and Object-Adapter forms like this:

This way, I’m still using containment rather than implementation inheritance, so none of the copying and the tight coupling that the copying implies is required. I implement both the Target and Adaptee interfaces, however, so I have the flexibility of the Class Adapter. You obviously can’t use this form of Adapter if the Adaptee doesn’t implement a well-defined interface.

The only use of Adapter in the Java libraries that comes to mind are the I/O system adapters, some of which were shown in Figure 4-9. A StringBufferInputStream, for example, is adapting StringBuffer so that it appears to implement the InputStream interface. StringBufferInputStream effectively changes the interface to a StringBuffer so that it can be treated as an InputStream.

The Java libraries don’t have many other Adapters, primarily because Adapters are usually used to force-fit a library into an existing context. You’ll typically find them in the code that uses the library, not in the library itself. Let’s say, for example, that you had written an application that used AWT for its user interface and that your boss suddenly announced that AWT was garbage, and you had to reimplement the application in terms of some off-the-wall library written by your boss’s brother-in-law. Refactoring 100,000 lines of code is one possibility, but it’s easier to write a set of Adapters that make the brother-in-law library appear to be AWT. This way you don’t have to rewrite your existing code.

People often confuse Bridge and Adapter. Keep things straight by keeping the intent of the pattern in mind. The point of Bridge is to isolate subsystems. The point of Adapter is to shoehorn a class into a program that was written in terms of an interface that the class doesn’t implement. Also, Bridges are big things, and Adapters are little things.

People also confuse Adapters and Decorators since they’re both wrappers. The point of a Decorator, however, is to change the behavior of one or more methods of some class without using extends. In terms of structure, a Decorator will always implement the same interface as the object it’s decorating. An Adapter probably won’t implement the interface of the wrapped object (though it may).

Getting back to the JDBC-layer code, the JDBCResultSet class (in Listing 4-42) is interesting in that it’s a true Gang-of-Four Object Adapter. It makes objects that implement Cursor appear to implement the ResultSet interface. For example, it changes the name of the advance() method to next(), and it hides the generic column(...) method (which gets a specified column of the current row) in a set of methods that get the column and do a type conversion as well (getString(), getDouble(), and so on). It also provides a few type-safe updatexxx() methods. These database accessors are useful in that they provide a modicum of type safety when the underlying system provides no type safety at all. (The Table stores everything as an Object, and the Database stores everything as a String.)

One final word on the subject of adapters is in order. My earlier use of the word Adapter in the JDBC-interface-implementation-class names (for example, ConnectionAdapter) is somewhat misleading. I’ve used the word Adapter because Java uses a similar default-implementation-that-does-nothing strategy in the AWT event model, and all those classes are called Adapters. (For example, MouseAdapter implements MouseListener.) These “Adapter” classes are not Adapters in the design-pattern sense of a class that makes an object appear to implement a foreign interface. This use of “Adapter” is just an unfortunate Java naming convention.

Finishing Up the Code

The final implementation class is JDBCResultSetMetaData in Listing 4-43, which normally provides metadata information about the columns. Since there is no typing in the current implementation, all columns are treated as a SQL VARCHAR.

When Bridges Fail

The JDBC layer that you’ve been looking at is another example of the Bridge pattern discussed earlier (in “The Bridge Pattern” section). You’re seeing only the implementation half of the Bridge, however (see Figure 4-4, on p. 199). As a Bridge, JDBC does serve to isolate your code from some of the problems that can emerge when you change databases.

JDBC is also a good example of how the Bridge pattern can fail, however. The problem is the SQL itself. Every database seems to use a different dialect of SQL, which is an enormous problem from a portability perspective. The whole point of Bridge is to replace some subsystem (for example, a database) with a completely different implementation (for example, a different database) without impacting your application code. You can certainly replace a SQL Server driver with a PostgreSQL driver with no difficulty. Unfortunately, though your code will still compile just fine, it probably won’t work anymore because PostgreSQL won’t recognize the SQL Server SQL dialect.

This problem has some solutions, but nobody has implemented them. One solution is to eliminate SQL altogether and provide a set of methods in the Bridge that does everything that you would normally do with SQL. A conforming driver would then have to implement these methods appropriately for its database. The main (significant) downside to this approach is that you can’t get a DBA to write SQL for you anymore; everything has to be done in Java.

A second “solution” is to require all drivers to support some defined standard SQL and to map this standard SQL to the native dialect as necessary. To really guarantee portability, the driver would also have to detect an attempt to issue a nonstandard SQL request and refuse to execute the request. The problem with this approach is a practical one. Most databases support a host of useful nonstandard features, and it’s often these nonstandard features that drive the decision to adopt a particular database. It’s simply not practical or appropriate to prevent a user of JDBC from using the very features that led him or her to select a particular database. It’s true that there’s a nontrivial common intersection between major SQL dialects, but you have to give up too much if you restrict yourself to that subset.

The same problem exists with the AWT bridge I mentioned earlier in the chapter. In both the JDBC and AWT case, you can even change runtime environments (or databases) on the fly as the program works. You certainly don’t have to recompile if you’re using a Bridge. However, as with JDBC, the behavior of the UI under AWT will change with the new environment, and things that used to work don’t work anymore. People used to jokingly call AWT the Write-Once-Test-Everywhere environment (as a foil to Sun’s Write-Once-Run-Everywhere slogan). The fact that Bridge rarely gives you complete isolation between subsystems is not insurmountable. Eclipse’s SWT library uses the Bridge pattern more effectively than did AWT, for example, primarily by making the Bridge so powerful that nobody needs to use OS-specific features. It is difficult to achieve true independence between subsystems, however.

Whew!

So, that’s all of the Gang-of-Four design patterns, all tangled together in two programs. As I said back in the preface, this is the way the patterns appear in the real world, and I hope you’ll develop a better understanding of the patterns by looking at them in a realistic context than you would by looking at a catalog. (Nonetheless, I’ve provided a catalog as an Appendix so that you can have a quick pattern reference.)

You’ll find two things start to happen as you become more familiar with the patterns. First, it will be a lot easier to talk about your code to other pattern-savvy programmers. It’s a lot easier to say “this is a Visitor” than it is to describe the structure of the code every time you talk about it.

The second emanation of pattern savvy is more important. As you build a mental catalog of not only the Gang-of-Four patterns but also the myriad other patterns that are documented in the literature, you’ll find that you code more effectively. You’ll be able to see where a pattern applies before you write the code and then write it “right” from the beginning.

So, go forth and program!