C++ Visitor Pattern: Motivation

The Visitor design pattern is perhaps not the best-loved of the GoF patterns. One indication of its unpopularity is its position as the last pattern in the GoF Design Patterns book. But I have found it useful in several projects, and would like to share some Visitor tricks I've learned along the way.

In C++, Visitor is an abstract base class, with a set of one-argument virtual functions -- one for each class in a forest of hierarchies -- thereby providing "multiple-dispatch" of some piece of functionality. Virtual functions are an example of single-dispatch: based on the type of an object, the correct virtual function is called. Multiple-dispatch means that a function is selected based on more than one type: in this case, the type of the visitor, and the type of the class it visits.

Have you ever been writing some code, and thought: "I wish I could add a virtual function to these classes, without changing the class interfaces"? If so, that is exactly what Visitor allows. Of course, you have to have designed the class to accept a Visitor first, but after that, you have this "external virtual function" capability.

Another way in which Visitor is helpful in big C++ projects, is that it allows you to have good source file hygiene -- as described in our coding standard -- but still keep related functionality in one place. An example is pretty-printing of an Expression hierarchy: to make consistency easier to maintain, you would like all the printing functions to be in a single file, which would violate our source file standards if implemented by virtual functions in the classes.

Sounds good, why is Visitor unpopular? There are a couple of valid complaints about the pattern. First, it can make for difficulties when adding a new class to a visited hierarchy. This is somewhat mitigated by the Default Visitor variant, and we can also use some preprocessor tricks to create a compile- or link-time error for Visitors which must be extended for some or all new classes. It's also worth mentioning that if the Visitor functionality were instead implemented as a pure virtual function, the same amount of work is required (except for tracking down all the Visitors).

Secondly, effective use of Visitors may imply a loss of encapsulation. If a Visitor is to do meaningful work on an object, it may need access to implementation details that -- all other things being equal -- we would prefer to hide inside the class.

Nevertheless, Visitor can be a very useful design pattern. In coming posts I will present some practical C++ examples for getting the most out of it.

Here is the complete list of posts in this series:

• C++ Visitor Pattern: Motivation (this post)
• C++ Visitors: Basic Implementation
• Easier-to-Use C++ Visitor
• The Default Visitor Idiom
• Handy C++ Visitor Macros

Getting Back to Where You Were in Emacs

When you do an interactive search in emacs (e.g.: C-s or C-r), the mark is set at the place you began your search. So when you're ready to go back to the editing you were doing when you started searching, a simple C-x C-x (exchange-point-and-mark) gets you back to where you were.

That's so second-nature to me that I am always a little surprised when C-x C-x doesn't take me where I expect, as can happen when you light one search off the end of another, or find yourself in another file. So here are a couple of tricks to try when C-x C-x fails you:

Double Undo: Usually the place you want to get back to is the place you've just been typing in the current file. So an undo -- C-x u -- will snap the window back to that spot as it undoes your recent typing. But you didn't want to undo that, so you have to "undo the undo". Successive C-x u commands just undo more and more, so first break the cycle by issuing some innocuous command -- I like to use C-n (next-line) -- followed by a second C-x u. In case that's confusing, the sequence is: C-x u C-n C-x u. Of course, that only works if you didn't change files while you were off searching.

Pop Global Mark: The command pop-global-mark -- C-x C-SPC -- is a power tool to center the window at a recent mark, no matter what file it was in. This is especially handy if your searching and grepping takes you across several files, or if you can't remember which file you were working in. Just keep popping marks until the file and location you want shows up. This command sometimes fails you, if the place you're trying to return to never had a mark set because you never started a search from there. If you know you're about to embark on a scavenger hunt and will want to return, set the mark explicitly -- C-SPC -- before you begin.

Oh yeah, don't forget point-to-register!

Emacs Repeat Command

One of the handiest commands in emacs is repeat-complex-command (shortcut: M-x ESC ESC). It opens in the minibuffer the lisp formulation of the last command you ran, for example:

Redo: (query-replace "j" "k" nil nil nil)

That way, if you just want to redo that thing you did, hit return. If you want to slightly modify it -- change "k" to "m", for example -- just edit the command before pressing return. Not very interesting in the "k" to "m" case, but if you run query-replace-regexp and then realize you got one tiny thing wrong in a huge regular expression, well, you can see that would be useful.

