Chapter 25: Concrete Examples

In this chapter concrete examples of C++ programs, classes and templates are presented. Topics covered by the C++ Annotations such as virtual functions, static members, etc. are illustrated in this chapter. The examples roughly follow the organization of earlier chapters.

As an additional topic, not just providing examples of C++ the subjects of scanner and parser generators are covered. We show how these tools may be used in C++ programs. These additional examples assume a certain familiarity with the concepts underlying these tools, like grammars, parse-trees and parse-tree decoration. Once the input for a program exceeds a certain level of complexity, it's attractive to use scanner- and parser-generators to create the code doing the actual input processing. One of the examples in this chapter describes the usage of these tools in a C++ environment.

25.1: Using file descriptors with `streambuf' classes

25.1.1: Classes for output operations

Reading and writing from and to file descriptors are not part of the C++ standard. But on most operating systems file descriptors are available and can be considered a device. It seems natural to use the class std::streambuf as the starting point for constructing classes interfacing such file descriptor devices.

Below we'll construct classes that can be used to write to a device given its file descriptor. The devices may be files, but they could also be pipes or sockets. Section 25.1.2 covers reading from such devices; section 25.2.3 reconsiders redirection, discussed earlier in section 6.6.2.

Using the streambuf class as a base class it is relatively easy to design classes for output operations. The only member function that must be overridden is the (virtual) member int streambuf::overflow(int c). This member's responsibility is to write characters to the device. If fd is an output file descriptor and if output should not be buffered then the member overflow() can simply be implemented as:

    class UnbufferedFD: public std::streambuf
    {
        public:
            virtual int overflow(int c);
            ...
    };

    int UnbufferedFD::overflow(int c)
    {
        if (c != EOF)
        {
            if (write(d_fd, &c, 1) != 1)
                return EOF;
        }
        return c;
    }

The argument received by overflow is either written to the file descriptor (and returned from overflow), or EOF is returned.

This simple function does not use output buffering. For various reasons, using a buffer is usually a good idea (see also the next section).

When output buffering is used, the overflow member is a bit more complex as it is only called when the buffer is full. Once the buffer is full, we first have to flush the buffer. Flushing the buffer is the responsibility of the (virtual) function streambuf::sync. Since sync is a virtual function, classes derived from streambuf may redefine sync to flush a buffer streambuf itself doesn't know about.

Overriding sync and using it in overflow is not all that has to be done. When the object of the class defining the buffer reaches the end of its lifetime the buffer may be only partially full. In that situation the buffer must also be flushed. This is easily done by simply calling sync from the class's destructor.

Now that we've considered the consequences of using an output buffer, we're almost ready to design our derived class. Several more features are added as well, though:

First, we should allow the user of the class to specify the size of the output buffer.
Second, it should be possible to construct an object of our class before the file descriptor is actually known. Later, in section 25.2 we'll encounter a situation where this feature is actually used.

To save some space in the C++ Annotations, the successful completion of the functions designed here is not checked in the example code. In `real life' implementations these checks should of course not be omitted. Our class OFdnStreambuf has the following characteristics:

Its member functions use low-level functions operating on file descriptors. So apart from streambuf the <unistd.h> header file must have been read by the compiler before its member functions can be compiled.
The class is derived from std::streambuf.

It defines three data members. These data members keep track of, respectively, the size of the buffer, the file descriptor, and the buffer itself. Here is the full class interface

    class OFdnStreambuf: public std::streambuf
    {
        int     d_fd = -1;
        size_t  d_bufsize = 0;
        char   *d_buffer = 0;

        public:
            OFdnStreambuf() = default;
            OFdnStreambuf(int fd, size_t bufsize = 1);
            virtual ~OFdnStreambuf();
            void open(int fd, size_t bufsize = 1);
        private:
            virtual int sync();
            virtual int overflow(int c);
    };

Its default constructor merely initializes the buffer to 0. Slightly more interesting is its constructor expecting a file descriptor and a buffer size. This constructor passes its arguments on to the class's open member (see below). Here are the constructors:
```
    inline OFdnStreambuf::OFdnStreambuf(int fd, size_t bufsize)
    {
        open(fd, bufsize);
    }
```
The destructor calls sync, flushing any characters stored in the output buffer to the device. In implementations not using a buffer the destructor can be given a default implementation:
```
    inline OFdnStreambuf::~OFdnStreambuf()
    {
        if (d_buffer)
        {
            sync();
            delete[] d_buffer;
        }
    }
```
This implementation does not close the device. It is left as an exercise to the reader to change this class in such a way that the device is optionally closed (or optionally remains open). This approach was adopted by, e.g., the Bobcat library. See also section 25.1.2.2.

The open member initializes the buffer. Using streambuf::setp, the begin and end points of the buffer are defined. This is used by the streambuf base class to initialize streambuf::pbase, streambuf::pptr, and streambuf::epptr:

    inline void OFdnStreambuf::open(int fd, size_t bufsize)
    {
        d_fd = fd;
        d_bufsize = bufsize == 0 ? 1 : bufsize;
        delete[] d_buffer;
        d_buffer = new char[d_bufsize];
        setp(d_buffer, d_buffer + d_bufsize);
    }

The member sync flushes the as yet unflushed content of the buffer to the device. After the flush the buffer is reinitialized using setp. After successfully flushing the buffer sync returns 0:

    inline int OFdnStreambuf::sync()
    {
        if (pptr() > pbase())
        {
            write(d_fd, d_buffer, pptr() - pbase());
            setp(d_buffer, d_buffer + d_bufsize);
        }
        return 0;
    }

The member streambuf::overflow is also overridden. Since this member is called from the streambuf base class when the buffer is full it should first call sync to flush the buffer to the device. Next it should write the character c to the (now empty) buffer. The character c should be written using pptr and streambuf::pbump. Entering a character into the buffer should be implemented using available streambuf member functions, rather than `by hand' as doing so might invalidate streambuf's internal bookkeeping. Here is overflow's implementation:
```
    inline int OFdnStreambuf::overflow(int c)
    {
        sync();
        if (c != EOF)
        {
            *pptr() = c;
            pbump(1);
        }
        return c;
    }
```

The next program uses the OFfdStreambuf class to copy its standard input to file descriptor STDOUT_FILENO, which is the symbolic name of the file descriptor used for the standard output:

    #include <string>
    #include <iostream>
    #include <istream>
    #include "fdout.h"
    using namespace std;

    int main(int argc, char **argv)
    {
        OFdnStreambuf   fds(STDOUT_FILENO, 500);
        ostream         os(&fds);

        switch (argc)
        {
            case 1:
                for (string  s; getline(cin, s); )
                    os << s << '\n';
                os << "COPIED cin LINE BY LINE\n";
            break;

            case 2:
                cin >> os.rdbuf();      // Alternatively, use:  cin >> &fds;
                os << "COPIED cin BY EXTRACTING TO os.rdbuf()\n";
            break;

            case 3:
                os << cin.rdbuf();
                os << "COPIED cin BY INSERTING cin.rdbuf() into os\n";
            break;
        }
    }

25.1.2: Classes for input operations

When classes for input operation are derived from std::streambuf, they should be provided with an input buffer of at least one character. The one-character input buffer allows for the use of the member functions istream::putback or istream::ungetc. Strictly speaking it is not necessary to implement a buffer in classes derived from streambuf. But using buffers in these classes is strongly advised. Their implementation is very simple and straightforward and the applicability of such classes is greatly improved. Therefore, all our classes derived from the class streambuf define a buffer of at least one character.

25.1.2.1: Using a one-character buffer

When deriving a class (e.g., IFdStreambuf) from streambuf using a buffer of one character, at least its member streambuf::underflow should be overridden, as this member eventually receives all requests for input. The member streambuf::setg is used to inform the streambuf base class of the size and location of the input buffer, so that it is able to set up its input buffer pointers accordingly. This ensures that streambuf::eback, streambuf::gptr, and streambuf::egptr return correct values.

The class IFdStreambuf is designed like this:

Its member functions use low-level functions operating on file descriptors. Therefore, in addition to streambuf, the <unistd.h> header file must have been read by the compiler before its member functions can be compiled.
Like most classes designed for input operations, this class is derived from std::streambuf as well.
The class defines two data members, one of them a fixed-sized one character buffer. The data members are defined as protected data members so that derived classes (e.g., see section 25.1.2.3) can access them. Here is the full class interface:
```
    class IFdStreambuf: public std::streambuf
    {
        protected:
            int     d_fd;
            char    d_buffer[1];
        public:
            IFdStreambuf(int fd);
        private:
            int underflow();
    };
```
The constructor initializes the buffer. However, the initialization sets gptr's return value equal to egptr's return value. This implies that the buffer is empty so underflow is immediately called to fill the buffer:
```
    inline IFdStreambuf::IFdStreambuf(int fd)
    :
        d_fd(fd)
    {
        setg(d_buffer, d_buffer + 1, d_buffer + 1);
    }
```
Finally underflow is overridden. The buffer is refilled by reading from the file descriptor. If this fails (for whatever reason), EOF is returned. More sophisticated implementations could act more intelligently here, of course. If the buffer could be refilled, setg is called to set up streambuf's buffer pointers correctly:
```
    inline int IFdStreambuf::underflow()
    {
        if (read(d_fd, d_buffer, 1) <= 0)
            return EOF;

        setg(d_buffer, d_buffer, d_buffer + 1);
        return static_cast<unsigned char>(*gptr());
    }
```

The following main function shows how IFdStreambuf can be used:

    int main()
    {
        IFdStreambuf fds(STDIN_FILENO);
        istream      is(&fds);

        cout << is.rdbuf();
    }

25.1.2.2: Using an n-character buffer

How complex would things get if we decided to use a buffer of substantial size? Not that complex. The following class allows us to specify the size of a buffer, but apart from that it is basically the same class as IFdStreambuf developed in the previous section. To make things a bit more interesting, in the class IFdNStreambuf developed here, the member streambuf::xsgetn is also overridden, to optimize reading a series of characters. Also a default constructor is provided that can be used in combination with the open member to construct an istream object before the file descriptor becomes available. In that case, once the descriptor becomes available, the open member can be used to initiate the object's buffer. Later, in section 25.2, we'll encounter such a situation.

To save some space, the success of various calls was not checked. In `real life' implementations, these checks should of course not be omitted. The class IFdNStreambuf has the following characteristics:

Its member functions use low-level functions operating on file descriptors. So apart from streambuf the <unistd.h> header file must have been read by the compiler before its member functions can be compiled.
As usual, it is derived from std::streambuf.

Like the class IFdStreambuf (section 25.1.2.1), its data members are protected. Since the buffer's size is configurable, this size is kept in a dedicated data member, d_bufsize:

    class IFdNStreambuf: public std::streambuf
    {
        protected:
            int         d_fd = -1;
            size_t      d_bufsize = 0;
            char*       d_buffer = 0;
        public:
            IFdNStreambuf() = default;
            IFdNStreambuf(int fd, size_t bufsize = 1);
            virtual ~IFdNStreambuf();
            void open(int fd, size_t bufsize = 1);
        private:
            virtual int underflow();
            virtual std::streamsize xsgetn(char *dest, std::streamsize n);
    };

The default constructor does not allocate a buffer. It can be used to construct an object before the file descriptor becomes known. A second constructor simply passes its arguments to open. Open will then initialize the object so that it can actually be used:
```
    inline IFdNStreambuf::IFdNStreambuf(int fd, size_t bufsize)
    {
        open(fd, bufsize);
    }
```
Once the object has been initialized by open, its destructor will both delete the object's buffer and use the file descriptor to close the device:
```
    IFdNStreambuf::~IFdNStreambuf()
    {
        if (d_bufsize)
        {
            close(d_fd);
            delete[] d_buffer;
        }
    }
```
Even though the device is closed in the above implementation this may not always be desirable. In cases where the open file descriptor is already available the intention may be to use that descriptor repeatedly, each time using a newly constructed IFdNStreambuf object. It is left as an exercise to the reader to change this class in such a way that the device may optionally be closed. This approach was followed in, e.g., the Bobcat library.
The open member simply allocates the object's buffer. It is assumed that the calling program has already opened the device. Once the buffer has been allocated, the base class member setg is used to ensure that streambuf::eback streambuf::gptr and streambuf::egptr return correct values:
```
    void IFdNStreambuf::open(int fd, size_t bufsize)
    {
        d_fd = fd;
        d_bufsize =  bufsize == 0 ? 1 : bufsize;
        delete[] d_buffer;
        d_buffer = new char[d_bufsize];
        setg(d_buffer, d_buffer + d_bufsize, d_buffer + d_bufsize);
    }
```

The overridden member underflow is implemented almost identically to IFdStreambuf's (section 25.1.2.1) member. The only difference is that the current class supports buffers of larger sizes. Therefore, more characters (up to d_bufsize) may be read from the device at once:

    int IFdNStreambuf::underflow()
    {
        if (gptr() < egptr())
            return *gptr();

        int nread = read(d_fd, d_buffer, d_bufsize);

        if (nread <= 0)
            return EOF;

        setg(d_buffer, d_buffer, d_buffer + nread);
        return static_cast<unsigned char>(*gptr());
    }

Finally xsgetn is overridden. In a loop, n is reduced until 0, at which point the function terminates. Alternatively, the member returns if underflow fails to obtain more characters. This member optimizes the reading of series of characters. Instead of calling streambuf::sbumpc n times, a block of avail characters is copied to the destination, using streambuf::gbump to consume avail characters from the buffer using one function call:

    std::streamsize IFdNStreambuf::xsgetn(char *dest, std::streamsize n)
    {
        int nread = 0;

        while (n)
        {
            if (!in_avail())
            {
                if (underflow() == EOF)
                    break;
            }

            int avail = in_avail();

            if (avail > n)
                avail = n;

            memcpy(dest + nread, gptr(), avail);
            gbump(avail);

            nread += avail;
            n -= avail;
        }

        return nread;
    }

The member function xsgetn is called by streambuf::sgetn, which is a streambuf member. Here is an example illustrating the use of this member function with an IFdNStreambuf object:

    #include <unistd.h>
    #include <iostream>
    #include <istream>
    #include "ifdnbuf.h"
    using namespace std;

    int main()
    {
                                    // internally: 30 char buffer
        IFdNStreambuf fds(STDIN_FILENO, 30);

        char buf[80];               // main() reads blocks of 80
                                    // chars
        while (true)
        {
            size_t n = fds.sgetn(buf, 80);
            if (n == 0)
                break;
            cout.write(buf, n);
        }
    }

