15.9.4. The eval Functions

The eval functions are the heart of our query system. Each of these functions calls eval on its operand(s) and then applies its own logic: The OrQuery eval operation returns the union of the results of its two operands; AndQuery returns the intersection. The NotQuery is more complicated: It must return the line numbers that are not in its operand’s set.

To support the processing in the eval functions, we need to use the version of QueryResult that defines the members we added in the exercises to §12.3.2 (p. 490). We’ll assume that QueryResult has begin and end members that will let us iterate through the set of line numbers that the QueryResult holds. We’ll also assume that QueryResult has a member named get_file that returns a shared_ptr to the underlying file on which the query was executed.

OrQuery::eval

An OrQuery represents the union of the results for its two operands, which we obtain by calling eval on each of its operands. Because these operands are Query objects, calling eval is a call to Query::eval, which in turn makes a virtual call to eval on the underlying Query_base object. Each of these calls yields a QueryResult representing the line numbers in which its operand appears. We’ll combine those line numbers into a new set:

// returns the union of its operands' result sets
QueryResult
OrQuery::eval(const TextQuery& text) const
{
    // virtual calls through the Query members, lhs and rhs
    // the calls to eval return the QueryResult for each operand
    auto right = rhs.eval(text), left = lhs.eval(text);
    // copy the line numbers from the left-hand operand into the result set
    auto ret_lines =
         make_shared<set<line_no>>(left.begin(), left.end());
    // insert lines from the right-hand operand
    ret_lines->insert(right.begin(), right.end());
    // return the new QueryResult representing the union of lhs and rhs
    return QueryResult(rep(), ret_lines, left.get_file());
}

We initialize ret_lines using the set constructor that takes a pair of iterators. The begin and end members of a QueryResult return iterators into that object’s set of line numbers. So, ret_lines is created by copying the elements from left’s set. We next call insert on ret_lines to insert the elements from right. After this call, ret_lines contains the line numbers that appear in either left or right.

The eval function ends by building and returning a QueryResult representing the combined match. The QueryResult constructor (§12.3.2, p. 489) takes three arguments: a string representing the query, a shared_ptr to the set of matching line numbers, and a shared_ptr to the vector that represents the input file. We call rep to generate the string and get_file to obtain the shared_ptr to the file. Because both left and right refer to the same file, it doesn’t matter which of these we use for get_file.

AndQuery::eval

The AndQuery version of eval is similar to the OrQuery version, except that it calls a library algorithm to find the lines in common to both queries:

// returns the intersection of its operands' result sets
QueryResult
AndQuery::eval(const TextQuery& text) const
{
    // virtual calls through the Query operands to get result sets for the operands
    auto left = lhs.eval(text), right = rhs.eval(text);
    // set to hold the intersection of left and right
    auto ret_lines = make_shared<set<line_no>>();
    // writes the intersection of two ranges to a destination iterator
    // destination iterator in this call adds elements to ret
    set_intersection(left.begin(), left.end(),
                   right.begin(), right.end(),
                   inserter(*ret_lines, ret_lines->begin()));
    return QueryResult(rep(), ret_lines, left.get_file());
}

Here we use the library set_intersection algorithm, which is described in Appendix A.2.8 (p. 880), to merge these two sets.

The set_intersection algorithm takes five iterators. It uses the first four to denote two input sequences (§10.5.2, p. 413). Its last argument denotes a destination. The algorithm writes the elements that appear in both input sequences into the destination.

In this call we pass an insert iterator (§10.4.1, p. 401) as the destination. When set_intersection writes to this iterator, the effect will be to insert a new element into ret_lines.

Like the OrQuery eval function, this one ends by building and returning a QueryResult representing the combined match.

NotQuery::eval

NotQuery finds each line of the text within which the operand is not found:

// returns the lines not in its operand's result set
QueryResult
NotQuery::eval(const TextQuery& text) const
{
    // virtual call to eval through the Query operand
    auto result = query.eval(text);
    // start out with an empty result set
    auto ret_lines = make_shared<set<line_no>>();
    // we have to iterate through the lines on which our operand appears
    auto beg = result.begin(), end = result.end();
    // for each line in the input file, if that line is not in result,
    // add that line number to ret_lines
    auto sz = result.get_file()->size();
    for (size_t n = 0; n != sz; ++n) {
        // if we haven't processed all the lines in result
        // check whether this line is present
        if (beg == end || *beg != n)
            ret_lines->insert(n);  // if not in result, add this line
        else if (beg != end)
            ++beg; // otherwise get the next line number in result if there is one
    }
    return QueryResult(rep(), ret_lines, result.get_file());
}

As in the other eval functions, we start by calling eval on this object’s operand. That call returns the QueryResult containing the line numbers on which the operand appears, but we want the line numbers on which the operand does not appear. That is, we want every line in the file that is not already in result.

We generate that set by iterating through sequenital integers up to the size of the input file. We’ll put each number that is not in result into ret_lines. We position beg and end to denote the first and one past the last elements in result. That object is a set, so when we iterate through it, we’ll obtain the line numbers in ascending order.

The loop body checks whether the current number is in result. If not, we add that number to ret_lines. If the number is in result, we increment beg, which is our iterator into result.

Once we’ve processed all the line numbers, we return a QueryResult containing ret_lines, along with the results of running rep and get_file as in the previous eval functions.