Sometimes the thing that comes up in the minibuffer isn't something worth repeating:

Redo: (find-file-other-window "~/.emacs" 1)

In that case, just use the minibuffer history (M-p, M-n) to get to the command you're looking for.

Gotcha: I scratched my head for a few minutes today wondering why nothing happened when I re-ran a replace-string. If your replace command is restricted to a region, the bounds of that region are present in the lisp command. So when you try to redo it, it redoes it for your old region -- not the current one. Best case for that is a no-op; worst case is changing a region you didn't want to. Be careful when redoing any command that might apply only to the region.

Open Your Eyes!

Here's a sweet piece of code (names have been changed to protect the guilty):

if (calculated_condition == some_test()) {
  // Ancient comment.
  // T intermediate = partial_value(val);
  // calculated_val = more_calculations(intermediate);
  // Merely elderly comment.
  // calculated_val = better_calculations(val);
  calculated_val = val;
}
else {
  calculated_val = val;
}

Good lord! Maybe if there wasn't a compulsion to comment out old code, it would have been clearer what was happening here, and this would have been replaced with the one-liner. Instead, a few years later I have to spend a couple minutes reading the whole thing, maybe pausing right at the beginning to figure out when the condition is met, only to find that none of it matters.

It's even more fun when several lines of code are commented with a single "/*", or the hated "#if 0". Then as you're grepping to figure out where something decrepit like more_calculations() is used, it looks like it's used in hundreds of places.

Delete dead code!

C++ Coding Standard: Complete

Over the course of several weeks, I presented 12 sections of a C++ coding standard, along with some rationalizing verbiage. For your convenience, here is is in one shot, with no adornment.

The standard may be food for thought for you; or you might find it laughably pompous or incomplete. But I hope that you'll get your team to agree to some written standard, and use it to speed code reviews by letting reviewers make their points with little more than a chapter and verse -- something like "line 435 violates 3.8".

• 1. Source files.
  • 1.1. Every class must have a header file called "{class}.hpp".
  • 1.2. Every class must have an implementation file called "{class}.cpp".
    • 1.2.1. Exception to 1.2: template class with only inline members.
    • 1.2.2. Exception to 1.1 and 1.2: class in anonymous namespace.
  • 1.3. {class}.hpp and {class}.cpp must be in the same directory.
  • 1.4. {class}.hpp must define one and only one class.
    • 1.4.1. Exception to 1.4: nested classes or structs.
  • 1.5. Filenames must match the class names exactly, including case.
• 2. Header file layout.
  • 2.1. Header files must begin with the standard C++ file comment.
  • 2.2. Then comes the "#ifndef" of the include guard.
  • 2.2.1. Guard macro format _<DIR>_<CLASS>_H (all caps).
  • 2.3. Then include directives and external class declarations (optional).
  • 2.4. Then outside-the-class typedefs (optional).
  • 2.5. Then the class definition.
  • 2.6. Then other interface declarations (optional).
  • 2.7. Then inline function definitions (optional).
  • 2.8. Then the "#endif" of the include guard.
• 3. Header file contents.
  • 3.1. A .hpp must never include an implementation file.
  • 3.2. A .hpp must include every file needed to compile itself.
  • 3.3. A .hpp must not include files not needed to compile itself.
  • 3.4. Class definitions must be preceded by a documentation comment.
  • 3.5. Function declarations must be preceded by a documentation comment.
    • 3.5.1. Document function pre- and postconditions when relevant.
  • 3.6. A .hpp must not declare variables or constants outside the class.
  • 3.7. A header file must not declare functions outside the class.
    • 3.7.1. Exception to 3.7: operators or template specializations may sometimes be declared outside the class.
  • 3.8. A header file must not use "using namespace" directives.
  • 3.9. Any functions declared in the .hpp which are to be inline, must be defined in the .hpp.
• 4. Implementation file layout has only a few restrictions.
  • 4.1. Implementation files must begin with the standard C++ file comment.
  • 4.2. The first non-comment line of {class}.cpp must be: #include "{class}.hpp".
  • 4.3. {class}.cpp definitions should be in the same order as {class}.hpp declarations.