25.1.2.3: Seeking positions in `streambuf' objects

When devices support seek operations, classes derived from std::streambuf should override the members streambuf::seekoff and streambuf::seekpos. The class IFdSeek, developed in this section, can be used to read information from devices supporting seek operations. The class IFdSeek was derived from IFdStreambuf, so it uses a character buffer of just one character. The facilities to perform seek operations, which are added to our new class IFdSeek, ensure that the input buffer is reset when a seek operation is requested. The class could also be derived from the class IFdNStreambuf. In that case the arguments to reset the input buffer must be adapted so that its second and third parameters point beyond the available input buffer. Let's have a look at the characteristics of IFdSeek:

As mentioned, IFdSeek is derived from IFdStreambuf. Like the latter class, IFdSeek's member functions use facilities declared in unistd.h. So, the header file <unistd.h> must have been read by the compiler before it can compile the class's members functions. To reduce the amount of typing when specifying types and constants from streambuf and std::ios, several using-declarations are defined by the class. These using-declarations refer to types that are defined in the header file <ios>, which must therefore also be included before the compiler can compile IFdSeek's class interface:
```
    class IFdSeek: public IFdStreambuf
    {
        using pos_type = std::streambuf::pos_type;
        using off_type = std::streambuf::off_type;
        using seekdir = std::ios::seekdir;
        using openmode = std::ios::openmode;

        public:
            IFdSeek(int fd);
        private:
            pos_type seekoff(off_type offset, seekdir dir, openmode);
            pos_type seekpos(pos_type offset, openmode mode);
    };
```
The class has a very basic interface. Its (only) constructor expects the device's file descriptor. It has no special tasks to perform and just calls its base class constructor:
```
    inline IFdSeek::IFdSeek(int fd)
    :
        IFdStreambuf(fd)
    {}
```

The member seek_off is responsible for performing the actual seek operations. It calls lseek to seek a new position in a device whose file descriptor is known. If seeking succeeds, setg is called to define an already empty buffer, so that the base class's underflow member refills the buffer at the next input request.

    IFdSeek::pos_type IFdSeek::seekoff(off_type off, seekdir dir, openmode)
    {
        pos_type pos =
            lseek
            (
                d_fd, off,
                (dir ==  std::ios::beg) ? SEEK_SET :
                (dir ==  std::ios::cur) ? SEEK_CUR :
                                          SEEK_END
            );

        if (pos < 0)
            return -1;

        setg(d_buffer, d_buffer + 1, d_buffer + 1);
        return pos;
    }

Finally, the companion function seekpos is overridden as well: it is actually defined as a call to seekoff:

    inline IFdSeek::pos_type IFdSeek::seekpos(pos_type off, openmode mode)
    {
        return seekoff(off, std::ios::beg, mode);
    }

Here is an example of a program using the class IFdSeek. If this program is given its own source file using input redirection then seeking is supported (and with the exception of the first line, every other line is shown twice):

    #include "fdinseek.h"
    #include <string>
    #include <iostream>
    #include <istream>
    #include <iomanip>
    using namespace std;

    int main()
    {
        IFdSeek fds(0);
        istream is(&fds);
        string  s;

        while (true)
        {
            if (!getline(is, s))
                break;

            streampos pos = is.tellg();

            cout << setw(5) << pos << ": `" << s << "'\n";

            if (!getline(is, s))
                break;

            streampos pos2 = is.tellg();

            cout << setw(5) << pos2 << ": `" << s << "'\n";

            if (!is.seekg(pos))
            {
                cout << "Seek failed\n";
                break;
            }
        }
    }

25.1.2.4: Multiple `unget' calls in `streambuf' objects

Streambuf classes and classes derived from streambuf should support at least ungetting the last read character. Special care must be taken when series of unget calls must be supported. In this section the construction of a class supporting a configurable number of istream::unget or istream::putback calls is discussed.

Support for multiple (say `n') unget calls is implemented by reserving an initial section of the input buffer, which is gradually filled up to contain the last n characters read. The class is implemented as follows:

Once again, the class is derived from std::streambuf. It defines several data members, allowing the class to perform the bookkeeping required to maintain an unget-buffer of a configurable size:

    class FdUnget: public std::streambuf
    {
        int     d_fd;
        size_t  d_bufsize;
        size_t  d_reserved;
        char   *d_buffer;
        char   *d_base;
        public:
            FdUnget(int fd, size_t bufsz, size_t unget);
            virtual ~FdUnget();
        private:
            int underflow();
    };

The class's constructor expects a file descriptor, a buffer size and the number of characters that can be ungot or pushed back as its arguments. This number determines the size of a reserved area, defined as the first d_reserved bytes of the class's input buffer.
- The input buffer will always be at least one byte larger than d_reserved. So, a certain number of bytes may be read. Once d_reserved bytes have been read at most d_reserved bytes can be ungot.
- Next, the starting point for reading operations is configured. It is called d_base, pointing to a location d_reserved bytes beyond the location represented by d_buffer. This is always the location where buffer refills start.
- Now that the buffer has been constructed, we're ready to define streambuf's buffer pointers using setg. As no characters have been read yet, all pointers are set to point to d_base. If unget is called at this point, no characters are available, and unget (correctly) fails.
- Eventually, the refill buffer's size is determined as the number of allocated bytes minus the size of the reserved area.
Here is the class's constructor:
```
    FdUnget::FdUnget(int fd, size_t bufsz, size_t unget)
    :
        d_fd(fd),
        d_reserved(unget)
    {
        size_t allocate =
                bufsz > d_reserved ?
                    bufsz
                :
                    d_reserved + 1;

        d_buffer = new char[allocate];

        d_base = d_buffer + d_reserved;
        setg(d_base, d_base, d_base);

        d_bufsize = allocate - d_reserved;
    }
```
The class's destructor simply returns the memory allocated for the buffer to the common pool:
```
    inline FdUnget::~FdUnget()
    {
        delete[] d_buffer;
    }
```
Finally, underflow is overridden as follows:
- First underflow determines the number of characters that could potentially be ungot. If that number of characters are ungot, the input buffer is exhausted. So this value may be any value between 0 (the initial state) or the input buffer's size (when the reserved area has been filled up completely, and all current characters in the remaining section of the buffer have also been read);
- Next the number of bytes to move into the reserved area is computed. This number is at most d_reserved, but it is set equal to the actual number of characters that can be ungot if this value is smaller;
- Now that the number of characters to move into the reserved area is known, this number of characters is moved from the input buffer's end to the area immediately before d_base;
- Then the buffer is refilled. This all is standard, but notice that reading starts from d_base and not from d_buffer;
- Finally, streambuf's read buffer pointers are set up. Eback is set to move locations before d_base, thus defining the guaranteed unget-area, gptr is set to d_base, since that's the location of the first read character after a refill, and egptr is set just beyond the location of the last character read into the buffer.
Here is underflow's implementation:
```
    int FdUnget::underflow()
    {
        size_t ungetsize = gptr() - eback();
        size_t move = std::min(ungetsize, d_reserved);

        memcpy(d_base - move, egptr() - move, move);

        int nread = read(d_fd, d_base, d_bufsize);
        if (nread <= 0)       // none read -> return EOF
            return EOF;

        setg(d_base - move, d_base, d_base + nread);

        return static_cast<unsigned char>(*gptr());
    }
```

An example using FdUnget

The next example program illustrates the use of the class FdUnget. It reads at most 10 characters from the standard input, stopping at EOF. A guaranteed unget-buffer of 2 characters is defined in a buffer holding 3 characters. Just before reading a character, the program tries to unget at most 6 characters. This is, of course, not possible; but the program nicely ungets as many characters as possible, considering the actual number of characters read:

    #include "fdunget.h"
    #include <string>
    #include <iostream>
    #include <istream>
    using namespace std;

    int main()
    {
        FdUnget fds(0, 3, 2);
        istream is(&fds);
        char    c;

        for (int idx = 0; idx < 10; ++idx)
        {
            cout << "after reading " << idx << " characters:\n";
            for (int ug = 0; ug <= 6; ++ug)
            {
                if (!is.unget())
                {
                    cout
                    << "\tunget failed at attempt " << (ug + 1) << "\n"
                    << "\trereading: '";

                    is.clear();
                    while (ug--)
                    {
                        is.get(c);
                        cout << c;
                    }
                    cout << "'\n";
                    break;
                }
            }

            if (!is.get(c))
            {
                cout << " reached\n";
                break;
            }
            cout << "Next character: " << c << '\n';
        }
    }
    /*
        Generated output after 'echo abcde | program':

        after reading 0 characters:
                unget failed at attempt 1
                rereading: ''
        Next character: a
        after reading 1 characters:
                unget failed at attempt 2
                rereading: 'a'
        Next character: b
        after reading 2 characters:
                unget failed at attempt 3
                rereading: 'ab'
        Next character: c
        after reading 3 characters:
                unget failed at attempt 4
                rereading: 'abc'
        Next character: d
        after reading 4 characters:
                unget failed at attempt 4
                rereading: 'bcd'
        Next character: e
        after reading 5 characters:
                unget failed at attempt 4
                rereading: 'cde'
        Next character:

        after reading 6 characters:
                unget failed at attempt 4
                rereading: 'de
        '
         reached
    */

25.1.3: Fixed-sized field extraction from istream objects

Usually when extracting information from istream objects operator>>, the standard extraction operator is perfectly suited for the task as in most cases the extracted fields are white-space (or otherwise clearly) separated from each other. But this does not hold true in all situations. For example, when a web-form is posted to some processing script or program, the receiving program may receive the form field's values as url-encoded characters: letters and digits are sent unaltered, blanks are sent as + characters, and all other characters start with % followed by the character's ascii-value represented by its two digit hexadecimal value.

When decoding url-encoded information, simple hexadecimal extraction won't work, as that extracts as many hexadecimal characters as available, instead of just two. Since the letters a-f` and 0-9 are legal hexadecimal characters, a text like My name is `Ed', url-encoded as

    My+name+is+%60Ed%27

results in the extraction of the hexadecimal values 60ed and 27, instead of 60 and 27. The name Ed disappears from view, which is clearly not what we want.

In this case, having seen the %, we could extract 2 characters, put them in an istringstream object, and extract the hexadecimal value from the istringstream object. A bit cumbersome, but doable. Other approaches are possible as well.

The class Fistream for fixed-sized field istream defines an istream class supporting both fixed-sized field extractions and blank-delimited extractions (as well as unformatted read calls). The class may be initialized as a wrapper around an existing istream, or it can be initialized using the name of an existing file. The class is derived from istream, allowing all extractions and operations supported by istreams in general. Fistream defines the following data members:

d_filebuf: a filebuffer used when Fistream reads its information from a named (existing) file. Since the filebuffer is only needed in that case, and since it must be allocated dynamically, it is defined as a unique_ptr<filebuf> object.
d_streambuf: a pointer to Fistream's streambuf. It points to d_filebuf when Fistream opens a file by name. When an existing istream is used to construct an Fistream, it points to the existing istream's streambuf.
d_iss: an istringstream object used for the fixed field extractions.
d_width: a size_t indicating the width of the field to extract. If 0 no fixed field extractions is used, but information is extracted from the istream base class object using standard extractions.

Here is the initial section of Fistream's class interface:

    class Fistream: public std::istream
    {
        std::unique_ptr<std::filebuf> d_filebuf;
        std::streambuf *d_streambuf;
        std::istringstream d_iss;
        size_t d_width;

As stated, Fistream objects can be constructed from either a filename or an existing istream object. The class interface therefore declares two constructors:

            Fistream(std::istream &stream);
            Fistream(char const *name,
                std::ios::openmode mode = std::ios::in);

When an Fistream object is constructed using an existing istream object, the Fistream's istream part simply uses the stream's streambuf object:

Fistream::Fistream(istream &stream)
:
    istream(stream.rdbuf()),
    d_streambuf(rdbuf()),
    d_width(0)
{}

When an fstream object is constructed using a filename, the istream base initializer is given a new filebuf object to be used as its streambuf. Since the class's data members are not initialized before the class's base class has been constructed, d_filebuf can only be initialized thereafter. By then, the filebuf is only available as rdbuf, returning a streambuf. However, as it is actually a filebuf, a static_cast is used to cast the streambuf pointer returned by rdbuf to a filebuf *, so d_filebuf can be initialized:

Fistream::Fistream(char const *name, ios::openmode mode)
:
    istream(new filebuf()),
    d_filebuf(static_cast<filebuf *>(rdbuf())),
    d_streambuf(d_filebuf.get()),
    d_width(0)
{
    d_filebuf->open(name, mode);
}

25.1.3.1: Member functions and example

There is only one additional public member:

setField(field const
&)

. This member defines the size of the next field to extract. Its parameter is a reference to a field class, a manipulator class defining the width of the next field.

Since a field & is mentioned in Fistream's interface, field must be declared before Fistream's interface starts. The class field itself is simple and declares Fistream as its friend. It has two data members: d_width specifies the width of the next field, and d_newWidth which is set to true if d_width's value should actually be used. If d_newWidth is false, Fistream returns to its standard extraction mode. The class field has two constructors: a default constructor, setting d_newWidth to false, and a second constructor expecting the width of the next field to extract as its value. Here is the class field:

    class field
    {
        friend class Fistream;
        size_t d_width;
        bool     d_newWidth;

        public:
            field(size_t width);
            field();
    };

    inline field::field(size_t width)
    :
        d_width(width),
        d_newWidth(true)
    {}

    inline field::field()
    :
        d_newWidth(false)
    {}

Since field declares Fistream as its friend, setField may inspect field's members directly.

Time to return to setField. This function expects a reference to a field object, initialized in one of three different ways:

field(): When setField's argument is a field object constructed by its default constructor the next extraction will use the same field width as the previous extraction.
field(0): When this field object is used as setField's argument, fixed-sized field extraction stops, and the Fistream acts like any standard istream object again.
field(x): When the field object itself is initialized by a non-zero size_t value x, then the next field width is x characters wide. The preparation of such a field is left to setBuffer, Fistream's only private member.

Here is setField's implementation:

std::istream &Fistream::setField(field const &params)
{
    if (params.d_newWidth)                  // new field size requested
        d_width = params.d_width;           // set new width

    if (!d_width)                           // no width?
        rdbuf(d_streambuf);                 // return to the old buffer
    else
        setBuffer();                        // define the extraction buffer

    return *this;
}

The private member setBuffer defines a buffer of d_width + 1 characters and uses read to fill the buffer with d_width characters. The buffer is an NTBS. This buffer is used to initialize the d_iss member. Fistream's rdbuf member is used to extract the d_str's data via the Fistream object itself:

void Fistream::setBuffer()
{
    char *buffer = new char[d_width + 1];

    rdbuf(d_streambuf);                         // use istream's buffer to
    buffer[read(buffer, d_width).gcount()] = 0; // read d_width chars,
                                                // terminated by a 0-byte
    d_iss.str(buffer);
    delete[] buffer;

    rdbuf(d_iss.rdbuf());                       // switch buffers
}

Although setField could be used to configure Fistream to use or not to use fixed-sized field extraction, using manipulators is probably preferable. To allow field objects to be used as manipulators an overloaded extraction operator was defined. This extraction operator accepts istream & and a field const & objects. Using this extraction operator, statements like

fis >> field(2) >> x >> field(0);

are possible (assuming fis is a Fistream object). Here is the overloaded operator>>, as well as its declaration:

istream &std::operator>>(istream &str, field const &params)
{
    return static_cast<Fistream *>(&str)->setField(params);
}

Declaration:

namespace std
{
    istream &operator>>(istream &str, FBB::field const &params);
}

Finally, an example. The following program uses a Fistream object to url-decode url-encoded information appearing at its standard input:

    int main()
    {
        Fistream fis(cin);

        fis >> hex;
        while (true)
        {
            size_t x;
            switch (x = fis.get())
            {
                case '\n':
                    cout << '\n';
                break;
                case '+':
                    cout << ' ';
                break;
                case '%':
                    fis >> field(2) >> x >> field(0);
                // FALLING THROUGH
                default:
                    cout << static_cast<char>(x);
                break;
                case EOF:
                return 0;
            }
        }
    }
    /*
        Generated output after:
            echo My+name+is+%60Ed%27 | a.out

        My name is `Ed'
    */

25.2: The `fork' system call

From the C programming language the fork system call is well known. When a program needs to start a new process, system can be used. The function system requires the program to wait for the child process to terminate. The more general way to spawn subprocesses is to use fork.

In this section we investigate how C++ can be used to wrap classes around a complex system call like fork. Much of what follows in this section directly applies to the Unix operating system, and the discussion therefore focuses on that operating system. Other systems usually provide comparable facilities. What follows is closely related to the Template Design Pattern (cf. Gamma et al. (1995) Design Patterns, Addison-Wesley)

When fork is called, the current program is duplicated in memory, thus creating a new process. Following this duplication both processes continue their execution just below the fork system call. The two processes may inspect fork's return value: the return value in the original process (called the parent process) differs from the return value in the newly created process (called the child process):

In the parent process fork returns the process ID of the (child) process that was created by the fork system call. This is a positive integer value.
In the child process fork returns 0.
If fork fails, -1 is returned.

25.2.1: A basic Fork class

A basic Fork class should hide all bookkeeping details of a system call like fork from its users. The class Fork developed here does just that. The class itself only ensures the proper execution of the fork system call. Normally, fork is called to start a child process, usually boiling down to the execution of a separate process. This child process may expect input at its standard input stream and/or may generate output to its standard output and/or standard error streams. Fork does not know all this, and does not have to know what the child process will do. Fork objects should be able to start their child processes.

Fork's constructor cannot know what actions its child process should perform. Similarly, it cannot know what actions the parent process should perform. For these kind of situations, the template method design pattern was developed. According to Gamma c.s., the template method design pattern

``Define(s) the skeleton of an algorithm in an operation, deferring some steps to subclasses. [The] Template Method (design pattern) lets subclasses redefine certain steps of an algorithm, without changing the algorithm's structure.''

This design pattern allows us to define an abstract base class already providing the essential steps related to the fork system call, deferring the implementation of other parts of the fork system call to subclasses.

The Fork abstract base class has the following characteristics:

It defines a data member d_pid. In the parent process this data member contains the child's process id and in the child process it has the value 0. Its public interface declares only two members:

a fork member function, responsible for the actual forking (i.e., it creates the (new) child process);
a virtual destructor ~Fork (having an empty body).

Here is Fork's interface:

    class Fork
    {
        int d_pid;

        public:
            virtual ~Fork();
            void fork();

        protected:
            int pid() const;
            int waitForChild();                 // returns the status

        private:
            virtual void childRedirections();
            virtual void parentRedirections();

            virtual void childProcess() = 0;    // pure virtual members
            virtual void parentProcess() = 0;
    };

All other non-virtual member functions are declared in the class's protected section and can thus only be used by derived classes. They are:
- pid(): The member function pid allows derived classes to access the system fork's return value:
```
    inline int Fork::pid() const
    {
        return d_pid;
    }
```
- waitForChild(): The member int waitForChild can be called by parent processes to wait for the completion of their child processes (as discussed below). This member is declared in the class interface. Its implementation is:
```
    #include "fork.ih"

    int Fork::waitForChild()
    {
        int status;

        waitpid(d_pid, &status, 0);

        return WEXITSTATUS(status);
    }
```
  This simple implementation returns the child's exit status to the parent. The called system function waitpid blocks until the child terminates.
When fork system calls are used, parent processes and child processes must always be distinguished. The main distinction between these processes is that d_pid becomes the child's process-id in the parent process, while d_pid becomes 0 in the child process itself. Since these two processes must always be distinguished (and present), their implementation by classes derived from Fork is enforced by Fork's interface: the members childProcess, defining the child process' actions and parentProcess, defining the parent process' actions were defined as pure virtual functions.
communication between parent- and child processes may use standard streams or other facilities, like pipes (cf. section 25.2.5). To facilitate this inter-process communication, derived classes may implement:
- childRedirections(): this member should be overridden by derived classes if any standard stream (cin, cout,) or cerr must be redirected in the child process (cf. section 25.2.3). By default it has an empty implementation;
- parentRedirections(): this member should be overridden by derived classes if any standard stream (cin, cout,) or cerr must be redirected in the parent process. By default it has an empty implementation.
Redirection of the standard streams is necessary if parent and child processes must communicate with each other via the standard streams. Here are their default definitions. Since these functions are virtual functions they should not be implemented inline, but in their own source file:
```
    void Fork::childRedirections()
    {}
    void Fork::parentRedirections()
    {}
```

25.2.2: Parents and Children

The member function fork calls the system function fork (Caution: since the system function fork is called by a member function having the same name, the :: scope resolution operator must be used to prevent a recursive call of the member function itself). The function ::fork's return value determines whether parentProcess or childProcess is called. Maybe redirection is necessary. Fork::fork's implementation calls childRedirections just before calling childProcess, and parentRedirections just before calling parentProcess:

    #include "fork.ih"

    void Fork::fork()
    {
        if ((d_pid = ::fork()) < 0)
            throw "Fork::fork() failed";

        if (d_pid == 0)                 // childprocess has pid == 0
        {
            childRedirections();
            childProcess();
            exit(1);                    // we shouldn't come here:
        }                               // childProcess() should exit

        parentRedirections();
        parentProcess();
    }

In fork.cc the class's internal header file fork.ih is included. This header file takes care of the inclusion of the necessary system header files, as well as the inclusion of fork.h itself. Its implementation is:

    #include "fork.h"
    #include <cstdlib>
    #include <unistd.h>
    #include <sys/types.h>
    #include <sys/wait.h>

Child processes should not return: once they have completed their tasks, they should terminate. This happens automatically when the child process performs a call to a member of the exec... family, but if the child itself remains active, then it must make sure that it terminates properly. A child process normally uses exit to terminate itself, but note that exit prevents the activation of destructors of objects defined at the same or more superficial nesting levels than the level at which exit is called. Destructors of globally defined objects are activated when exit is used. When using exit to terminate childProcess, it should either itself call a support member function defining all nested objects it needs, or it should define all its objects in a compound statement (e.g., using a throw block) calling exit beyond the compound statement.

Parent processes should normally wait for their children to complete. Terminating child processes inform their parents that they are about to terminate by sending a signal that should be caught by their parents. If child processes terminate and their parent processes do not catch those signals then such child processes remain visible as so-called zombie processes.

If parent processes must wait for their children to complete, they may call the member waitForChild. This member returns the exit status of a child process to its parent.

There exists a situation where the child process continues to live, but the parent dies. This is a fairly natural event: parents tend to die before their children do. In our context (i.e. C++), this is called a daemon program. In a daemon the parent process dies and the child program continues to run as a child of the basic init process. Again, when the child eventually dies a signal is sent to its `step-parent' init. This does not create a zombie as init catches the termination signals of all its (step-) children. The construction of a daemon process is very simple, given the availability of the class Fork (cf. section 25.2.4).

25.2.3: Redirection revisited

Earlier, in section 6.6.2 streams were redirected using the ios::rdbuf member function. By assigning the streambuf of a stream to another stream, both stream objects access the same streambuf, thus implementing redirection at the level of the programming language itself.

This may be fine within the context of a C++ program, but once we leave that context the redirection terminates. The operating system does not know about streambuf objects. This situation is encountered, e.g., when a program uses a system call to start a subprogram. The example program at the end of this section uses C++ redirection to redirect the information inserted into cout to a file, and then calls

    system("echo hello world")

to echo a well-known line of text. Since echo writes its information to the standard output, this would be the program's redirected file if the operating system would recognize C++'s redirection.

But redirection doesn't happen. Instead, hello world still appears at the program's standard output and the redirected file is left untouched. To write hello world to the redirected file redirection must be realized at the operating system level. Some operating systems (e.g., Unix and friends) provide system calls like dup and dup2 to accomplish this. Examples of the use of these system calls are given in section 25.2.5.

Here is the example of the failing redirection at the system level following C++ redirection using streambuf redirection:

    #include <iostream>
    #include <fstream>
    #include <cstdlib>
    using namespace std;

    int main()
    {
        ofstream of("outfile");

        streambuf *buf = cout.rdbuf(of.rdbuf());
        cout << "To the of stream\n";
        system("echo hello world");
        cout << "To the of stream\n";
        cout.rdbuf(buf);
    }
    /*
        Generated output: on the file `outfile'

        To the of stream
        To the of stream

        On standard output:

        hello world
    */

25.2.4: The `Daemon' program

Applications exist in which the only purpose of fork is to start a child process. The parent process terminates immediately after spawning the child process. If this happens, the child process continues to run as a child process of init, the always running first process on Unix systems. Such a process is often called a daemon, running as a background process.

Although the next example can easily be constructed as a plain C program, it was included in the C++ Annotations because it is so closely related to the current discussion of the Fork class. I thought about adding a daemon member to that class, but eventually decided against it because the construction of a daemon program is very simple and requires no features other than those currently offered by the class Fork. Here is an example illustrating the construction of such a daemon program. Its child process doesn't do exit but throw 0 which is caught by the catch clause of the child's main function. Doing this ensures that any objects defined by the child process are properly destroyed:

    #include <iostream>
    #include <unistd.h>
    #include "fork.h"

    class Daemon: public Fork
    {
        virtual void parentProcess()        // the parent does nothing.
        {}
        virtual void childProcess()         // actions by the child
        {
            sleep(3);
                                            // just a message...
            std::cout << "Hello from the child process\n";
            throw 0;                        // The child process ends
        }
    };

    int main()
    try
    {
        Daemon{}.fork();
    }
    catch(...)
    {}

    /*
        Generated output:
    The next command prompt, then after 3 seconds:
    Hello from the child process
    */

25.2.5: The class `Pipe'

Redirection at the system level requires the use of file descriptor, created by the pipe system call. When two processes want to communicate using such file descriptors, the following happens:

The process constructs two associated file descriptors using the pipe system call. One of the file descriptors is used for writing, the other file descriptor is used for reading.
Forking takes place (i.e., the system fork function is called), duplicating the file descriptors. Now we have four file descriptors as the child process and the parent process both have their own copies of the two file descriptors created by pipe.
One process (say, the parent process) uses the file descriptors for reading. It should close its file descriptor intended for writing.
The other process (say, the child process) uses the file descriptors for writing. It should therefore close its file descriptor intended for reading.
All information written by the child process to the file descriptor intended for writing, can now be read by the parent process from the corresponding file descriptor intended for reading, thus establishing a communication channel between the child and the parent process.

Though basically simple, errors may easily creep in. Functions of file descriptors available to the two processes (child or parent) may easily get mixed up. To prevent bookkeeping errors, the bookkeeping may be properly set up once, to be hidden thereafter inside a class like the Pipe class developed here. Let's have a look at its characteristics (before using functions like pipe and dup the compiler must have read the <unistd.h> header file):

The pipe system call expects a pointer to two int values, representing, respectively, the file descriptor used for reading and the file descriptor used for writing. To avoid confusion, the class Pipe defines an enum having values associating the indices of the array of 2-ints with symbolic constants. The two file descriptors themselves are stored in a data member d_fd. Here is the initial section of the class's interface:
```
    class Pipe
    {
        enum    RW { READ, WRITE };
        int     d_fd[2];
```
The class only needs a default constructor. This constructor calls pipe to create a set of associated file descriptors used for accessing both ends of a pipe:
```
    Pipe::Pipe()
    {
        if (pipe(d_fd))
            throw "Pipe::Pipe(): pipe() failed";
    }
```
The members readOnly and readFrom are used to configure the pipe's reading end. The latter function is used when using redirection. It is provided with an alternate file descriptor to be used for reading from the pipe. Usually this alternate file descriptor is STDIN_FILENO, allowing cin to extract information from the pipe. The former function is merely used to configure the reading end of the pipe. It closes the matching writing end and returns a file descriptor that can be used to read from the pipe:
```
    int Pipe::readOnly()
    {
        close(d_fd[WRITE]);
        return d_fd[READ];
    }
    void Pipe::readFrom(int fd)
    {
        readOnly();

        redirect(d_fd[READ], fd);
        close(d_fd[READ]);
    }
```
writeOnly and two writtenBy members are available to configure the writing end of a pipe. The former function is only used to configure the writing end of the pipe. It closes the reading end, and returns a file descriptor that can be used for writing to the pipe:
```
    int Pipe::writeOnly()
    {
        close(d_fd[READ]);
        return d_fd[WRITE];
    }
    void Pipe::writtenBy(int fd)
    {
        writtenBy(&fd, 1);
    }
    void Pipe::writtenBy(int const *fd, size_t n)
    {
        writeOnly();

        for (size_t idx = 0; idx < n; idx++)
            redirect(d_fd[WRITE], fd[idx]);

        close(d_fd[WRITE]);
    }
```
For the latter member two overloaded versions are available:
- writtenBy(int fd) is used to configure single redirection, so that a specific file descriptor (usually STDOUT_FILENO or STDERR_FILENO) can be used to write to the pipe;
- (writtenBy(int const *fd, size_t n)) may be used to configure multiple redirection, providing an array argument containing file descriptors. Information written to any of these file descriptors is actually written to the pipe.
The class has one private data member, redirect, used to set up redirection through the dup2 system call. This function expects two file descriptors. The first file descriptor represents a file descriptor that can be used to access the device's information; the second file descriptor is an alternate file descriptor that may also be used to access the device's information. Here is redirect's implementation:
```
    void Pipe::redirect(int d_fd, int alternateFd)
    {
        if (dup2(d_fd, alternateFd) < 0)
            throw "Pipe: redirection failed";
    }
```

Now that redirection can be configured easily using one or more Pipe objects, we'll use Fork and Pipe in various example programs.

25.2.6: The class `ParentSlurp'

The class ParentSlurp, derived from Fork, starts a child process executing a stand-alone program (like /bin/ls). The (standard) output of the executed program is not shown on the screen but is read by the parent process.

For demonstration purposes the parent process writes the lines it receives to its standard output stream, prepending linenumbers to the lines. It is attractive to redirect the parent's standard input stream to allow the parent to read the output from the child process using its std::cin input stream. Therefore, the only pipe in the program is used as an input pipe for the parent, and an output pipe for the child.

The class ParentSlurp has the following characteristics:

It is derived from Fork. Before starting ParentSlurp's class interface, the compiler must have read fork.h and pipe.h. The class only uses one data member, a Pipe object d_pipe.
As Pipe's constructor already defines a pipe, and as d_pipe is automatically initialized by ParentSlurp's default constructor, which is implicitly provided, all additional members only exist for ParentSlurp's own benefit so they can be defined in the class's (implicit) private section. Here is the class's interface:
```
    class ParentSlurp: public Fork
    {
        Pipe    d_pipe;

        virtual void childRedirections();
        virtual void parentRedirections();
        virtual void childProcess();
        virtual void parentProcess();
    };
```
The childRedirections member configures the writing end of the pipe. So, all information written to the child's standard output stream ends up in the pipe. The big advantage of this is that no additional streams are needed to write to a file descriptor:
```
    inline void ParentSlurp::childRedirections()
    {
        d_pipe.writtenBy(STDOUT_FILENO);
    }
```
The parentRedirections member, configures the reading end of the pipe. It does so by connecting the reading end of the pipe to the parent's standard input file descriptor (STDIN_FILENO). This allows the parent to perform extractions from cin, not requiring any additional streams for reading.
```
    inline void ParentSlurp::parentRedirections()
    {
        d_pipe.readFrom(STDIN_FILENO);
    }
```
The childProcess member only needs to concentrate on its own actions. As it only needs to execute a program (writing information to its standard output), the member can consist of one single statement:
```
    inline void ParentSlurp::childProcess()
    {
        execl("/bin/ls", "/bin/ls", 0);
    }
```

The parentProcess member simply `slurps' the information appearing at its standard input. Doing so, it actually reads the child's output. It copies the received lines to its standard output stream prefixing line numbers to them:

    void ParentSlurp::parentProcess()
    {
        std::string     line;
        size_t    nr = 1;

        while (getline(std::cin, line))
            std::cout << nr++ << ": " << line << '\n';

        waitForChild();
    }

The following program simply constructs a ParentSlurp object, and calls its fork() member. Its output consists of a numbered list of files in the directory where the program is started. Note that the program also needs the fork.o, pipe.o and waitforchild.o object files (see earlier sources):

    int main()
    {
        ParentSlurp{}.fork();
    }
    /*
        Generated Output (example only, actually obtained output may differ):

        1: a.out
        2: bitand.h
        3: bitfunctional
        4: bitnot.h
        5: daemon.cc
        6: fdinseek.cc
        7: fdinseek.h
        ...
    */

25.2.7: Communicating with multiple children

The next step up the ladder is the construction of a child-process monitor. Here, the parent process is responsible for all its child processes, but it also must read their standard output. The user enters information at the standard input of the parent process. A simple command language is used for this:

start: this starts a new child process. The parent returns the child's ID (a number) to the user. The ID is thereupon be used to identify a particular child process;
<nr> text sends ``text'' to the child process having ID <nr>;
stop <nr> terminates the child process having ID <nr>;
exit terminates the parent as well as all its child processes.

If a child process hasn't received text for some time it will complain by sending a message to the parent-process. Those messages are simply transmitted to the user by copying them to the standard output stream.

A problem with programs like our monitor is that they allow asynchronous input from multiple sources. Input may appear at the standard input as well as at the input-sides of pipes. Also, multiple output channels are used. To handle situations like these, the select system call was developed.

25.2.7.1: The class `Selector': interface

The select system call was developed to handle asynchronous I/O multiplexing. The select system call is used to handle, e.g., input appearing simultaneously at a set of file descriptors.

The select function is rather complex, and its full discussion is beyond the C++ Annotations' scope. By encapsulating select in a class Selector, hiding its details and offering an intuitively attractive interface, its use is simplified. The Selector class has these features:

Efficiency. As most of Select's members are very small, most members can be implemented inline. The class requires quite a few data members. Most of these data members belong to types that require some system headers to be included first:
```
    #include <limits.h>
    #include <unistd.h>
    #include <sys/time.h>
    #include <sys/types.h>
```

The class interface can now be defined. The data type fd_set is a type designed to be used by select and variables of this type contain the set of file descriptors on which select may sense some activity. Furthermore, select allows us to fire an asynchronous alarm. To set the alarm time, the class Selector defines a timeval data member. Other members are used for internal bookkeeping purposes. Here is the class Selector's interface:

    class Selector
    {
        fd_set          d_read;
        fd_set          d_write;
        fd_set          d_except;
        fd_set          d_ret_read;
        fd_set          d_ret_write;
        fd_set          d_ret_except;
        timeval         d_alarm;
        int             d_max;
        int             d_ret;
        int             d_readidx;
        int             d_writeidx;
        int             d_exceptidx;

        public:
            Selector();

            int exceptFd();
            int nReady();
            int readFd();
            int wait();
            int writeFd();
            void addExceptFd(int fd);
            void addReadFd(int fd);
            void addWriteFd(int fd);
            void noAlarm();
            void rmExceptFd(int fd);
            void rmReadFd(int fd);
            void rmWriteFd(int fd);
            void setAlarm(int sec, int usec = 0);

        private:
            int checkSet(int *index, fd_set &set);
            void addFd(fd_set *set, int fd);
    };

25.2.7.2: The class `Selector': implementation

Selector's member functions serve the following tasks:

Selector(): the (default) constructor. It clears the read, write, and execute fd_set variables, and switches off the alarm. Except for d_max, the remaining data members do not require specific initializations:
```
    Selector::Selector()
    {
        FD_ZERO(&d_read);
        FD_ZERO(&d_write);
        FD_ZERO(&d_except);
        noAlarm();
        d_max = 0;
    }
```

int wait(): this member blocks until the alarm times out or until activity is sensed at any of the file descriptors monitored by the Selector object. It throws an exception when the select system call itself fails:

    int Selector::wait()
    {
        timeval t = d_alarm;

        d_ret_read = d_read;
        d_ret_write = d_write;
        d_ret_except = d_except;

        d_readidx = 0;
        d_writeidx = 0;
        d_exceptidx = 0;

        d_ret = select(d_max, &d_ret_read, &d_ret_write, &d_ret_except,
                       t.tv_sec == -1 && t.tv_usec == -1 ? 0 : &t);

        if (d_ret < 0)
            throw "Selector::wait()/select() failed";

        return d_ret;
    }

int nReady: this member function's return value is only defined when wait has returned. In that case it returns 0 for an alarm-timeout, -1 if select failed, and otherwise the number of file descriptors on which activity was sensed:
```
    inline int Selector::nReady()
    {
        return d_ret;
    }
```
int readFd(): this member function's return value is also only defined after wait has returned. Its return value is -1 if no (more) input file descriptors are available. Otherwise the next file descriptor available for reading is returned:
```
    inline int Selector::readFd()
    {
        return checkSet(&d_readidx, d_ret_read);
    }
```
int writeFd(): operating analogously to readFd, it returns the next file descriptor to which output is written. It uses d_writeidx and d_ret_read and is implemented analogously to readFd;
int exceptFd(): operating analogously to readFd, it returns the next exception file descriptor on which activity was sensed. It uses d_except_idx and d_ret_except and is implemented analogously to readFd;
void setAlarm(int sec, int usec = 0): this member activates Select's alarm facility. At least the number of seconds to wait for the alarm to go off must be specified. It simply assigns values to d_alarm's fields. At the next Select::wait call, the alarm fires (i.e., wait returns with return value 0) once the configured alarm-interval has passed:
```
    inline void Selector::setAlarm(int sec, int usec)
    {
        d_alarm.tv_sec  = sec;
        d_alarm.tv_usec = usec;
    }
```
void noAlarm(): this member switches off the alarm, by simply setting the alarm interval to a very long period:
```
    inline void Selector::noAlarm()
    {
        setAlarm(-1, -1);
    }
```
void addReadFd(int fd): this member adds a file descriptor to the set of input file descriptors monitored by the Selector object. The member function wait returns once input is available at the indicated file descriptor:
```
    inline void Selector::addReadFd(int fd)
    {
        addFd(&d_read, fd);
    }
```
void addWriteFd(int fd): this member adds a file descriptor to the set of output file descriptors monitored by the Selector object. The member function wait returns once output is available at the indicated file descriptor. Using d_write, it is implemented analogously to addReadFd;
void addExceptFd(int fd): this member adds a file descriptor to the set of exception file descriptors to be monitored by the Selector object. The member function wait returns once activity is sensed at the indicated file descriptor. Using d_except, it is implemented analogously to addReadFd;
void rmReadFd(int fd): this member removes a file descriptor from the set of input file descriptors monitored by the Selector object:
```
    inline void Selector::rmReadFd(int fd)
    {
        FD_CLR(fd, &d_read);
    }
```
void rmWriteFd(int fd): this member removes a file descriptor from the set of output file descriptors monitored by the Selector object. Using d_write, it is implemented analogously to rmReadFd;
void rmExceptFd(int fd): this member removes a file descriptor from the set of exception file descriptors to be monitored by the Selector object. Using d_except, it is implemented analogously to rmReadFd;

The class's remaining (two) members are support members, and should not be used by non-member functions. Therefore, they are declared in the class's private section:

The member addFd adds a file descriptor to a fd_set:

    void Selector::addFd(fd_set *set, int fd)
    {
        FD_SET(fd, set);
        if (fd >= d_max)
            d_max = fd + 1;
    }

The member checkSet tests whether a file descriptor (*index) is found in a fd_set:

    int Selector::checkSet(int *index, fd_set &set)
    {
        int &idx = *index;

        while (idx < d_max && !FD_ISSET(idx, &set))
            ++idx;

        return idx == d_max ? -1 : idx++;
    }

25.2.7.3: The class `Monitor': interface

The monitor program uses a Monitor object doing most of the work. The class Monitor's public interface only offers a default constructor and one member, run, to perform its tasks. All other member functions are located in the class's private section.

Monitor defines the private enum Commands, symbolically listing the various commands its input language supports, as well as several data members. Among the data members are a Selector object and a map using child order numbers as its keys and pointer to Child objects (see section 25.2.7.7) as its values. Furthermore, Monitor has a static array member s_handler[], storing pointers to member functions handling user commands.

A destructor should be implemented as well, but its implementation is left as an exercise to the reader. Here is Monitor's interface, including the interface of the nested class Find that is used to create a function object:

    class Monitor
    {
        enum Commands
        {
            UNKNOWN,
            START,
            EXIT,
            STOP,
            TEXT,
            sizeofCommands
        };

        using MapIntChild = std::map<int, std::shared_ptr<Child>>;

        friend class Find;
        class Find
        {
            int     d_nr;
            public:
                Find(int nr);
                bool operator()(MapIntChild::value_type &vt) const;
        };

        Selector    d_selector;
        int         d_nr;
        MapIntChild d_child;

        static void (Monitor::*s_handler[])(int, std::string const &);
        static int s_initialize;

        public:
            enum Done
            {};

            Monitor();
            void run();

        private:
            static void killChild(MapIntChild::value_type it);
            static int initialize();

            Commands    next(int *value, std::string *line);
            void    processInput();
            void    processChild(int fd);

            void    createNewChild(int, std::string const &);
            void    exiting(int = 0, std::string const &msg = std::string{});
            void    sendChild(int value, std::string const &line);
            void    stopChild(int value, std::string const &);
            void    unknown(int, std::string const &);
    };

Since there's only one non-class type data member, the class's constructor is a very simple function which could be implemented inline:

    inline Monitor::Monitor()
    :
        d_nr(0)
    {}

25.2.7.4: The class `Monitor': s_handler

The array s_handler, storing pointers to functions needs to be initialized as well. This can be accomplished in several ways:

Since the Commands enumeration only specifies a fairly limited set of commands, compile-time initialization could be considered:
```
    void (Monitor::*Monitor::s_handler[])(int, string const &)  =
    {
        &Monitor::unknown,              // order follows enum Command's
        &Monitor::createNewChild,       // elements
        &Monitor::exiting,
        &Monitor::stopChild,
        &Monitor::sendChild,
    };
```
The advantage of this is that it's simple, not requiring any run-time effort. The disadvantage is of course relatively complex maintenance. If for some reason Commands is modified, s_handler must be modified as well. In cases like these, compile-time initialization often is asking for trouble. There is a simple alternative though.
Looking at Monitor's interface we see a static data member s_initialize and a static member function initialize. The static member function handles the initialization of the s_handler array. It explicitly assigns the array's elements and any modification in ordering of enum Commands' values is automatically accounted for by recompiling initialize:
```
    void (Monitor::*Monitor::s_handler[sizeofCommands])(int, string const &);

    int Monitor::initialize()
    {
        s_handler[UNKNOWN] =    &Monitor::unknown;
        s_handler[START] =      &Monitor::createNewChild;
        s_handler[EXIT] =       &Monitor::exiting;
        s_handler[STOP] =       &Monitor::stopChild;
        s_handler[TEXT] =       &Monitor::sendChild;
        return 0;
    }
```
The member initialize is a static member and so it can be called to initialize s_initialize, a static int variable. The initialization is enforced by placing the initialization statement in the source file of a function that is known to be executed. It could be main, but if we're Monitor's maintainers and only have control over the library containing Monitor's code then that's not an option. In those cases the source file containing the destructor is a very good candidate. If a class has only one constructor and it's not defined inline then the constructor's source file is a good candidate as well. In Monitor's current implementation the initialization statement is put in run's source file, reasoning that s_handler is only needed when run is used.

25.2.7.5: The class `Monitor': the member `run'

Monitor's core activities are performed by run. It performs the following tasks:

Initially, the Monitor object only monitors its standard input. The set of input file descriptors to which d_selector listens is initialized to STDIN_FILENO.
Then, in a loop d_selector's wait function is called. If input on cin is available, it is processed by processInput. Otherwise, the input has arrived from a child process. Information sent by children is processed by processChild.
To prevent zombies, the child processes must catch their children's termination signals. This is discussed below.
As noted by Ben Simons (ben at mrxfx dot com) Monitor must not catch the termination signals. Instead, the process spawning child processes has that responsibility (the underlying principle being that a parent process is responsible for its child processes; a child process, in turn, is responsible for its own child processes).
As stated, run's source file also defines and initializes s_initialize to ensure the proper initialization of the s_handler array.

Here is run's implementation and s_initialize's definition:

    #include "monitor.ih"

    int Monitor::s_initialize = Monitor::initialize();

    void Monitor::run()
    {
        d_selector.addReadFd(STDIN_FILENO);

        while (true)
        {
            cout << "? " << flush;
            try
            {
                d_selector.wait();

                int fd;
                while ((fd = d_selector.readFd()) != -1)
                {
                    if (fd == STDIN_FILENO)
                        processInput();
                    else
                        processChild(fd);
                }
                cout << "NEXT ...\n";
            }
            catch (char const *msg)
            {
                exiting(1, msg);
            }
        }
    }

The member function processInput reads the commands entered by the user using the program's standard input stream. The member itself is rather simple. It calls next to obtain the next command entered by the user, and then calls the corresponding function using the matching element of the s_handler[] array. Here are the members processInput and next:

    void Monitor::processInput()
    {
        string line;
        int    value;
        Commands cmd = next(&value, &line);
        (this->*s_handler[cmd])(value, line);
    }

    Monitor::Commands Monitor::next(int *value, string *line)
    {
        if (!getline(cin, *line))
            exiting(1, "Monitor::next(): reading cin failed");

        if (*line == "start")
            return START;

        if (*line == "exit" || *line == "quit")
        {
            *value = 0;
            return EXIT;
        }

        if (line->find("stop") == 0)
        {
            istringstream istr(line->substr(4));
            istr >> *value;
            return !istr ? UNKNOWN : STOP;
        }

        istringstream istr(line->c_str());
        istr >> *value;
        if (istr)
        {
            getline(istr, *line);
            return TEXT;
        }

        return UNKNOWN;
    }

All other input sensed by d_select is created by child processes. Because d_select's readFd member returns the corresponding input file descriptor, this descriptor can be passed to processChild. Using a IFdStreambuf (see section 25.1.2.1), its information is read from an input stream. The communication protocol used here is rather basic. For every line of input sent to a child, the child replies by sending back exactly one line of text. This line is then read by processChild:

    void Monitor::processChild(int fd)
    {
        IFdStreambuf ifdbuf(fd);
        istream istr(&ifdbuf);
        string line;

        getline(istr, line);
        cout << d_child[fd]->pid() << ": " << line << '\n';
    }

The construction d_child[fd]->pid() used in the above source deserves some special attention. Monitor defines the data member

map<int,
shared_ptr<Child>> d_child

. This map contains the child's order number as its key, and a (shared) pointer to the Child object as its value. A shared pointer is used here, rather than a Child object, since we want to use the facilities offered by the map, but don't want to copy a Child object time and again.

25.2.7.6: The class `Monitor': example

Now that run's implementation has been covered, we'll concentrate on the various commands users might enter:

When the start command is issued, a new child process is started. A new element is added to d_child by the member createNewChild. Next, the Child object should start its activities, but the Monitor object can not wait for the child process to complete its activities, as there is no well-defined endpoint in the near future, and the user probably wants to be able to enter more commands. Therefore, the Child process must run as a daemon. So the forked process terminates immediately, but its own child process continues to run (in the background). Consequently, createNewChild calls the child's fork member. Although it is the child's fork function that is called, it is still the monitor program wherein that fork function is called. So, the monitor program is duplicated by fork. Execution then continues:
- At the Child's parentProcess in its parent process;
- At the Child's childProcess in its child process
As the Child's parentProcess is an empty function, returning immediately, the Child's parent process effectively continues immediately below createNewChild's cp->fork() statement. As the child process never returns (see section 25.2.7.7), the code below cp->fork() is never executed by the Child's child process. This is exactly as it should be.
In the parent process, createNewChild's remaining code simply adds the file descriptor that's available for reading information from the child to the set of input file descriptors monitored by d_select, and uses d_child to establish the association between that file descriptor and the Child object's address:
```
    void Monitor::createNewChild(int, string const &)
    {
        Child *cp = new Child{ ++d_nr };

        cp->fork();

        int fd = cp->readFd();

        d_selector.addReadFd(fd);
        d_child[fd].reset(cp);

        cerr << "Child " << d_nr << " started\n";
    }
```
Direct communication with the child is required for the stop <nr> and <nr> text commands. The former command terminates child process <nr>, by calling stopChild. This function locates the child process having the order number using an anonymous object of the class Find, nested inside Monitor. The class Find simply compares the provided nr with the children's order number returned by their nr members:
```
    inline Monitor::Find::Find(int nr)
    :
        d_nr(nr)
    {}
    inline bool Monitor::Find::operator()(MapIntChild::value_type &vt) const
    {
        return d_nr == vt.second->nr();
    }
```
If the child process having order number nr was found, its file descriptor is removed from d_selector's set of input file descriptors. Then the child process itself is terminated by the static member killChild. The member killChild is declared as a static member function, as it is used as function argument of the for_each generic algorithm by exiting (see below). Here is killChild's implementation:
```
    void Monitor::killChild(MapIntChild::value_type it)
    {
        if (kill(it.second->pid(), SIGTERM))
            cerr << "Couldn't kill process " << it.second->pid() << '\n';

        // reap defunct child process
        int status = 0;
        while( waitpid( it.second->pid(), &status, WNOHANG) > -1)
            ;
    }
```
Having terminated the specified child process, the corresponding Child object is destroyed and its pointer is removed from d_child:
```
    void Monitor::stopChild(int nr, string const &)
    {
        auto it = find_if(d_child.begin(), d_child.end(), Find{ nr });

        if (it == d_child.end())
            cerr << "No child number " << nr << '\n';
        else
        {
            d_selector.rmReadFd(it->second->readFd());
            d_child.erase(it);
        }
    }
```

The command <nr> text sends text to child process nr using the member function sendChild. This function also uses a Find object to locate the child-process having order number nr, and simply inserts the text into the writing end of a pipe connected to that child process:

    void Monitor::sendChild(int nr, string const &line)
    {
        auto it = find_if(d_child.begin(), d_child.end(), Find(nr));

        if (it == d_child.end())
            cerr << "No child number " << nr << '\n';
        else
        {
            OFdnStreambuf ofdn{ it->second->writeFd() };
            ostream out(&ofdn);

            out << line << '\n';
        }
    }

When users enter exit or quit the member exiting is called. It terminates all child processes using the for_each generic algorithm (see section 19.1.18) to visit all elements of d_child. Then the program itself ends:

    void Monitor::exiting(int value, string const &msg)
    {
        for_each(d_child.begin(), d_child.end(), killChild);
        if (msg.length())
            cerr << msg << '\n';
        throw value;
    }

The program's main function is simple and needs no further comment:

    int main()
    try
    {
        Monitor{}.run();
    }
    catch (int exitValue)
    {
        return exitValue;
    }

25.2.7.7: The class `Child'

When the Monitor object starts a child process, it creates an object of the class Child. The Child class is derived from the class Fork, allowing it to operate as a daemon (as discussed in the previous section). Since Child is a daemon class, we know that its parent process must be defined as an empty function. Its childProcess member has a non-empty implementation. Here are the characteristics of the class Child:

The Child class has two Pipe data members, to handle communications between its own child- and parent processes. As these pipes are used by the Child's child process, their names refer to the child process. The child process reads from d_in, and writes to d_out. Here is the interface of the class Child:

    class Child: public Fork
    {
        Pipe                d_in;
        Pipe                d_out;

        int         d_parentReadFd;
        int         d_parentWriteFd;
        int         d_nr;

        public:
            Child(int nr);
            virtual ~Child();
            int readFd() const;
            int writeFd() const;
            int pid() const;
            int nr() const;
        private:
            virtual void childRedirections();
            virtual void parentRedirections();
            virtual void childProcess();
            virtual void parentProcess();
    };

The Child's constructor simply stores its argument, a child-process order number, in its own d_nr data member:
```
    inline Child::Child(int nr)
    :
        d_nr(nr)
    {}
```
The Child's child process obtains commands from its standard input stream and writes its output to its standard output stream. Since the actual communication channels are pipes, redirections must be used. The childRedirections member looks like this:
```
    void Child::childRedirections()
    {
        d_in.readFrom(STDIN_FILENO);
        d_out.writtenBy(STDOUT_FILENO);
    }
```
Although the parent process performs no actions, it must configure some redirections. Realizing that the names of the pipes indicate their functions in the child process. So the parent writes to d_in and reads from d_out. Here is parentRedirections:
```
    void Child::parentRedirections()
    {
        d_parentReadFd = d_out.readOnly();
        d_parentWriteFd = d_in.writeOnly();
    }
```
The Child object exists until it is destroyed by the Monitor's stopChild member. By allowing its creator, the Monitor object, to access the parent-side ends of the pipes, the Monitor object can communicate with the Child's child process via those pipe-ends. The members readFd and writeFd allow the Monitor object to access these pipe-ends:
```
    inline int Child::readFd() const
    {
        return d_parentReadFd;
    }
    inline int Child::writeFd() const
    {
        return d_parentWriteFd;
    }
```

The Child object's child process performs two tasks:

It must reply to information appearing at its standard input stream;
If no information has appeared within a certain time frame (the implementations uses an interval of five seconds), then a message is written to its standard output stream.

To implement this behavior, childProcess defines a local Selector object, adding STDIN_FILENO to its set of monitored input file descriptors.

Then, in an endless loop, childProcess waits for selector.wait() to return. When the alarm goes off it sends a message to its standard output (hence, into the writing pipe). Otherwise, it echoes the messages appearing at its standard input to its standard output. Here is the childProcess member:

    void Child::childProcess()
    {
        Selector    selector;
        size_t    message = 0;

        selector.addReadFd(STDIN_FILENO);
        selector.setAlarm(5);

        while (true)
        {
            try
            {
                if (!selector.wait())       // timeout
                    cout << "Child " << d_nr << ": standing by\n";
                else
                {
                    string  line;
                    getline(cin, line);
                    cout << "Child " << d_nr << ":" << ++message << ": " <<
                                                        line << '\n';
                }
            }
            catch (...)
            {
                    cout << "Child " << d_nr << ":" << ++message << ": " <<
                                "select() failed" << '\n';
            }
        }
        exit(0);
    }

Two accessors are defined allowing the Monitor object to obtain the Child's process ID and its order number:

    inline int Child::pid() const
    {
        return Fork::pid();
    }
    inline int Child::nr() const
    {
        return d_nr;
    }

A Child process terminates when the user enters a stop command. When an existing child process number was entered, the corresponding Child object is removed from Monitor's d_child map. As a result, its destructor is called. Child's destructor calls kill to terminate its child, and then waits for the child to terminate. Once its child has terminated, the destructor has completed its work and returns, thus completing the erasure from d_child. The current implementation fails if the child process doesn't react to the SIGTERM signal. In this demonstration program this does not happen. In `real life' more elaborate killing-procedures may be required (e.g., using SIGKILL in addition to SIGTERM). As discussed in section 10.12 it is important to ensure the proper destruction. Here is the Child's destructor:
```
    Child::~Child()
    {
        if (pid())
        {
            cout << "Killing process " << pid() << "\n";
            kill(pid(), SIGTERM);
            int status;
            wait(&status);
        }
    }
```

25.3: Adding binary operators to classes

As we've seen in section 11.6 binary operators expecting const & arguments can be implemented using a member implementing the operation, only offering the basic exception guarantee. This latter function can in turn be implemented using the binary assignment member. The following examples illustrated this approach for a fictitious class Binary:

    class Binary
    {
        public:
            Binary();
            Binary(int value);
                // copy and move constructors are available by default, or
                // they can be explicitly declared and implemented.

            Binary &operator+=(Binary const &other) &;    // see the text
            Binary &&operator+=(Binary const &other) &&;

        private:
            void add(Binary const &rhs);

        friend Binary operator+(Binary const &lhs, Binary const &rhs);
        friend Binary operator+(Binary &&lhs, Binary const &rhs);
    };

Eventually, the implementation of binary operators depends on the availability of the member implementing the basic binary operation, modifying the object calling that member (i.e., void Binary::add(Binary const &) in the example).

Since template functions are not instantiated before they are actually used we can call non-existing functions from template functions that are never instantiated. If such a template function is never instantiated, nothing happens; if it is (accidentally) instantiated, then the compiler generates an error message, complaining about the missing function.

This allows us to implement all binary operators, movable and non-movable, as templates. In the following subsections we develop the class template Binops, prividing binary operators. A complete implementation of a class Derived illustrating how addition and insertion operators can be added to a class is provided in the file annotations/yo/concrete/examples/binopclasses.cc in the C++ Annotations' source archive.

25.3.1: Merely using operators

In section 11.6 addition operators are implemented in terms of a support member add. This is less attractive when developing function templates, as add is a private member, requiring us to provide friend declarations for all function templates so they may access the private add member.

At the end of section 11.6 we saw that add's implementation can be provided by operator+=(Class const &rhs) &&. This operator may thereupon be used when implementing the remaining addition operators:

    inline Binary &operator+=(Binary const &rhs) &
    {
        return *this = Binary{*this} += rhs;        
    }

    Binary operator+(Binary &&lhs, Binary const &rhs)
    {
        return std::move(lhs) += rhs;
    }

    Binary operator+(Binary const &lhs, Binary const &rhs)
    {
        return Binary{lhs} += rhs;
    }

In this implementation add is no longer required. The plain binary operators are free functions, which supposedly can easily be converted to function templates. E.g.,

    template <typename Binary>
    Binary operator+(Binary const &lhs, Binary const &rhs)
    {
        return Binary{lhs} += rhs;
    }

25.3.1.1: To namespace or not to namespace?

When using the function template

Binary operator+(Binary const &lhs, Binary
const &rhs)

, however, we may encounter a subtle and unexpected complication. Consider the following program. When run, it displays the value 12, rather than 1:

    enum Values
    {
        ZERO,
        ONE
    };
    
    template <typename Tp>
    Tp operator+(Tp const &lhs, Tp const &rhs)
    {
        return static_cast<Tp>(12);
    };
    
    int main()
    {
        cout << (ZERO + ONE);       // shows 12
    }

This complication can be avoided by defining the operators in their own namespace, but then all classes using the binary operator also have to be defined in that namespace, which is not a very attractive restriction. Fortunately, there is a better alternative: using the CRTP (cf. section 22.12).

25.3.2: The CRTP and defining operator function templates

When deriving classes from a class template Binops, using the CRTP the operators are defined for arguments of the class Binops<Derived>: a base class receiving the derived class as its template argument.

Thus the class Binops as well as the additional operators are defined, expecting Binops<Derived> type of arguments:

    template <class Derived>
    struct Binops
    {
        Derived &operator+=(Derived const &rhs) &;
    };

    template <typename Derived>
    Derived operator+(Binops<Derived> const &lhs, Derived const &rhs)
    {
        return Derived{static_cast<Derived const &>(lhs) } += rhs;
    }
    // analogous implementation for Binops<Derived> &&lhs

This way, a class that derives from Binops, and that provides an operator+= member which is bound to an rvalue reference object, suddenly also provides all other binary addition operators:

    class Derived: public Binops<Derived>
    {
        ...
        public:
            ...
            Derived &&operator+=(Derived const &rhs) &&
    };

All, but one....

The operator that's not available is the compound addition operator, bound to an lvalue reference. As its function name is identical to the one in the class Derived, it is not automatically visible at the user level.

Although this problem can simply be solved by providing the class Derived with a using Binops<Derived>::operator+= declaration, it is not a very attractive solution, as separate using declarations have to be provided for each binary operator that is implemented in the class Derived.

But a much more attractive solution exists. A beautiful out-of-the-box solution, completely avoiding the hidden base class operator, was proposed by Wiebe-Marten Wijnja. Wiebe-Marten conjectured that operator+=, bound to an lvalue reference could also very well be defined as a free function. In that case no inheritance is used and therefore no function hiding occurs. Consequently, the using directive can be avoided.

The implementation of this free operator+= function looks like this:

    template <class Derived>
    Derived &operator+=(Binops<Derived> &lhs, Derived const &rhs) 
    {
        Derived tmp{ Derived{ static_cast<Derived &>(lhs) } += rhs };
        tmp.swap(static_cast<Derived &>(lhs));
        return static_cast<Derived &>(lhs);
    }

The flexibility of this design can be further augmented once we realize that the right-hand side operand doesn't have to be a Derived class object. Consider operator<<: oftentimes shifts are bit-shifts, using a size_t to specify the number of bits to shift. In fact, the type of the right-hand side operand can completely be generalized by defining a second template type parameter, which is used to specify the right-hand side's operand type. It's up to the Derived class to specify the argument type of its operator+= (or any other binary compound operator), whereafter the compiler will deduce the types of the right-hand side operands for the remaining binary operators. Here is the final implementation of the free operator+= function:

    template <class Derived, typename Rhs>
    Derived &operator+=(Binops<Derived> &lhs, Rhs const &rhs) 
    {
        Derived tmp{ Derived{ static_cast<Derived &>(lhs) } += rhs };
        tmp.swap(static_cast<Derived &>(lhs));
        return static_cast<Derived &>(lhs);
    }

25.3.3: Insertion and extraction

Classes also frequently define overloaded insertion and extraction operators. Since there are no `compound insertion operators' the design shown so far cannot be used when overloading these operators. Instead using standardized member function signatures is advocated:

void
insert(std::ostream &out) const

to insert an object into an ostream and void extract(std::istream &in) const to extract an object from an istream. As these functions are only used by, respectively, the insertion and extraction operators, they can be declared in the Derived class's private interface. Instead of declaring the insertion and extraction operators friends of the class Derived a single friend Binops<Derived> is specified. This allows Binops<Derived> to define private, inline iWrap and eWrap members, merely calling, respectively, Derived's insert and extract members:

    template <typename Derived>
    inline void Binops<Derived>::iWrap(std::ostream &out) const
    {
        static_cast<Derived const &>(*this).insert(out);
    }

Binops<Derived> then declares the insertion and extraction operators as its friends, allowing these operators to call, respectively, iWrap and eWrap. Note that the software engineer designing the class Derived only has to provide a friend Binops<Derived> declaration. Here is the implementation of the overloaded insertion operator:

    template <typename Derived>
    std::ostream &operator<<(std::ostream &out, Binops<Derived> const &obj)
    {
        obj.iWrap(out);
        return out;
    }

This completes the coverage of the essentials of a class template Binops potentially offering binary operators and insertion/extraction operators for any class derived from Binops. Finally, as noted at the beginning of this section, a complete implementation of a class offering addition and insertion operators is provided in the file annotations/yo/concrete/examples/binopclasses.cc in the C++ Annotations' source archive.

25.4: Distinguishing lvalues from rvalues with operator[]()

A problem with operator[] is that it can't distinguish between its use as an lvalue and as an rvalue. It is a familiar misconception to think that

    Type const &operator[](size_t index) const

is used as rvalue (as the object isn't modified), and that

    Type &operator[](size_t index)

is used as lvalue (as the returned value can be modified).

The compiler, however, distinguishes between the two operators only by the const-status of the object for which operator[] is called. With const objects the former operator is called, with non-const objects the latter is always used. It is always used, irrespective of it being used as lvalue or rvalue.

Being able to distinguish between lvalues and rvalues can be very useful. Consider the situation where a class supporting operator[] stores data of a type that is very hard to copy. With data like that reference counting (e.g., using shared_ptrs) is probably used to prevent needless copying.

As long as operator[] is used as rvalue there's no need to copy the data, but the information must be copied if it is used as lvalue.

The Proxy Design Pattern (cf. Gamma et al. (1995)) can be used to distinguish between lvalues and rvalues. With the Proxy Design Pattern an object of another class (the Proxy class) is used to act as a stand in for the `real thing'. The proxy class offers functionality that cannot be offered by the data themselves, like distinguishing between its use as lvalue or rvalue. A proxy class can be used in many situations where access to the real data cannot or should not be directly provided. In this regard iterator types are examples of proxy classes as they create a layer between the real data and the software using the data. Proxy classes could also dereference pointers in a class storing its data by pointers.

In this section we concentrate on the distinction between using operator[] as lvalue and rvalue. Let's assume we have a class Lines storing lines from a file. Its constructor expects the name of a stream from which the lines are read and it offers a non-const operator[] that can be used as lvalue or rvalue (the const version of operator[] is omitted as it causes no confusion because it is always used as rvalue):

    class Lines
    {
        std::vector<std::string> d_line;

        public:
            Lines(std::istream &in);
            std::string &operator[](size_t idx);
    };

To distinguish between lvalues and rvalues we must find distinguishing characteristics of lvalues and rvalues that we can exploit. Such distinguishing characteristics are operator= (which is always used as lvalue) and the conversion operator (which is always used as rvalue). Rather than having operator[] return a string & we can let it return a Proxy object that is able to distinguish between its use as lvalue and rvalue.

The class Proxy thus needs operator=(string const &other) (acting as lvalue) and operator std::string const &() const (acting as rvalue). Do we need more operators? The std::string class also offers operator+=, so we should probably implement that operator as well. Plain characters can also be assigned to string objects (even using their numeric values). As string objects cannot be constructed from plain characters promotion cannot be used with operator=(string const &other) if the right-hand side argument is a character. Implementing operator=(char value) could therefore also be considered. These additional operators are left out of the current implementation but `real life' proxy classes should consider implementing these additional operators as well. Another subtlety is that Proxy's operator std::string const &() const is not used when using ostream's insertion operator or istream's extraction operator as these operators are implemented as templates not recognizing our Proxy class type. So when stream insertion and extraction is required (it probably is) then Proxy must be given its own overloaded insertion and extraction operator. Here is an implementation of the overloaded insertion operator inserting the object for which Proxy is a stand-in:

inline std::ostream &operator<<(std::ostream &out, Lines::Proxy const &proxy)
{
    return out << static_cast<std::string const &>(proxy);
}

There's no need for any code (except Lines) to create or copy Proxy objects. Proxy's constructor should therefore be made private, and Proxy can declare Lines to be its friend. In fact, Proxy is intimately related to Lines and can be defined as a nested class. In the revised Lines class operator[] no longer returns a string but instead a Proxy is returned. Here is the revised Lines class, including its nested Proxy class:

    class Lines
    {
        std::vector<std::string> d_line;

        public:
            class Proxy;
            Proxy operator[](size_t idx);
            class Proxy
            {
                friend Proxy Lines::operator[](size_t idx);
                std::string &d_str;
                Proxy(std::string &str);
                public:
                    std::string &operator=(std::string const &rhs);
                    operator std::string const &() const;
            };
            Lines(std::istream &in);
    };

Proxy's members are very lightweight and can usually be implemented inline:

    inline Lines::Proxy::Proxy(std::string &str)
    :
        d_str(str)
    {}
    inline std::string &Lines::Proxy::operator=(std::string const &rhs)
    {
        return d_str = rhs;
    }
    inline Lines::Proxy::operator std::string const &() const
    {
        return d_str;
    }

The member Lines::operator[] can also be implemented inline: it merely returns a Proxy object initialized with the string associated with index idx.

Now that the class Proxy has been developed it can be used in a program. Here is an example using the Proxy object as lvalue or rvalue. On the surface Lines objects won't behave differently from Lines objects using the original implementation, but by adding an identifying cout statement to Proxy's members it can be shown that operator[] behaves differently when used as lvalue or as rvalue:

    int main()
    {
        ifstream in("lines.cc");
        Lines lines(in);

        string s = lines[0];        // rvalue use
        lines[0] = s;               // lvalue use
        cout << lines[0] << '\n';   // rvalue use
        lines[0] = "hello world";   // lvalue use
        cout << lines[0] << '\n';   // rvalue use
    }

25.5: Implementing a `reverse_iterator'

In section 22.14.1 the construction of iterators and reverse iterators was discussed. In that section the iterator was constructed as an inner class in a class derived from a vector of pointers to strings.

An object of this nested iterator class handles the dereferencing of the pointers stored in the vector. This allowed us to sort the strings pointed to by the vector's elements rather than the pointers.

A drawback of this is that the class implementing the iterator is closely tied to the derived class as the iterator class was implemented as a nested class. What if we would like to provide any class derived from a container class storing pointers with an iterator handling pointer-dereferencing?

In this section a variant of the earlier (nested class) approach is discussed. Here the iterator class is defined as a class template, not only parameterizing the data type to which the container's elements point but also the container's iterator type itself. Once again, we concentrate on developing a RandomIterator as it is the most complex iterator type.

Our class is named RandomPtrIterator, indicating that it is a random iterator operating on pointer values. The class template defines three template type parameters:

The first parameter specifies the derived class type (Class). Like before, RandomPtrIterator's constructor is private. Therefore friend declarations are needed to allow client classes to construct RandomPtrIterators. However, a friend class Class cannot be used as template parameter types cannot be used in friend class ... declarations. But this is a minor problem as not every member of the client class needs to construct iterators. In fact, only Class's begin and end members must construct iterators. Using the template's first parameter, friend declarations can be specified for the client's begin and end members.
The second template parameter parameterizes the container's iterator type (BaseIterator);
The third template parameter indicates the data type to which the pointers point (Type).

RandomPtrIterator has one private data member, a BaseIterator. Here is the class interface and the constructor's implementation:

    #include <iterator>
    #include <compare>

    template <typename Class, typename BaseIterator, typename Type>
    struct RandomPtrIterator;

    #define PtrIterator RandomPtrIterator<Class, BaseIterator, Type>
    #define PtrIteratorValue RandomPtrIterator<Class, BaseIterator, value_type>

    template <typename Class, typename BaseIterator, typename Type>
    bool operator==(PtrIterator const &lhs, PtrIterator const &rhs);

    template <typename Class, typename BaseIterator, typename Type>
    auto operator<=>(PtrIterator const &lhs, PtrIterator const &rhs);

    template <typename Class, typename BaseIterator, typename Type>
    int operator-(PtrIterator const &lhs, PtrIterator const &rhs);

    template <typename Class, typename BaseIterator, typename Type>
    struct RandomPtrIterator
    {
        using iterator_category = std::random_access_iterator_tag;
        using difference_type   = std::ptrdiff_t;
        using value_type        = Type;
        using pointer           = value_type *;
        using reference         = value_type &;


        friend PtrIterator Class::begin();
        friend PtrIterator Class::end();

        friend bool operator==<>(RandomPtrIterator const &lhs,
                                 RandomPtrIterator const &rhs);
        friend auto operator<=><>(RandomPtrIterator const &lhs,
                                  RandomPtrIterator const &rhs);
        friend int operator-<>(RandomPtrIterator const &lhs,
                               RandomPtrIterator const &rhs);
        private:
            BaseIterator d_current;

        public:
            int operator-(RandomPtrIterator const &rhs) const;
            RandomPtrIterator operator+(int step) const;
            value_type &operator*() const;
            RandomPtrIterator &operator--();
            RandomPtrIterator operator--(int);
            RandomPtrIterator &operator++();
            RandomPtrIterator operator++(int);
            RandomPtrIterator operator-(int step) const;
            RandomPtrIterator &operator-=(int step);
            RandomPtrIterator &operator+=(int step);
            value_type *operator->() const;

        private:
            RandomPtrIterator(BaseIterator const &current);
    };

    template <typename Class, typename BaseIterator, typename value_type>
    PtrIteratorValue::RandomPtrIterator(BaseIterator const &current)
    :
        d_current(current)
    {}

Looking at its friend declarations, we see that the members begin and end of a class Class, returning a RandomPtrIterator object for the types Class, BaseIterator and Type are granted access to RandomPtrIterator's private constructor. That is exactly what we want. The Class's begin and end members are declared as bound friends.

All RandomPtrIterator's remaining members are public. Since RandomPtrIterator is just a generalization of the nested class iterator developed in section 22.14.1, re-implementing the required member functions is easy and only requires us to change iterator into RandomPtrIterator and to change std::string into Type. For example, operator<, defined in the class iterator as is now implemented as:

    template <typename Class, typename BaseIterator, typename Type>
    inline auto operator<=>(PtrIterator const &lhs, PtrIterator const &rhs)
    {
        return **lhs.d_current <=> **rhs.d_current;
    }

Some additional examples: operator*, defined in the class iterator as

inline std::string &StringPtr::iterator::operator*() const
{
    return **d_current;
}

is now implemented as:

    template <typename Class, typename BaseIterator, typename value_type>
    value_type &PtrIteratorValue::operator*() const
    {
        return **d_current;
    }

The pre- and postfix increment operators are now implemented as:

    template <typename Class, typename BaseIterator, typename value_type>
    PtrIteratorValue &PtrIteratorValue::operator++()
    {
        ++d_current;
        return *this;
    }
    template <typename Class, typename BaseIterator, typename value_type>
    PtrIteratorValue PtrIteratorValue::operator++(int)
    {
        return RandomPtrIterator(d_current++);
    }

Remaining members can be implemented accordingly, their actual implementations are left as exercises to the reader (or can be obtained from the cplusplus.yo.zip archive, of course).

Re-implementing the class StringPtr developed in section 22.14.1 is not difficult either. Apart from including the header file defining the class template RandomPtrIterator, it only requires a single modification. Its iterator using-declaration must now be associated with a RandomPtrIterator. Here is the full class interface and the class's inline member definitions:

    #ifndef INCLUDED_STRINGPTR_H_
    #define INCLUDED_STRINGPTR_H_

    #include <vector>
    #include <string>
    #include "iterator.h"

    class StringPtr: public std::vector<std::string *>
    {
        public:
            using iterator =
                    RandomPtrIterator
                    <
                        StringPtr,
                        std::vector<std::string *>::iterator,
                        std::string
                    >;

            using reverse_iterator = std::reverse_iterator<iterator>;

            iterator begin();
            iterator end();
            reverse_iterator rbegin();
            reverse_iterator rend();
    };

    inline StringPtr::iterator StringPtr::begin()
    {
        return iterator(this->std::vector<std::string *>::begin() );
    }
    inline StringPtr::iterator StringPtr::end()
    {
        return iterator(this->std::vector<std::string *>::end());
    }
    inline StringPtr::reverse_iterator StringPtr::rbegin()
    {
        return reverse_iterator(end());
    }
    inline StringPtr::reverse_iterator StringPtr::rend()
    {
        return reverse_iterator(begin());
    }
    #endif

Including StringPtr's modified header file into the program given in section 22.14.2 results in a program behaving identically to its earlier version. In this case StringPtr::begin and StringPtr::end return iterator objects constructed from a template definition.

25.6: Using `bisonc++' and `flexc++'

The example discussed below digs into the peculiarities of using parser- and scanner generators generating C++ sources. Once the input for a program exceeds a certain level of complexity, it becomes attractive to use scanner- and parser-generators generating the code which does the actual input recognition.

The examples in this and subsequent sections assume that the reader knows how to use the scanner generator flex and the parser generator bison. Both bison and flex are well documented elsewhere. The original predecessors of bison and flex, called yacc and lex are described in several books, e.g. in O'Reilly's book `lex & yacc'.

Scanner- and parser generators are also available as free software. Both bison and flex are usually part of software distributions or they can be obtained from ftp://prep.ai.mit.edu/pub/non-gnu. Flex creates a C++ class when %option c++ is specified.

For parser generators the program bison is available. In the early 90's Alain Coetmeur (coetmeur@icdc.fr) created a C++ variant (bison++) creating a parser class. Although the bison++ program produces code that can be used in C++ programs it also shows many characteristics that are more suggestive of a C context than a C++ context. In January 2005 I rewrote parts of Alain's bison++ program, resulting in the original version of the program bisonc++. Then, in May 2005 a complete rewrite of the bisonc++ parser generator was completed (version number 0.98). Current versions of bisonc++ can be downloaded from https://fbb-git.gitlab.io/bisoncpp/. Binary versions for various architectures are available as, e.g., Debian package (including bisonc++'s documentation).

Bisonc++ creates a cleaner parser class than bison++. In particular, it derives the parser class from a base-class, containing the parser's token- and type-definitions as well as all member functions which should not be (re)defined by the programmer. As a result of this approach, the generated parser class is very small, declaring only members that are actually defined by the programmer (as well as some other members, generated by bisonc++ itself, implementing the parser's parse() member). One member that is not implemented by default is lex, producing the next lexical token. When the directive %scanner (see section 25.6.2.1) is used, bisonc++ produces a standard implementation for this member; otherwise it must be implemented by the programmer.

In early 2012 the program flexc++ http://flexcpp.org/ reached its initial release. Like bisonc++ it is part of the Debian linux distribution.

Jean-Paul van Oosten (j.p.van.oosten@rug.nl) and Richard Berendsen (richardberendsen@xs4all.nl) started the flexc++ project in 2008 and the final program was completed by Jean-Paul and me between 2010 and 2012.

These sections of the C++ Annotations focus on bisonc++ as our parser generator and flexc++ as our lexical scanner generator. Previous releases of the C++ Annotations were using flex as the scanner generator.

Using flex++ and bisonc++ class-based scanners and parsers are generated. The advantage of this approach is that the interface to the scanner and the parser tends to become cleaner than without using class interfaces. Furthermore, classes allow us to get rid of most if not all global variables, making it easy to use multiple parsers in one program.

Below two example programs are developed. The first example only uses flexc++. The generated scanner monitors the production of a file from several parts. That example focuses on the lexical scanner and on switching files while churning through the information. The second example uses both flexc++ and bisonc++ to generate a scanner and a parser transforming standard arithmetic expressions to their postfix notations, commonly used in code generated by compilers and in HP-calculators. In the second example the emphasis is mainly on bisonc++ and on composing a scanner object inside a generated parser.

25.6.1: Using `flexc++' to create a scanner

The lexical scanner developed in this section is used to monitor the production of a file from several subfiles. The setup is as follows: the input-language defines #include directives, followed by a text string specifying the file (path) which should be included at the location of the #include.

In order to avoid complexities irrelevant to the current example, the format of the #include statement is restricted to the form #include <filepath>. The file specified between the angle brackets should be available at the location indicated by filepath. If the file is not available, the program terminates after issuing an error message.

The program is started with one or two filename arguments. If the program is started with just one filename argument, the output is written to the standard output stream cout. Otherwise, the output is written to the stream whose name is given as the program's second argument.

The program defines a maximum nesting depth. Once this maximum is exceeded, the program terminates after issuing an error message. In that case, the filename stack indicating where which file was included is printed.

An additional feature of the program is that (standard C++) comment-lines are ignored. Include-directives in comment-lines are also ignored.

The program is created in five major steps:

First, the file lexer is constructed, containing the input-language specifications.
From the specifications in lexer the requirements for the class Scanner evolve. The Scanner class derives from the base class ScannerBase generated by flexc++.
Next, main is constructed. A Scanner object is created inspecting the command-line arguments. If successful, the scanner's member lex is called to produce the program's output.
Now that the global setup of the program has been specified, the member functions of the various classes are implemented.
Finally, the program is compiled and linked.

25.6.1.1: The derived class `Scanner'

The function matching the regular expression rules (lex) is a member of the class Scanner. Since Scanner is derived from ScannerBase, it has access to all of ScannerBase's protected members that execute the lexical scanner's regular expression matching algorithm.

Looking at the regular expressions themselves, notice that we need rules to recognize comment, #include directives, and all remaining characters. This all is fairly standard practice. When an #include directive is sensed, the directive is parsed by the scanner. This too is common practice. Our lexical scanner performs the following tasks:

As usual, preprocessor directives are not analyzed by a parser, but by the lexical scanner;
The scanner uses a mini scanner to extract the filename from the directive, throwing a exception if this fails;
If the filename could be extracted, processing switches to the next stream, controlling for a maximum nesting depth.
Once the end of the current file has been reached processing automatically returns to the previous file, restoring the previous file name and line number. The scanner returns 0 if all files have been processed.

25.6.1.2: The lexical scanner specification file

The lexical scanner specification file is organized comparably to the one used for flex in C contexts. However, in C++ contexts, flexc++ creates a class Scanner, rather than just a scanner function.

Flexc++'s specification file consists of two sections:

The specification file's first section is flexc++'s symbol area, used to define symbols, like a mini scanner, or options. The following options are suggested:
- %debug: includes debugging code into the code generated by flexc++. Calling the member function setDebug(true) activates this debugging code at run-time. When activated, information about the matching process is written to the standard output stream. The execution of debug code is suppressed after calling the member function setDebug(false).
- %filenames: defines the base-name of the class header files generated by flexc++. By default the class name (itself using the default Scanner) is used.
Here is the specification files' symbol area:
```
%filenames scanner
%debug
%max-depth 3

%x      comment
%x      include
```

The specification file's second section is a rules section in which the regular expressions and their associated actions are defined. In the example developed here, the lexer should copy information from the standard input stream (std::cin) to the standard output stream (std::cout). For this the predefined macro ECHO can be used. Here are the rules:

%%
    // The comment-rules: comment is ignored.
//.*                    // ignore eoln comment
"/*"                    begin(StartCondition__::comment);
<comment>{
    .|\n                // ignore all characters in std C comment
    "*/"                begin(StartCondition__::INITIAL);
}

    // File switching: #include <filepath>
#include[ \t]+"<"      begin(StartCondition__::include);
<include>{
    [^ \t>]+            d_nextSource = matched();
    ">"[ \t]*\n         switchSource();
    .|\n                throw runtime_error("Invalid include statement");
}

    // The default rule: echo anything else to std::cout
.|\n                    echo();

25.6.1.3: Implementing `Scanner'

The class Scanner is generated once by flexc++. This class has access to several members defined by its base class ScannerBase. Some of these members have public access rights and can be used by code external to the class Scanner. These members are extensively documented in the flexc++(1) man-page, and the reader is referred to this man-page for further information.

Our scanner performs the following tasks:

it matches regular expressions, ignoring comment, and writing the matched text to the standard output stream;
it switches to other files, and returns to the previous file once a file has completely been processed, ending the lexical scan once the end of the first input file has been reached.

The #include statements in the input allow the scanner to distill the name of the file where the scanning process must continue. This file name is stored in a local variable d_nextSource and a member stackSource handles the switch to the next source. Nothing else is required. Pushing and popping input files is handled by the scanner's members pushStream and popStream, provided by flexc++. Scanner's interface, therefore, only needs one additional function declaration: switchSource.

Switching streams is handled as follows: once the scanner has extracted a filename from an #include directive, a switch to another file is realized by switchSource. This member calls pushStream, defined by flexc++, to stack the current input stream and to switch to the stream whose name is stored in d_nextSource. This also ends the include mini-scanner, so to return the scanner to its default scanning mode begin(StartCondition__::INITIAL) is called. Here is its source:

#include "scanner.ih"

void Scanner::switchSource()
{
    pushStream(d_nextSource);
    begin(StartCondition__::INITIAL);
}

The member pushStream, defined by flexc++, handles all necessary checks, throwing an exception if the file could not be opened or if too many files are stacked.

The member performing the lexical scan is defined by flexc++ in Scanner::lex, and this member can be called by code to process the tokens returned by the scanner.

25.6.1.4: Using a `Scanner' object

The program using our Scanner is very simple. It expects a filename indicating where to start the scanning process.

The program first checks the number of arguments. If at least one argument was given, then that argument is passed to Scanner's constructor, together with a second argument "-", indicating that the output should go to the standard output stream.

If the program receives more than one argument debug output, extensively documenting the lexical scanner's actions, is written to the standard output stream as well.

Next the Scanner's lex member is called. If anything fails, a std::exception is thrown, which is caught by main's try-block's catch clause. Here is the program's source:

#include "lexer.ih"

int main(int argc, char **argv)
try
{
    if (argc == 1)
    {
        cerr << "Filename argument required\n";
        return 1;
    }

    Scanner scanner(argv[1], "-");

    scanner.setDebug(argc > 2);

    return scanner.lex();
}
catch (exception const &exc)
{
    cerr << exc.what() << '\n';
    return 1;
}

25.6.1.5: Building the program

The final program is constructed in two steps. These steps are given for a Unix system, on which flexc++ and the GNU C++ compiler g++ have been installed:

First, the lexical scanner's source is created using flexc++. For this the following command can be given:
```
    flexc++ lexer
```
Next, all sources are compiled and linked:
```
    g++ -Wall *.cc
```

Flexc++ can be downloaded from https://fbb-git.gitlab.io/flexcpp/, and requires the bobcat library, which can be downloaded from http://fbb-git.gitlab.io/bobcat/.

25.6.2: Using `bisonc++' and `flexc++'

Once an input language exceeds a certain level of complexity, a parser is often used to control the complexity of the language. In this case, a parser generator can be used to generate the code verifying the input's grammatical correctness. The lexical scanner (preferably composed into the parser) provides chunks of the input, called tokens. The parser then processes the series of tokens generated by the lexical scanner.

Starting point when developing programs that use both parsers and scanners is the grammar. The grammar defines a set of tokens that can be returned by the lexical scanner (called the scanner below).

Finally, auxiliary code is provided to `fill in the blanks': the actions performed by the parser and by the scanner are not normally specified literally in the grammar rules or lexical regular expressions, but should be implemented in member functions, called from the parser's rules or which are associated with the scanner's regular expressions.

In the previous section we've seen an example of a C++ class generated by flexc++. In the current section we concentrate on the parser. The parser can be generated from a grammar specification file, processed by the program bisonc++. The grammar specification file required by bisonc++ is similar to the file processed by bison (or bison++, bisonc++'s predecessor, written in the early nineties by Alain Coetmeur).

In this section a program is developed converting infix expressions, where binary operators are written between their operands, to postfix expressions, where operators are written behind their operands. Also, the unary operator - is converted from its prefix notation to a postfix form. The unary + operator is ignored as it requires no further actions. In essence our little calculator is a micro compiler, transforming numeric expressions into assembly-like instructions.

Our calculator recognizes a rather basic set of operators: multiplication, addition, parentheses, and the unary minus. We'll distinguish real numbers from integers, to illustrate a subtlety in bison-like grammar specifications. That's all. The purpose of this section is, after all, to illustrate the construction of a C++ program that uses both a parser and a lexical scanner, rather than to construct a full-fledged calculator.

In the coming sections we'll develop the grammar specification for bisonc++. Then, the regular expressions for the scanner are specified. Following that, the final program is constructed.

25.6.2.1: The `bisonc++' specification file

The grammar specification file required by bisonc++ is comparable to the specification file required by bison. Differences are related to the class nature of the resulting parser. Our calculator distinguishes real numbers from integers, and supports a basic set of arithmetic operators.

Bisonc++ should be used as follows:

As usual, a grammar is defined. With bisonc++ this is no different, and bisonc++ grammar definitions are for all practical purposes identical to bison's grammar definitions.
Having specified the grammar and (usually) some declarations bisonc++ can generate files defining the parser class and the implementation of the member function parse.
All class members (except those that are required for the proper functioning of the member parse) must be separately implemented. Of course, they should also be declared in the parser class's header. At the very least the member lex must be implemented. This member is called by parse to obtain the next available token. However, bisonc++ offers a facility providing a standard implementation of the function lex. The member function error(char const *msg) is given a simple default implementation that may be modified by the programmer. The member function error is called when parse detects (syntactic) errors.
The parser can now be used in a program. A very simple example would be:
```
int main()
{
    Parser parser;
    return parser.parse();
}
```

The bisonc++ specification file has two sections:

The declaration section. In this section bison's tokens, and the priority rules for the operators are declared. However, bisonc++ also supports several new declarations. These new declarations are important and are discussed below.
The rules section. The grammatical rules define the grammar. This section is identical to the one required by bison, albeit that some members that were available in bison and bison++ are obsolete in bisonc++, while other members can be used in a wider context. For example, ACCEPT and ABORT can be called from any member called from the parser's action blocks to terminate the parsing process.

Readers familiar with bison may note that there is no header section anymore. Header sections are used by bison to provide for the necessary declarations allowing the compiler to compile the C function generated by bison. In C++ declarations are part of or already used by class definitions. Therefore, a parser generator generating a C++ class and some of its member functions does not require a header section anymore.

The declaration section

The declaration section contains several sets of declarations, among which definitions of all the tokens used in the grammar and the priorities and associativities of the mathematical operators. Moreover, several new and important specifications can be used here as well. Those relevant to our current example and only available in bisonc++ are discussed here. The reader is referred to bisonc++'s man-page for a full description.

%baseclass-preinclude header
Use header as the pathname to the file pre-included in the parser's base-class header. This declaration is useful in situations where the base class header file refers to types which might not yet be known. E.g., with %union a std::string * field might be used. Since the class std::string might not yet be known to the compiler once it processes the base class header file we need a way to inform the compiler about these classes and types. The suggested procedure is to use a pre-include header file declaring the required types. By default header is surrounded by double quotes (using, e.g., #include "header"). When the argument is surrounded by angle brackets #include <header> is included. In the latter case, quotes might be required to escape interpretation by the shell (e.g., using -H '<header>').
%filenames header
Defines the generic name of all generated files, unless overridden by specific names. By default the generated files use the class-name as the generic file name.
%scanner header
Use header as the pathname to the file pre-included in the parser's class header. This file should define a class Scanner, offering a member int lex() producing the next token from the input stream to be analyzed by the parser generated by bisonc++. When this option is used the parser's member int lex() is predefined as (assuming the default parser class name Parser is used):
```
inline int Parser::lex()
{
    return d_scanner.lex();
}
```
and an object Scanner d_scanner is composed into the parser. The d_scanner object is constructed by its default constructor. If another constructor is required, the parser class may be provided with an appropriate (overloaded) parser constructor after having constructed the default parser class header file using bisonc++. By default header is surrounded by double quotes (using, e.g., #include "header"). When the argument is surrounded by angle brackets #include <header> is included.
%stype typename
The type of the semantic value of tokens. The specification typename should be the name of an unstructured type (e.g., size_t). By default it is int. See YYSTYPE in bison. It should not be used if a %union specification is used. Within the parser class, this type may be used as STYPE.
%union union-definition
Acts identically to the bison declaration. As with bison this generates a union for the parser's semantic type. The union type is named STYPE. If no %union is declared, a simple stack-type may be defined using the %stype declaration. If no %stype declaration is used, the default stacktype (int) is used.

An example of a %union declaration is:

    %union
    {
        int     i;
        double  d;
    };

In pre-C++11 code a union cannot contain objects as its fields, as constructors cannot be called when a union is created. This means that a string cannot be a member of the union. A string *, however, is a possible union member. It might also be possible to use unrestricted unions (cf. section 9.9), having class type objects as fields.

As an aside: the scanner does not have to know about such a union. It can simply pass its scanned text to the parser through its matched member function. For example using a statement like

    $$.i = A2x(d_scanner.matched());

matched text is converted to a value of an appropriate type.

Tokens and non-terminals can be associated with union fields. This is strongly advised, as it prevents type mismatches, since the compiler may then check for type correctness. At the same time, the bison specific variables $$, $1, $2, etc. may be used, rather than the full field specification (like $$.i). A non-terminal or a token may be associated with a union field using the <fieldname> specification. E.g.,

    %token <i> INT          // token association (deprecated, see below)
           <d> DOUBLE
    %type  <i> intExpr      // non-terminal association

In the example developed here, both the tokens and the non-terminals can be associated with a union field. However, as noted before, the scanner does not have to know about all this. In our opinion, it is cleaner to let the scanner do just one thing: scan texts. The parser, knowing what the input is all about, may then convert strings like "123" to an integer value. Consequently, the association of a union field and a token is discouraged. Below, while describing the grammar's rules, this is further illustrated.

In the %union discussion the %token and %type specifications should be noted. They are used to specify the tokens (terminal symbols) that can be returned by the scanner, and to specify the return types of non-terminals. Apart from %token the token declarators %left, %right, and %nonassoc can be used to specify the associativity of operators. The tokens mentioned at these indicators are interpreted as tokens indicating operators, associating in the indicated direction. The precedence of operators is defined by their order: the first specification has the lowest priority. To overrule a certain precedence in a certain context %prec can be used. As all this is standard bisonc++ practice, it isn't further elaborated here. The documentation provided with bisonc++'s distribution should be consulted for further reference.

Here is the specification of the calculator's declaration section:

%filenames parser
%scanner ../scanner/scanner.h

%union {
    int i;
    double d;
};

%token  INT DOUBLE

%type   <i> intExpr
%type   <d> doubleExpr

%left   '+'
%left   '*'
%right  UnaryMinus

In the declaration section %type specifiers are used, associating the intExpr rule's value (see the next section) to the i-field of the semantic-value union, and associating doubleExpr's value to the d-field. This approach, admittedly, is rather complex, as expression rules must be included for each of the supported union types. Alternatives are definitely possible, and involve the use of polymorphic semantic values, covered in detail in the Bisonc++ user guide.

The grammar rules

The rules and actions of the grammar are specified as usual. The grammar for our little calculator is given below. There are quite a few rules, but they illustrate various features offered by bisonc++. In particular, note that no action block requires more than a single line of code. This keeps the grammar simple, and therefore enhances its readability and understandability. Even the rule defining the parser's proper termination (the empty line in the line rule) uses a single member function called done. The implementation of that function is simple, but it is worth while noting that it calls Parser::ACCEPT, showing that ACCEPT can be called indirectly from a production rule's action block. Here are the grammar's production rules:

    lines:
        lines
        line
    |
        line
    ;

    line:
        intExpr
        '\n'
        {
            display($1);
        }
    |
        doubleExpr
        '\n'
        {
            display($1);
        }
    |
        '\n'
        {
            done();
        }
    |
        error
        '\n'
        {
            reset();
        }
    ;

    intExpr:
        intExpr '*' intExpr
        {
            $$ = exec('*', $1, $3);
        }
    |
        intExpr '+' intExpr
        {
            $$ = exec('+', $1, $3);
        }
    |
        '(' intExpr ')'
        {

            $$ = $2;
        }
    |
        '-' intExpr         %prec UnaryMinus
        {
            $$ = neg($2);
        }
    |
        INT
        {
            $$ = convert<int>();
        }
    ;

    doubleExpr:
        doubleExpr '*' doubleExpr
        {
            $$ = exec('*', $1, $3);
        }
    |
        doubleExpr '*' intExpr
        {
            $$ = exec('*', $1, d($3));
        }
    |
        intExpr '*' doubleExpr
        {
            $$ = exec('*', d($1), $3);
        }
    |
        doubleExpr '+' doubleExpr
        {
            $$ = exec('+', $1, $3);
        }
    |
        doubleExpr '+' intExpr
        {
            $$ = exec('+', $1, d($3));
        }
    |
        intExpr '+' doubleExpr
        {
            $$ = exec('+', d($1), $3);
        }
    |
        '(' doubleExpr ')'
        {
            $$ = $2;
        }
    |
        '-' doubleExpr         %prec UnaryMinus
        {

            $$ = neg($2);
        }
    |
        DOUBLE
        {
            $$ = convert<double>();
        }
    ;

This grammar is used to implement a simple calculator in which integer and real values can be negated, added, and multiplied and in which standard priority rules can be overruled by parentheses. The grammar shows the use of typed nonterminal symbols: doubleExpr is linked to real (double) values, intExpr is linked to integer values. Precedence and type association is defined in the parser's definition section.

The Parser's header file

Several class members called from the grammar are defined as member templates. Bisonc++ generates multiple files, among which the file defining the parser's class. Functions called from the production rule's action blocks are usually member functions of the parser. These member functions must be declared and defined. Once bisonc++ has generated the header file defining the parser's class, that header file isn't automatically rewritten, allowing the programmer to add new members to the parser class whenever required. Here is `parser.h' as used in our little calculator:

#ifndef Parser_h_included
#define Parser_h_included

#include <iostream>
#include <sstream>
#include <bobcat/a2x>

#include "parserbase.h"
#include "../scanner/scanner.h"

#undef Parser
class Parser: public ParserBase
{
    std::ostringstream d_rpn;
    // $insert scannerobject
    Scanner d_scanner;

    public:
        int parse();

    private:
        template <typename Type>
        Type exec(char c, Type left, Type right);

        template <typename Type>
        Type neg(Type op);

        template <typename Type>
        Type convert();

        void display(int x);
        void display(double x);
        void done() const;
        void reset();
        void error(char const *msg);
        int lex();
        void print();

        static double d(int i);

    // support functions for parse():

        void executeAction(int d_ruleNr);
        void errorRecovery();
        int lookup(bool recovery);
        void nextToken();
        void print__();
};

inline double Parser::d(int i)
{
    return i;
}

template <typename Type>
Type Parser::exec(char c, Type left, Type right)
{
    d_rpn << " " << c << " ";
    return c == '*' ? left * right : left + right;
}

template <typename Type>
Type Parser::neg(Type op)
{
    d_rpn << " n ";
    return -op;
}

template <typename Type>
Type Parser::convert()
{
    Type ret = FBB::A2x(d_scanner.matched());
    d_rpn << " " << ret << " ";
    return ret;
}

inline void Parser::error(char const *msg)
{
    std::cerr << msg << '\n';
}

inline int Parser::lex()
{
    return d_scanner.lex();
}

inline void Parser::print()
{}

#endif

25.6.2.2: The `flexc++' specification file

The flex-specification file used by the calculator is simple: blanks are ignored, single characters are returned, and numeric values are returned as either Parser::INT or Parser::DOUBLE tokens.

The flexc++ directive %interactive is provided since the calculator is a program actively interacting with its human user.

Here is the complete flexc++ specification file:

%interactive
%filenames scanner

%%

[ \t]                       // ignored

[0-9]+                      return Parser::INT;

"."[0-9]*                   |
[0-9]+("."[0-9]*)?          return Parser::DOUBLE;

.|\n                        return matched()[0];

25.6.2.3: Building the program

The calculator is built using bisonc++ and flexc++. Here is the implementation of the calculator's main function:

#include "parser/parser.h"

using namespace std;

int main()
{
    Parser parser;

    cout << "Enter (nested) expressions containing ints, doubles, *, + and "
            "unary -\n"
            "operators. Enter an empty line to stop.\n";

    return parser.parse();
}

The parser's files parse.cc and parserbase.h are generated by the command:

    bisonc++ grammar

The file parser.h is created only once, to allow the developer to add members to the Parser class occe the need for them arises.

The program flexc++ is used to create a lexical scanner:

    flexc++ lexer

On Unix systems a command like

    g++ -Wall -o calc *.cc -lbobcat -s

can be used to compile and link the source of the main program and the sources produced by the scanner and parser generators. The example uses the A2x class, which is part of the bobcat library (cf. section 25.6.1.5) (the bobcat library is available on systems offering either bisonc++ or flexc++). Bisonc++ can be downloaded from

http://fbb-git.gitlab.io/bisoncpp/.