• 5. Implementation file (.cpp) contents.
  • 5.1. A .cpp must never include an implementation file.
  • 5.2. A .cpp must not include files not needed to compile itself.
  • 5.3. Every non-inline function declared in {class}.hpp must be defined in {class}.cpp.
    • 5.3.1. Exception to 5.3: copy constructor and assignment operator may be declared private and not implemented, to override C++ defaults.
  • 5.4. Every static member variable declared in {class}.hpp must be defined in {class}.cpp.
  • 5.5. Anything defined in {class}.cpp which is not declared in {class}.hpp must be in the anonymous namespace.
  • 5.6. Every anonymous namespace function must be preceded by a documentation comment.
• 6. Class design.
  • 6.1. Non-static data members must be private.
  • 6.2. A class must implement at least one public constructor.
  • 6.3. A class must declare its copy constructor and assignment operator.
    • 6.3.1. Exception to 6.3: not if declared private in base class.
  • 6.4. Member functions which do not change data members must be declared "const".
  • 6.5. Protected members should not be used.
  • 6.6. Consider changing private member functions to anonymous namespace functions in the implementation file.
  • 6.7. Classes must not declare "friend" classes.
  • 6.8. Classes should not declare "friend" functions for non-inline functions.
  • 6.9. Declare blank constructor if and only if a client needs it.
  • 6.10. Consider calculating data instead of storing it.
  • 6.11. Data members allocated on the heap must have type auto_ptr<T> or boost::shared_ptr<T>.
  • 6.12. Member functions marked "const" must be idempotent.
• 7. Class layout.
  • 7.1. All public things first, then all protected, then all private.
  • 7.2. Within a public or private section, use the following order:
    • 7.2.1. First any nested type definitions or typedefs.
    • 7.2.2. Then constructors, destructors, and the assignment operator.
    • 7.2.3. Then any const member functions.
    • 7.2.4. Then any non-const member functions.
    • 7.2.5. Then any static member functions.
    • 7.2.6. Then any data members.
  • 7.3. Define inline functions outside of the class definition.
• 8. Inheritance.
  • 8.1. Public inheritance must only be used to model the "is a" relation.
  • 8.2. Use private and protected inheritance sparingly, and only to model the "looks like a" relation.
  • 8.3. Only inherit publicly from an abstract base class.
  • 8.4. Destructors of public base classes must be pure virtual (but implemented).
  • 8.5. Don't use multiple inheritance.
• 9. Preprocessor issues.
  • 9.1. Preprocessor macros should be rarely used.
    • 9.1.1. Obvious exception to 9.1: multiple-include guard.
    • 9.1.2. Use enum constants instead of constant macros.
    • 9.1.3. Use inline functions instead of function macros (when possible).
  • 9.2. Never use a macro to invent new syntax.
  • 9.3. Conditional compilation should be rarely used.
  • 9.4. Operating system #includes use angle brackets, e.g. <unistd.h>.
  • 9.5. Non-operating system #includes use double quotes, e.g. "Object.hpp".
  • 9.6. Use the standard C++ system header files, e.g. <string> not <string.h>.
• 10. Naming conventions.
  • 10.1. Constant names must be in all caps.
  • 10.2. Private data and function member names must begin with '_'.
  • 10.3. Type names must begin with a capital letter.
  • 10.4. Function macro names must be in all caps.
  • 10.5. Names not covered above must begin with a lower-case letter.
  • 10.6. Do not use underscores and mixed-case in a single name.
  • 10.7. Typedefs must not obscure the fact that a type is a pointer, reference, or array type.
  • 10.8. All class definitions must be within a namespace.
• 11. Function design.
  • 11.1. Constructors must initialize all data members in the initialization list, and in the order they're declared in the class definition.
  • 11.2. Class member functions which return a pointer or reference to a data member, must return it as "const T*" or "const T&".
  • 11.3. A class function must not deallocate memory that was allocated outside of the class implementation file.
  • 11.4. A class destructor must deallocate all of the memory allocated for data members of the instance.
  • 11.5. Function arguments which are pointer, array, or reference types, which are not changed by the function, must be declared "const".
  • 11.6. A function must contain at most one "return" statement.
  • 11.7. Do not use "goto" or "continue".
  • 11.8. Only use "break" in switch statements.
  • 11.9. Declare variables at the latest possible location.
  • 11.10. Use assert() to check for programming or interface errors.
  • 11.11. Functions with "true/false" semantics must return "bool".
  • 11.12. Declare default arguments in the .hpp file, not the .cpp file.
  • 11.13. Pass objects (especially containers) by (const) reference, not value.
  • 11.14. Return objects (especially containers) by value, unless it makes sense to return a const reference.
  • 11.15. Exceptions must be caught by reference, not by value or pointer.
  • 11.16. When re-throwing an exception, use "throw;", not "throw ex;".
  • 11.17. Destructors must catch all exceptions and throw none.
  • 11.18. Exception specifications must not be used.
    • 11.18.1. Exception to 11.18: a destructor which catches all exceptions can be marked with "throw()".
• 12. Other stylistic issues.
  • 12.1. Mark 64-bit constants "LL" or "ULL", e.g. 0xffffffffffffffffULL.
  • 12.2. Mark 32-bit constants >= 0x80000000 "U", e.g. 0xffffffffU.
  • 12.3. Use C++-style typecasts instead of C-style typecasts.
  • 12.4. A source file must not include tab characters (only spaces).
  • 12.5. Lines must contain no more than 80 characters, including the (invisible) newline character at the end.
  • 12.6. A source line must not contain two statements.
  • 12.7. Use 2 spaces per level of indentation.
  • 12.8. Indent the body of a compound statement ("if", "while", etc.) one level more than the head of the statement.
  • 12.9. An "else" must have the same indentation as its "if".
  • 12.10. Two statements in a sequence must have the same indentation.
  • 12.11. A comment is indented the same as the statement following it.
  • 12.12. No character must appear to the right of a brace ("{" or "}").
  • 12.13. A closing right brace must be indented to the same level as the line containing its corresponding left brace.
  • 12.14. There must be no space between the function name and the left parenthesis of a function call (e.g. "printf(...)").
  • 12.15. There must be a space between a keyword and a left parenthesis (e.g. "if (x != NULL)").
  • 12.16. Do not use C-style comments (except for documentation comments).
  • 12.17. Do not comment out or "#if 0" dead code. Remove it.
  • 12.18. Do not use external include guards.

Tcl is Still a Toy Language

Let's extend the chain of complaints about Tcl.

6. Expressions sometimes have to be wrapped in [expr {}], but not always:

if { $x == "a" || $x == "b" } {
  return [expr {$x == "a"}]
}

7. Variable argument lists are handled with a special argument name: "args". It's not a keyword, just a variable treated differently from every other variable. That's just demented.

Stupid, stupid makedepend

One of the most frustrating, time-wasting debugging experiences you can have is when the code you thought you compiled didn't really get compiled. Or something you didn't even think about because someone else updated it didn't get compiled.

This is why the utility makedepend was introduced, so that compile dependencies get taken care of automatically, every time. So why is the Linux makedepend so stupid that it doesn't work every time?!?!

In the interest of speed, the Linux makedepend was written to parse include files only once per run (usually this is per directory). That's usually OK, but when the include file is preprocessed differently by different files (or multiple times in one file), it doesn't work. I thought the first rule of optimization was: make the common case fast, but make every case work.

Moral: use the dependency scheme described in the GNU make info pages. It goes like this:

# In the variables area:
sources = foo.cpp bar.cpp ...
OBJS = $(sources:.cpp=.o)

# In the targets area, somewhere after "all:"
ifneq ($(MAKECMDGOALS),clean)
include $(sources:.cpp=.d)
endif

%.d: %.cpp
  @(set -o pipefail; \
    $(CXX) -MM $(CXXFLAGS) $< \
     | sed 's,\($*\)\.o[ :]*,\1.o $@ : ,g' \
      > $@;) || $(RM) $@

Of course this assumes that CXX = g++. By the way, that little gem about not building the dependencies during "clean" is in the info pages, but not the page that describes the generic dependency rules. Yes, I have read every make info page.

The "pipefail" bit is my own little contribution; it saves you some headaches when the g++ command fails when you're not watching, because the sed command will succeed and allow make to continue ignorantly on its way. That's a bash option, so it might not work on platforms other than Linux.